JP2000112995A - Document search method, document search device, and recording medium - Google Patents

Abstract

(57) [Summary] [PROBLEMS] To realize a method and an apparatus for efficiently searching a document using a visual structure such as a chart in the document. A target document is analyzed to generate structural information describing a visual structure of the target document (351). For example, text is deleted from the raster image of the document, and a point set corresponding to the remaining components is generated. Alternatively, a set of endpoints of line segments generated by a command in the page description language file is generated. The generated structure information is compared with the structure information describing the set of stored electronic documents (352), and the stored electronic document that is considered to have the same structure information is extracted (35).
3). The Hausdorff method is used to determine the coincidence of structural information.

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a document search technique, and more particularly, to a document search technique based on a visual appearance of a document.

[0002]

2. Description of the Related Art There are many methods for searching for a document that matches parameters defined by a document searcher. The most common search methods are text,
This is the base search method. For example, a document searcher can match desired or specified contents by defining a character string consisting of one or more keywords contained in a desired document, or by defining a "logical search expression". You can find a document to do.

There is also a method for retrieving a document image. For example,
There is an image search method that uses the line structure of a document. Such a search method is generally used for drawings, maps, flowcharts, and the like. Another example of an image search technique is Nibl
ack, W., et al., "The QBIC Project: Querying Images
By Content Using Color, Textureand Shape "SPIE Pro
ceedings, Vol. 1908, pp.173-187 (February, 1993).

[0004] Humans often search for physical documents because humans can recognize documents based on their visual appearance. For example, if you know that a particular chart was included in a set of presentation slides, you can quickly search for that chart from a stored document and retrieve the slides associated with it. However, when the particular document containing the desired diagram cannot be remembered, more documents may need to be consulted. In the case of documents stored on computer systems, thinking about a file, opening it and examining it thoroughly, especially when the number of files to be searched is large,
Will be very time consuming.

[0005]

SUMMARY OF THE INVENTION Accordingly, it is an object of the present invention to provide a method and apparatus for automatically retrieving a document using a visual structure such as a diagram or table in the document. It is another object of the present invention to provide such a document search method and apparatus that is less affected by the text content of the document.

[0006]

A main feature of the present invention to achieve the above object is to generate structural information describing a visual structure of a target document and store the structural information describing the generated target document. One of the stored electronic documents is compared with a set of structural information describing a set of documents, and when the structural information describing the stored document matches the structural information describing the target document within a predetermined tolerance. This is to retrieve the stored electronic document. Another feature of the present invention is that text is deleted from a raster image of a target document, and a point set corresponding to the remaining components is generated as structure information of the target document. Another feature of the present invention is to determine an endpoint that describes a line for a command in a page description language file of a target document;
A point set corresponding to the obtained end point is generated as structure information of the target document.

The above and other features of the present invention will be specifically described in the following description.

[0008]

DETAILED DESCRIPTION In the following description, various examples are set forth for purposes of explanation. However, it will be apparent to one skilled in the art that the present invention may be practiced without such an embodiment. On the other hand, well-known structures and devices are shown in block diagram form in order to not unnecessarily obscure the present invention.

In the following detailed description, there are portions represented by algorithms and symbolic representations of operations on data bits in computer memory. Such algorithm descriptions and representations will be readily apparent to those skilled in the data processing arts,
It is the means used to most effectively convey the contents of the research to other persons skilled in the art. Suppose we have an algorithm, which is generally understood to be a sequence of reasonable steps leading to a desired result. These steps require physical manipulation of physical quantities. Usually, but not necessarily, these physical quantities take the form of electrical or magnetic signals that can be stored, transferred, combined, compared, and otherwise manipulated. It has been found convenient to refer to these signals by bits, numbers, elements, symbols, characters, terms, numbers, and the like, which may be convenient mainly for reasons of convention.

It should be noted, however, that these and similar terms should be associated with appropriate physical quantities and are merely convenient labels attached to these physical quantities. As will be apparent from the following description, discussions using terms such as “processing”, “calculation”, “calculation”, “judgment”, “display”, etc.
Processing data expressed as physical (electronic) quantities inside registers and memories of computer systems,
The operation and process of a computer system or similar electronic computing device that converts to other data, also expressed as physical quantities, inside a memory or register of a computer system or other similar information storage device, information transmission device or display device. It points.

