Method and system for image recognition using a similarity inverse matrix

• US 7,921,120 B2
• Filed: 11/30/2007
• Issued: 04/05/2011
• Est. Priority Date: 11/30/2006
• Status: Expired due to Fees

• Current Assignee: D&S Consultants Incorporated
• Original Assignee: D&S Consultants Incorporated
• Inventors: Podilchuk, Christine
• Primary Examiner(s): Ali, Mohammad
• Assistant Examiner(s): Hocker, John P
• Application Number:
  US11/948,072
• Publication Number:
  US 20080133521A1
• Time in Patent Office: 1,222 Days
• Field of Search: 707 1- 10, 707/102, 707/749, 707/748
• US Class Current: 707/749
• CPC Class Codes: G06F 16/583 using metadata automatically derived from the content
• CPC Class Codes: G06V 30/2504 Coarse or fine approaches, e.g. resolution of ambiguities or multiscale approaches

Abstract

A method and system for recognizing images are described. Embodiments of the invention apply techniques of the Levenshtein algorithm for matching or searching one-dimensional strings for comparing graphical contents of 2D images.

Claims

1. A computer readable medium storing software that, when executed by a processor, causes an apparatus or system to perform a method for recognizing images, the images including a query image and a plurality of reference images, comprising:

(a) generating a matrix of similarity scores of the reference images, wherein the similarity score of each reference image versus itself forms a diagonal matrix element and similarity scores of the reference images one versus another form non-diagonal matrix elements;

(b) calculating a similarity inverse matrix by transforming the matrix of similarity scores into a matrix that, when multiplied by said similarity matrix will yield an identity matrix in which said diagonal matrix elements are equal to 1 and said non-diagonal matrix elements are equal to 0;

(c) generating a query vector having as each element a similarity score of the query image versus one of said reference images;

(d) calculating an adjusted query vector equal to the product of said query vector and said similarity inverse matrix; and

(e) using said adjusted query vector to compare the query and reference images;

wherein the query image is a two-dimensional image and each of the reference images is a pre-stored two-dimensional image.

2. The method of claim 1, wherein the query and reference images are presented in digital formats.

3. The method of claim 2, further comprising:

matching at least one of a digital resolution or a scale factor of the query image with a digital resolution and a scale factor of the reference images.

4. The method of claim 1, wherein the query image or at least some of the reference images are portions of larger image planes.

5. The method of claim 1, further comprising:

morphing at least a portion of the reference images.

6. The method of claim 5, wherein the morphing step comprises:

modifying at least one of lighting conditions, poses, or attributes of elements of graphical contents of the reference images.

7. The method of claim 5, wherein the step (a) further comprises:

generating the matrix of similarity scores that includes morphed reference images.

8. The method of claim 1 wherein said similarity scores are defined as a complement to a pictorial edit distance, which is asserted as a weighted sum of a 2D representation of Insertion, Deletion, and Substitution Error terms of a distance metric algorithm for matching or searching one-dimensional data strings.

19. The method of claim 8 wherein said distance metric algorithm is the Levenshtein algorithm.

21. The method of claim 8, wherein the pictorial edit distance is determined using a pre-determined block matching algorithm for comparing (i) matrices of blocks of pixels of the reference images or (ii) matrices of blocks of pixels of the query image and the reference images.

22. The method of claim 21, wherein a degree of correlation between the blocks of pixels is expressed using the terms of the Levenshtein algorithm as follows:

defining one-to-many correspondence between the blocks of pixels as an equivalent of an Insertion term;

defining one-to-none correspondence between the blocks of pixels as an equivalent of a Deletion term; and

defining a cost function associated with partial matching between the blocks of pixels as an equivalent of a Substitution Error term.

23. The method of claim 22, further comprising:

asserting the one-to-many correspondence between the blocks of pixels when a value of the cost function is smaller than a first pre-determined threshold;

asserting the one-to-none correspondence between the blocks of pixels when a value of the cost function is greater than a second pre-determined threshold; and

asserting partial correspondence between the blocks of pixels when a value of the cost function is disposed between the first and second pre-determined thresholds.

24. The method of claim 23, wherein the value of the cost function is based on a mean absolute difference or a mean square error between the blocks of pixels.

25. The method of claim 24, further comprising the steps of:

identifying a reference image having a highest similarity score with the query image; and

recognizing graphical contents of the query image and said reference image as identical when the highest similarity score is greater than a pre-selected threshold.

9. A system for recognizing images, comprising:

a processor;

a computer-readable medium;

a database of graphical data, said data including reference images;

a source of one or more query images; and

software, stored on said computer-readable medium for execution on said processor, said software performing the steps of;

(a) generating a matrix of similarity scores of the reference images, wherein the similarity score of each reference image versus itself forms a diagonal matrix element and similarity scores of the reference images one versus another form non-diagonal matrix elements;

(b) calculating a similarity inverse matrix by converting the matrix of similarity scores into a matrix that, when multiplied by said similarity matrix will yield an identity matrix in which said diagonal matrix elements are equal to 1 and said non-diagonal matrix elements are equal to 0;

(c) generating a query vector having as each element a similarity score of the query image versus one of said reference images;

(d) calculating an adjusted query vector equal to a product of the query vector and the similarity inverse matrix; and

(e) using the adjusted query vector to compare the query and reference images;

wherein the query image is a two-dimensional image and each of the reference images is a pre-stored two-dimensional image.

10. The system of claim 9, wherein said database is stored on said computer-readable medium.

11. The system of claim 9, wherein said database is a portion of a remote apparatus.

12. The system of claim 9, wherein the source of the one or more query images is a portion of the database.

13. The system of claim 9, wherein the source of the one or more query images is a remote device.

14. The system of claim 13, wherein said device is a digital video-recording device, an image-digitizing device, or a remote data storage.

15. The system of claim 9, wherein the query image or at least some of the reference images are portions of larger image planes.

16. The system of claim 9, wherein said software further performs the steps of:

identifying a reference image having a highest similarity score with the query image; and

recognizing graphical contents of the query image and said reference image as identical when the highest similarity score is greater than a pre-selected threshold.

17. The system of claim 9, wherein said software further performs the steps of:

morphing at least a portion of the reference images; and

generating the matrix of similarity scores that includes morphed reference images.

18. The system of claim 9 wherein said similarity scores are defined as a complement to a pictorial edit distance, which is asserted as a weighted sum of a 2D representation of Insertion, Deletion, and Substitution Error terms of a distance metric algorithm for matching or searching one-dimensional data strings.

20. The system of claim 18 wherein said distance metric algorithm is the Levenshtein algorithm.