Abstract:
A method and apparatus that augments the traditional Phase Plane Correlation (PPC) approach incorporates image structure into the correlation process. In so doing, the energy in spurious peaks that can occur in the phase plane correlation surface are dramatically reduced.

Description:
FIELD OF INVENTION 
       [0001]    The present invention is related to image processing. 
       BACKGROUND 
       [0002]    Phase plane correlation (PPC) is an efficient technique for correlating two images, resulting in a correlation surface in which the peaks and their respective amplitudes are a direct indication of the similarity in image luminance between the two images. In the PPC technique, a normalization step attenuates dissimilarities in luminance that results in a normalized correlation surface that is far more discerning than simple correlation. 
         [0003]    There are historical reasons for performing a luminance only analysis, such as PPC. PPC originated out of a need to perform image registration for mapping purposes. The PPC technique is an ideal tool for computing, in a very efficient manner, the translational displacement between two images when it was assumed that the images differed only by translation and variations in luminance. However, when complex motions become part of the image scene, the interpretation of the PPC surface becomes much more complicated. 
         [0004]    The traditional PPC technique only takes into account the luminance of the images. As a consequence of this, if two portions of an image are similar in luminance, then their respective correlation will be strong; even if the pixels are part of different structures in the image. This is a fundamental limitation to applying a PPC technique strictly to luminance. 
         [0005]    Therefore, there exists a need for an improved method and apparatus for image processing and correlation that takes into account image structure. 
       SUMMARY 
       [0006]    A method and apparatus that augments the traditional Phase Plane Correlation (PPC) technique incorporates image structure into the correlation process. In so doing, the energy in spurious peaks that can occur in the phase plane correlation surface are dramatically reduced. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWING(S) 
         [0007]      FIG. 1  is an image of the US Flag; 
           [0008]      FIG. 2  is a texture decomposition using anisotropic diffusion for a portion of the US flag; 
           [0009]      FIG. 3  is a block diagram of an apparatus employing the disclosed image correlation method; 
           [0010]      FIG. 4  is a flow diagram of the disclosed image correlation method; 
           [0011]      FIG. 5  is an illustration of a sequence of two images showing object motion; 
           [0012]      FIG. 6  is a PPC surface luminance only; 
           [0013]      FIG. 7  is an example anisotropic decomposition of images  1  and  2 ; 
           [0014]      FIG. 8  is a structured PPC surface; 
           [0015]      FIG. 9  is an example the PPC surface using luminance only; and 
           [0016]      FIG. 10  is a structural PPC surface taking into account the disclosed method. 
       
    
    
     DETAILED DESCRIPTION 
       [0017]    Although the features and elements are described in particular combinations, each feature or element can be used alone (without the other feature or elements) or in various combinations with or without other features and elements. 
         [0018]      FIG. 1  is an image of the United States flag. As shown in this image, there are many structures that are disparate but which are defined by near equivalent luminance. The stars and the stripes are examples of different structures with equivalent luminance. 
         [0019]      FIG. 2  is a texture decomposition of a portion of the image of the United States flag shown in  FIG. 1 . An anisotropic diffusion-based method was used to generate a (u, v) gradient vector field based on image content. As indicated hereinbefore, a Phase Plane Correlation (PPC) surface based solely on luminance would result in different structures in this image with the same luminance interacting strongly with other parts. 
         [0020]    If the stars and stripes are considered, the PPC peak energy associated with any inter-image shift that has the stars overlap with the stripes will benefit from this luminance similarity and cause any peaks associated with the stars and stripes that match to grow in amplitude. This results in unwanted peak energy that is associated with a spurious peak. As those having skill in the art know, spurious peaks are peaks that owe part of their existence to portions of the image whose luminance happens to match closely, but represents otherwise completely unrelated portions of the image. In fact, they generally represent different structures in the image and their contribution to any correlation surface should be attenuated. 
         [0021]    As such, a method and apparatus are disclosed that matches both luminance and image structure, and combines them into one surface so that the peaks result in fewer pre-assignment motion vector candidates. This method allows the correlation surface to be more discriminating and therefore, results in a more accurate computation of translational displacement between two images. 
         [0022]      FIG. 3  is a block diagram of an apparatus  100  employing the disclosed image correlation method. Referring to  FIG. 3 , apparatus  100  comprises an input processor  121 , a plurality of gradient processors  120   1 ,  120   2 , a luminance processor  122 , a plurality of decomposition processors  123   1 ,  123   2 , a gradient correlation processor  124 , and a combiner  130 . It is preferable that the luminance and the gradient correlation processors  122 ,  124 , respectively use PPC correlation. As will be appreciated, the functions performed by processors  122  and  124  are similar and, thus, alternative methods may use (and re-use) processor  122  with different inputs—images I 1  and I 2  (described below) in one operation and gradient fields (w 1 , w 2 —also described below) in a second operation. 
         [0023]    Two images I 1  and I 2  are received at apparatus  100  and forwarded to input processor  121 , and also forwarded to gradient processors  120   i  and  120   2 , respectively. Input processor  121 , coupled to luminance processor  122 , processes the received images I 1 , I 2 , for correlation, which may include smoothing or filtering the two images, for example. 
         [0024]    The process of generating the structured PPC surface includes combining a luminance-based correlation and a gradient-based correlation. The luminance-based correlation, preferably luminance-based PPC correlation, is a cross-correlation between images that is normalized with respect to offsets in brightness. The process of correlation is one where the two images slide over one another and the overlapping portions of the images are summed. The sum is a measure of similarity between the two images at particular shifts in the x and y directions. 
         [0025]    Referring to  FIG. 3 , luminance processor  122  receives the processed image signals I 1  and I 2 . Luminance processor  122  conducts a real correlation analysis of images using a luminance-based PPC correlation, where alpha=1. The luminance-based PPC correlation is determined using the following: 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       PPC 
                        
                       
                         ( 
                         
                           
                             I 
                             1 
                           
                           , 
                           
                             I 
                             2 
                           
                         
                         ) 
                       
                     
                     = 
                     
                       
                         F 
                         
                           - 
                           1 
                         
                       
                        
                       
                         ( 
                         
                           
                             
                               F 
                                
                               
                                 ( 
                                 
                                   I 
                                   1 
                                 
                                 ) 
                               
                             
                             × 
                             
                               
                                 F 
                                  
                                 
                                   ( 
                                   
                                     I 
                                     2 
                                   
                                   ) 
                                 
                               
                               * 
                             
                           
                           
                              
                             
                               
                                 F 
                                  
                                 
                                   ( 
                                   
                                     I 
                                     1 
                                   
                                   ) 
                                 
                               
                               × 
                               
                                 
                                   F 
                                    
                                   
                                     ( 
                                     
                                       I 
                                       2 
                                     
                                     ) 
                                   
                                 
                                 * 
                               
                             
                              
                           
                         
                         ) 
                       
                     
                   
                   ; 
                 
               
               
                 
                   Equation 
                    
                   
                       
                   
                    
                   
                     ( 
                     1 
                     ) 
                   
                 
               
             
           
         
       
     
         [0000]    where F(I 1 ) and F(I 2 ) are the Fourier transforms of the images I 1  and I 2  respectively; F(I 2 )* is the complex conjugate of F(I 2 ). It should be noted that this quantity is based on luminance similarity only. Although the disclosed method is described herein using the frequency domain, correlation may be done in the time domain. In the frequency domain, though, it is more efficient and the correlation can be normalized with respect to luminance. 
         [0026]    Once luminance processor  122  has completed its correlation analysis, the resulting points PPC (I 1 , I 2 ) are forwarded to combiner  130 , preferably a multiplier, for combining with a gradient-based PPC correlation, to be described below. 
         [0027]    As indicated, the received images I 1 , I 2  are forwarded to gradient processors  120  respectively, (I 1  to gradient processor  120   1  and I 2  to gradient processor  120   2 ). Gradient processors  120   1 ,  120   2  estimate local structure dimensionality, for example using Gradient Square Tensor (GST). The values generated by gradient processors  120   1  and  120   2  are then forwarded to decomposition processors  123   1  and  123   2 , respectively. Although images I 1  and I 2  are shown as being forwarded to gradient processor  120   1 ,  120   2  prior to input processor  121 , the images used by gradient processors  120   1 ,  120   2  may first be processed by input processor  121 , as disclosed above, and then forwarded to gradient processor  120   1 ,  120   2 . Also, gradient processor  120   1 ,  120   2  may be a single processor that makes local structure dimensionality of both images I 1 , I 2  and forwards each separately to decomposition processors  123   1 ,  123   2 . 
         [0028]    Decomposition processors  123   1  and  123   2 , coupled to gradient processors  120   1  and  120   2 , respectively, and gradient correlation processor  124 , then derive a complex gradient field for each image I 1  and I 2  received from gradient processors  120 . The complex gradient field is derived by defining an array of complex phasors from a gradient decomposition by forming: 
         [0000]        w=u+j·v;   Equation (2) 
         [0000]    where j=√{square root over (−1)} and u(x,y) and v(x,y) are the x and y components of the gradient direction. The more accurately the decomposition reflects the structures in the image, the better structural cross-talk during correlation will be attenuated. As such, it is preferable, but not required, for decomposition processors  123   1 ,  123   2  to use anisotropic decomposition with an energy diffusion term. 
         [0029]    Anisotropic decomposition allows larger structures defined by their boundaries to maintain their structural orientation well away from their edges. As those having skill in the art would recognize, without energy diffusion, the estimate of direction, (i.e., u+jv), is limited to the breadth of the kernel used to perform the gradient decomposition. By adding a diffusion term to the gradient field, what is tantamount to a regularization step that captures image structure more generally is performed. Without diffusion, flat areas into which the entire gradient analysis kernel fits will result in a non-direction (no structure). That is, u and v will be approximately zero. In this case, the structured PPC surface will simply degenerate to the luminance PPC for flat areas with similar gradients. Although anisotropic decomposition with an energy diffusion term is preferable, any gradient decomposition, or any other structural decomposition, which doesn&#39;t propagate the gradient field into flat areas may be used. 
         [0030]    Once decomposition processors  123   1 ,  123   2  derive the gradient field for each image w 1 , w 2 , a correlation analysis is conducted by gradient correlation processor  124 . In accordance with the disclosed image correlation method, gradient correlation processor  124  conducts a gradient-based PPC analysis on each derived gradient field w 1 , w 2 . 
         [0031]    Gradient correlation processor  124 , coupled to decomposition processors  123   1  and  123   2  and combiner  130 , receives the gradient fields w 1 , w 2  from decomposition processors  123   1  and  123   2 , respectively. Using gradient fields w 1 , and w 2 , gradient correlation processor  124  conducts a gradient-based correlation analysis, preferably gradient-based PPC correlation. 
         [0032]    The gradient-based PPC (image structure based PPC correlation), which is a measure of the correlation in the structure of the image content, is computed using the following: 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       PPC 
                        
                       
                         ( 
                         
                           
                             w 
                             1 
                           
                           , 
                           
                             w 
                             2 
                           
                         
                         ) 
                       
                     
                     = 
                     
                       
                         F 
                         
                           - 
                           1 
                         
                       
                        
                       
                         ( 
                         
                           
                             
                               F 
                                
                               
                                 ( 
                                 
                                   w 
                                   1 
                                 
                                 ) 
                               
                             
                             × 
                             
                               
                                 F 
                                  
                                 
                                   ( 
                                   
                                     w 
                                     2 
                                   
                                   ) 
                                 
                               
                               * 
                             
                           
                           
                              
                             
                               
                                 F 
                                  
                                 
                                   ( 
                                   
                                     w 
                                     1 
                                   
                                   ) 
                                 
                               
                               × 
                               
                                 
                                   F 
                                    
                                   
                                     ( 
                                     
                                       w 
                                       2 
                                     
                                     ) 
                                   
                                 
                                 * 
                               
                             
                              
                           
                         
                         ) 
                       
                     
                   
                   , 
                 
               
               
                 
                   Equation 
                    
                   
                       
                   
                    
                   
                     ( 
                     3 
                     ) 
                   
                 
               
             
           
         
       
     
         [0000]    where, again, w 1  and w 2  represent the complex gradient fields for images I 1  and I 2 , respectively, and F(w 1 ) and F(w 2 ) are the respective Fourier transforms. Gradient correlation processor  124 , therefore, determines the gradient-based correlation between the received images I 1  and I 2  and forwards the values PPC (w 1 , w 2 ) to multiplier  130 . 
         [0033]    Combiner  130 , coupled to gradient correlation processor  124  and luminance processor  122 , receives the luminance-based correlation values PPC (I 1 , I 2 ) from processor  122  and the gradient-based correlation values PPC (w 1 , w 2 ) from processor  124 . Combiner  130  then combines the luminance-based PPC and the gradient-based PPC into one surface, producing a list of unassigned motion vector candidates. The luminance-based PPC and gradient-based PPC are combined in accordance with the following: 
         [0000]      SPPC=PPC( I   1   ,I   2 )×PPC( w   1   ,w   2 ).  Equation (4) 
         [0000]    In this way, structures that are unrelated in each image will contribute far less to the overall candidate list than otherwise. As those having skill in the art know, the resulting candidate motion vectors may then be validated and used for further image processing, such as format conversion, de-interlacing, and any others where any sort of temporal interpolation is necessary. Although it is preferable that combiner  130  multiplies the surfaces to generate the structure PPC, any type of combiner may be used. For example, a weighting matrix may be applied to the image (signal) being correlated. 
         [0034]    A flow diagram of the disclosed method of correlation is illustrated in  FIG. 4 . As indicated hereinbefore, two images I 1 , I 2  are received by apparatus  100  for image processing and correlation, (step  400 ). Both images I 1 , I 2  are forwarded to gradient processors  120   1 ,  120   2  and decomposition processors  123   1 ,  123   2 , for determining the local structure dimensionality and a gradient field w 1 , w 2  for each image I 1 , I 2 , and luminance processor  122 , for luminance-based correlation, (step  401 ). A gradient field w 1 , w 2  for each image I 1 , I 2  is generated by gradient processors  120   1 ,  120   2  and decomposition processors  123   1 ,  123   2 , (step  402 ). Luminance-based PPC correlation is conducted for each image, (step  403 ). Gradient-based PPC correlation is conducted on each of the gradient fields w 1 , w 2  for the images I 1 , I 2  (step  404 ). The luminance-based correlation structure and gradient-based correlation structure are forwarded to combiner  130 , (step  405 ) for combining. Combiner  130  then combines the luminance-based PPC correlation and gradient-based PPC, (step  406 ), thereby generating a structure that considers the luminance and the structure of each image I 1 , I 2 . Although the luminance-based PPC correlation has been disclosed as being conducted after the gradient field is generated and before gradient-based PPC correlation, luminance-based correlation may be done in parallel, before or after gradient processing of the images I 1 , I 2 . 
         [0035]    An example of the present method is demonstrated in  FIG. 5 . Referring to  FIG. 5 , a sequence of two images (image  1  and image  2 ), each of which contains two objects with identical luminance, is shown. In accordance with this example, one object moves to the right by 20 pixels and another moves down by 30 pixels. Using the standard PPC surface (alpha=1) for these images results in a surface as shown in  FIG. 6 . 
         [0036]    It should be noted in  FIG. 6  that the surface is quite noisy and contains many spurious peaks. The largest 10 peaks (in amplitude) are shown in Table 1. 
         [0000]                                                TABLE 1                   Largest 10 peaks for PPC (alpha = 1)            Peak               Magnitude   Y-position   X-position                    0.5139   0   20.0000       0.4923   30.0000   0       0.1613   0   15.0000       0.1460   30.0000   31.0000       0.1433   30.0000   5.0000       0.1427   35.0000   0       0.1418   30.0000   −5.0000       0.1401   34.0000   −34.0000       0.1391   5.0000   20.0000       0.1295   30.0000   −31.0000                    
