Method and apparatus for creating, indexing and viewing abstracted documents

• US 6,002,798 A
• Filed: 01/19/1993
• Issued: 12/14/1999
• Est. Priority Date: 01/19/1993
• Status: Expired due to Term

• Current Assignee: Canon Kabushiki Kaisha (Canon Inc.)
• Original Assignee: Canon Kabushiki Kaisha (Canon Inc.)
• Inventors: Yagasaki, Toshiaki, Palmer, Douglas L.
• Primary Examiner(s): Follansbee, John A.
• Application Number:
  US08/005,444
• Time in Patent Office: 2,520 Days
• Field of Search: 395/800, 395/147, 395/162, 395/100, 395/144, 395/145, 395/118, 395/603, 395/615, 395/800.01, 382/61, 382/10, 382/58, 382/159, 382/176, 382/180, 382/181, 707/3, 707/104, 712/1
• US Class Current: 382/176
• CPC Class Codes: G06F 16/313 Selection or weighting of terms for indexing

Abstract

Method and apparatus for storing document images, for creating retrieval index by which the document images may be retrieved, and for displaying the retrieved document images. When a document image is obtained, the document image is subjected to rule-based block selection techniques whereby individual regions within the document region are identified, and the types of regions are also identified, such as title-type regions, text-type regions, line art-type regions, halftone-type regions and color image-type regions. The identification is used to create structural information and both the document image and the structural information is stored. A word-based retrieval index is created based on title-type regions and/or text-type regions, the retrieval index being used in conjunction with a search query so as to be able to retrieve documents which match the search query. The retrieved documents are displayed in either a full image mode or a rapid browsing mode. In the rapid browsing mode, the full image of the document is not displayed, but rather only an abstract structural view of the document image based on the stored structural information. The level of abstraction may be specified by the operator in connection with the identified structural regions of the document, whereby, for example, only a structural view is displayed, or only title-type regions are displayed mixed with remaining structure.

Claims

1. A method for creating a retrieval index by which an image of an arbitrarily formatted document may be retrieved, the method comprising the steps of:

processing the image of the arbitrarily formatted document to identify text regions on the document and non-text regions on the document, said processing step including, for each text region on the document, the step of automatically determining a region type using rule-based decisions automatically applied to the image of the text region without regard to a position of the text region in the document and without regard to a predetermined format for the document, the region type being one of plural different predefined region types encompassed by the rules;

converting the image of the document in text regions into text;

indexing the converted text so as to permit retrieval by reference to the converted text;

indexing the automatically determined region types so as to permit retrieval by reference to one of the determined region types; and

storing the image of the document such that the stored document image may be retrieved by reference to whether text in a text query appears in the indexed text and by reference to whether the text in the text query appears in one of the indexed region types.

2. A method according to claim 1, further comprising the step of determining a region type for both text regions and non-text regions on the document.

3. A method according to claim 2, further comprising the steps of retrieving a document and displaying an abstracted view of the document in which regions of the document are identified in accordance with the corresponding region types.

4. A method according to claim 3, further comprising the step of progressive replacement of regions within the abstracted view of the document with corresponding full images of the regions of the document.

5. A method according to claim 4, wherein progressive replacement is automatic and proceeds in an order determined by priority among the plural different predefined region types.

6. A method according to claim 4, wherein progressive replacement is manual in accordance with operator designation.

7. A method according to claim 3, wherein said step of retrieving assigns a score to each retrieved document in accordance with the degree of match to retrieval parameters and wherein the retrieved documents are displayed in an order determined by the score.

8. A method according to claim 3, wherein said step of retrieving includes retrieval over modem or local area network (LAN).

9. A method according to claim 8, further comprising the step of retrieving images of regions for the document over the modem or LAN when sufficient time is available, and the step of progressive replacement of regions within the abstracted view of the document with the retrieved images of the regions of the document.

10. A method according to claim 9, wherein progressive replacement is automatic and proceeds in an order determined by priority among the plural different predefined region types.

