US6718063B1
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for computing the similarity between images
Assignee: Canon Inc
•
Filing: 1999-12-10
•
Granted: 2004-04-06
•
Expires: 2019-12-10
Abstract
Abstract The method first segments both images into homogeneous regions ( 205 A) and assigns ( 207 A) semantic labels (such as “sky”, “cloud”, “water”, “foliage” etc) to the homogeneous regions to describe the content of the regions using a probabilistic method. This process also results in each assigned label for a region having an associated probability value expressing the confidence level of the label being correctly assigned The method then computes ( 108 ) a distance metric which averages over all corresponding pixels in the two images a value which is the product of a predetermined semantic difference between the assigned labels at the corresponding pixels and a weighting function which is derived from the associated probability values of the labels for each of the corresponding pixels. The semantic difference reflects similarities between the labels. For example, the semantic difference of the label pair “sky” and “foliage” is higher than the semantic difference between the more similar “sky” and “cloud” label pair. The method then compares ( 110 ) the distance metric value with a predetermined threshold value in order to determine the similarity of the images.
Inventors
- 👤 Alison Joan Lennon
- 👤 Jing Wu
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-09 16:20
CPC Classifications
G; G06; G06V; G06V20/00; G06V20/35; G06V20/38; G06V10/00; G06V10/40; G06V10/42; G06V10/422; G06V10/426; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99933; Y10S707/99936
Claims Analysis
Total Claims: 43
Claim 1
Independent Claim
86 words
A method of computing the similarity between two images, wherein said images each comprise a plurality of pixels and said method comprises the steps of: segmenting each of the images into homogeneous regions; assigning to at least one of the generated regions a semantic label which describes the content of the region; and computing a distance metric from predetermined semantic differences between the assigned semantic labels at corresponding pixels in the two images, wherein said distance metric is representative of the similarity of the two images.
Claim 2
Independent Claim
86 words
A method of computing the similarity between two images, wherein said images each comprise a plurality of pixels and said method comprises the steps of: segmenting each of the images into homogeneous regions; assigning to at least one of the generated regions a semantic label which describes the content of the region; and computing a distance metric from predetermined semantic differences between the assigned semantic labels at corresponding pixels in the two images, wherein said distance metric is representative of the similarity of the two images.
Claim 3
Dependent Claim
50 words
A method as claimed in claim 1 , wherein said method further comprises, prior to said segmenting step, the step of: determining whether both images have the same dimensions in pixels and if not converting one of the said images to have the same pixel dimensions as the other image.
Claim 4
Dependent Claim
19 words
A method as claimed in claim 2 , wherein said determining and converting step occurs after said assigning step.
Claim 5
Dependent Claim
19 words
A method as claimed in claim 2 , wherein said determining and converting steps occurs during said computing step.
Claim 6
Dependent Claim
35 words
A method as claimed in claim 1 , wherein the predetermined semantic difference between two labels for a corresponding pixel is 1 if the labels are different and 0 if the labels are the same.
Claim 7
Dependent Claim
36 words
A method as claimed in claim 1 , wherein the predetermined semantic difference between two labels is a value between 0 and 1, wherein a greater value is indicative of labels that are semantically substantially different.
Claim 8
Dependent Claim
46 words
A method as claimed in claim 1 , wherein said assigning step comprises assigning the semantic labels to the homogeneous regions using a probabilistic method which results in each assigned label for a region having an associated probability or likelihood of the label being correctly assigned.
Claim 9
Dependent Claim
24 words
A method as claimed in claim 7 , wherein the homogeneous regions generated in said segmenting step are represented by a region adjacency graph.
Claim 10
Dependent Claim
33 words
A method as claimed in claim 8 , wherein the probabilistic method used to assign the labels to particular regions is based on a Markov Random Field modeled on the region adjacency graph.
Claim 11
Dependent Claim
38 words
A method as claimed in claim 7 , wherein the associated probabilities of labels being correctly assigned are represented as energies, wherein a small energy value is indicative that a label has been assigned with a high probability.
Claim 12
Dependent Claim
41 words
A method as claimed in claim 1 , wherein said method further comprises the steps of: comparing the distance metric with a predetermined threshold, and if the distance metric is below said predetermined threshold, outputting data indicating said images are similar.
Claim 13
Dependent Claim
36 words
A method as claimed in claim 11 , wherein if the distance metric is equal to or above said predetermined threshold said method further comprises the step of: outputting data indicating said images are not similar.
Claim 14
Dependent Claim
18 words
A method as claimed in claim 1 , wherein the images are frames from a digital video signal.
Claim 15
Dependent Claim
39 words
A method as claimed in claim 1 , wherein if the two images have different dimensions in pixels, then the image having the larger dimensions is scaled down to the smaller dimensions for the computation of the distance metric.
Claim 16
Dependent Claim
52 words
A method as claimed in claim 1 , wherein said distance metric is computed by averaging over all corresponding pixels in the two images the product of said predetermined semantic difference and a weighting function which depends on the probability of the labels being correctly assigned for each of the corresponding pixels.
Claim 17
Dependent Claim
28 words
A method as claimed in claim 15 , wherein the weighting function is the minimum value of the probabilities associated with the labels of the two corresponding pixels.
Claim 18
Dependent Claim
24 words
A method as claimed in claim 15 , wherein the weighting function is the mean of the label probabilities of the two corresponding pixels.
Claim 19
Dependent Claim
140 words
A method as claimed in claim 15 , wherein the distance metric D is computed for the two images i and j by averaging over all the pixel coordinates, k, in the images using, D = ∑ k d [ l ( k i ) , l ( k j ) ] w [ e ( k i ) , e ( k j ) ] / n k , where n k represents the total number of pixels in the images, d[.] represents the distance between the labels applied to the pixel in each of image i, l(k i ), and image j, l(k j ), and w[.] is said weighting function which depends on the label energies of image i, e(k i ), and image j, e(k j ).
Claim 20
Independent Claim
143 words
A method of computing the similarity between two images, wherein said images each comprise a plurality of pixels and said method comprises the steps of: segmenting each of the images into homogeneous regions; assigning semantic labels to the homogeneous regions to describe the content of the regions using a probabilistic method which results in each assigned label for a region having an associated probability or likelihood of the label being correctly assigned; computing a distance metric which averages over all corresponding pixels in the two images a value which is the product of a predetermined semantic difference between the assigned labels at the corresponding pixels and a weighting function which is derived from the associated probability of the labels for each of the corresponding pixels; and comparing the distance metric with a predetermined threshold in order to determine the similarity of the images.
Claim 21
Independent Claim
143 words
A method of computing the similarity between two images, wherein said images each comprise a plurality of pixels and said method comprises the steps of: segmenting each of the images into homogeneous regions; assigning semantic labels to the homogeneous regions to describe the content of the regions using a probabilistic method which results in each assigned label for a region having an associated probability or likelihood of the label being correctly assigned; computing a distance metric which averages over all corresponding pixels in the two images a value which is the product of a predetermined semantic difference between the assigned labels at the corresponding pixels and a weighting function which is derived from the associated probability of the labels for each of the corresponding pixels; and comparing the distance metric with a predetermined threshold in order to determine the similarity of the images.
Claim 22
Independent Claim
89 words
An apparatus for computing the similarity between two images, wherein said images each comprise a plurality of pixels and said apparatus comprises: means for segmenting each of the images into homogeneous regions; means for assigning to at least one of the generated regions a semantic label which describes the content of the region; and means for computing a distance metric from predetermined semantic differences between the assigned semantic labels at corresponding pixels in the two images, wherein said distance metric is representative of the similarity of the two images.
Claim 23
Independent Claim
89 words
An apparatus for computing the similarity between two images, wherein said images each comprise a plurality of pixels and said apparatus comprises: means for segmenting each of the images into homogeneous regions; means for assigning to at least one of the generated regions a semantic label which describes the content of the region; and means for computing a distance metric from predetermined semantic differences between the assigned semantic labels at corresponding pixels in the two images, wherein said distance metric is representative of the similarity of the two images.
Claim 24
Dependent Claim
43 words
An apparatus as claimed in claim 20 , wherein said apparatus further comprises: means for determining whether both images have the same dimensions in pixels, and if not, converting one of the images to have the same pixel dimensions as the other image.
Claim 25
Dependent Claim
35 words
An apparatus as claimed in claim 20 , wherein the predetermined semantic difference between two labels for a corresponding pixel is 1 if the labels are different and 0 if the labels are the same.
Claim 26
Dependent Claim
36 words
An apparatus as claimed in claim 20 , wherein the predetermined semantic difference between two labels is a value between 0 and 1, wherein a greater value is indicative of labels that are semantically substantially different.
Claim 27
Dependent Claim
48 words
An apparatus as claimed in claim 20 , wherein said assigning means comprises means for assigning the semantic labels to the homogeneous regions using a probabilistic method which results in each assigned label for a region having an associated probability or likelihood of the label being correctly assigned.
Claim 28
Dependent Claim
24 words
An apparatus as claimed in claim 24 , wherein the homogeneous regions generated by the segmenting means are represented by a region adjacency graph.
Claim 29
Dependent Claim
33 words
An apparatus as claimed in claim 25 , wherein the probabilistic method used to assign the labels to particular regions is based on a Markov Random Field modelled on the region adjacency graph.
Claim 30
Dependent Claim
38 words
An apparatus as claimed in claim 24 , wherein the associated probabilities of labels being correctly assigned are represented as energies, wherein a small energy value is indicative that a label has been assigned with a high probability.
Claim 31
Dependent Claim
34 words
An apparatus as claimed in claim 20 , wherein said apparatus further comprises: means for comparing the distance metric with a predetermined threshold; and means for outputting data indicating whether said images are similar.
Claim 32
Dependent Claim
18 words
An apparatus as claimed in claim 20 , wherein the images are frames from a digital video signal.
Claim 33
Dependent Claim
39 words
An apparatus as claimed in claim 20 , wherein if the two images have different dimensions in pixels, then the image having the larger dimensions is scaled down to the smaller dimensions for the computation of the distance metric.
Claim 34
Dependent Claim
52 words
An apparatus as claimed in claim 20 , wherein said distance metric is computed by averaging over all corresponding pixels in the two images the product of said predetermined semantic difference and a weighting function which depends on the probability of the labels being correctly assigned for each of the corresponding pixels.
Claim 35
Dependent Claim
28 words
An apparatus as claimed in claim 31 , wherein the weighting function is the minimum value of the probabilities associated with the labels of the two corresponding pixels.
Claim 36
Dependent Claim
24 words
An apparatus as claimed in claim 31 , wherein the weighting function is the mean of the label probabilities of the two corresponding pixels.
Claim 37
Dependent Claim
140 words
An apparatus as claimed in claim 31 , wherein the distance metric D is computed for the two images i and j by averaging over all the pixel coordinates, k, in the images using, D = ∑ k d [ l ( k i ) , l ( k j ) ] w [ e ( k i ) , e ( k j ) ] / n k , where n k represents the total number of pixels in the images, d[.] represents the distance between the labels applied to the pixel in each of image i, l(k i ), and image j, l(k j ), and w[.] is said weighting function which depends on the label energies of image i, e(k i ), and image j, e(k j ).
Claim 38
Independent Claim
148 words
An apparatus for computing the similarity between two images, wherein said images each comprise a plurality of pixels and said apparatus comprises: means for segmenting each of the images into homogeneous regions; means for assigning semantic labels to the homogeneous regions to describe the content of the regions using a probabilistic method which results in each assigned label for a region having an associated probability or likelihood of the label being correctly assigned; means for computing a distance metric which averages over all corresponding pixels in the two images a value which is the product of a predetermined semantic difference between the assigned labels at the corresponding pixels and a weighting function which is derived from the associated probability of the labels for each of the corresponding pixels; and means for comparing the distance metric with a predetermined threshold in order to determine the similarity of the images.
Claim 39
Independent Claim
148 words
An apparatus for computing the similarity between two images, wherein said images each comprise a plurality of pixels and said apparatus comprises: means for segmenting each of the images into homogeneous regions; means for assigning semantic labels to the homogeneous regions to describe the content of the regions using a probabilistic method which results in each assigned label for a region having an associated probability or likelihood of the label being correctly assigned; means for computing a distance metric which averages over all corresponding pixels in the two images a value which is the product of a predetermined semantic difference between the assigned labels at the corresponding pixels and a weighting function which is derived from the associated probability of the labels for each of the corresponding pixels; and means for comparing the distance metric with a predetermined threshold in order to determine the similarity of the images.
Claim 40
Dependent Claim
95 words
A computer readable medium comprising a computer program for computing the similarity between two images, wherein said images each comprise a plurality of pixels, said computer program comprises: code for segmenting each of the images into homogeneous regions; code for assigning to at least one of the generated regions a semantic label which describes the content of the region; and code for computing a distance metric from predetermined semantic differences between the assigned semantic labels at corresponding pixels in the two images, wherein said distance metric is representative of the similarity of the two images.
Claim 41
Dependent Claim
95 words
A computer readable medium comprising a computer program for computing the similarity between two images, wherein said images each comprise a plurality of pixels, said computer program comprises: code for segmenting each of the images into homogeneous regions; code for assigning to at least one of the generated regions a semantic label which describes the content of the region; and code for computing a distance metric from predetermined semantic differences between the assigned semantic labels at corresponding pixels in the two images, wherein said distance metric is representative of the similarity of the two images.
Claim 42
Dependent Claim
154 words
A computer readable medium comprising a computer program for computing the similarity between two images, wherein said images each comprise a plurality of pixels, said computer program comprises: code for segmenting each of the images into homogeneous regions; code for assigning semantic labels to the homogeneous regions to describe the content of the regions using a probabilistic method which results in each assigned label for a region having an associated probability or likelihood of the label being correctly assigned; code for computing a distance metric which averages over all corresponding pixels in the two images a value which is the product of a predetermined semantic difference between the assigned labels at the corresponding pixels and a weighting function which is derived from the associated probability of the labels for each of the corresponding pixels; and code for comparing the distance metric with a predetermined threshold in order to determine the similarity of the images.
Claim 43
Dependent Claim
154 words
A computer readable medium comprising a computer program for computing the similarity between two images, wherein said images each comprise a plurality of pixels, said computer program comprises: code for segmenting each of the images into homogeneous regions; code for assigning semantic labels to the homogeneous regions to describe the content of the regions using a probabilistic method which results in each assigned label for a region having an associated probability or likelihood of the label being correctly assigned; code for computing a distance metric which averages over all corresponding pixels in the two images a value which is the product of a predetermined semantic difference between the assigned labels at the corresponding pixels and a weighting function which is derived from the associated probability of the labels for each of the corresponding pixels; and code for comparing the distance metric with a predetermined threshold in order to determine the similarity of the images.
References Cited (Backward Citations)
US5544256A
Cited
US5745598A
Cited
US6108674A
Cited
US5995668A
Cited
US5929940A
Cited
US5963670A
Cited
US5893095A
Cited
US5884294A
Cited
US6463426B1
Cited
US6134541A
Cited
US6175663B1
Cited
US6516090B1
Cited
US6345274B1
Cited
US6192150B1
Cited
US6584221B1
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2007-04-06 | 2007-10-06 | 2008-04-06 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2011-04-06 | 2011-10-06 | 2012-04-06 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2015-04-06 | 2015-10-06 | 2016-04-06 | $7700.00 | Window Closed / Lapsed |