Report CopyRight/DMCA Form For : Chapter 31 Landmark Based Registration Using Features
Handbook of Medical Imaging Processing and Analysis I Bankman Editor Academic Press 2000 Chapter 31 Landmark Based Registration Using Features Identi ed Through Differential Geometry Xavier Pennec Nicholas Ayache Jean Philippe Thirion INRIA Projet Epidaure Registration of 3D medical images consists in comput
Chap 31 Landmark Based Registration Using Features Identified Through Differencial Geometry 500. Figure 1 Differential geometry of 3D curves and surfaces Left principal directions and curvatures of a surface. Right Fre net trihedron of a 3D curve and first differential invariants curvature and torsion. 1 1 Definition and Properties We have proposed another method to compute them in. 39 38 for the case of iso intensity surfaces Our method. Differential Geometry of 3D Surfaces is based on the use of the implicit functions theorem Ba. Let us first recall briefly some results of differential geom sically we have shown that the crest lines can be extracted. etry about surface curvatures a good introduction to these as the intersection of two implicit surfaces f I and. notions can be found in 9 or in 21 In this paper we e 0 where f represents the intensity value of the im. call a smooth surface a 3D surface which is continuously age I an iso intensity threshold and e k1 t1 is the. differentiable up to the third order At any point P of such extremality function see Figure 2 left We have pro. a 3D surface we can define one curvature per direction t posed an algorithm called the Marching Lines to auto. in the tangent plane of the surface This directional cur matically extract these crest lines This algorithm can also. vature kt is the curvature of the 3D curve defined by the be used to overcome some orientation problems mainly. intersection of the plane P t n with the surface where due to the fact that the principal directions are only di. n is normal to the surface rections and not oriented vectors by locally orienting the. Except for the points where this curvature kt is the principal directions along the extracted lines. same for all the directions t which are called umbilic In fact for each point of the surface two different ex. points the total set of curvatures can be described with tremality coefficients can be defined corresponding to the. only two privileged directions t1 and t2 and two asso two principal curvatures. ciated curvature values k1 kt1 and k2 kt2 which, are called respectively the principal directions and the as. sociated principal curvatures of the surface at point P as e1 k1 t1 and e2 k2 t2 1. shown in Figure 1 These two principal curvatures are. the extrema of the directional curvatures at point P and. except for umbilic points one of these two is maximal We found experimentally that the maxima in absolute. in absolute value let us say k1 we call this the largest values are more stable landmarks than the minima crests. curvature in order not to be mistaken with the maximal or rifts maxima are stable whereas the loci in a valley. curvature We simply call the second principal curva where the ground floor is the flattest minima are very. ture the other principal curvature k2 sensitive to small perturbations in the data. We call extremal lines all the lines defined as the zero. Extremal Lines crossings of either e1 or e2 There is therefore four major. different types of extremal lines depending of whether. The crest lines are intuitively the loci of the surface where the corresponding curvature is the largest or the second. the curvature is locally maximal More precisely we one and whether it is a local maximum or minimum Fur. define them as the loci of the surface where the largest thermore the signs of the largest and second curvatures. curvature k1 is locally maximal in absolute value in help to distinguish between four additional sub types of. the associated principal direction t1 In 26 it is shown extremal lines leading to a classification into 16 types. that these points can be defined as the zero crossing of an The crest lines are two of them positive largest curvature. extremality function e which is the directional derivative maxima k1 0 and e1 t1 0 and negative largest. of k1 in the direction t1 curvature minima k1 0 and e1 t1 0. This draft paper is provided to ensure timely dissemination of scholarly and technical work Copyright and all rights therein are retained by authors or by other. copyright holders All person copying this information are expected to adhere to the terms and constraints invoked by each author s copyright This work may not be. reposted without the explicit permission of the copyright holder. 501 Handbook of Medical Imaging Processing and Analysis IV Registration. Figure 2 Left Crest lines as the intersection of two implicit surfaces Right Definition of the extremal points as the. intersection of three implicit surfaces,Extremal Points Geometric Characteristics. Let us begin with the points on a surface We have already. We now define the extremal points as the intersection of seen Figure 1 left that any such point could be provided. the three implicit surfaces f I e1 0 and e2 0 with a trihedron n t1 t2 formed by the normal to the. The notions of extremal lines and extremal points are surface and the two principal directions As our points are. closely related to the notion of corner points in 2D im also on extremal lines we could provide them with the. ages as defined in 20 27 and 8 A study of the differential characteristics of 3D curves Figure 1 right. evolution in 2D of corner points with respect to the scale i e the Fre net trihedron t nc b where t is the tangent. can be found in 13 A similar study on the scale space to the curve nc its normal and b the binormal. behavior of the extremal lines and the extremal points was. These two trihedrons are not the same as the extremal. presented in 12, lines are generally not lines of curvature However as. Extremalities e1 and e2 are geometric invariants of the curve is embedded in the surface the tangent to the. the implicit surface f I they are preserved with curve t is constrained to be in the tangent plane of the. rigid transforms rotations and translations of the object surface spanned by t1 t2 Thus there are two indepen. Therefore the relative positions of the extremal points are dent parameters characterizing the relative configuration. also invariant with respect to a rigid transformation i e of the trihedron we can measure two angles t dt1. for two different acquisitions of the same subject There and nd c n These characteristics are invariant with. are 16 different types of extremal points depending on respect to rigid transformations. the type of extremality local minimum or maximum of Two other invariants come from the surface principal. the extremalities e1 and e2 and the signs of k1 and k2 curvatures k1 and k2 One could also think to add the. This classification can be used to reduce the complexity curvature k the torsion of the curve and the geodesic. of the matching algorithm torsion g of the curve with respect to the surface but it. However the intuitive interpretation of extremal points appears that k and g are completely determined by the. is not straightforward The extremal lines are 3D curves surface invariants k cos k1 cos2 k2 sin2 and. for which we are able to compute the curvature but the ex g k2 k1 cos sin Thus we are left with the. tremal points are generally not the points of the extremal torsion of the curve. lines whose curvature is locally maximal Even if they However the computation of the Fre net trihedron. are not extremal curvature points the extremal points are t g b and the curve torsion has to be done on the. very well defined and there is no reason for their loca extremal curve itself after its extraction If this can be. tions along the extremal lines to be less precise that the done directly on the polygonal approximation a much. lines positions themselves because the precision of the better method is to compute the characteristics on a local. computation of k1 and k2 is approximately the same B spline approximation of the curve 15. This draft paper is provided to ensure timely dissemination of scholarly and technical work Copyright and all rights therein are retained by authors or by other. copyright holders All person copying this information are expected to adhere to the terms and constraints invoked by each author s copyright This work may not be. reposted without the explicit permission of the copyright holder. Chap 31 Landmark Based Registration Using Features Identified Through Differencial Geometry 502. Figure 3 Extraction of the Extremal Points An empty circle denotes a positive value whereas a filled circle indicates. a negative one, 1 2 The Automatic Extraction of the Ex defined as the intersection of the three implicit surfaces. tremal Points f I e1 0 and e2 0 The method varies according. to the type of interpolation or convolution function used. In practical cases e1 and e2 can be computed for each to extend continuously the three values at the vertices of. point of the 3D image with the equations described in the cubic cell to the entire cell The tri linear interpolation. 37 directly from the differentials of the intensity func is a good first order approximation. tion of the image f We compute these differentials with The extraction of a polygonal approximation of the. linear filtering using the convolution of the discrete image crest lines with some warranties about the topology and. with the differentials of the Gaussian function e kxk 2 the orientation of the reconstructed 3D curves is presented. The normalization of these filters is not straightforward with the marching line algorithm 39 Its extension to the. we use the responses to simple polynomials as proposed extraction of the extremal points was performed in 38. in 26 We choose the Gaussian function because it is We briefly recall here the method on a very simple ex. isotropic a prerequisite if we are looking for geometric ample where the iso surface is a triangle in the cell This. invariants for rigid transformations Different values of operation can be extended to any configuration of the val. can be chosen depending on the level of noise in the 3D ues of f and e1 while ensuring that the extracted segments. images Changing is somewhat equivalent to changing form a continuous and closed 3D curve except when f or. the scale at which we look for extremal lines and points e1 is not defined for instance at the borders of the im. The hypothesis that the iso surfaces are a good repre age The original algorithm also considers orientation. sentation of the surface of organs for the case of medical problems which allows us to distinguish between mini. images is a prerequisite sometimes the iso surface can mum and maximum extremal points. be extracted directly from the 3D image such as the skin. The first step Figure 3 left is to extract the iso surface. surface in Magnetic Resonance Image MRI or the bones. within the cell The iso surface intersects the edges on the. in X ray scanner images For other soft tissues such as for. cell with the value I Computing by linear interpolation. the brain surface a pre segmentation step is required to. along the edges the points where f I we get the three. isolate the brain from the rest of the data This can be done. points Q1 Q2 Q3 Since we are using a tri linear inter. with a combination of mathematical morphological oper. polation within the cell the intersection of the iso surface. ators filtering and the search for connected parts or with. with the cell is the triangle Q1 Q2 Q3, an automatic surface edge extractor such as the zero. crossing of the image Laplacian In all cases the final In the second step Figure 3 middle we compute the. step of the segmentation is performed using iso surface values of e1 for Q1 Q2 Q3 by linear interpolation. techniques along the edges of the cubic cell If they have the same. sign there is no extremal line of e1 in this cell Otherwise. we look for the two points along the triangle edges where. Computation of the Extremal Points in a 8 Voxel Cell. the interpolated value of e1 is null we get the two points. One solution to get the set of extremal points of the 3D P1 P2 which form a segment This is the approxima. image is to compute e1 and e2 for all the voxels of the 3D tion of the extremal line within the cell. image and then to consider individually each cubic cell The last step Figure 3 right is to compute the position. formed with 8 voxels 8 cell as shown in Figure 3 There of the extremal point Since P1 and P2 lie on the surface. are therefore three values defined for each vertex of the of the cell we compute the value of e2 at these points. cube f e1 and e2 The extremal points in that 8 cell are with a bi linear interpolation of e2 in the faces If the. This draft paper is provided to ensure timely dissemination of scholarly and technical work Copyright and all rights therein are retained by authors or by other. copyright holders All person copying this information are expected to adhere to the terms and constraints invoked by each author s copyright This work may not be. reposted without the explicit permission of the copyright holder. 503 Handbook of Medical Imaging Processing and Analysis IV Registration. Figure 4 Left An axial slice of a 3D CT image of a dry skull in Plexiglas Middle and right the crest lines extracted. on this image The iso intensity was manually chosen to delimit the skull Original 3D Image courtesy of GE CGR. Buc France, two values have the same sign there is no extremal point the inverse of its length This method reduces drastically. on this cell Otherwise as is shown here we compute the number of computations to perform compared to the. its position P by interpolating the zero value along the extensive implementation typically one uses 10 of the. segment number of voxels as seeds Even if the set of generated. extremal points is not complete it is generally sufficient. to perform a reliable 3D registration,Randomized Extraction of Extremal Points. Of course we could look for extremal points in all the. possible cells of the image excepting regions of null gra 1 3 Example of Extracted Extremal Lines. dient and umbilics However it is much more efficient to and Points. randomize the search we start with seed cells randomly. chosen in the 3D image and discard the ones for which In Figure 4 we can see an example of the lines extracted. the sign of f I is the same for all the vertices Then automatically with a manual choice of the iso intensity. we compute the values of e1 for the 8 vertices of the cell threshold in a CT image of a dry skull Some of the 550. Once again a simple test discards the cells which are not crest lines may be recognized as anatomical landmarks. crossed by a k1 extremal line the sign of e1 is the same such as the orbits or the inferior border of the mandible. for the 8 vertices If there is an extremal line we extract The lines are colored by the sign of the e2 extremality. it from end to end using the Marching Lines algorithm Thus extremal points are located at the color changes. we follow the extremal line marching from one cell to along the lines There are around 3000 such extremal. the next points, At each point of the polygonal approximation of the In an MR image the surface of the brain is not very. crest line we compute the second extremality e2 by bi well defined by an iso intensity of the image A pre. linear interpolation If there is a sign change we compute segmentation step is usually needed to isolate the brain. the extremal point on the segment of the extremal line that from the rest of the data This can be done with a combi. we are currently following nation of mathematical morphological operators filtering. The randomized implementation of the Marching Lines and the search for connected parts or with an automatic. allows us to extract the main extremal lines i e the surface edge extractor such as the zero crossing of the. longest ones which experimentally appeared to be the image Laplacian In Figure 5 we used a segmentation of. most reliable ones of the 3D image with only very few the surface of the brain and extracted the crest lines on. seeds with respect to the total number of voxels ran this surface Lines in red with a positive largest curva. domly distributed in the 3D images The probability of ture roughly correspond to sulci whereas blue lines with. missing an extremal line is approximately proportional to a negative largest curvature could be interpreted as gyri. This draft paper is provided to ensure timely dissemination of scholarly and technical work Copyright and all rights therein are retained by authors or by other. copyright holders All person copying this information are expected to adhere to the terms and constraints invoked by each author s copyright This work may not be. reposted without the explicit permission of the copyright holder. Chap 31 Landmark Based Registration Using Features Identified Through Differencial Geometry 504. Figure 5 Left A sagittal slice of a 3D MR image Middle and right 3D views of the extremal lines extracted. superimposed on the surface of the brain Original MR images and segmentation courtesy of Prof R Kikinis Brigham. and Women s Hospital Boston, 2 Rigid Registration a rigid transformation is computed by superimposing the. Fre net frames and used to index the match in a new accu. mulator sampling the rigid transformation space Hough. Let us now consider two images of the same modality and transform step Densely populated cells in this second ac. of the same patient but in a different position We extract cumulator are detected as rigid body transformations that. extremal lines on both images The problem is to put into are candidates to match a large number of crest points. correspondence the two sets of lines the model and the For each such cell a refined least squares transformation. scene which is often called the matching step and to is computed using the matches indexed in this cell. compute the best rigid transformation that superimposes. the matched lines, It is important to note that a global registration algo 2 2 Extremal Points Registration using. rithm for instance superimposing the barycenters of all Alignment. points and the inertia axes will often fail due to the oc. With the development of completely automated methods. clusion Indeed the images being taken in different po. to extract crest lines and the higher resolution of images. sitions the region of interest are frequently different in. the number of crest lines drastically increased leading. the two images leading to crest lines and extremal points. to a much higher density of invariants in the hash table. present in one image and not in the other The images. This could lead to an important number of false positives. noise will also induce the extraction of spurious lines and. that would overwhelm the correct matches The maxi,points in different parts of the two images. mum complexity would then be reached and the algorithm. could even provide a wrong answer To address this prob. 2 1 Curve Registration lem Thirion reduced once again the image information by. keeping only a very small number of specific points on the. Several algorithms adapted from computer vision have crest lines the extremal points Typically they represent. been proposed and used over time In 15 Gue ziec only 16 of the number of crest line points but we are. matches the crest lines using a combination of geometric still left with 2000 to 5000 points in each image. hashing 22 and Hough transform see for instance 23 Thirion used in 37 another computer vision based. The basic idea was to index each point of each model crest technique alignment or prediction verification 3 17. line in a hash table using its invariant characteristics At The basic idea is to compute the registration of each triplet. recognition time the invariants of each scene crest line of model points with each triplet of scene points super. point are used to recover thanks to the hash table the pos impose the two sets of points using this transformation. sible matches with model points geometric hashing step and verify this match using an iterative closest point al. For each match i e couple of model and scene points gorithm see Section 2 4 However the search for com. This draft paper is provided to ensure timely dissemination of scholarly and technical work Copyright and all rights therein are retained by authors or by other. copyright holders All person copying this information are expected to adhere to the terms and constraints invoked by each author s copyright This work may not be. reposted without the explicit permission of the copyright holder. 505 Handbook of Medical Imaging Processing and Analysis IV Registration. patible triplets in the model and the scene can be reduced keep the matches that are above a given threshold typi. since there are some unary invariants the principal cur cally 10 of the number of extremal points. vatures k1 and k2 secondary invariants e g the dis. tance between the two points or the relative orientation. of the surface normals and the principal curvatures and Clustering Compatible Matches and Verification For. even ternary invariants involving the whole triplet of ex each individual match we maintain during the recognition. tremal points Thirion used 18 such invariants for each step an estimation of the associated transformation by fus. triplet pre computed and stored them in a hash table to ing the transformations between confirming frames To. retrieve in constant time the compatible triplets Thus the group matches belonging to the same rigid substructure. complexity of the algorithm is O n4 since there are n3 we run a very simple clustering algorithm on the associ. triplets and a verification of O n for each triplet match ated transformation Indeed up to measurement errors. In practice this complexity is not reached as we can stop frames should undergo a similar transformation within a. as soon as a given number of points is matched after veri single substructure Each cluster is then refined by an it. fication typically 10 erative closest neighbor technique where we enforce sym. metry of the matches and verify their validity with a 2. 2 3 Substructure Matching with Frame, Matching Crest Lines In order to reduce once again the. We came back in 16 to geometric hashing but the idea complexity of the algorithm we exploited in this method. was to use all the geometric information on the features the structure of the extremal points they belong to crest. while taking great care of the uncertainty handling for the lines The principle is to consider each model crest line. algorithm to be robust see 29 for an analysis of recog as a different object Index all model lines in the same. nition algorithms with uncertain geometric features In hash table we retrieve at recognition time the model lines. addition to the point s position we can add the normal corresponding to each scene crest line. vector n and the two principal directions t1 and t2 of the However different crest line matches can correspond. surface to constitute a local coordinate system or a frame to different transformations Thus we run once again our. In this context each medical image is modeled by a set clustering algorithm on the transformations to find out the. of frames and the matching problem is to find the corre compatible line matches and we obtain a single transfor. spondences between two subsets of frames that are in the mation from the model to the scene image. same configuration in the two images up to a global. rigid transformation,2 4 ICP on Frames, Invariant Representation Preprocessing Step To ob When images are close enough one can use still another. tain an invariant representation with respect to the global algorithm the Iterative Closest Point 5 41 The basic. position and orientation of the considered structure we principle is the following For each scene point we look. can express the configuration of all frames relative to one for the closest point in the model with the current trans. frame called the basis For efficiency this representa formation compute a new rigid transformation with these. tion is stored in a hash table and for correctness we in matches and iterate the process until convergence. clude the uncertainty of each invariant As only part of Of course since we have more geometric information. the frames are in the same configuration in the two im than just the point position we use a generalization the. ages the one chosen as the basis may not be present in Iterative Closest Feature 29 The idea is to use a higher. the other image The preprocessing step is thus repeated dimensional space for the closest point search In our. with each frame as the basis case the space is made of the extremal point position the. trihedron n t1 t2 and the unary invariants k1 and k2. Recognition Step Choosing a frame of the second The important point is to set an appropriate metric on this. structure the scene as the basis we compute the invari space in order to combine efficiently the different units. ant representation and retrieve thanks to the hash table of measurement In our algorithm this is done using the. what are the compatible model frame couples If the basis inverse of the covariance matrix of the features This ma. belongs to a common substructure then a significant num trix can be re estimated after convergence and the whole. ber of frames are in the same configuration with respect to process iterated However we did not observe a critical. it We then match the model and scene bases Fig 6 influence of the covariance matrix values as soon as it is. This process is repeated for every extremal point as the approximately respecting the variation range of the differ. basis to find its possible matches in the model and we only ent components. This draft paper is provided to ensure timely dissemination of scholarly and technical work Copyright and all rights therein are retained by authors or by other. copyright holders All person copying this information are expected to adhere to the terms and constraints invoked by each author s copyright This work may not be. reposted without the explicit permission of the copyright holder. Chap 31 Landmark Based Registration Using Features Identified Through Differencial Geometry 506. Figure 6 Preprocessing the 6D invariant vector associated with every couple of model frames is computed with. its error zone and used as an index for the couple in the hash table Recognition for each scene frame couple we. compute the 6D invariant vector and retrieve through the hash table every compatible model frame couple For each. such couple we tally a vote for the matching of the reference frames here the match F mi F sj scores 2. Figure 7 Example of registered crest lines between two CT skull images of the same phantom acquired in two different. positions Extremal points are represented by a color change from yellow to blue on the lines Left Front view with. all crest lines from the two skulls after registration Middle Left view of the matched crest lines Right Closeup on. the occipital foramen on the right In this last image the width of a line is a tenth of a voxel which shows the very. precise registration of these extremal points One can also see that the trihedron part of the matched frames is very. well conserved, This draft paper is provided to ensure timely dissemination of scholarly and technical work Copyright and all rights therein are retained by authors or by other. copyright holders All person copying this information are expected to adhere to the terms and constraints invoked by each author s copyright This work may not be. reposted without the explicit permission of the copyright holder. 507 Handbook of Medical Imaging Processing and Analysis IV Registration. Figure 8 Example of registered crest lines between two MR T1 images of the same patient Only the 240 matched. lines are displayed Extremal points are represented by a color change from yellow to blue on the lines Left View of. matched crest lines from the left of the head Middle View from the front. 2 5 Examples of Rigid Registrations 3 Robustness and Uncertainty. Registration of CT Images of the Skull Figure 7 Analysis. presents an example of the registration of two CT images. of the a dry skull in a Plexiglas box in two different posi Once we have registered the images i e found matches. tions We used the geometric hashing algorithm on frames and a rigid transformation the question is how confident. Section 2 3 As the transformation between the two im can we be with this result There are two main types of. ages is close enough to the identity the ICP algorithm errors in feature based registration algorithms Firstly the. also gives very similar results About 75 crest lines are matches could be completely wrong and we simply rec. matched with more than 4 extremal points among the 550 ognized by chance n features in approximately the same. lines in each image leading to a total of 550 matched ex configuration This is called a gross error in statistics and. tremal points only on the 75 matched lines Using the a false positive in recognition But even if we got the. techniques described in Section 3 2 we have computed matches right the features we are using to compute the. that the typical object accuracy the expected standard registration are corrupted by noise and induce a small er. RMS error on image super imposition due to the trans ror or uncertainty on the transformation parameters In. formation in the area of the matched features is 0 04 mm this section we analyze in turn these two types of error. whereas the typical corner accuracy is 0 1 mm This is to. be compared with the voxel size 1 x 1 x 1 5 mm,3 1 Robustness Analysis. Since our features are noisy we had to allow for a cer. Registration of MR Images of the Head Figure 8 is tain error when matching them In the registration algo. an example of the registration of two MR T1 images of rithm of Sections 2 3 and 2 4 this is computed from the. the same patient In this case 240 crest lines are matched covariance matrices The existence of such an error zone. among approximately 2100 in each image for a total of allows us to match features that by chance fall in this area. 860 matched extremal points among 3600 in each image When this probability is sufficiently high individual false. about 25 We used the zero crossing of the Laplacian matches can combine themselves conspiracy to produce. to define the interest surfaces Thus there are crest lines an important matching score. all over the head However if some of the matched lines However we should note that such a false positive is a. are located on the surface of the skin we can recognize correct recognition from a feature point of view a glob. the nose and the eyes most of them are located on the ally consistent matching but is incorrect from the image. surface of the brain The typical object accuracy of the or data point of view This problem is inherent to the as. registration is 0 06 mm for a typical corner accuracy of cendent organization of information some important in. 0 125 mm Once again the accuracy is far below the voxel formation can be dismissed by simplifying the image as a. size 0 97 x 0 97 x 1 5 mm set of features, This draft paper is provided to ensure timely dissemination of scholarly and technical work Copyright and all rights therein are retained by authors or by other. copyright holders All person copying this information are expected to adhere to the terms and constraints invoked by each author s copyright This work may not be. reposted without the explicit permission of the copyright holder. Chap 31 Landmark Based Registration Using Features Identified Through Differencial Geometry 508. In 30 we developed a generic method to evaluate the The actual matches found involve about 500 features. probability of matching features just by chance The and the probability of being a false positive is thus practi. basic framework is the following Let us assume for the cally zero However we must be careful that the object. moment that the transformation between the two images we registered is not always the one we wanted even if. is fixed First we compute the selectivity which is the this is definitely not a false positive there can be several. probability that a random feature uniformly distributed in different rigid motions in a single image for instance the. the image falls in a given error zone Then we compute skull and the brain in MR images. the probability that at least of the m scene features fall. in one of the n model error zones In our analysis com. putations are simplified by assuming that all features are. 3 2 From Feature to Transformation Uncer,randomly distributed tainty. Now we will accept a match if there exists one trans Here we assume that the matches are right However. formation such that at least features are put into cor measurement errors on the features induce an estimation. respondence Thus to obtain the mean number of false error on the transformation We developed in 32 31 a. positives we just have to integrate over all possible trans method where we register the features estimate the noise. formations Let d be the diameter of the images we get on the frames and propagate this noise to estimate the un. the following estimation certainty of the rigid transformation. 2 d 3 X nm, P 1 e nm Feature Uncertainty For extremal points modeled as. j frames we proposed a compositive model of noise, Basically this means that the noise is assumed to be iden. In the example of Section 3 3 we compute that the se tical on all extremal points in the local frame i e with. lectivity is pt 2 10 6 if we just use the position of the respect to the surface normal and the principal directions. extremal points and f r 1 5 10 8 if we model them us This has to be compared with the standard additive noise. ing frames The diameter of the image is d 400mm and model on points where we assume an identical noise with. we extracted around 2 500 extremal points in each image respect to the image axes In the case of the MR images. We plot in Figure 9 the number of false positives P with of the next Section this leads to an interesting observa. these values tion we draw in Figure 10 a graphical interpretation of. the covariance matrix estimated on the extremal points af. ter registration,We obtain an approximately diagonal covariance ma. trix with standard deviations t1 t2 2 deg n, Figure 9 Qualitative estimation of the number of false Figure 10 Graphical interpretation of the compositive. positives involving at least matches in MR images of noise model estimated on extremal points The uncer. 2500 features Comparison between frames and points tainty of the origin point X is 4 times larger in the tan. we need roughly 5 times more point matches than frame gent plane than along the surface normal The uncertainty. matches to obtain the same probability 10 frames and 56 of the normal is isotropic whereas the principal directions. point matches for a probability of 10 10 t1 and t2 are 3 times more uncertain in the tangent plane. This draft paper is provided to ensure timely dissemination of scholarly and technical work Copyright and all rights therein are retained by authors or by other. copyright holders All person copying this information are expected to adhere to the terms and constraints invoked by each author s copyright This work may not be. reposted without the explicit permission of the copyright holder. 509 Handbook of Medical Imaging Processing and Analysis IV Registration. Figure 11 Uncertainty induced on the point positions image corners left some object points right by the transfor. 6 deg for the rotation vector these are typical values of values for the rotation and metric values for the transla. the angle of rotation around the corresponding axis and tion To characterize the transformation accuracy with a. xt1 xt2 0 8 mm xn 0 2 mm for the position single number we can compute the uncertainty expected. As far as the trihedron part is concerned this means that RMS error induced on a set of representative points by. the surface normal is more stable than the principal direc the registration uncertainty alone without the uncertainty. tions which is expected since the normal is a first order due to the feature extraction In our case two sets are. differential characteristic of the image and the principal particularly well suited the position of the matched ex. directions are second order ones tremal point represents the localization of the object of. For the position the coordinate along the normal is interest whereas the corners of the image symbolize the. once again more stable than in the tangent plane for the worst case In the example below we find for instance. same reasons The 3D standard deviation of the posi a typical boundary precision around corn 0 11 mm. tion is 1 04 which is in agreement with the ad and a typical object precision far below the voxel size. ditive noise model on points However for the additive obj 0 05 mm for echo 1 registrations The values are. noise model the estimated covariance is isotropic Thus even a little smaller for echo 2 registrations corn 0 10. using an adapted model of noise on frames allows us to and obj 0 045 mm. extract much more information about the feature noise. This constitutes an a posteriori validation of our com. positive model of noise on extremal points Validation Index Last but not least we need to vali. date this whole chain of estimations to verify if our uncer. Transformation Uncertainty Now the problem is to tainty prediction is accurate We observed that under the. propagate the feature uncertainty to the rigid transforma Gaussian hypothesis the Mahalanobis distance between. tion Let f represent a rigid transformation and the ob the estimated and the exact transformation or between. served data The optimal transformation f minimizes a two independent estimations of the same transformation. given criterion C f for instance the least squares or should be 26 distributed if the covariance matrix on the. the Mahalanobis distance Let f C f f estimation is exact To verify this the idea is to repeat a. The characterization of an optimum is f 0 Now registration experiment N times and P to2 compute the em. if the data are moving around their observed values we pirical mean value I 2 N1 i and the variance. can relate the new optimal parameters using a Taylor ex I2 of this Mahalanobis distance The values for an exact. pansion Let H f and J be the val 26 are respectively 6 and 12 We can also verify using. ues of the second order derivatives of the criterion at the the Kolmogorov Smirnov test K S test that the empiri. actual values f We have cal distribution corresponds to the exact distribution The. validation index I 32 can be interpreted as an indication. f f J H f 0 of how the estimation method under estimates I 6 or. f f E f f T H 1 J J T H 1 over estimates I 6 the covariance matrix of the es. timated transformation It can also be seen as a sort of. Thus we can express an approximation of the covari relative error on the error estimation. ance of the resulting transformation using the covariance We run several sets of tests with synthetic data and ver. on features and the criterion derivatives ify that our uncertainty estimations very perfectly vali. However a covariance matrix on a rigid transforma dated for more than 15 extremal point matches Now the. tion is quite hard to understand since it mixes angular question we want to answer is is it still valid for real data. This draft paper is provided to ensure timely dissemination of scholarly and technical work Copyright and all rights therein are retained by authors or by other. copyright holders All person copying this information are expected to adhere to the terms and constraints invoked by each author s copyright This work may not be. reposted without the explicit permission of the copyright holder. Chap 31 Landmark Based Registration Using Features Identified Through Differencial Geometry 510. Figure 12 Left Example of MS images The same slice of one acquisition in echo 1 left and echo 2 right Right evolution. of an image row going through a lesion across 24 time points over a year Left without registration Right after registration and. intensity correction Original 3D Images courtesy of Dr Charles Guttmann and Prof Ron Kikinis from the Brigham and Woman s. Hospital Harvard Medical School Boston, 3 3 Validation with Real Data ages The resulting validation index clearly indicates that. the transformations do not agree I 50 instead of, The experiment is performed using multiple 2D contigu 6 However our registration method cannot detect sys. ous Magnetic Resonance images MRI which constitute tematic biases. a 3D representation of the head The images are part. To discover the biases we ran a series of experiments. of an extensive study of the evolution of the Multiple. where we repeated the same registration while varying the. Sclerosis MS disease performed at the Brigham and, algorithm parameters This confirms that the observed un. Woman s Hospital Harvard Medical School Boston by, certainty is similar in size and shape to the predicted one. Dr Guttmann and Prof Kikinis Each patient underwent. Moreover other experiments show that the inter echo 1. a complete head MR examination several times during. and the inter echo 2 registrations are compatible but the. one year typically 24 different 3D acquisitions The aim. two groups significantly differ Figure 13 Thus we con. is to register precisely all the images acquired at multiple. cluded that there was a systematic bias between echo 1. time points in order to segment the lesions and evaluate. and echo 2 registrations Additional experiments showed. very accurately their evolution,that the bias was different for each registration. Each acquisition provides a first echo image and a sec. ond echo image typically 256 x 256 x 54 voxels of size. 9375 x 9375 x 3mm The two images represent the, same slice of T2 weighted signal imaged at different echo. times Thus they are expected to be in the same coordi. nate system This protocol was designed to optimize the. contrast in the two channels for easier tissue segmenta. tion Considering two acquisitions A and B the regis. trations of echo 1 images A1 to B1 and echo 2 images. A2 to B2 give two relatively independent estimates of. the genuine transformation from A to B The comparison. of these two transformations using the Mahalanobis dis. tance gives a real validation index which can be tested for. the accuracy of the uncertainty estimation, In this experiment the images being close enough we. used the iterative closest feature algorithm Typically we. match 1000 extremal points out of the about 3000 ex Figure 13 This diagram represents three acquisitions A B and. tracted with a residual mean square error RMS of about C with the three echo 1 images A1 B1 C1 and the three echo. 1mm 2 images A2 B2 C2 The echo 1 and echo 2 registrations. are significantly different 2 fAB1 fAB2 2 fAC1 fAC2. 2 fBC1 fBC2 50 but the intra echo 1 and intra echo 2 reg. Direct Validation Shows Biases With n different ac istrations are compatible 2 fBC1 fAB1 fAC1 6 and. quisitions we can run n n 1 2 registrations per echo 2 fBC2 fAB2 fAC2 6 This led us to assume a global. In a first experiment we compared directly the registra bias for each acquisition between echo 1 and echo 2 images. tions between the corresponding echo 1 and echo 2 im represented here by the transformations fA fB and fC. This draft paper is provided to ensure timely dissemination of scholarly and technical work Copyright and all rights therein are retained by authors or by other. copyright holders All person copying this information are expected to adhere to the terms and constraints invoked by each author s copyright This work may not be. reposted without the explicit permission of the copyright holder. 511 Handbook of Medical Imaging Processing and Analysis IV Registration. I I K S test num im num reg,Theoretical values 6 12 3 46 0 01 1 n 24 n n 1 2. patient 1 6 29 4 58 0 14 15 105,patient 2 5 42 3 49 0 12 18 153. patient 3 6 50 3 68 0 25 14 91,patient 4 6 21 3 67 0 78 21 210. Table 1 Theoretical and observed values of the real validation index with bias for different patients The number of registrations. which is also the number of values used to compute the statistics on the validation index is directly linked to the number of images. used Results indicate a very good validation of the registration accuracy prediction the mean validation index is within 10 of its. theoretical value and the K S test exhibits impressively high values. Estimation of the Biases To estimate the biases we Origin of the Bias Most of the extremal points we. first observed that the transformation from image A1 to match are situated on the surface of the brain and the ven. image B2 can be written fA1 B2 fB fAB1 fAB2 fA tricles These surfaces appear differently in echo 1 and. If measurements where perfect the bias fA could be ex echo 2 images due to the difference in contrast Other ar. pressed for any other image Z fA fAZ 2, fZ fAZ1 tifacts such as chemical shift or susceptibility effects see. Since measurements are noisy we obtain an estimator of for instance 18 may also account for the observed bias. the bias fA by taking the Fre chet mean value 28 as they influence the detection of extremal points Indeed. the two echoes are acquired with different receiver RF. X bandwidth to improve the signal noise ratio 19 There. f A arg min dist2 f fAZ, fZ fAZ1 fore the chemical shift and the susceptibility effect are. different in the two echoes, We plan to correlate the biases with diverse quantities in. In this formula each acquisition bias depends upon the the images in order to understand their origin Ultimately. others Thus we begin with null biases identity transfor we would like to predict the biases in each acquisition be. mations and iteratively estimate each bias until conver fore registration This would allow the definite validation. gence of the registration accuracy prediction, We effectively obtain a different bias for each acqui. sition that significantly differs from the identity How. ever from a more global point of view all the biases 4 Conclusion. could be modeled as an additional noise on the trans. formation with an identity mean and standard deviations. of r 0 06 deg on the rotation not significantly differ We presented in this chapter a method to extract reliable. ent from 0 and x 0 09 y 0 11 and z 0 13 mm differential geometry features crest lines and extremal. on the translation significantly different from 0 Very points from 3D images and several rigid registration al. similar values were observed for other patients gorithms to put into correspondence these features in two. different images and to compute the rigid transformation. between them We also presented an analysis of the ro. Validation with Bias Although the biases appear very bustness with the computation of the probability or mean. small they are sufficient to explain the previous errors in number of false positives and an analysis of the accuracy. the registration accuracy prediction Indeed taking the of the transformation. biases into account the real validation index between ac This method proves to be very powerful for monomodal. quisition A and B becomes rigid registration of the same patient imaged at different. times as we show that an accuracy of less than a tenth. IAB 2 fB fAB1 fAB2 fA of voxel can be achieved In the last experiment we. showed that this uncertainty estimation technique is pre. Since the biases are estimated from the registration val cise enough to put into evidence systematic biases on the. ues using their uncertainties in this formula would bias order of 0 1 voxel between features in echo 1 and echo 2. the validation index toward low values Thus we consider images Once corrected multiple experiments on several. them as deterministic The mean value and standard de patients show that our uncertainty prediction is validated. viation of this new index across all registrations are now on real data. very close to their theoretical value see table 1 This registration technique is currently used in many. This draft paper is provided to ensure timely dissemination of scholarly and technical work Copyright and all rights therein are retained by authors or by other. copyright holders All person copying this information are expected to adhere to the terms and constraints invoked by each author s copyright This work may not be. reposted without the explicit permission of the copyright holder. Chap 31 Landmark Based Registration Using Features Identified Through Differencial Geometry 512. medical applications such as the registration of a pre 001 Center for Mathematical Sciences The Univer. operative MR used for planning and MR with a stereotac sity of Aizu Japan July 1996. tic frame for neuro surgery navigation European Com. munity project Roboscope or the registration of a series 5 P J Besl and N McKay A method for registration. of acquisitions over time of images of Multiple Sclerosis of 3 d shapes PAMI 14 2 239 256 1992. patients to study the disease s evolution European Com. munity project Biomorph 6 C B Cutting Applications of computer graphics to. Several tracks have been followed to generalize this the evaluation and treatment of major craniofacial. work to non rigid registration Feldmar 11 used the prin malformation In Udupa and Herman editors 3 D. cipal curvatures to register surfaces with rigid affine and Imaging in Medicine CRC Press 1989. locally affine transformations Subsol designed an algo. 7 D Dean P Buckley F Bookstein J Kamath, rithm for non rigid matching of crest lines In 35 he. D Kwon L Friedman and C Lys Three di, used this method to warp 3D MR images of different pa. mensional MR based morphometric comparison of, tients brains in the same coordinate system and even to. schizophrenic and normal cerebral ventricles In Vi. warp an atlas onto a given 3D MR image of a brain in. sualization in Biomedical Computing volume 1131, order to segment it In 36 he used the same method to. of LNCS pages 363 371 Springer Verlag 1996, construct automatically a morphometric atlas of the skull. crest lines from several acquisitions of different patients 8 R Deriche and G Giraudon A computational. CT images with applications in cranio facial surgery approach for corner and vertex detection IJCV. 10 2 101 124 1993, Acknowledgments 9 Manfredo P Do Carmo Differential Geometry of. Curves and Surfaces Prentice Hall 1976,The authors wish to thank the whole epidaure team. and particularly their colleagues or ex colleagues who 10 D Eberly Ridges in Image and Data Analysis. worked on differential geometry features and registration Kluwer Academic Publishers 1996. S Benayoun M Fidrich A Gourdon A Gue ziec O,11 J Feldmar and N Ayache Rigid affine and lo. Monga and G Subsol This research would have not, cally affine registration of free form surfaces IJCV. been possible without the CT data from GE CGR Buc,18 2 99 119 May 1996. France the MR data of Dr C Guttmann and Prof R, Kikinis Brigham Women s Hospital and Harvard Med 12 Ma rta Fidrich Multiscale analysis of invariants. ical School Boston USA Application to volumetric medical image processing. PhD thesis University Paris XI July 1997, References 13 John M Gauch Multiresolution Image Shape De. scription Springer Verlag 1992,1 E V Anoshkina A G Belyaev R Huang and T L. Kunii Ridges and Ravines on a Surface and Related 14 A Gue ziec Surface representation with deformable. Geometry of Skeletons Caustics and Wavefronts In splines Using decoupled variables IEEE Computa. R A Earnshaw and J A Vince editors Computer tional Science and Engineering Magazine 2 1 69. Graphics Developments in Virtual Environments 80 March 1995. chapter 22 pages 311 326 Academic Press 1995,15 A Gue ziec and N Ayache Smoothing and matching. 2 N Ayache Medical computer vision virtual reality of 3d space curves International Journal of Com. and robotics promising research Image and Vision puter Vision 12 1 79 104 1994. Computing 13 4 295 313 1995,16 A Gue ziec X Pennec and N Ayache Medical. 3 N Ayache and O D Faugeras Hyper A new ap image registration using geometric hashing IEEE. proach for the recognition and positioning of two Computational Science Engineering special issue. dimensional objects IEEE Trans on Pattern Analy on Geometric Hashing 4 4 29 41 1997 Oct Dec. sis and Machine Intelligence 8 1 44 54 1986, 17 D P Huttenlocher and S Ullman Object recognition. 4 A G Belyaev I A Bogaevski and T L Kunii using alignment In Proc of ICCV pages 72 78. Principal direction ridges Technical Report 96 4 1987. This draft paper is provided to ensure timely dissemination of scholarly and technical work Copyright and all rights therein are retained by authors or by other. copyright holders All person copying this information are expected to adhere to the terms and constraints invoked by each author s copyright This work may not be. reposted without the explicit permission of the copyright holder. 513 Handbook of Medical Imaging Processing and Analysis IV Registration. 18 P Jezzard Physical basis of spatial distortions in Proc of First Int Conf on Medical Image Com. magnetic resonance images In Handbook of Medi puting and Computer Assisted Intervention MIC. cal Image Processing Academic Press 1999 CAI 98 number 1496 in LNCS pages 1107 1114. Cambridge USA October 1998 Springer Verlag,19 R Kikinis C R G Guttmann D Metcalf W M III. Wells G J Ettinger H L Weiner and F A Jolesz 32 X Pennec and J P Thirion A framework for un. Quantitative follow up of patients with multiple certainty and validation of 3D registration methods. sclerosis using MRI Technical aspects JMRI based on points and frames Int Journal of Com. 9 4 519 530 1999 puter Vision 25 3 203 229 1997, 20 Les Kitchen and Azriel Rosenfield Gray level cor 33 I R Porteous Ridges and Umbilics of Surfaces In. ner detection Pattern Recognition Letters 1 95 R R Martin editor The mathematics of surfaces II. 102 1982 pages 447 458 Clarendon Press Oxford 1987. 21 J J Koenderink Solid Shape M I T Press 1990 34 I R Porteous Geometric Differentiation For the. Intelligence of Curves and Surfaces Cambridge, 22 Y Lamdan and H J Wolfson Geometric hash University Press 1994. ing A general and efficient model based recognition. scheme In Proc of Second ICCV pages 238 289 35 G Subsol Crest lines for curve based warping In. 1988 A W Toga editor Brain Warping chapter 14 pages. 241 262 Academic Press 1998,23 V F Leavers Survey which Hough trans. form CVGIP Image Understanding 58 2 250 36 G Subsol J Ph Thirion and N Ayache A general. 264 september 1993 scheme for automatically building 3D morphomet. ric anatomical atlases application to a skull atlas. 24 S Markatis Some Generic Phenomena in Families Medical Image Analysis 2 1 27 60 1998. of Surfaces in R3 PhD thesis University of Liver, pool 1980 37 J P Thirion New feature points based on geometric. invariants for 3D image registration International. 25 O Monga N Ayache and P T Sander From voxel Journal of Computer Vision 18 2 121 137 May. to intrinsic surface features Image and Vision Com 1996. puting 10 6 403 417 August 1992,38 J P Thirion and A Gourdon Computing the differ. 26 O Monga and S Benayoun Using Partial Deriva ential characteristics of isointensity surfaces Com. tives of 3D Images to Extract Typical Surface Fea puter Vision and Image Understanding 61 2 190. tures Computer Vision and Image Understanding 202 March 1995. 61 2 171 189 March 1995, 39 J P Thirion and A Gourdon The 3D marching lines. 27 Alison J Noble Finding corners Image and Vision algorithm Graphical Models and Image Processing. Computing 6 121 128 1988 58 6 503 509 1996, 28 X Pennec Computing the mean of geometric fea 40 P A van den Elsen J B A Maintz E J D Pol and. tures application to the mean rotation Research M A Viergever Automatic Registration of CT and. Report 3371 INRIA March 1998 MR Brain Images Using Correlation of Geometri. cal Features IEEE Transactions on Medical Images, 29 X Pennec Toward a generic framework for recogni. 14 2 384 398 1995,tion based on uncertain geometric features Videre. Journal of Computer Vision Research 1 2 58 87 41 Z Zhang Iterative point matching for registration. 1998 of free form curves and surfaces Int Journ Comp. Vis 13 2 119 152 1994 Also Research Report,30 X Pennec and N Ayache Uniform distribution dis. No 1658 INRIA Sophia Antipolis 1992,tance and expectation problems for geometric fea. tures processing Journal of Mathematical Imaging,and Vision 9 1 49 67 July 1998. 31 X Pennec C R G Guttmann and J P Thirion,Feature based registration of medical images Es. timation and validation of the pose accuracy In, This draft paper is provided to ensure timely dissemination of scholarly and technical work Copyright and all rights therein are retained by authors or by other. copyright holders All person copying this information are expected to adhere to the terms and constraints invoked by each author s copyright This work may not be. reposted without the explicit permission of the copyright holder.