JP2715930B2 - Line detection method - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a method for detecting a line segment,
In particular, lines on devices that input and recognize documents as images
Minute detection method .

[0002]

2. Description of the Related Art In reading mail and general documents,
Processing for detecting and separating the contact portion between the character and the line segment is required. As a conventional method therefor, a method using Hough transform, a method of extracting a character line by layout analysis processing and detecting a line segment from a projection pattern, and the like have been proposed.

First, a method using the Hough transform will be described. Equation y of a line segment in a two-dimensional plane such as an image
= A x + b (where a and b are constants), b =
−x · a + y, which can be regarded as a straight line equation in the ab plane. Therefore, when the cumulative value of the points on the (a, b) plane corresponding to all the black pixel points (x, y) on the image is calculated, the local maximum point (a0, b0) becomes the equation of the line segment to be obtained. If the black pixels are arranged in a line, even if there is a contact with a character or the like, it can be detected.

Next, a layout analysis process and a line segment detection method using a projection pattern will be described. For the layout analysis processing by Tsuji as a conventional example entitled "Structural Analysis of a page image based on split-detection method", there is a paper published in Electronics and Communication Engineers Technical Report pattern recognition and learning PRL85-17. Here, the input document image is recursively divided into regions by detecting blanks in the horizontal or vertical projection pattern and extracting element regions such as figures, columns, character lines, and characters. Next, one or a plurality of element regions are structured as blocks, and the attributes of the blocks and the arrangement structure between the blocks are hierarchically determined and stored in accordance with the inclusion relation of each block and the vertical or horizontal arrangement relation. You. As for the character string, the position, size and direction of the area can be obtained, so the presence or absence of a line segment such as an underline is detected from the maximum value of the projection pattern in the character string direction, and the line segment, the character and the Can be determined.

[0005]

The method using the Hough transform has a problem that the amount of calculation is large, and the method using the layout analysis processing and the projection pattern requires the projection pattern corresponding to the line segment when the document is inclined. There is a problem that the maximum value is difficult to detect.

SUMMARY OF THE INVENTION An object of the present invention is to provide a line segment detecting method which is hardly affected by the inclination of a document and which requires less calculation than Hough transform or the like.

[0007]

According to the present invention, there is provided a line segment detecting method comprising: image input means for inputting a document as an image; connected component extracting means for extracting connected components from the image; When (x, y) and P are constants, a point A that minimizes x + Py, a point B that minimizes xPy, a point C that maximizes x + Py, xPy a line segment end point detecting means for calculating coordinates of a total of four points, that is, a point D which maximizes y, and a square A represented by the points A, B, C, and D
A circumscribed rectangle determining means for calculating a circumscribed rectangular coordinate of the BCD and selecting and outputting a coordinate having a long side and a short side satisfying a predetermined condition; and a quadrangle for the connected component selected by the circumscribed rectangle determining means. when the two sides corresponding to the short sides of ABCD was sides AB and CD, the said side AB
If both sides CD are shorter than a predetermined length, the first case,
If only one of the side AB and the side CD is shorter than a predetermined length, the second case is set, and the first case or the
A short-side determining unit that selects and outputs a component that satisfies the second case; and a connected component selected by the short-side determining unit. For the component corresponding to the first case, each of the side AB and the side CD is used. The midpoint is calculated, and if the ratio of black pixels on the line segment connecting the two midpoints exceeds a predetermined value, it is determined that the connected component includes the line segment, and for the case corresponding to the second case, Is a point near the middle point of the side AB (referred to as the point D), of the two end points of the longer side (referred to as the side CD) of the side AB and the side CD.
Is calculated, a point C ′ separated from the point D by a length AB in the direction of the point C is calculated, each midpoint of the side AB and the side C′D is calculated, and a line segment connecting the two midpoints is calculated. If the black pixel ratio exceeds a predetermined value, the connected component includes a black pixel determining unit that determines that the connected component includes a line segment.

[0008] line detection device of the present invention an image input unit for inputting a document as an image, a connected component extraction unit for extracting connected components from the image, the outline coordinates of the connected component and (x, y) , P as constants, a point A that minimizes x + P · y, a point B that minimizes x−P · y, x + P ·
a line segment end point detector for calculating coordinates of a total of four points: a point C that maximizes y and a point D that maximizes x-P · y;
A circumscribed rectangle determining unit that calculates circumscribed rectangular coordinates of a quadrangle ABCD represented by B, C, and D, and selects and outputs one having a long side and a short side satisfying a predetermined condition; With respect to the connected component selected in
Wherein when the two sides corresponding to the short side was sides AB and CD of CD, the side AB and the side CD are both first case is shorter than the predetermined length, one of the sides AB and the side CD If only one of them is shorter than a predetermined length, it is regarded as a second case, and a short side determining unit for selecting and outputting one satisfying the first case or the second case, and a connected component selected in the short side determining unit. For the case corresponding to the first case, the respective midpoints of the side AB and the side CD are calculated, and if the black pixel ratio on the line segment connecting the two midpoints exceeds a predetermined value, It is determined that the connected component includes a line segment, and for the case corresponding to the second case, of the two end points of the longer side (referred to as the side CD) of the side AB and the side CD, the shorter side direction point coordinates value is close to the midpoint of the side AB and (the point D That) to select, to calculate a spaced point C 'length AB from the point D in the direction of point C, the side AB
And the midpoints of the sides C′D are calculated, and if the ratio of black pixels on the line segment connecting the two midpoints exceeds a predetermined value, it is determined that the connected component includes a line segment. And a unit.

[0009]

According to the line segment detection method of the present invention, the detection target is limited to those in which the line segment is sufficiently longer than the character line and the vicinity of both ends of the line segment does not come in contact with the character, as is often seen in postal mail. I do. Referring to FIG. 1, a connected component extraction unit 1
1, after extracting the connected component, the line segment end point detection unit 12
In step (2), a line segment end point candidate is obtained from the outline coordinates. The circumscribed rectangle determination unit 13 selects a connected component that may include a line segment based on the conditions regarding the aspect ratio and the size. The short side determination unit 14 determines whether the end point obtained by the line segment end point detection unit 12 is a part of a line segment or a part of another component. To the end point. The black pixel determination unit 15 calculates the black pixel ratio by tracking the line segment, and makes a final determination as to whether or not the pixel is a line segment.
From this, the connected component including the line segment is extracted, and at the same time, the end point of the line segment can be obtained.

[0010]

BRIEF DESCRIPTION OF THE DRAWINGS FIG.
You.

An embodiment of the line segment detecting method according to the present invention will be described with reference to FIG.

In the image input unit 10, a document is input by an image input device such as an image scanner to obtain a digital image. Hereinafter, this is referred to as a document image.

The connected component extracting section 11 performs a labeling process on the document image to extract connected components.

In the line segment end point detecting section 12, the coordinates of the outline point of the connected component obtained in the connected component extracting section 11 are (x, y), and when P is a constant, the point which minimizes x + P.y A, a point B which minimizes x−P · y, B, x + P ·
The coordinates of a total of four points, that is, a point C that maximizes y and a point D that maximizes xP · y are calculated, and are set as end point candidates of the line segment. For example, if P = 1, each point means a contact point with a line segment in the direction of 45 degrees or 135 degrees, and the tangential direction can be controlled by the value of P. For example, the following three methods can be considered as specific calculation means of the end point candidate.

While performing the contour tracing process, maximum / minimum values are calculated as needed from the coordinates.

A connected component and its circumscribed rectangle are obtained by raster labeling, and the city block from each vertex of the circumscribed rectangle is determined.
Contour distance (= Manhattan distance): A contour point at which d = | x0−x1 | + | y0−y1 | is minimum is obtained.

The city block distance Euclidean distance in: d '= (x0 -x1) 2 + (y0 -y1) was changed to ^2, determine the contact point between the circle and the contour point around each vertex of the circumscribing rectangle.

[0018] In FIG. 2 represents the original image 2 is (a) is input, representative of the line segment endpoint candidate Figure 2 (b) was obtained.

Referring to FIG. 1 again, one embodiment of the line segment detecting method of the present invention will be described.

The circumscribed rectangle judging unit 13 selects and outputs a connected component by utilizing the fact that the connected component including a line segment becomes an elongated figure. The circumscribed rectangular coordinates of the square ABCD are calculated, and those whose long sides and short sides satisfy predetermined conditions are selected and output. Also, not just the rectangle circumscribing the square ABCD
And the long side of the circumscribed rectangle of the connected component including the square ABCD
Selection can be made from the short side under the same conditions.
FIG. 2C shows an example in which the circumscribed rectangle and the long and short sides of the connected component including the square ABCD are obtained. As specific selection conditions, the aspect ratio (the ratio between the long side and the short side) is larger than a predetermined value. -The long side is longer than the predetermined value, and the short side is shorter than the predetermined value.
And so on.

The short side determining section 14 selects and outputs a connected component under the condition that the line width is shorter than a predetermined value. Specifically, two sides of the rectangular ABCD corresponding to the short sides are A
Assuming B and CD, Case 1: AB and CD are both shorter than a predetermined length, Case 2: Only one of AB and CD is shorter than a predetermined length. Select one that satisfies either of The square ABCD in FIG. 2B is an example of Case 1 and shows a case where all four points are end points of a line segment. On the other hand, the square ABCD in FIG. 3B is an example of Case 2, and only the point C represents a part of the character.