11. A method according to claim 9, wherein progressive replacement is manual in accordance with operator designation.

12. A method according to claim 2, wherein the region type for non-text regions is selected from a group of predefined region types which includes line art regions, half-tone regions, and table regions.

13. A method according to claim 1, further comprising the step of designating an index level which specifies which region types should be indexed, and wherein said converting step converts text regions in accordance with the designated index level.

14. A method according to claim 1, wherein the region types for text regions are selected from a group of predefined region types which include title regions and main text regions.

15. A method according to claim 1, wherein said processing step comprises block selection processing of the image to decompose the image into a set of objects and to use rule-based decisions to identify text and non-text regions on the document.

16. A method according to claim 15, wherein the block selection processing uses rule-based decisions to identify related regions on the document.

17. A method according to claim 1, wherein the region type is automatically determined without user intervention.

18. A method according to claim 17, wherein the arbitrarily formatted document is of a format previously unknown to the rule-based decisions.

19. Apparatus for creating a retrieval index by which an image of an arbitrarily formatted document may be retrieved, said apparatus comprising:

a scanner for scanning an original arbitrarily formatted document and for outputting a bit map document image corresponding to the original arbitrarily formatted document;

a first memory region for storing a document image and a retrieval index;

a second memory region for storing process steps; and

a processor for executing the process steps stored in said second memory region;

wherein said second memory region includes process steps to (a) receive the bit map document image scanned by said scanner, (b) process the bit map document image to identify text regions in the document and non-text regions in the document, said processing step including, for each text region on the document, the step of automatically determining a region type using rule-based decisions automatically applied to the image of the text region without regard to a position of the text region in the document and without regard to a predetermined format for the document, the region type being one of plural different predefined region types encompassed by the rules, (c) convert the document image in text regions into text, (d) index the converted text so as to permit retrieval by reference to the converted text, (e) index the automatically determined region types so as to permit retrieval by reference to one of the predetermined region types, and (f) store the document image in said first memory region such that the stored document image may be retrieved by reference to whether text in a text query appears in the indexed text and by reference to whether the text in the text query appears in one of the indexed region types.

20. Apparatus according to claim 19, wherein said second memory region includes process steps to determine a region type for both text regions and non-text regions in the bit map document.

21. Apparatus according to claim 20, further comprising a display interface, and wherein said second memory region includes process steps to retrieve a document and to transmit an abstracted view of retrieved documents to said display interface in which regions of the document are identified in accordance with corresponding region types.

22. Apparatus according to claim 21, wherein said second memory region includes process steps to progressively replace regions within the abstracted view of retrieved documents with corresponding regions from the document image.

23. Apparatus according to claim 22, wherein progressive replacement is automatic and proceeds in an order determined by priority among the plural different predefined region types.

24. Apparatus according to claim 22, further including a designation means, and wherein replacement is manual in accordance with designation by said designation means.

25. Apparatus according to claim 21, wherein retrieved documents are assigned a score in accordance with the degree of match to retrieval parameters, and wherein the retrieved documents are displayed in an order determined by the score.

26. Apparatus according to claim 21, further comprising data transmission means comprised by a modem or a local area network (LAN), wherein documents are retrieved over said data transmission means.

27. Apparatus according to claim 26, further comprising retrieving means for retrieving images of regions for the document over the modem or LAN when sufficient time is available, and replacement means for progressively replacing regions within the abstracted view of the document with the retrieved images of the regions of the document.

28. Apparatus according to claim 27, wherein progressive replacement is automatic and proceeds in an order determined by priority among the plural different predefined region types.

29. Apparatus according to claim 27, further including designation means, and wherein replacement is manual in accordance with designation by said designation means.

30. Apparatus according to claim 20, wherein the region type for non-text regions is selected from a group of predefined region types which includes line art regions, half-tone regions, and table regions.

31. Apparatus according to claim 19, wherein said process steps include steps to designate an index level which specifies which region types should be indexed, and wherein said process step to convert converts text regions in accordance with the designated index level.

