Automated image interpretation and retrieval system

• US 7,065,250 B1
• Filed: 09/15/1999
• Issued: 06/20/2006
• Est. Priority Date: 09/18/1998
• Status: Expired due to Fees

• Current Assignee: Canon Kabushiki Kaisha (Canon Inc.)
• Original Assignee: Canon Kabushiki Kaisha (Canon Inc.)
• Inventors: Lennon, Alison Joan
• Primary Examiner(s): Bali, Vikkram
• Application Number:
  US09/395,993
• Time in Patent Office: 2,470 Days
• Field of Search: 382/190, 382/199, 382/224, 382/225, 382/226, 382/229, 382/230, 382/266, 382/305, 382/306, 704/256, 707/103.R, 707/103.Y, 707/104.1, 707/500.1
• US Class Current: 382/224
• CPC Class Codes: G06V 10/426 Graphical representations
• CPC Class Codes: G06V 30/1988 Graph matching graphical image representation G06V30/18181

Abstract

A method of classifying a digital image is disclosed. The method provides a region adjacency graph (310) representing the digital image and analyses the region adjacency graph (310) for predetermined patterns. For each identified pattern a classification of the digital image is selected. The region adjacency graph (310) is classified as one of a number of stereotypes.

Claims

1. A method of classifying a digital image, said method comprising the steps of:

segmenting the digital image into a plurality of substantially homogeneous regions;

processing the plurality of regions to provide a region adjacency graph for the digital image, the region adjacency graph representing spatial adjacency between the plurality of regions of the digital image;

labeling at least one of the regions of the region adjacency graph with one of a plurality of predetermined semantic labels to provide a labeled region adjacency graph;

providing a set of plural predetermined patterns of semantic labels, wherein each predetermined pattern of semantic labels corresponds to one of plural stereotypes each representing a different classification of a digital image;

analyzing the labeled region adjacency graph to identify one or more of the plural predetermined patterns of semantic labels in the labeled region adjacency graph;

assigning corresponding ones of the plural stereotypes to the digital image in accordance with which of the plural predetermined patterns were identified in said analyzing step, such that the assigned stereotype describes the plurality of regions of the digital image and represents a classification of the digital image; and

storing the assigned stereotypes and the digital image in one or more databases of digital images, wherein the digital image is retrievable from the one or more databases using a search for the assigned stereotype.

2. The method according to claim 1, wherein identification of the predetermined pattern is based on a size of one or more regions of the digital image.

3. The method according to claim 1, wherein identification of the predetermined pattern is based on an adjacency of the regions.

4. The method according to claim 1, wherein identification of the predetermined pattern is based on semantic label content of the region adjacency graph.

5. The method according to claim 1, wherein identification of the predetermined pattern is based on a mean color of one or more regions of the digital image.

6. The method according to claim 1, wherein the plurality of stereotypes are stored in an association lookup table.

7. The method according to claim 1, wherein the stereotypes are represented in a hierarchical arrangement.

8. The method according to claim 1, wherein each of the stereotypes has a hierarchical path.

9. The method according to claim 1, wherein the region adjacency graph is provided by analyzing contextual data associated with one or more regions of the digital image.

10. The method according to claim 9, wherein the contextual data comprises information generated by one or more separate sources of the information.

11. The method according to claim 10, wherein a corresponding portion of the contextual data is obtained from a temporal region of interest for each source of the information.

12. The method according to claim 1, further comprising the step of providing metadata associated with the digital image, wherein the metadata includes the stereotypes of the digital image.

13. The method according to claim 12, wherein the metadata includes a hierarchical path associated with the respective stereotype of each digital image.

14. The method according to claim 13, wherein the hierarchical path is stored with a respective stereotype as a metadata object which is associated with a respective image object.

15. The method according to claim 13, wherein the hierarchical path is stored as a referenced lookup table.

16. An apparatus for classifying a digital image, said apparatus comprising:

segmenting means for segmenting the digital image into a plurality of substantially homogeneous regions;

processing means for processing the plurality of regions to provide a region adjacency graph for the digital image, the region adjacency graph representing spatial adjacencies between the plurality of regions of the digital image;

labeling means for labeling at least one of the regions of the region adjacency graph with one of a plurality of predetermined semantic labels to provide a labeled region adjacency graph;

pattern storage means for storing a set of plural predetermined patterns of semantic labels, wherein each predetermined pattern of semantic labels corresponds to one of plural stereotypes each representing a different classification of a digital image;

analyzing means for analyzing the labeled region adjacency graph to identify one or more of the plural predetermined patterns of semantic labels in the labeled region adjacency graph;

assigning means for assigning corresponding ones of the plural stereotypes to the digital image in accordance with which of the plural predetermined patterns were identified in said analyzing step, such that the assigned stereotype describes the plurality of regions of the digital image and represents a classification of the digital image; and

storage means for storing the assigned stereotypes and the digital image in one or more databases of digital images, wherein the digital image is retrievable from the one or more databases using a search for the assigned stereotypes.

17. The apparatus according to claim 16, wherein identification of the predetermined pattern is based on a size of one or more regions of the digital image.

18. The apparatus according to claim 16, wherein identification of the predetermined pattern is based on an adjacency of the regions.

19. The apparatus according to claim 16, wherein identification of the predetermined pattern is based on semantic label content of the region adjacency graph.

20. The apparatus according to claim 16, wherein identification of the predetermined pattern is based on a mean color of one or more regions of the digital image.

21. The apparatus according to claim 16, wherein the plurality of stereotypes are stored in an association lookup table.

22. The apparatus according to claim 16, wherein the stereotypes are represented in a hierarchical arrangement.

23. The apparatus according to claim 16, wherein each of the stereotypes has a hierarchical path.

24. The apparatus according to claim 16, wherein the region adjacency graph is provided by analyzing contextual data associated with one or more regions of the digital image.

25. The apparatus according to claim 24, wherein the contextual data comprises information generated by one or more separate sources of the information.

26. The apparatus according to claim 25, wherein a corresponding portion of the contextual data is obtained from a temporal region of interest for each source of the information.

27. The apparatus according to claim 16, further comprising metadata providing means for providing metadata associated with each digital image, wherein the metadata includes the stereotypes of each digital image.

28. The apparatus according to claim 27, wherein the metadata includes a hierarchical path associated with the respective stereotypes of each digital image.

29. The apparatus according to claim 28, wherein the hierarchical path is stored with a respective stereotype as a metadata object which is associated with a respective image object.

30. The apparatus according to claim 28, wherein the hierarchical path is stored as a referenced lookup table.

31. A computer program product comprising a computer readable medium having a computer program recorded for classifying a digital image, said computer program product comprising:

a segmenting module, for segmenting the digital image into a plurality of substantially homogeneous regions;

a processing module, for processing the plurality of regions to provide a region adjacency graph for the digital image, the region adjacency graph representing spatial adjacency between the plurality of regions of the digital image;

a labeling module, for labeling at least one of the regions of the region adjacency graph with one of a plurality of predetermined semantic labels to provide a labeled region adjacency graph;

a pattern storage module for storing a set of plural predetermined patterns of semantic labels, wherein each predetermined pattern of semantic labels corresponds to one of plural stereotypes each representing a different classification of a digital image;

an analyzing module, for analyzing the labeled region adjacency graph to identify one or more of the plural predetermined patterns of semantic labels in the labeled region adjacency graph;

an assigning module, for assigning corresponding ones of the plural stereotypes to the digital image in accordance with which of the plural predetermined patterns were identified in said analyzing step, such that the assigned stereotype describes the plurality of regions of the digital image and represents a classification of the digital image; and

a storage module, for storing the assigned stereotypes and the digital image in one or more databases of digital images, wherein the digital image is retrievable from the one or more databases using a search for the assigned stereotype.

32. The computer program product according to claim 31, wherein identification of the predetermined pattern is based on a size of one or more regions of the digital image.

33. The computer program product according to claim 31, wherein identification of the predetermined pattern is based on an adjacency of the regions.

34. The computer program product according to claim 31, wherein identification of the predetermined pattern is based on semantic label content of the region adjacency graph.

35. The computer program product according to claim 31, wherein identification of the predetermined pattern is based on a mean color of one or more regions of the digital image.

36. The computer program product according to claim 31, wherein the plurality of stereotypes are stored in an association lookup table.

37. The computer program product according to claim 31, wherein the stereotypes are represented in a hierarchical arrangement.

38. The computer program product according to claim 31, wherein each of the stereotypes has a hierarchical path.

39. The computer program product according to claim 31, wherein the region adjacency graph is provided by analyzing contextual data associated with one or more regions of the digital image.

40. The computer program product according to claim 39, wherein the contextual data comprises information generated by one or more separate sources of the information.

41. The computer program product according to claim 40, wherein a corresponding portion of the contextual data is obtained from a temporal region of interest for each source of the information.

42. The computer program product according to claim 31 further comprising a metadata providing module for providing metadata associated with each digital image, wherein the metadata includes the stereotypes of each digital image.

43. The computer program product according to claim 42, wherein the metadata includes a hierarchical path associated with the respective stereotype of each digital image.

44. The computer program product according to claim 43, wherein the hierarchical path is stored with a respective stereotype as a metadata object which is associated with a respective image object.

45. The computer program product according to claim 43, wherein the hierarchical path is stored as a referenced lookup table.

46. A method of classifying a digital image signal, said method comprising the steps of:

segmenting the digital image into a plurality of substantially homogeneous regions;

processing the plurality of regions to provide a region adjacency graph for the digital image, the region adjacency graph representing spatial adjacency between the plurality of regions of the digital image;

labeling at least one of the regions of the region adjacency graph with one of a plurality of predetermined semantic labels to provide a labeled region adjacency graph;

providing a set of plural predetermined patterns of semantic labels, wherein each predetermined pattern of semantic labels corresponds to one of plural stereotypes each representing a different classification of a digital image, and wherein each predetermined pattern comprises;

(J) a set of labeled regions;

or

(ii) a set of labeled regions and corresponding adjacency information;

analyzing the labeled region adjacency graph to identify the presence of one or more of the plural patterns of semantic labels in the labeled region adjacency graph;

for each pattern of labeled regions identified in the labeled region adjacency graph as matching a predetermined pattern, selecting the corresponding stereotype classifications from the plural stereotype classifications based on the matching;

assigning the selected stereotype classifications to the digital image such that the assigned stereotype describes the plurality of regions of the digital image and represents a classification of the digital image; and

storing the assigned stereotype classifications and the digital image in one or more databases of digital images, wherein the digital image is retrievable from the one or more databases using a search for the assigned stereotype classification.

47. The method according to claim 46, wherein the digital image is classified on the basis of semantic label content of the labeled region adjacency graph.

48. The method according to claim 46, wherein a stereotype is assigned to the digital image signal on the basis of the adjacency of a set of regions with specified labels in the labeled region adjacency graph.

49. The method according to claim 46, wherein a stereotype is assigned to the digital image signal on the basis of the size of one or more regions with a specified label in the labeled region adjacency graph.

50. The method according to claim 46, wherein a stereotype is assigned to the digital image signal on the basis of a label which represents a mean color of one or more regions in the labeled region adjacency graph.

51. The method according to claim 46, wherein a stereotype is assigned to the digital image signal on the basis of a label which represents a mean color texture of one or more regions in the labeled region adjacency graph.

52. The method according to claim 46, wherein the plurality of stereotypes are stored in an association lookup table.

53. The method according to claim 46, wherein the stereotypes are represented in an hierarchical arrangement.

54. The method according to claim 53, wherein each of the stereotypes has a hierarchical path.

55. The method according to claims 46, wherein each of the stereotypes is represented by one of a plurality of icons.

56. The method according to claims 46, wherein the digital image is retrievable from the one or more databases using a keyword representing a stereotype.

57. The method according to claim 46, wherein the digital image is retrievable from the one or more databases using an icon representing a stereotype.

58. The method according to claim 46, wherein the digital image is retrievable from the one or more databases using either a keyword or icon representing a generalization, or broader version, of a stereotype.

59. An apparatus for classifying a digital image signal, said apparatus comprising:

segmenting means for segmenting the digital image into a plurality of substantially homogeneous regions;

processing means for processing the plurality of regions to provide a region adjacency graph for the digital image, the region adjacency graph representing spatial adjacency between the plurality of regions of the digital image;

labeling means for labeling at least one of the regions of the region adjacency graph with one of a plurality of predetermined semantic labels to provide a labeled region adjacency graph;

pattern storage means means for storing a set of plural predetermined patterns of semantic labels, wherein each predetermined pattern of semantic labels corresponds to one of plural stereotypes each representing a different classification of a digital image, and wherein each predetermined pattern comprises;

(I) a set of labeled regions;

or

(ii) a set of labeled regions and corresponding adjacency information;

analyzing means for analyzing the labeled region adjacency graph to identify the presence of one or more of the plural predetermined patterns of semantic labels in the labeled region adjacency graph, wherein for each pattern of labeled regions identified in the labeled region adjacency graph as matching a predetermined pattern, said classification providing means assigns the predetermined stereotype classifications to the digital image such that the assigned stereotype describes the plurality of regions of the digital image and represents a classification of the digital image; and

storage means for storing the assigned stereotype classifications and the digital image in one or more databases of digital images, wherein the digital image is retrievable from the one or more databases using a search for the assigned stereotype classification.

60. The apparatus according to claim 59, wherein a stereotype is assigned to the digital image signal on the basis of the semantic label content of one or more regions in the labeled region adjacency graph.

61. The apparatus according to claim 59, wherein a stereotype is assigned to the digital image signal on the basis of the adjacency of a set of regions with specified labels in the labeled region adjacency graph.

62. The apparatus according to claim 59, wherein a stereotype is assigned to the digital image signal on the basis of the size of one or more regions with a specified label in the labeled region adjacency graph.

63. The apparatus according to claim 59, wherein a stereotype is assigned to the digital image signal on the basis of a label which represents a mean color of one or more regions in the labeled region adjacency graph.

64. The apparatus according to claim 59, wherein a stereotype is assigned to the digital image signal on the basis of a label which represents a mean color texture of one or more regions in the labeled region adjacency graph.

65. The apparatus according to claim 59, wherein the plurality of stereotypes are stored in an association lookup table.

66. The apparatus according to claim 59, wherein the stereotypes are represented in an hierarchical arrangement.

67. The apparatus according to claim 66, wherein each of the stereotypes has a hierarchical path.

68. The apparatus according to claim 59, wherein each of the stereotypes is represented by one of a plurality of icons.

69. The apparatus according to claim 59, wherein the digital image is retrievable from the one or more databases using a keyword representing a stereotype.

70. The apparatus according to claim 59, wherein the digital image is retrievable from the one or more databases using a icon representing a stereotype.

71. The apparatus according to claim 59, wherein the digital image is retrievable from the one or more databases using either a keyword or icon representing a generalization, or broader version, of a stereotype.

72. A computer program product comprising a computer readable medium having a computer program recorded for classifying a digital image signal, said computer program product comprising:

a segmenting module, for segmenting the digital image into a plurality of substantially homogeneous regions;

a processing module, for processing the plurality of regions to provide a region adjacency graph for the digital image, the region adjacency graph representing spatial adjacency between the plurality of regions of the digital image;

labeling at least one of the regions of the region adjacency graph with at least one of a plurality of predetermined semantic labels to provide a labeled region adjacency graph;

a pattern storage module, for storing a set of plural predetermined patterns of semantic labels, wherein each pattern of semantic labels corresponds to one of plural stereotypes each representing a different classification of a digital image, wherein each predetermined pattern comprises;

(I) a set of labeled regions;

or

(ii) a set of labeled regions and corresponding adjacency information;

an analyzing module, for analyzing the labeled region adjacency graph to identify the presence of one or more of the plural patterns of semantic labels in the labeled region adjacency graph, wherein for each pattern of labeled regions identified in the labeled region adjacency graph as matching a predetermined pattern, said classification providing module assigns the corresponding predetermined stereotype classifications to the digital image such that the assigned stereotype describes the plurality of regions of the digital image and represents a classification of the digital image; and

a storage module, for storing the assigned stereotype classifications and the digital image in one or more databases of digital images, wherein the digital image is retrievable from the one or more databases using a search for the assigned stereotype classification.

73. The computer program product according to claim 72, wherein a stereotype is assigned to the digital image signal on the basis of the semantic label content of one or more regions in the labeled region adjacency graph.

74. The computer program product according to claim 72, wherein a stereotype is assigned to the digital image signal on the basis of the adjacency of a set of regions with specified labels in the labeled region adjacency graph.

75. The computer program product according to claim 72, wherein a stereotype is assigned to the digital image signal on the basis of the size of one or more regions with a specified label in the labeled region adjacency graph.

76. The computer program product according to claim 72, wherein a stereotype is assigned to the digital image signal on the basis of a label which represents a mean color of one or more regions in the labeled region adjacency graph.

77. The computer program product according to claim 72, wherein a stereotype is assigned to the digital image signal on the basis of a label which represents a mean color texture of one or more regions in the labeled region adjacency graph.

78. The computer program product according to claim 72, wherein the plurality of stereotypes are stored in an association lookup table.

79. The computer program product according to claim 72, wherein the stereotypes are represented in an hierarchical arrangement.

80. The computer program product according to claim 79, wherein each of the stereotypes has a hierarchical path.

81. The computer program product according to claim 72, wherein each of the stereotypes is represented by one of a plurality of icons.

82. The computer program product according to claim 72, wherein the digital image is retrievable from the one or more databases using a keyword representing a stereotype.

83. The computer program product according to claim 72, wherein the digital image is retrievable from the one or more databases using a icon representing a stereotype.

84. The computer program product according to claim 72, wherein the digital image is retrievable from the one or more databases using either a keyword or icon representing a generalization, or broader version, of a stereotype.

85. A method of classifying a digital image, said method comprising the steps of:

segmenting the digital image into substantially homogeneous regions;

processing the regions to provide a labeled region adjacency graph for the digital image, wherein the labeled region adjacency graph represents spatial adjacency between the regions of the digital image, and wherein at least one of the regions of the labeled region adjacency graph is associated with one of a plurality of predetermined semantic labels;

providing a set of plural predetermined patterns of semantic labels, wherein each predetermined pattern of semantic labels corresponds to one of plural stereotypes based on a minimum size of the regions in the labeled adjacency graph, and wherein the plural stereotypes define a multi-level hierarchical structure with each of the stereotypes representing a different classification of a digital image;

analyzing the labeled region adjacency graph to identify one or more of the plural predetermined patterns of semantic labels in the labeled region adjacency graph;

assigning corresponding ones of the plural stereotypes to the digital image in accordance with which of the plural predetermined patterns were identified in said analyzing step, such that the assigned stereotype represents a classification of the digital image; and

storing the assigned stereotypes and the digital image in one or more databases of digital images together with one or more hierarchical paths, the one or more hierarchical paths being based on the multi-level hierarchical structure, wherein the digital image is retrievable from the one or more databases using a search for the assigned stereotypes and hierarchical paths.

