Perceptual similarity image retrieval

• US 7,031,555 B2
• Filed: 02/28/2003
• Issued: 04/18/2006
• Est. Priority Date: 07/30/1999
• Status: Expired due to Term

• Current Assignee: Mind Fusion, LLC (Ascend Innovation Management, LLC)
• Original Assignee: Pixlogic, LLC
• Inventors: Troyanker, Vlad
• Primary Examiner(s): MARIAM, DANIEL G
• Application Number:
  US10/378,160
• Publication Number:
  US 20030231806A1
• Time in Patent Office: 1,145 Days
• Field of Search: 382/165, 382/190, 382/209, 382/219, 382/282, 382/305, 382/162, 382/170, 382/195, 382/199, 382/203, 382/224, 382/241, 707 1- 10, 358/403
• US Class Current: 382/305
• CPC Class Codes: G06F 16/532 Query formulation, e.g. graphical querying
• CPC Class Codes: G06F 16/5838 using colour
• CPC Class Codes: G06V 10/478 Contour-based spectral representations or scale-space representations, e.g. by Fourier analysis, wavelet analysis or curvature scale-space [CSS]
• CPC Class Codes: G06V 20/00 Scenes; Scene-specific elements control of digital cameras H04N23/60
• CPC Class Codes: G06V 20/582 of traffic signs
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching

Abstract

A system and method indexes an image database by partitioning an image thereof into a plurality of cells, combining the cells into intervals and then spots according to perceptual criteria, and generating a set of spot descriptors that characterize the perceptual features of the spots, such as their shape, color and relative position within the image. The shape preferably is a derivative of the coefficients of a Discrete Fourier Transform (DFT) of the perimeter trace of the spot. The set of spot descriptors forms as an index entry for the spot. This process repeated for the various images of the database. To search the index, a key comprising a set of spot descriptors for a query image is generated and compared according to a perceptual similarity metric to the entries of the index. The metric determines the perceptual similarity that the features of the query image match those of the indexed image. The search results are presented as a scored list of the indexed images. A wide variety of image types can be indexed and searched, including: bi-tonal, gray-scale, color, “real scene” originated, and artificially generated images. Continuous-tone “real scene” images such as digitized still pictures and video frames are of primary interest. There are stand alone and networked embodiments. A hybrid embodiment generates keys locally and performs image and index storage and perceptual comparison on a network or web server.

Claims

1. A method of indexing images according to visual characteristics of the images, the method comprising the steps of:

receiving an array of pixel representations that represent an image;

processing the array of pixel representations to determine a plurality of spots associated with the image, each spot comprising a connected region of the image having selected visual characteristics that vary spatially within a selected tolerance;

generating a plurality of spot descriptors, each spot descriptor indicating the visual characteristics of a respective spot; and

using the plurality of spot descriptors as an index entry for the image.

2. The method of claim 1, wherein the steps are performed by a programmable processor functionally coupled with a memory unit in response to a program stored in the memory unit.

3. The method of claim 1 wherein the steps are performed by a processing unit in response to a program embedded in the processing unit.

4. The method of claim 1, wherein the steps are performed by an embedded system.

5. The method of claim 1, wherein a first server performs the receiving, processing, generating, and using steps for each of a plurality of images to generate a plurality of index entries, and transmits the plurality of index entries to a second server that searches the plurality of index entries according to user supplied criteria.

6. The method of claim 1, wherein the step of receiving, processing, generating and using are repeated for each of a plurality of images to provide a respective plurality of index entries that index the plurality of images.

7. The method of claim 6, further comprising:

receiving a second array of pixel representations that represent a query image;

performing the acts of processing and using on the second array of pixels to determine a second plurality of spot descriptors; and

comparing the plurality of spot descriptors of the query image to each respective index entry and responsive thereto determining a score that indicates the perceptual similarity of each of the plurality of images to the query image.

8. The method of claim 1, wherein processing the array of pixel representations comprises:

partitioning the array of pixel representations to generate a plurality of cells, each cell comprising a connected region of the image;

determining a plurality of visual characteristics of each cell; and

forming the plurality of spots by joining connected cells where the perceptual difference between the cells joined is within a selected tolerance.

9. The method of claim 1, wherein processing the array of pixel representations comprises:

partitioning the array of pixel representations to generate a two-dimensional array of cells, each cell comprising a connected region of the image;

determining a plurality of visual characteristics of each cell;