32. Apparatus according to claim 19, wherein the region types for text regions are selected from a group of predefined region types which include title regions and main text regions.

33. A method according to claim 19, wherein the step to process the bit map document image comprises block selection processing of the image to decompose the image into a set of objects and to use rule-based decisions to identify text and non-text regions on the document.

34. A method according to claim 33, wherein the block selection processing uses rule-based decisions to identify related regions on the document.

35. An apparatus according to claim 19, wherein the region type is automatically determined without user intervention.

36. An apparatus according to claim 35, wherein the arbitrarily formatted document is of a format previously unknown to the rule-based decisions.

37. A method for displaying documents comprising the steps of:

providing an image of a document and corresponding composition information for the document, the composition information including region type information for each of up to plural regions of the document;

displaying an abstracted view of the document using the composition information;

replacing, within the abstracted view itself, at least one region of the abstracted view with a corresponding image of the document, so that composition information and image information are mixedly displayed.

38. A method according to claim 37, further comprising the step of designating an abstraction level based on the composition information for displaying the abstracted view of the document, and wherein in said displaying step the abstracted view is displayed with mixed regions of composition information and document image in accordance with the designated abstraction level.

39. A method according to claim 37, wherein in said providing step a plurality of document images and corresponding document composition information are provided, and further comprising the step of retrieving one of the plurality of document images and corresponding document composition information for display.

40. A method according to claim 39, wherein the retrieved documents are assigned a score in accordance with the degree of match to retrieval parameters, and wherein the retrieved documents are displayed in an order determined by the score.

41. A method according to claim 39, wherein in said displaying step, the abstracted view is displayed mixed with retrieval parameters.

42. A method according to claim 37, further comprising the step of labelling regions of the abstracted view in accordance with the composition information for the regions.

43. A method according to claim 37, wherein said displaying step is a verbal enunciation of document structure through text-to-speech conversion of the composition information.

44. A method according to claim 37, further comprising the step of identifying document type based on the composition information.

45. A method according to claim 37, further comprising the step of identifying related regions in the document, and wherein in said replacing step, when a region within the abstracted view is replaced, related regions within the abstracted view are also replaced.

46. A method according to claim 37, wherein in said replacing step, text regions on the document are replaced with text images of the document or with text equivalents in accordance with manual selection.

47. A method according to claim 37, wherein in said providing step, the image of the document is provided from a remote source over a modem or a local area network (LAN).

48. A method according to claim 47, wherein in said providing step, images for regions of the document are retrieved over the modem or LAN when sufficient time is available, and wherein said replacing step is progressive such that regions on the abstracted view are progressively replaced within the abstracted view with the retrieved images of regions of the document.

49. A method according to claim 48, wherein progressive replacement is automatic and proceeds in an order determined by priority among the plural different predefined region types.

50. A method according to claim 48, wherein progressive replacement is manual in accordance with operator designation.

51. Apparatus for displaying a document comprising:

means for providing an image of a document and corresponding composition information for the document, the composition information including region type information for each of up to plural regions of the document;

means for displaying an abstracted view of the document using the composition information; and

means for replacing, within the abstracted view itself, at least one region of the abstracted view with a corresponding image of the document, so that composition information and image information are mixedly displayed.

52. An apparatus according to claim 51, further comprising designating means for designating an abstraction level based on the composition information for displaying the abstracted view of the document, wherein said abstracted view is displayed with mixed regions of composition information and document image in accordance with the designated abstraction level.

53. An apparatus according to claim 51, wherein a plurality of document images and corresponding document composition information are provided, and further comprising retrieving means for retrieving one of the plurality of document images and corresponding document composition information for display.

54. An apparatus according to claim 53, wherein the retrieved documents are assigned a score in accordance with the degree of match to retrieval parameters, and wherein the retrieved documents are displayed in an order determined by the score.

55. An apparatus according to claim 53, wherein said displaying means displays the abstracted view mixed with retrieval parameters.

