US6181817B1
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and system for comparing data objects using joint histograms
Assignee: Cornell Research Foundation Inc
•
Filing: 1998-11-16
•
Granted: 2001-01-30
•
Expires: 2018-11-16
Abstract
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.
Inventors
- 👤 Ramin D. Zabih
- 👤 Gregory S. Pass
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-04 08:51
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/50; G06F16/58; G06F16/583; G06F16/5854; G06T; G06T7/00; G06T7/40; G06T7/41; G06F16/5838; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99933; Y10S707/99936; Y10S707/99941; Y10S707/99944; Y10S707/99945
Claims Analysis
Total Claims: 32
Claim 1
Independent Claim
108 words
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.
Claim 2
Dependent Claim
108 words
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.
Claim 3
Dependent Claim
22 words
The method of claim 1 wherein said selecting step further comprises selecting features according to requirements of a selected data comparison process.
Claim 4
Dependent Claim
30 words
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.
Claim 5
Dependent Claim
27 words
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.
Claim 6
Dependent Claim
17 words
The method of claim 1 further comprising the step of: storing the joint histogram in a database.
Claim 7
Dependent Claim
13 words
The method of claim 5 further comprising the step of: indexing the database.
Claim 8
Dependent Claim
42 words
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.
Claim 9
Dependent Claim
24 words
The method of claim 7 further comprising tracking results of the comparing step to produce a plurality of joint histograms matching the query vector.
Claim 10
Dependent Claim
19 words
The method of claim 7 wherein the comparing step uses a reduced intersection of histogram entries for vector comparison.
Claim 11
Dependent Claim
102 words
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.
Claim 12
Dependent Claim
102 words
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.
Claim 13
Dependent Claim
25 words
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.
Claim 14
Dependent Claim
30 words
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.
Claim 15
Dependent Claim
28 words
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.
Claim 16
Dependent Claim
18 words
The method of claim 10 further comprising the step of: storing the joint histogram in an indexed database.
Claim 17
Dependent Claim
40 words
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.
Claim 18
Dependent Claim
27 words
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.
Claim 19
Dependent Claim
19 words
The method of claim 15 wherein the comparing step uses a reduced intersection of histogram entries for vector comparison.
Claim 20
Dependent Claim
98 words
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.
Claim 21
Dependent Claim
98 words
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.
Claim 22
Dependent Claim
25 words
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.
Claim 23
Dependent Claim
30 words
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.
Claim 24
Dependent Claim
29 words
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.
Claim 25
Dependent Claim
13 words
The method of claim 18 further comprising the step of: indexing the database.
Claim 26
Dependent Claim
42 words
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.
Claim 27
Dependent Claim
27 words
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.
Claim 28
Dependent Claim
19 words
The method of claim 23 wherein the comparing step uses a reduced intersection of histogram entries for vector comparison.
Claim 29
Independent Claim
97 words
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.
Claim 30
Independent Claim
97 words
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.
Claim 31
Dependent Claim
13 words
The system of claim 26 further comprising: a means for indexing the database.
Claim 32
Dependent Claim
42 words
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.
References Cited (Backward Citations)
US5579471A
Cited
US5521841A
Cited
US5606655A
Cited
US5546475A
Cited
US5594807A
Cited
US5893095A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2004-01-30 | 2004-07-31 | 2005-01-30 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2008-01-30 | 2008-07-31 | 2009-01-30 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2012-01-30 | 2012-07-31 | 2013-01-30 | $7700.00 | Window Closed / Lapsed |