JPH0434668A - Image processor - Google Patents

Abstract

PURPOSE:To improve the performance of drawing recognizing processing by shaping an approximate straight line found from a thinned image obtained by thinning an input image in accordance with the outline information of the input image. CONSTITUTION:A comparatively accurate approximate segment found from a thinned image is shaped by using the approximate segment of an outline. In the case of a segment L1 having an approximate straight line {Li} found from a thinned image shown in the figure, segments R1, R5 are respectively found out on the right and left sides of the figure and the corresponding processing of these segments is applied to the whole segment Li. Then, the shaping processing of the 1st approximate straight line {Li} is executed by using the information of the 2nd approximate straight line {Ri} based on relation between the corresponding segments Li, Ri. Thus, various recognition processing based on linearly approximate data can be highly accurately executed.

Description

Detailed Description of the Invention (Industrial Application Field) The present invention relates to image processing that can accurately obtain approximate line segment figures of an input image when performing recognition processing on a drawing input as an image in a drawing reading device or the like. Regarding equipment.

(Prior Art) Recently, various drawing reading devices have been developed that input images of various drawings such as maps and facility management charts, recognize characters, symbols, and line segments in the input images, and input data. . In order for this type of drawing reading device to recognize drawing components such as characters, symbols, and line segments in input images with high performance, an important issue is how to accurately detect various line information in drawings. becomes.

Conventionally, the following reports have been made as typical methods for detecting straight lines in graphic areas in drawings of this type. One of them is a method of detecting straight lines in a drawing by thinning a graphic area in the drawing and approximating the resulting thin line to a polygonal line. However,
The drawback is that a highly accurate approximate straight line cannot be obtained due to noise in the line thinning process.

On the other hand, by approximating the outline of the connected black pixel area of the figure area with polygonal lines and finding parallel line bears of these outlines,
There is a method of obtaining an approximate straight line by finding the center line (core line) of a line segment in a drawing. However, this method has a problem in that highly accurate approximate straight lines cannot be obtained due to the following reasons.

In other words, the approximate straight line (core line) of the graphic area in the drawing is
Since it is determined based on a contour line approximated by a polygonal line, there is a problem in that the accuracy of the core line greatly depends on the accuracy of the contour line approximation. Moreover, when approximating the contour line to a polygonal line,
Generally, the end point of the line segment is found on the point of change of curvature, so there is a problem that the accuracy of the approximate straight line changes greatly even if there is a shift of just one point (one pixel). In a place where the curvature changes greatly, such as a part, the shape of the contour line itself is not accurate because it is easily affected by noise during binarization of the input image.

Furthermore, in drawings, there are many cases where a parallel line pair of straight lines approximating the outline cannot necessarily be obtained, for example, when a character string touches one side of a straight line.

In such a case, since the line segment itself cannot be recognized, a problem arises in that the core line cannot be detected.

(Problem to be Solved by the Invention) In the past, when line segments in a drawing input as an image are approximated by a straight line and used for recognition processing of characters, symbols, and line segments, the accuracy of the straight line approximation has not been improved. There were some problems, such as being a factor in the deterioration of recognition performance.

The present invention has been made in consideration of these circumstances, and its purpose is to easily obtain approximate straight lines with high accuracy for drawings input as images, and to improve drawing recognition processing performance. An object of the present invention is to provide an image processing device that can greatly contribute to

[Structure of the Invention] (Means for Solving the Problems) An image processing device according to the present invention obtains approximate line segments of the input image from a thinned image obtained by thinning the input image, and connects the input images. The present invention is characterized in that an approximate line segment of the outline of the black pixel area is obtained, and the approximate line segment obtained from the thinned image is shaped using the approximate outline segment.

(Function) According to the present invention configured as described above, since the approximate line segment with a certain degree of accuracy obtained from the thinned image is shaped using the contour line approximate line segment, noise during the line thinning process is reduced. Since it is possible to effectively correct the factors that reduce accuracy due to factors such as the above, it is possible to obtain an approximate straight line of the input image with high accuracy through simple processing.

(Example) Hereinafter, an example of an image processing apparatus according to the present invention will be described with reference to the drawings.

FIG. 1 shows the flow of the basic processing procedure of the embodiment apparatus. In this embodiment device, a processing procedure (processing A) for performing line thinning processing on an input image, and approximating the line thinning processed image with a polygonal line to obtain a first approximate straight line, and determining a connected black pixel area of the input image, A processing procedure (processing B) for obtaining a second approximate straight line by performing polygonal line approximation to the outline of the connected black pixel area is performed in parallel.

