Region-based image archiving and retrieving system

• US 6,502,105 B1
• Filed: 01/15/1999
• Issued: 12/31/2002
• Est. Priority Date: 01/15/1999
• Status: Expired due to Term

• Current Assignee: Uniloc 2017 LLC (FIG LLC (d/b/a Fortress Investment Group LLC))
• Original Assignee: Koninklijke Philips Electronics N.V. (Koninklijke Philips N.V.)
• Inventors: Challapali, Kiran, Caron, Cedric Y., Yan, Yong
• Primary Examiner(s): Kindred, Alford W.
• Application Number:
  US09/232,896
• Time in Patent Office: 1,446 Days
• Field of Search: 707/1-104, 707/200-205, 707/500, 707/526, 707/515, 345/348, 345/326-355, 345/621, 345/625, 345/440, 382/180
• US Class Current: 1/1
• CPC Class Codes: G06F 16/5854 using shape and object relationship
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing
• CPC Class Codes: Y10S 707/99948 Application of database or data structure, e.g. distributed, multimedia, or image

Abstract

The system disclosed herein builds a database of image-related data by inputting a plurality of images, and for each image: dividing the image into N₁ (N₁≧1) regions which are substantially homogenous with respect to at least one attribute of the image, generating a graph based on M₁ (M₁≧1) of the N₁ regions, and storing data for the graph in the database. The database may then be used to determine whether a query image is similar to one or more of the plurality of images. To this end, the system inputs the query image, and divides the query image into N₂ (N₂≧1) regions which are substantially homogenous with respect to at least one attribute of the query image. The system then generates a graph based on M₂ (M₂≧1) of the N₂ regions, and compares the generated graph to other graphs in the database that correspond to the plurality of images. Thereafter, an image is retrieved from memory that has a graph that is substantially similar to the generated graph.

Claims

1. A method of building a database of image-related data, the method comprising the steps of:

inputting a plurality of images; and

for each image;

dividing the image into N (N≧

1) regions which are substantially homogenous with respect to at least one attribute of the image;

generating a graph based on M (M≧

1) of the regions; and

storing data for the graph in the database by forming groups of images primarily based on graphs of the images and storing the groups of images into sub-databases, wherein the forming step forms the groups based on images having graphs with at least a predetermined number of similarities.

2. A method according to claim 1, wherein the inputting step comprises the steps of:

inputting frames of video data; and

extracting key frames from the video data;

wherein the dividing, generating and storing steps are performed for each extracted key frame of video.

3. A method according to claim 1, wherein the at least one attribute comprises textures and/or colors in the image.

4. A method according to claim 1, further comprising, between the generating and storing steps, the step of assigning labels to regions of the graph based on contents of the regions.

5. A method according to claim 4, wherein the assigning step assigns at least one region in the graph a label based on its position in a color space.

6. A method accordingly to claim 1, wherein the step of dividing the image into N (N≧

1) regions comprises dividing the image into N (N≧

1) regions which are substantially homogenous with respect to at least two attributes of the image.

7. A method of using graphs corresponding to a plurality of images as a primary type of interest to determine whether a query image is similar to one or more of the plurality of images, the method comprising the steps of:

inputting the query image;

dividing the query image into N (N≧

1) regions which are substantially homogenous with respect to at least one attribute of the query image;

generating a graph based on M (M≧

1) of the regions; and

comparing the generated graph to other graphs that correspond to the plurality of images.

8. A method according to claim 7, further comprising the step of retrieving an image from memory that has a graph that is substantially similar to the generated graph.

9. A method according to claim 7, wherein the inputting step comprises the steps of:

inputting frames of video; and

extracting a key frame from the video, the query image corresponding to at least part of the key frame.

10. A method according to claim 7, further comprising, between the generating and comparing steps, the step of assigning labels to regions of the generated graph based on contents of the regions;

wherein the comparing step determines which, if any, regions of the generated graph to compare to the other graphs based on the labels assigned to the generated graph and labels included on the other graphs.

11. A method according to claim 7, further comprising the step of pruning the generated graph prior to comparing it to the other graphs;

wherein pruning comprises removing at least one of vertices, labels and edges from the generated graph.

12. A method according to claim 11, wherein the pruning step removes vertices, labels and/or edges from the generated graph that correspond to homogeneous image regions having a predetermined attribute.

13. Computer-executable process steps stored on a computer-readable medium, the computer-executable process steps to build a database of image-related data, the computer-executable process steps comprising:

code to input a plurality of images; and

code, for each image, (i) to divide the image into N (N≧

1) regions which are substantially homogenous with respect to at least one attribute of the image, (ii) to generate a graph based on M (M≧

1) of the regions, and (iii) to store data for the graph in the database by forming groups of images primarily based on graphs of the images and storing the groups of images into sub-databases, wherein the code for forming the groups of images forms the groups based on images having graphs with at least a predetermined number of similarities.

14. Computer-executable process steps according to claim 13, wherein the inputting code comprises:

code to input frames of video data; and

code to extract key frames from the video data;

