Matching and reconstruction of brachytherapy seeds using the Hungarian algorithm (MARSHAL)

TitleMatching and reconstruction of brachytherapy seeds using the Hungarian algorithm (MARSHAL)
Publication TypeJournal Article
Year of Publication2005
AuthorsJain, A. K., Zhou Y., Mustufa T., E. Burdette C., Chirikjian G., & Fichtinger G.
JournalJournal of Medical Physics
Date PublishedNov
KeywordsAlgorithms, Automated, Brachytherapy, Calibration, Computer Simulation, Computer-Assisted, Humans, Image Interpretation, Imaging, Male, methods, Models, Numerical Analysis, Pattern Recognition, Phantoms, Prostatic Neoplasms, Radiographic Image Enhancement, Radiographic Image Interpretation, Radiometry, Radiotherapy, Radiotherapy Dosage, Radiotherapy Planning, Reproducibility of Results, Statistical, Theoretical, Three-Dimensional, Time Factors, Ultrasonography

Intraoperative dosimetric quality assurance in prostate brachytherapy critically depends on discerning the three-dimensional (3D) locations of implanted seeds The ability to reconstruct the implanted seeds intraoperatively will allow us to make immediate provisions for dosimetric deviations from the optimal implant plan A method for seed reconstruction from segmented C-arm fluoroscopy images is proposed The 3D coordinates of the implanted seeds can be calculated upon resolving the correspondence of seeds in multiple x-ray images We formalize seed-matching as a combinatorial optimization problem, which has salient features: (a) extensively studied solutions by the computer science community; (b) proof for the nonexistence of any polynomial time exact algorithm;, (c) a practical pseudo-polynomial algorithm that mostly runs in O(N3) time using any number of images We prove that two images are insufficient to correctly match the seeds, while a third image renders the matching problem to be of nonpolynomial complexity We utilize the special structure of the problem, propose a pseudopolynomial time algorithm Using three presegmented images, matching, reconstruction of brachytherapy seeds using the Hungarian algorithm achieved complete matching in simulation experiments;, 98 5% in phantom experiments 3D reconstruction error for correctly matched seeds has a mean of 0 63 mm, and 0 9 mm for incorrectly matched seeds The maximum seed reconstruction error in each implant was typically around 1 32 mm Both on synthetic data, in phantom experiments, matching rate, reconstruction error achieved using presegmented images was found to be sufficient for prostate brachytherapy The algorithm is extendable to deal with arbitrary number of images without any loss in speed or accuracy The algorithm is sufficiently generic to provide a practical solution to any correspondence problem, across different imaging modalities, features

PerkWeb Citation KeyJain2005e