Template matching system for images

• US 6,628,834 B2
• Filed: 07/11/2002
• Issued: 09/30/2003
• Est. Priority Date: 07/20/1999
• Status: Expired due to Fees

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Gotsman, Craig, Elad, Michael, Keren, Daniel
• Primary Examiner(s): Mariam, Daniel G.
• Application Number:
  US10/193,077
• Publication Number:
  US 20030026485A1
• Time in Patent Office: 446 Days
• Field of Search: 382/103, 382/115-119, 382/155, 382/159, 382/173, 382/181, 382/197, 382/209, 382/217-220, 382/224, 382/254, 382/258, 382/276, 382/278, 382/305, 358/403, 348/169, 707/1-10
• US Class Current: 382/209
• CPC Class Codes: G06F 16/583 using metadata automatically derived from the content
• CPC Class Codes: G06F 18/213 Feature extraction, e.g. by transforming the feature space; Summarisation; Mappings, e.g. subspace methods
• CPC Class Codes: G06V 40/161 Detection; Localisation; Normalisation
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99936 Pattern matching access

Abstract

This disclosure provides a system for classifying images, used in image detection, image recognition, or other computer vision. The system processes directory images to obtain eigenvectors and eigenvalues, and selects a set of “smooth” basis vectors formed by linear combinations of these eigenvectors to be applied against a target image. Contrary to conventional wisdom, however, a group of the eigenvectors having the weakest eigenvalues are used to select the basis vectors. A second process is then performed on this group of “weakest” eigenvectors to identify a set of candidate vectors, ordered in terms of “smoothness.” The set of basis vectors (preferably 3-9) is then chosen from the candidate vectors in order of smoothness, which are then applied in an image detection or image recognition process. Unlike some conventional systems where “strong” directory presence and thresholds are used to detect possible matches, the present system uses smooth, weak vectors to ideally produce zero or near zero results for matches.

Claims

1. In a template matching system having both a training phase, in which a directory of image examples is processed by a digital computer to derive component vectors, as well as a search phase, in which a digital computer processes a target image with vectors selected using component vectors to thereby determine presence of one or more image examples in the target image, an improvement comprising:

identifying component vectors which most negatively correlate with the directory of image examples;

applying a function to component vectors to yield a result from which relative smoothness of vectors in a set can be determined;

selecting a subset of the vectors in the set for processing the target image, the subset including only relatively smooth vectors which relatively negatively correlate with the directory of image examples.

2. An improvement according to claim 1, further comprising using during the search phase substantially only the subset to perform detection of possible match regions between the target image and the image examples.

3. An improvement according to claim 2, further comprising using vectors during the search phase to also perform image recognition, wherein the only vectors used to perform image recognition are from the subset.

4. An improvement according to claim 1, wherein identifying component vectors includes obtaining a complete set of eigenvectors for the directory of image examples.

5. An improvement according to claim 4, wherein identifying component vectors includes selecting a subset of basis vectors that correlate negatively with the directory of images, relative to other, unselected basis vectors.

6. An improvement according to claim 4, wherein applying a function includes applying a function to eigenvectors that yields a set of basis vectors and a measure of relative smoothness of each basis vector elative to other basis vectors.

7. An improvement according to claim 4, wherein selecting a subset includes selecting less than fifteen vectors, said improvement further comprising during the search phase, applying the selected vectors to input images as part of an image matching process.

8. An improvement according to claim 4, wherein selecting a subset includes selecting less than fifteen vectors, said improvement further comprising during the search phase, applying the selected vectors to input images as part of an image recognition process.