Thereafter, the first and second approximate straight lines are correlated according to their positional information in the input image and the characteristics of the approximate straight line (C), and the first and second approximate straight lines obtained from the thinned image are processed according to the correspondence relationship. The approximate straight line is shaped according to the second approximate straight line obtained from the contour line
), which is characterized in that an approximate straight line of the input image with high approximation accuracy is obtained.

Here, the first approximate line segment obtained from the thinned image obtained by thinning the input image is (L11,
Further, the second approximate line segments obtained by linearly approximating the outlines of the connected black pixel regions of the input image are each expressed as IRil.

Basically, as mentioned above, the first approximate straight line (Ll) is obtained by appropriately applying various line thinning processing methods proposed in the past to the input image. A thin line image (equivalent to ) is obtained, and each line segment in this thin line image is obtained by linear approximation by using, for example, a point with a large curvature as a break point and connecting each break point with a straight line.

Through such straight line approximation processing of the thinned image, for example, the first approximate straight line of the input image as shown in FIG.
For example, line segment information 11. as shown in FIG.
1! 2. Information about ... and each of these line segments 11
End point P of ゜12,... 1. P2. . . information as shown in FIG. 4 is required. In other words, each line segment #1 approximated by a straight line. N2. Where are the end points of ... and each end point P1. P2. ... is required to obtain information about which line segment it belongs to.

On the other hand, the second approximate straight line IRl) is obtained by obtaining all contours of connected black pixel regions of the input image and subjecting these contours to linear approximation processing. The contour detection of this input image is performed using, for example, “A high 5peed raster to v
ector conversionuslng 5pe
cial hardware for contour
tracking'' (IAPRworkshop o
n CV-5peclal hardware an
industrial application,
1988. This is done using a method such as that introduced in pp. 18-23).

This contour detection process is achieved by executing the following process while tracing the contour of the connected black pixel area.

That is, in this contour tracking process, first, [black/
While tracing the boundaries of white, it sequentially outputs chain codes that indicate the direction of the contour line. This chain code consists of a series of codes in which the direction indicated by the [black/white] boundary in the input image is set in 45'' increments, for example, as shown in Figure 5. First, the calculation shown in the following equation (1) is performed according to the chain code, and the curvature Ci at the tracking point pt is calculated.

However, kj is a chain code at the contour tracking point Pj.

Next, on the above contour line, a continuous contour line (Pl, P2°...
・Extract Pn). Then, based on this continuous contour line chain code, a straight line [P 1
−P n], the area S of the closed region composed of
Obtained by the calculation shown in the formula.

S-Σ (Xi* δxi-Yi* δyl)
-(2) However, (Xi, Yi) are the coordinate values of point P1, δxi-Xi+l -Xi, δyi -Y
i+1-Yi.

When the value (area S) obtained in this way is smaller than the threshold value, this continuous contour line represents one straight line, and the above-mentioned end point P1. Line segment connecting Pn [P L-P n]
Let be the approximate straight line of the continuous contour line.

Further, when the value (area S) obtained by the calculation shown in equation (2) above is larger than the threshold value, it is determined that the continuous contour line is composed of a plurality of line segments. Then, this continuous contour line is approximated by a polygonal line, for example, by the two-division method. This two-division method is, for example, “Pattern classification a
nd 5scene analyzes″R1chard
O, Duda and Peter E, Hart
.

A Viley-1interseince Publl
cation, pp 43B-339.

In this way, the above-described process is executed for all the contours of the input image, and each approximate straight line for all the contours that are subtracted as a result is registered as the second approximate straight line (Ril). Regarding the linear approximation process, it is possible to simply approximate the outline of the input image using a polygonal line using the 2-division method, but performing the process described above is more accurate in that the outline of the input image is approximated by a straight line. You can get something good.

As described above, the first approximate straight line I for the input image
Once L it and the second approximate straight line (R1) are obtained, next these first and second approximate straight lines IL i
Correlation is made between l and fRil. This correspondence processing is performed for each line segment L1 of the first approximate straight line +L l+, sono end point P 1O (XiO, YiO)
The second approximate straight line I existing in the vicinity of Xil, Yil)
The process starts by searching for line segment R1 in R1). In this search, for example, from the midpoint Pi2 of the line segment Li, we distinguish both the left and right directions with respect to the direction of this line segment, and among the line segments closest to the midpoint Pi2, the threshold value θ is determined by the angle formed with the line segment L1.
This is done by finding the following straight line.

