Automated identification of image outliers

• US 8,463,026 B2
• Filed: 12/22/2010
• Issued: 06/11/2013
• Est. Priority Date: 12/22/2010
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Barros, Marcelo De, Kanduri, Satya Pradeep, Kaushal, Nabeel, Parakhin, Mikhail, Mittal, Manish, Edlavitch, Adam
• Primary Examiner(s): Chen, Wenpeng
• Assistant Examiner(s): Niu, Feng
• Application Number:
  US12/975,684
• Publication Number:
  US 20120163709A1
• Time in Patent Office: 902 Days
• Field of Search: None
• US Class Current: 382/162
• CPC Class Codes: G06F 16/583 using metadata automatically derived from the content
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06F 18/2193 based on specific statistical tests
• CPC Class Codes: G06F 18/2433 Single-class perspective, e.g. one-against-all classification; Novelty detection; Outlier detection
• CPC Class Codes: G06V 10/7796 based on specific statistical tests

Abstract

Outlier images—those images that differ substantially from other images in a set—can be automatically identified. One or more penalty values can be assigned to each image that quantifies how different that image is from others in the set. A threshold can be determined based on the set of penalty values. Each image whose penalty values are above the threshold is an outlier image. The penalty values can be the sum of per-pixel penalty values multiplied by the number of pixels with nonzero penalty values. A per-pixel penalty value can be the difference between a color value for that pixel and a predetermined range of color values, based on corresponding pixels in other images. The per-pixel penalty value can be determined for each component color and then optionally summed together. The threshold penalty values can be adjusted to provide for greater, or less, sensitivity to differences among the images.

Claims

1. One or more hardware computer-readable storage media comprising computer-executable instructions for automatically identifying outlier images in a set of images, the computer-executable instructions performing steps comprising:

selecting a pixel in an image from the set of images;

generating an average color value for the selected pixel by averaging color values for corresponding pixels in other images from the set of images;

establishing a color value range around the generated average color value for the selected pixel, the established color value range being based on the color values for the corresponding pixels in the other images from the set of images;

generating a per-pixel penalty value for the selected pixel based on a difference between a color value of the selected pixel and a threshold color value of the established color value range for the selected pixel that is closest to the color value of the selected pixel if the color value of the selected pixel is outside of the established color value range for the selected pixel;

setting the per-pixel penalty value for the selected pixel to zero if the color value of the selected pixel is within the established color value range for the selected pixel;

repeating, for other pixels in the image, the selecting, the generating the average color value, the establishing, the generating the per-pixel penalty value and the setting the per-pixel penalty value;

generating an image penalty value for the image from the set of images based on a sum of the generated per-pixel penalty values for pixels in the image;

generating a threshold penalty value based on the generated image penalty values;

identifying, as the outlier images, images having the image penalty value greater than the threshold penalty value.

2. The hardware computer-readable storage media of claim 1, wherein the computer-executable instructions for generating the threshold penalty value comprise computer-executable instructions for:

generating an average penalty value by averaging the generated image penalty values;

determining a standard deviation of the generated image penalty values; and

generating the threshold penalty value by adding a multiple of the standard deviation to the average penalty value.

3. The hardware computer-readable storage media of claim 1, wherein the computer-executable instructions for generating the threshold penalty value comprise computer-executable instructions for:

receiving a sensitivity adjustment value and generating the threshold penalty value in accordance with the sensitivity adjustment value, such that a higher sensitivity adjustment value results in a higher threshold penalty value and a lower sensitivity adjustment value results in a lower threshold penalty value.

4. The hardware computer-readable storage media of claim 1, wherein the computer-executable instructions for generating the image penalty value comprise computer-executable instructions for generating the image penalty value based on a product of a number of pixels in the image having non-zero per-pixel penalty values and the sum of the generated per-pixel penalty values.

5. The hardware computer-readable storage media of claim 1, wherein the average color value for the selected pixel comprises average color values for each component color of the selected pixel;

and wherein further the computer-executable instructions for generating the per-pixel penalty value comprise computer-executable instructions for generating a per-pixel penalty value for each of the component colors and summing the generated per-pixel penalty values for each of the component colors to generate the per-pixel penalty value for the selected pixel.

6. The hardware computer-readable storage media of claim 1, wherein the computer-executable instructions for generating the per-pixel penalty value for the selected pixel comprise computer-executable instructions for amortizing the difference between the color value of the selected pixel and the average color value for the selected pixel based on a distance between the selected pixel and a center of the image.

7. The hardware computer-readable storage media of claim 1, comprising further computer-executable instructions for resizing images in the set of images to a common image size.

8. A method for automatically identifying outlier images in a set of images, the method comprising the steps of:

selecting a pixel in an image from the set of images;

generating an average color value for the selected pixel by averaging color values for corresponding pixels in other images from the set of images;

establishing a color value range around the generated average color value for the selected pixel, the established color value range being based on the color values for the corresponding pixels in the other images from the set of images;

generating a per-pixel penalty value for the selected pixel based on a difference between a color value of the selected pixel and a threshold color value of the established color value range for the selected pixel that is closest to the color value of the selected pixel if the color value of the selected pixel is outside of the established color value range for the selected pixel;

setting the per-pixel penalty value for the selected pixel to zero if the color value of the selected pixel is within the established color value range for the selected pixel;

repeating, for other pixels in the image, the selecting, the generating the average color value, the establishing, the generating the per-pixel penalty value and the setting the per-pixel penalty value;

generating an image penalty value for the image from the set of images based on a sum of the generated per-pixel penalty values for pixels in the image;

generating a threshold penalty value based on the generated image penalty values;

identifying, as the outlier images, images having the image penalty value greater than the threshold penalty value.

9. The method of claim 8, wherein the generating the threshold penalty value comprises:

generating an average penalty value by averaging the generated image penalty values;

determining a standard deviation of the generated image penalty values; and

generating the threshold penalty value by adding a multiple of the standard deviation to the average penalty value.

10. The method of claim 8, wherein the generating the threshold penalty value comprises:

receiving a sensitivity adjustment value and generating the threshold penalty value in accordance with the sensitivity adjustment value, such that a higher sensitivity adjustment value results in a higher threshold penalty value and a lower sensitivity adjustment value results in a lower threshold penalty value.

11. The method of claim 8, wherein the generating the image penalty value comprises generating the image penalty value based on a product of a number of pixels in the image having non-zero per-pixel penalty values and the sum of the generated per-pixel penalty values.

12. The method of claim 8, wherein the average color value for the selected pixel comprises average color values for each component color of the selected pixel;

and wherein further the generating the per-pixel penalty value comprises generating a per-pixel penalty value for each of the component colors and summing the generated per-pixel penalty values for each of the component colors to generate the per-pixel penalty value for the selected pixel.

13. The method of claim 8, wherein the generating the per-pixel penalty value for the selected pixel comprises amortizing the difference between the color value of the selected pixel and the average color value for the selected pixel based on a distance between the selected pixel and a center of the image.

14. The method of claim 8, further comprising the step of resizing images in the set of images to a common image size.

15. A user interface generated on a display device by computing device, the user interface comprising:

a user-controllable interface element for modifying a sensitivity adjustment value; and

a dynamically updated set of images comprising those images, from among an initial set of images, that are associated with penalty values less than a threshold penalty value that is determined by increasing an average penalty value by an amount based on the sensitivity adjustment value, the set of images being dynamically updated in response to modifications to the sensitivity adjustment value;

wherein a penalty value associated with an image is determined by performing steps comprising;

selecting a pixel in the image;

generating an average color value for the selected pixel by averaging color values for corresponding pixels in other images from the initial set of images;

establishing a color value range around the generated average color value for the selected pixel, the established color value range being based on the color values for the corresponding pixels in the other images from the initial set of images;

generating a per-pixel penalty value for the selected pixel based on a difference between a color value of the selected pixel and a threshold color value of the established color value range for the selected pixel that is closest to the color value of the selected pixel if the color value of the selected pixel is outside of the established color value range for the selected pixel;

setting the per-pixel penalty value for the selected pixel to zero if the color value of the selected pixel is within the established color value range for the selected pixel;

repeating, for other pixels in the image, the selecting, the generating the average color value, the establishing, the generating the per-pixel penalty value and the setting the per-pixel penalty value; and

generating the penalty value associated with the image based on a sum of the generated per-pixel penalty values for pixels in the image.

16. The user interface of claim 15, wherein the generating the penalty value associated with the image comprises generating the penalty value associated with the image based on a product of a number of pixels in the image having non-zero per-pixel penalty values and the sum of the generated per-pixel penalty values.

17. The user interface of claim 15, wherein the average color value for the selected pixel comprises average color values for each component color of the selected pixel;

and wherein further the generating the per-pixel penalty value comprises generating a per-pixel penalty value for each of the component colors and summing the generated per-pixel penalty values for each of the component colors to generate the per-pixel penalty value for the selected pixel.

18. The user interface of claim 15, wherein the generating the per-pixel penalty value for the selected pixel comprises amortizing the difference between the color value of the selected pixel and the average color value for the selected pixel based on a distance between the selected pixel and a center of the image.

19. The user interface of claim 15, wherein images in the initial set of images are resized to a common image size prior to the determination of penalty values associated with the images.