Image analysis – Pattern recognition – Template matching
Reexamination Certificate
1998-12-18
2001-06-05
Au, Amelia M. (Department: 2623)
Image analysis
Pattern recognition
Template matching
C382S217000, C382S278000
Reexamination Certificate
active
06243494
ABSTRACT:
BACKGROUND OF THE INVENTION
This invention relates to template matching within a data domain, and more particularly to a method for locating a given data template within a data domain.
Template matching in the context of an image search is a process of locating the position of a subimage within an image of the same, or more typically, a larger size. The subimage is referred to as the template and the larger image is referred to as the search area. The template matching process involves shifting the template over the search area and computing a similarity between the template and the window of the search area over which the template lies. Another step involves determining a single or a set of matched positions in which there is a good similarity measure between the template and the search area window.
A common technique for measuring similarity in template matching and image registration is cross-correlation. A correlation measure is determined between the template and respective windows of the search area to find the template position which has maximum correlation. For a two-dimensional search area the correlation function generally is computed for all translations of the template within the search area. A statistical correlation measure is a common approach in which window areas are spatially convolved with the template using spatial filter functions. Because this approach is extremely expensive in terms of computation time, a more common computer implementation is to use a sum of absolute differences.
Rosenfeld et al., in “Coarse-Fine Template Matching,” IEEE Transactions on Systems, Man and Cybernetics (February 1977, pp. 104-107) describe an approach where a ‘reduced-resolution’ template is used during a first, coarse evaluation stage. The template is divided into blocks of equal size (e.g., ‘m’ pixels per block). The average of each block is computed. For each pixel of the search area an average also is calculated over a neighborhood of the same size as the reduced-resolution template (e.g., m pixels). The average absolute difference between each template block average and the picture neighborhood average then is computed for each pixel of the search area. If the average absolute difference for any pixel of the search area is below a select value, then a possible match has been identified. Next, the full resolution template is compared to a window of the search area about each pixel point where the average absolute difference in the prior coarse evaluation step was below the threshold value. This fine evaluation step identifies if there actually is a good correlation.
Goshtasby et al. in “A Two-Stage Correlation Approach to Template Matching,” IEEE Transaction on Pattern Analysis and Machine Intelligence, (Vol. PAMI-6, No. 3, May 1984), note the need for an accurate threshold value for the first stage evaluation. They describe a method for deriving the threshold value based upon subtemplate size and false dismissal probability.
The coarse-fine or two stage method subsample the template to match with the image. The task of subsampling the template is not a trivial task and contributes significant processing cost. In addition, the false alarms result in wasted, or an ineffective use of, processing time. Accordingly, there is a need for a more efficient method of template matching.
In the area of motion estimation for digital video and multimedia communications a three stage correlation strategy is used. In a first step, a search step size of 4 is used. Once a maximum point is found, the step size is reduced to 2 to evaluate the neighborhood of the previously determined point to choose the next search point. The third step is to search all neighboring points to find the best match. This approach speeds up the search process, but also has a high probability of mismatches or suboptimal matches. It also has difficulty handling cases in which multiple match points occur. Thus, there is a need for a more reliable, fast search method for correlating a template to windows of a search area. Further, there is a need for performing a search among 3 data dimensions using either a two dimensional.
SUMMARY OF THE INVENTION
According to the invention, a 3-dimensional correlation auto-predictive search (3-D CAPS) method is used to compare a 2-dimensional template to various 2-dimensional windows of a search area. The location(s) where the template has the highest correlation coefficient with an underlying window is selected as a match for the template. The principle of 3-D CAPS as conceived by the inventors is (1) to extract statistical information from the template itself to determine search step sizes, and (2) to perform fast searching based on this extracted information. Searching is performed by correlating the template to various windows of a search area. The windows are selected along 3 dimensions. For a 2 dimensional search area two of the dimensions for selecting windows are the two dimensions of the search area. A third dimension corresponds to searches among manipulations of the search area and template or additional slices of the search area. In one embodiment the template is rotated relative to the search area. In such embodiment the third dimension is rotation. In another embodiment the template is scaled (e.g., zooming in or out) relative to the search area. In such embodiment the third dimension is scaling factor. In another embodiment the template and the search area are subsampled to vary the resolution of each. In such embodiment the third dimension is subsampling factor (i.e., resolution). Each of such examples correspond to manipulations of the search area relative to the template. these manipulations may result in additional slices of the search area, in which the search area content is manipulated (e.g., rotated, scaled or subsampled). In other embodiments the third dimension is time, frequency or space. For example, subsequent frames of the subject matter of the search area may be captured over time. In another example, additional samplings of the subject matter of the search area are captured for differing frequencies. In yet another example the subject matter is captured in three spatial dimensions resulting in a three dimensional search area.
According to one aspect of the invention, during a first analytical step, autocorrelation is performed on the template to generate desired statistics. To use autocorrelation, the original template is padded with additional pixels to increase the template size. Cross-correlation then is performed between the padded template and the original template. The autocorrelation is highest at the center of the padded template as this area is formed by the original template. This corresponds to a peak in a graph of the autocorrelation of the padded template to original template. The width of the peak, either along a horizontal direction of the padded template, or along a vertical direction of the padded template, may be measured. The height of the maximum peak is 1.0. The horizontal width is taken as the distance along the horizontal axis between autocorrelation values of, for example, 0.5 to each side of the maximum peak. Similarly, the vertical width is taken as the distance along the vertical axis between autocorrelation values of 0.5 to each side of the maximum peak. Such value, 0.5, is referred to herein as the cut value. The cut value is exemplary and may differ for various embodiments.
The correlation between the padded template and the original template is derived about the center of the padded template along both horizontal and vertical axes. As the correlations are derived during this stepping along the axes, there comes a point where the correlation decreases to the cut value. Along the horizontal axis, there is a cut value reached to either direction of center. The horizontal distance between these two locations where the correlation has decreased to the cut value is the horizontal width. Further correlations along such axis need not be derived. Along the vertical axis, there also is a cut value reached to either direction
Kim Yongmin
Sun Shijun
Au Amelia M.
Dastouri Mehrdad
Koda Steven P.
University of Washington
LandOfFree
Template matching in 3 dimensions using correlative... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Template matching in 3 dimensions using correlative..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Template matching in 3 dimensions using correlative... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2497465