For example, in the example shown in FIG. 10, which will be described later, regarding the line segment L1 of the approximate straight line (L il) obtained from the thinned image, the line segment R1 is on the right side in the figure, and the line segment R5 is on the left side. Such line segment correspondence is performed for each line segment Li.

Next, based on the relationship between the line segment Li and the line segment Ri associated as described above, a shaping process is performed on the first approximate straight line (L i ) using the information of the second approximate straight line (Ril).

This shaping process is performed on two line segments R that are associated with line segment Li.
This is realized by determining the position of the end point P1 of the thin approximate line segment Li based on i.

A pair of contour approximation line segments (bare) that are two contour approximation line segments R1 associated with the thin line approximation line segment Li consisting of (Ri
, Rj).

Then, the straight line determined by this set is determined, for example, as shown in FIG. 7, at the midpoint c of the line segment (indicated by a broken line) that connects the end points of the contour approximation line segments Ri and Rj.11. Define as a straight line determined by Cjj.

However, the contour approximate line segments corresponding to the thin approximate line segment L1 do not necessarily exist as a set as described above. In that case, for example, as shown in FIG. 8, the thin approximate line segment L
A line segment k that corresponds to the thin approximate line segment L1 passing through the midpoint P1 of L and is parallel to the contour approximate line segment R1 is defined as the straight line. By defining a straight line in this way, in the following explanation, when a pair of contour approximating line segments (R1, Rj) is indicated, two contour approximating line segments R1 exist even if one of them is missing. The same argument can be made in this case.

