System and method for determining image similarity

• US 6,826,316 B2
• Filed: 03/02/2001
• Issued: 11/30/2004
• Est. Priority Date: 01/24/2001
• Status: Expired due to Term

• Current Assignee: Monument Peak Ventures, LLC (Dominion Harbor Enterprises, LLC)
• Original Assignee: Eastman Kodak Company
• Inventors: Zhu, Wei, Luo, Jiebo, Mehrotra, Rajiv, Gray, Robert T., Sotak, George E.
• Primary Examiner(s): Miriam, Daniel
• Application Number:
  US09/798,604
• Publication Number:
  US 20020131641A1
• Time in Patent Office: 1,369 Days
• Field of Search: 382/173, 382/176, 382/203, 382/209, 382/190, 382/218, 382/220, 382/224, 382/228, 382/305, 358/403, 707/1-10
• US Class Current: 382/305
• CPC Class Codes: G06F 18/21 Design or setup of recognition systems or techniques; Extraction of features in feature space; Blind source separation
• CPC Class Codes: G06V 10/42 Global feature extraction by analysis of the whole pattern, e.g. using frequency domain transformations or autocorrelation
• CPC Class Codes: G06V 10/70 using pattern recognition or machine learning optical pattern recognition or electronic computations therefor G06V10/88
• CPC Class Codes: Y10S 707/99936 Pattern matching access

Abstract

A system and method for determining image similarity. The method includes the steps of automatically providing perceptually significant features of main subject or background of a first image; automatically providing perceptually significant features of main subject or background of a second image; automatically comparing the perceptually significant features of the main subject or the background of the first image to the main subject or the background of the second image; and providing an output in response thereto. In the illustrative implementation, the features are provided by a number of belief levels, where the number of belief levels are preferably greater than two. The perceptually significant features include color, texture and/or shape. In the preferred embodiment, the main subject is indicated by a continuously valued belief map. The belief values of the main subject are determined by segmenting the image into regions of homogenous color and texture, computing at least one structure feature and at least one semantic feature for each region, and computing a belief value for all the pixels in the region using a Bayes net to combine the features. In an illustrative application, the inventive method is implemented in an image retrieval system. In this implementation, the inventive method automatically stores perceptually significant features of the main subject or background of a plurality of first images in a database to facilitate retrieval of a target image in response to an input or query image. Features corresponding to each of the plurality of stored images are automatically sequentially compared to similar features of the query image. Consequently, the present invention provides an automatic system and method for controlling the feature extraction, representation, and feature-based similarity retrieval strategies of a content-based image archival and retrieval system based on an analysis of main subject and background derived from a continuously valued main subject belief map.

Claims

1. A method for determining image similarity, comprising the steps of:

providing a first image having an associated set of perceptually significant features, said features each corresponding to individual ones of a set of belief levels, said belief levels being step-valued as to likelihood of main subject;

automatically generating a belief level image from a second image, at each of said step-valued belief levels, to provide a plurality of belief level images;

automatically extracting one or more perceptually significant features from each of said belief level images to provide extracted features; and

comparing, at each of the corresponding said belief levels, said extracted features to corresponding said features of said sets of perceptually significant features.

2. The method of claim 1 wherein said generating further comprises the steps of:

creating a continuously valued belief map of said second image, wherein said map has belief values that vary with likelihood of main subject;

deriving a multiple valued belief map from said continuously valued belief map, said multiple valued belief map having belief levels corresponding to said set of step-valued belief levels;

masking said second image with said multiple valued belief map to provide said belief level images.

3. The method of claim 2 wherein said creating further comprises:

segmenting the second image into a plurality of regions of homogenous color and texture;

computing at least one structure feature and/or one semantic feature for each of said regions; and

computing a belief value for all the pixels in each of said regions using a Bayes net to combine the features.

4. A method for determining image similarity, comprising the steps of:

providing a plurality of database images, each of said database images having an associated set of perceptually significant features, said features each corresponding to individual ones of a set of belief levels, said belief levels being step-valued as to likelihood of main subject;

automatically generating a belief level image from a query image, at each of said step-valued belief levels, to provide a plurality of belief level images;

automatically extracting one or more perceptually significant features from each of said belief level images to provide extracted features; and

comparing, at each of the corresponding said belief levels, said extracted features to corresponding said features of said sets of perceptually significant features.

5. The method of claim 4 wherein said generating further comprises the steps of:

creating a continuously valued belief map of said query image, wherein said map has belief values that vary with likelihood of main subject;

deriving a multiple valued belief map from said continuously valued belief map, said multiple valued belief map having belief levels corresponding to said set of step-valued belief levels;

