JP4504702B2 - Document processing apparatus, document processing method, and document processing program - Google Patents

Description

  The present invention aims at obtaining a search key that characterizes a document without recognizing characters, and by focusing on the result of summarizing the characteristics representing the arrangement state of the in-line rectangles of the character line, The present invention relates to a document processing apparatus, a document processing method, and a document processing program for extracting shape features.

  Conventionally, a technique for extracting and outputting a character line from a circumscribed rectangle of a character component in a document image has been proposed. This technique extracts a character line by applying a plurality of restrictions on features (size, spacing, etc.) related to the shape and position of a circumscribed rectangle of a character (see, for example, Patent Documents 1 to 5). ).

International Publication No. 00/62243 Pamphlet Japanese Patent Laid-Open No. 11-143879 JP 11-219407 A JP-A-9-231317 JP-A-8-161430

  However, in the above prior art, in order to determine a character line, it is necessary to manually adjust a plurality of constraints related to the circumscribed rectangle to the optimum values. In addition, although the character likelihood can be determined, characteristics relating to the contents of the character line cannot be obtained.

  In order to solve the above-described problems, the present invention extracts features representing the arrangement state of in-line rectangles in a character line image, generates symbols by quantizing these in a fixed stage, and without recognizing characters. It is an object of the present invention to provide a document processing apparatus, a document processing method, and a document processing program that enable extraction of the characteristics of a character line and perform an efficient search regarding the contents of the character line.

In order to solve the above-described problems and achieve the object, a document processing apparatus according to claim 1 of the present invention performs predetermined image processing on an input document image, extracts image features, and performs document processing. An in-line height symbol generating means for generating a fixed type symbol by quantizing a height in a line of a starting point of an in-line rectangle of a character line image extracted from the document image into a fixed stage; and the character A line height estimating means for estimating the line height of the line image; and an in-line rectangular height ratio symbol generating means for generating a fixed type symbol by quantizing the ratio of the height of the in-line rectangle to the line height in a fixed stage; In-line rectangular width ratio symbol generating means for generating a fixed type symbol by quantizing the ratio of the width of the in-line rectangle to the line height in a fixed stage, and a fixed type by quantizing the black pixel density in the rectangle in the fixed stage The Black pixel density symbol generating means for generating Bol, appearance frequency totaling means for converting features representing the arrangement state of in-line rectangles in a test row into a symbol series, and summing up the appearance frequency of symbols in the test row, and the appearance frequency totalization And similarity determination means for determining similarity based on the appearance frequency of symbols aggregated by the means and the arrangement tendency of the symbol series learned in advance.

  According to the first aspect of the present invention, the character representing the arrangement state of the in-line rectangle of the character line image is extracted, and these are quantized to a fixed stage to generate a symbol, so that the character can be recognized without recognizing the character. Line features can be extracted, and an efficient search for the contents of character lines can be performed.

  According to a second aspect of the present invention, the document processing apparatus according to the first aspect further extracts one or more representative ones from a plurality of features representing the arrangement state of the in-line rectangle, and based on the extracted one. And a representative symbol generating means for generating a fixed type of symbol.

  According to the second aspect of the present invention, it is possible to omit the process related to the measurement / recording of the feature of the in-line rectangle which is unnecessary depending on the search target, and more efficient document processing can be performed.

  According to a third aspect of the present invention, there is provided the document processing apparatus according to the second aspect, wherein the ratio of the distance between the target rectangle and the adjacent rectangle with respect to the row height is quantized at a fixed stage to obtain a fixed type symbol. A distance ratio symbol generating means for generating is provided.

  According to the third aspect of the present invention, the character line characteristics can be defined in more detail, and a strict character line determination is possible.

  According to a fourth aspect of the present invention, there is provided the document processing apparatus according to the first aspect, wherein the distance calculation means calculates the distance between the end point of the in-line rectangle of interest and the start point of the adjacent in-line rectangle, and the distance calculation means. A symbol series conversion means for comparing the distance calculated by the step and the line height and inserting a blank symbol to convert the arrangement state of the in-line rectangle into a symbol series when the ratio exceeds a certain value; It is characterized by having.

  According to the fourth aspect of the present invention, when defining the characteristics of a character line, it is possible to determine a character line with higher accuracy by including information on a blank portion in the character line.

  According to a fifth aspect of the present invention, in the document processing apparatus according to the second aspect, the plurality of features representing the arrangement state of the in-line rectangle are vector-quantized corresponding to each dimension of the multi-dimensional vector, and the in-line rectangle is obtained. In-line rectangular arrangement state symbol generating means for generating a fixed type of symbol indicating the arrangement state of is provided.

  According to the fifth aspect of the present invention, it is possible to extract the characteristics of the character line without recognizing the character by vector quantization of the feature representing the arrangement state of the rectangle and converting this to a symbol series. , You can efficiently search for the contents of character lines.

  According to a sixth aspect of the present invention, there is provided the document processing apparatus according to the second aspect, wherein the symbol information of the character line generated by the representative symbol generating means is stored in a specific range such as the entire original or the entire predetermined area. A specific range similarity determination means for determining the similarity between the training document and the test document is provided.

  According to the invention described in claim 6, it is possible to search for the contents of the character line in the predetermined area.

  According to a seventh aspect of the present invention, there is provided the document processing device according to the first aspect, wherein a character input unit, a character font set, and a character text input from the character input unit are used to generate a character based on the character font set. Document image acquisition means for expanding a font into a character image and generating a character string image from a character text string input from the character input means, and generating an in-line rectangular symbol for the character string image Means.

  According to the seventh aspect of the present invention, it is possible to perform a text search on a document image without performing character recognition which has been conventionally performed. Therefore, the character pattern dictionary conventionally required for character recognition becomes unnecessary.

  Further, in the invention according to claim 7, the document processing apparatus according to claim 8 further represents a rectangular arrangement state in the character for each character with respect to the in-line rectangular symbol generated in advance for each character. Symbol correspondence means for associating the symbol to be processed, and rectangular symbol conversion means for converting the character string of the input text input from the character input means into a rectangular symbol series.

  According to the eighth aspect of the present invention, it is possible to directly convert a text character string into an in-line rectangular symbol without passing through a character image, thereby improving processing efficiency.

A document processing apparatus according to claim 9 is an apparatus for performing predetermined image processing on an input document image, extracting image features, and performing document processing, wherein a character extracted from the document image In-line height symbol generating means for generating a fixed type of symbol by quantizing the height of the start point of the in-line rectangle of the line image in a fixed stage, and a line height estimating means for estimating the line height of the character line image Inline rectangle height ratio symbol generation means for generating a fixed type symbol by quantizing the ratio of the height of the inline rectangle to the line height into a fixed stage, and the ratio of the width of the inline rectangle to the line height in a fixed stage An in-line rectangular width ratio symbol generating means for generating a fixed type symbol by quantizing the black pixel density into a fixed stage and generating a fixed type symbol by quantizing the black pixel density in the rectangle to a fixed stage; The training line learning means for converting the feature representing the arrangement state of the in-line rectangle in the training line into a symbol series and learning the tendency thereof, the feature representing the arrangement state of the in-line rectangle in the test line into the symbol series, and the training line Using the learning result of the training line by the learning means, the evaluation value calculating means for calculating the evaluation value of the test line, the learning result of the training line by the training line learning means, and the test line calculated by the evaluation value calculating means And a similarity determination unit that compares the evaluation value and determines the similarity.

  According to the ninth aspect of the present invention, the character representing the arrangement state of the in-line rectangle of the character line image is extracted, and these are quantized to a fixed stage to generate a symbol, so that the character can be recognized without recognizing the character. The feature of the line can be extracted, and the search for the contents of the character line can be performed efficiently.

The document processing apparatus according to claim 10 is a document processing apparatus for determining similarity between character line images extracted from a document image, wherein the height of the start point of an in-line rectangle of the character line image is fixed. The in-line start point height quantizing means for quantizing the character line image, the in-line rectangle height quantizing means for quantizing the height of the in-line rectangle of the character line image in a fixed stage, and the width of the in-line rectangle of the character line image are fixed. In-line rectangular width quantization means for quantizing in stages, the height of the start point of the in-line rectangle quantized by the in-line start height quantization means, and the in-line quantized by the in-line rectangular height quantization means Symbol generation means for generating a symbol from an arrangement state determined based on the height of the rectangle and the width of the in-line rectangle quantized by the in-line rectangle width quantization means, and the symbol generation means generated in the test row. Symbol Appearance frequency totaling means for totaling the appearance frequency, and similarity determination means for determining similarity based on the appearance frequency of the symbols calculated by the appearance frequency totaling means and the arrangement tendency of the symbol series learned in advance. It is characterized by having.

  According to the tenth aspect of the present invention, the character representing the arrangement state of the in-line rectangle of the character line image is extracted, and these are quantized to a fixed stage to generate a symbol, so that the character can be recognized without recognizing the character. The feature of the line can be extracted, and the search for the contents of the character line can be performed efficiently.

A document processing method according to an eleventh aspect is a method performed by a document processing apparatus that performs predetermined image processing on an input document image, extracts image features, and performs document processing. An in-line height symbol generating step in which the document processing apparatus generates a fixed type symbol by quantizing the height in the line of the starting point of the in-line rectangle of the character line image extracted from the document image; and the character line image A line height estimation step for estimating the line height of the line, a line height ratio symbol generation step for generating a fixed type symbol by quantizing the ratio of the height of the line rectangle to the line height in a fixed stage, and a line The in-line rectangle width ratio symbol generation step for generating a fixed type symbol by quantizing the ratio of the width of the in-line rectangle to the height in a fixed stage, and the fixed pixel type by quantizing the black pixel density in the rectangle in the fixed stage A black pixel density symbol generating step for generating a similar symbol, an appearance frequency counting step for converting the feature representing the arrangement state of the in-line rectangle in the test row into a symbol series, and counting the appearance frequency of the symbols in the test row, and the appearance A similarity determination step is performed in which similarity is determined based on the appearance frequency of the symbols in the test row tabulated by the frequency tabulation step and the sequence tendency of the previously learned symbol series.

A document processing program according to a twelfth aspect is a program for performing predetermined image processing on an input document image, extracting image features, and performing document processing, wherein a character extracted from the document image is processed. An in-line height symbol generating step for generating a fixed type of symbol by quantizing the height of the starting point of the in-line rectangle of the line image into a fixed stage, and a line height estimating step for estimating the line height of the character line image And, the ratio of the height of the in-line rectangle to the line height is quantized in a fixed stage to generate a fixed type symbol, and the ratio of the width of the in-line rectangle to the line height is fixed. In-line rectangular width ratio symbol generation step for generating a fixed type symbol by quantizing the black pixel density into a fixed stage and generating a fixed type symbol by quantizing the black pixel density in the rectangle to a fixed stage Generation step, an appearance frequency totaling step for converting the feature representing the arrangement state of the in-line rectangle in the test row into a symbol series, and totaling the appearance frequency of the symbols in the test row, and the test row totalized by the appearance frequency totaling step And a similarity determination step of determining similarity based on the appearance frequency of symbols and the arrangement tendency of previously learned symbol sequences.

  According to the document processing device, the document processing method, and the document processing program according to the present invention, by extracting features representing the arrangement state of the in-line rectangles of the character line image, and quantizing these in a fixed stage to generate a symbol Thus, it is possible to extract the characteristics of the character line without recognizing the character, and it is possible to efficiently perform a search regarding the contents of the character line.

  Exemplary embodiments of a document processing apparatus, a document processing method, and a document processing program according to the present invention will be explained below in detail with reference to the accompanying drawings.

(Hardware configuration of document processing device)
First, the hardware configuration of the document processing apparatus according to the embodiment of the present invention will be described. FIG. 1 is a diagram showing a hardware configuration of the document processing apparatus. The document processing apparatus includes a CPU 101, ROM 102, RAM 103, HDD (hard disk drive) 104, HD (hard disk) 105, FDD (flexible disk drive) 106, FD 112, display 107, network board 108, keyboard 109, mouse 110, and scanner. 111 is connected and configured by the bus 100.

  The CPU 101 controls the entire apparatus. The ROM 102 stores a basic input / output program. The RAM 103 is used as a work area for the CPU 101. The HDD 104 controls data read / write with respect to the HD 105 according to the control of the CPU 101. The HD 105 stores data written according to the control of the HDD 104. The FDD 106 performs data read / write control with respect to the FD (flexible disk) 112 according to the control of the CPU 101. The FD 112 is detachable and stores data written according to the control of the FDD 106. The display 107 displays a cursor, a menu, a window, or various data such as characters and images. The network board 108 is connected to the network 114 via the communication cable 113. The keyboard 109 inputs various information. The mouse 110 moves and selects a cursor, menu, and window displayed on the display 107, and performs an opening / closing operation. The scanner 111 performs optical reading of characters and images.

(Functional configuration of document processing device)
Next, a functional configuration of the document processing apparatus according to the embodiment of the present invention will be described. FIG. 2 is a block diagram showing a functional configuration of the document processing apparatus. The document processing apparatus includes an image input unit 201, a rectangle extraction unit 202, a line cutout unit 203, a symbol generation unit 204, an appearance frequency totaling unit 205, a determination unit 206, and a display unit 207.

  The image input unit 201 inputs a document image to be identified. The rectangle extraction unit 202 extracts a rectangle from the document image input from the input unit 201. The line cutout unit 203 performs a process of cutting out an in-line rectangle from the rectangle extracted by the rectangle extraction unit 202. The symbol generation unit 204 determines the arrangement state of the rectangle from the in-line rectangle cut out by the line cut-out unit 203, such as the height of the start point of the in-line rectangle, the rectangle size (height and width), the black pixel density, and the distance from the adjacent rectangle. Are extracted and quantized to generate a symbol. The appearance frequency totaling unit 205 applies a trigram table previously learned from the training in-line rectangular symbol data for each language to the symbol series generated by the symbol generation unit 204, and calculates the appearance probability of the symbol series for each language. ,Tally. The determination unit 206 determines from the tabulation result by the appearance frequency tabulation unit 205 that the language showing the highest appearance probability is the language to which the matching target line belongs. The display unit 207 displays the input image, the progress of each process, the result, and the like.

  The function of the image input unit 201 can be realized by the scanner 111 shown in FIG. The functions of the rectangular extraction unit 202, line cutout unit 203, symbol generation unit 204, appearance frequency totaling unit 205, and determination unit 206 can be realized by the CPU 101 shown in FIG. The function of the display unit 207 can be realized by the display 107 shown in FIG.

  In addition, the document processing apparatus of the present invention includes communication means (network board 108), so that it can be connected to a network. For example, as shown in FIG. 3, by connecting a plurality of document processing apparatuses to a network 114, data can be exchanged between the apparatuses. Further, if a communication means is provided in each function unit constituting the document processing apparatus, the document processing apparatus can be operated from a remote place by connecting each function unit to the network 114.

  The operation of the document processing apparatus according to the embodiment of the present invention will be described in detail below. Here, for example, a case where a specific row image is searched for a document image as shown in FIG. 4 is considered. Note that the specific line image does not have to be the same as that in the original image, and may have the same shape as a partial line even if the resolution is different. It is not necessary to completely match the images.

  For the document image (see FIG. 4) input from the image input unit 201, the rectangle extraction unit 202 extracts a circumscribed rectangle of black pixels as shown in FIG. The circumscribing rectangle extracted by the rectangle extraction unit 202 is subjected to a row cutout process by the row cutout unit 203. The line cut-out process is a process for connecting neighboring circumscribed rectangles shown in FIG. 5 and growing them into lines (see FIG. 6). Since this process can be performed by a well-known method, description thereof is omitted.

  Next, a description will be given of a process for quantizing a feature representing a rectangular arrangement state and a process for generating a symbol from a feature representing a quantized rectangular arrangement state. This process is performed in the symbol generation unit 204.

  First, a description will be given of a quantization process for features representing a rectangular arrangement state. FIG. 7A and FIG. 7B are diagrams illustrating arrangement examples of the in-row rectangles. When comparing the in-line rectangle of the European characters in Fig. 7-1 with the in-line rectangle of the Asian characters in Fig. 7-2, the arrangement of the in-line rectangles depends on the contents of the character line regardless of the language type. It can be seen that it has changed. Therefore, by extracting the circumscribed rectangle of the character, it is possible to capture a rough feature of the character. That is, even if the character itself is not specified, for example, as shown in FIG. 8, the start point (Xs, Ys) and end point (Xe, Ye) of the rectangular coordinates are obtained, and the arrangement of the circumscribed rectangle of the character image using this is obtained. The image feature of the character line can be captured only by acquiring the feature representing the state.

  A rectangle in a line is uniquely defined by measuring the height of the starting point of the in-line rectangle, the rectangle size (width, height), and the black pixel density in the in-line rectangle. Using these measurement results, the arrangement state of the in-line rectangle is defined. Since the in-line rectangle has already been obtained in the process of the line cut-out process, it is convenient because it is not necessary to perform an additional feature extraction process in order to specify the character line.

  Hereinafter, an example of defining the arrangement state of the in-line rectangle with reference to the height of the start point of the in-line rectangle will be shown. FIG. 9 is a diagram for explaining a method of quantizing a feature indicating an arrangement state of in-row rectangles. Under the situation where the document is not specified, the line height is variable, and the height of the starting point of the in-line rectangle is normalized by the following expression so that the processing does not depend on the value of the line height.

