Multiresolutional critical point filter and image matching using the same

Abstract

A multiresolutional filter called a critical point filter is introduced. This filter extracts a maximum, a minimum, and two types of saddle points of pixel intensity for every 2×2 (horizontal×vertical) pixels so that an image of a lower level of resolution is newly generated for every type of a critical point. Using this multiresolutional filter, a source image and a destination image are hierarchized, and source hierarchical images and destination hierarchical images are matched using image characteristics recognized through a filtering operation.

What is claimed is:  
     
         1 . A multiresolutional filtering method comprising: 
 a detection step of detecting a critical point through a two dimensional search carried out on a first image; and    a generation step of generating a second image having a lower resolution than that of the first image through extraction of the critical point detected.    
     
     
         2 . A method as defined in  claim 1 , wherein a critical point is searched for inside each of a plurality of blocks constituting the first image.  
     
     
         3 . A method as defined in  claim 2 , wherein a critical point is detected by searching for a point having either a maximum or minimum pixel value in two directions of each of the blocks .  
     
     
         4 . A method as defined in  claim 3 , wherein a pixel having a maximum pixel value in the two directions is detected as a maximum.  
     
     
         5 . A method as defined in  claim 3 , wherein a pixel having a minimum pixel value in the two directions is detected as a minimum.  
     
     
         6 . A method as defined in  claim 3 , wherein a pixel having a maximum pixel value in one of the two directions and a minimum pixel value in the other direction is detected as a saddle point.  
     
     
         7 . A method as defined in  claim 3 , wherein each of the blocks includes four pixels consisting of two pixels in a horizontal direction and two pixels in a vertical direction; and 
 each of the four pixels is classified into either a maximum, a minimum, or one of two types of saddle points.    
     
     
         8 . A method as defined in  claim 2 , wherein an image of a critical point detected inside a block is made to represent an image of the block to thereby reduce resolution of the image.  
     
     
         9 . A method as defined in  claim 2 , wherein the second image is generated for each type of a critical point detected inside each of the blocks.  
     
     
         10 . An image matching method comprising: 
 a first step of generating source hierarchical images each having a different resolution through multiresolutional critical point filtering carried out to a source image;    a second step of generating destination hierarchical images each having a different resolution through multiresolutional critical point filtering carried out to a destination image; and    a third step of matching the source hierarchical images and the destination hierarchical images.    
     
     
         11 . A method as defined in  claim 10 , wherein a mapping between an image of a certain level of resolution among the source hierarchical images and an image of the same level of resolution among the destination hierarchical images is determined in consideration of a mapping at another predetermined level of resolution.  
     
     
         12 . A method as defined in  claim 11 , wherein the mapping is determined using the mapping at the predetermined level of resolution as a constraint.  
     
     
         13 . A method as defined in  claim 11 , wherein the predetermined level of resolution is a coarser level than that at which the mapping is currently determined.  
     
     
         14 . A method as defined in  claim 13 , wherein the predetermined level of resolution is one level coarser than that at which the mapping is currently determined.  
     
     
         15 . A method as defined in  claim 11 , wherein a mapping is first determined at a coarsest level of resolution, and then sequentially at finer levels of resolution.  
     
     
         16 . A method as defined in  claim 11 , wherein the mapping is determined so as to satisfy Bijectivity conditions.  
     
     
         17 . A method as defined in  claim 16 , wherein a relaxation is provided to the Bijective conditions.  
     
     
         18 . A method as defined in  claim 17 , wherein the relaxation is to allow a mapping to be retraction.  
     
     
         19 . A method as defined in  claim 11 , wherein the source hierarchical images and the destination hierarchical images are generated for each type of a critical point, and the mapping is computed for each type of a critical point.  
     
     
         20 . A method as defined in  claim 19 , wherein a mapping is computed for a certain type of a critical point in consideration of a mapping which has already been obtained for another type of a critical point at the same level of resolution.  
     
     
         21 . A method as defined in  claim 20 , wherein the mapping is computed under a condition that the mapping should be similar to the mapping which has already been obtained.  
     
     
         22 . A method as defined in  claim 10 , wherein a plurality of evaluation equations are defined according to a plurality of matching evaluation items; 
 the plurality of evaluation equations are combined so as to define a combined evaluation equation; and    an optimal matching is searched while noting the neighborhood of an extreme of the combined evaluation equation.    
     
     
         23 . A method as defined in  claim 22 , wherein the combined evaluation equation is defined as a sum of the plurality of equation equations at least one of which has been multiplied by a coefficient parameter.  
     
     
         24 . A method as defined in  claim 23 , wherein each of the plurality of evaluation equations takes a smaller value for better evaluation, and the coefficient parameter is automatically determined so that a minimum of the combined evaluation equation becomes its smallest value.  
     
     
         25 . A method as defined in  claim 23 , wherein each of the plurality of evaluation equations takes a larger value for better evaluation, and the coefficient parameter is automatically determined so that a maximum of the combined evaluation equation becomes its largest value.  
     
     
         26 . A method as defined in  claim 23 , wherein the coefficient parameter is automatically determined by detecting the neighborhood of an extreme of one of the plurality of evaluation equations.  
     
     
         27 . A method as defined in  claim 22 , wherein the combined evaluation equation is defined as a linear sum of a first evaluation equation for a pixel value and a second evaluation equation for a pixel location; 
 a value of the first evaluation equation is recorded when the combined evaluation equation takes a value which is in the neighborhood of an extreme while varying a coefficient parameter of at least the first evaluation equation; and    the coefficient parameter is fixed when the first evaluation equation takes a value which is in the neighborhood of an extreme and is used in subsequent evaluations.    
     
     
         28 . An image matching method wherein, for matching a source image and a destination image, an evaluation equation is set for each of a plurality of matching evaluation items; 
 the plurality of evaluation equations are combined so as to define a combined evaluation equation; and    an optimal matching is searched while noting the neighborhood of an extreme of the combined evaluation equation.    
     
     
         29 . A method as defined in  claim 28 , wherein the combined evaluation equation is defined as a sum of the plurality of equation equations at least one of which has been multiplied by a coefficient parameter.  
     
     
         30 . A method as defined in  claim 29 , wherein each of the plurality of evaluation equations takes a smaller value for better evaluation, and the coefficient parameter is automatically determined so that a minimum of the combined evaluation equation becomes its smallest value.  
     
     
         31 . A method as defined in  claim 29 , wherein each of the plurality of evaluation equations takes a larger value for better evaluation, and the coefficient parameter is automatically determined so that a maximum of the combined evaluation equation becomes its largest value.  
     
     
         32 . A method as defined in  claim 29 , wherein the coefficient parameter is automatically determined by detecting the neighborhood of an extreme of one of the plurality of evaluation equations.  
     
     
         33 . A method as defined in  claim 28 , wherein the combined evaluation equation is defined as a linear sum of a first evaluation equation for a pixel value and a second evaluation equation for a pixel location; 
 a value of the first evaluation equation is recorded when the combined evaluation equation takes a value which is in the neighborhood of an extreme while varying a coefficient parameter of at least the first evaluation equation; and    the coefficient parameter is fixed when the first evaluation equation takes a value which is in the neighborhood of an extreme and is used in subsequent evaluations.    
     
     
         34 . A multiresolutional filtering method, wherein a critical point is detected in a first image by performing a two dimensional search, and a second image having a lower resolution than that of the first image is generated with the critical point detected.  
     
     
         35 . An image matching method, wherein source hierarchical images each having a different resolution is generated through multiresolutional critical point filtering carried out to a source image; 
 destination hierarchical images each having a different resolution is generated through multiresolutional critical point filtering carried out to a destination image; and    the source hierarchical images and the destination hierarchical images are matched.