generating a plurality of intervals and determining a plurality of visual characteristics for each interval, each interval generated by joining cells connected along a first axial direction that have determined visual characteristics that vary spatially within a first respective tolerance; and

determining at least one spot associated with the image, each spot determined by joining intervals connected along a second axial direction that have visual characteristics that vary within a second respective tolerance.

10. The method of claim 1, wherein processing the array of pixel representations comprises:

a) partitioning the array of pixel representations to generate an array of cells, each cell comprising a connected region of the image, the array having first and second axial directions;

b) determining a plurality of visual characteristics of each cell;

c) generating an interval having a plurality of visual characteristics by joining cells connected along the first axial direction that have determined visual characteristics which perceptually differ from the visual characteristics of the interval by at most a first tolerance;

d) repeating step b) to generate a plurality of intervals; and

e) determining a spot having a plurality of visual characteristics by joining intervals connected along the second axial direction that have determined visual characteristics which perceptually differ from the visual characteristics of the spot by at most a second tolerance.

11. A method of generating a plurality of spots associated with an image, a spot comprising a connected region of the image and having substantially similar visual characteristics, the method comprising:

the steps of

receiving an array of pixel representations;

partitioning the array of pixel representations to generate an array of cells, the array have first and second axial directions, each cell comprising a like-sized connected region of the image;

determining a plurality of visual characteristics of each cell;

joining cells connected along the first axial direction to form a plurality of disjoint intervals, each interval having visual characteristics that vary by at most a first tolerance; and

joining intervals connected along the second axial direction to form at least one spot, each spot having visual characteristics that vary by at most a second tolerance.

12. The method of claim 11, wherein the first tolerance is represented as a degree of perceptual variation.

13. The method of claim 11, wherein the second tolerance is represented as a degree of perceptual variation.

14. The method of claim 11, wherein the steps are performed by a programmable processor functionally coupled with a memory unit in response to a program stored in the memory unit.

15. The method of claim 11 wherein the steps are performed by a processing unit in response to a program embedded in the processing unit.

16. The method of claim 11, wherein the steps are performed by an embedded system.

17. The method of claim 11, wherein the cells are rectangular.

18. The method of claim 11, wherein each cell is square.

19. The method of claim 11, wherein the cells are hexagonal.

20. A method of generating a description of the shape of a region in a digital image, the method comprising the steps of:

generating an approximation of the shape of the region, said approximation comprising a plurality of connected like-sized cells that intersect the region;

generating a sequence of coordinates along a boundary curve of the approximation;

transforming the sequence of coordinates to a spectral domain; and

processing a plurality of lower frequency spectral coefficients of the transformed sequence to generate the description of the region.

21. The method of claim 20, wherein the processing step comprises determining an amplitude of each of the plurality of lower frequency spectral coefficients and using the determined amplitudes as the description of the region.

22. A computer readable medium carrying instructions executable by a computer to perform a method of indexing images according to visual characteristics of the images, the method comprising the steps of:

receiving an array of pixel representations that represent an image;

processing the array of pixel representations to determine a plurality of spots associated with the image, each spot comprising a connected region of the image having selected visual characteristics that vary spatially within a selected tolerance;

generating a plurality of spot descriptors, each spot descriptor indicating the visual characteristics of a respective spot; and

using the plurality of spot descriptors as an index entry for the image.

23. A computer readable medium carrying instructions executable by a computer to perform a method of generating a plurality of spots associated with an image, each spot comprising a connected region of the image having substantially uniform visual characteristics, the method comprising the steps of:

receiving an array of pixel representations;

partitioning the array of pixel representations to generate an array of cells, the array having first and second axial directions, each cell comprising a like-sized connected region of the image;

determining a plurality of visual characteristics of each cell;

joining cells connected along the first axial direction to form a plurality of disjoint intervals, each interval having visual characteristics that vary spatially by at most a first tolerance; and

joining intervals connected along the second axial direction to form at least one spot, each spot having visual characteristics that vary spatially by at most a second tolerance.

24. A computer readable medium carrying instructions executable by a computer to perform a method of generating a description of a shape of a region in a digital image, the method comprising the steps of:

generating an approximation of the shape of the region, said approximation comprising a plurality of connected like-sized cells that intersect the region;

generating a sequence of coordinates along a boundary curve of the approximation;

transforming the sequence of coordinates to a spectral domain; and

processing a plurality of lower frequency spectral coefficients of the transformed sequence to generate the description of the region.