masking said query image with said multiple valued belief map to provide said belief level images.

6. The method of claim 5 wherein said creating further comprises:

segmenting the query image into a plurality of regions of homogenous color and texture;

computing at least one structure feature and/or one semantic feature for each of said regions; and

computing a belief value for all the pixels in each of said regions using a Bayes net to combine the features.

7. The method of claim 4 further comprising the step of retrieving one of said database images based upon similarity of said extracted features to features of the set of perceptually significant features associated with said one of said database images.

8. The method of claim 4 further comprising, during said comparing, emphasizing some of said belief level images relative to others of said belief level images.

9. The method of claim 8 wherein said belief level images having a highest likelihood of main subject are emphasized and said belief level images having lowest likelihood of main subject are deemphasized.

10. The method of claim 9 further comprising providing different options of relative emphasis of said belief level images during said comparing.

11. The method of claim 10 wherein said options include:

(a) positive emphasis on said belief level images, with most emphasis on belief level images having a highest likelihood of main subject and least emphasis on belief level images having a lowest likelihood of main subject;

(b) only emphasis on belief level images having a highest likelihood of main subject;

(c) only emphasis on belief level images having a lowest likelihood of main subject; and

(d) differential emphasis on belief level images, with some of said belief level images positively emphasized and others of said belief level images negatively emphasized.

12. The method of claim 4 wherein said perceptually significant features of said database images are weighted sums and said extracting further comprises calculating weighted sums from each of said belief level images.

13. The method of claim 4 wherein said comparing further comprises calculating:

$S<br><br>\left(Q,D\right)=\underset{j=0}{\overset{N}{\sum <br><br>}}<br><br>\text{\hspace{1em}<br><br>}<br><br>\underset{i=0}{\overset{N}{\sum <br><br>}}<br><br>\text{\hspace{1em}<br><br>}<br><br>w_{\mathrm{ij}}<br><br>s_{\mathrm{ij}}$

where S(Q,D) is the similarity of features of said belief level images of said query image, Q, and one of said database images D, at corresponding said belief levels;

N is the number of belief levels,s_ij is the similarity between the ith belief level image of the query image and the jth belief level of the database image, and w_ij is a predetermined weight.

14. The method of claim 13 wherein $w_{\mathrm{ij}}=\left[\begin{array}{ccc}0.5& 0.2& 0\\ 0.2& 0.3& 0.1\\ 0& 0.1& 0.2\end{array}\right].$

15. The method of claim 4 wherein said perceptually significant features include at least one of color, texture, and shape.

16. The method of claim 4 wherein said sets of perceptually significant features are stored in a database, organized by index structures and said comparing further comprises searching said index structures.

17. The method of claim 4 wherein the retrieved image has a similar main subject.

18. The method of claim 4 wherein the retrieved image has a similar background.

19. The method of claim 4 wherein the retrieved image has a similar main subject, but different background.

20. The method of claim 4 wherein the retrieved image has a different main subject, but similar background.

21. The method of claim 4 wherein the retrieved image has a similar main subject, and similar background.

22. A method for determining image similarity, comprising the steps of:

providing a plurality of input images, each of said input images having an associated set of perceptually significant features, said features each corresponding to individual ones of a set of belief levels, said belief levels being step-valued as to likelihood of main subject;

automatically creating a continuously valued belief map of a query image, wherein said map has belief values that vary with likelihood of main subject;

deriving a multiple valued belief map from said continuously valued belief map, said multiple valued belief map having belief levels corresponding to said set of step-valued belief levels;

masking said query image with said multiple valued belief map to provide a belief level image at each of said step-valued belief levels;

automatically extracting one or more perceptually significant features from each said belief level image to provide extracted features; and

comparing, at each of the corresponding said belief levels, said extracted features to corresponding said features of said sets of perceptually significant features.

23. The method of claim 22 wherein said creating further comprises:

segmenting the image into a plurality of regions of homogenous color and texture;

computing at least one structure feature and/or one semantic feature for each of said regions; and

computing a belief value for all the pixels in each of said regions using a Bayes net to combine the features.

24. The method of claim 23 further comprising the step of retrieving one of said input images based upon similarity of said extracted features to features of the set of perceptually significant features associated with said one of said input images.

25. The method of claim 24 wherein said perceptually significant features include at least one of color, texture, and shape.

26. The method of claim 25 wherein said sets of perceptually significant features are stored in a database, organized by index structures and said comparing further comprises searching said index structures.

27. The method of claim 26 wherein said perceptually significant features of said input images are weighted sums and said extracting further comprises calculating weighted sums from each of said belief level images.