Perceptual similarity image retrieval method

• US 6,563,959 B1
• Filed: 07/30/1999
• Issued: 05/13/2003
• 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): Patel, Jayanti K.
• Assistant Examiner(s): Kassa, Yosef
• Application Number:
  US09/364,302
• Time in Patent Office: 1,383 Days
• Field of Search: 382/306, 382/305, 382/282, 382/280, 382/250, 382/220, 382/209, 382/208, 382/201, 382/195, 382/190, 382/172, 382/165, 382/164, 382/162, 345/605, 345/604, 345/597, 345/593, 345/591, 345/589, 358/538, 358/527, 358/515, 707/7, 707/6, 707/4, 707/3, 707/1
• US Class Current: 382/282
• 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

Abstract

Method of effective search and retrieval through large collections of images is presented. Search criteria are based on perceptual similarity of images. Method is capable to process such images as bitonal, gray-scale and colorful, either of artificial or “real” world origin. Continuos-tone “real scene” images such as digitized still pictures and video frames are the primary objects of interest. Search operation starts from creating of an index out of a query image. Next, the index is to be applied as a key for searching through the index database. Index creation is a multi-step procedure, wherein the essential stages are: dissection of an image into areas of free shapes (spots) and computation of certain properties for each one. The properties are shape, color and relative position within the whole image. Spot shape is stored as derivatives of coefficients of DFT applied to a spot perimeter trace. Thus, every spot is represented by a set of numerical values (spot descriptor). Each image is represented in the database by plurality of its spot descriptors. A metric to compare spots in terms of their perceptual similarity is provided. Search results are presented as a scored list of relevant images where the score is based on their perceptual similarity to a query image.

Claims

1. A method for characterizing a digital image represented by an array of pixels, comprising

dividing the pixel array into a plurality of cells, each cell comprising a plurality of pixels,

calculating properties of individual cells,

joining neighboring cells into a plurality of spots based on the similarity of cell properties said cell properties including color characteristics and position within the image, and

calculating properties of spots to provide a set of spot descriptors for respective spots including determining shape and color characterisics of spots and their relative position within the image, whereby the resulting sets of spot descriptors characterize the digital image.

2. A method according to claim 1 wherein each cell comprises substantially the same number of pixels.

3. A method according to claim 1 wherein calculating properties of individual cells includes determining the color characteristics of cells.

4. A method according to claim 3 wherein the color characteristics of cells are determined in a perceptually uniform color space.

5. A method according to claim 1 wherein calculating properties of individual cells includes determining the probability of contours crossing cells.

6. A method According to claim 5 wherein determining the probability of contours crossing cells includes applying a Discrete Frequency Transform to data representing cells.

7. A method according to claim 5 wherein calculating properties of individual cells further includes determining the color characteristics of cells.

8. A method according to claim 1 wherein joining neighboring cells includes an iterative process that applies a plurality of different similarity thresholds.

9. A method according to claim 1 wherein the cell properties used as a basis for joining neighboring cells into a plurality of spots further includes the probability of a contour crossing a cell.

10. A method according to claim 1 wherein the properties of spots calculated to provide a set of spot descriptors for respective spots further includes determining the shape of spots.

11. A method according to claim 10 wherein spot shapes are represented by amplitudes of coefficients of Discrete Fourier Transformations applied to spot perimeters.

12. A method according to claim 11 wherein the coefficient amplitudes are normalized.

13. A method according to claim 1 wherein spot shapes are represented by amplitudes of coefficients of Discrete Fourier Transformations applied to spot perimeters.

14. A method according to claim 13 wherein the coefficient amplitudes are normalized.

15. A method according to claim 1 further comprising transforming the pixel array into a perceptually uniform color space before dividing the pixel array into a plurality of cells.