Method for representing and comparing digital images

• US 20020146176A1
• Filed: 04/09/2001
• Published: 10/10/2002
• Est. Priority Date: 04/09/2001
• Status: Active Grant

• Current Assignee: Gary Elliott Meyers
• Original Assignee: Gary Elliott Meyers
• Inventors: Meyers, Gary Elliott
• Granted Patent: US 6,690,828 B2
• Time in Patent Office: Days
• US Class Current: 382/218
• CPC Class Codes: G06T 2207/20021 Dividing image into blocks, subimages or windows
• CPC Class Codes: G06T 7/90 Determination of colour characteristics
• CPC Class Codes: G06V 10/40 Extraction of image or video features

Abstract

A method of generating a compact representation of a digital image is described, A digital image is converted to a square bitmap and divided into a plurality of cells. Each cell is subdivided into a plurality of regions. A minimum intensity region and a maximum intensity region in each cell are identified in each set of the plurality of cells. Cell representation data is generated for each cell in each set of cells based on the positions of the minimum intensity region and the maximum intensity region in the cell. Combining all of the cell representation data in each set of cells for the image creates a compact representation of the original digital image.

A method of comparing cell representation data is also described. Cell representation data for a collection of source images is organized into a database. A search of the database identifies candidate images that are at least minimally similar to a target image. The target image is then compared directly to each identified candidate image and a similarity score for each candidate image is calculated and recorded.

Claims

1. A method of generating a compact representation of a digital image, the method comprising:

dividing the digital image into a plurality of cells;

identifying a minimum intensity region in each cell in each set of the plurality of cells;

identifying a maximum intensity region in each cell in each set of the plurality of cells;

generating cell representation data for each cell in each set of cells based on the positions of the minimum intensity region and the maximum intensity region in that cell; and

generating a representation of the digital image, the representation including the cell representation data.

2. The method of claim 1, and further comprising converting the original digital image to a square bitmap prior to dividing the digital image into a plurality of cells.

3. The method of claim 1, and further comprising subdividing each cell into a plurality of regions.

4. The method of claim 3, and further comprising calculating a pixel intensity sum for each region, the pixel intensity sum for each region representing the sum of the intensities of the pixels contained in that region.

5. The method of claim 4, wherein the minimum and maximum intensity regions are identified based on the calculated pixel intensity sums.

6. The method of claim 1, and further comprising identifying cells that have low contrast, and associating a low contrast identifier with each identified cell.

7. The method of claim 6, wherein upon detection of an image having a predominance of low contrast cells, the image'"'"'s contrast is dynamically increased and its cell representation data is recalculated.

8. The method of claim 6, wherein the low contrast identifier is a negative integer.

9. The method of claim 6, wherein the representation of the digital image includes the cell representation data.

10. The method of claim 1, wherein the intensity angle for each cell is generated based on an angle between a horizontal reference line and a line formed between the cell'"'"'s minimum intensity region and its maximum intensity region.

11. The method of claim 10, wherein the cell representation data for each cell is an integer representing either the value of the intensity angle for the cell or the low contrast identifier.

13. The method of claim 12, wherein the representation of each of the first and the second digital images are generated by:

dividing the first and the second digital images into a plurality of cells;

identifying a minimum intensity region in each cell in each set of the plurality of cells;

identifying a maximum intensity region in each cell in each set of the plurality of cells;

generating cell representation data for each cell in each set of cells based on the positions of the minimum intensity region and the maximum intensity region in that cell; and

generating representations of the first and the second digital images, the representations including the cell representation data.

14. The method of claim 13, and further comprising converting each of the first and the second digital images to a square bitmap prior to dividing each of the first and the second digital images into a plurality of cells.

15. The method of claim 13, and further comprising subdividing each cell into a plurality of regions.

16. The method of claim 15, and further comprising calculating a pixel intensity sum for each region, the pixel intensity sum representing the sum of the intensities of the pixels contained in that region.

17. The method of claim 16, wherein the minimum and maximum intensity regions are identified based on the calculated pixel intensity sums.

18. The method of claim 13, and further comprising identifying cells that have low contrast, and associating a low contrast identifier with each identified cell.

19. The method of claim 18, wherein the representation of each of the first and the second digital images includes the cell representation data.

20. The method of claim 13, wherein the intensity angle for each cell is generated based on an angle between a reference line and a line formed between the cell'"'"'s minimum intensity region and its maximum intensity region.

21. The method of claim 20, wherein the cell representation data for each cell is an integer representing either the value of the intensity angle for the cell or the low contrast identifier.

12. A method of comparing a first and a second digital image and determining a degree of similarity of the compared images, the method comprising:

generating representations of the first and the second digital image based on the relative positions of minimum and maximum intensity regions within the images; and

comparing the representations of the first and the second digital images and generating a similarity score based on the comparison, the similarity score representing the degree of similarity between the images.

22. A method of identifying candidate images in a library of digital images that are similar to a digital target image and determining a degree of similarity of the candidate images to the target image, the method comprising:

dividing the digital target image and the digital source images in the library of digital images into a plurality of cells;

identifying a minimum intensity region in each cell of the digital target and source images in the library;

identifying a maximum intensity region in each cell of the digital target and source images in the library;

generating cell representation data for each cell in each digital target and source image in the library based on the positions of the minimum intensity region and the maximum intensity region in the respective cells of the respective digital source and target images;

generating a candidate image database that organizes the images according to the cell representation data of each source image;

searching the candidate image database to identify candidate images having at least one cell that is similar to the target image;

comparing the target image to each image from the candidate database identified as having at least one cell similar to the target image; and

calculating similarity scores for the digital images with which the target image was compared.

23. The method of claim 22 wherein the candidate database is organized into a plurality of angle index categories, the number of categories corresponding to a transposed count of the number of possible cell representation data values, each category being further subdivided into a series of arrays, the number of arrays corresponding in number up to the number of cells into which each digital image has been divided, the arrays containing identifiers of those images having a cell representation datum corresponding to the value assigned to the current angle index category in a cell corresponding to the array associated with the angle index category.

25. A method of claim 24 wherein the representation of the first and the second digital images is comprised of a plurality of intensity angles.

26. A method of claim 24 wherein the cell representation data from the first and the second digital images are compared on a cell by cell basis across a plurality of sets of cells.

27. The method of claim 25 and further comprising the step of transposing the plurality of intensity angles that comprise the representation of the target and the candidate digital images.

28. A method of claim 24 wherein the representation of each of the target and the candidate digital images is based on one or more image properties chosen from a list comprising intensity, color, hue, saturation, value, luminance, and chrominance.

30. The method of generating a compact representation of a digital image of claim 29 wherein the image data values are derived from one of a group comprising:

intensity, color, hue, saturation, value, luminance, and chrominance.

24. A method of identifying candidate images among a library of source images that are similar to a target image, the method comprising:

generating a representation of the target image and each of the source images based on the relative positions of a minimum and a maximum intensity region within the target and source images;

generating a candidate image list, each candidate image having at least a predetermined degree of similarity with the target image;

comparing the representations of the target image and the candidate images and generating a similarity score based on this comparison, the similarity score representing the degree of similarity of the digital images.

29. A method of generating a compact representation of a digital image, the method comprising:

dividing the digital image into a plurality of cells;

identifying a minimum image data value region in each cell in each set of the plurality of cells;

identifying a maximum image data value region in each cell in each set of the plurality of cells;

generating cell representation data for each cell in each set of cells based on the positions of the minimum image data value region and the maximum image data value region in that cell; and

generating a representation of the digital image, the representation including the cell representation data.