An apparatus for carrying out the present invention may be made exclusively for a desired purpose, or may be a general-purpose computer selectively driven or reconfigured by a built-in computer program. . Such a computer program can be a computer readable storage medium, any type of disk, such as, but not limited to, a floppy disk, optical disk, CD-ROM, magneto-optical disk, read only memory (ROM) , Random access memory (RAM), E
It may be stored on a PROM, EEPROM, magnetic or optical card, any type of medium suitable for storing electronic instructions and connected to a computer system bus. The algorithms presented here are essentially irrelevant to any particular computer or other device. Various general-purpose machines may be used with programs in accordance with the teachings herein, but it may be advantageous to make more specialized apparatus to perform the steps for the required method. The required structure for a variety of these machines will appear from the description given. Furthermore, the present invention is described without association with any particular programming language. It will be appreciated that a variety of programming languages may be utilized to implement the subject matter described herein.

In the present invention, document matching is performed using the visual structure of a document. The document targeted by the present invention may be any electronic file that transmits information.
Presentations, reports, etc., but are not limited to them. Using structural information that describes a certain document (target document), from a group of stored electronic documents,
A desired document is searched by matching with the structure information.

In general, structural information includes, for example, a figure,
Any representation or description of one or more graphic features, such as a line drawing, an array of parts or line segments, or portions thereof, may be used. The graphic feature may include a line segment. In an image, line segments can be deleted by operators such as the Hough transform. In page description languages such as PostScript, line segments are explicitly represented by commands such as "lineto". Line segments in the image and those generated by the PostScript program are mapped to cells in the Hough transform array. Accuracy can be improved by displaying the Hough space as a parameter for each position in the image. A high degree of similarity between Hough arrays means that the Hough arrays represent the same graphic image. The similarity between Hough arrays can be measured by a simple distance function such as a dot product. For more complex distance functions, the inaccuracy of the line segments will be taken into account. Line segments detected at the same location may be mapped to several nearby locations in Hough space, thereby making them robust against noise and detecting similar line segments in the two images The possibilities increase.

A similar method can be used, using edges as features. Edge detection can be performed using many commonly available methods, for example, using the Canny operator. And after applying a line segment to the edge,
According to the above procedure, two images can be matched. However, PostScript programs may be modified so that any operator that produces a straight edge also outputs an edge. For example, a linto command may generate two edges, one on each side of the line. A command that generated one fill rectangle may generate four lines, one on each side of the rectangle.

In one embodiment, the structure information is a point set,
The point set of the target document is compared with the point set of the stored electronic document to be searched, and it is determined whether or not the stored electronic document matches the target document. Document (or part of document)
Is converted to a point set. If the point sets match within a predetermined tolerance, the documents are considered matched. In one embodiment, a Hausdorff measure is used for comparing point sets. In short, these point sets become queries for searching for figures and other structures in the document database.

FIG. 1 is a block diagram showing an example of a document processing apparatus capable of implementing the present invention. Document processing device 100
Has a bus 101 for information transmission or other communication devices, and has a processor 102 connected to the bus 101 for information processing. The document processing device 100 further includes a random access memory (RAM) or other dynamic storage device 104 (called main memory) for storing information and instructions executed by the processor 102.
Are connected to the bus 101. Main memory 104
Can also be used to store temporary variables and other intermediate information while the processor 102 is executing instructions. The document processing apparatus 100 includes a read-only memory (RO) for storing fixed information and instructions for the processor 102.
M) 106 is also connected to the bus 101. A data storage device 107 such as a hard disk device for storing information and instructions is also connected to the bus 101. A drive 109 for reading and writing a recording medium 108 such as a magnetic disk, a CD-ROM, and a DVD is also connected to the bus 101. A display device 121 such as a liquid crystal display (LCD) for displaying information to a user is also connected to the document processing apparatus 100 via a bus 101. The input device 125 is also connected to the bus 101, and the user can input and control the document processing device 100 using the input device 125. The input device 125 is, for example, a keyboard, a keypad, a mouse, a trackball, a trackpad, a touch screen, or the like. FIG.
Although not shown, the document processing apparatus 100 may include an interface with a communication line or a network.

