Abstract:
A method of aligning at least two breast images includes aligning a relevant image part in each of the images, the relevant image parts being obtained on the basis of the result of a shape analysis procedure performed on the breast images.

Description:
CROSS-REFERENCE TO RELATED APPLICATIONS 
       [0001]    This application is a 371 National Stage Application of PCT/EP2013/053691, filed Feb. 25, 2013. This application claims the benefit of U.S. Provisional Application No. 61/603,504, filed Feb. 27, 2012, which is incorporated by reference herein in its entirety. In addition, this application claims the benefit of European Application No. 12157165.7, filed Feb. 27, 2012, which is also incorporated by reference herein in its entirety. 
     
    
     BACKGROUND OF THE INVENTION 
       [0002]    1. Field of the Invention 
         [0003]    The present invention relates to a method for image alignment of breast images. 
         [0004]    2. Description of the Related Art 
         [0005]    Radiologists examine mammographic images to diagnose various abnormalities in a breast. The images are nowadays examined on a display device such as the display screen of a computer workstation. 
         [0006]    Essential for a mammographic display system is the ability of the radiologist to quickly analyze the mammographic images of the breast and create a report of his diagnosis. 
         [0007]    Analyzing breast images often comprises comparing breast images by aligning two or more breast images. These images may be images of the same object acquired at different times and/or with different display settings or images of right and left breast etc. 
         [0008]    The conventional procedure to achieve such an alignment is based on nipple alignment or pectoralis alignment. Mostly, for craniocaudal (CC) images, the nipple is located in each pair of images and the images are positioned such that the nipple is located at the same height (see  FIG. 2 ). For mediolateral-oblique (MLO) images, either nipple or pectoralis alignment is used (see  FIG. 3 ). While both methods generate similar results, it is possible that the alignment is different when the position of the breasts during the acquisition differs (see  FIG. 4 ). 
         [0009]    The observation that pectoralis alignment can be suboptimal in combination with the fact that accurate nipple detection is not always possible, is an indication that more robust alignment methods are desirable. Radiologists prefer aligned images because it facilitates comparison of the images. Aligned images are most similar to mirrored images for which our eyes and brains are trained to find differences. Alignment based on a few key features, being the nipple or the pectoralis muscle, is not optimal. 
         [0010]    U.S. Pat. No. 7,885,443 as well as US 2011/0128289 disclose a method for facilitating temporal comparison of breast mammograms by a viewer. A first and a second mammogram are displayed at identical tissue distance per unit display distance in a number of display windows sized and paired according to a hanging protocol. A fiducial alignment marker location is identified in the breast tissue area of each of the mammograms. Paired ones of the displayed mammogram views are displayed horizontally adjacent to each other and are vertically aligned on said mammogram display according to said identified fiducial marker locations. 
         [0011]    It is an aspect of the present invention to provide a method for optimal alignment of breast images so as to facilitate optimal analysis of breast images. 
       SUMMARY OF THE INVENTION 
       [0012]    The above-mentioned aspects are realized by a method having the specific features set out below. 
         [0013]    Specific features for preferred embodiments of the invention are also set out below. 
         [0014]    Preferred embodiments of the present invention comprise alignment of breast images based on shape information of these breast images. By this method similar structures in mammograms may be placed at the same height. 
         [0015]    The technique may be applied to align at least two images with different lateralities from the same patient but is also applicable to align images for temporal comparisons. 
         [0016]    In one preferred embodiment a breast image is first segmented into a direct exposure or background region and foreground regions. From this segmentation, the skin boundary is determined. Optionally, the pectoralis muscle can be located. From these boundaries, only the relevant parts are retained. An example of a relevant part is the convex part of the skin boundary. To align two relevant parts, the parts are sampled and the points are aligned e.g. with the robust point matching technique. 
         [0017]    In the context of the present invention the term ‘mammographic image’, ‘mammogram’ or ‘breast image’ refers to an image of a breast such as a radiation image of a breast. A radiation image of a breast in this invention is provided in the form of a (digital) signal representation wherein the signal values represent grey values of image pixels. 
         [0018]    Further in the context of this application ‘direct exposure area’ or ‘background area’ means an area part of the radiation image of a breast in which radiation is not attenuated by the breast and has impigned directly onto a radiation detector used for recording the radiation image of the breast. 
         [0019]    Also in the context of the present invention the term ‘skin line estimate’ (also referred to as ‘skin line’) is defined as the edge between the background area and the remainder of the mammographic image. This skin line is determined by a skin line extraction algorithm described below. The determined skin line may comprise pixels of the breast boundary as well as pixels not belonging to the breast boundary such as chest pixels, markers etc. 
         [0020]    Several types of systems exist for generating a radiation image of a breast. Such systems are described furtheron. 
         [0021]    Preferred embodiments of the present invention are generally implemented in the form of a computer program product adapted to carry out the method steps of the present invention when run on a computer. The computer program product is commonly stored in a computer readable carrier medium or device. Alternatively the computer program product takes the form of an electric signal and can be communicated to a user through electronic communication. Examples are one or more diskettes, compact disks, tapes, chips, wireless transmission means, internet transmission or downloading means etc. readable or accessible by computer for configurating and operating the computer when the storage media or device is read by the computer to perform the procedures described herein. 
         [0022]    Further advantages and embodiments of the present invention will become apparent from the following description and drawings. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0023]      FIG. 1  shows a system in which a preferred embodiment of the present invention can be implemented. 
           [0024]      FIG. 2(   a ) shows left and right unaligned CC breast images. 
           [0025]      FIG. 2(   b ) shows nipple aligned CC breast images, 
           [0026]      FIG. 3(   a ) shows left and right unaligned MLO breast images. 
           [0027]      FIG. 3(   b ) shows nipple/pectoralis aligned MLO breast images. 
           [0028]      FIG. 4  shows pectoralis aligned MLO images for images where the image position differs (distance detector edge to chest). 
           [0029]      FIG. 5(   a ) shows for a star-shaped background search region the situation wherein all criteria are valid. 
           [0030]      FIG. 5(   b ) shows for a star-shaped background search region the situation wherein intensity criteria are not valid for angles between 12 and 3 o&#39;clock. 
           [0031]      FIGS. 6(   a ) to ( d ) illustrate the segmentation of different clinical views. 
           [0032]      FIG. 7(   a ) illustrates the distance computation, 
           [0033]      FIG. 7(   b ) illustrates the classification of points based on a threshold values set at −10. 
           [0034]      FIGS. 8(   a ) to ( d ) show extended skin lines which are classified as true breast boundary. 
           [0035]      FIG. 9  shows the results of the first annealing step of the Robust Point Matching algorithm. 
           [0036]      FIG. 9(   a ) shows the initial position and correspondence. 
           [0037]      FIGS. 9(   b ) and ( c ) show the new position and correspondence after 1 or 2 iterations, respectively, of the deterministic annealing. 
           [0038]      FIGS. 9(   d ) and ( e ) illustrate intermediate steps. 
           [0039]      FIG. 9(   f ) shows the result after the convergence for M. 
           [0040]      FIG. 10  illustrates breast aligned images obtained by a preferred embodiment of the present invention showing better results than obtained by nipple or pectoralis alignment. 
           [0041]      FIG. 10(   a ) shows the situation in which the images are aligned according to the distance measure between the breast shape extracted from the images. The nipple is not perfectly aligned but general alignment of the breast is guaranteed. 
           [0042]      FIG. 10(   b ) shows that the general shape of the breasts are aligned which results in suboptimal pectoralis alignment but places similar breast structures at the same height. 
       
    
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS 
       [0043]    While the present invention will hereinafter be described in connection with preferred embodiments thereof, it will be understood that it is not intended to limit the invention to those embodiments. 
         [0044]      FIG. 1  shows an example preferred embodiment of a mammography system  100 . A mammography system  100  may contain a processor  102 , operatively coupled to memory  104 . Memory  104  stores a breast window module  110  for defining breast windows on images  120  stored on image database  122 . 
         [0045]    Images  120  stored on image database  122  may comprise mammography images. Those skilled in the art will appreciate that there are different types of mammography images such as craniocaudal (CC), containing a view of a breast as taken through the top of the breast and mediolateral oblique (MLO), containing a view of a breast as taken from the center of the chest to the lateral of the breast. 
         [0046]    Various systems may be envisaged for acquiring a digital signal representation of a radiographic image of the breast such as projection radiography image acquisition systems, echography image acquisition systems, tomosynthesis systems, computed tomography systems etc. 
         [0047]    Mammographic image acquisition systems typically comprise a radiation sensitive detector (e.g. x-ray radiation sensitive) for storing an image of an irradiated breast. Examples of suitable detectors are a radiographic film, a photo-stimulable phosphor screen, a direct radiography detector etc. A digital signal representation of the breast image is then obtained by reading out the image from the detector (e.g. by scanning the film, stimulating the photo-stimulable phosphor screen or reading out the direct digital detector) and eventually digitizing the read out signal. The digital signal representation of a mammographic image represents the grey value in each image pixel. 
         [0048]    Image database  122  stores breast images  120 , and may be implemented using any database software or persistent storage method known in the art. For example, image database  122  may be implemented using Oracle®, Microsoft SQL Server® or IBM DB2® with suitably defined schemas to identify and navigate images  120 . In the exemplary embodiment, image database  122  may be part of a Picture Archiving and Communication Systems (PACS) deployment, such as those found in a hospital. While image database  122  is illustrated as residing in the same memory as mammography system  100 , it will be understood that image database  122  may be stored and accessed remotely through a network connection, for example, using a Digital Imaging and Communications in Medicine (DICOM) protocol. In such case, it will be further understood that the operations of the breast window module  110  may be performed locally on the mammography system, remotely on the system where the image database  122  resides, or on a third-party system configured to access image database  122  and mammography system  100 . 
       Segmentation 
       [0049]    The first step of one preferred embodiment of the method of the present invention is a segmentation step which is applied to the digital signal representation of the rendered breast image. In this segmentation step a mask is created indicating direct exposure or background pixels. This segmentation step may also be omitted, e.g. when the gradient image derived from the breast image is used for further analysis. 
         [0050]    This mask is in this preferred embodiment constructed in 2 steps: (1) an initial classification step and (2) a step for generation of a sequence of background masks from which the optimal background mask is selected. The optimal background mask is created by an iterative process in which the classification rules are strenghtened in each iteration step. 
         [0051]    First an initial mask of candidate background pixels is computed based on the grey pixel values in the rendered breast image. In this context the term ‘rendered’ refers to the image signal obtained by window/level setting and conversion to grey values. In the described exemplary preferred embodiment the rendering of the image uses the default, most conservative, window/level settings found in the DICOM tags associated with the image. The threshold is derived from the histogram of the image and selected such that typically all background pixels are selected with some additional non-background pixels. 
         [0052]    Starting from this initial background mask, a sequence of further background masks is generated with a sequence of a so-called second thresholds th. The sequence of the second thresholds is in this preferred embodiment the initial gray level intensity for the local intensity variability within a search region. 
         [0053]    As illustrated in  FIG. 5 , the search region in the described preferred embodiment is defined as a star defining a number (in this embodiment: 8) radial search directions. 
         [0054]    The difference between two successive masks is computed and used as a selection criterium for the most suitable background mask. As a measure of this selection criterium the difference is used between the number of background pixels in the 2 masks. The final background mask is the mask which shows minimum difference with the next mask in the sequence of segmentation masks. 
         [0055]    Alternative forms of search regions (other forms or patterns of search area) and selection criteria may be envisaged. 
         [0056]    Preferably each image in the sequence for a specified threshold th, is computed using the following classification rules for all pixels i: 
         [0057]    1. the pixel must be a candidate background pixel in the initial background mask 
         [0058]    2. there is no pixel at a distance of 2 pixels which is not an initial background pixel 
         [0059]    3. no pixel is found along one of 8 search directions radiating outwards of pixel i which exceeds a varying threshold t var  over a fixed distance. t var  is initialized with the intensity value of pixel i scaled with the specified threshold th for the mask in the sequence. The varying threshold t var  is adjusted with a fraction of the central intensity value at pixel i. The fraction with which t var  is adjusted may also be dependent on the intensity value of the pixel under investigation. E.g. the update can be smaller if the pixel under investigation is smaller than the intensity value for the central pixel. 
         [0060]    As an additional step, small or irregular regions within the optimal background mask can be identified and removed. 
         [0061]    Some results of the segmentation algorithm are shown in  FIG. 6 . 
       Skin-Line 
       [0062]    Having segmented the image into a background and foreground region, in the next step of the described preferred embodiment a skin line boundary is found by applying a minimal cost path technique to the selected optimal mask defining direct exposure pixels. The cost for pixels on the edge of the direct exposure area are set to a low value e.g. 2 and the cost to traverse any other pixel is set to a high value e.g. 255. With standard dynamic programming techniques it is easy to find a path from the bottom of the image located at the side of the breast to the top of the image. Some extracted skin-lines are also shown in  FIG. 8 . 
         [0063]    Having found the skin-line, points of the skin-line are classified as a point belonging to the breast boundary by computing and evaluating a measure which is an indication of convexity and evaluating this measure with regard to a given tolerance value. 
         [0064]    The measure is computed as follows: 
         [0065]    1. Take one point from the set of skin-line points, 
         [0066]    2. Take a second point located a fixed number positions further in the set of skin-line points, 
         [0067]    3. Connect these two points with an imaginary line, 
         [0068]    4. Compute the signed distance for all intermediate points on the skin-line with this imaginary line, 
         [0069]    5. Mark both points as convex points if the minimum of the signed distance of all intermediate points of step 4 is greater than 0 
         [0070]    6. Mark each point as extension point if the signed distance is larger than a defined threshold and the point is not already marked as breast point. 
         [0071]    The above algorithm is illustrated in  FIG. 7   a . The final breast boundary is then determined as the segment of convex and extension points containing the longest segment of convex points. In the example of  FIG. 7   b , the threshold is set to a minimum of −10. 
         [0072]    Alternatives for the above described shape analysis method may be envisaged such as analysis of curvature, of Fourier descriptors, of curvelets, Eigenshape analysis/PCA (Principal Component analysis) etc. 
         [0073]    Alternative methods may be envisaged for determining the skin line estimate in general such as identifying border points of the largest object in the image etc. 
         [0074]    The above-described segmentation algorithm may be omitted, e.g. if the minimum cost path analysis is applied to the gradient image deduced from the radiation image of the breast. 
       Alignment 
       [0075]    Once the breast boundaries are found, they need to be aligned. To align the breast images, only the vertical offset is needed. To determine this offset a more general transformation is searched in this preferred embodiment such as an affine transformation and only the parameter determining this vertical offset is used. 
         [0076]    In the context of the present invention, a more general transformation is a transformation that generates more than only a vertical offset value. 
         [0077]    Examples are a transformation that results in a vertical and horizontal alignment, or vertical and horizontal alignment combined with scaling and/or rotation, an affine transformation. 
         [0078]    Also possible are a transformation which generates a vertical and horizontal alignment component and a non-rigid component or all above-described combinations with an additional non-rigid component. 
         [0079]    It is also possible to apply a transformation which only generates a vertical component. 
         [0080]    The problem of finding the optimal transformation between 2 boundaries can be reduced to a minimization problem (see reference [3]). Denote the boundary points from boundary P and boundary Q, P i =(x i ,y i ),i=1,2, . . . , N p  and Q i =(x i ,y i ), j=1,2, . . . , N q  respectively. N p  and N q  are the number of points. The robust point matching (RPM) algorithm minimizes the following objective function: 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       min 
                       
                         M 
                         , 
                         θ 
                         , 
                         t 
                         , 
                         s 
                       
                     
                      
                     
                         
                     
                      
                     
                       E 
                        
                       
                         ( 
                         
                           M 
                           , 
                           θ 
                           , 
                           t 
                           , 
                           s 
                         
                         ) 
                       
                     
                   
                   = 
                   
                     
                       
                         ∑ 
                         
                           i 
                           = 
                           1 
                         
                         
                           N 
                           p 
                         
                       
                        
                       
                           
                       
                        
                       
                         
                           ∑ 
                           
                             j 
                             = 
                             1 
                           
                           
                             N 
                             q 
                           
                         
                          
                         
                             
                         
                          
                         
                           
                             M 
                             ij 
                           
                            
                           
                               
                           
                            
                           
                             
                                
                               
                                 
                                   P 
                                   i 
                                 
                                 - 
                                 t 
                                 - 
                                 
                                   
                                     sR 
                                      
                                     
                                       ( 
                                       θ 
                                       ) 
                                     
                                   
                                    
                                   
                                     Q 
                                     j 
                                   
                                 
                               
                                
                             
                             2 
                           
                         
                       
                     
                     + 
                     
                       
                         
                           γ 
                           2 
                         
                          
                         
                           
                             ( 
                             
                               log 
                                
                               
                                   
                               
                                
                               s 
                             
                             ) 
                           
                           2 
                         
                       
                       
                          
                         
                           scale 
                            
                           
                               
                           
                            
                           regularization 
                         
                       
                     
                     - 
                     
                       
                         α 
                          
                         
                           
                             ∑ 
                             
                               i 
                               = 
                               1 
                             
                             
                               N 
                               p 
                             
                           
                            
                           
                               
                           
                            
                           
                             
                               ∑ 
                               
                                 j 
                                 = 
                                 1 
                               
                               
                                 N 
                                 q 
                               
                             
                              
                             
                                 
                             
                              
                             
                               M 
                               ij 
                             
                           
                         
                       
                       
                          
                         
                           outlier 
                            
                           
                               
                           
                            
                           regularization 
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   1 
                   ) 
                 
               
             
             
               
                 
                   
                       
                   
                    
                   
                     subject 
                      
                     
                         
                     
                      
                     to 
                   
                    
                   
                       
                   
                 
               
               
                 
                     
                 
               
             
             
               
                 
                   
                       
                   
                    
                   
                     
                       
                         
                           
                             ∑ 
                             
                               i 
                               = 
                               1 
                             
                             
                               
                                 N 
                                 p 
                               
                               + 
                               1 
                             
                           
                            
                           
                             M 
                             ij 
                           
                         
                         = 
                         
                           1 
                            
                           
                               
                           
                            
                           
                             ∀ 
                             
                               j 
                               ∈ 
                               
                                 { 
                                 
                                   1 
                                   , 
                                   … 
                                    
                                   
                                       
                                   
                                   , 
                                   
                                     N 
                                     q 
                                   
                                 
                                 } 
                               
                             
                           
                         
                       
                       , 
                       
                         
                           M 
                           ij 
                         
                         ∈ 
                         
                           { 
                           
                             0 
                             , 
                             1 
                           
                           } 
                         
                       
                     
                      
                     
                       
 
                     
                      
                     
                         
                     
                      
                     
                       
                         
                           
                             ∑ 
                             
                               i 
                               = 
                               1 
                             
                             
                               
                                 N 
                                 q 
                               
                               + 
                               1 
                             
                           
                            
                           
                             M 
                             ij 
                           
                         
                         = 
                         
                           1 
                            
                           
                               
                           
                            
                           
                             ∀ 
                             
                               i 
                               ∈ 
                               
                                 { 
                                 
                                   1 
                                   , 
                                   … 
                                    
                                   
                                       
                                   
                                   , 
                                   
                                     N 
                                     p 
                                   
                                 
                                 } 
                               
                             
                           
                         
                       
                       , 
                       
                         
                           M 
                           ij 
                         
                         ∈ 
                         
                           { 
                           
                             0 
                             , 
                             1 
                           
                           } 
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   2 
                   ) 
                 
               
             
             
               
                 
                   
                       
                   
                    
                   
                     
                       M 
                       ij 
                     
                     = 
                     
                       { 
                       
                         
                           
                             
                               
                                 1 
                               
                               
                                 
                                   if 
                                    
                                   
                                       
                                   
                                    
                                   point 
                                    
                                   
                                       
                                   
                                    
                                   
                                     P 
                                     i 
                                   
                                    
                                   
                                       
                                   
                                    
                                   corresponds 
                                    
                                   
                                       
                                   
                                    
                                   to 
                                    
                                   
                                       
                                   
                                    
                                   
                                     Q 
                                     j 
                                   
                                 
                               
                             
                             
                               
                                 0 
                               
                               
                                 otherwise 
                               
                             
                           
                            
                           
                             
 
                           
                            
                           
                               
                           
                            
                           
                             M 
                             
                               i 
                                
                               
                                 ( 
                                 
                                   
                                     N 
                                     q 
                                   
                                   + 
                                   1 
                                 
                                 ) 
                               
                             
                           
                         
                         = 
                         
                           { 
                           
                             
                               
                                 
                                   
                                     1 
                                   
                                   
                                     
                                       if 
                                        
                                       
                                           
                                       
                                        
                                       point 
                                        
                                       
                                           
                                       
                                        
                                       
                                         P 
                                         i 
                                       
                                        
                                       
                                           
                                       
                                        
                                       is 
                                        
                                       
                                           
                                       
                                        
                                       an 
                                        
                                       
                                           
                                       
                                        
                                       outlier 
                                     
                                   
                                 
                                 
                                   
                                     0 
                                   
                                   
                                     otherwise 
                                   
                                 
                               
                                
                               
                                 
 
                               
                                
                               
                                   
                               
                                
                               
                                 M 
                                 
                                   
                                     ( 
                                     
                                       
                                         N 
                                         p 
                                       
                                       + 
                                       1 
                                     
                                     ) 
                                   
                                    
                                   j 
                                 
                               
                             
                             = 
                             
                               { 
                               
                                 
                                   
                                     1 
                                   
                                   
                                     
                                       if 
                                        
                                       
                                           
                                       
                                        
                                       point 
                                        
                                       
                                           
                                       
                                        
                                       
                                         Q 
                                         j 
                                       
                                        
                                       
                                           
                                       
                                        
                                       is 
                                        
                                       
                                           
                                       
                                        
                                       an 
                                        
                                       
                                           
                                       
                                        
                                       outlier 
                                     
                                   
                                 
                                 
                                   
                                     0 
                                   
                                   
                                     otherwise 
                                   
                                 
                               
                             
                           
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   3 
                   ) 
                 
               
             
           
         
       
     
         [0081]    Equation 1 describes an optimization problem from which the transformation parameters—translation t, rotation angle θ and scale s—can be obtained by minimization. γ is a regularization parameter which controls the degree of departure of the scale parameter from unity. Equation 1 also sets up an optimization problem on the point correspondences through the correspondence variables M ij . The variable M ij  is a correspondence variable which indicates when correspondences between points have been found or outliers are discarded. The degree of robustness is enforced by the parameter α. If α is large, fewer points are discarded and vice-versa. An example of correspondence matrix is shown in Table 1. 
         [0000]    
       
         
               
               
               
               
               
               
               
             
           
               
                   
                   
               
               
                   
                 M i, j   
                 X 1   
                 X 2   
                 X 3   
                 X 4   
                 outlier 
               
               
                   
                   
               
             
             
               
                   
                 Y 1   
                 1 
                 0 
                 0 
                 0 
                 0 
               
               
                   
                 Y 2   
                 0 
                 1 
                 0 
                 0 
                 0 
               
               
                   
                 Y 3   
                 0 
                 0 
                 0 
                 0 
                 1 
               
               
                   
                 outlier 
                 0 
                 0 
                 1 
                 1 
               
               
                   
                   
               
             
          
         
       
     
         [0082]    Table 1: An example of the correspondence matrix. Points x 1  and x 2  correspond to y 1  and y 2  respectively. The rest of the points are outliers. 
         [0083]    To overcome the difficulty in jointly solving for the spatial mapping and the correspondences, the approach of ref. [3] can be followed. The Birkhoff-von Neumann theorem states that “the set of (N×N) doubly stochastic matrices is the convex hull of the set of (N×N) permutation matrices” (ref. [1]). A doubly stochastic matrix is a square matrix with all positive entries and rows and columns summing to one. Following the Birkhoff-von Neumann theorem, we relax the correspondence matrix constraints from permutation matrix constraints to doubly stochastic matrix constraints. The row and column constraints are enforced using Lagrange parameters and the positivity constraint via a barrier function ([2]): 
         [0000]    
       
         
           
             
               
                 
                   
                     E 
                      
                     
                       ( 
                       
                         M 
                         , 
                         θ 
                         , 
                         t 
                         , 
                         s 
                         , 
                         μ 
                         , 
                         v 
                       
                       ) 
                     
                   
                   = 
                   
                     
                       
                         ∑ 
                         
                           i 
                           = 
                           1 
                         
                         
                           N 
                           p 
                         
                       
                        
                       
                           
                       
                        
                       
                         
                           ∑ 
                           
                             j 
                             = 
                             1 
                           
                           
                             N 
                             q 
                           
                         
                          
                         
                           
                             M 
                             ij 
                           
                            
                           
                             
                                
                               
                                 
                                   P 
                                   i 
                                 
                                 - 
                                 t 
                                 - 
                                 
                                   
                                     sR 
                                      
                                     
                                       ( 
                                       θ 
                                       ) 
                                     
                                   
                                    
                                   
                                     Q 
                                     j 
                                   
                                 
                               
                                
                             
                             2 
                           
                         
                       
                     
                     + 
                     
                       
                         γ 
                         2 
                       
                        
                       
                         
                           ( 
                           
                             log 
                              
                             
                                 
                             
                              
                             s 
                           
                           ) 
                         
                         2 
                       
                     
                     - 
                     
                       α 
                        
                       
                         
                           ∑ 
                           
                             i 
                             = 
                             1 
                           
                           
                             N 
                             p 
                           
                         
                          
                         
                             
                         
                          
                         
                           
                             ∑ 
                             
                               j 
                               = 
                               1 
                             
                             
                               N 
                               q 
                             
                           
                            
                           
                             M 
                             ij 
                           
                         
                       
                     
                     + 
                     
                       
                         
                           
                             ∑ 
                             
                               i 
                               = 
                               1 
                             
                             
                               N 
                               p 
                             
                           
                            
                           
                             
                               μ 
                               i 
                             
                              
                             
                               ( 
                               
                                 
                                   
                                     ∑ 
                                     
                                       j 
                                       = 
                                       1 
                                     
                                     
                                       
                                         N 
                                         q 
                                       
                                       + 
                                       1 
                                     
                                   
                                    
                                   
                                     M 
                                     ij 
                                   
                                 
                                 - 
                                 1 
                               
                               ) 
                             
                           
                         
                         + 
                         
                           
                             ∑ 
                             
                               j 
                               = 
                               1 
                             
                             
                               N 
                               q 
                             
                           
                            
                           
                             
                               v 
                               i 
                             
                              
                             
                               ( 
                               
                                 
                                   
                                     ∑ 
                                     
                                       i 
                                       = 
                                       1 
                                     
                                     
                                       
                                         N 
                                         p 
                                       
                                       + 
                                       1 
                                     
                                   
                                    
                                   
                                     M 
                                     ij 
                                   
                                 
                                 - 
                                 1 
                               
                               ) 
                             
                           
                         
                       
                       
                          
                         
                           Lagrange 
                            
                           
                               
                           
                            
                           parameters 
                         
                       
                     
                     + 
                     
                       
                         
                           1 
                           β 
                         
                          
                         
                           
                             ∑ 
                             
                               i 
                               = 
                               1 
                             
                             
                               
                                 N 
                                 p 
                               
                               + 
                               1 
                             
                           
                            
                           
                             
                               ∑ 
                               
                                 j 
                                 = 
                                 1 
                               
                               
                                 
                                   N 
                                   q 
                                 
                                 + 
                                 1 
                               
                             
                              
                             
                               
                                 M 
                                 ij 
                               
                                
                               log 
                                
                               
                                   
                               
                                
                               
                                 M 
                                 ij 
                               
                             
                           
                         
                       
                       
                          
                         
                           barrier 
                            
                           
                               
                           
                            
                           function 
                            
                           
                               
                           
                            
                           for 
                            
                           
                               
                           
                            
                           positivity 
                            
                           
                               
                           
                            
                           constraint 
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   4 
                   ) 
                 
               
             
           
         
       
     
         [0084]    Fixing the spatial mapping, we can solve for the correspondence matrix M in the above objective function. Minimizing Eq. 4 w.r.t. M, we get 
         [0000]    
       
         
           
             
               
                 
                   
                     M 
                     ij 
                   
                   = 
                 
               
               
                 
                   exp 
                    
                   
                     [ 
                     
                       
                         - 
                         
                           β 
                            
                           
                             ( 
                             
                               
                                 
                                    
                                   
                                     
                                       P 
                                       i 
                                     
                                     - 
                                     t 
                                     - 
                                     
                                       
                                         sR 
                                          
                                         
                                           ( 
                                           θ 
                                           ) 
                                         
                                       
                                        
                                       
                                         Q 
                                         j 
                                       
                                     
                                   
                                    
                                 
                                 2 
                               
                               - 
                               α 
                               + 
                               
                                 μ 
                                 i 
                               
                               + 
                               
                                 v 
                                 j 
                               
                             
                             ) 
                           
                         
                       
                       - 
                       1 
                     
                     ] 
                   
                 
               
             
             
               
                 
                   
                     M 
                     
                       i 
                        
                       
                         ( 
                         
                           
                             N 
                             q 
                           
                           + 
                           1 
                         
                         ) 
                       
                     
                   
                   = 
                 
               
               
                 
                   exp 
                    
                   
                     [ 
                     
                       
                         
                           - 
                           β 
                         
                          
                         
                             
                         
                          
                         
                           μ 
                           i 
                         
                       
                       - 
                       1 
                     
                     ] 
                   
                 
               
             
             
               
                 
                   
                     M 
                     
                       
                         ( 
                         
                           
                             N 
                             p 
                           
                           + 
                           1 
                         
                         ) 
                       
                        
                       j 
                     
                   
                   = 
                 
               
               
                 
                   exp 
                    
                   
                     [ 
                     
                       
                         
                           - 
                           β 
                         
                          
                         
                             
                         
                          
                         
                           v 
                           i 
                         
                       
                       - 
                       1 
                     
                     ] 
                   
                 
               
             
           
         
       
       
         
           
             ∀ 
             
               i 
               ∈ 
               
                 { 
                 
                   1 
                   , 
                   … 
                    
                   
                       
                   
                   , 
                   
                     N 
                     p 
                   
                 
                 } 
               
             
           
         
       
       
         
           
             ∀ 
             
               j 
               ∈ 
               
                 { 
                 
                   1 
                   , 
                   … 
                    
                   
                       
                   
                   , 
                   
                     N 
                     q 
                   
                 
                 } 
               
             
           
         
       
       
         
           
             ∀ 
             
               i 
               ∈ 
               
                 { 
                 
                   1 
                   , 
                   … 
                    
                   
                       
                   
                   , 
                   
                     N 
                     p 
                   
                 
                 } 
               
             
           
         
       
       
         
           
             ∀ 
             
               j 
               ∈ 
               
                 { 
                 
                   1 
                   , 
                   … 
                    
                   
                       
                   
                   , 
                   
                     N 
                     q 
                   
                 
                 } 
               
             
           
         
       
     
         [0085]    Solving for the two Lagrange parameters using a gradient ascent approach is likely to be slow and inefficient. Now solving for the Lagrange parameters by alternating between solving for μ and then ν rather then steepest ascent is identical to Sinkhorn&#39;s algorithm (except for the added benefit of the outliers) ([4]). Sinkhorn&#39;s theorem states that “a doubly stochastic matrix is obtained from any square matrix with positive entries by the simple process of alternating row and column normalizations”. 
         [0086]    [3] refers to the barrier function control parameter β as the inverse temperature and the update of the matrix elements M ij  as the soft assign. β is slowly increased according to an annealing schedule. As the deterministic annealing parameter β is increased, the correspondence matrix entries approach binary values. Outlier rejection occurs in the limit when β→∞ with the outliers becoming binary valued. Since the entire process is deterministic, they refer to the overall approach as deterministic annealing. 
         [0087]    The spatial mapping parameters are updated with the correspondence matrix held fixed. Closed-form solutions are obtained for the rotation and translation parameters by equating to zero the partial derivatives of E(M,θ,t,s) w.r.t. to each parameter. The scale parameter is set using a few iterations of Newton&#39;s method. 
         [0088]    The pseudo code of the Robust Point Matching (RPM) algorithm is: 
         [0000]    
       
         
               
             
           
               
                   
               
             
             
               
                 • Initialize θ = 0, s = 1, t = 0, β = β 0 , M ij  = 1 + ε ij   
               
               
                 • Deterministic annealing in β 
               
               
                  • Repeat until convergence for M 
               
               
                   • Soft assign 
               
               
                    ∀i ∈ {1, . . . , N p }, ∀j ∈ {1, . . . , N q } 
               
               
                    Δ ij  ← −∥P i  − t − sR(θ)Q j ∥ 2  + α 
               
               
                    M ij  ← exp(βΔ ij ) 
               
               
                    • Sinkhorn&#39;s algorithm: Update M by alternating normalization of the  
               
               
                      rows and columns 
               
               
                     
         M   ij     ←       M   ij         ∑     j   =   1         N   q     +   1            M   ij             
 
               
               
                     
         M   ij     ←       M   ij         ∑     i   =   1         N   p     +   1            M   ij             
 
               
               
                   • Update spatial mapping 
               
               
                  • Increase β 
               
               
                   
               
             
          
         
       
     
         [0089]    ε ij  are small random variables. The algorithm is illustrated in  FIG. 9  for the alignment of 2 bones in the hand. 
         [0090]    The advantage of the RPM algorithm is that it allows to align 2 two boundary sets with a different number of points. It also is robust to missing parts (eg. missing pectoralis muscle boundary). 
         [0091]      FIG. 10  shows results of the technique applied to align the extracted breast boundaries. This example is especially selected to demonstrate that this method does not align the nipple or pectoralis. The results demonstrated in  FIG. 10  are very much suitable for image comparison compared to nipple or pectoralis aligned images. 
         [0092]    While preferred embodiments of the present invention have been described above, it is to be understood that variations and modifications will be apparent to those skilled in the art without departing from the scope and spirit of the present invention. The scope of the present invention, therefore, is to be determined solely by the following claims. 
         [0093]    The following references have been referred to: 
         [0094]    [1] J. J. Kosowsky and A. L. Yuille. The invisible hand algorithm: solving the assignment problem with statistical physics. Neural Netw., 7(3):477-490, 1994. 
         [0095]    [2] D. G. Luenberger. Linear and nonlinear programming. Addison-Wesley, 2nd edition, 1984. 
         [0096]    [3] A. Rangarajan, H. Chui, E. Mjolsness, S. Pappu, L. Davachi, P. Goldman-Rakic, and J. Duncan. A robust point matching algorithm for autoradiograph alignment. Medical Image Analysis, 4(1), 1997. 
         [0097]    [4] Anand Rangarajan, Steven Gold, and Eric Mjolsness. A novel optimizing network architecture with applications. Neural Computation, 8(5):1041-1060, 1996.