Use of Fourier and Karhunen-Loeve Decomposition for Fast Pattern-Matching
with a Large Set of Templates
M. Uenohara, and T. Kanade. Transactions on Pattern Recognition and Machine Intelligence, 19 (8):
891-898(August 1997)
Abstract
Abstract: We present a fast pattern matching algorithm with a large
set of templates. The algorithm is based on the typical template
matching speeded up by the dual decomposition; the Fourier transform
and the Karhunen-Loeve transform. The proposed algorithm is appropriate
for the search of an object with unknown distortion within a short
period. Patterns with different distortion differ slightly from each
other and are highly correlated. The image vector subspace required
for effective representation can be defined by a small number of
eigenvectors derived by the Karhunen-Loeve transform. A vector subspace
spanned by the eigenvectors is generated, and any image vector in
the subspace is considered as a pattern to be recognized. The pattern
matching of objects with unknown distortion is formulated as the
process to extract the portion of the input image, find the pattern
most similar to the extracted portion in the subspace, compute normalized
correlation between them at each location in the input image, and
find the location with the best score. Searching for objects with
unknown distortion requires vast computation. The formulation above
makes it possible to decompose highly correlated reference images
into eigenvectors, as well as to decompose images in frequency domain,
and to speed up the process significantly. Index Terms: Template
matching, pattern matching, Karhunen-Loeve transform, Fourier transform,
eigenvector.
%0 Journal Article
%1 Uenohara1997
%A Uenohara, M.
%A Kanade, T.
%D 1997
%J Transactions on Pattern Recognition and Machine Intelligence
%K imported
%N 8
%P 891-898
%T Use of Fourier and Karhunen-Loeve Decomposition for Fast Pattern-Matching
with a Large Set of Templates
%U http://www.ri.cmu.edu/pub_files/pub2/uenohara_michihiro_1997_1/uenohara_michihiro_1997_1.pdf
%V 19
%X Abstract: We present a fast pattern matching algorithm with a large
set of templates. The algorithm is based on the typical template
matching speeded up by the dual decomposition; the Fourier transform
and the Karhunen-Loeve transform. The proposed algorithm is appropriate
for the search of an object with unknown distortion within a short
period. Patterns with different distortion differ slightly from each
other and are highly correlated. The image vector subspace required
for effective representation can be defined by a small number of
eigenvectors derived by the Karhunen-Loeve transform. A vector subspace
spanned by the eigenvectors is generated, and any image vector in
the subspace is considered as a pattern to be recognized. The pattern
matching of objects with unknown distortion is formulated as the
process to extract the portion of the input image, find the pattern
most similar to the extracted portion in the subspace, compute normalized
correlation between them at each location in the input image, and
find the location with the best score. Searching for objects with
unknown distortion requires vast computation. The formulation above
makes it possible to decompose highly correlated reference images
into eigenvectors, as well as to decompose images in frequency domain,
and to speed up the process significantly. Index Terms: Template
matching, pattern matching, Karhunen-Loeve transform, Fourier transform,
eigenvector.
@article{Uenohara1997,
abstract = {Abstract: We present a fast pattern matching algorithm with a large
set of templates. The algorithm is based on the typical template
matching speeded up by the dual decomposition; the Fourier transform
and the Karhunen-Loeve transform. The proposed algorithm is appropriate
for the search of an object with unknown distortion within a short
period. Patterns with different distortion differ slightly from each
other and are highly correlated. The image vector subspace required
for effective representation can be defined by a small number of
eigenvectors derived by the Karhunen-Loeve transform. A vector subspace
spanned by the eigenvectors is generated, and any image vector in
the subspace is considered as a pattern to be recognized. The pattern
matching of objects with unknown distortion is formulated as the
process to extract the portion of the input image, find the pattern
most similar to the extracted portion in the subspace, compute normalized
correlation between them at each location in the input image, and
find the location with the best score. Searching for objects with
unknown distortion requires vast computation. The formulation above
makes it possible to decompose highly correlated reference images
into eigenvectors, as well as to decompose images in frequency domain,
and to speed up the process significantly. Index Terms: Template
matching, pattern matching, Karhunen-Loeve transform, Fourier transform,
eigenvector.},
added-at = {2011-03-27T19:47:06.000+0200},
author = {Uenohara, M. and Kanade, T.},
bibsource = {http://www.visionbib.com/bibliography/match-pl489.html#TT37776},
biburl = {https://www.bibsonomy.org/bibtex/20a1ebed98406aa7011ae64fbd8f0d304/cocus},
file = {:./uenohara_michihiro_1997_1.pdf:PDF},
interhash = {43ffbd3497ec2aa9ff5dbda3eb73563e},
intrahash = {0a1ebed98406aa7011ae64fbd8f0d304},
journal = {Transactions on Pattern Recognition and Machine Intelligence},
keywords = {imported},
month = {August},
number = 8,
owner = {CK},
pages = {891-898},
timestamp = {2011-03-27T19:47:10.000+0200},
title = {Use of Fourier and Karhunen-Loeve Decomposition for Fast Pattern-Matching
with a Large Set of Templates},
url = {http://www.ri.cmu.edu/pub_files/pub2/uenohara_michihiro_1997_1/uenohara_michihiro_1997_1.pdf},
volume = 19,
year = 1997
}