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

Purpose: Intraoperative dosimetric quality assurance in prostate brachytherapy critically depends on discerning the 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. Method: 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 network flow problem, which has salient features: (a) extensively studied exact solutions, (b) performance claims on the space-time complexity, (c) optimality bounds on the final solution. A fast implementation is realized using the Hungarian algorithm. Results: We prove that two images can correctly match only about 67% of the seeds, and that a third image renders the matching problem to be of non-polynomial complexity. We utilize the special structure of the problem and propose a pseudo-polynomial time algorithm. Using three images, MARSHAL achieved 100% matching in simulation experiments; and 98.5% in phantom experiments. 3D reconstruction error for correctly matched seeds has a mean of 0.63 mm, and 0.91 mm for incorrectly matched seeds. Conclusion: Both on synthetic data and in phantom experiments, matching rate and reconstruction accuracy were found to be sufficient for prostate brachytherapy. The algorithm is extendable to deal with arbitrary number of images without loss in speed or accuracy. The algorithm is sufficiently generic to be used for establishing correspondences across any choice of features in different imaging modalities.