Integrated solution to digital image similarity searching

• US 7,379,627 B2
• Filed: 10/20/2003
• Issued: 05/27/2008
• Est. Priority Date: 10/20/2003
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Sun, Yanfeng, Li, Mingjing, Zhang, Lei, Zhang, Hong-Jiang, Parlin, David R.
• Primary Examiner(s): Carter; Aaron W
• Application Number:
  US10/689,106
• Publication Number:
  US 20050084154A1
• Time in Patent Office: 1,681 Days
• Field of Search: 382/190, 382218-222, 382/305, 707/104.1
• US Class Current: 382/305
• CPC Class Codes: G06V 10/56 relating to colour
• CPC Class Codes: G06V 20/10 Terrestrial scenes scenes under surveillance with static cameras G06V20/52; scenes perceived from the exterior of a vehicle G06V20/56; scenes perceived from the interior of a vehicle G06V20/59
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing
• CPC Class Codes: Y10S 707/99948 Application of database or data structure, e.g. distributed, multimedia, or image

Abstract

A process for comparing two digital images is described. The process includes comparing texture moment data for the two images to provide a similarity index, combining the similarity index with other data to provide a similarity value and determining that the two images match when the similarity value exceeds a first threshold value.

Claims

1. A process implemented by a computing device for comparing two digital images, the process comprising:

comparing texture moment data for the two images to provide a first similarity index;

comparing color correlogram data for the two images to provide a second similarity index;

comparing color moment data for the two images to provide a third similarity index;

combining the first, second and third similarity indices to provide a similarity value;

determining that the two images match when the similarity value exceeds a first threshold value; and

responsive to determining that the two images match, providing an indication that the two images match.

2. The process of claim 1, wherein combining comprises forming a weighted sum from the first, second and third similarity indices.

3. The process of claim 1, further comprising determining that the two images do not match when the similarity value is less than a second threshold value.

4. The process of claim 1, wherein the two images comprise a first and a second image, the first of the two images comprises a query image, and further comprising locating one or more matches to a plurality of images in a database of images by iterating the acts of comparing color correlogram data, comparing color moment data, comparing texture moment data, combining and determining using as the second image a successive one image of the plurality of images.

5. The process of claim 1, further comprising:

comparing one or more high-level features from each of the two images; and

adjusting the similarity value in accordance with comparing one or more high-level features, prior to determining.

6. The process of claim 1, further comprising:

extracting one or more high-level features from each of the two images, wherein the one or more high-level features include a high-level feature chosen from a group consisting of;

presence/absence of one or more human faces, indoor/outdoor scene and time/date of image formation;

comparing one or more of the high-level features from each of the two images; and

adjusting the similarity value in accordance with comparing one or more high-level features, prior to determining.

7. The process of claim 1, further comprising, after combining and before determining, adjusting the similarity value based on a calculation of commonality or lack of commonality between one or more high-level features associated with each of the two images and a confidence value thereof.

8. The process of claim 1, wherein at least one of the two images is a digital image taken using a digital camera.

9. The process of claim 1, wherein combining comprises:

weighting the first, second and third similarity indices by assigning the first similarity index a greatest weight and assigning the third similarity index a least weight; and

adding the weighted first, second and third similarity indices to provide an adjusted similarity value, wherein determining employs the adjusted similarity value in determining that the two images match.

10. The process of claim 1, further comprising quantizing the similarity value prior to determining, wherein quantizing comprises quantizing according to a tiered ranking scheme employing fewer than ten levels ranging from a lowest to a highest tier, with greater similarity values corresponding to higher tiers, wherein the first threshold value corresponds to a highest tier into which similarity values are quantized.

11. A process implemented by a computing device for manipulating image characterization data from a digital image, the process comprising:

indexing the digital image by extracting low-level feature data corresponding to a plurality of low-level features from the digital image, the plurality comprising two or more low-level features chosen from a group comprising texture moment data, color correlogram data, and color moment data;

organizing the data into a feature vector by;

(a) forming a query vector;

(b) if extracted low-level feature data corresponds to;

(i) texture moment data;

comparing texture moment data for the query and feature vectors to provide a first similarity index;

(ii) color correlogram data;

comparing color correlogram data for the query and feature vectors to provide a second similarity index; and

(iii) color moment data;

comparing color moment data for the query and feature vectors to provide a third similarity index; and

(c) combining available ones of the first, second and third similarity indices to provide the feature vector;

utilizing the feature vector to identify a set of similar digital images; and

providing a result that identifies the set of similar images.

12. The process of claim 11, wherein indexing comprises:

first extracting texture moment data from the digital image;

second extracting color correlogram data from the digital image; and

third extracting color moment data from the digital image.

13. The process of claim 11, further comprising storing the feature vector in a database.

14. The process of claim 11, wherein organizing the data comprises forming a query vector, and further comprising:

obtaining a feature vector from a group of feature vectors corresponding to a plurality of digital images;

comparing the query vector to the feature vector to provide a similarity value;

determining when the similarity value exceeds a first threshold; and

iterating obtaining, comparing and determining for each feature vector of the group.

15. A computer-readable storage medium having embedded there on computer-program instructions for comparing two digital images, the computer-program instructions, when executed by a processor, for performing operations comprising:

comparing texture moment data for the two images to provide a similarity index, the similarity index being a first similarity index;

comparing color correlogram data for the two images to provide a second similarity index;

comparing color moment data for the two images to provide a third similarity index;

combining the first similarity index with other data to provide a similarity value, the other data comprising the second and the third similarity indices;

determining a degree to which the two images match when the similarity value exceeds a first threshold value; and

responsive to determining the degree to which the two images match, providing a result that indicates whether the two images match.

16. The computer-readable storage medium of claim 15, wherein combining comprises forming a weighted sum from the similarity index and other data.

17. The computer-readable storage medium of claim 15, further comprising determining that the two images do not match when the similarity value is less than a second threshold value.

18. The computer-readable storage medium of claim 15, wherein the two images comprise a first and a second image, the first of the two images comprises a query image, and further comprising locating one or more matches to a plurality of images in a database of images by iterating the acts of comparing, combining and determining using as the second image a successive one image taken from the plurality of images.

19. The computer-readable storage medium of claim 15, further comprising:

comparing one or more high-level features from each of the two images; and

adjusting the similarity value in accordance with comparing one or more high-level features, prior to determining.

20. The computer-readable storage medium of claim 15, further comprising:

extracting one or more high-level features from each of the two images, wherein the one or more high-level features include a high-level feature chosen from a group consisting of;

presence/absence of one or more human faces, indoor/outdoor scene and time/date of image formation;

comparing one or more high-level features from each of the two images; and

adjusting the similarity value in accordance with comparing one or more high-level features, prior to determining.

21. The computer-readable storage medium of claim 15, further comprising, after combining and before determining, adjusting the similarity value based on a calculation of commonality or lack of commonality between one or more high-level features associated with each of the two images and a confidence value thereof.

22. The computer-readable storage medium of claim 15, wherein at least one of the two images is a digital image taken using a digital camera.

23. The computer-readable storage medium of claim 15, wherein combining the first similarity index with the other data further comprises:

weighting the first, second and third similarity indices by assigning the first similarity index a greatest weight and assigning the third similarity index a least weight; and

adding the weighted first, second and third similarity indices to provide an adjusted similarity value, wherein determining employs the adjusted similarity value in determining that the two images match when the similarity value exceeds the first threshold value.

24. The computer-readable storage medium of claim 15, further comprising quantizing the similarity value according to a tiered ranking scheme employing fewer than ten levels ranging from a lowest to a highest tier, with greater similarity values corresponding to higher tiers, wherein the first threshold value corresponds to a highest tier into which similarity values are quantized.

25. A camera comprising:

an image capture device configured to capture digital images;

a memory coupled to the image capture device and configured to store a database of image data, including the digital images and associated feature vectors each comprising texture moment data, correlogram data and color moment data; and

an image similarity module coupled to the memory and configured to;

generate a query vector comprising texture moment data, correlogram data and color moment data;

