Method for computerized indexing and retrieval of digital images based on spatial color distribution

• US 6,594,386 B1
• Filed: 04/22/1999
• Issued: 07/15/2003
• Est. Priority Date: 04/22/1999
• Status: Expired due to Fees

• Current Assignee: Forouzan Golshani, Youngchoon Park
• Original Assignee: Forouzan Golshani, Youngchoon Park
• Inventors: Park, Youngchoon, Golshani, Forouzan
• Primary Examiner(s): Patel, Jayanti K.
• Application Number:
  US09/296,228
• Time in Patent Office: 1,545 Days
• Field of Search: 382/100, 382/103, 382/166-167, 382/171, 382/209, 382/232-239, 382/253-254, 382/304-306, 341/67, 341/51, 345/440, 348/384.1, 348/718, 348/726-728, 348/760, 358/426, 358/432, 358/450, 358/515, 358/517, 358/518, 708/203, 708/402
• US Class Current: 382/166
• CPC Class Codes: G06F 16/5838 using colour
• CPC Class Codes: G06F 16/5854 using shape and object relationship
• CPC Class Codes: G06F 16/5862 using texture

Abstract

In the context of image database systems, a method for indexing and retrieval of images by their color content and the spatial distribution of color is disclosed. The method is implemented as a software tool that runs on a personal computer and enables the computer to find a desired image from an image database. The user interface allows the user to describe the desired image, and the tool searches the repository for any images that satisfy the description. The description of the composite image may include information on shapes, texture, presence or absence of objects, and color. The process of search and retrieval of images makes use of a method that determines whether a specific color, or a combination of colors, is present in an image. Further, the method determines the location where the specific color or color combination can be found. By analyzing the results of comparisons between the features found in the composite image and in the stored images, the tool retrieves those images that satisfy the description of the query, image. Calculation of color-related features makes significant use of the calculations that are made in the process of image compression which is an essential step prior to image storage. The process of search and retrieval on the basis of features relating to color are provided via a library of routines that perform the necessary tasks.

Claims

1. A method by which a computer system comprising:

a) a repository of color images

b) an input channel for importing color images, and

c) a computer terminal for user interaction, for extracting color information and spatial color distribution information from a given color image, storing the said image in the image repository and indexing the color related information for future retrieval, comprising the steps of;

(a) receiving the given image;

(b) breaking the image into blocks of 8×

8 pixels;

(c) compressing each block into a standard format known as JPEG and extracting key coefficients DC and AC values;

(d) repeatedly comparing the DC values of the adjacent blocks to determine whether regions of similar intensity can be formed;

(e) indexing the information on color and its spatial distribution; and

(f) storing the image, its features, and the extracted color information in the image repository.

2. The method of claim 1 when the image is in any format including TIFF, GIF, PCX, TGA, BMP and JPEG2, each of which is a different way of encoding images.

3. A software tool for storage and retrieval of images that incorporates the method of claim 2 by implementing a library of software routines that execute the said method.

4. The method of claim 1 in which the input is heterogeneous information on a desired target image presented to the computer system through the visual interface providing windows for textual information, color information, sketches and texture information, and the output is a ordered list of images that satisfy the given criteria, comprising the steps of:

(a)receiving information from any of the user interface windows designated for inputting;

textual information color, position of color, shape, and texture;

(b)creating a composite image representing all of the information obtained from the user interface windows listed in 3(a);

(c)breaking the composite image obtained in 3(b) into blocks of 8×

8 pixels;

(d)compressing each block into a standard format known as JPEG and extracting key coefficients DC and AC values;

(e)repeatedly comparing the DC values of the adjacent blocks to form regions of similar intensity;

(f)indexing the information on color and its spatial distribution;

(g)comparing the images contained in the image repository and their attributes and indexes with the composite image, its attributes and indexes in order to find complete or partial match;

(h)ranking the results obtained in step 3(g) in the order of closeness to the composite image obtained in 3(b); and

(i)displaying the images in the order of ranking on a window of the user interface.

5. The method of claim 4 in which other information including date and author may be also provided through a window of the user interface.

6. A software tool for storage and retrieval of images that incorporates the method of claim 5 by implementing a library of software routines that execute the said method.

7. The method of claim 4 in which a message indicating that there are no possible matching images in the image repository is displayed on a window of the user interface when the step 3(g) does not find a complete or partial match for the composite image.

8. A software tool for storage and retrieval of images that incorporates the method of claim 7 by implementing a library of software routines that execute the said method.

9. A software tool for storage and retrieval of images that incorporates the method of claim 4 by implementing a library of software routines that execute the said method.

10. A software tool for storage and retrieval of images that incorporates the method of claim 1 by implementing a library of software routines that execute the said method.

11. A method by which a computer system comprising:

a) repository of color images

b) an input channel for importing color images, and

c) a computer terminal for user interaction, for extracting color information and spatial color distribution information from a given color image, storing the said image in the image repository and indexing the color related information for future retrieval, comprising the steps of;

(a) receiving the given image;

(b) compressing each block into a standard format known as JPEG and extracting key coefficients DC and AC values;

(c) repeatedly comparing the DC values of the adjacent blocks to determine whether regions of similar intensity can be formed;

(d) indexing information on color and its spatial distribution; and

(e) storing the image, its features, and the extracted color information in the image repository.

12. The method of claim 11 in which the input is heterogeneous information on a desired target image presented to the computer system through the visual interface providing windows for textual information, color information, sketches and texture information, and the output is a ordered list of images that satisfy the given criteria, comprising the steps of:

(a) receiving information from any of the user interface windows designated for inputting data selected from the following group;

textual information, color, position of color, shape, or texture;

(b) creating a composite image representing all of the information obtained from the user interface windows listed in 12(a);

(c) indexing information on color and its spatial distribution; and

(d) comparing the images contained in the image repository and their attributes and indexes with the composite image, its attributes and indexes in order to find complete or partial match.

13. The method of claim 11 comprising the further steps of:

(a) compressing the composite image created in step 12(b) into a standard format known as JPEG and extracting key coefficients DC and AC values; and

(b) prior to indexing said information on color and its spatial distribution, repeatedly comparing the DC values of the adjacent blocks to form regions of similar intensity.

14. The method of claim 13 comprising the further steps of:

(a) ranking the results obtained in step 12(d) in the order of closeness to the composite image obtained in 12(b); and

(b) displaying the images on a window of the user interface.