Method and apparatus for computing the similarity between images

• US 6,718,063 B1
• Filed: 12/10/1999
• Issued: 04/06/2004
• Est. Priority Date: 12/11/1998
• Status: Expired due to Fees

• Current Assignee: Canon Kabushiki Kaisha (Canon Inc.)
• Original Assignee: Canon Kabushiki Kaisha (Canon Inc.)
• Inventors: Wu, Jing, Lennon, Alison Joan
• Primary Examiner(s): Mehta, Bhavesh M.
• Assistant Examiner(s): DESIRE, GREGORY M
• Application Number:
  US09/458,063
• Time in Patent Office: 1,579 Days
• Field of Search: 345/700, 382/173, 382/180, 382/190, 382/209, 382/219-220, 382/224, 382/228, 382/305, 707/3, 707/5-6
• US Class Current: 382/224
• CPC Class Codes: G06V 10/426 Graphical representations
• CPC Class Codes: G06V 20/38 Outdoor scenes
• CPC Class Codes: Y10S 707/99936 Pattern matching access

Abstract

The method first segments both images into homogeneous regions (205A) and assigns (207A) 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.

Claims

1. 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.

2. 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.

3. A method as claimed in claim 2, wherein said determining and converting step occurs after said assigning step.

4. A method as claimed in claim 2, wherein said determining and converting steps occurs during said computing step.

5. 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.

6. 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.

7. 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.

8. A method as claimed in claim 7, wherein the homogeneous regions generated in said segmenting step are represented by a region adjacency graph.

9. 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.

10. 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.

11. 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.

12. 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.

13. A method as claimed in claim 1, wherein the images are frames from a digital video signal.

14. 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.

15. 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.

16. 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.

17. A method as claimed in claim 15, wherein the weighting function is the mean of the label probabilities of the two corresponding pixels.

18. 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=\sum _{}$

k

 



d

[l

(ki),l

(kj)]

w

[e

(ki),e

(kj)]/nk,

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).

19. 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.

20. 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.

21. 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.

22. 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.

23. 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.

24. 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.

25. An apparatus as claimed in claim 24, wherein the homogeneous regions generated by the segmenting means are represented by a region adjacency graph.

26. 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.

27. 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.

28. 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.

29. An apparatus as claimed in claim 20, wherein the images are frames from a digital video signal.

30. 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.

31. 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.

32. 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.

33. An apparatus as claimed in claim 31, wherein the weighting function is the mean of the label probabilities of the two corresponding pixels.

34. 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=\sum _{}$

k

 



d

[l

(ki),l

(kj)]

w

[e

(ki),e

(kj)]/nk,

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).

35. 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.

36. 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.

37. 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.