Annotating images

• US 8,422,832 B2
• Filed: 04/17/2009
• Issued: 04/16/2013
• Est. Priority Date: 06/06/2008
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Makadia, Ameesh, Kumar, Sanjiv
• Primary Examiner(s): Park, Chan S
• Assistant Examiner(s): Roz, Mark
• Application Number:
  US12/425,910
• Publication Number:
  US 20090304272A1
• Time in Patent Office: 1,460 Days
• Field of Search: 382/305, 382/224, 382/229, 382/209
• US Class Current: 382/305
• CPC Class Codes: G06F 16/58 Retrieval characterised by using metadata, e.g. metadata not derived from the content or metadata generated manually
• CPC Class Codes: G06F 40/169 Annotation, e.g. comment data or footnotes
• CPC Class Codes: G06V 10/40 Extraction of image or video features
• CPC Class Codes: G06V 20/10 Terrestrial scenes scenes under surveillance with static cameras G06V20/52; scenes perceived from the exterior of a vehicle G06V20/56; scenes perceived from the interior of a vehicle G06V20/59
• CPC Class Codes: G06V 20/70 Labelling scene content, e.g. deriving syntactic or semantic representations

Abstract

Methods, systems, and apparatus, including computer program products, for generating data for annotating images automatically. In one aspect, a method includes receiving an input image, identifying one or more nearest neighbor images of the input image from among a collection of images, in which each of the one or more nearest neighbor images is associated with a respective one or more image labels, assigning a plurality of image labels to the input image, in which the plurality of image labels are selected from the image labels associated with the one or more nearest neighbor images, and storing in a data repository the input image having the assigned plurality of image labels. In another aspect, a method includes assigning a single image label to the input image, in which the single image label is selected from labels associated with multiple ranked nearest neighbor images.

Claims

1. A method of image annotation performed by a data processing apparatus, the method comprising:

receiving an input image in the data processing apparatus;

identifying a plurality of nearest neighbor images of the input image from among a collection of digital images stored on computer-readable media by operation of the data processing apparatus, wherein each of the nearest neighbor images is associated with a respective one or more image labels;

assigning a plurality of image labels to the input image, wherein the plurality of image labels are selected by the data processing apparatus from the image labels associated with the nearest neighbor images,

ranking one or more first image labels according to a respective frequency of occurrence in the collection of digital images, wherein each of the one or more first image labels is associated with a first nearest neighbor image;

ranking one or more second image labels, each of the second image labels being associated with one or more remaining nearest neighbor images, wherein ranking of the one or more second image labels comprises sorting the one or more second image labels according to a co-occurrence of each of the second image labels with each first image label in the collection of digital images,

and wherein assigning the plurality of image labels comprises (1) assigning at least one of the first image labels to the input image based on the ranking of the one or more first image labels and (2) assigning at least one of the second image labels to the input image based on the ranking of the one or more second image labels; and

storing in a digital data repository the input image having the assigned plurality of image labels.

2. The method of claim 1, wherein the input image is stored in the digital data repository in an image file including the plurality of image labels as metadata.

3. The method of claim 1, wherein the collection of digital images comprises a plurality of reference images, and wherein identifying the plurality of nearest neighbor images comprises:

determining, for each reference image, a corresponding whole-image distance representing a degree of difference between the input image and the reference image; and

identifying reference images closest to the input image, as measured by the whole-image distances, as the plurality of nearest neighbors.

4. The method of claim 1, wherein ranking of the one or more second image labels comprises sorting the one or more second image labels according to a local frequency of each of the second image labels in the one or more remaining nearest neighbor images.

5. The method of claim 3, wherein the whole-image distance comprises a combination of feature distances, each feature distance representing a degree of difference between an image feature associated with the input image and a corresponding image feature associated with the corresponding reference image.

6. The method of claim 5, wherein at least one image feature is a global image feature extracted from both the input image and the reference image.

7. The method of claim 5, wherein at least one image feature is a local image feature extracted from both the input image and the reference image.

8. The method of claim 5, wherein each feature distance is weighted equally in the whole-image distance.

9. The method of claim 5, wherein two or more feature distances are weighted differently from one another in the whole-image distance.

10. The method of claim 5, further comprising:

calculating a weighting for each of the feature distances based on the collection of digital images, wherein the collection of digital images is a group of training images comprising pairs of similar and dissimilar images.

11. The method of claim 5, further comprising:

calculating at least one of the feature distances as a difference between a texture feature of the input image and a corresponding texture feature of the corresponding reference image.

12. The method of claim 5, further comprising:

calculating at least one of the feature distances as a difference between a color feature of the input image and a corresponding color feature of the corresponding reference image.

13. A system comprising:

a server implemented on one or more computers and operable to perform operations comprising;

receiving an input image in the server;

identifying a purality of nearest neighbor images of the input image from among a collection of digital images stored on computer-readable media by operation of the server, wherein each of the nearest neighbor images is associated with a respective one or more image labels;

assigning a plurality of image labels to the input image, wherein the plurality of image labels are selected by the server from the image labels associated with the nearest neighbor images,

ranking one or more first image labels according to a respective frequency of occurrence in the collection of digital images, wherein each of the one or more first image labels is associated with a first nearest neighbor image;

