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

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; and (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 and propose a pseudopolynomial time algorithm. Using three presegmented images, matching and reconstruction of brachytherapy seeds using the Hungarian algorithm achieved complete 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.9 mm for incorrectly matched seeds. The maximum seed reconstruction error in each implant was typically around 1.32 mm. Both on synthetic data and in phantom experiments, matching rate and 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 and features.

FTRAC--a robust fluoroscope tracking fiducial.

C-arm fluoroscopy is ubiquitous in contemporary surgery, but it lacks the ability to accurately reconstruct three-dimensional (3D) information. A major obstacle in fluoroscopic reconstruction is discerning the pose of the x-ray image, in 3D space. Optical/magnetic trackers tend to be prohibitively expensive, intrusive and cumbersome in many applications. We present single-image-based fluoroscope tracking (FTRAC) with the use of an external radiographic fiducial consisting of a mathematically optimized set of ellipses, lines, and points. This is an improvement over contemporary fiducials, which use only points. The fiducial encodes six degrees of freedom in a single image by creating a unique view from any direction. A nonlinear optimizer can rapidly compute the pose of the fiducial using this image. The current embodiment has salient attributes: small dimensions (3 x 3 x 5 cm); need not be close to the anatomy of interest; and accurately segmentable. We tested the fiducial and the pose recovery method on synthetic data and also experimentally on a precisely machined mechanical phantom. Pose recovery in phantom experiments had an accuracy of 0.56 mm in translation and 0.33 degrees in orientation. Object reconstruction had a mean error of 0.53 mm with 0.16 mm STD. The method offers accuracies similar to commercial tracking systems, and appears to be sufficiently robust for intraoperative quantitative C-arm fluoroscopy. Simulation experiments indicate that the size can be further reduced to 1 x 1 X 2 cm, with only a marginal drop in accuracy.