As shown in Table 1, the ratio of peak heights (correlation energy) between the first two peaks to the total peak energy for the first ten peaks is 46.8%. That is, the non-spurious peak energy is larger than the true displacement.  FIG. 7  illustrates the anisotropic decomposition for images  1  and  2 .
 
         [0037]    When both the structure and luminance are combined as disclosed above, the correlation surface shown in  FIG. 8  is obtained. 
         [0038]    The peak surface in  FIG. 8  contains only two peaks and no spurious peaks of significance. The two peaks are therefore, the likely true peaks of interest. The corresponding largest ten peaks (in magnitude) are shown in Table 2. 
         [0000]                                                TABLE 2                   Largest 10 peaks for Structured PPC.            Peak   y-   x-       Magnitude   position   position                    0.2681   0   20.0000       0.2363   30.0000   0       0.0103   −36.0000   46.0000       0.0093   34.0000   −34.0000       0.0085   30.0000   −5.0000       0.0082   0   15.0000       0.0074   35.0000   0       0.0072   5.0000   20.0000       0.0059   30.0000   5.0000       0.0053   −5.0000   20.0000                    
As shown in Table 2, the ratio of peak heights (correlation energy) for the first two peaks to the total peak energy for the first ten peaks is now almost 90%. That is, the non-spurious peak energy constitutes only 10% of the total peak energy. This represents a five-fold decrease in energy in the spurious peaks.
 
         [0039]    Using the image of  FIG. 2 ,  FIG. 9  illustrates the correlation of the surface using luminance only. As clearly shown in  FIG. 9 , the peak is not significantly differentiated. The energy is widely distributed because the luminance only correlation cares only about similar luminance and not about image structure. 
         [0040]    However, when the structural PPC surface is computed and taken into account along with the luminance correlation, as shown in  FIG. 10 , a much more differentiated (sharper) peak is obtained with far less energy distributed throughout the entire surface. As shown, using both structural and luminance correlations results in an immediate marked reduction in the energy away from the true match. Thereby generating a more accurate correlation between two images. 
         [0041]    The disclosed method computes an image similarity based on the PPC technique that takes into account image structure. In so doing, PPC based on combining luminance and a textural decomposition of the image mitigates the affect of spurious peak energy; an undesirable consequence of the PPC technique. 
         [0042]    Although this method is disclosed using a two-dimensional image, it should be noted that this method may be employed in a non-dimension or three dimension images as well. A series of images can be used, which when arranged side-by-side cause objects in the image sequence to form volumes. These volumes also have a structure in three dimensions and the disclosed structured PPC method can be used. In general, due to the separability of the Fast Fourier Transform (FFT), the disclosed structured PPC method can be performed in an arbitrary number of dimensions. If cause relationships between multi-dimensional quantities, such as is the case in data mining, are being investigated, (on to name but one example where data is multi-dimensional), the disclosed correlation method may be applicable. 
         [0043]    Although the features and elements are described in particular combinations, each feature or element can be used alone without the other features and elements or in various combinations with or without other features and elements. The methods or flow charts provided may be implemented in a computer program, software, or firmware tangibly embodied in a computer-readable storage medium for execution by a general purpose computer or a processor. Examples of computer-readable storage mediums include a read only memory (ROM), a random access memory (RAM), a register, cache memory, semiconductor memory devices, magnetic media such as internal hard disks and removable disks, magneto-optical media, and optical media such as CD-ROM disks, and digital versatile disks (DVDs). 
         [0044]    Suitable processors include, by way of example, a general purpose processor, a special purpose processor, a conventional processor, a digital signal processor (DSP), a plurality of microprocessors, one or more microprocessors in association with a DSP core, a controller, a microcontroller, Application Specific Integrated Circuits (ASICs), Field Programmable Gate Arrays (FPGAs) circuits, any other type of integrated circuit (IC), and/or a state machine.