Fast image retrieval using multi-scale edge representation of images

• US 6,072,904 A
• Filed: 12/31/1997
• Issued: 06/06/2000
• Est. Priority Date: 12/31/1997
• Status: Expired due to Fees

• Current Assignee: Philips Electronics North America Corporation (Koninklijke Philips N.V.)
• Original Assignee: Philips Electronics North America Corporation (Koninklijke Philips N.V.)
• Inventors: Desai, Ranjit, Abdel-Mottaleb, Mohamed
• Primary Examiner(s): Tran, Phuoc
• Assistant Examiner(s): Mariam, Daniel G.
• Application Number:
  US09/002,097
• Time in Patent Office: 888 Days
• Field of Search: 382/141, 382/168, 382/203, 382/204, 382/224, 382/225, 382/217, 382/279, 382/305, 358/403, 358/404, 707/1, 707/3, 707/102, 707/103, 707/104
• US Class Current: 382/225
• CPC Class Codes: G06F 16/5854 using shape and object relationship
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing

Abstract

An image retrieval system for retrieving images from a data base in dependence upon the degree of correspondence with a user-input target image. The target image and each image in the data base are characterized by a vector of edge characteristics within each image. Retrieval is effected by a comparison of the characteristic vectors, rather than a comparison of the images themselves. To optimize performance, a set of characteristic vectors, at different levels of abstraction of the image, are associated with each data base image; images which are similar to the target image, at any level of abstraction, are retrieved. To further optimize the speed of search, the data base is partitioned into clusters, and the search is limited to the cluster most similar to the target image.

Claims

1. An image retrieval system for retrieving one or more data base images from a data base, said image retrieval system comprising:

a means for creating a characteristic vector associated with an image,

said means for creating the characteristic vector comprising;

a means for detecting edges within the image,

a means for characterizing the detected edges,

a means for partitioning the image into a plurality of blocks,

a means for characterizing the blocks in dependence upon the characterization of the detected edges within each block of the image, and

wherein said characteristic vector is a composite of the characterizations of the blocks comprising the image,

a means for providing each data base image to said characteristic vector creation means to create a data base characterization vector associated with each data base image,

a means for providing a target image to said characteristic vector creation means to create a target characterization vector associated with the target image, and

a means for selecting one or more of said data base images in dependence upon a comparison of the target characteristic vector with the data base characteristic vector associated with each of said one or more data base images.

3. An image retrieval system as claimed in claim 1, further comprising:

a means for determining a degree of similarity between characteristic vectors,

a means for partitioning the data base images into groups, in dependence upon the degree of similarity among the data base images, and

a means for creating a group characteristic vector associated with each group, in dependence upon the data base characteristic vectors associated with the data base images within each group,

wherein said means for selecting one or more of said data base images is further dependent upon the degree of similarity between the target characteristic vector and the group characteristic vectors.

5. An image retrieval system as claimed in claim 1, wherein

said means for characterizing the detected edges comprises a means for determining an orientation of each of the detected edges, and

said means for characterizing the blocks comprises a means for creating a histogram of the orientations of each of the detected edges within each block.

7. An image retrieval system as claimed in claim 3, wherein

said means of characterizing the detected edges comprises a means for determining an orientation of each of the detected edges, and

said means for characterizing the blocks comprises a means for creating a histogram of the orientations of each of the detected edges within each block.

9. An image retrieval system as claimed in claim 7, wherein

said means for determining the degree of similarity between characteristic vectors comprises the computation of the Euclidean distance between the characteristic vectors.

11. An image retrieval system as claimed in claim 3, wherein

said means for partitioning the data base images comprises a means for K-means clustering.

13. An image retrieval system as claimed in claim 9, wherein

said means for partitioning the data base images comprises a means for K-means clustering.

2. An image retrieval system for retrieving one or more data base images from a data base, said image retrieval system comprising:

a means for creating a characteristic vector associated with an image,

said means for creating the characteristic vector comprising;

a means for detecting edges within the image, and

a means for characterizing the detected edges,

a means for providing a target image to said characteristic vector creation means to create a target characterization vector associated with the target image,

a means for selecting one or more of said data base images in dependence upon a comparison of the target characteristic vector with the data base characteristic vector associated with each of said one or more data base images,

a means for creating a set of at least two abstract images associated with each of said one or more data base images, each of the abstract images being at a different level of abstraction,

a means for providing each abstract image to said characteristic vector creation means to create a set of abstract characterization vectors associated with each of said one or more data base image, and

a means for selecting the one or more data base images dependent upon a comparison of the target characteristic vector with the set of abstract characteristic vectors associated with each of said one or more data base images.

4. An image retrieval system as claimed in claim 2, further comprising:

a means for determining a degree of similarity between characteristic vectors,

a means for partitioning the data base images into a set of groups, in dependence upon the degree of similarity among the abstract characterization vectors of each set of abstract characterization vectors, and

a means for creating a set of group characteristic vectors associated with each group, in dependence upon the abstract characteristic vectors associated with the data base images within each group,

wherein said means for selecting one or more of said data base images is further dependent upon the degree of similarity between the target characteristic vector and the set of group characteristic vectors.

6. An image retrieval system as claimed in claim 2, wherein

