Description

US A1 (19) United States (12) Patent Application Publication (10) Pub. No.: US 2006/ A1 Khamene et al. (43) Pub. Date: (54) TREE STRUCTURE BASED 2D TO 3D REGISTRATION (76) Inventors:

Information

Category:
## Automobiles

Publish on:

Views: 18 | Pages: 8

Extension: PDF | Download: 0

Share

Transcript

US A1 (19) United States (12) Patent Application Publication (10) Pub. No.: US 2006/ A1 Khamene et al. (43) Pub. Date: (54) TREE STRUCTURE BASED 2D TO 3D REGISTRATION (76) Inventors: Ali Khamene, Princeton, NJ (US); Charles Florin, Princeton, NJ (US); Frank Sauer, Princeton, NJ (US); James P. Williams, Princeton Junction, NJ (Us) Correspondence Address: Siemens Corporation Intellectual Property Department 170 Wood Avenue South Iselin, NJ (US) (21) Appl. No.: 11/303,564 (22) Filed: Dec. 16, 2005 Related US. Application Data (60) Provisional application No. 60/ 637,645,?led on Dec. 20, optimal pose is found. Publication Classi?cation (51) Int. Cl. G06K 9/00 ( ) (52) US. Cl /130; 382/154 (57) ABSTRACT A system and method for tree structure based two-dimen sional to three-dimensional registration are provided for receiving three-dimensional (3D) data indicative of vessels, segmenting the 3D data With a vessel tree, simulating two-dimensional (2D) data responsive to the segmented 3D data to form a simulated 2D image, receiving 2D data indicative of vessels, segmenting the received 2D data With a vessel tree,?nding a distance transform of the segmented 2D data to form a 2D distance map image, considering a set of poses as state vectors With the corresponding probability computed using the similarity measure computation, re sampling the pose vector to?nd a set of most probable poses and considering them as hypothesized poses, recomputing the projection and re-evaluating the probability of the hypothesized poses and updating the state vector until the f \ 1 Calibration : Parameters s Hypothesized / l w Pose (.e., translation Volumetric \?osllsjgllifpece projection ' k and rotation) Data (e.g.,. - Image ' 328 Segmentation. t. CTA, MRA) Method Simulator / Re-sampling M 326 / v f ( Projection vigslglérgrge T2552)? Match/Prob. pamilsozitermg Single/Multiple.... mage(s) (8'9 ' - Se mentation D from Binary ' Measur? ' parameters as contrast gll/lethod lma e Computatlon state vector) enhanced x-ray) g Patent Application Publication Sheet 1 0f 2 US 2006/ A1 922, m: 02 wcozmoezeeoo _ _Om H.uE é 2:.663 wumtbe mciomt. o m mo_ oc TREE STRUCTURE BASED 2D TO 3D REGISTRATION CROSS-REFERENCE TO RELATED APPLICATION [0001] This application claims the bene?t of US. Provi sional Application Ser. No. 60/637,645 (Attorney Docket No. 2004P21317US),?led Dec. 20, 2004 and entitled Tree Structure Based 2D-3D Registration, Which is incorporated herein by reference in its entirety. BACKGROUND [0002] TWo-dimensional (2D) to three-dimensional (3D) registration of a projection image to a volumetric data set typically involves three steps. First, a simulated projection image or digitally reconstructed radiograph (DRR) is com puted given the current relative position of the projection source and the pre-operative volume. Second, a similarity measure and/or difference measure is computed for charac terizing a metric to compare projection images to DRRs. Third, an optimization scheme searches through the param eter space, such as for six-dimensional rigid body motion, in order to maximize or minimize the similarity or difference measure. Once the optimum position is found, the DRR images are supposed to match the corresponding projection images. [0003] 2D to 3D registration is a Well-researched topic. It is generally known to?rst to compute the DRRs from the volumetric image in a Way that matches the real x-ray imaging results in terms of both brightness and contrast, and then to choose a Well-behaved similarity or difference mea sure that can robustly characterize a comparison metric for the images (see L Zollei: 2D-3D Rigid-Body Registration of X-Ray Fluoroscopy and CT Images, Masters Thesis, MIT Al Lab, August 2001, hereinafter Zollei ). Unfortu nately, in order to make such an algorithm practical, the computational time has to be reduced. [0004] State of the art implementations of such techniques suggest that for typical three-dimensional volume data sets, the computational time is on the order of a few minutes (see Zollei). Most of this time is spent on generating DRRs. The number of iterations over Which these lengthy computations have to be done is also very important. In Zollei, the research suggests random sampling of the DRRs and performing computations based only on these random samples in order to decrease the computation load. The main goal is to reduce the computational complexity. HoWever, this approach sac ri?ces robustness, 15 since less information is available to the optimizer to take an accurate step toward the global solutions. [0005] Aside from the intensity based registration method, there have been methods proposed in the literature that require a segmentation step. Feature-based registration methods have been heavily investigated for tissue images, and several such methods have been developed for vascular images. This class of methods includes surface-based meth ods (see A J Herline, J L Herring, J D Stefansic, W C Chapman, R L GalloWay, B M DaWant, Surface Registra tion for Use in Interactive, Image-Guided Liver Surgery, Computer Aided Surgery: 5(1), 2000, pp ), iterative closest point algorithms (see P J Besi, N D McKay, A method for registration of 3-D shapes, IEEE Transactions on Pattern Analysis and Machine Intelligence: 14, 1992, pp ; see also Y Ge, C R Maurer Jr, J M Fitzpatrick, Surface-based 3-D image registration using the Iterative Closest Point algorithm With a closest point transform, Medical Imaging 1996: Image Processing, Proceedings of SPIE, 1996), and landmark-based techniques (see I Dryden, K Mardia, Statistical Shape Analysis, John Wiley and Sons, NeW York, NY, 1998). This class also includes 2D to 3D registration methods that attempt to determine how to project vessel structure from a 3D image so as to best match the vessel structure in a 2D projection image of the same anatomy (see E Bullitt, A Liu, S R AylWard, and S M Pizer, Reconstruction of the intracerebral vasculature from MRA and a pair of projection views, Information Processing in Medical Imaging, Pouitney, VT, 1997, pp ; see also E Bullitt, A Liu, S RAylWard, C Coffey, J Stone, S Mukherji, and S M Pizer Registration of 3d cerebral vessels With 2d digital angiograms: Clinical evaluation, Academic Radiol ogy: 6, 1999, pp ). A model-based method is also described (see Stephen R. AyiWard, Julien Jornier, Sue Weeks, Elizabeth Bullitt, Registration and Analysis of Vascular Images, International Journal of Computer Vision, Volume 55, Issue 2-3 November-December 2003, Pages: ,2003). [0006] For many practical applications, especially inter ventional scenarios, registration time is crucial. Performing registration in real-time or close to real-time is a highly desirable feature that enables such applications. SUMMARY [0007] These and other drawbacks and disadvantages of the prior art are addressed by an exemplary system and method for tree structure based two-dimensional to three dimensional registration. [0008] An exemplary system for tree structure based two dimensional to three-dimensional registration includes a processor, a segmentation unit for segmenting 2D data and 3D data With respective vessel trees, and a distance trans form module for computing distance maps of the segmented 2D data to form a 2D distance map image, a particle?ltering based optimization technique to randomize, re-sampling, and test the validity (i.e., probability based on a similarity/ distance measure computed using 2D distance image and projection of the 3D points from the segmented 3D data) of the hypothesized poses in order to register the received 2D data relative to the projection of the received 3D data. An exemplary method for tree structure based two-dimensional to three-dimensional registration includes receiving three dimensional (3D) data indicative of vessels, segmenting the 3D data With a vessel tree, simulating two-dimensional (2D) image points through a projection given geometry of pro jection device and a pose responsive to the segmented 3D data to form a simulated 2D image, receiving 2D data indicative of vessels, segmenting the received 2D data With a vessel tree,?nding the distance transform of the segmented 2D data to form a 2D distance map image, randomizing, testing and re-sampling the hypothesized poses of the 2D data relative to the projection of the received 3D data based on a similarity/ distance measure, following the particle?lter based optimization scheme. [0009] These and other aspects, features and advantages of the present disclosure Will become apparent from the fol lowing description of exemplary embodiments, which is to be read in connection with the accompanying drawings. BRIEF DESCRIPTION OF THE DRAWINGS [0010] The present disclosure teaches a system and method for tree structure based two-dimensional to three dimensional registration in accordance with the following exemplary?gures, in which: [0011] FIG. 1 shows a schematic diagram of a system for tree structure based two-dimensional to three-dimensional registration in accordance with an illustrative embodiment of the present disclosure; and [0012] FIG. 2 shows a data and control?ow diagram of a system and method for tree structure based two-dimensional to three-dimensional registration in accordance with an illustrative embodiment of the present disclosure. DETAILED DESCRIPTION OF PREFERRED EMBODIMENTS [0013] A system and method are provided for rigidly registering volumetric data to a set of projection images, such as those generated by an x-ray device or a linear accelerator, for example. In an interventional or radiation treatment scenario, it is desired to relate the intra-procedural images to the pre-procedural volumetric data, which might have been acquired days before a given operation. [0014] As shown in FIG. 1, a system for tree structure based two-dimensional to three-dimensional registration, according to an illustrative embodiment of the present disclosure, is indicated generally by the reference numeral 100. The system 100 includes at least one processor or central processing unit (CPU) 102 in signal communication with a system bus 104. A read only memory (ROM) 106, a random access memory (RAM) 108, a display adapter 110, an I/O adapter 112, a user interface adapter 114, a commu nications adapter 128, and an imaging adapter 130 are also in signal communication with the system bus 104. A display unit 116 is in signal communication with the system bus 104 via the display adapter 110. A disk storage unit 118, such as, for example, a magnetic or optical disk storage unit is in signal communication with the system bus 104 via the I/O adapter 112. A mouse 120, a keyboard 122, and an eye tracking device 124 are in signal communication with the system bus 104 via the user interface adapter 114. [0015] A two-dimensional (2D) imaging device 132 or external image storage device and a three-dimensional (3D) imaging device 133 or external image storage device are each in signal communication with the system bus 104 via the imaging adapter 130. A segmentation unit 170 and a distance unit 180 are also included in the system 100 and in signal communication with the CPU 102 and the system bus 104. While the 2D to 3D registration unit 180 is illustrated as coupled to the at least one processor or CPU 102, this component is preferably embodied in computer program code stored in at least one of the memories 106, 108 and 118, wherein the CPU 102 executes the computer program code. [0016] Turning now to FIG. 2, control and data?ow for tree structure based two-dimensional to three-dimensional registration is indicated generally by the reference numeral 300. Here, volumetric data 310, such as computed tomo graphic angiography (CTA) or magnetic resonance angiog raphy (MRA), is acquired from a data storage device or the scanner and passed to a 3D or volumetric vessel tree segmentation block 312. The block 312 passes segmented 3D data to a projection image simulator 316, which also receives calibration parameters 314. [0017] Projection image data 318 may be single or mul tiple images such as contrast and enhanced x-ray, for example, which is also retrieved from a data storage device or intra-operative scanning device. The projection image data 318 is passed to a 2D image vessel tree segmentation block 320, which, in turn, passes segmented 2D data to a transform block that extracts the distance map from the segmented binary image. [0018] The 2D distance map image is passed to a com putation block 324 that also receives the projection of the 3D data from the block 316. The computation block 324 esti mates the similarity measure or matching criterion, which can be thought of as the probability of the pose using the projection of 3D data (i.e., from projection image simulation block 316) that was computed. The particle-?ltering state vectors indicated by block 326 are a set of the most probable poses, which are the input of re-sampling block 328. The re-sampling block, in turn, re-samples the pose data, and passes re-sampled data as a hypothesized (randomized around the most probable) pose, such as translation and rotation for example. The hypothesized pose is fed back to the projection image simulator 316. [0019] The presently disclosed method utilizes tree-like structures for both the volumetric and projection images. A well-de?ned image metric is established for evaluating the accuracy of registration for a given set of parameters. In addition, a particular particle-?ltering scheme is used. This scheme is based on a Bayesian framework as the engine for performing a maximization or minimization of a similarity or metric quanti?er. A similarity or metric measure is de?ned to quantify the distance between the synthetic projection image based on a hypothesized pose and the real segmented projection images. [0020] The similarity or metric measure is computed based on the distance transform of the segmented structures in the projection images. The algorithm contains several building blocks, and is relatively simple to implement with low computational complexity. This algorithm has the potential to be used for real-time applications, where update for the pose has to be calculated at a high rate. [0021] In an exemplary embodiment, a fast and automated method is provided for aligning images of tree structures, particularly images of a human vessel tree. While the general task of aligning images of tubes is difficult, the speci?c task of aligning vascular images introduces addi tional complications including vascular network changes and non-rigid deformations, such as changes in the number, size, and relative location of the vessels in the images. Yet vessels can still provide an excellent basis for registration. [0022] Vessels are often well distributed throughout an organ and thereby capture misalignment within that organ. On the other hand, surfaces and landmarks, which are commonly used in other methods, may be poorly correlated with internal deformations. Additionally, compared to volu metric registration methods, the sparseness, multi-scale geo metric properties and network con?guration of the vessels may make vessel-based registration methods faster and more broadly applicable. This exemplary embodiment method for registration includes the following primary building blocks. [0023] A volumetric segmentation block automatically segments the vascular structure from volumetric data sets, such as by using particle?lters for segmentation of vascular structures with a Kalman-directed prior knowledge. A cen terline of the segmentation is extracted and saved in a multi-element tree data structure format, such as a B-tree. This increases the performance of traverse operations. This process effectively reduces the amount of the volumetric data to a minimum required to accurately present the tree structure or vessel tree. An advantage here is that the amount of time spent to compute the synthesized projection images of the vessel tree is much smaller than the time it takes to compute the projection of the full 3D volume. [0024] A projection segmentation block automatically segments the vascular structure from projection images based on the method of using particle?lters for segmenta tion of vascular structures with a Kalman-directed prior knowledge. The same process as it is explained in the previous item can be applied here to extract the binary mask representing the segmentation. [0025] A distance measurement block de?nes a well behaved metric in order to quantify the closeness of a synthetically projected vessel tree image given the calibra tion parameters, such as those estimated off-line through a calibration process or available based on geometrical prop erties of the imaging devise provided by the manufacturer, and a hypothetical pose. The distance transform of the segmented projection image(s) in arbitrary dimensions is computed using a linear time algorithm. The multi-element tree array of the three dimensional segmented structure is traversed, the projected points are computed based on the assumed pose, the corresponding location in the distance transform is looked up and the distance values are accumu lated. The?nal result is a geometrically correct distance measure between the two graphs (i.e., projected 3D graph and segmented 2D graph), and it is valid for large discrep ancies between the two structures. [0026] The particle?lter framework is used on registration parameters, such as pose, as an optimizer to maximize or minimize the match or difference measure. A particle?lter method is a sequential Monte-Carlo technique that can be used to estimate the Bayesian posterior density function with a set of samples. In the context of rigid registration, using a particle?lter method, this embodiment estimates the prob ability density function (PDF) of pose parameters consid ered as the feature space (i.e., state vector). Each sample in the feature space is associated with the weight determining its impact on the PDF. Advantages of utilizing the particle?ltering approach for registration include?rst to decrease the chance of converging to a local optimum for the pose and second to increase the capture range of the optimization process. [0027] The optimization process can be explained as fol lows. First, the process starts with an initial particle distri bution as the prior (pose parameters and the probability). This could be a Gaussian distribution of particle centered around a?rst guess for the pose. It should be noted that the width of the distribution here in?uences the capture range of the registration process as a whole. Second, these particles are considered as current state particles. [0028] Third, some noise is added to the state particles to dislocate them randomly. The new weights associated with modi?ed pose particles are computed using the method described previously (i.e., through computation of a simi larity measure). It should be noted that weight computation here is quite fast and it is based on a distance transform that is only needed to be computed once at the beginning of the operation. These weights can serve as the probability of a particle s pose parameters being correct. [0029] Fourth, the current state and the modi?ed particles are then processed into a re-sampling step to normalize the weights. Re-sampling allows for greater accuracy in esti mating the PDF. The overall effect of the re-sampling step is that particles with high relative weights contribute more to the PDF. Therefore, they increasingly affect the re-sampled particle, while low-weight particle presence in re-sampled particles decreases over time or iterations. Fifth, the process is resumed by returning to the second step. [0030] Thus, a system and method for tree structure based two-dimensional to three-dimensional registration have been disclosed for receiving three-dimensional (3D) data indicative of vessels, segmenting the

Related Search

Similar documents

We Need Your Support

Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks