JPS6286465A - Document image area division method - Google Patents

Abstract

(57) [Summary] This bulletin contains application data before electronic filing, so abstract data is not recorded.

Description

DETAILED DESCRIPTION OF THE INVENTION [Field of Application of the Invention] The present invention relates to a device for inputting and storing a document as an image, and particularly for storing an input document image in a character area.

This invention relates to a method for dividing document images into graphic areas, photographic areas, etc.

[Background of the invention]

Conventional document image area segmentation methods include, for example, creating a histogram by projecting the document image in the vertical and horizontal directions, and determining the locations where the histogram changes extremely.
Method for extracting character strings (Akita, Masuda: [Paper component extraction method that does not rely on format specification information" Journal of the Institute of Electronics and Communication Engineers)
83/1 v o 1.

J66-D, Nα1. 111 to 118), and a method that uses two-dimensional Fourier transform of document images (Hoshino: "
``Method for area segmentation of printed document images'', JP-A-59-55
581 Publication), a method of dividing regions by focusing on the characteristics of white runs and black runs that appear in a document image (Murao, Sakai:
“Extraction of structural information from document images”, Proceedings of the 21st National Conference of the Information Processing Society of Japan, 7H-1, pp. 857-85
8 pages).

Methods that use vertical and horizontal projection of a document image or two-dimensional Fourier transformation are based on global information of the image, and can efficiently divide the document into nine parts if there are characters over a wide area. , this becomes difficult when the text part is small. Furthermore, since global information is processed, a memory capable of storing all images is required, which increases the amount of processing.

There is also a method that focuses on the characteristics of white and black runs in a document image.
Since runs are processed, there is a problem in that the amount of data to be processed becomes large.

[Purpose of the invention]

An object of the present invention is to provide a document image area division method that does not require a large image memory and has high processing efficiency.

[Summary of the invention]

In order to achieve the above object, the document image region segmentation method according to the present invention includes a step of focusing on connected components in a document image including a character region and a figure or photo region, and extracting a rectangle circumscribing each connected component. and a step of determining the average size of character circumscribing rectangles constituting a vertically or horizontally written character string from the adjacency relationship of each of the circumscribed rectangles. and a step of distinguishing between the two.

The above-mentioned method of the present invention utilizes the following properties of a circumscribed rectangle of connected components in a document image. That is, characters used in a document generally constitute a character string written vertically or horizontally, and (1) in the case of a horizontally written character string, rectangles of similar height are arranged close to each other in the horizontal direction.

(2) In the case of a vertical text string, rectangles with similar widths are arranged close to each other in the vertical direction.

(3) The circumscribed rectangle of connected components in a graphic area or photo area is 2 times taller than the circumscribed rectangle of connected components that make up a character.
The width is quite large, and there is no similarity in size or position.

(4) The number of connected components that make up a character is greater than the number of connected components that make up a graphic area or a photographic area.

Therefore, by utilizing these properties, it is possible to divide a text portion and other areas in a document image by, for example, the procedure shown in FIG.

That is, a circumscribed rectangle of connected components is extracted from the input document image (process 100). Next, vertical writing/horizontal writing is determined using the extracted outer rectangle information (process 200). This determination is performed by the method described below, focusing on the properties (1) and (2) above. First, distances between mutually adjacent rectangles that are considered to constitute a character string are determined for the entire image for both vertical writing and horizontal writing, and the distances are averaged. The assumption with the lower average value is determined to be correct. Simultaneously with the vertical writing/horizontal writing determination, the average height and one width of the characters are estimated (process 300). This is done by calculating the average of the height and width of each rectangle determined to constitute a character string over the entire image. Based on the estimated height and width of the character part determined in this way, we assume that rectangles with clearly larger values (height and width) constitute the graphic area and the photo, and If there are any, they are integrated and extracted as a "figure, photo area" (process 400). Regarding the extracted "figure, photo area",
The original image is examined and separated into a "graphic area" and a "photographic area" (process 500). In this case, focusing on the general property that figures have many white background parts and photographs have many black background parts, for example, by determining the black and white pixel ratio within each area, it is determined which of the above areas it is. Here, if the black-and-white pixel ratio is used as the criterion, when extracting the circumscribed rectangle of connected components, the black-and-white pixel ratio within the rectangle can be determined at the same time. Without "shape area"
Separation of "photo area" is possible.

Finally, for rectangles that are determined to constitute characters, extract character strings by integrating them vertically in the case of vertical writing or horizontally in the case of horizontal writing, and extract the character area by integrating each character string. (
Process 600).

[Embodiments of the invention]

The present invention will be explained in detail below.

FIG. 2 is a schematic explanatory diagram of the area division method according to the present invention. A document to be processed is input as input document image data 10 to an image input device such as a scanner. The connected component circumscribed rectangle extraction unit 11 extracts circumscribed rectangles of connected components from the input document image data 10 and writes the result into the circumscribed rectangle information table 12. This process is described in, for example, "Digital Image Processing J (Rosnfeld, kak),
A known method can be employed, such as the one published by Shin Nagao (supervising translation), Kindai Kagakusha, pages 353 to 361). There are various formats for representing rectangular information; for example, maximum values in the vertical and horizontal directions.

