Medical Image Analysis 8 2004 465 473 www elsevier com locate media Adaptive registration using local information measures Hyunjin Park a Peyton H Bland a Kristy K Brock b Charles R Meyer a a Department of Radiology University of Michigan Medical School Ann Arbor MI 48109 0533 USA b Radiation Medicine Program Princess Margaret Hospital Toronto Ont Canada Received 12 December 2002 received in revised form 22 September 2003 accepted 4 March 2004 Available online 23 April 2004 Abstract Rapidly advancing registration methods increasingly employ warping transforms High degrees of freedom DOF warpings can be speci ed by manually placing control points or instantiating a regular dense grid of control points everywhere The former approach is laborious and prone to operator bias whereas the latter is computationally expensive We propose to improve upon the latter approach by adaptively placing control points where they are needed Local estimates of mutual information MI and entropy are used to identify local regions requiring additional DOF 2004 Elsevier B V All rights reserved Keywords Adaptive registration Thin plate splines Warping registration Grid re nement 1 Introduction Associated with rapid developments of medical imaging there is an increasing need for nonlinear registration Registration literature has shifted its focus from a ne rigid registrations to high degrees of freedom DOF warping registrations Hill et al 2001 Johnson and Christensen 2001 Meyer et al 1998 Meyer and Boes 1998 Reuckert et al 1999 Warping registration algorithms also employ di erent similarity measures i e measures of alignment and geometric transforms to suit their purposes A popular choice of similarity measure has been mutual information MI Wells et al 1996 Collignon et al 1995 Additionally there are many geometric transforms to choose from where Bsplines and thin plate splines TPS are notable Lee et al 1996 Bookstein 1991 Recently a warping registration algorithm with normalized MI as the similarity measure and B splines as the geometric transform has gained much support Reuckert et al 1999 Herein we employ MI as the similarity measure and TPS as the Corresponding author Tel 1 734 763 5881 fax 1 734 7648541 E mail address cmeyer umich edu C R Meyer URL http www dipl med umich edu 1361 8415 see front matter 2004 Elsevier B V All rights reserved doi 10 1016 j media 2004 03 001 geometric transform as in our previous work Kim et al 1999 Meyer et al 1997 1999 Although TPS may be less e cient to compute than B splines due to the local support properties of B splines TPS is supported by a rich literature in shape statistics and Morphometrics Bookstein 1991 1997 Dryden and Mardia 1998 A warping registration starts with an initial set of control points in both the reference and homologous dataset and then optimizes the loci of the control points typically in the homologous dataset to maximize MI while control points on the reference side remain xed The initial set of control points may be realized either by manually specifying all control points or by instantiating a regular grid of control points The rst method may be impractical for high DOF since manually specifying all control points is laborious and prone to operator bias Given the presence of local minima in numerical optimization of the MI di erent initial locations of control points may lead to di erent nal optimized control point locations Thus removing operator bias is important The second i e the regular grid method su ers from increased computational expense instead Typical DOF may be in hundreds or even in thousands In this paper we propose to improve the second method by adaptively placing control points only where they are needed rather than placing control points regularly everywhere to 466 H Park et al Medical Image Analysis 8 2004 465 473 improve overall registration Our adaptive registration results in an irregularly spaced grid of control points with fewer DOF than a regular grid of control points and lesser computational expense There are other adaptive registration methods Rohde et al 2001 2003 Rohl ng and Maurer 2001 Schnabel et al 2001 They typically share a common approach i e rst they identify a region where registration can be improved and then increase DOF in that region The geometric transforms and the methods to identify the region requiring additional DOF may be di erent Rohde et al use Wu s radial basis function as the geometric transform and the gradient of global MI to identify the region to increase warping DOF Rohde et al 2001 2003 Others use B splines as the geometric transform and measures based on entropy to identify the region to increase DOF Rohl ng and Maurer 2001 Schnabel et al 2001 Our method uses TPS as the geometric transform and a novel information measure based on a local MI and entropy to identify the region to increase DOF We refer to this local information measure as a mismatch measure Note that in our paper the global MI used to optimize the control point locations is calculated over all of both datasets but our mismatch measure is calculated only over sub regions of the datasets In summary we propose to improve a regularly spaced TPS warping registration method by instantiating an irregular grid of control points derived from a novel local information measure to determine where to increase DOF 2 Methods In this paper the following notations are assumed A x is the reference dataset and B x is the homologous or oating dataset T x is the geometric transform between two datasets where x is the coordinates in 2D or 3D The homologous dataset is mapped onto the reference dataset before calculating the similarity measure Once T is found all the coordinates are assumed to in the reference coordinate frame since the homologous coordinate frame can always be found by applying the transform T T arg maxMI A BT 1 T 2F where T is the estimate of the transform and F is the family of feasible transforms 1991 Dryden and Mardia 1998 Assuming that x is the reference coordinates x0 is the homologous coordinates and that there are N control point pairs x1 xN and x01 x0N the formulation of TPS is the following where x0 f x is the geometric transform U r is the basis function ri is the Euclidean distance between xi and x i e jx xi j T x a0 a1 x N X wi U ri 2 i 1 where a0 a1 are a ne parameters and wi is the warp coe cient 2 r log r2 in 2D U r jrj in 3D B splines are constructed to have a local support property but with TPS the local