Image analysis – Pattern recognition – Template matching
Reexamination Certificate
1999-03-16
2002-03-19
Johns, Andrew W. (Department: 2621)
Image analysis
Pattern recognition
Template matching
C707S793000
Reexamination Certificate
active
06360013
ABSTRACT:
BACKGROUND OF THE INVENTION
The invention relates to matching a template to samples.
A template is a reference object having certain quantifiable characteristic properties or attributes that can be related to corresponding quantifiable characteristic properties or attributes of other objects referred to as samples. The difference between these properties or attributes is computed and the sample producing the smallest distance measure relative to the template is considered a “match.” Template matching is an important task in the field of computer vision, image processing, and pattern and voice recognition. In image processing, for example, video applications, template matching is applied to block motion estimation, stereo correspondence, pattern matching, and accumulative nonlinear optimization.
In general, given a template, T
d
(where d is the dimension of the template), and r samples in a search range, S
i
d
, i=1, . . . , r, the goal is to find the sample in S
i
d
, i=1, . . . , r, which has the smallest distance measure (i.e. has a minimum error) to the template T
d
. The dimension d of the template T
d
refers to the number of attributes characterizing the template. The attributes will be matched with attributes of the samples S
i
d
. Dimension d will also be referred to as the dimensionality of the attribute space. The distance between the sample, S
i
d
, and the template, T
d
, is frequently defined as the sum of absolute difference D(T
d
, S
i
d
)=&Sgr;
d
j=1
|T(j)−S
i
(j)| or as the sum of square differences D(T
d
, S
i
d
)=&Sgr;
d
j=1
|T(j)−S
i
(j)|
2
, where j represents the various coordinates in attribute space. Here, the distance measure D(T
d
,S
i
d
) represents the matching error between the sample, S
i
d
, and the template, T
d
. For the application of accumulative nonlinear optimization, the distance measure (or error measure) can be defined as D(S
i
)=&Sgr;
d
j=1
F(S
i
), in which F(S
i
) is a positive function. The goal of optimization is to find the S
i
that D(S
i
) is minimal in the search range.
The complexity of the straightforward algorithm for finding the global minimum using exhaustive search is of the order O(r*d). Because in many applications, the dimensionality of the attribute space and the number of samples can be very large, template matching can be a time-consuming bottleneck. Consider, for example, a video compression application. Each frame in a video sequence is first divided into square image blocks for block motion estimation that usually uses template matching techniques. Each block of the current frame is compared with the blocks in a search range of the previous frame. The attributes used in this application are usually the chromatic values of the pixels in the block. As a simple example, the block size chosen to be 16×16 with each pixel containing R, G, and B information. Thus, the attribute space is 768-dimensional (d=16×16×3=768). If the search range is chosen to be 64×64, then the number of samples will be 4096 (i.e., r=4096). Notice that this operation is required to be repeated for each block in the frame and for each frame in the video sequence.
In the past few decades, many methods have been proposed to speed up the computations of template matching for different applications. For example, in the field of object recognition, the samples in the search space can be fixed and compared with different templates (inputs). A K-dimensional binary search tree (d=K) can then be used to partition in advance the search space of the samples into hyper-rectangular buckets. The search process for the matching sample includes a global search of the order O(log r) for a target bucket and a local search for the desired sample in the target bucket and the neighboring buckets in the K-dimensional space. The performance degrades exponentially with increasing dimensionality because the query hyper-sphere tends to intersect many more adjacent buckets, causing the number of points to be examined to increase dramatically. Another drawback of this method is that whenever the samples in the search space are changed, a new K-dimensional binary search tree has to be built again, which is quite time-consuming and is usually performed in advance if the search space is static. Due to the above two drawbacks, this method is not suitable for speeding up the template matching where the samples in the search space is dynamic or when the dimensionality of the attribute space is large, such as in the case of motion estimation for video coding.
References which describe the above-mentioned K-dimensional binary search tree include:
1. J. L. Bentley, “Multidimensional Binary Search Trees Used for Associative Searching,” Comm. ACM, vol.18, no.9, pp.509-517, Sep., 1975.
2. J. L. Bentley, “Multidimensional Binary Search Trees in Database Applications,” IEEE Trans. Software Engineering, vol.5, no.4, pp.333-340, July, 1979.
For those applications for which it is impractical to partition and restrict the search space before a search, other methods need to be used to reduce the number of computations. In video compression applications, for example, gradient descent methods (e.g., three-step search) have been used to narrow the search space for block motion estimation, i.e., to omit the search in certain dimensions of the search space. The search space can also be restricted by using motion prediction from neighboring blocks or from previous frames. Another way of reducing the computational cost is to omit the search in certain dimensions of the attribute space by using a subsampling or early jump-out technique while accumulating the respective distance measures. However, all of the above-mentioned approaches do not guarantee that a global minimum will be found.
A reference which describes a three-step search is: T. Koga, K. Linuma, A. Hirano and T. Ishiguro, “Motion compensated interframe coding for video conferencing,” Proceedings of National Telecommunication Conference, pp. G5.3.1-5.3.5, November, 1981.
The work we refer to for using motion prediction is: J. Chalidabbongse and C. C. Jay Kuo, “Fast motion vector estimation using multiresolution-spatio-temporal correlations,” IEEE Trans. on Circuits and Systems for Video Technology, vol. 7, pp. 477-488, 1997.
U.S. Pat. No. 5,682,209 describes an early jump-out (or early-exit) technique which omits some dimensions of the attribute space, instead of omitting some dimensions of the search space as is the case in a three-step search.
The invention features a method of omitting certain dimensions of the attribute space to find the global optima using a different strategy than conventional approaches, such as a three-step search and an early jump-out, neither of which can guarantee finding the globally optimal match.
SUMMARY OF THE INVENTION
In general, in one aspect, the invention provides an optimal match between attributes of a template and a sample, the attributes to be matched defining an attribute space, by first computing distance measures between the template and each of the samples in a first subspace of the attribute space that has a lower dimensionality than the attribute space. The smallest distance measure of the computed distance measures is then determined and a new distance measure is computed for the sample that has the smallest distance measure in the first subspace, in a second subspace of a higher dimensionality than the first subspace. The new distance measure is compared with the distance measures previously determined in the first subspace for the other samples. A new minimal distance measure is computed and the process is repeated until the dimensionality of the subspace at which the computed new distance measure is a minimum, is equal to the dimensionality of the attribute space.
Advantageous embodiments of the invention may include one or more of the following features.
The attributes are physical properties of an object, such as size, spatial orientation
Chen Yong-Sheng
Hung Yi-Ping
Academia Sinica
Fish & Richardson P.C.
LandOfFree
Fast method and system for template matching acquiring... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Fast method and system for template matching acquiring..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Fast method and system for template matching acquiring... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2823497