YsRate = ys / H (1)
(However, ys indicates the height of the in-line rectangle start point, and H indicates the line height.)

Since 0 <YsRate ≦ 1, it is easy to quantize YsRate to a fixed stage. For example, if you quantize to N stages,
YsVal = INT (YsRate * (N−1)) (2)
(However, INT (): rounded down to the nearest decimal point)
And it is sufficient. Each stage is labeled 0- (N-1). Note that if the document is tilted when the document is scanned, the character lines in FIG. 10 are also tilted. In the case of an extreme inclination, the line cut-out process fails. However, if the inclination is a little, a line can be cut out using a blank portion between lines.

  However, when paying attention to the height of the starting point of the in-line rectangle, even a slight inclination of the line greatly affects the result. In FIG. 10, the distance from the end point to the start point of the in-line rectangle is uniformly distributed with respect to the line height, and the concentration in two distinct frequencies, which is a feature of Western character lines, is observed. Can not. Therefore, a baseline is determined and the height from there to the starting point of the in-line rectangle is determined. In order to determine the baseline, a straight line connecting the end points of the in-line rectangles may be obtained. Specifically, a regression line of the distribution of the end point coordinates of the in-line rectangle may be obtained. Since the method of obtaining the regression line is well known, it will not be described here. For example, it is detailed in “Statistical Overview for Engineering” (Baifukan) I. Gutman and SS Wilkes.

With the above processing, the height of the start point of the in-line rectangle can be quantized. Similarly, in the case where the height of the in-line rectangle is used as a feature of the character line image, it is as follows in FIG.
HeightRate = h / H (3)
HeightVal = INT ((HeightRate * (N−1)) + 0.5) (4)
(However, INT (): rounded down to the nearest decimal point)
Each stage is labeled 0- (N-1).

Moreover, when using the width | variety of a rectangle, it is as follows.
WidthRate = w / H (5)
WidthVal = INT ((WidthRate * (N−1)) + 0.5) (6)
(However, INT (): rounded down to the nearest decimal point)
Each stage is labeled 0- (N-1).

  The in-line rectangle is not related to the contents of the character, but is a circumscribed rectangle of the constituent element of the character. However, even if the arrangement state of the in-line rectangles is the same, the structure of the European characters is simple, so the density of black pixels in the rectangles is low. On the other hand, Asian characters have a complicated structure, so the black pixel density in the rectangle is high. Of course, even in the same Asian characters, it can be easily imagined that the black pixel density of hiragana and katakana with a simple structure is low and the black pixel density of kanji is high. In this way, the rectangular black pixel density can be a feature that distinguishes characters. Therefore, the black pixel density (= the number of black pixels in the rectangle / the total number of pixels in the rectangle) is similarly quantized and defined as a fixed stage. As described above, it has been shown that the arrangement state of the in-line rectangle can be defined by a plurality of measurement results. These multiple measurement results define one independent in-line rectangle.

  By the way, some of the plurality of measurement results defining the in-line rectangle are not necessary depending on the search target. For example, if the search target line is only a Latin character line, the measurement result of the black pixel density will be unnecessary. This is because, for Latin character lines, since the character structure is as complex as every character, the black pixel density of the in-line rectangle is almost the same, and does not contribute to characterizing the in-line rectangle. Thus, depending on the nature of the set of search rows and searched rows, there is a feature that does not affect identification, and the feature need not be used. Of the plurality of measurement results, only a feature sufficient to distinguish the corresponding line from the non-corresponding line may be used. As a result, the processing efficiency is improved.

Further, the difference in the arrangement state of the in-line rectangle between the European character line and the Asian character line also appears in the distance from the adjacent rectangle as shown in FIG. In Western character lines, the distance between adjacent rectangles is often a positive value, and the rectangles rarely overlap. On the other hand, in Asian character lines, the case of overlapping with adjacent rectangles is frequently observed. In addition, there are points that are vertically on a rectangle, such as the letters “i” and “j”, those that have two points on a rectangle, such as umlauts in German, and (N + ˜: in Spanish) Characters that are characteristic with respect to the distance from adjacent rectangles exist for each language, such as those in which a thin rectangle exists on the rectangle as in (Ene). By quantizing this feature, the arrangement state of the in-line rectangle can be defined in more detail. Specifically, in each rectangle shown in FIG.
RightDistanceRate = d / H (7)
(However, d indicates the distance between rectangles.)
RightDistanceVal
= INT_PLUS ((Right DistanceRate * (N-1)) + 0.5) (8)
(However, INT_PLUS (): Convert to a positive number and round down after the decimal point)
And the ratio of the distance between the target rectangle and the adjacent rectangle is quantized to a fixed stage. Each stage is labeled 0- (N-1). As a result, the characteristics of the character line including many Asian characters can be defined in more detail, and the strict character line determination can be performed.

Next, processing for generating a symbol from the feature representing the quantized rectangular arrangement state will be described. Here, by combining a plurality of types of measurement results related to one in-line rectangle into one symbol, it becomes possible to make one in-line rectangle correspond to one symbol. For example, three types of information, that is, the height of the starting point of the rectangle, the height of the rectangle, and the width of the rectangle are collected. Suppose that the height of the rectangular starting point (ys / H) is quantized to 15 levels, the rectangular height (h / H) is quantized to 8 levels, and the rectangular width (w / H) is quantized to 2 levels. As a result, as shown in FIG. 12, each piece of information has a rectangular start point height (ys / H) of 15 levels, 4 bits, and a rectangular height (h / H) of 8 levels, 3 bits, a rectangle. Since the width (w / H) has two stages, it can be expressed by 1 bit. Also,
4bits + 3bits + 1bit = 8bits
Therefore, all information can be stored in each bit of 1 byte. And the type of symbol that combines these three types of information into one,
15 stages × 8 stages × 2 stages = 240 types. Note that the type of information to be collected, the storage area for storing the information, and the storage size are not fixed, and it is needless to say that information suitable for specifying the character line to be identified is appropriately selected and determined.

  Also, the presence information of blanks in the character line characterizes the line. This is especially important for Latin text lines where it is customary to insert spaces between words. The presence of white space in a line can be detected by comparing the distance between the in-line rectangle and the adjacent rectangle with the line height. For example, in FIG. 13, a threshold value is provided for the ratio of the inter-rectangular distance to the row height (a / H, b / H, c / H). Then, the ratio of the inter-rectangular distance to the line height is compared with a threshold value, and it is determined that there is a blank when the ratio of the inter-rectangular distance to the line height is larger than the threshold value. If it is determined that there is a blank, a symbol (for example, sSPC) meaning a blank is inserted. In the above example, there are 240 types of symbols corresponding to the rectangular arrangement information, whereas the storage area size is 1 byte, so that 16 types (= 256-240) of special symbols can be further set. The blank symbol sSPC corresponds to one of these 16 types.

  Further, if a plurality of features representing the arrangement state of the rectangle are regarded as each dimension of the multidimensional vector, the rectangle can be converted into one vector data (vector quantization) using each feature. Vector quantization is to obtain a small number of vector data representing them from a large variety of vector data, as is well known. By labeling the obtained representative vectors in order, the vector data series can be converted into a simple one-dimensional symbol data series. For vector quantization, see “Vector quantization and information compression” (Corona) Allen Gersho, Robert M. et al. Familiar with Gray, Saburo Tazaki et al.

  In this way, if it can be converted into a symbol series, the arrangement tendency can be learned as described above. For example, three-dimensional vector data relating to the arrangement of rectangles is obtained from the training data, and 240 types of representative vectors are obtained therefrom. This representative vector group is called a code book. An ID that distinguishes 240 vectors in the codebook is a symbol. The arrangement of the in-line rectangles in the character line data to be identified is converted into a three-dimensional vector, the vector most similar to the vector in the codebook is selected, and the ID is used as the symbol of the rectangle.

  Through the above operations, the rectangle included in the row can be converted into a fixed number of symbols (labels). Therefore, the actual arrangement of the in-line rectangles can be regarded as a simple symbol series as shown in FIG. This can record the arrangement tendency of the symbol series, which is equivalent to recording the arrangement tendency of the in-line rectangles. After the conversion to the symbol series, it is possible to perform a search by a general search method as in the text search. That is, it is only necessary to obtain a perfect match between symbol sequences. However, since the measurement result of the feature of the character rectangle varies depending on the reading error of the character line image, the symbol conversion result may not be the same even if the character line images are the same. Therefore, there is a possibility that the same character line image cannot be searched only by obtaining a complete match of the symbol strings.

  Therefore, in the document processing apparatus of the present invention, the similarity of the symbol arrangement tendency is obtained instead of the complete matching of the symbol strings. Specifically, a trigram table learned in advance using training in-line rectangular symbol data for each language is applied to the converted symbol series, and the appearance probability of the symbol series is calculated for each language and tabulated. This process is performed by the appearance frequency counting unit 205. Details will be described below.

  There is an n-gram model as a method for recording the tendency of arrangement. The n-gram model is a language model proposed by Claude Elwood Shannon. Assume that the appearance of a symbol in the sequence is affected by the immediately preceding n symbols (n is a natural number). A stochastic process whose current state is determined depending on the n-th previous input is called an n-fold Markov process, and the n-gram model is also called an (n-1) -fold Markov model. In particular, the case of n = 3 is called trigram and is widely used.

  Specifically, it is a model represented by the following equation (9). Furthermore, according to the equation (10), the appearance frequency of the triplet of symbols is counted from the symbol series data for training.

  On the other hand, the appearance frequency rank of trigram is obtained. Table 1 shows an example of trigram aggregation.

  Obtaining a trigram total as shown in Table 1 for a character line corresponds to obtaining (learning) the characteristics of the character line. After the arrangement state of the in-line rectangle of the character line to be searched is converted into a symbol series in the same manner as at the time of learning, a trigram total is obtained.

  By the way, the method of calculating the similarity between character lines using the trigram tabulation result is not only for line character lines, but also for determining similarity in units of areas that are sets of character lines or in units of originals. Obviously, it is applicable. In a region to be compared, a line segmentation process is performed and converted into a symbol series by each line, and then a rectangular trigram is totaled in units of regions (that is, symbolization information of character lines is collected in a specific range such as the entire document or the entire region) trigram total). If the rank correlation coefficient is obtained with respect to the trigram count result, it becomes a reference for determining the similarity between the regions.

  Finally, the trigram total result is compared with the trigram total result learned from the search target character line, and the most similar one is selected. That is, it is determined that the language having the highest appearance frequency is the language to which the verification target line belongs. This process is performed by the determination unit 206. This will be described in detail below.

First, since the number of in-line rectangles included in one line differs between the search line and the search target line, the appearance frequencies themselves cannot be compared. Therefore, in order to determine the similarity of the trigram summary table, the rank correlation coefficient obtained by the following equation is used. Since the method of calculating the rank correlation coefficient is well known, it will not be described here. For example, it is detailed in “Non-parametric method” written by Kei Yanagi (Baifukan).
Rxy = 1- (6 * Σ (Rxi-Ryi) ^ 2) / (n * (n ^ 2-1)) (11)
(However, n indicates the number of data, and Rxi and Ryi indicate the numerical value of the data.)

  Then, the rank correlation coefficient of the trigram aggregation result between the search line and the search target line is obtained, and the one closest to 1 may be selected. Further, the rank correlation coefficient may be statistically tested, and if the maximum rank correlation coefficient does not show a significant value, it may be determined that the search is not applicable.

  The processing so far can be summarized as shown in FIG. That is, the in-line rectangle of the image to be collated is converted into a symbol in advance (step S1401), the trigram is totaled in a predetermined area (step S1402), and a trigram appearance frequency totaling table is created (step S1403). On the other hand, the in-line rectangle of the verification target image is converted into a symbol (step S1404), the trigram is totaled in a predetermined area (step S1405), and a trigram appearance frequency totaling table is created (step S1406). Finally, the highest occurrence rate is obtained by collating the occurrence frequency tabulation table created in step S1403 and the occurrence frequency tabulation table created in step S1406 to obtain a rank correlation coefficient (step S1407). It can be determined that the language indicating the probability is the language to which the verification target line belongs.

  By the way, although reference has been made so far regarding collation between character line images, if a character line image can be created from text data, a line including a designated character can be searched. In order to obtain a character image from text data, font data may be used. For example, vector data such as a true type font is expanded to generate character bitmap data (image), and a designated character string (text) is converted into a symbol series. For this purpose, it is necessary that the symbol generation unit 204 has a function of converting a character font set and a character font from character text, generating a character string image from the text character string, and then converting it into an in-line rectangular symbol. It is. After both the search character string and the character string to be searched are converted to the in-line rectangular symbol series, a portion where the symbol series completely matches is obtained as in the general text search technique. As a result, text search can be performed on the document image without recognizing characters. It is clear that the character pattern dictionary required for character recognition is unnecessary.

  In this way, once a character image is generated and then converted to an in-line rectangular symbol, it is convenient to take into account fluctuations in the in-line rectangular symbol due to differences in fonts if only a font set is prepared. . However, in order to convert to the in-line rectangular symbol series, it is not only necessary to prepare font data for all characters but also an arithmetic process for generating a character image. Therefore, a function that converts the character string of the input text into a rectangular symbol series by preparing a rectangular symbol conversion result for each character in advance, associating each symbol with a symbol that represents the arrangement information of the rectangle within the character. It is good to have. In this way, if a corresponding converted in-line rectangular symbol is obtained for each character in advance and recorded, it can be converted from a text string to an in-line rectangular symbol without going through a character image. become. FIG. 15 shows the correlation between the character code and the rectangular symbol conversion result. However, since one character does not necessarily have one rectangle, one character may be converted into a plurality of symbol sequences.

(Document processing procedure)
The procedure of document processing using the document processing apparatus of the present invention will be described below. FIG. 16 is a flowchart showing the procedure of this document processing. First, the image input unit 201 inputs a document image to be identified (step S1601). Next, the rectangle extraction unit 202 extracts a rectangle from the input document image (step S1602). Next, the line cutout unit 203 performs a process of cutting out the in-line rectangle from the rectangle extracted by the rectangle extraction unit 202 (step S1603). The symbol generation unit 204 extracts features representing the arrangement state of the rectangles from the in-line rectangles cut out by the line cut-out unit 203, and quantizes them to generate symbols (step S1604). The appearance frequency totaling unit 205 applies a trigram table previously learned from the in-line rectangular symbol data for training to each symbol series generated by the symbol generation unit 204 and calculates the appearance frequency of the symbol series for each language. And totalize (step S1605). Finally, the determination unit 206 determines that the language showing the highest appearance frequency is the language to which the verification target line belongs from the aggregation result by the appearance frequency totaling unit 205 (step S1606).

(Rectangle placement state symbol generation processing procedure)
Next, the procedure of the rectangular arrangement state symbol generation process in step S1604 will be described in more detail. FIG. 17 is a flowchart showing the procedure of the rectangular arrangement state symbol generation process. First, the line height of characters represented in the document image is estimated (step S1701). Next, the in-line rectangles are classified based on the start point position of the in-line rectangle with respect to the line height (step S1702). Next, the characteristics (the height of the start point of the in-line rectangle, the rectangle size (height, width), the black pixel density, the distance from the adjacent rectangle, etc.) representing the layout state of each classified in-line rectangle are measured (step S1703). . Then, the feature representing the rectangular arrangement state is quantized to generate a symbol (step S1704). Finally, the symbol series generated in step S1704 is recorded (step S1705).

  By performing each of the above processes, the language to which the target line belongs is extracted from the feature representing the arrangement state of the in-line rectangle (features obtained in the process of line segmentation processing, not the process of newly extracting line features). Can be classified. As a result, language identification processing can be realized at high speed, and a criterion for selecting a document processing optimum for the language can be obtained according to the language identification result. Therefore, highly accurate document processing can be realized.

  As described above, according to the document processing device, the document processing method, and the document processing program according to the present invention, the feature representing the arrangement state of the in-line rectangle of the character line image is extracted, and these are quantized to the fixed stage. By generating a symbol, it is possible to extract the characteristics of the character line without recognizing the character, and it is possible to perform an efficient search regarding the contents of the character line.

  The document processing method described in this embodiment can be realized by executing a program prepared in advance on a computer such as a personal computer or a workstation. This program is recorded on a computer-readable recording medium such as a hard disk, a flexible disk, a CD-ROM, an MO, and a DVD, and is executed by being read from the recording medium by the computer. The program may be a transmission medium that can be distributed via a network such as the Internet.

  As described above, the document processing device, the document processing method, and the document processing program according to the present invention are useful for character identification processing that needs to efficiently extract the characteristics of the shape of a character line. Suitable for such as.

It is a figure which shows the hardware constitutions of the document processing apparatus concerning embodiment of this invention. It is a block diagram which shows the functional structure of the document processing apparatus concerning embodiment of this invention. It is a figure which shows an example of the network structure using the document processing apparatus concerning embodiment of this invention. FIG. 4 is a diagram illustrating an example of a document image input to a document processing apparatus. It is a figure which shows an example of the circumscribed rectangle of the black pixel calculated | required from a document image. It is a figure for demonstrating a line cut-out process. It is a figure which shows the example of arrangement | positioning of the rectangle in a line. It is a figure which shows the example of arrangement | positioning of the rectangle in a line. It is a figure for demonstrating the example of a setting of the coordinate with respect to a rectangle. It is a figure for demonstrating the method of quantizing the characteristic showing the arrangement | positioning state of the rectangle in a line. It is a figure which shows the example which produced | generated the symbol from the characteristic showing the arrangement | positioning state of the rectangle in a line. It is a figure for demonstrating the insertion process of the blank symbol based on the distance between rectangles. It is a figure for demonstrating quantization of the distance between rectangles. It is a figure for demonstrating the insertion process of the blank symbol based on the distance between rectangles. It is a flowchart which shows the procedure of the document image collation using the rectangle trigram. It is a table | surface for demonstrating the case where it converts directly from a character code to a rectangular symbol. It is a flowchart which shows the procedure of document processing. It is a flowchart which shows the procedure of a rectangular arrangement | positioning state symbol production | generation process.

Explanation of symbols

100 bus 101 CPU
102 ROM
103 RAM
104 HDD (Hard Disk Drive)
105 HD (hard disk)
106 FDD (flexible disk drive)
107 Display 108 Network Board 109 Keyboard 110 Mouse 111 Scanner 112 FD (Flexible Disk)
113 Communication Cable 114 Network 201 Image Input Unit 202 Rectangular Extraction Unit 203 Line Extraction Unit 204 Symbol Generation Unit 205 Appearance Frequency Total Unit 206 Determination Unit 207 Display Unit

Claims (12)

An apparatus that performs predetermined image processing on an input document image, extracts image characteristics, and performs document processing,
In-line height symbol generating means for generating a fixed type symbol by quantizing the height in the line of the starting point of the in-line rectangle of the character line image extracted from the document image into a fixed stage;
A line height estimating means for estimating a line height of the character line image;
An in-line rectangular height ratio symbol generating means for generating a fixed type symbol by quantizing a ratio of the in-line rectangular height to the line height into a fixed stage;
In-line rectangle width ratio symbol generating means for generating a fixed type symbol by quantizing the ratio of the width of the in-line rectangle to the line height in a fixed stage;
Black pixel density symbol generating means for generating a fixed type of symbol by quantizing the black pixel density in the rectangle in a fixed stage;
Appearance frequency totaling means for converting the feature representing the arrangement state of the in-line rectangle in the test line into a symbol series, and totaling the appearance frequency of the in-line rectangle symbol in the test line;
Similarity determination means for determining similarity based on the appearance frequency of the symbols aggregated by the appearance frequency aggregation means and the arrangement tendency of the symbol series learned in advance;
A document processing apparatus comprising:       And a representative symbol generating means for extracting one or more representative ones from a plurality of features representing the arrangement state of the in-line rectangles and generating a fixed type symbol based thereon. Item 2. The document processing apparatus according to Item 1.       The distance ratio symbol generating means for generating a fixed type symbol by quantizing the ratio of the distance between the target rectangle and the adjacent rectangle with respect to the row height into a fixed stage. Document processing device. The distance calculation means for calculating the distance between the end point of the in-line rectangle of interest and the start point of the adjacent in-line rectangle, the distance calculated by the distance calculation means and the line height are compared, and the ratio exceeds a certain value. A symbol series conversion means for inserting a blank symbol and converting the arrangement state of the in-line rectangle into a symbol series,
The document processing apparatus according to claim 1, further comprising:       Furthermore, a plurality of features representing the arrangement state of the in-line rectangle are vector-quantized corresponding to each dimension of the multi-dimensional vector, and an in-line rectangular arrangement state symbol generating means for generating a fixed type symbol indicating the arrangement state of the in-line rectangle is provided. The document processing apparatus according to claim 2, wherein:       Further, the symbol information of the character line generated by the representative symbol generating means is aggregated in a specific range such as the entire manuscript or the entire predetermined region, and the similarity within the specific range for determining the similarity between the training document and the test document is determined. The document processing apparatus according to claim 2, further comprising a determination unit. Character input means;
Character font set,
Document image acquisition means for developing a character font from the character text input from the character input means to obtain a character image based on the character font set;
An in-line rectangular symbol generating means for generating a character string image from a character string of character text input from the character input means, and generating an in-line rectangular symbol of the character string image;
The document processing apparatus according to claim 1, further comprising: Furthermore, symbol corresponding means for associating a symbol representing the arrangement state of the rectangle in the character for each character with respect to the in-line rectangular symbol generated in advance for each character;
Rectangular symbol conversion means for converting a character string of the input text input from the character input means into a rectangular symbol series;
The document processing apparatus according to claim 7, further comprising: An apparatus that performs predetermined image processing on an input document image, extracts image characteristics, and performs document processing,
In-line height symbol generating means for generating a fixed type symbol by quantizing the height in the line of the starting point of the in-line rectangle of the character line image extracted from the document image into a fixed stage;
A line height estimating means for estimating a line height of the character line image;
An in-line rectangular height ratio symbol generating means for generating a fixed type symbol by quantizing a ratio of the in-line rectangular height to the line height into a fixed stage;
In-line rectangle width ratio symbol generating means for generating a fixed type symbol by quantizing the ratio of the width of the in-line rectangle to the line height in a fixed stage;
Black pixel density symbol generating means for generating a fixed type of symbol by quantizing the black pixel density in the rectangle in a fixed stage;
A training line learning means for converting the feature representing the arrangement state of the in-line rectangle in the training line into a symbol series and learning the tendency thereof;
An evaluation value calculating means for converting the feature representing the arrangement state of the in-line rectangle in the test line into a symbol series, and using the learning result of the training line by the training line learning means;
Similarity determination means for comparing the learning result of the training line by the training line learning means with the evaluation value of the test line calculated by the evaluation value calculation means, and determining the similarity;
A document processing apparatus comprising: A document processing apparatus for determining similarity between character line images extracted from a document image,
In-line start point height quantization means for quantizing the height in the line of the start point of the in-line rectangle of the character line image in a fixed stage;
In-line rectangle height quantization means for quantizing the height of the in-line rectangle of the character line image in a fixed stage;
In-line rectangle width quantization means for quantizing the width of the in-line rectangle of the character line image in a fixed stage;
The height of the start point of the in-line rectangle quantized by the in-line start point quantization means, the height of the in-line rectangle quantized by the in-line rectangle height quantization means, and the in-line rectangle width quantization means Symbol generating means for generating a symbol from the arrangement state determined based on the quantized width of the in-line rectangle;
Appearance frequency counting means for counting the appearance frequencies of the symbols generated in the test row by the symbol generating means;
Similarity determination means for determining similarity based on the appearance frequency of the symbols aggregated by the appearance frequency aggregation means and the arrangement tendency of the symbol series learned in advance;
A document processing apparatus comprising: A document processing method performed by a document processing apparatus that performs predetermined image processing on an input document image, extracts image characteristics, and performs document processing ,
The document processing device is
An in-line height symbol generation step of generating a fixed type symbol by quantizing the height in the line of the start point of the in-line rectangle of the character line image extracted from the document image;
A line height estimating step for estimating a line height of the character line image;
An in-line rectangle height ratio symbol generation step of generating a fixed type symbol by quantizing a ratio of the height of the in-line rectangle to the line height into a fixed stage;
An in-line rectangle width ratio symbol generation step of generating a fixed type of symbol by quantizing a ratio of the width of the in-line rectangle to the line height into a fixed stage;
A black pixel density symbol generating step of generating a fixed type of symbol by quantizing the black pixel density in the rectangle into a fixed stage;
An appearance frequency totaling step of converting the feature representing the arrangement state of the in-line rectangle in the test line into a symbol series, and totaling the appearance frequency of the symbols in the test line,
A similarity determination step of determining similarity based on the appearance frequency of the symbols in the test row tabulated by the appearance frequency tabulation step and the pre-learned arrangement sequence of the symbol series;
The document processing method characterized by performing . A program that performs predetermined image processing on an input document image, extracts image features, and performs document processing,
An in-line height symbol generation step of generating a fixed type symbol by quantizing the height in the line of the start point of the in-line rectangle of the character line image extracted from the document image;
A line height estimating step for estimating a line height of the character line image;
An in-line rectangle height ratio symbol generation step of generating a fixed type symbol by quantizing a ratio of the height of the in-line rectangle to the line height into a fixed stage;
An in-line rectangle width ratio symbol generation step of generating a fixed type of symbol by quantizing a ratio of the width of the in-line rectangle to the line height into a fixed stage;
A black pixel density symbol generating step of generating a fixed type of symbol by quantizing the black pixel density in the rectangle into a fixed stage;
An appearance frequency totaling step of converting the feature representing the arrangement state of the in-line rectangle in the test line into a symbol series, and totaling the appearance frequency of the symbols in the test line,
A similarity determination step of determining similarity based on the appearance frequency of the symbols in the test row tabulated by the appearance frequency tabulation step and the pre-learned arrangement sequence of the symbol series;
A document processing program for causing a computer to execute.

Images