Method and system for comparing data objects using joint histograms

• US 6,181,817 B1
• Filed: 11/16/1998
• Issued: 01/30/2001
• Est. Priority Date: 11/17/1997
• Status: Expired due to Term

• Current Assignee: Cornell Research Foundation Incorporated (Cornell University)
• Original Assignee: Cornell Research Foundation Incorporated (Cornell University)
• Inventors: Pass, Gregory S., Zabih, Ramin D.
• Primary Examiner(s): Au, Amelia
• Assistant Examiner(s): Wu, Jingge
• Application Number:
  US09/192,991
• Time in Patent Office: 806 Days
• Field of Search: 382/305, 382/168, 382/170, 382/165, 382/162, 358/522, 707/3, 707/6, 707/101, 707/104
• US Class Current: 382/170
• CPC Class Codes: G06F 16/5838 using colour
• CPC Class Codes: G06F 16/5854 using shape and object relationship
• CPC Class Codes: G06T 7/41 based on statistical description of texture
• CPC Class Codes: Y10S 707/99936 Pattern matching access
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing

Abstract

A joint histogram is used for content-based data object comparison. For a data object which can be described by a plurality of features and values, a set of features describing the data object is selected. A joint histogram is a k-dimensional vector, such that each entry in the joint histogram contains the number of data points in the data object that are described by a k-tuple of feature values. The data object is analyzed according to the set of features and the results entered into the joint histogram. The joint histogram distinguishes the data object from other data objects. Joint histogram comparisons may be used to identify the similarity between two or more particular data objects.

Claims

1. A computer-implemented method for comparing data objects where those data objects may be described by features, comprising the steps of:

selecting a set of features describing a data object, each feature having a range of values;

creating a joint histogram template based on the set of features, the joint histogram template having entries for combinations of features and values;

analyzing the data object according to the set of features to obtain joint histogram values; and

,

entering the joint histogram values into the joint histogram template to create a joint histogram describing the data object,

whereby the data object is identifiable by the joint histogram from other data objects.

2. The method of claim 1 wherein said selecting step further comprises selecting features according to requirements of a selected data comparison process.

3. The method of claim 1 further comprising the step of:

discretizing the range of feature values to reduce the number of value entries to be made in the joint histogram.

4. The method of claim 3 wherein each range is discretized such that each discrete value occurs with approximately equal likelihood over a representative set of data objects.

5. The method of claim 1 further comprising the step of:

storing the joint histogram in a database.

6. The method of claim 5 further comprising the step of:

indexing the database.

7. The method of claim 1 further comprising the steps of:

determining a query vector of a query object;

comparing the query vector with the joint histogram of the data object to determine a similarity between the data object and the query object.

8. The method of claim 7 further comprising tracking results of the comparing step to produce a plurality of joint histograms matching the query vector.

9. The method of claim 7 wherein the comparing step uses a reduced intersection of histogram entries for vector comparison.

10. A computer-implemented method for comparing images where those images may be described by features, comprising the steps of:

selecting a set of features describing an image, each feature having a range of values;

creating a joint histogram template based on the set of features, the joint histogram template having entries for combinations of features and value;

analyzing the image according to the set of features to obtain joint histogram values; and

,

entering the obtained joint histogram values into the joint histogram template to create a joint histogram describing the image,

whereby the image is identifiable by the joint histogram from other images.

11. The method of claim 10 wherein the selecting step further comprises selecting features which remain constant when transformations are applied to objects in the image.

12. The method of claim 10 further comprising the step of:

discretizing the range of feature values to reduce the number of value entries to be made in the joint histogram.

13. The method of claim 12 wherein each range of values is discretized such that each discrete value occurs with approximately equal likelihood over a representative set of images.

14. The method of claim 10 further comprising the step of:

storing the joint histogram in an indexed database.

15. The method of claim 10 further comprising the steps of:

determining a query vector of a query image;

comparing the query vector with the joint histogram of the image to determine the similarity between the image and the query image.

16. The method of claim 15 further comprising the step of:

tracking results of the comparing step to produce a plurality of joint histograms matching the query vector.

17. The method of claim 15 wherein the comparing step uses a reduced intersection of histogram entries for vector comparison.

18. A computer-implemented method of image retrieval from a database, comprising the steps of:

selecting a set of features describing an image;

creating a joint histogram template based on the set of features, the joint histogram template having entries for combinations of features and values;

analyzing the image according to the set of features to obtain histogram values;

entering the obtained histogram values into the joint histogram template to create a joint histogram describing the image; and

storing the joint histogram in the database,

whereby the image is identifiable by the joint histogram from other images in the database.

19. The method of claim 18 wherein the selecting step further comprises selecting features which remain constant when transformations are applied to objects in the image.

20. The method of claim 18 further comprising the step of:

discretizing the range of feature values to reduce the number of value entries to be made in the joint histogram.

21. The method of claim 20 wherein each range of values is discretized such that each discrete value occurs with approximately equal likelihood over a representative set of data objects.

22. The method of claim 18 further comprising the step of:

indexing the database.

23. The method of claim 18 further comprising the steps of:

determining a query vector based on an image to be retrieved from the database;

comparing the query vector with histograms stored in the database to find a histogram matching the query vector.

24. The method of claim 23 further comprising the step of:

tracking results of the comparing step to produce a plurality of joint histograms matching the query vector.

25. The method of claim 23 wherein the comparing step uses a reduced intersection of histogram entries for vector comparison.

26. A system for data object retrieval from a database, comprising:

means for selecting a set of features describing a data object;

means for creating a joint histogram template based on the set of features, the joint histogram template having entries for combinations of features and values;

an object analyzer for analyzing the data object according to the selected set of features, the object analyzer producing histogram values, the object analyzer creating a joint histogram describing the data object by entering the values into the joint histogram template; and

,

means for storing the joint histogram in the database.

27. The system of claim 26 further comprising:

a means for indexing the database.

28. The system of claim 26 further comprising:

means for determining a query vector to retrieve the data object from the database; and

means for comparing the query vector with histograms stored in the database to find the histogram matching the query vector.