86. A method of classifying a digital image, said method comprising the steps of:

segmenting the image into substantially homogeneous regions;

processing, the regions to provide a labeled region adjacency graph for the digital image, wherein the labeled region adjacency graph represents spatial adjacency between the regions of the image, and wherein at least one of the regions of the labeled region adjacency graph is associated with one of a plurality of predetermined semantic labels;

providing a set of plural predetermined patterns of semantic labels, wherein each predetermined pattern of semantic labels corresponds to one of plural stereotypes based on a minimum size of the regions in the labeled adjacency graph, and wherein the plural stereotypes define a multi-level hierarchical structure with each of the stereotypes representing a different classification of a digital image;

analyzing the labeled region adjacency graph to identify one or more of the plural predetermined patterns of semantic labels in the labeled region adjacency graph; and

assigning corresponding ones of the plurality of stereotypes to the digital image in accordance with which of the plural predetermined patterns were identified in said analyzing step, such that each assigned stereotype represents a classification of the digital image, wherein the plurality of stereotypes are represented in a multi-level hierarchical tree-structure such that the digital image is retrievable from one or more databases of digital images upon selection of at least one of the assigned stereotypes using the multi-level hierarchical tree-structure.

87. A method of classifying a digital image, said method comprising the steps of:

segmenting the image into substantially homogeneous regions;

processing the regions to provide a labeled region adjacency graph for the digital image, wherein the labeled region adjacency graph represents spatial adjacency between the regions of the image, and wherein at least one of the regions of the labeled region adjacency graph is associated with one of a plurality of predetermined semantic labels;

providing a set of plural predetermined patterns, of semantic labels, wherein each predetermined pattern of semantic labels corresponds to one of plural stereotypes based on a minimum size of the regions in the labeled adjacency graph, and wherein the plural stereotypes define a multi-level hierarchical structure with each of the stereotypes representing a different classification of a digital image;

analyzing the labeled region adjacency graph to identify one or more of the plural predetermined patterns of semantic labels in the labeled region adjacency graph; and

assigning corresponding ones of the plural stereotypes to the digital image in accordance with which of the plural predetermined patterns were identified in said analyzing step, such that each assigned stereotype represents a classification of the digital image, wherein the plurality of stereotypes have a hierarchical arrangement adapted for representation as a navigable stereotype tree such that the digital image is retrievable from one or more databases of digital images upon selection of at least one of the assigned stereotypes using the stereotype tree.

88. A method of classifying a digital image, said method comprising the steps of:

determining an initial probability value for substantially each of a plurality of predetermined semantic labels, each of said initial probability values being set to a predetermined default value for each of said semantic labels;

adjusting said initial probability values for said semantic labels in a selected application domain for said digital image;

segmenting said digital image into a plurality of substantially homogeneous regions;

processing said plurality of regions to provide a region adjacency graph for the digital image, said region adjacency graph representing spatial adjacency between said plurality of regions of said digital image;

labeling each of said regions of said region adjacency graph with a corresponding one of said plurality of predetermined semantic labels to provide a labeled region adjacency graph comprising one or more labeled regions, said one semantic label being selected by multiplying an adjusted initial probability value for each semantic label with a conditional probability density value determined for said at least one region;

analyzing said label region adjacency graph to identify one of a plurality of predetermined patterns of labeled regions in said labeled region adjacency graph;

assigning one of said plurality of predetermined stereotypes to said labeled region adjacency graph according to said identified predetermined pattern, each of said plurality of predetermined patterns corresponding to one of said predetermined stereotypes such that the assigned stereotype describes the labeled regions of said digital image and represents at least one classification of said digital image; and

storing the assigned stereotype and said digital image in one or more databases of digital images, wherein said digital image is retrievable from said one or more databases using the assigned stereotype.