Use of Fourier and Karhunen-Loeve Decomposition for Fast Pattern Matching With a Large Set of Templates

Michihiro Uenohara and Takeo Kanade
IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 19, No. 8, August, 1997, pp. 891 - 898.


Download
  • Adobe portable document format (pdf) (857KB)
Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.

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.

Notes

Text Reference
Michihiro Uenohara and Takeo Kanade, "Use of Fourier and Karhunen-Loeve Decomposition for Fast Pattern Matching With a Large Set of Templates," IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 19, No. 8, August, 1997, pp. 891 - 898.

BibTeX Reference
@article{Uenohara_1997_960,
   author = "Michihiro Uenohara and Takeo Kanade",
   title = "Use of Fourier and Karhunen-Loeve Decomposition for Fast Pattern Matching With a Large Set of Templates",
   journal = "IEEE Transactions on Pattern Analysis and Machine Intelligence",
   pages = "891 - 898",
   month = "August",
   year = "1997",
   volume = "19",
   number = "8",
}