JPH0740268B2 - Document matching device - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION [Industrial field of application] The present invention is a document that uses a large-capacity storage device such as an optical disk device to convert paper surface information of a printed matter or the like into raw or character information and stores it. Regarding the filing device,
The present invention relates to a method of constructing index information used when extracting a stored document.

[Conventional technology]

Conventionally, when storing a document in a document filing apparatus, the page information is converted into an electric signal by a scanner or the like and input from the original information, and independently of this, language information such as a heading representing the page information, that is, a keyword. After the human character inputs the character string information such as, for example, from a keyboard separately, both of them are accumulated. To retrieve a document that should have been stored, relying on human memory etc., humans also enter character string information that was supposed to have been given at the time of storage from the keyboard etc. It uses the method of obtaining the information page.

[Problems to be solved by the invention]

By the way, although the character string information as a keyword is excellent in accuracy, it is difficult to accurately recall the character string information given at the time of character storage because of the diversity of natural language and the ambiguity of human memory. . Therefore, trial and error are likely to occur during the document retrieval operation in the large-volume document storage device, and the retrieval operation is only realized at an actual speed extremely slow as compared with the speed based on the hardware performance thereof.

Also, as another conventional method, there is a method of using a typical drawing associated with a document as an index, but there is a drawback that the index has too much information and is not practical. As another method, as in Japanese Patent Application No. 58-199572, a method of displaying an original document at high speed can be considered, but even that is a method effective only in a partial area inside a specified file. Nothing more.

An object of the present invention is to provide a document filing device which solves the conventional problem that the index is only the character string information and is inconvenient, and can use relatively stable (memorable) image information as human memory information. It is in.

[Means and Actions for Solving Problems]

The document filing apparatus of the present invention divides the read document sheet surface into a plurality of areas by reading the document, storing the read document, and determining the attributes of each area from the physical characteristics of the area. When the attributes of the divided areas are not determined, the area is further divided into a plurality of small areas, and the means for repeatedly obtaining the attributes of the small areas until the attributes are determined, and the obtained attributes of each area and small area. And a means for storing the set of (1) as the index of the read document in association with the corresponding document.

That is, the present invention, by measuring and calculating the physical constants of the input document paper in a layered manner, and storing the main numerical values obtained as a result in the index storage means and the index storage means. When retrieving a document, it is possible to specify a keyword and a physical constant on the paper so that a desired document can be retrieved quickly and accurately from a large amount of stored documents.

〔Example〕

FIG. 1 shows the overall configuration of an embodiment of the document filing apparatus of the present invention. The image scanner 1 reads the document paper surface as black and white binary information. The image buffer 2 temporarily stores the document data read by the image scanner 1.
In this embodiment, the image buffer 2 is 1728 dots × 2304.
Suppose it consists of lines. The buffer control circuit 3 controls the image buffer 2 and the switching circuit 4 to divide the central portion (1024 dots × 1536 lines) of the input document data of the image buffer 2 excluding the blank portion into N pieces, and the switching circuit 4 To sequentially output to the image data bus 9. In this embodiment, N = 6. The information companding circuit 10 is a circuit for compressing / decompressing document data. The document data storage device 110 stores the document data compressed by the information companding circuit 10. The document data read from the document data storage device 110 is
On the contrary, it is expanded by the information companding circuit 10 and displayed on the CRT display device 112. The index data storage device 111 stores an index for the document data of the document data storage device 110.

The horizontal peripheral distribution counting circuit 5 counts the horizontal peripheral distribution of each divided area and stores it in the memory 51. The vertical marginal distribution counting circuit 6 similarly calculates the vertical marginal distribution and stores it in the memory 61. The horizontal run length counting circuit 7 calculates the horizontal run length of each of the divided areas, and the memory 71 or
Store in 72. The vertical run length counting circuit 8 similarly calculates the vertical run length and stores it in the memory 81 or 82. The fast Fourier transform circuit 32 is for performing Fourier transform processing at high speed independently of the CPU 100. CPU100
Is a microprocessor, for example, and executes most of the processing for generating an index corresponding to document data.
The operation will be described below.

The reading CPU 100 issues a reading command to the image scanner 1 via the bus 101, reads the document original inserted in the scanner 1, and temporarily stores it in the image buffer 2 as monochrome binary data (1728 dots × 2304 lines).

This page space information is stored and saved in the document data storage device 110 via the information companding circuit 10, but independently of this, the second
As shown in the figure, only 1024 dots × 1536 lines in the central portion of the paper are stored in the image buffer 2 for the feature extraction operation.

The divided image buffer control circuit 3 firstly outputs the binary data of 512 dots × 512 lines (corresponding to 1/6 of the central portion of the paper) corresponding to the upper left area 1 of the document paper shown in FIG. 2 in the horizontal direction. It scans and outputs to the image data bus 9 one after another. After that, the image buffer control circuit 3 vertically scans the binary data corresponding to the upper left of the same document paper surface and outputs it to the image data bus 9 one after another. Less than,
This is repeated for regions 2-6.

Horizontal distribution and run length The horizontal peripheral distribution circuit 5 integrates the number of black pixels in each horizontal line of the divided image data and stores the value in the memory 51 for 512 lines. At the same time, the horizontal run length counting circuit 7 individually measures the run lengths in one horizontal line, averages the values and stores them in the memory 71, and at the same time calculates the variance and simultaneously calculates the memory 72. Store in. This operation is repeated for 512 lines.
Similarly, also in the vertical direction, the number of black pixels and the average / dispersion of the run lengths are calculated by the vertical peripheral distribution circuit 6 and the vertical run length counter 8 and stored in the memories 61, 81 and 82, respectively. This operation is repeated for 512 lines.

Feature vector Horizontal marginal distribution vector by the series of horizontal and vertical operations
Ph (512 elements), vertical marginal distribution vector Pv (512 elements),
This means that four vectors, the run length average value vector Lr (horizontal black run average, vertical black run average) and the run length variance vector Lv (horizontal run variance, vertical run variance) are available. At this time, the number of dimensions of each vector is 51
It is 2,512,2,2. These four vectors are generated as a set of four for each of the six-divided paper of FIG. as a result,
Six sets and 24 sets of vectors are transferred to the CPU 100 via the bus 101 for each page of the paper. These vectors have too much data for this index, and
Since it is also inconvenient for classification, the CPU 100 further converts it into a representative value as follows.

Representation of marginal distribution First, as is well known, marginal distribution vectors P generated in two sets per one area of a paper surface divided into six can be considered as two marginal distribution curves (vertical and horizontal) of a monovalent function, It can be represented by an average value Pm and a variance Vp of two each. These are horizontal
There are a total of two sets of vertical, but the horizontal marginal distribution average value Pmh and the vertical marginal distribution average value Pmv are, by definition, Pmh = Pmv, and the value is the average brightness of the paper surface (number of black pixels / total number of pixels). Proportional to. Therefore, both of them will be referred to as the average brightness Pm. By doing this, the arithmetic features of the marginal distribution are
It can be aggregated into a three-dimensional vector P (Pm, Vpv, Vph). Physically, the average brightness expresses the degree of concentration of the black portion.

Next, the periodic features of the marginal distribution are extracted using the FFT (Fast Fourier Transform) as follows. Based on the command, the CPU 100 uses the data group of the horizontal peripheral distribution vector Ph (for example, 51
2) from the horizontal distribution memory 51 to the FFT operation circuit 32,
Perform FFT operation. The CPU 100 sucks only the result via the bus 101, and then obtains the representative lateral frequency Fh.

Similarly, the representative vertical frequency Pv is obtained from the vertical marginal distribution vector. With these as elements, the frequency feature vector (Fh, F
v) is defined.

As described above, the physical parameters based on the peripheral distribution are aggregated into two vectors (scalar amount: five). Next, the parameterization based on the run length is performed.

Representation of run lengths Previously, it was shown that the information on run lengths is aggregated into four scalar quantities of white run, black run average Lrw and Lrb, and variances Lvh and Lvb. The run vector L having these elements can be expressed by L (Lrw, Lrb), and the run dispersion vector Lv can be expressed by Lv (Lvh, Lvb). That is, the four scalar quantities are aggregated into two vectors. Physically,
It expresses the connection tendency of black pixels in the entire area and detects photographs and charts.

Index amount If one scalar parameter is represented by 2 bytes, 18 bytes of index information consisting of 4 vectors can be generated. This 18-byte index information is 18 x 6 = 108 bytes because 6 sets can be created per page when the page is divided into 6 pages, and up to this point, it is not suitable for storage as an index. Turn into.

Area Category Determination The 6-divided area of interest is classified into one of four categories such as blank, diagram, character string, and photo by the following method. We will not span two categories. That is, the model that the document is composed of the above-mentioned four kinds of elements is adopted.

Blank: It is regarded as blank when the average density Pm is smaller than 1 × 10 ^-2 . However, in order to distinguish it from a line drawing, those with a black run length variance of greater than 1 × 10 ² are excluded.

Line drawing: A line drawing is considered when the average density Pm is smaller than 1 × 10 ^-1 . However, in order to distinguish it from the blank, those with a black run length variance of less than 1 × 10 ² are excluded.

Character string: Determined by two-dimensional space mapping of frequency feature vector. As shown in FIG. 3, if any of the coordinates is in the portion where the frequency is higher than 10, it is regarded as a character string. This utilizes line configuration information. In addition, the run vector is analyzed, and the condition that the average of black runs is less than 5 is used, and the fact that the runs are short in the character portion is used. Furthermore, when it is close to either of the two axes, it can be regarded as a vertical / horizontal format. In FIG. 3, one circle corresponds to one divided area, a white circle is a character string or a table, and a black circle is other (drawing,
Graphs, photos, etc.). Frequency 1 corresponds to a case where the right half surface of the screen is blank and the left half surface is black.

Photo sequence: A photo is considered to have an average density Pm larger than 1 × 10 ^-1 . Further, the run vector is inspected, and the condition is that the black run average is greater than 5 both horizontally and vertically.

Hierarchization of Area Attribute Judgment Of course, in most cases, the category is not decided by the above-mentioned first hierarchy decision operation because a plurality of kinds of elements are mixed in the 6-divided area. In that case,
The area of 512x512 pixels is further decomposed into 4 and 128x128 area 4
Disassemble into individual pieces. The second layer determination operation is further performed on this decomposition area to perform the category determination. The case where all four categories of the four decomposition areas match each other is defined as the identification of the first layer.

If this is still unclear, divide the decomposition area for an additional 4 minutes and
It is subdivided into x64 and the third layer judgment operation is performed. And so on
It is determined that the Nth layer is obtained by four coincidences of the N + 1th layer. FIG. 4 is a diagram explaining this.

Description of judgment result Assign symbols S, G, C, P to blanks, line drawings, character strings, photographs, etc. For example, if all 6 divided areas are character strings, sample document 1 = C is expressed. Expresses that elements other than character strings are not included. This is called the 0th layer display.

For example, if the lower two places (areas 5 and 6) in Fig. 2 are the screen and the photograph, describe as sample document 2 = X, CCCCGP (X is an uncategorized display), and display the mixed document in the 0th layer display. This is indicated by X, and more specifically, it is displayed that the six areas are sequentially composed of the character string 4, the line drawing 1, and the proportion of the photograph 1. This is the first
This is called layer display.

Documents that are not found in the first hierarchy are described as follows. Fourth
As shown in the figure, if the photograph in the lower part of the sample document 2 is slightly large and protrudes into the area 4, the margin and a part of the photograph are mixed in the area 4, and there may be a case where the unique determination cannot be made. . In such a case, describe as sample document 3 = X, CCCXGP, ... And continue displaying the second layer information.

Assuming that the upper half is blank and the lower half is almost a photograph in the four decomposition areas of the second layer, the sample document 3 is displayed as sample document 3 = X, CCCXGP, SSGG.

If it is not known up to the second layer, for example, if the lower right of the four decomposition areas in the above example is a mixture of margins and photos, describe the third layer further and sample document 4 = X, CCCXGP, SSGX, SSGG Write .. In this case, it is not always necessary to specify the hierarchical level, and sample document 4 = XCCCXGPSSGXSSGG may be simply described to extend the symbol as follows. This is because the first symbol is always present, the following symbols are always 6, and the second and subsequent layers are always separated by 4.
This is also because the lower hierarchy is described in the same order as the indefinite symbol X.

Indexing of determination result Since the notation of one symbol described above indicates a total of 5 states of the category category 4 and the category unknown number 1, a total of 1 states, a minimum of 3 bits is required. Considering the matching with the processing device,
Although 4 bits is close to this, it will be described with 8 bits (1 byte) after considering the future expansion of the number of categories. That is, the notation character string is treated as the index symbol string.

When this is done, the amount of information in the index is 1 byte / page for "divided" and 1 for the first layer.
+6 (byte), 1 + 6 + when detailed in the second layer
4 × n (n ≧ 6), 1 when detailed up to the third layer
+ 6 + 4 × n + 4 × m (m ≦ 4), which is 47 bytes / page at the maximum when the third layer is used. The use of the fourth layer and below causes the size to be further increased, and is not used for any purpose other than the special purpose.

The index symbol string thus generated can be classified in the same manner as the conventional keyword character string. For example, when the letters assigned to the category symbols are alphabets, the index symbol string can be sorted and sorted just like keywords. This is extremely advantageous for efficient retrieval at a later date.

If this index symbol string is regarded as a numerical value string, several vectors can be generated in each layer, and this will be called a feature vector set A. A ₀ = a ₀ A ₁ = (a ₁₁ ,, a ₁₂ , a ₁₃ , a ₁₄ , a ₁₃ , a ₁₄ ) A ₂ ＝ (a ₂₁ , a ₂₂ , a ₂₃ , a ₂₄ ) ・ A _m ＝ (a _m1,, a _m2 , a _m3 , a _m4 ), where a _mn is described as a symbol S, G, C, PX and a one-to-one numerical value.
When the m-th layer vector exists, this is called an m-th layer feature vector, and the number thereof is generally plural.

Storage of index When a document is stored, it is common to add a plurality of keywords for retrieval at a later date, and this keyword is also stored in this embodiment. That is, the date, the document name, etc. are stored in the index data storage device 111 in a character string format by a known method.

Since the feature vector is no longer represented by the same character string as the keyword, it is stored immediately after the keyword storage area. When the m-th layer vector exists, it is continuously stored and saved. In this case, in order to realize an effective high-speed search, it is common practice to generate a keyword index file in which only keywords are classified and rearranged. Needless to say, if a feature vector index file is generated in the index data storage device 111 for the same purpose, the processing speed at the time of executing a search operation at a later date is increased. In addition,
The index data storage device 111 is the document data storage device 110.
Together with the same memory.

This completes the document storage operation and the associated saving of the search index.

Retrieving Documents When retrieving documents, first enter keywords from a keyboard based on human memory to narrow down candidate documents. Up to this point, a conventionally known technique is used. In the case where the narrowed-down result is not single or not at all, the conventional method is to approach the target document while changing the input keyword by trial and error. In this embodiment, the process continues as follows.

Input of example page and feature extraction After inputting the keyword, the example page based on memory is entered. In principle, prepare a blank sheet of the same size as the target document, draw a 1-page layout stored in the target document with a writing instrument, insert it into the scanner 1,
The parameterization operation is performed in the same procedure as when storing the document.

Actually, instead of the operation of drawing on paper, a known means similar to CAD (Computer Aided Design) or a word processor with a drawing function is used to create an example paper surface only by the operation on the CRT. When creating the example paper, write vertically / horizontally,
It goes without saying that it is desirable to include format information such as line pitch, drawing / photograph, and margin position. The feature vector E is calculated for each of the six divided areas of the exemplary paper surface data created in this way, in the same manner as when the document was stored.
When E is only the 0th layer, when any one of E = S, C, G, P is up to the 1st layer, E ₁ = (e ₁₁ , e ₁₂ , e ₁₃ , e ₁₄ , e ₁₅ , e ₁₆ ), and up to the mth layer, E _m = (e _m1 , e _m2 , e _m2 , e _m4 ), where e _mn is a numerical value that has a one-to-one correspondence with the symbols S, G, C, P, X Ask for.

Parameter comparison method When S _m is one of the feature vector m-th layer of the candidate document,
A distance vector D _m indicating a difference from the vector E _{m of the} example document is defined by D _m = S _m -S _m . Furthermore, the distance function | D _m | when the vector indefinite element X is not included is It is defined as That is, | D ₁ | = 0 means that the candidate and the example attributes are the same in all six areas on one page, and | D ₁ |
| = 6 means that the attributes are different in all areas.

On the other hand, the distance function | D _m | when X is included in the vector can be defined by the following extension. The feature vector m including X
Since the layer must be accompanied by the feature vector m + 1th layer, if this is expressed as a vector S _m1 , for example, S _m1 = (CCGP) can be immediately obtained. On the other hand, since E _m does not include the indefinite symbol X, the feature vector m + 1-th layer is not attached, but it is obvious that all four elements of the 6-divided region were e _m .
For example, write E _{m + 1} = (CCCC). The extended distance function | D _m | is defined by the following equation. As before, the distance function is And δ _x requires an operation including the indefinite element X. Then δ _x If all four elements under one hierarchy are different, | D _m | = 1, and if all are the same, | D _m |
= 0.

With the above definition, the size of | D | well expresses the degree of approximation between the candidate document and the example document. Therefore, if | D | is calculated for all of the candidate documents and only candidate documents having a constant value, for example, 1 or less are left, only documents having a close appearance will remain. Further, it is possible to search at higher speed by searching the feature vector index file that has been sorted and sorted at the time of storing the document without checking all candidate documents.

The final specification CPU 100 searches the indexes one after another while calculating the degree of approximation with the example sheet by the value of the distance vector, and leaves only the candidates of | D | = 0. The original document data found as a result is taken out from the storage device 110, the original document is displayed on the CRT display device 112 via the information companding circuit 10, and the person makes the final identification and ends the document.

Also, if | D | = 0 and no document remains, | D | <1.25
Is displayed, and if not, the range is expanded to | D | <1.5 …… and left to human judgment.

As described above, in the embodiment, the original document paper surface division number of 6 and the subdivision number of 4 are adopted, but other values may be used depending on the size of the paper surface, the aspect ratio, and the like. Further, although the fast Fourier transform is used for the frequency component conversion, other orthogonal transforms such as the Hadamard transform may be used. Further, narrowing down by the characteristic index may be preceded before narrowing down by the keyword.

〔The invention's effect〕

As described above, according to the present invention, not only the keyword but also the appearance of the document sheet and the layout information can be finely incorporated by the area attribute determination in a hierarchical manner as the index. In comparison, it is possible to effectively find a desired document from a large number of documents. In addition, even if a keyword is completely forgotten, there is an advantage that a desired document can be easily found in a self-made report or the like that often remembers the outline of the paper. Furthermore, when storing a document in a personal binder, folder, etc. in the electronic file system, the binder name,
There is an advantage that it is possible to use only the automatically generated feature index without adding any special keywords other than the folder name.

In addition, the function of being able to classify a document by capturing it mainly from the physical side of its appearance, that is, its appearance,
It is paired with the classification function from the aspect of conceptual information,
Contributes to the automation of document processing, which accounts for the majority of paperwork.

These advantages are high convenience of the electronic file system considering that human beings often use both the extracted non-verbal information and the extracted linguistic information to capture and think of images, which is the case for human beings. It can be said that this is extremely effective for

[Brief description of drawings]

FIG. 1 is an overall configuration diagram of an embodiment of the present invention, FIG. 2 is a diagram showing an example of document page division, FIG. 3 is a conceptual diagram of character string region feature extraction, and FIG. 4 is a document page hierarchy. It is a schematic diagram of a structure display. 1 ... Scanner, 2 ... Image buffer memory, 3 ...
... buffer control circuit, 4 switching circuit, 5 horizontal peripheral distribution counting circuit, 6 vertical peripheral distribution counting circuit, 7
Horizontal run length counting circuit, 8 ... Vertical run length counting circuit, 9 ... Image data bus, 10 ... Information companding circuit, 32 ... Fast Fourier transform circuit, 100 ... Microcomputer, 101 ... Control data bus , 110 ... Document data storage device, 111 ... Index data storage device, 112 ...
… CRT display.

Claims (2)

[Claims] 1. A device for reading a document, a device for storing the read document, a device for dividing the read paper surface into a plurality of areas, and obtaining the attributes of each area from the physical characteristics thereof.
When the attributes of the divided areas are not determined, the area is further divided into a plurality of small areas, and the means for repeatedly obtaining the attributes of the small areas until the attributes are determined, and the obtained attributes of each area and small area. And a means for storing the set of (1) as the index of the read document in association with the corresponding document. 2. The document filing apparatus according to claim 1, further comprising means for inputting an exemplary paper surface,
The similarity between the means for obtaining the index of the example sheet and the index of the example sheet and the stored index is calculated by operating the means for dividing the example sheet to obtain the attribute, and the similarity is constant. A document filing apparatus provided with means for extracting an original document within a range.