Also, the contour approximation line segment pair (R1, R2) and the contour approximation line segment pair (
The contour approximation line segment R1(i
=1. ..., 4) are all different, the straight line determined by the pair of contour approximating line segments (R1, R2) and the straight line determined by the pair of contour approximating line segments (R3, R4) described above. Define as an intersection. Moreover, the above contour approximation line segment R1 is [R1
=Rj (1-1or 2.j-3or 4)], the intersection point is defined as a point Q obtained as follows.

That is, as shown in FIG. 9, for example, the intersection Q connects the end points of the contour approximation line segment R2 and contour approximation line segment R3 with a straight line connecting the midpoints of the two thin approximation line segments LL and L2. Assume that it is an intersection with a straight line m that passes through the midpoint of the line segment and is perpendicular to the contour approximation line segment R1 (-R4).

Under the above definition, the first approximate line segment (L il
The formatting process for ' is proceeded as follows.

Specifically, when the line segment is branched as shown in FIG. 10, for example, shaping of the thin approximate straight line L1 by determining the position of the end point P1 of the thin approximate straight line L1 is performed as follows. That is, at the end point P1 of the thin approximate straight line L1, there are three thin approximate straight lines LL, L2, .
L3 is connected. Therefore, each of these thin approximate straight lines Ll.

Second approximate line segment (R1) corresponding to R2 and R3, respectively
The set (R1, R5) (R2, R3) (R4, R
5) respectively.

In this case, the second approximate line segment [Ri) passes through each intersection of the set (R1, R5) (R4, R5) and is parallel to the contour approximate line segment R5, and the second approximate line segment Find the position of the intersection point Qi of the straight lines found from the set (R2, R1) of the line segment (R1). The position of the intersection point Q1 obtained in this manner is changed to the position of the end point PI to shape the thin approximate straight line L L (L 2 . L 3.).

Furthermore, when the line segment is bent as shown in FIG. 2 approximate line segment (set of Rfl (
R1, R2) Find (R3, R4). And the set (R1, R2) of these second approximate line segments (R1)
Find the position of the intersection Q1 of (R3, R4), and
The position of is changed to the position of the above-mentioned intersection Q1. This end point Pi
By changing the position of the thin approximate straight line L1. L2 is reshaped.

Furthermore, in the case where line segments intersect as shown in FIG. 12, as in the example shown in FIG. , thin approximate straight line LL, second approximate line segment (R1) corresponding to L2 (R2, R3) (R4, R5)
, and change the position of the end point P2 of the thin approximate straight line L3, which is found as a polygonal line and is 0, to the position of the intersection point Q1 of the other thin approximate straight line L3. Second approximate line segment (Ri) corresponding to L4
The position is changed to the intersection Q2 of the set (R8, R7) (RLRI). Note that the intersection Ql is the second approximate line segment iR
It is between the set (RI3.R7) of il, and the set (R8,
R1), the line segment Lx that virtually connects the points P1 and P2 is removed, the points P1 and P2 are merged, and the coordinate values are set as the intersection point Q1 and the intersection Q2. The midpoint between The position thus obtained is changed to the position of the end point P1 of the thin approximate straight line LL (L2.L3.L4). Through this process, the thin approximate straight line LJ,
.

L2. L3. L4 is shaped respectively.

Further, in the case where a bent line segment is in contact with a straight line as shown in FIG. 13, the following procedure is performed.

In other words, as shown in the line segment L1, the line segment length is short, and there is no corresponding contour approximation line segment, and the line segment L1
If the contour approximation line segment corresponding to the other two thin line approximation line segments connected to the end point P1 of is a common line segment R4,
The line segment L1 is removed. Then, the positions of PL and P2, which are the end points of the line segment L1 and the connection points with other thin line approximation line segments, are moved to the contour approximation straight line pair (R3, R4) (R4, R5
), and the pair of contour approximation straight lines (R1, R2) (
R3, R4), respectively, and shape the thin approximate line segment.

Furthermore, as shown in FIG. 14, two contour approximation line segments (R1
, R2), the line segments LL, . . . L5 are removed. Then, a new line segment connecting points P3 and P4 and a line segment connecting points P5 and P6 are respectively generated to shape the thin approximate line segment.

By applying the above processing to each end point of the first approximate straight line (L11), the thin approximate line segment is shaped.

According to the shaping process described above, the approximate straight line of the drawing obtained from the thinned image obtained by thinning the input image is shaped using the approximate straight line obtained from the contour line of the input image. Even if the accuracy of the thinned image is poor due to noise in the input image and the accuracy of the approximate straight line is poor due to this, this can be effectively corrected according to the contour information of the input image, It becomes possible to obtain corrected linear approximation data of the drawing with high approximation accuracy. Moreover, since the approximate straight line obtained from the thinned image is shaped according to the contour line information of the input image while associating line segments as described above, it is possible to easily and efficiently obtain highly accurate straight line approximate data. Many practical effects can be achieved.

Note that the present invention is not limited to the embodiments described above. For example, instead of completely thinning the input image, a filled area can be obtained by performing partial thinning processing that removes black pixels on the boundary a limited number of times.

Therefore, the area where the line width did not completely become [1] due to the above partial line thinning process is determined as a filled area,
That portion can be shaped using the same process as when shaping the thin line approximation straight line described above using the contour information of the partial thinned image. In addition, the present invention can be implemented with various modifications without departing from the gist thereof.

[Effects of the Invention] As explained above, according to the present invention, a method is introduced in which an approximate straight line obtained from a thinned image obtained by thinning an input image is shaped according to information about the contour of the input image. By doing so, it becomes possible to efficiently obtain linear approximation data that is simple and highly accurate. As a result, great practical effects can be achieved, such as making it possible to perform various recognition processes based on linear approximation data with high precision.

[Brief explanation of drawings]

The figures show an image processing device according to the present invention, and FIG. 1 is a diagram showing a schematic processing flow in the embodiment device, FIG. 2 is a diagram showing approximate line segments of a thinned image, and FIG.
Figure 4 shows an example of the data structure of a thin approximate line segment, Figure 5 shows a chain code, and Figure 6 shows the relationship between an approximate line segment that approximates a contour line and the original image. , Fig. 7 shows a straight line determined by a set of contour approximating line segments, and Fig. 8 shows a straight line determined by the relationship between a contour approximating line and a thinned approximating line when a set of contour approximating line segments does not exist. 9 is a diagram showing a straight line, FIG. 9 is a diagram showing the intersection of two contour approximation line segments, and FIGS. 10 to 14 are diagrams for explaining the shaping process using the contour approximation straight line of the thin line' approximation line, respectively. be. A... Straight line approximation processing from the thinned image, B... Linear approximation processing of the contour line, C... Processing of correspondence between the thin line approximation straight line and the contour approximation straight line, D... Processing of the contour approximation straight line Shaping processing of the used thin line approximation straight line, IL l...First approximate line (thin line approximation line) 1R1)...Second approximate line (contour approximation line). Applicant's agent Patent attorney Takehiko Suzue Figure 5 Figure 6 Figure 1 Figure 2 Figure 7 Figure 8 RI=R4 Figure 9

Claims (1)

[Claims] means for obtaining a first approximation line segment of the input image from a thinned image obtained by thinning the input image; and means for approximating the contour of the connected black pixel area obtained from the input image by line segment to obtain a second approximate line segment of the contour. An image processing device comprising: means for obtaining an approximate line segment; and means for shaping a first approximate line segment obtained from the thinned image using a second approximate line segment of the contour.