The present invention provides such a document processing apparatus 100.
Is used for document matching based on structural image data. According to one embodiment, the main memory 10
When the processor 102 executes the instruction sequence stored in the document processing apparatus 4, the document matching is performed in the document processing apparatus 100 according to the present invention. By executing the instruction sequence in the main memory 104, the processor 10
2 performs document matching using the structural image data.

The method of loading the instruction sequence into the main memory 104 for carrying out the present invention includes reading from a recording medium 108 such as a magnetic disk, CD-ROM, or DVD, reading from a data storage device 107, and via a remote connection ( For example, via a network). As another embodiment, the present invention may be implemented using a wired circuit instead of, or in combination with, software instructions. Thus, the present invention is not limited to any particular combination of hardware circuits and software.

The document processing apparatus 100 may be a computer system. In this case, the document is generated by an application program, for example, a word processing program, an e-mail program, a spreadsheet program, and the like. Document processing device 100 may be a copier, fax device, or printer that stores a copy of the processed document. For example, a copier can store an image of a copied document. Some fax machines can store images of transmitted or received documents. Some printers can store copies of printed documents.

In one embodiment, document processing device 100 is an image-based file system that digitally stores paper documents in the form of electronic documents. Converting paper documents to file images makes access to information easier than manual systems such as cabinets and archives.

FIG. 2 shows an embodiment of a document processing system having a plurality of document processing devices. This document processing system is shown in a form in which a plurality of document processing apparatuses are interconnected by a network. However, a document processing system can be configured with only one such device.

In one embodiment, network 200 is a local area network interconnecting a plurality of document processing devices and other computing devices. However, other types of networks may be used. For example, the network 200 may be the Internet or another wide area network.

Copier 210 is a document copying device that can store documents in database 240 or other internal or external storage. Copier 210 is connected to network 200 for communication of copied document images and control information and other information. The document is stored on the network 20 for further processing or other purposes.
0 can be transmitted to other devices. In one embodiment, documents copied by copier 210 are stored in database 240 for later retrieval. By storing the processed document, the paper manuscript of that document is no longer needed. When the document is needed, an electronic document of the document can be retrieved from the database 240.

The fax machine 220 is also connected to the network 20
Connected to 0. The fax device 220 stores a copy of the transmitted / received document in the database 240 or an internal or external storage device. For example, a document can be retrieved directly from the database 240 and sent by the fax device 220 without the need for a paper document. Similarly, the printer 250 is connected to the network 2
00, or documents retrieved from the database 240 or other storage device.

The computer system 230 can be of any type and can be used for document matching according to the present invention. Computer system 230
Alternatively, a scanner (not shown in FIG. 2) for converting a physical document into an electronic document may be connected. Printer 250 may be, for example, a printer that stores documents in database 240 or retrieves documents from database 240. In one embodiment, a single device is copier 21
0, the functions of the fax device 220 and the printer 250 are provided.

For performing the document matching according to the present invention, any of the document processing apparatuses shown in FIG. 2 may be used.
For example, computer system 230 can generate structural information based on a document and search database 240 for a matching document. Other devices can be used for document matching as well.

FIG. 3 is a block diagram showing an example of the document search system according to the present invention. In FIG. 3, reference numeral 300 denotes a target document, 310 denotes a document search device, 320 denotes a database, and 330 denotes an output device. The block diagram shown in FIG. 3 shows a system that performs both matching between a physical document and an electronic document and matching between electronic documents. Using document graphic features or components for document matching, one or more stored electronic documents having the same or similar graphic components or features can be retrieved. Such features include, but are not limited to, graphics, lines, shapes, textures, sizes, and other features.

The target document 300 can be a physical document or an electronic document. Target document 300
Has some graphic features in common with the electronic document to be searched. For example, in the target document 300,
It may contain a block diagram of a particular system. The block diagram in this target document 300 is
Other documents containing the same or similar block diagrams,
For example, it can be used to search for technical reports, presentation slides, patent application documents, and the like.

