JP6204076B2 - Text area reading order determination apparatus, text area reading order determination method, and text area reading order determination program - Google Patents

Description

  The present invention relates to a technique for determining the reading order of a text area.

  In order to convert the text in the document image into text data, or to rearrange the document image according to the screen size of the display device (reflow), the document image is divided into areas for each text, and the reading order of each text area There is a method of determining (Patent Document 1).

Japanese Patent Laid-Open No. 3-269689

  However, if the ruled lines are not artificially inserted between the text areas, the accuracy of determining the reading order may be reduced and may not be determined uniquely.

  The present invention has been made in view of the above circumstances, and an object thereof is to improve the determination accuracy of the reading order of a text area.

  The sentence area reading order determination device according to claim 1, wherein the content is read from the storage means, divided into a plurality of sentence areas, and an index is assigned to each sentence area; The gist of the present invention is to include a determination unit that determines the reading order of each sentence area based on the character direction and each index.

  According to the present invention, the content is divided into a plurality of text areas, each index is assigned, and the reading order of each text area is determined based on the writing direction of each content and each index. The determination accuracy can be improved.

  The sentence area reading order determining apparatus according to claim 2, wherein the dividing / giving unit divides the content into left and right or up and down, and the divided division pattern. The gist is to further add an identifier for identifying

  The sentence region reading order determination device according to claim 3 is the sentence region reading order determination device according to claim 1 or 2, wherein the dividing / giving unit determines each division pattern for dividing the content horizontally and vertically. The gist is to divide the sentence area repeatedly by changing alternately.

  The sentence area reading order determination device according to claim 4 is the sentence area reading order determination apparatus according to any one of claims 1 to 3, wherein two adjacent sentence areas are divided once or a plurality of times. In the case where both are not re-divided and both are divided into left and right and both are vertically written, or vertically divided and both are horizontally written, there is further provided a recombination means for recombining the respective sentence areas. To do.

  The sentence region reading order determining device according to claim 5 is the sentence region reading order determining device according to claim 4, wherein the recombination means is configured such that each interval between the two sentence regions is equal to or less than a threshold value. The gist is to recombine the text areas.

  The sentence region reading order determination device according to claim 6 is the sentence region reading order determination device according to any one of claims 1 to 5, wherein two adjacent sentence regions are both in one line, and left and right In the case of dividing horizontally and writing both horizontally, or vertically and both writing vertically, the gist is to further include recombining means for recombining the respective text areas.

  The sentence region reading order determination device according to claim 7 is the sentence region reading order determination device according to any one of claims 1 to 6, wherein the dividing / giving unit sets the index to the left side when dividing into left and right parts. In this case, the index is assigned in order from the upper sentence area.

  The sentence region reading order determining device according to claim 8 is the sentence region reading order determining device according to claim 7, wherein the dividing / applying unit assigns −1, −2, −3 when assigning from the left side. ,..., And when the index is given from the upper side, the gist is to give the index as +1, +2, +3,.

  The sentence region reading order determination device according to claim 9 is the sentence region reading order determination device according to any one of claims 1 to 8, wherein the dividing / giving unit divides at a position of a ruled line included in the content. The gist is to do.

  The sentence region reading order determination device according to claim 10 is the sentence region reading order determination device according to any one of claims 1 to 9, wherein the determination unit is configured to write the content when divided into left and right parts. If the character direction is horizontal writing, the text area to which the index is assigned first is the first, if it is vertical writing, the text area is the last, and if the text is divided vertically, the text area is determined to be the first. The gist is to do.

  The sentence region reading order determination device according to claim 11 is the sentence region reading order determination device according to claim 8, wherein the determination means is given as -1, -2, -3,. If the writing direction of the content is horizontal writing, the summary is to determine the sentence area to which the index having the smaller absolute value is assigned first, and if the writing direction is vertical writing, the sentence area is determined to be later.

  The sentence region reading order determining device according to claim 12 is the sentence region reading order determining device according to any one of claims 1 to 11, wherein the determining means is configured to estimate the writing direction of each sentence region. The gist is to determine the writing direction of the content based on the above.

  The sentence area reading order determination method according to claim 13, wherein the content is read from the storage means by a computer, divided into a plurality of sentence areas, and an index is assigned to each sentence area. And a determination step of determining the reading order of each sentence area based on the writing direction of the content and each index.

  According to the present invention, the content is divided into a plurality of text areas, each index is assigned, and the reading order of each text area is determined based on the writing direction of each content and each index. The determination accuracy can be improved.

  The sentence area reading order determination program according to claim 14, wherein the computer program reads the content from the storage means, divides the contents into a plurality of sentence areas, and assigns an index to each sentence area, The gist is to execute a determination process for determining the reading order of each sentence area based on the writing direction of the content and each index.

  According to the present invention, the content is divided into a plurality of text areas, each index is assigned, and the reading order of each text area is determined based on the writing direction of each content and each index. The determination accuracy can be improved.

  ADVANTAGE OF THE INVENTION According to this invention, the determination precision of the reading order of a text area can be improved.

It is a figure which shows the functional block structure of a text area | region reading order determination apparatus. It is a figure which shows the processing flow of the text area | region reading order determination method. It is a figure which shows the image of a one-dimensional projection histogram. It is a reference figure at the time of 1-dimensional projection histogram generation. It is a reference figure at the time of 1-dimensional projection histogram generation. It is a figure which shows the example of a provision result of an index.

  Hereinafter, an embodiment for carrying out the present invention will be described with reference to the drawings.

  FIG. 1 is a diagram showing a functional block configuration of a text area reading order determination device 1 according to the present embodiment. This text region reading order determination device 1 includes a content storage unit 11, a document image region extracting unit 12, a document image region dividing unit 13, a letter estimating unit 14, a division processing canceling unit 15, and a text region reading order. And a determination unit 16.

  The content storage unit 11 is a functional unit such as a memory that stores a plurality of contents input to the text region reading order determination device 1 using a scanner device or the like.

  The document image region extraction unit 12 is a functional unit that reads the content to be determined from the content storage unit 11 and extracts the document image region.

  The document image area dividing unit 13 is a functional unit that divides the extracted document image area into a plurality of text areas and assigns an index to each text area.

  The writing estimation unit 14 is a functional unit that estimates the writing direction (horizontal writing / vertical writing) and the number of lines of a sentence included in each sentence area.

  The division process canceling unit 15 is a functional unit that cancels the executed division process according to a condition, that is, recombines the divided text areas so as to return to the text area before the division.

  The sentence area reading order determination unit 16 determines the writing direction of the entire document image area from the estimation result of the writing direction of each sentence area, and reads each sentence area based on the writing direction of the document image area and each index. It is a functional unit that determines the order.

  The sentence region reading order determination apparatus 1 having such a function unit can be realized by a computer having a memory and a CPU. Further, the processing of each functional unit can be executed by a program.

  FIG. 2 is a diagram showing a processing flow of the sentence region reading order determination method. The determination method will be described with reference to FIG.

  First, the document image area extraction unit 12 reads the content to be determined from the content storage unit 11, converts the printed portion to black, and converts the unprinted portion to white, thereby converting the content 2. A valued image is generated (step S1).

  This binarization processing is executed in order to ensure that characters in the content can be recognized as characters even if they are drawn with a gray value other than black (such as red characters). If it is clear that the content to be determined is a novel or the like and the printed character portion is black and the background is white, this step can be omitted.

  Next, the document image area extraction unit 12 designates the entire binarized image generated in step S1 as a processing area, and a minimum rectangular area including all black pixels in the processing area is an initial area. It is extracted as (document image area) (step S2).

  By this extraction process, the top, bottom, left, and right margins included in the content to be determined are removed, and only the document image region that is the actual target of the determination is extracted. As a method for specifying the processing area, the entire binarized image may be automatically specified by a computer. When the content is scanned slightly obliquely and the image is out of paper, the image is taken as a photograph. The rectangular area may be designated by the user in consideration of the case where an extra print area is included.

  Next, the document image region extraction unit 12 generates a one-dimensional projection histogram in the initial region extracted in step S2 (step S3).

  For example, as shown in FIG. 3, each one-dimensional projection histogram in the x-axis direction and the y-axis direction is generated by counting the number of black pixels in the initial area A on the vertical line and the horizontal line, respectively. To do.

More specifically, as shown in FIG. 4, the pixel position at the upper left corner of the initial area A is (x _r , y _r ), the width in the x-axis direction is w _r , and the width in the y-axis direction is h _r . A one-dimensional projection histogram h _x in the x-axis direction is generated from the following equation (1), and a one-dimensional projection histogram h _y in the y-axis direction is generated from the following equation (2).

However, the possible value of the variable _Bc is 1 or 0. It is 1 when the pixel (x, y) is a black pixel, and 0 when it is not a black pixel.

  On the other hand, in addition to this method, a group in which black pixels are connected in the initial area is detected, and the minimum rectangular area including the group is used as a label area, and the number of label areas is set on the vertical line. And may be generated using values counted on the horizontal line.

More specifically, as shown in FIG. 5, for example, when a rectangular range including the character “A” is used as the label region R and a one-dimensional projection histogram h _x in the x-axis direction is generated, the label region 1 is added to h _x (i) for all i satisfying “left end ≦ i ≦ right end” of R. On the other hand, when generating a one-dimensional projection histogram h _y in the y-axis direction, 1 is added to h _y (j) for all j satisfying “upper end ≦ j ≦ lower end” of the label region R.

  The above is an example of generating a one-dimensional projection histogram. Depending on the content, a horizontally long or vertically long ruled line G (FIG. 3) may be drawn in order to clarify the division between columns. In that case, the ruled line portion histogram value is deleted from the one-dimensional projection histogram. The ruled line position may be stored and used as a region division position. As a ruled line portion detection method, for example, since the label region is extremely elongated compared to the character label region, a rectangular range whose aspect ratio or area does not fall within a specified range is set as the ruled line portion.

  Subsequently, the document image area extraction unit 12 sets the hierarchy of the initial area extracted in step S2 to 0 (step S4). Note that this step may be executed before step S3.

  Next, the dividing direction (horizontal direction or vertical direction) of the initial region is determined by the document image region dividing unit 13 using the one-dimensional projection histogram in each direction generated in step S3 (step S5).

  For example, when there is a vertical or horizontal column, there is a white run with a long axial length between the columns, so the average axis length of the white run in the x-axis direction and the average axis of the white run in the y-axis direction Compare the lengths and divide by the larger white run. In other words, when the y-axis width of the white run in the y-axis direction is larger than the x-axis width of the white run in the x-axis direction, the y-axis direction is divided in the vertical direction to divide up and down. If it is small, the x-axis direction is set as the division direction (horizontal direction: horizontal division) in order to divide it left and right.

  In addition, the black run axial length may be used. For example, the value obtained by dividing the average axis length of the white run in the x-axis direction by the average axis length of the black run in the x-axis direction is equal to the average axis length of the white run in the y-axis direction. If it is larger than the value divided by the average axis length, the vertical division is assumed.

  Next, the document image region dividing unit 13 determines whether or not there is a white run having an axial length equal to or greater than a threshold value in the division direction using the one-dimensional projection histogram in the division direction determined in step S5. (Step S6), in some cases, the initial region is divided into a plurality of divided regions (text regions) at the position of the white run (Step S7).

  Instead of using the white run, the determination may be made based on whether the gap length between adjacent black runs is greater than or equal to a threshold value. Further, as described above, when a ruled line portion is detected, it may be divided at the position of the ruled line.

  Next, after step S7, the document image area dividing unit 13 assigns an index in the current hierarchy that can identify the dividing direction to each divided area divided in step S7 (step S8). ).

  For example, in the case of horizontal division, indexes such as −1, −2, −3,. On the other hand, in the case of vertical division, +1, +2, +3,. + And − are identifiers of division directions (division patterns).

  Next, the document image area dividing unit 13 determines whether or not the current hierarchy has reached the upper limit hierarchy for division (step S9). If the upper limit hierarchy is not reached, the current hierarchy is updated to 1 by adding 1 to the number of hierarchies (step S10), and a one-dimensional projection histogram of each divided region is generated (step S11). . The upper limit hierarchy of division is determined in advance according to the assumed complexity of the layout. For example, in the case of a book including a chart, the upper limit hierarchy is preferably about 2-3.

  Then, after step S11, the process returns to step S6, the re-division process for each divided area is recursively repeated, and indexes are additionally given to all divided areas after the re-division. However, the subdivision trial direction is opposite to the division direction of the division source area. For example, a region divided in the vertical direction is attempted to be divided in the horizontal direction.

  Here, an example of the result of index assignment is shown in FIG. For example, “+1” is assigned to the vertically divided divided region B1, “+2” is assigned to the divided region B2, and “+3” is assigned to the divided region B3. Further, “−1” is further given to the divided region B11 obtained by further dividing the divided region B1, and “−2” is further given to the divided region B12.

  Subsequently, when the determination result of step S6 is No, or when the determination result of step S9 is Yes, the writing direction of the sentence described in each divided region (horizontal writing / vertical writing) is written by the writing estimating unit 14. Writing) is estimated (step S12), and it is specified whether or not the number of lines in the sentence is one (step S13).

  The writing direction and the number of sentence lines can be specified from the distribution state of the one-dimensional projection histogram generated for each divided region. For example, the average axis lengths of white run and black run are calculated in the y-axis direction, respectively, and when the average axis length of white run is close to 0, vertical writing is performed. This is because in the case of vertical writing, when there is a projection in the y-axis direction, a portion without characters does not appear.

  Next, after the division processing cancellation unit 15 divides two adjacent areas in the same layer once or after being divided once or a plurality of times, both are not re-divided, and both horizontal division and vertical writing or vertical division are performed. & If both correspond to horizontal writing, it is considered that the line is divided at a break such as double line feed, and if the interval between the two divided areas is equal to or smaller than the threshold value, they are recombined (step S14). Even when the threshold value is exceeded, recombination may be performed.

  Note that the threshold used here is larger than the threshold used in step S6. Further, when a ruled line exists between two divided areas and the area is always divided at the position of the ruled line, recombination is not performed regardless of the interval between the divided areas.

  In addition, when the division processing canceling unit 15 includes two divided areas adjacent to each other in the same layer and corresponds to horizontal division & both horizontal writing or vertical division & both vertical writing, gaps such as punctuation marks. And the two divided areas are recombined (step S15).

  Note that step S14 and step S15 have no temporal relationship in the processing order, and may be executed at the same timing. In addition, the index (only the index in the corresponding hierarchy) assigned to the combined divided area is replaced with one of the indexes of the combined divided areas.

  Next, the document image area dividing unit 13 determines whether or not there is a divided area that has not been subdivided and has not yet been tried for division in another direction (step S16).

  Here, with respect to the corresponding divided area, the process after step S6 is executed again by changing the dividing direction. For example, the divided area B2 shown in FIG. Since this divided area B2 is not subdivided, it is tried again whether or not further division is possible by changing the division direction to the vertical direction.

  Next, when the determination result of step S16 is No, the sentence area reading order determination unit 16 compares the total area of the horizontal writing area and the total area of the vertical writing area, and the letter having the larger area is written. The direction is determined as the reading direction (writing direction) of the entire initial area (step S17).

  Next, the reading order of each divided area is determined by the same text area reading order determination unit 16 using the reading direction of the initial area determined in step S17 and the order of the indexes assigned to each divided area. (Step S18).

  Specifically, for any two divided regions, values are compared in order starting from the shallowest level of each assigned index, and the reading order is determined from the magnitude relationship of the index values that are initially not equal.

  For example, in the specific example where the index order is used in step S8, in the case of horizontal division, if the reading direction of the initial area is horizontal writing, the reading order of the divided areas to which the index having the smaller absolute value of the index value is assigned. If the reading direction is vertical writing, it is determined that the reading order of the divided area is later (the reading order of the divided area to which the index having the larger absolute value of the index value is given first).

  That is, in the case of horizontal division, if the reading direction of the initial area is horizontal writing, the divided area to which the index is assigned first is the first, and if it is vertical writing, the divided area is the rear. On the other hand, in the case of vertical division, regardless of the reading direction of the initial area, the sentence area to which the index with the first order is assigned is determined as the first.

  Finally, based on the determination result of step S18, the read order is assigned to each divided area, and the read order is stored in a memory or the like in association with the identifier of each divided area. Thereafter, when the determination target content is rearranged in accordance with the screen size of the display device, the divided areas are rearranged and displayed in the reading order in the list.

  As described above, according to the present embodiment, the initial image of the document image area is divided into a plurality of divided areas, and indexes are assigned respectively, and the reading order of each text area is based on the writing direction of the initial image and each index. Therefore, the determination accuracy of the reading order of the text area can be improved. In other words, even a document image with a complicated layout can be appropriately divided into regions and arranged in the correct reading order. Further, it is possible to correct the order of the areas from which sentences are extracted when text data is generated or reflowed.

  Finally, in the present embodiment, the case where the natural numbers are assigned in the order of 1, 2, 3,... Has been described as an example of the index, but if the order of the indexes themselves (magnitude relationship in the case of natural numbers) can be grasped. Therefore, for example, an alphabetic character assigned in the order of A, B, C,... May be used as an index.

DESCRIPTION OF SYMBOLS 1 ... Text area reading order determination apparatus 11 ... Content storage part (storage means)
12 ... Document image area extraction unit 13 ... Document image area division unit (division / giving means)
14: Letter estimation unit 15 ... Division processing cancellation unit (recombination means)
16 ... sentence region reading order determination unit (determination means)
S1-S18 ... Step

Claims (16)

Dividing / giving means for reading out content from the storage means and dividing it into a plurality of sentence areas, and assigning an index to each sentence area;
Determining means for determining the reading order of each sentence area based on the writing direction of the content and each index ;
The dividing / giving means is
When dividing into left and right, a symbol indicating the order in order from the left sentence area and an identifier for identifying the division pattern divided into left and right are given as the index, and when dividing up and down, the order is in order from the upper sentence area. A sentence region reading order determination apparatus characterized by assigning a symbol representing the character and an identifier for identifying a divided pattern divided vertically as the index . The dividing / giving means is
The sentence area reading order determination apparatus according to claim 1, wherein the sentence area is repeatedly divided by alternately changing each division pattern for dividing the content into right and left or up and down. When two adjacent text areas are not subdivided after being divided once or a plurality of times, and are divided into left and right and both written vertically, or divided vertically and both written horizontally, 3. The sentence area reading order determination apparatus according to claim 1, further comprising recombination means for recombining each sentence area. The recombination means includes
4. The sentence area reading order determination apparatus according to claim 3, wherein when the interval between the two sentence areas is equal to or less than a threshold value, the respective sentence areas are recombined. In the case where two adjacent text areas are both in one line and divided into left and right and both are horizontally written, or vertically divided and both are vertically written, recombination means for recombining the respective text areas is further provided. The sentence region reading order determination apparatus according to claim 1, comprising: The dividing / giving means is
The index is assigned in order from the left sentence area when dividing into left and right, and the index is given in order from the upper sentence area when dividing up and down. The sentence region reading order determination device according to claim 1. The dividing / giving means is
The index is assigned as -1, -2, -3, ... when given from the left side, and the index is given as +1, +2, +3, ... when given from the upper side. The sentence region reading order determination device according to claim 6. The dividing / giving means is
The sentence region reading order determination apparatus according to claim 1, wherein division is performed at a position of a ruled line included in the content. The determination means includes
When the content is divided horizontally, if the writing direction of the content is horizontal writing, the sentence area to which the index is assigned is the first, and if it is vertical writing, the sentence area is the rear, and divided vertically. The sentence area reading order determination apparatus according to any one of claims 1 to 8, wherein the sentence area is determined to be the destination when the sentence area is determined to be a destination. The determination means includes
If the writing direction of the content is horizontal writing, the sentence area to which the index having the smaller absolute value is given first, and the vertical writing is possible. The sentence area reading order determination apparatus according to claim 7, wherein the sentence area is determined to be later. The determination means includes
11. The sentence region reading order determination apparatus according to claim 1, wherein the writing direction of the content is determined based on an estimation result of a writing direction of each of the sentence regions. Computer
A division / granting step of reading content from the storage means and dividing it into a plurality of sentence areas, and assigning an index to each sentence area,
A determination step of determining the reading order of each sentence area based on the writing direction of the content and each index;
In the dividing / giving step,
When dividing into left and right, a symbol indicating the order in order from the left sentence area and an identifier for identifying the division pattern divided into left and right are given as the index, and when dividing up and down, the order is in order from the upper sentence area. A sentence region reading order determination method, comprising: an index for identifying a divided pattern divided vertically and an identifier for identifying a divided pattern. On the computer,
Dividing and assigning processing for reading content from the storage means and dividing it into a plurality of sentence areas, and assigning an index to each sentence area;
A determination process for determining the reading order of each sentence area based on the writing direction of the content and each index,
In the division / grant process,
When dividing into left and right, a symbol indicating the order in order from the left sentence area and an identifier for identifying the division pattern divided into left and right are given as the index, and when dividing up and down, the order is in order from the upper sentence area. A sentence region reading order determination program characterized in that a symbol representing the character and an identifier for identifying a divided pattern divided vertically are assigned as the index. Dividing / giving means for reading out content from the storage means and dividing it into a plurality of sentence areas, and assigning an index to each sentence area;
Determining means for determining the reading order of each sentence area based on the writing direction of the content and each index;
The dividing / giving means is
When dividing into left and right, the index is given in order from the left sentence area, and when dividing up and down, the index is given in order from the upper sentence area,
The index is assigned as -1, -2, -3, ... when given from the left side, and the index is given as +1, +2, +3, ... when given from the upper side. Sentence reading order determination device. Computer
A division / granting step of reading content from the storage means and dividing it into a plurality of sentence areas, and assigning an index to each sentence area,
A determination step of determining the reading order of each sentence area based on the writing direction of the content and each index;
In the dividing / giving step,
When dividing into left and right, the index is given in order from the left sentence area, and when dividing up and down, the index is given in order from the upper sentence area,
The index is assigned as -1, -2, -3, ... when given from the left side, and the index is given as +1, +2, +3, ... when given from the upper side. To determine the reading order of sentence areas. On the computer,
Dividing and assigning processing for reading content from the storage means and dividing it into a plurality of sentence areas, and assigning an index to each sentence area;
A determination process for determining the reading order of each sentence area based on the writing direction of the content and each index,
In the division / grant process,
When dividing into left and right, the index is given in order from the left sentence area, and when dividing up and down, the index is given in order from the upper sentence area,
The index is assigned as -1, -2, -3, ... when given from the left side, and the index is given as +1, +2, +3, ... when given from the upper side. To determine the reading order of the text area.

Images