Method and System for Image Recognition Using a Similarity Inverse Matrix

• US 20080133521A1
• Filed: 11/30/2007
• Published: 06/05/2008
• Est. Priority Date: 11/30/2006
• Status: Active Grant

• Current Assignee: D&S Consultants Incorporated
• Original Assignee: D&S Consultants Incorporated
• Inventors: Podilchuk, Christine
• Granted Patent: US 7,921,120 B2
• Time in Patent Office: Days
• US Class Current: 707/6
• 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 method for recognizing images, said images including a query image and a plurality of reference images, comprising:

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

(b) calculating a similarity inverse matrix transforming the matrix of similarity scores in an identity matrix, which diagonal matrix elements are equal to 1 and non-diagonal matrix elements are equal to 0;

(c) generating a query vector having elements each selectively equal to a similarity score between the query image and a reference image of the plurality of 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 similarity score is 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 the Levenshtein algorithm for matching or searching one-dimensional data strings.

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, 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.

6. The method of claim 5, 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.

7. The method of claim 6, 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.

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

9. The method of claim 1, wherein the step (e) further comprises:

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.

10. The method of claim 1, further comprising:

morphing at least a portion of the reference images.

11. The method of claim 10, wherein the morphing step comprises:

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

12. The method of claim 10, wherein the step (a) further comprises:

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

13. An apparatus or system executing the method of claim 1.

14. A computer readable medium storing software that, when executed by a processor, causes an apparatus or system to perform the method of claim 1.

15. A system for recognizing images, comprising:

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

a source of one or more query images; and

an analyzer of the database and query images, the analyzer adapted to execute software having instructions causing the analyzer to perform the steps of;

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

(b) calculating a similarity inverse matrix converting the matrix of similarity scores in an identity matrix which diagonal matrix elements are equal to 1 and non-diagonal matrix elements are equal to 0;

(c) generating a query vector having elements each selectively equal to a similarity score between the query image and a reference image of the plurality of 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 similarity score is 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 the Levenshtein algorithm for matching or searching one-dimensional data strings.

16. The system of claim 15, wherein the analyzer is a computer or a portion thereof.

17. The system of claim 15, wherein the database is a portion of the analyzer.

18. The system of claim 15, wherein the database is a portion of a remote apparatus coupled to the analyzer.

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

20. The system of claim 15, wherein the source of the one or more query images is a remote device adapted for communicating with the analyzer.

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

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

23. The system of claim 15, further adapted to at least one 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.

24. The system of claim 15, further adapted to:

morphing at least a portion of the reference images; and

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