Pre-computing digests for image similarity searching of image-based listings in a network-based publication system

Patent metadata

Field	Value
Publication number	US-9280563-B2
Application number	US-201314133455-A
Country	US
Kind code	B2
Filing date	Dec 18, 2013
Priority date	Mar 29, 2010
Publication date	Mar 8, 2016
Grant date	Mar 8, 2016

Abstract

A system and method, which may be an offline method, extracts relevant image features about images in a network-based publication system for enabling image similarity searching of such images. An image is uploaded and may be sent to a picture processing service, which generates digests. The digests are compressed data structures each representing a particular image feature such as edge, color, texture, or words. These digests are then stored in a search database, where the digests can be used to retrieve images by image similarity at scale. A similar process can be performed for an image query for searching the search database for images similar to the image.

First claim

What is claimed is:

1. A computer implemented method, comprising:
receiving an image associated with an item on a network-based publication system, the image including pixels that are addressable; and
detecting, using one or more processors, regions of visually perceptible color change in the image by computing a color gradient of the image using a plurality of windows of computation to compute the distance between histograms of at least some of the pixels of the image.

2. The method of claim 1 , further including using individual windows of the plurality of windows of computation to divide the pixels of at least one of the images into a plurality of areas, and computing a difference in intensity of blackness versus whiteness of at least some of the plurality of areas.

3. The method of claim 1 , wherein each window of computation is a circle, the diameter of each circle dividing an area of the image within the circle into a plurality of regions, the method further including computing the histograms of at least some of the pixels that lie in each of the plurality of regions.

4. The method of claim 3 , further including rotating the diameter of the circle after each calculation of the histogram, and computing the histogram at a new location of the diameter of the circle.

5. The method of claim 3 wherein the plurality of regions is two regions.

6. The method of claim 4 , wherein the diameter of the circle is rotated a predetermined number of degrees for a predetermined number of times.

7. The method of claim 1 wherein the detecting regions of visually perceptible color change includes:
dividing a color spectrum represented by a circumference of a circle of a Hue, Lightness, Saturation (HLS) cone into discrete regions, each of the discrete regions representing a color of the color spectrum;
calculating increasing luminosity along one dimension of the HLS cone;
calculating increasing saturation along another axis of the HLS cone; and
computing the distance between the histograms of the pixels of the image, the computing of the difference between the histograms including weighting the discrete region representing a first color with respect to the discrete region representing a second color, the weighting being proportional to a number of discrete regions between the region representing the first color and the region representing the second color.

8. The method of claim 1 , wherein the detecting regions of visually perceptible color change includes:
dividing a circular hue space into a plurality of discrete regions representing the colors of the visible spectrum, white, black, and grey;
calculating values of a count of pixels falling into each discrete region representing a color, an average luminosity of each pixel in the discrete region, and an average saturation of each pixel; and
weighting the distance between one discrete region and each of the other discrete regions by a weight respectively proportional to a number of discrete regions between the one discrete region and each of the other discrete regions.

9. The method of claim 1 further including detecting a texture of individual ones of the portions of the image by assembling matrices of grey level co-occurrence of the individual portions, and transforming the matrices to emphasize high contrast between the individual portions by applying a transforming equation.

10. The method of claim 9 wherein
the transforming equation is n x,y =m x,y ((|x−y|)+1) 2

where m x,y is the value in the original matrix at position (x,y);
and x,y are grey values.

11. The method of claim 1 , wherein at least one of the portions of the image including structured data and unstructured data.

12. The method of claim 1 , further including:
providing translation normalization for an image by performing edge detection for the image; computing a gradient for the image that is edge detected; constructing a bounding box around the edge detected image; dividing the edge detected image into a plurality of sub-images, each of the plurality of sub-images representing a multi-dimensional vector;
running a clustering algorithm on a plurality of multi-dimensional vectors to determine a centroid of each of the plurality the multi-dimensional vectors; and
assigning the centroid to a respective one of the multi-dimensional vectors.

13. The method of claim 1 further including providing rotation normalization for an image by:
performing edge detection of an image;
finding the two major Eigen vectors of the edge detected image; and
aligning one of the major Eigen vectors of the edge detected image with an axis of the system.

14. One or more computer-readable storage device having embedded therein a set of instructions which, when executed by one or more processors of a computer, causes the computer to execute operations comprising:
receiving an image associated with an item on a network-based publication system, the image including addressable pixels; and
detecting regions of visually perceptible color change in the image by computing a color gradient of the image using a plurality of windows of computation to compute the distance between histograms of at least some of the pixels of the image.

15. The one or more computer-readable storage device of claim 14 further including using individual windows of the plurality of windows of computation to divide the pixels of at least one of the images into a plurality of areas, and computing a difference in intensity of blackness versus whiteness of at least some of the plurality of areas.

16. The one or more computer-readable storage device of claim 15 wherein each window of computation is a circle, a diameter of each circle dividing an area of the image within the circle into a plurality of regions, the operations further including computing the histograms of the pixels that lie in each of the plurality of regions.

17. The one or more computer-readable storage device of claim 16 further including rotating the diameter of the circle after each calculation of the histogram, and computing the histogram at the new location of the diameter of the circle.

18. The one or more computer-readable storage device of claim 17 wherein the diameter of the circle is rotated a predetermined number of degrees for a predetermined number of times.

19. A computer system comprising: A computer processor and storage configured to execute A receiving module for receiving an image associated with an item on a network-based publication system, the image including addressable pixels; and a detector module for detecting regions of visually perceptible color change in the image by computing a color gradient of the image using a plurality of windows of computation to compute the distance between histograms of at least some of the pixels of the image.

20. The computer system of claim 19 the processor and storage further configured to execute an image texture detection module for detecting the texture of individual ones of the portions of the image by assembling matrices of grey level co-occurrence of the individual ones of the portions, and transforming the matrices to emphasize high contrast between the ones of the individual portions by applying a transforming equation.

Assignees

• Ebay Inc

Inventors

• Chittar Naren
• Ghatare Sanjay Pundlkrao
• Mcdonald Ryan
• Roper John
• Schmitz Michael

Classifications

• G06F16/532 Primary

  Query formulation, e.g. graphical querying · CPC title

• G06T7/90

  Determination of colour characteristics · CPC title

• G06F16/50

  of still image data · CPC title

• G06F16/5838

  using colour · CPC title

• G06V10/56

  relating to colour · CPC title