said means for characterizing the detected edges comprises a means for determining an orientation of each of the detected edges, and

said means for characterizing the blocks comprises a means for creating a histogram of the orientations of each of the detected edges within each block.

8. An image retrieval system as claimed in claim 4, wherein

said means for characterizing the detected edges comprises a means for determining an orientation of each of the detected edges, and

said means for characterizing the blocks comprises a means for creating a histogram of the orientations of each of the detected edges within each block.

10. An image retrieval system as claimed in claim 8, wherein

said means of determining the degree of similarity between characteristics vectors comprises the computation of the Euclidean distance between the characteristic vectors.

12. An image retrieval system as claimed in claim 4, wherein

said means for partitioning the data base images comprises a means for K-means clustering.

14. An image retrieval system as claimed in claim 10, wherein

said means for partitioning the data base images comprises a means for K-means clustering.

15. An image retrieval system as claimed in claim 2, wherein

said means for creating each abstract image comprises a means for convoluting the data base image with a Gaussian kernel of a specified width.

16. An image retrieval system as claimed in claim 4, wherein

said means for creating each abstract image comprises a means for convoluting the data base image with a Gaussian kernel of a specified width.

17. An image retrieval system as claimed in claim 6, wherein

said means for creating each abstract image comprises a means for convoluting the data base image with a Gaussian kernel of a specified width.

18. An image retrieval system as claimed in claim 8, wherein

said means for creating each abstract image comprises a means for convoluting the data base image with a Gaussian kernel of a specified width.

19. An image retrieval system as claimed in claim 8, wherein

the set of abstract images associated with each data base image comprise at least two abstract images, each at a different level of abstraction;

each image is partitioned into 256 blocks; and

the orientation of each edge is one of horizontal, vertical, left-diagonal, and right-diagonal.

20. An image retrieval system as claimed in claim 19, wherein

said means for creating each of the at least two abstract images comprise a means for convoluting the data base image with Gaussian kernels of differing widths.

21. A method for image characterization comprising:

creating a characteristic vector associated with an image, said characteristic vector creation comprising;

detecting edges within the image, characterizing the detected edges partitioning each image of a plurality of images into a plurality of blocks, detecting edges within each block of the plurality of blocks of each image, characterizing the detected edges within each block to form a characterization of the detected edges within each block,

characterizing each block based on the characterization of the detected edges within each block, and

composing an image characteristic vector corresponding to each image of the plurality of images based on the characterization of edges within each block of the plurality of blocks of each image.

22. The method of claim 21, further including:

partitioning a target image into a plurality of target image blocks,

characterizing each target image block of the plurality of target image blocks based on a characterization of edges within each target image block,

composing a target characteristic vector corresponding to the target image, based on the characterization of edges within each target image block of the plurality of target image blocks to form a target characteristic vector corresponding to the target image, and

comparing the target characteristic vector to the plurality of image characteristic vectors to facilitate an identification of at least one image of the plurality of images that are similar to the target image.

23. The method of claim 21, wherein the step of characterizing each block based on a characterization of edges within each block includes:

determining an orientation of each of the edges, and

creating a histogram of the orientations of each of the edges within each block.

24. The method of claim 21, further including:

creating a set of abstract images associated with each image of the plurality of images, each abstract image of the set of abstract images having a different level of abstraction,

partitioning each abstract image into a plurality of abstract blocks,

characterizing each abstract block of the plurality of abstract blocks of each abstract image of the set of abstract images based on a characterization of edges within each abstract block,

composing an abstract characteristic vector corresponding to each abstract image of the set of abstract images of the plurality of images, based on the characterization of edges within each abstract block of the plurality of abstract blocks of each abstract image to form a set of abstract characteristic vectors corresponding to each image of the plurality of images.

25. The method of claim 24, further including:

forming a plurality of clusters of images based on a first abstract characteristic of the set of abstract characteristic vectors corresponding to each image of the plurality of images, and

composing a plurality of cluster characteristic vectors corresponding to each cluster of the plurality of clusters, based on the first abstract characteristic vector corresponding to each image in each cluster of the plurality of cluster of images.

26. The method of claim 25, further including:

partitioning a target image into a plurality of target image blocks,

characterizing each target image block of the plurality of target image blocks based on a characterization of edges within each target image block,

composing a target characteristic vector corresponding to the target image, based on the characterization of edges within each target image block of the plurality of target image blocks to form a target characteristic vector corresponding to the target image, and

comparing the target characteristic vector to each cluster characteristic vector of the plurality of cluster characteristic vectors to facilitate an identification of at least one cluster of the plurality of clusters containing images that are similar to the target image.

27. A method for image characterization comprising:

detecting edges within each image of a plurality of images, characterizing the detected edges within each image to form a characterization of the detected edges within each image, creating a characteristic vector associated with each image based on the characterization of the detected edges creating a plurality of abstract images associated with each image of the plurality of images, each abstract image of the plurality of abstract images being at a different level of abstraction,

characterizing each abstract image of the plurality of abstract images based on a further characterization of the detected edges within the image to form an abstract characteristic vector corresponding to each different level of abstraction, thereby forming a set of abstract characteristic vectors associated with each image.