Pre-computing digests for image similarity searching of image-based listings in a network-based publication system
A system and method, which may be an offline method, extracts relevant image features about listing items in a network-based publication system for enabling image similarity searching of such listing items. When a seller lists an item, an image of the item is uploaded and may be sent to a picture processing service, which generates several 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 listings by image similarity at scale. A similar process can be performed for a query listing for searching the search database for items similar to the query listing.
1. A computer implemented method, comprising:
receiving a listing image associated with an item listing on a network-based publication system, the listing image including addressable pixels; and
detecting, using one or more processors, regions of visually perceptible color change in the listing image by computing a color gradient of the listing image using a plurality of windows of computation to compute the distance between histograms of at least some of the pixels of the listing 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 listing 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 window dividing an area of the listing image within the circle into a plurality of regions, the method further including computing the histograms 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 the 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 an 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 difference between the histograms of the pixels of the listing 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 listing image by assembling matrices of grey level co-occurrence of the individual portions, and transforming the matrices to emphasize high contrast between the individual one of the 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 listing image includes structured data and unstructured data.
12. The method of claim 1 , further including:
providing translation normalization for a listing image by performing edge detection for the listing image;
computing a gradient for the edge detected listing image;
constructing a bounding box around the edge detected listing image;
dividing the edge detected listing 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 a listing image by
performing edge detection of a listing 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 edge detected image.
14. A non-transitory computer-readable storage medium having embedded therein a set of instructions which, when executed by one or more processors of a computer, causes the computer to execute the operations comprising:
receiving a listing image associated with an item listing on a network-based publication system, the listing image including addressable pixels; and
detecting regions of visually perceptible color change in the listing image by computing a color gradient of the listing image using a plurality of windows of computation to compute the distance between histograms of at least some of the pixels of the listing image.
15. The non-transitory computer-readable medium of claim 14 the operations further comprising using individual windows of the plurality of windows of computation to divide the pixels of at least one of the listing 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 non-transitory computer-readable medium of claim 15 wherein each window of computation is a circle, the diameter of each window dividing an area of the listing 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 non-transitory computer-readable medium of claim 15 the operations further comprising 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 non-transitory computer-readable medium of claim 17 wherein the plurality of regions is two regions.
19. The non-transitory computer-readable medium of claim 18 wherein the diameter of the circle is rotated a predetermined number of degrees for a predetermined number of times.
20. The non-transitory computer-readable medium of claim 15 wherein the detecting regions of visually perceptible color change includes:
dividing a color spectrum represented by a circumference of a circle of an 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 difference between the histograms of the pixels of the listing 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.
21. The non-transitory computer-readable medium of claim 15 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.
22. The non-transitory computer-readable medium of claim 15 the operations further including detecting a texture of individual ones of the portions of the listing 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 individual ones of the portions by applying a transforming equation.
23. The non-transitory computer-readable medium of claim 22 wherein the transforming equation is
nx,y = mx,y ((| x−y |)+1)2
where
mx,y is the value in the original matrix at position (x,y); and
x,y are grey values.
24. The non-transitory computer-readable medium of claim 15 wherein at least one of the portions of the listing image including structured data and unstructured data.
25. The non-transitory computer-readable medium of claim 15 the operators further including:
providing translation normalization for a listing image by performing edge detection for the listing image;
computing a gradient for the edge detected listing image;
constructing a bounding box around the edge detected listing image;
dividing the edge detected listing 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.
26. The non-transitory computer-readable medium of claim 15 the operators further including providing rotation normalization for a listing image by
performing edge detection of a listing 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 edge detected image.
27. A computer system comprising:
a computer processor and storage configured to execute
a receiving module for receiving a listing image associated with an item listing on a network-based publication system, the listing image including addressable pixels; and
a detector module for detecting regions of visually perceptible color change in the listing image by computing a color gradient of the listing image using a plurality of windows of computation to compute the distance between histograms of at least some of the pixels of the listing image.
28. The computer system of claim 27 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 listing 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 ones of the portions by applying a transforming equation.