Use the minimum value. 131 is an area division processing unit, [process 601): When the determination result of process 200 is vertical writing, process 6
02 is executed, and when horizontal writing is performed, process 604 is executed.

[Process 602]: In FIG. 8, "r character".

Rectangles that are determined to be "horizontal characters" and "vertical characters" are used as character constituent elements, and groups of rectangles that mutually satisfy the directional connection condition are found. Find a rectangle that circumscribes all the rectangles in the winter group and use it as a "character string."

[Process 603): Regarding the rectangle representing the "character string" obtained in Process 604, when two horizontally adjacent rectangles satisfy the following condition, they can be integrated as a character area.

Let the two adjacent rectangles be i+ -1 (11 is the right neighbor of i), and let the maximum and minimum values of their X and Y coordinates be Xm1n
l, XmaXI93'+++1nl, ymaX
l,! , +m1nJyX maxJ t :l'
m1nd l y lla! If J, then (j)
There is some overlap in the vertical position.

wax(y+++tnt+ V□nJ)〈++n('/
maXI'/Il+aXj) (14) (5) The lateral distance is γ1 times or less the average width of the two rectangles.

xmsna −x+maxt<γI X (0'@ax
t Xmtnt) + (XmaxJ-xmtnz)
) / 2...(15) However, γ1 is a parameter that indicates the ratio of the distance between character strings to the width of the character string, and in the case of a normal printed document, it is 1
~2.

For the rectangle showing all the character strings, the above conditions (i), (
Find groups of rectangles that mutually satisfy j), and extract rectangles that circumscribe all rectangles in each group as a "character area."

[Process 604): In the same way as Process 602, groups of rectangles that mutually satisfy the horizontal connection condition are found among the character components, and for each group, a rectangle that circumscribes all the rectangles is found, and a "character string" is found. do.

[Process 605): Regarding the rectangle representing the "r character string" obtained in Process 604, when two vertically adjacent rectangles satisfy the following conditions, they can be integrated as a character area. If two adjacent rectangles are II j (F is the descent of j), then (iii) there is an overlapping portion in the lateral position.

+++ax(X++uni, xmtna)〈ll
tn(xmaxt XmaxJ) ”' (
15) (tv) The vertical distance is 72 times or less the average height of the two rectangles.

3/ m1n-y maxt < γ2X ((3/
+aaxi Vmlni) +('/maxa
3/m+nj) ) / 2...(16) However, γ2 is a parameter indicating the ratio of the distance between character strings to the height of the character strings, and is 1 in the case of a normal printed document.
~2.

The above condition (iii) is applied to the rectangle representing all character strings.
A group of rectangles that mutually satisfy (tv) is found, and in each group, a rectangle that circumscribes all the rectangles is extracted as a "character area".

〔Effect of the invention〕

According to the present invention 41. This has the following effects.

(1) Connected component glue ■Since the basic unit of processing is a bounded rectangle, a document image can be divided into "text area,""graphicarea," and "photo area" more efficiently than processing using pixels or runs as the basic unit. be able to.

(2) Except for separating the "graphic area" and "photo area."

Processing is performed using only the circumscribed rectangle information of connected components. Extraction of the circumscribed rectangle of connected components can be performed with line memory, but everything except separation of the "figure area" and "photo area" can be achieved with line memory alone. In addition, for separation of "graphic area) and photographic area," if you use features that can be obtained at the same time when extracting the circumscribed rectangle, such as the black-and-white pixel ratio, as the feature quantity when performing separation, the entire process can be performed on the entire image. It can be realized using only a line memory without using a memory for storing data.