56. An apparatus according to claim 51, further comprising labelling means for labelling regions of the abstracted view in accordance with the composition information for the regions.

57. An apparatus according to claim 51, wherein said displaying means is a verbal enunciation of document structure through text-to-speech conversion of the composition information.

58. An apparatus according to claim 51, further comprising identifying means for identifying document type based on the composition information.

59. An apparatus according to claim 51, further comprising identifying means for identifying related regions within the document, and wherein when said replacing means replaces a region in the abstracted view, related regions within the abstracted view are also replaced.

60. An apparatus according to claim 51, wherein the regions on the document are replaced with text images of the document or with text equivalents in accordance with a manual selection.

61. Apparatus according to claim 51, wherein the image of the document is provided from a remote source over a modem or a local area network (LAN).

62. Apparatus according to claim 61, wherein images for regions of the document are retrieved over the modem or LAN when sufficient time is available, and wherein replacement of regions of the abstracted view is progressive such that regions of the abstracted view are progressively replaced within the abstracted view with the retrieved images of regions of the document.

63. A method according to claim 62, wherein progressive replacement is automatic and proceeds in an order determined by priority among the plural different predefined region types.

64. Apparatus according to claim 62, wherein progressive replacement is manual in accordance with operator designation.

65. A document display apparatus comprising:

a display;

a first memory region from which an image of a document and corresponding composition information for the document may be retrieved;

a second memory region for storing process steps;

a processor for executing the process steps stored in said second memory region;

wherein said second memory region includes process steps to (a) display on said display an abstracted view of a retrieved document in accordance with the composition information, and (b) replace, within the abstracted view itself, a selected region of the abstracted view with a corresponding document image, so that composition information and image information are mixedly displayed.

66. Apparatus according to claim 65, further comprising input means for inputting operator designations, and wherein said second memory region includes process steps to permit designation of an abstraction level at which the abstracted view is displayed, wherein mixed regions of composition information and document image are displayed in accordance with the designated abstraction level.

67. Apparatus according to claim 65, wherein said first memory region includes plural document images and plural corresponding composition information, and wherein said second memory region includes process steps to retrieve one of the plurality of stored document images and corresponding document composition information for display.

68. An apparatus according to claim 67, wherein the retrieved documents are assigned a score in accordance with the degree of match to retrieval parameters, and wherein the retrieved documents are displayed in an order determined by the score.

69. Apparatus according to claim 67, wherein the abstracted view is displayed mixed with retrieval parameters.

70. Apparatus according to claim 65, wherein said processor labels the displayed abstracted view in accordance with the composition information stored in said first memory region.

71. Apparatus according to claim 65, wherein said processor enunciates the document composition information in accordance with text-to-speech conversion of the composition information.

72. Apparatus according to claim 65, wherein said processor identifies document type based on the stored composition information.

73. Apparatus according to claim 65, wherein the stored composition information correlates related regions within the document, and wherein when said processor replaces a region of the abstracted view with corresponding regions of document image, said processor also replaces related regions within the abstracted view.

74. An apparatus according to claim 65, wherein text regions on the document are replaced with text images of the document or with text equivalents in accordance with a manual selection.

75. Apparatus according to claim 65, wherein said first memory region is accessed remotely over a modem or a local area network (LAN).

76. Apparatus according to claim 75, wherein images for regions of the document are retrieved over the modem or LAN when sufficient time is available, and wherein replacement of regions of the abstracted view is progressive such that regions of the abstracted view are progressively replaced within the abstracted view with the retrieved images of regions of the document.

77. A method according to claim 76, wherein progressive replacement is automatic and proceeds in an order determined by priority among the plural different predefined region types.

78. Apparatus according to claim 76, wherein progressive replacement is manual in accordance with operator designation.

79. A method for creating a retrieval index by which an image of an arbitrarily formatted document may be retrieved, the method comprising the steps of:

processing the image of the arbitrarily formatted document to identify text regions on the document and non-text regions on the document, said processing step including, for each text region on the document, the step of automatically determining a region type using rule-based decisions automatically applied to the image of the text region without regard to a position of the text region in the document and without regard to a predetermined format for the document, the region type being one of plural different predefined region types encompassed by the rules;

converting the image of the document in text regions into text;

indexing the converted text so as to permit retrieval by reference to the converted text;

indexing the automatically determined region types so as to permit retrieval by reference to one of the determined region types; and

associating the image of the document with the indexed text such that the image of the document may be retrieved by reference to whether text in a text query appears in the indexed text and by reference to whether the text in the text query appears in one of the indexed region types.

80. A method according to claim 79, further comprising the step of determining a region type for both text regions and non-text regions on the document.

81. A method according to claim 80, further comprising of the steps of retrieving a document and displaying an abstracted view of the document in which regions of the document are identified in accordance with the corresponding region types.

82. A method according to claim 81, further comprising the step of progressive replacement of regions within the abstracted view of the document with corresponding full images of the regions of the document.

83. A method according to claim 82, wherein progressive replacement is automatic and proceeds in an order determined by priority among the plural different predefined region types.

84. A method according to claim 82, wherein progressive replacement is manual in accordance with operator designation.

85. A method according to claim 81, wherein said step of retrieving assigns a score to each retrieved document in accordance with the degree of match to retrieval parameters and wherein the retrieved documents are displayed in an order determined by the score.

86. A method according to claim 81, wherein said step of retrieving includes retrieval over modem or local area network (LAN).

87. A method according to claim 86, further comprising the step of retrieving images of regions for the document over the modem or LAN when sufficient time is available, and the step of progressive replacement of regions within the abstracted view of the document with the retrieved images of the regions of the document.

88. A method according to claims 87, wherein progressive replacement is automatic and proceeds in an order determined by priority among the plural different predefined region types.

89. A method according to claim 87, wherein progressive replacement is manual in accordance with operator designation.

90. A method according to claim 80, wherein the region type for non-text regions is selected from a group of predefined region types which includes line art regions, half-tone regions, and table regions.

91. A method according to claim 79, further comprising the step of designating an index level which specifies which region types should be indexed, and wherein said converting step converts text regions in accordance with the designated index level.

92. A method according to claim 79, wherein the region types for text regions are selected from a group of predefined region types which include title regions and main text regions.

93. A method according to claim 79, wherein said processing step comprises block selection processing of the image to decompose the image into a set of objects and to use rule-based decisions to identify text and non-text regions on the document.

94. A method according to claim 93, wherein the block selection processing uses rule-based decisions to identify related regions on the document.

95. A method according to claim 79, wherein the region type is automatically determined without user intervention.

96. A method according to claim 95, wherein the arbitrarily formatted document is of a format previously unknown to the rule-based decisions.

97. Apparatus for creating a retrieval index by which an image of an arbitrarily formatted document may be retrieved, said apparatus comprising:

a scanner for scanning an arbitrarily formatted original document and for outputting a bit map document image corresponding to the original arbitrarily formatted document;

a first memory region for storing a document image and a retrieval index;

a second memory region for storing process steps; and

a processor for executing the process steps stored in said second memory region;

wherein said second memory region includes process steps to (a) receive the bit map document image scanned by said scanner, (b) process the bit map document image to identify text regions in the document and non-text regions in the document, said processing step including, for each text region on the document, the step of automatically determining a region type using rule-based decisions applied to the image of the text region without regard to a position of the text region in the document and without regard to a predetermined format for the document, the region type being one of plural different predefined region types encompassed by the rules, (c) convert the document image in text regions into text, (d) index the converted text so as to permit retrieval by reference to the converted text, (e) index the automatically determined region types so as to permit retrieval by reference to one of the region types, and (f) associate the document image with the indexed text such that the document image may be retrieved by reference to whether text in a text query appears in the indexed text and by reference to whether the text in the text query appears in one of the indexed region types.