The black pixel judging section 15 calculates the black pixel ratio by tracing the line segment, and if the ratio exceeds a predetermined value, judges that the line segment is included. In case 1, the midpoints of AB and CD are calculated, and the determination is made by obtaining the ratio of black pixels on a line segment connecting the midpoints. In case 2, as shown in FIG. 3 (b), of the two end points of the long side (here, CD) of AB and CD, the coordinate value in the short side direction (here, the vertical direction) is the middle point of AB. A near point (here, point D) is determined as a part of a line segment. Since the remaining point C is determined to be a part of a component other than the line segment, a point C ′ (= a point separated by a length AB from the point D in the direction of the point C) is obtained instead of the point C. Next, each midpoint of AB and C'D is calculated, and the determination is made by obtaining a black pixel ratio on a line connecting the two midpoints.

As described above, the length, the aspect ratio,
A connected component satisfying the conditions relating to the line width and the black pixel ratio is detected, and the end point coordinates of the line segment can be obtained.

[0024]

According to the present invention, regarding the contact between a character and a line segment, the case where both ends of the line segment project sufficiently beyond the character string as shown in FIG. As described above, when only one end of the line segment protrudes from the character string and the other end touches the character, these are determined to be the contact area, and the end point coordinates of the line segment can be obtained. The inclination of the line segment affects only when the circumscribed rectangle determination unit 14 uses the aspect ratio, and is not substantially affected.

[Brief description of the drawings]

FIG. 1 is a flowchart showing a line segment detection method of the present invention .

FIG. 2 is a diagram illustrating a detection example in a case where both ends of a line segment project sufficiently from a character string;

FIG. 3 is a diagram illustrating a detection example in a case where only one end of a line segment protrudes from a character string and the other end contacts a character;

[Explanation of symbols]

 Reference Signs List 10 Image input unit 11 Connected component extraction unit 12 Line segment end point detection unit 13 Bounding rectangle judgment unit 14 Short side judgment unit 15 Black pixel judgment unit

Claims (2)

(57) [Claims] 1. An image input means for inputting a document as an image, a connected component extracting means for extracting a connected component from the image, and when the contour coordinates of the connected component are (x, y) and P is a constant , X + P · y at minimum A, x−P ·
Point B that minimizes y, Point C that maximizes x + P · y, x
A line segment end point detecting means for calculating coordinates of a total of four points including a point D which maximizes P · y, and a circumscribed rectangular coordinate of a square ABCD expressed by the points A, B, C, and D is calculated; A circumscribing rectangle determining means for selecting and outputting one having a long side and a short side satisfying a predetermined condition, and a connected component selected by the circumscribing rectangle determining means corresponding to the short side of the square ABCD when the two sides was sides AB and CD, is shorter than the side AB and the side CD are both predetermined length first
One case, if only one of the side AB and the side CD is shorter than a predetermined length, a second case is selected, and a short side determining means for selecting and outputting a result satisfying the first case or the second case; Regarding the connected component selected by the short side determining means, for those corresponding to the first case, the respective midpoints of the side AB and the side CD are calculated, and the black pixels on the line connecting the two midpoints are calculated. If the ratio exceeds a predetermined value, it is determined that the connected component includes a line segment . For the case corresponding to the second case, the side AB and the side C
Of the two end points of the long side (referred to as the side CD) of D,
A point whose coordinate value in the short side direction is close to the middle point of the side AB (referred to as the point D) is selected, and the length AB in the direction from the point D to the point C is selected.
Is calculated, the midpoints of the side AB and the side C′D are calculated, and if the black pixel ratio on the line segment connecting the two midpoints exceeds a predetermined value, A black pixel determining unit that determines that the connected component includes a line segment. 2. An image input unit for inputting a document as an image, a connected component extracting unit for extracting a connected component from the image, and when the contour coordinates of the connected component are (x, y) and P is a constant. , X + P · y at minimum A, x−P ·
Point B that minimizes y, Point C that maximizes x + P · y, x
A line segment end point detection unit that calculates coordinates of a total of four points, ie, a point D that maximizes P · y, and a circumscribed rectangular coordinate of the square ABCD represented by the points A, B, C, and D; A circumscribed rectangle determination unit that selects and outputs a long side and a short side satisfying a predetermined condition, and a connected component selected by the circumscribed rectangle determination unit, and corresponds to the short side of the square ABCD. When the two sides are a side AB and a side CD, the first case is provided if both the side AB and the side CD are shorter than a predetermined length, and if only one of the side AB and the side CD is shorter than a predetermined length. A second case, a short side determining unit that selects and outputs the one that satisfies the first case or the second case, and a connected component selected by the short side determining unit that corresponds to the first case and the side AB for the sides CD Those calculates the middle point, if a black pixel ratio on a line segment connecting the two midpoints in which exceeds a predetermined value, the connected component is determined to contain a line segment, corresponding to the second case for the out of 2 end points of the long sides (and the side CD) of the sides AB and the side CD, the coordinate values of the short-side direction (the said point D) the midpoint point near the said side AB
Is calculated, a point C ′ separated from the point D by a length AB in the direction of the point C is calculated, each midpoint of the side AB and the side C′D is calculated, and a line segment connecting the two midpoints is calculated. A black pixel determination unit that determines that the connected component includes a line segment if the black pixel ratio of the line segment exceeds a predetermined value.