[Brief explanation of drawings]

FIG. 1 is an overall flow diagram showing the procedure of region division processing according to the present invention, FIG. 2 is an explanatory diagram of the region division method according to the present invention,
FIG. 3 is a diagram showing an example of the configuration of a bird wuf for the above-mentioned area division, FIGS. 4 and 5 are explanatory diagrams regarding the interposition conditions in the horizontal direction and the vertical direction, respectively, and FIGS. 6
-2, FIG. 7, and FIG. 9 are detailed flowcharts of FIG. 1, respectively. If the process is not completed, the process 207 is executed. [Process 205): Find the distance dh between the rectangle of interest and the found rectangle. The maximum X coordinate value of the rectangle of interest is Xmaxi, and the minimum X coordinate value of the rectangle found is X+
If m1XJ, d h = x m1nd x max+
-(7) dh allows negative values. [Process 206): Number of sets of rectangles adjacent in the horizontal direction Cou
ntH and the sum of distances between rectangles distH are updated. Also, the width W and height h of the rectangle we are looking at, the sum of the widths νsum
)l, update the sum of heights hsumH. [Process 207): Similar to the horizontal direction, find a rectangle that satisfies the vertical adjacency condition and is closest to the bottom. [Process 20B]: If a rectangle satisfying the vertical adjacency condition is found, process 209 is executed; if not, process 302 is executed. [Process 209]: Find the short distance du between the rectangle of interest and the found rectangle. The maximum y-difference value of the rectangle of interest is 'l manl, and the minimum y-difference value of the found rectangle is 3'mi. Then, d v='fmsra-y+max+
”' (8) dv allows negative values. [Processing 2103: Number of pairs of rectangles adjacent in the vertical direction Cou
ntV and the sum of distances between rectangles distV are updated. Also, the width W and height h of the rectangle we are looking at, the sum of the widths wsum
V, update the sum of heights hsumV. [Process 211): Average distance a between horizontally adjacent rectangles
vrdH and the average distance between vertically adjacent rectangles avr
Find dV. [Process 21.2): avrd)I-avrdV
When the value of is smaller than one ε, it is determined to be horizontal writing, and when it is larger than ε, it is determined to be vertical writing. When the value is between -ε and ε, it is impossible to judge. Here, E is a non-negative constant and is a parameter that determines the range in which 1 cannot be determined. If E=0, avrdH
It becomes impossible to judge only when = avrdV. [Process 300): Estimate the height and width of the character based on the result of process 200. FIG. 7 is a diagram showing the detailed flow of character height and width estimation in process 300. (Step 2) [Processing 301): When the judgment result in Processing 200 is vertical writing,
Processing 302. Execute process 308, and when writing horizontally, process 3
04. Processing 305 is executed. [Processing 302), (Processing 303]: Average height av of rectangles determined to constitute a vertical character string in Processing 200
The average avrW of rH and width is determined and used as an estimated value. avrH=hsumV/countV
0°"(9)avrW=vsumV/count
V-(10) [Processing 304), [Processing 305]: Find the average height avrl (and average width avrW) of the rectangles determined to constitute the horizontal character string in the process 200, and calculate the estimated value. avrH=hsumH/countl(-(11)a
vrW=wsumV/countH-(12) [Processing 4
00) Based on the estimated values of the character height and width found in process 300,
Extract "shape, photo area". FIG. 8 is a diagram showing extraction thresholds. Here, st. sz, tt, tz are parameters, O<81<1<
s x , O < t 1 < 1. <tx. A rectangle whose width is larger than (S2) X (aura) or whose height is larger than (tz) and integrate them into the "figure, photo area". [Processing 500] Processing 4. In the "graphic and photo areas" extracted by OO, the black and white pixel ratio rwb in each area is determined. To find the black-and-white pixel ratio within a region, it is generally necessary to use the original image data, but if you simultaneously calculate the number of black pixels for connected component extraction, etc., you can find the black-and-white pixels without examining the original pixels. can. rwb=numtil/numB ・
+ (13) However, numV: number of white pixels, numB
: is the number of black pixels, and when rwb>u, "graphic area J
, rwb<V, it is determined to be a "photograph area". u, v
is a parameter, 0 < u < v <'J. [Process 600] The rectangles determined to be character constituent elements in process 400 are integrated to extract "r character area." FIG. 9 is a detailed flow diagram of process 600. Using the information in the circumscribed rectangle information table 12, region division is performed according to the flow shown in FIG. 1, and a region division result 14 is obtained. In this area division process, the original image data is used to separate the "figure area" and the "photo area", but other processes can be performed only using the circumscribed rectangle information stored in the table 12. . FIG. 3 shows an example of a hardware configuration for performing the above processing. Document image data is input into the image memory 25 by the image input device 24. The image processing device 26 extracts connected components from the image data in the image memory 25 and writes the circumscribed rectangle information to the circumscribed rectangle information table 12 on the main memory 21 . The region division process is executed by the CPU 20 using this circumscribed rectangle information and image data. The region division results are stored in the image file 27 together with the image data. In addition, the results of region division can be displayed on the display 22 in different patterns for each type of region, outputted to an image output device 23 such as a printer, and the original image can be displayed and outputted by region. . CCPU2
0 also controls the operation of each element described above. In this example,
Although a dedicated image processing device 26 was used for the purpose of high-speed processing,
When extracting a circumscribed rectangle of connected components by program processing of the CPU 20, the image processing device 26 can be omitted. Next, details of the processing shown in FIG. 1 will be explained. First, the horizontal and vertical adjacency conditions are determined by rectangle-1- shown in Fig. 4.
yJ is defined as follows. [Horizontal adjacency conditions] (1) In the horizontal direction, there is no relationship in which one side includes the other. (Xm1nI Xm1□J)X(xmaxi X+
ma□)>0 (1) (2) The vertical positions (y coordinates) of both centers of gravity are between the vertical overlaps of the two rectangles. (3) They are similar in height. 1/α< h i/ h J <α (α>1) α is
A parameter that indicates the height ratio range. ...(3) [Vertical adjacency condition] In Q, the rectangle shown in FIG. 5 has the following conditions: (1) In the vertical direction, one does not contain the other. (xminh x+mtnk)X(xmaxkxma
xt)>O・= (4) (2) The lateral positions of both centers of gravity (Xm mark) are between the lateral overlaps of the two rectangles. maX(y+m1nkt ymtnt)<(gyh+
gyt)<mtn(ymaxh ymaxt)gyk
=(3/+5axh Vma□)/2gyt=(ym
axx y*axk)/2 ”' (5
)(3) The widths are similar. [Process 100] Extract the circumscribed rectangle of the connected component from the image data, and write the information in the circumscribed rectangle information table. [Process 200] Vertical or horizontal writing of the document image is determined from the circumscribed rectangle information of the extracted connected components as follows. 6-1.6-2 are diagrams showing the detailed flow of vertical writing/horizontal writing determination in process 200. In the following description, the circumscribed rectangle of a connected component is abbreviated as a rectangle. (Process 201): Initialize variables. CountH. distH is the sum of the number of pairs of rectangles that satisfy the horizontal adjacency condition and are close to each other and the distance between the rectangles, hsum
l(, wsumH is the sum of the width and height of those rectangles. Similarly, CountV, distV, hsumV,
wsumV is that in the vertical direction. [Process 202): Repeat processes 203 to 21.0 for all the rectangles obtained in process 100. At the end of the repetition, process 211 is executed. [Process 203]: For the rectangle of interest, find a rectangle that satisfies the horizontal adjacency condition and is closest to the right side. Finding the right neighbor is a means to prevent a set of rectangles from being processed redundantly, and it is also possible to find the left neighbor, or to take the overlap into consideration, to find both neighbors. [Process 204): If a rectangle that satisfies the horizontal adjacency condition is found in process 203, process 205 is executed, and Figure 8 is a diagram showing the classification of regions according to the height and width of the rectangle. 10... Input document image data, 11... Connected component circumscribing rectangle extraction unit, 12... Connected component circumscribing rectangle information table, 13... Area division processing unit, 1-4... Area division result, 20...CPU, 21...Main memory, 2
2...Display, 23...Image output device, 24.
...Image input device, 25...Image memory, 26...
Image processing device, 27... image file.

Claims (1)

[Claims] A step of extracting a rectangle circumscribing each connected component by focusing on connected components in a document image including a text area and a graphic or photographic area, and constructing a vertically written or horizontally written character string from the adjacency relationship of each of the circumscribed rectangles. A method for dividing a document image into an area, the method comprising the steps of determining a flat size of a character circumscribing rectangle, and distinguishing between a character area and a figure or photograph area other than characters based on the average size.