When the target document 300 is a physical document, the document search device 310 includes a device capable of converting the physical document into an electronic document, for example, a scanner or a facsimile device. The document search device 310 may be, for example, a computer system, a scanner, a copier, and the like. The target document 300 is an electronic document created by the document search device 310 or another electronic document. The target document 300 is processed for document matching, and the processing will be described in detail below.

FIG. 4 is a flowchart showing an outline of the processing of the document search apparatus 310. The document retrieval device 310 fetches the target document 300 (processing block 350), and describes the target document 300 or obtains the target document 300 to determine the structural information contained therein.
Is analyzed (processing block 351). In one embodiment, the generated structural information is a set of points characterizing target document 300. The document search device 300 stores the structure information generated from the target document 300 in the database 3
A comparison is made with a similar set of structural information describing the set of electronic documents stored in 20 (processing block 352). The comparison, that is, one or more stored electronic documents that are determined to match in the document structure information matching are retrieved from the database 320 and output by the output device 330 (processing block 353).

In one embodiment, the Hausdorff method is used for matching between point sets as structural information, the details of which will be described later. For more information on the Hausdorff Act, see Huttenlocher, Klan
derman & Rucklidge, ”Comparing Images Using the H
ausdorff Distance, ”IEEE Transactionson Pattern An
alysis and Machine Intelligence, V. 15, September
1993, pgs. 8,50-863.

The document whose structure information matches is output to the output device 330.
Output by The output device 330 may be, for example, an electronic display device such as a liquid crystal display or a CRT. The output device 330 may be a device that outputs a physical document, such as a printer or a fax device. In another embodiment, output device 330 is a device that sends an electronic document over a communication channel.

FIG. 5 is a flowchart showing an example of a structure information generating process when a target document is provided as a physical document. The processing shown in FIG. 5 is executed by processing logic to generate structural information that can be used for matching between the target document and the stored electronic document. In one embodiment, the processing logic comprises software running on a dedicated or general-purpose computer system or computer, dedicated hardware, or a combination thereof.

A description will be given with reference to FIG. Processing logic converts a physical document into a target electronic document (processing block 410). This conversion may be performed, for example, using a scanner in a manner well known in the art. This conversion may be performed by making a copy at the copier or receiving or sending a fax at a fax machine,
In this case, the electronic document of the copied or faxed document is automatically saved. In one embodiment, the device utilized to convert the physical document to an electronic document uses a copy of the electronic document in its own database or in a database in another device accessed through a bus or network connection. (Not shown in FIG. 5).

Next, processing logic deletes text from the target electronic document (processing block 42).
0). Since only the structural information remains after the text is deleted, a search based on the graphic characteristics of the document and not affected by the text content of the document becomes possible.
In one embodiment, the target electronic document is downsampled after text deletion (not shown in FIG. 5). In one embodiment, this downsampling is performed at 144 dpi.

Next, processing logic detects connected components or other graphical features (processing block 430). In one embodiment, only one set of connected components or non-connected components is used for identifying a search target document. Multiple components may be searched simultaneously. These features of the figure are used for searching for similar figures.

The connection component is used as a characteristic component of the target electronic document. Document matching may be performed without limiting the structure of interest to only one large connected component. If only one component is used, the amount of processing required for matching can be reduced, thereby increasing the matching speed of the system. In one embodiment, the target electronic document is downsampled after detecting a connected component (not shown in FIG. 5). In one embodiment, the downsampling rate is 72 dpi.

Next, processing logic detects the endpoint of the line segment (processing block 440). One of the end point detection methods is
Smith, S.M and Brady, JM, ”SUSAN-A New Approach
toLow Level Image Processing, ”International Jou
rnal of Computer Vision, 23 (1), pp. 45-78, May 1997
Is described in detail. Other end point detection methods may be used. For example, a method of convolving an image using a mask design and detecting the end point of a line may be used. The result of the convolution is subjected to threshold processing, and a match is determined based on whether or not the threshold has been exceeded. Many other feature extraction methods can be used.

Processing logic generates structural information based on endpoints that are graphic features (processing block 450). In one embodiment, the structure information is a set of points corresponding to the endpoints of the line segment. However, for example, but not limited to, other structure information such as line segments and curves may be used.

