Premium
SU‐FF‐J‐103: A Robust Marker Registration Algorithm
Author(s) -
Parra A,
Narasimhan G,
Samant S
Publication year - 2005
Publication title -
medical physics
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.473
H-Index - 180
eISSN - 2473-4209
pISSN - 0094-2405
DOI - 10.1118/1.1997649
Subject(s) - bipartite graph , algorithm , singular value decomposition , mathematics , robustness (evolution) , missing data , computer science , artificial intelligence , graph , combinatorics , statistics , biochemistry , chemistry , gene
Purpose: We present a novel marker registration algorithm for rigid‐body transformations that minimizes sum of least squares between two point sets, and requires no user intervention to handle missing markers. Method and Materials: The novel registration algorithm computes the sum of squared distances by finding the minimum weighted matching of a dense bipartite graph (DPG). The space of rigid‐body transforms (3 translations and 3 rotations) is explored using a branch‐and‐bound method. The minimum weighted bipartite match is calculated using a modified Dijkstra's algorithm[1]. The branch‐and‐bound method is an extension to 3D of the method in [2]. Unlike conventional singular value decomposition (SVD), i) DPG works with point sets with different cardinalities; and ii) no homology or correspondence has to be defined between reference and target point sets. These advantages provide our algorithm with greater robustness for automatic marker detection, and handling missing markers. Though DPG is not limited by number of markers (N), here N=3 to 7 was used to simulate clinical conditions. Results: DPG yielded an accuracy of <0.1mm translational and <0.1° rotational errors, which are within the precision of back projection errors. It was validated using simulated portal images and a high precision table. It was tested on clinical portal imaging data to validate robustness for missing markers. Conclusion: DPG provides an accurate and robust point based registration that works with missing markers and different cardinalities, which can be used in conjunction with automatic marker detection.