wherein the dividing, generating and storing code is executed for each extracted key frame of video.

15. Computer-executable process steps according to claim 13, wherein the at least one attribute comprises textures and/or colors in the image.

16. Computer-executable process steps according to claim 13, further comprising code to assign labels to regions of the graph based on contents of the regions.

17. Computer-executable process steps according to claim 16, wherein the assigning code assigns at least one region in the graph a label based on its position in a color space.

18. Computer-executable process steps according to claim 13, wherein the storing code comprises:

code to form groups of images based on graphs of the images; and

code to store the groups of images into sub-databases.

19. Computer-executable process steps according to claim 17, wherein the forming code forms the groups based on images having graphs with at least a predetermined number of similarities.

20. Computer-executable process steps stored on a computer-readable medium, the computer executable process steps using graphs corresponding to a plurality of images to determine whether a query image is similar to one or more of the plurality of images, the computer-executable process steps comprising:

code to input the query image;

code to divide the query image into N (N≧

1) regions which are substantially homogenous with respect to at least one attribute of the query image;

code to generate a graph based on M (M≧

1) of the regions; and

code to primarily compare the generated graph to other graphs that correspond to the plurality of images.

21. Computer-executable process steps according to claim 20, further comprising code to retrieve an image from memory that has a graph that is substantially similar to the generated graph.

22. Computer-executable process steps according to claim 20, wherein the inputting code comprises:

code to input frames of video; and

code to extract a key frame from the video, the query image corresponding to at least part of the key frame.

23. Computer-executable process steps according to claim 20, further comprising code to assign labels to regions of the generated graph based on contents of the regions;

wherein the comparing code determines which, if any, regions of the generated graph to compare to the other graphs based on the labels assigned to the generated graph and labels included on the other graphs.

24. Computer-executable process steps according to claim 20, further comprising code to prune the generated graph prior to comparing it to the other graphs;

wherein pruning comprises removing at least one of vertices, labels and edges from the generated graph.

25. Computer-executable process steps according to claim 24, wherein the pruning code removes vertices, labels and/or edges from the generated graph that correspond to homogeneous image regions having a predetermined attribute.

26. An apparatus for building a database of image-related data, the apparatus comprising:

a memory which stores computer-executable process steps; and

a processor which executes the process steps so as to input a plurality of images, and for each image;

(i) to divide the image into N (N≧

1) regions which are substantially homogenous with respect to at least one attribute of the image, (ii) to generate a graph based on M (M≧

1) of the regions, and (iii) to store data for the graph in the database by forming groups of images primarily based on graphs of the images and storing the groups of images into sub-databases, wherein the forming groups of images forms the groups based on images having graphs with at least a predetermined number of similarities.

27. An apparatus according to claim 26, wherein the processor inputs the plurality of images by (i) inputting frames of video data, and (ii) extracting key frames from the video data, wherein the dividing, generating and storing steps are performed for each extracted key frame of video.

28. An apparatus according to claim 26, wherein the at least one attribute comprises textures and/or colors in the image.

29. An apparatus according to claim 26, wherein the processor, between the generating and storing steps, executes process steps to assign labels to regions of the graph based on contents of the regions.

30. An apparatus according to claim 29, wherein the assigning step assigns at least one region in the graph a label based on its position in a color space.

31. An apparatus according to claim 26, wherein the processor stores the data by (i) forming groups of images based on graphs of the images, and (ii) storing the groups of images into sub-databases.

32. An apparatus according to claim 31, wherein the forming step forms the groups based on images having graphs with at least a predetermined number of similarities.

33. An apparatus for using graphs corresponding to a plurality of images as a primary type of interest to determine whether a query image is similar to one or more of the plurality of images, the apparatus comprising:

a memory which stores computer-executable process steps; and

a processor which executes the process steps so as (i) to input the query image, (ii) to divide the query image into N (N≧

1) regions which are substantially homogenous with respect to at least one attribute of the query image, (iii) to generate a graph based on M (M≧

1) of the regions, and (iv) to compare the generated graph to other graphs that correspond to the plurality of images.

34. An apparatus according to claim 33, wherein the processor further executes process steps to retrieve an image from memory that has a graph that is substantially similar to the generated graph.

35. An apparatus according to claim 33, wherein the processor inputs the query image by (i) inputting frames of videos and (ii) extracting a key frame from the video, the query image corresponding to at least part of the key frame.

36. An apparatus according to claim 33, wherein the processor executes, between the generating and comparing steps, process steps to assign labels to regions of the generated graph based on contents of the regions;

wherein the comparing step determines which, if any, regions of the generated graph to compare to the other graphs based on the labels assigned to the generated graph and labels included on the other graphs.

37. An apparatus according to claim 33, wherein the processor executes process steps so as to prune the generated graph prior to comparing it to the other graphs;

wherein pruning comprises removing at least one of vertices, labels and edges from the generated graph.

38. An apparatus according to claim 37, wherein the pruning step removes vertices, labels and/or edges from the generated graph that correspond to homogeneous image regions having a predetermined attribute.