The generated structure information of the target electronic document can be used for matching between the target electronic document and the stored electronic document. In one embodiment, structural features describing the stored electronic document are compared to structural information describing the target electronic document. The structure information of the stored electronic document may be stored prior to the document matching process, or may be generated in real time. When the structural information matches within a predetermined allowable range, the corresponding stored electronic document is regarded as a matching document. The matching document can be extracted and used by the user.

In one embodiment, matching is performed by the Hausdorff method. Assuming two point sets A = {a1, ..., am} B = {b1, ..., bn}, the Hausdorff distance is

(Equation 1) It is. here,

(Equation 2) The function h (A, B) is the directed Hausdorff distance from A to B, finds the point a∈A farthest from all points in B, and the distance from a to the nearest point in B Weigh The Hausdorff distance H (A, B) represents the distance between the point A farthest from all points of B and the point B farthest from all points of A. Is a measure of

That is, if the Hausdorff distance is d, every point of A is within a distance d from a point of B, and similarly, every point of B is within a distance d of a point of a. is there. In one embodiment, when the Hausdorff distance is equal to or smaller than a certain allowable error value, it is determined that they match. Instead of this method, another matching method may be used.

FIG. 6 is a flowchart showing an example of a structure information generation process when a target document is provided as a file in a page description language such as PostScript. The processing logic as described above executes this structure information generation process. The process illustrated in FIG. 6 represents generation of structural information for one page of an electronic document. In one embodiment, each page of the document is analyzed in a similar manner. This process may also be applied to stored electronic documents that are compared to target documents.

Processing logic first splits the target electronic document into pages (processing block 510). In one embodiment, structure information is generated for each page. Instead, structure information describing the target electronic document may be generated using a plurality of pages. In one embodiment, graphics that span multiple pages may be handled. In one embodiment, Po
An explicit page break command is included in the stScript file. With these commands, figures spanning a plurality of pages can be processed one page at a time. But other
PostScript implementations and other page description languages may be able to detect graphics that span page breaks and perform feature matching on such graphics as a group.

Next, processing logic determines whether each command generates a line segment (processing block 52).
0). In one embodiment, a page description language (eg, PostScri
pt) is analyzed to determine whether a line segment is generated. When using PostScript as an example, li
Commands such as neto, rlineto, and moveto are determined to be commands for generating line segments.

If the command generates a line segment, processing logic detects the endpoint of the line segment (processing block 530). If the command does not generate a line segment, the command is ignored (processing block 540). Processing logic repeats the parsing process until the end of the page is reached (processing block 550). A similar process is performed for each page of the target electronic document (not shown in FIG. 6).

Note that this analysis process may not be completely static. PostScript is a programming language. In one embodiment, the PostScript interpreter is executed with specially modified logic, which allows
The end point is output each time the neto command is executed. The reason is that a command that draws a line from (x, y) to (x + day, y) (the date cannot be determined until execution)
May be included in the PostScript instruction. This produces a "perfect" feature set that is not affected by existing digitizing noise when such features are detected from the image.

Processing logic generates structural information based on the detected endpoint (processing block 560). In one embodiment, the structural information is a point set of the endpoints of the line in the page. Of course, different types of structural information may be generated based on line endpoints on the page.

The structural features generated from the electronic document are used in the same manner as the structural information generated from the physical document. The generated structural information is compared to structural information describing one or more stored electronic documents. If an acceptable match is obtained, the corresponding stored document can be retrieved and presented to the user.

FIG. 7 shows an example of a raster image of a document. FIG. 8 shows a graphic extracted by deleting the text of the raster image shown in FIG. FIG. 9 shows a point set generated as the structure information of the graphic feature from the graphic shown in FIG. As is clear from a comparison between FIG. 9 and FIG. 8, the point set generated as the structure information includes the corner points of the rectangle, the end points of the horizontal and vertical lines, and the outline edge of the arrow shown in FIG. Includes the end points of the line segment fitted to. Note that it is also allowed to generate a point set consisting only of rectangular corner points.

The present invention has been described with reference to the embodiments. However, it is clear that various modifications and changes to the embodiments are possible. Therefore, the specification and drawings are to be understood as being illustrative rather than limiting on the present invention.

[0052]