compare, in succession, the query vector to each feature vector in the database, to generate a similarity value;

classify each feature vector to assign each feature vector to a tier in a tiered similarity structure based on the associated similarity value;

group images associated with the respective feature vectors in each tier of the similarity structure to generate group(s) of similar images; and

provide the group(s) of similar images for sorting.

26. The camera of claim 25, wherein the image similarity module is further configured to:

adjust each similarity value in conformance with comparison of high-level data corresponding to the query vector and high-level data corresponding to each feature vector to provide an adjusted similarity value corresponding to each feature vector; and

use the adjusted similarity value to classify each feature vector in the tiered similarity structure.

27. The camera of claim 25, wherein the image similarity module is further configured to adjust each similarity value in conformance with comparison of high-level data corresponding to the query vector and high-level data corresponding to each feature vector to provide an adjusted similarity value corresponding to each feature vector, wherein high-level

data comprises:

presence/absence of one or more human faces;

indoor/outdoor scene; and

time of image formation.

28. The camera of claim 25, wherein the image similarity module is further configured to:

adjust each similarity value in conformance with comparison of high-level data corresponding to the query vector and high-level data corresponding to each feature vector to provide an adjusted similarity value corresponding to each feature vector, wherein high-level data comprises;

presence/absence of one or more human faces, indoor/outdoor scene and time/date of image formation; and

use the adjusted similarity value to classify each feature vector in the tiered similarity structure.

29. The camera of claim 25, further comprising a monitor configured to facilitate viewing of digital images stored in the database, wherein the digital images are accessed via associated feature vectors selected within a tier of the tiered similarity structure.

30. A computer readable storage medium having embedded thereon a plurality of computer-program instructions, the computer-program instructions, when executed by one or more processors, for performing operations comprising:

successively comparing a query vector to each feature vector in a database, the query vector and the feature vectors each including texture moment data, correlogram data and color moment data;

successively compare texture moment data from the query vector to texture moment data from each feature vector to provide a first similarity index;

successively compare correlogram data from the query vector to correlogram data from each feature vector to provide a second similarity index;

successively compare color moment data from the query vector to color moment data from each feature vector to provide a third similarity index; and

form a similarity value as a weighted sum of the first, second and third similarity indices for each feature vector, wherein the plurality of instructions that cause the one or more processors to rank comprise instructions that cause the one or more processors to quantize similarity values into ranked tiers based in part on high-level features associated with the query vector and the feature vectors, each tier corresponding to a different degree of similarity between the query vector and the feature vectors associated with that tier;

ranking each feature vector into a tier of a tiered classification scheme based on the comparison between the feature vector and the query vector; and

utilizing the tiered classification scheme to provide an indication whether first and second digital images have matching similarities.

31. A system for image correlation comprising:

one or more processors;

a memory coupled to the one or more processors, the memory comprising computer-program instructions executable by the one or more processors to store a database representing digital images, the computer-program instructions comprising;

an image comparison module configured to

(a) cause the one or more processors to access the data representing the images and to select one or more feature vectors each associated with a corresponding image based on comparison of color texture data and other data contained in each feature vector with analogous data contained in a query feature vector; and

(b) compare correlogram data and color moment data contained in each feature vector with analogous data contained in the query feature vector; and

(c) select the one or more feature vectors based on a weighted sum of similarity indices respectively derived from comparing the color texture moments, the correlogram data and the color moment data; and

a display device coupled to the one or more processors and to the memory and configured to display digital images corresponding to the selected one or more feature vectors in response to user input, the digital images having been determined to share a set of similarity characteristics.

32. The system of claim 31, wherein the other data include high-level feature data.

33. The system of claim 31, wherein the image comparison module further is configured to cause the one or more processors to:

extract one or more high-level features contained in each feature vector and analogous data contained in the query feature vector, wherein the one or more high-level features include a high-level feature chosen from a group consisting of;

presence/absence of one or more human faces;

indoor/outdoor scene; and

time of image formation;

compare one or more of the high-level features from each feature vector and analogous data contained in the query feature vector; and

employ results from comparing the one or more high-level features in selecting the one or more feature vectors.