98. Apparatus according to claim 97, wherein said second memory region includes process steps to determine a region type for both text regions and non-text regions in the bit map document.

99. Apparatus according to claim 98, further comprising a display interface, and wherein said second memory region includes process steps to retrieve a document and to transmit an abstracted view of retrieved documents to said display interface in which regions of the document are identified in accordance with corresponding region types.

100. Apparatus according to claim 99, wherein said second memory region includes process steps to progressively replace the abstracted regions within the abstracted view of retrieved documents with corresponding regions from the full document image.

101. Apparatus according to claim 100, wherein progressive replacement is automatic and proceeds in an order determined by priority among the plural different predefined types.

102. Apparatus according to claim 100, further including a designation means, and wherein replacement is manual in accordance with designation by said designation means.

103. Apparatus according to claim 99, wherein retrieved documents are assigned a score in accordance with the degree of match to retrieval parameters, and wherein the retrieved documents are displayed in an order determined by the score.

104. Apparatus according to claim 99, further comprising data transmission means comprised by a modem or a local area network (LAN), wherein documents are retrieved over said data transmission means.

105. Apparatus according to claim 104, wherein images of regions for the document are retrieved over the modem or LAN when sufficient time is available, and wherein regions within the abstracted view of the document are progressively replaced with the retrieved images of the regions of the document.

106. Apparatus according to claim 105, wherein progressive replacement is automatic and proceeds in an order determined by priority among the plural different predefined region types.

107. Apparatus according to claim 105, further including designation means, and wherein replacement is manual in accordance with designation by said designation means.

108. Apparatus according to claim 98, wherein the region type for non-text regions is selected from a group of predefined region types which includes line art regions, half-tone regions, and table regions.

109. Apparatus according to claim 97, wherein said process steps include steps to designate an index level which specifies which region types should be indexed, and wherein said process step to convert converts text regions in accordance with the designated index level.

110. Apparatus according to claim 97, wherein the region types for text regions are selected from a group of predefined region types which include title regions and main text regions.

111. A method according to claim 97, wherein the step to process the bit map document image comprises block selection processing of the image to decompose the image into a set of objects and to use rule-based decisions to identify text and non-text regions on the document.

112. A method according to claim 111, wherein the block selection processing uses rule-based decisions to identify related regions on the document.

113. An apparatus according to claim 97, wherein the region type is automatically determined without user intervention.

114. An apparatus according to claim 113, wherein the arbitrarily formatted document is of a format previously unknown to the rule-based decisions.

115. A computer-readable memory medium storing computer-executable process steps to create a retrieval index by which an image of an arbitrarily formatted document may be retrieved, comprising:

a processing step to process the image of the arbitrarily formatted document to identify text regions on the document and non-text regions on the document, said processing step including, for each text region on the document, a step to determine a region type using rule-based decisions automatically applied to the image of the text region without regard to a position of the text region in the document and without regard to a predetermined format for the document, the region type being one of plural different predefined region types encompassed by the rules;

a converting step to convert the image of the document in text regions into text;

a text indexing step to index the converted text so as to permit retrieval by reference to the converted text;

a region type indexing step to index the automatically determined region types so as to permit retrieval by reference to one of the determined region types; and

a storing step to store the image of the document such that the stored document image may be retrieved by reference to whether text in a text query appears in the indexed text and by reference to whether the text in the text query appears in one of the indexed region types.

116. A computer-readable memory medium according to claim 115, wherein the region type is automatically determined without user intervention.

117. A computer-readable memory medium according to claim 116, wherein the arbitrarily formatted document is of a format previously unknown to the rule-based decisions.

118. A computer-readable memory medium storing computer-executable process steps to display documents comprising:

a providing step to provide an image of a document and corresponding composition information for the document, the composition information including region type information for each of up to plural regions of the document;

a displaying step to display an abstracted view of the document using the composition information;

a replacing step to replace, within the abstracted view itself, at least one region of the abstracted view with a corresponding image of the document, so that composition information and image information are mixedly displayed.