According to the first, second, third, seventh, eighth or ninth aspect of the present invention, it is possible to efficiently retrieve documents having the same or similar visual structure such as figures and tables in the documents. And such a document search that is not affected by the text content in the document is possible. According to the fourth, fifth, or sixth aspect of the invention, it is possible to obtain such effects that such a document search can be easily executed using a general computer.

[Brief description of the drawings]

FIG. 1 is a block diagram illustrating an example of a document processing apparatus for implementing the present invention.

FIG. 2 is a diagram illustrating an example of a document processing system having a plurality of document processing apparatuses.

FIG. 3 is a block diagram showing an example of a document search system according to the present invention.

FIG. 4 is a flowchart showing an outline of a document search process according to the present invention.

FIG. 5 is a flowchart illustrating an example of a process of generating structure information of a target document provided as a physical document.

FIG. 6 is a flowchart illustrating an example of a process of generating structure information of a target document given as a file in a page description language.

FIG. 7 is a diagram illustrating an example of a raster image of a target document.

8 is a diagram illustrating an example of a graphic extracted by deleting text from the raster image of FIG. 7;

FIG. 9 is a diagram illustrating an example of a point set generated from the graphic in FIG. 8;

[Explanation of symbols]

 REFERENCE SIGNS LIST 100 document processing device 101 bus 102 processor 104 main memory 106 ROM 107 data storage device 108 recording medium 109 drive 121 display device 125 input device 200 network 210 copier 220 fax device 230 computer system 240 database 250 printer 300 target document 310 document search device 320 Database 330 Output device

Claims (9)

[Claims] 1. A method for deleting text from a raster image of a target document, generating a point set corresponding to the remaining components as structure information describing the target document, and generating structure information describing the generated target document, The stored electronic document is compared with a set of structural information describing a set of stored electronic documents, and when the structural information describing the stored document matches the structural information describing the target document within a predetermined tolerance. Extracting one or more stored electronic documents from a set of documents. 2. An end point that describes a line for a command in a page description language file of the target document is determined, and a point set corresponding to the determined end point is generated as structure information describing the target document. The structural information describing the document is compared with a set of structural information describing a set of stored electronic documents, and the structural information describing the stored document matches the structural information describing the target document within a predetermined tolerance. Extracting one or more stored electronic documents from the set of stored electronic documents. 3. The document search method according to claim 1, wherein the structural information is compared by the Hausdorff method. 4. A process for deleting text from a raster image of a target document and generating a point set corresponding to the remaining components as structure information describing the target document. A process of comparing with a set of structural information describing a set of documents, when the structural information describing the stored document matches with the structural information describing the target document within a predetermined allowable error range, A computer-readable recording medium on which a program for causing a computer to execute a process of extracting one or more stored electronic documents from a set is recorded. 5. A process for obtaining an end point for describing a line for a command in a page description language file of a target document, and generating a point set corresponding to the obtained end point as structure information for describing the target document. A process of comparing the described structural information with a set of structural information describing a set of stored electronic documents, wherein the structural information describing the stored document matches the structural information describing the target document within a predetermined tolerance. A computer-readable recording medium having recorded thereon a program for causing a computer to execute a process of extracting one or more stored electronic documents from the set of stored electronic documents. 6. The computer-readable recording medium according to claim 4, wherein the structural information is compared by the Hausdorff method. 7. A means for receiving a raster image of a target document, deleting text from the raster image, and generating a point set corresponding to the remaining components as structural information describing the target document, describing the target document. Means for comparing the structure information with a set of structure information describing a set of stored electronic documents; and when the structure information describing the stored document matches within a predetermined tolerance a structure information describing the target document. A means for extracting one or more stored electronic documents from the set of stored electronic documents. 8. A means for receiving a page description language file of a target document, obtaining an endpoint describing a line for a command in the file, and generating a point set corresponding to the determined endpoint as structure information describing the target document. Means for comparing the structural information describing the target document with a set of structural information describing a set of stored electronic documents, wherein the structural information describing the stored document is different from the structural information describing the target document by a predetermined allowable error. A document processing search device, comprising: means for extracting one or more stored electronic documents from the set of stored electronic documents when they match within the range. 9. The document search apparatus according to claim 7, wherein said means for comparing structural information compares structural information by the Hausdorff method.