ranking one or more second image labels, each of the second image labels being associated with one or more remaining nearest neighbor images, wherein ranking of the one or more second image labels comprises sorting the one or more second image labels according to a co-occurrence of each of the second image labels with each first image label in the collection of digital images,

and wherein assigning the plurality of image labels comprises (1) assigning at least one of the first image labels to the input image based on the ranking of the one or more first image labels and (2) assigning at least one of the second image labels to the input image based on the ranking of the one or more second image labels; and

storing in a digital data repository the input image having the assigned plurality of image labels.

14. The system of claim 13, wherein the collection of digital images comprises a plurality of reference images, and wherein identifying the plurality of nearest neighbor images comprises:

determining, for each reference image, a corresponding whole-image distance representing a degree of difference between the input image and the reference image; and

identifying the reference images closest to the input image, as measured by the whole-image distances, as the plurality of nearest neighbors.

15. The system of claim 13, wherein ranking of the one or more second image labels comprises sorting the one or more second image labels according to a local frequency of each of the second image labels in the one or more remaining nearest neighbor images.

16. The system of claim 14, wherein the whole-image distance comprises a combination of feature distances, each feature distance representing a degree of difference between an image feature associated with the input image and a corresponding image feature associated with the corresponding reference image.

17. The system of claim 16, wherein at least one image feature is a global image feature extracted from both the input image and the reference image.

18. The system of claim 16, wherein at least one image feature is a local image feature extracted from both the input image and the reference image.

19. The system of claim 16, wherein each feature distance is weighted equally in the whole-image distance.

20. The system of claim 16, wherein two or more feature distances are weighted differently from one another in the whole-image distance.

21. The system of claim 16, wherein the server is operable to perform operations further comprising:

calculating a weighting for each of the feature distances based on the collection of digital images, wherein the collection of digital images is a group of training images comprising pairs of similar and dissimilar images.

22. The system of claim 16, wherein the server is operable to perform operations further comprising:

calculating at least one of the feature distances as a difference between a texture feature of the input image and a corresponding texture feature of the corresponding reference image.

23. The system of claim 16, wherein the server is operable to perform operations further comprising:

calculating at least one of the feature distances as a difference between a color feature of the input image and a corresponding color feature of the corresponding reference image.

24. A non-transitory computer storage medium encoded with a computer program, the program comprising instructions that when executed by data processing apparatus cause the data processing apparatus to perform operations comprising:

receiving an input image in the data processing apparatus;

identifying a plurality of nearest neighbor images of the input image from among a collection of digital images stored on computer-readable media by operation of the data processing apparatus, wherein each of the one or more nearest neighbor images is associated with a respective one or more image labels;

assigning a plurality of image labels to the input image, wherein the plurality of image labels are selected by the data processing apparatus from the image labels associated with the nearest neighbor images,

ranking one or more first image labels according to a respective frequency of occurrence in the collection of digital images, wherein each of the one or more first image labels is associated with a first nearest neighbor image;

ranking one or more second image labels, each of the second image labels being associated with one or more remaining nearest neighbor images, wherein ranking of the one or more second image labels comprises sorting the one or more second image labels according to a co-occurrence of each of the second image labels with each first image label in the collection of digital images,

and wherein assigning the plurality of image labels comprises (1) assigning at least one of the first image labels to the input image based on the ranking of the one or more first image labels and (2) assigning at least one of the second image labels to the input image based on the ranking of the one or more second image labels; and

storing in a digital data repository the input image having the assigned plurality of image labels.

25. The computer storage medium of claim 24, wherein the collection of digital images comprises a plurality of reference images, and wherein identifying the plurality of nearest neighbor images comprises:

determining, for each reference image, a corresponding whole-image distance representing a degree of difference between the input image and the reference image; and

identifying one or more reference images closest to the input image, as measured by the whole-image distances, as the plurality of nearest neighbors.

26. The computer storage medium of claim 24, wherein ranking of the one or more second image labels comprises sorting the one or more second image labels according to a local frequency of each of the second image labels in the one or more remaining nearest neighbor images.

27. The computer storage medium of claim 25, wherein the whole-image distance comprises a combination of feature distances, each feature distance representing a degree of difference between an image feature associated with the input image and a corresponding image feature associated with the corresponding reference image.

28. The computer storage medium of claim 27, wherein at least one image feature is a global image feature extracted from both the input image and the reference image.

29. The computer storage medium of claim 27, wherein at least one image feature is a local image feature extracted from both the input image and the reference image.

30. The computer storage medium of claim 27, wherein each feature distance is weighted equally in the whole-image distance.

31. The computer storage medium of claim 27, wherein two or more feature distances are weighted differently from one another in the whole-image distance.

32. The computer storage medium of claim 27, operable to cause data processing apparatus to perform operations further comprising:

calculating a weighting for each of the feature distances based on the collection of digital images, wherein the collection of digital images is a group of training images comprising pairs of similar and dissimilar images.

33. The computer storage medium of claim 27, operable to cause data processing apparatus to perform operations further comprising:

calculating at least one of the feature distances as a difference between a texture feature of the input image and a corresponding texture feature of the corresponding reference image.

34. The computer storage medium of claim 27, operable to cause data processing apparatus to perform operations further comprising:

calculating at least one of the feature distances as a difference between a color feature of the input image and a corresponding color feature of the corresponding reference image.