JPH0362269A - Method and device for approximating line image - Google Patents

Abstract

PURPOSE:To correctly approximate a line image including the segments, circular arcs and circles by deciding each approximate section including the position error between he result of approximation and an actual center line point and applying the liner approximation to the direction of an inputted line image to divide the center line. CONSTITUTION:A liner direction section extracting device 8 applies the linear approximation to the change of the direction value in a direction series to divide an approximate point train into the linear direction sections having the linear average direction change rate and also calculates the average direction change rate of the linear direction sections and the linear error. A form numerizing device 9 calculates a circular arc or a circular radius and the center point coordinates for each linear direction section. A segment circular arc deciding device 10 performs the approximation after deciding whether or not the linear direction section is equal to a segment or a circular arc based on the position coordinates obtained by the segment approximation of an approximate point train of the linear direction section, the position coordinates obtained by the circular arc approximation of the approximate point train, the direction linear error of the linear direction section, and the rate of the linear direction section set to the approximate point train length respectively. Thus the corner points of a minute circular arc and a segment can be correctly approximated.

Description

Detailed Description of the Invention (Industrial Field of Application) The present invention relates to a drawing recognition method and apparatus for recognizing input images by scanning figures drawn on paper, and in particular to a drawing recognition method and apparatus for recognizing input images by scanning figures drawn on paper, and in particular, the present invention relates to a drawing recognition method and apparatus for recognizing input images by scanning figures drawn on paper. This invention relates to a method and apparatus for numerically approximating a structure.

(Prior Art) As a first step in the process of recognizing a drawing image, the line structure of straight lines and curves that constitute line figures in the drawing image is generally extracted. As a typical conventional method for approximating the line structure of an input line image to line segments and circular arcs, a method proposed by the same applicant is disclosed in Japanese Patent Application No. 87120/1983. This method calculates the direction value at each pixel from a line image obtained by scanning a figure, finds a linear direction section that has a linear average direction change rate on the line, and then calculates a linear direction section that has a linear average direction change rate on the line. This method approximates the linear direction section of 0 to an arc or circle, and the linear direction section of less than a threshold to a line segment.

(Problems to be Solved by the Invention) However, the above-mentioned conventional system has the following problems. This will be explained using FIGS. 3(a) and 3(b). FIG. 3 (a> is an input image containing two line figures,
FIG. 3(b) is a diagram schematically representing the direction of each pixel of this line image using a short line bone.

Since the direction at each pixel determined from the line image contains some errors, it is smooth as shown in section L1 in Fig. 3(b) at the corner point of two orthogonal line segments as shown in Fig. 3(a). The direction may change.

Since this section L1 has almost the same average rate of change as the section L2 in FIG. In the method of approximating an interval with a direction change rate as an arc,
Both the section L1 and the section L2 are approximated by circular arcs, or both are approximated by line segments.

In other words, in the conventional line segment arc approximation method, whether it is a line segment or a circular arc is determined only based on the average direction change rate of the linear direction section, so there is a problem that it is easily affected by errors included in the direction extraction results. was there.

SUMMARY OF THE INVENTION An object of the present invention is to provide a line image approximation method and apparatus that can solve the above problems and accurately approximate corner points of minute arcs and line segments without being affected by errors in the direction extraction results. It is in.

(Means for Solving the Problem) In order to solve the above-mentioned problem, the line image approximation method according to the present invention uses a center line image representing the center line point of a line image obtained by scanning a line figure, and a center line image representing the center line point of the line image obtained by scanning a line figure. In a line figure approximation method that approximates an input line image using line segments and arcs from a direction image representing the direction of the line at each pixel, the position coordinates of a point sequence from an arbitrary feature point to another feature point on the center line image are calculated. Using an approximate point sequence extraction process to extract an approximate point sequence and the direction value of the direction image in the approximate point sequence, the approximate point sequence is divided into a plurality of linear direction sections having a linear average direction change, and each linear Linear direction section extraction processing that calculates the average direction change rate and linearity error of the direction section, position error due to line segment approximation of the approximate point sequence of the linear direction section, position error due to arc approximation of the approximate point sequence, linear direction Line segment/arc determination processing that performs approximation by determining whether the linear direction section is a line segment or a circular arc based on the linearity error in the direction of the section and the ratio of the linear direction section length to the approximate point sequence length; This is a line image approximation method characterized by including the following.

The line image approximation device according to the present invention also calculates the center line point of the line and the local direction of the line at each position of the line image, which are obtained from a line image obtained by scanning a line figure recorded on a paper surface. In a line image approximation device including at least a centerline memory and a direction image memory for storing, the number of centerline points from an arbitrary feature point to another feature point read from the centerline memory? Approximate point sequence extraction means for outputting IfJu marks as an approximate point sequence; direction sequence reading means for reading out direction values at positions corresponding to the approximate point sequence from the image memory; and changes in direction values on the direction sequence. linear direction section extracting means for linearly approximating and dividing the approximate point sequence into a plurality of linear direction sections having linear average direction changes, and calculating the average direction change rate and linearity error of each linear direction section; For each direction interval, the position error due to line segment approximation of the approximate point sequence, the position error due to arc approximation of the approximate point sequence, the linearity error in the direction of the linear direction interval, and the ratio of the linear direction interval length to the approximate point sequence length. A line image approximation device is provided with a line segment/arc determining means for determining whether the linear direction section is a line segment or a circular arc based on the linear direction section.

(Example) Next, an example of the present invention will be described with reference to the drawings.

FIG. 1 shows a processing procedure of an embodiment of the present invention.

Upon starting the process, first, center line extraction processing is performed to obtain the center line of the line image (step 101), and a center line image consisting of connected pixels passing through the center of the line of the line image is obtained. The procedure is realized using a known method of line thinning.
The thinning procedure shown in Shunji Mori and Toshiko Sakakura (co-authored, 1986) can be used. Alternatively, a known procedure may be used in which the midpoints of the contour lines on both sides of the line are sequentially traced.

Next, a direction image generation process is performed to find the direction of the line at each pixel of the line image (step 102).

The first procedure for determining the direction at each pixel was proposed by the same applicant and disclosed in Japanese Patent Application No. 62-285043. A procedure can be used in which the reliability for T directions is determined in advance by local matching, and the results are combined to determine the direction of each pixel and its reliability.

In the following, for simplicity, the value of the line image at position (x, y) is expressed as F (x, y), 1≦X≦M, 1≦y≦N, where X and y are on the line image. 0M and N are the horizontal and vertical sizes of the line image, respectively, with the right direction being the X axis and the bottom direction being the Y axis.

When the parameter W is a number representing the field of view determined based on the expected line width, and the parameter T is the number of different directions in which a preset reliability is to be determined, first, the position (x, y
), whose vertical and horizontal widths are within the range of W, i.e.,
WxW local line elemental image f (t, 5) (1≦t, s≦W
), the reliability that a predetermined direction line element exists in the center within the local line element pixel 1f V r (x, y) (1=
1 to T).

Here, as a method for determining the reliability that the directional line element set in the local line element image f exists, a matching method used in pattern recognition technology, for example, by eigenvalue expansion of a pattern of directional line elements set in advance. This is realized using a known method such as a similarity method.

For example, create dictionaries for T = 4, that is, four directional line elements: vertical, horizontal, diagonal downward to the right, and diagonal upward to the right, and calculate the similarity with each dictionary for the local line element image f. Bye.

Next, the reliability for T directions is combined according to the following formula. As a result, the direction θ(x, y) of the line at the position (x, y) is determined.

Sz (x, y) =Σ V+ (x, y)*C03
(2*^rc++) (1) Sy (x, y) = Σ
V+ (X, V)”5IN(21Ar1J+)
(2) θ(X, /) = TAH-”(S, (
x, V)/S, (x, y))/2 (3) Here, Arg is the angle of the 0th direction line element. For example, if the above direction line element T=4 is selected (this 、A
r g I = O, A r g
2 = yr/2.

Arg3=i/4. Arga=3g/4.

As a second method for determining the direction at each pixel, a method for determining the principal axis of inertia of the local line image f (x, y) (1≦X+V≦W) may be used. In other words, the direction θ determined by the following formula may be used. A method in which the direction of the pixel (x, y) is used may also be used.

[Shin = 2; Σ t xr(x, y)]/Eyu
(5) Next, perform approximate point sequence extraction processing and obtain an approximate point sequence S consisting of a series of coordinates of center line points to be approximated by the following steps [1] to [4] (step 103). , let the feature points be branch points or end points,
A point P where there is one other center line point in the 8 vicinity of one point p of the center line point is an end point, and a point P where there are three or more other center line points in the 8 neighborhood of one point p of the center line point Let p be a branching point.

[1] Select an arbitrary feature point to which non-approximated center line points are connected, and set this as the starting point po of the approximate point sequence S.

[2] Among the center line points connected to po, one of the center line points that is not approximated is set as pI, and pI is added to the approximate point sequence S. 1=1.

[3] If pI is a feature point, end.

[4] Among the center line points connected to p+, let p r+1 be the point that is not included in the approximate point sequence S, and use this as the approximate point sequence S
Add to. Replace 1 with i+1 and go to [3].

As a result, one of the approximate point sequences S is 5=(po+pr,
It is determined as p-do...p,).

Next, linear direction section extraction processing is performed (step 104).
, the sequence of values of the direction image on the approximate point sequence S is D=(θ0
．． θ1. When θt...θ,), a linear direction section in which the change in direction is linear from the direction series, that is, a section where there is no change in direction or a section where change in direction is expressed by a linear equation, Find (1≦m≦K). Furthermore, the value S of l at the starting point of the linear direction section, the value e1 of i at the end point, and the two end point coordinates E, which are the position coordinates of the center line points corresponding to the starting point and the ending point, = (Xs++ yst) and Em *= (X
stl 'l 112→, and the average direction change rate MT, which is the average value of the in-hole change in the linear direction section RI, is determined.

The average rate of change in direction is the amount of change in direction per unit length,
The unit is radian/dat, where a dot is a unit of length. Here, the procedure for linearly approximating the change in direction is achieved by applying a method of linearly approximating a sequence of points distributed on a plane.
eaIlention of Plane Cur-v
es”, T. Pavlidis and S. L. Ho.
rowitz, IEEE Trans.

Vol, C-23, No. 8. pp, 86G-870 [
1974)) can be used.

That is, the plane (1, θ) with 1 and θ as two orthogonal axes
By approximating the arrangement of the point sequence of θ1 above with a plurality of line segments, the range of the linear direction section and the average rate of change in direction can be determined. Note that the linear direction section obtained by this is as follows.

The equation of the approximate straight line L1 (1≦m≦K) is θ, = M T −X i+β, (1
1), and the linearity error A 4 r r in the direction of the linear direction section is determined by the following equation.

Ixl is the absolute value of X. Next, line segment arc determination processing is performed (step 105), and K
It is determined whether each of the linear direction sections is a line segment or a circular arc, and a line segment approximation or circular arc approximation result is output.

First, the two end point coordinates E1 and E,2 of the linear section D1
, and find the center point O1 of a circle whose radius R1 is R, = 1/l MT-. Two candidate points 01 and 0112 are found as the center point of the circle that satisfies this, but the vector O@
Center point 0 where the sign of the change in the declination angle of the declination vector 01E1 of IB @1 matches the sign of the average direction change rate MT.
The correct center point by choosing 1 is 0. is found. That is, the deflection angle of Ar9(v) measured in the positive direction of the X-axis of the vector V, Sign (x)
When is the sign of the value X, Sign ((Arc+(0, tE, z)−Atc
+(0, t E sil ))=Sign(HT m)
(13) The center point Os+
The center point to be found is 0. becomes.

Let the coordinates of this center point O1 be (0□, 0□).

Next, from the position coordinates of the approximate point sequence corresponding to the linear direction interval, calculate the line segment approximation error of the approximate point sequence according to the following formula,
1, and the circular arc approximation error C* r r. however,
Let the coordinates of the approximate point sequence p be (p + -, p ty).

+(p,,-po,) (p,,-p,,) l
) 0-'(14) However, ^=((P,,-PG,) 2 +(P,,-
PG,) ”) 0・S-Q,,) 2-1.2
))0・5(15) This line segment approximation error 11 and arc approximation error C61,
The first line segment arc determination is performed using the following conditions, where B is a predetermined constant.

(1) If 1. If B * Cerr < L err is satisfied, the linear direction section is determined to be a circle i or a circle, and circular arc approximation is performed. That is, the directions θ and I connecting the center point O1 and the two end points E1 and Eat, respectively. and θ
, 2 as the starting and ending angles of the arc, and the center point 0
1. Output radius R, starting angle θ1, ending angle θ, 2 as arc approximation results.

(2) If + B ” L err < Cerr is satisfied, the linear direction interval is determined to be a line segment,
Line segment approximation is performed, that is, two end point coordinates E at and Eat are output as the line segment approximation result.

As a result, when condition (1) or (2) is satisfied, line segment arc determination is performed and an approximate result is obtained.

If neither condition (1) or (2) is met,
The second line segment arc determination is performed under the following conditions.

(3) R-1-/P-<R-<Ft---*P
- and if DT, , /P, < DT, then the linear direction section is determined to be an arc or a circle, and circular arc approximation is performed, that is, the center point O1 and the two end points E1 and Ess
The directions θ, I, and 0.1 connecting these are determined as the starting angle and ending angle of the arc, and the center point 01, radius R, starting angle θ, I, and ending angle θn are output as the arc approximation result.

Here, Rm l m, Rwax, and DTmts are predetermined constants, the direction change amount DT, and the reliability P.

is a value determined by the following formula.

Mouth T, =HT, In, (
16) P, = (φ, (A,,, )−φ2 (ns
+ n)) '°5 (17) Here, φ1 (x) is a monotonically decreasing function with respect to X, and for example, we can choose φl (x)=1/ (x+1)'' (18). , φx (x, y) are functions that are monotonically increasing with respect to X and monotonically decreasing with respect to y. For example, φt(x, y)=(x/y)'' (19) can be chosen.

(4) Otherwise, determine that the linear direction interval is a line segment, and perform line segment approximation, that is, the two end point coordinates E1
and Eat are output as line segment approximation results.

As described above, line segment arc approximation is performed for one approximate point sequence S. If there are center line points in the center line image that have not been approximated yet, repeat the steps from the approximate point sequence extraction process and perform the same process on other approximate point sequences; if there are no approximate point sequences, end all processing. do. As a result, the entire line image is approximated by a line segment arc.

In FIG. 1 and the above explanation, the direction image generation process is performed after the center line extraction process, but as is clear from the above explanation, these two processes can be performed independently.
The steps may be performed in the reverse order or at the same time.

FIG. 2 is a functional block diagram of the line image approximation device according to the present invention.

The image input device 1 scans a figure, inputs and stores line images. The center line extraction device 2 finds the center point of a line from the line image in the image input device 1. The center line memory 3 stores the center line point and approximated points. The direction image generation device 4 is
A direction image is generated by determining the local direction at each pixel from the line image in the image input device 1. The direction image memory 5 stores the direction image. Approximate point sequence extraction device 6 reads center line points from center line memory 3 and obtains a sequence of center line points to be approximated. The direction series reading device 7 reads out from the direction image memory 5 a direction series consisting of a series of direction values at positions corresponding to the approximate point series.

The linear direction section extraction device 8 linearly approximates changes in direction values on the direction series, divides the approximate point sequence into linear direction sections having a linear average direction change rate, and calculates the average direction change rate of each linear direction section. and calculate the linearity error. Shape digitization 9 calculates the radius and center point coordinates of an arc or circle for each linear direction section. The line segment arc determination device 10 determines the position coordinates of a series of approximate points in a linear direction section by line segment approximation, the position coordinates of the series of approximate points by arc approximation, the linearity error in the direction of the linear direction section, and the position coordinates of the approximate point sequence. The control device 11 starts the image input device or the line segment/arc determination device 10, which determines whether the linear direction section is a line segment or a circular arc based on the ratio of the length of the linear direction section and performs approximation. Control the execution of a series of processes. The operation will be explained in more detail below.

The control device 11 first starts the image input device 1, inputs an image, and stores it as a numerically converted line image.

In order to simplify the line image below, the value of the line image at the position coordinates (x, y) is expressed as F(x, y), 1≦X≦M, 1≦y≦N, where X
and y are the position coordinates on the line image, and the right direction is
The horizontal and vertical dimensions of the line image are 0, with the downward direction being the Y axis. It can be easily configured using a converter that converts the value into a value, and a rewritable storage device such as a RAM or a disk-type file device that stores the value.

When the line image is stored in the image input device 1, the control device 1
1 activates the centerline extraction device 2 and finds connected centerline points passing through the center of the line of the input line image.

The center line extraction device 2 is realized using a known thinning method.
(Co-authored by Shunji Mori and Yuko Sakakura, 1986) was realized using a computer program such as a microcomputer, and this was applied to the input image stored in the image input device 1. This can be easily achieved by executing the following.

The centerline extraction device 2 stores the obtained centerline points in the centerline memory 3. The centerline memory 3 is a device that stores data in a format that can distinguish between pixels that are centerline points and pixels that are not centerline points, and also distinguish between approximated points and non-approximated points, which will be described later. For example, the centerline memory 3 stores a centerline image in which pixels that are centerline points are represented by 1 and pixels that are not centerline points are represented by 0, and approximated points are represented by 0. 1. It is realized by storing two binary images of approximated images in which unapproximated points are represented by O. Also, for example, a combination can be multi-valued such that a point that is a centerline point but has not been approximated is represented by 0, a point that is not a centerline point but not approximated is represented by 1, and a point that is a centerline point and has been approximated is represented by 3. Note that if the centerline extraction device 2 is configured by a computer program and a storage device, the centerline memory 3 may be provided in the memory of the same computer. can.

Next, the control device 11 activates the direction image generation device 4.

The direction image generation device 4 generates each point (x, y) of the line image F(x, y).
, y), the local line drawing taf(t.

s), for example, when the local range is a rectangle with horizontal and vertical widths of W, f(t, 5)=F(x+t-1-W/2.y+5-1-
W/2), 1≦t, and s≦n are read out from the line image input device 1, and the direction θ(x, y) of the local line image f (t, s) is determined. This is performed for all points of the line image F to generate a direction image θ(x, y) (1≦X≦M, 1≦y≦N). In order to realize the direction image generation device 4, the methods shown in equations (1) to (3) or the methods shown in equations (4) to (10) of the first invention can be implemented using a microcomputer, for example. realized by a program on an electronic computer,
This can be easily realized by processing a line image stored in the image input device 1. Direction image memory Wt4
stores the obtained direction image θ(x, y) in the direction image memory 5.

The direction image memory 5 may be easily constituted by a rewritable storage device such as a RAM or a disk-type file device, or when the direction image generation device 4 is constituted by a computer program and a storage device, the direction image memory 5 The image memory 5 may be provided within the storage device of the same computer.

Next, the control device 11 starts the approximation section extraction device 6, and the approximation section extraction device 6 performs the following operations to obtain a sequence of approximate points S from the sequence of coordinates of the center line points to be approximated. The centerline memory 3 stores a centerline image g (x, y) in which pixels that are centerline points are represented by 1 and pixels that are not centerline points are represented by O.
This is realized by storing two binary images of the approximated image h (x, y) in which approximated points are represented by 1 and unapproximated points are represented by O. Approximated picture @h
A case will be explained in which (x, y) are all initialized to O.

[11a=1. Set b=1 and perform the operation [3].

[2] If a<M, replace a with a+1.

If a=M, replace a with 1 and replace b with b+1. Here, when a=M and b=N, a termination signal is sent to the control device 11. If not, perform operation [3].

[3] Read g(a, b') from center line memory 3, and
If (a, b)=1, operation [4] is performed; otherwise, operation [2] is performed.

[4] Center line memory 3 to g (a-1, b-1).

g(a, b-1), g(a+1.b-1).

g (a-1+b)+g(a+1.b).

g (a 1. b + 1) + g (a, b tent).

g Read eight values of (a+1.b+1), and if one or three of these values are 1, then perform operation [5], otherwise perform operation [2].

[5] (c, d) (a-1, bl) (a, b
1 ) + (a + 1 * b 1 ) *
(a-1, b), (a+1.b) (a-1, b+1), (a, b+1).

(a+1.b+1), read h (c, d) from the center line memory 3 and h (c, d)=0
Find (c, d) such that Something like this (c, d
) does not exist, perform the operation [2]; if it exists, output (a, b) to the direction sequence reading device 7 and linear direction section extraction device 8, and convert (a, b) to (px, p
y) and perform the operation [6].

[6] g (c-1, d 1) from the zero-order centerline memory 3 which outputs (c, d) to the direction sequence reading device 7 and the linear direction section extracting device 8.

g (c, d-1), g (c+1.d-1).

g (c-1,d), g (c+1.d)g (C-1
, d+1), g (C, d+1).

g Read the 8 values of (c+1.d+1), and if one or three of these values are 1, the process ends. Otherwise, rewrite h (c, d) to 1 and perform the operation in [7] .

[7] (e, f) (c 1.d 1) +
(c.

d 1 ), (c +1 + d 1 ), (
c1.

d), (c+1.d), (ci, d+1) (C, d+
1), (c+1.d+1), then extract g(e, f) from the center line memory 3 and get g(e, f)=
1 and (e, f)≠(px, py).
f) Find. Replace (c, d) with new (px, py), replace (e, f) with new (c, d) [6
].

As described above, a sequence of approximate points between one feature point is extracted and output to the direction sequence reading device 7 and the linear direction section extraction device 8.

When the approximate interval extracting device 6 outputs the approximate point sequence, the direction sequence reading device 7 sequentially reads out the values of the direction image at the position corresponding to each approximate point sequence from the direction image memory 5, and extracts the linear direction interval as a direction series. Output to device 8. That is, the approximate interval S output by the approximate interval extraction device 6 is as follows: 5=((x+, y+), (X2, Y2), --
-----(xm, y, )), the direction sequence reading device 7 reads the direction sequence as follows:
θ(x, +ym))=(θ1, 1≦i≦n) is read out from the direction image memory 5 and output to the linear direction section extraction device 8.

Next, the control device 11 starts the linear direction section extraction device 8,
From the direction series in the approximate interval S, we can find a linear interval in which the change in direction value is linear, that is, an interval in which there is no change in direction or an interval in which the change in direction is expressed by a linear equation, (1≦m≦K〉
seek. Furthermore, the value sa of the starting point l of the linear direction section D yo and the value e of 1 of the end point, , two end point coordinates E a+= (x m
l , y + mt ) and E a2=(X m2+ 3
'112) , the average direction change rate MT, which is the average value of the inward direction change in the linear direction section, the linearity error A determined by equation (12), 2. seek. The average rate of change in direction is the amount of change in direction per unit length, and the unit is radian/dot.
(radian/dot) Also, a dot is a unit of unit length.

In order to linearly approximate the direction change in the linear direction section extraction device 8, the procedure explained in the linear direction section extraction process in the embodiment shown in FIG. This can be easily realized by executing this on the position coordinate string and direction string of the center line points of the approximation section that have been read into the memory within the computer or an external storage device.

The linear direction section extraction device 8 outputs the obtained average direction change rate MT, , and two end point coordinates E sll Em2 for each of the K linear direction sections to the shape digitization device 9, and further outputs the linear direction The coordinates S of the partial approximate point sequence corresponding to the interval , and the average direction change rate MT, linearity error A, 11
．． The two end points M II E 1°Eat and the number n of the approximate point sequence input to the linear direction section extraction device 8 are output to the line segment arc determination device 10 .

The shape digitization device 9 calculates the two end point coordinates E1 and El inputted from the linear direction section extraction device 8 and the average direction change MT.
Find the radius and center point of a circle or arc from .

First, the radius R, R1 is R, = 1/IMT.

Then, the two end point coordinates E1 and Effi
2 and find the center point O1 of the circle with radius R1.

Two candidate points O, I and 0.2 are found as the center point of the circle that satisfies this, but the vector Oer l E w
The correct center point O1 is found by selecting the center point Oml where the sign of the change in the declination angle of r1 and the declination angle of the vector Os+E+a* matches the sign of the average direction change rate MT. In other words, the deviation angle, Sign(x
) is the sign of the value X, the center point 01 that satisfies equation (13) becomes the center point O1 to be found.

The shape digitizing device 9 outputs the calculated radius R1 and the coordinates (0,, O,,) of the center point 0 to the line segment arc determining device 10. Note that the shape digitization device 9 is realized by a program of an electronic computer such as a microcomputer, and can be easily realized by executing the above processing on the values input from the linear direction section extraction device 8.

The line segment arc determination device 10 calculates the coordinates S of the partial approximate point sequence input from the linear direction section extraction device 8 and the average direction change rate M.
T, , linearity error A err % two end point coordinates E
@11 Es2 It is determined whether each linear direction section is a line segment or a circular arc from the number n of the approximate point sequence, the radius R1 and the center point coordinates O1 input from the shape digitization device.

First, the position coordinates and radius R of the partial approximate point sequence S.

According to equations (14) and (15), the line segment approximation error L 11 r r and the arc approximation error Ce of the approximate point sequence are
Find r r.

Next, using the line segment approximation error L@rF and the arc approximation error Cerr, a first line segment/arc determination is performed according to conditions (1) and <2) described in the embodiment shown in FIG.

If it is determined that it is a circular arc, the center point O
Find the directions θ1 and θ, 2 connecting a and the two end points E ml + E s+2, respectively, as the starting angle and ending angle of the arc, and output the center point 01, radius R1, starting angle θ1, and ending angle θ0 as the arc approximation result. do.

On the other hand, if it is determined that it is a line segment, two end point coordinates E wa l and Bat are output as the line segment approximation result.

If the first line segment/arc determination fails, use the linearity error A111, the average direction change rate MT, the number n of the approximate point sequence, and the number n of the partial approximate point sequence,
The second line segment is determined as an arc according to conditions (3) and (4) explained in the example of FIG.
Directions θ, I and θ connecting l and Effi2, respectively
, 2 as the starting and ending angles of the arc, and the center point 0
1. Output the radius R1, start angle θ, I, and end θn as the circular arc approximation result. On the other hand, if it is determined that it is a line segment, the two end point coordinates E1 and E are output as the line segment approximation result.

When the line segment arc determining device 10 outputs the approximation results for the linear direction sections extracted by the linear direction section extracting device 8, the control device 11 starts up the approximate section extracting device 6 again and performs another approximation. Extract the interval. At this time, when an end signal is sent from the approximate interval extraction device 6 to the control device 11, 1
1 ends all processing. As a result, image input device 1
The entire line image stored in is approximated to a line segment arc.

(Effects of the invention) The conventional method of determining whether it is a line segment or an arc using only the average rate of change in direction on a line image had the problem of being susceptible to errors in the determined direction. In the present invention, each approximation section is determined not only based on the average direction change rate, but also the positional error between the approximation result and the actual center line point, so it is possible to determine Correct determination can be made even at points where the direction of the image changes rapidly.

In addition, since the center line is divided by linearly approximating the direction of the input line image, the effect of accurately separating the line segment portion and the circular arc portion is not impaired. It is possible to accurately approximate line images including lines, arcs, and circles at feature points such as branch points and corner points, or at arc portions with large curvature.

[Brief explanation of drawings]

FIG. 1 is a diagram showing the procedure of a line image approximation method according to an embodiment of the present invention, FIG. 2 is a block diagram showing the functions of a line image approximation device according to another embodiment of the present invention, and FIG. It is a figure showing operation by a method. 1... Image input device, 2... Center line extraction device, 3.
...Center line memory, 4...Direction image generation device, 5...
・Direction image memo・6...Approximate point sequence extraction device, 7・
...Direction series reading device, 8.. Linear direction section extraction device, 9.. Shape digitization device, 10.. Line segment arc determination device, 11.. Control device.

Claims (2)

[Claims] (1) Approximate the input line image with line segments and circular arcs from the center line image representing the center line point of the line image obtained by scanning the line figure, and the direction image representing the direction of the line at each pixel of the line image. In the line figure approximation method, an approximate point sequence extraction process that extracts the positional coordinates of a point sequence from an arbitrary feature point to another feature point on a centerline image as an approximate point sequence; and a direction image in the approximate point sequence. A linear direction section extraction process that divides the approximate point sequence into a plurality of linear direction sections having a linear average direction change using the direction value, and calculates the average direction change rate and linearity error of each linear direction section. , a position error due to line segment approximation of the approximate point sequence of the linear direction section, a position error due to circular arc approximation of the approximate point sequence, a linearity error in the direction of the linear direction section, and a ratio of the linear direction section length to the approximate point sequence length. A line image approximation method comprising: a line segment/arc determination process of determining whether the linear direction section is a line segment or a circular arc based on the above and performing an approximation. (2) A center line memory and a direction image that store the center line point of the line obtained from the line image obtained by scanning the line figure recorded on the paper surface and the local direction of the line at each position of the line image. A line image approximation device comprising at least a memory, comprising approximate point sequence extracting means for outputting positional coordinates of center line points from an arbitrary feature point read from the center line memory to another feature point as an approximate point sequence; direction series reading means for reading direction values at positions corresponding to the approximate point series from the image memory; and a plurality of linear direction sections having linear average direction changes by linearly approximating changes in direction values on the direction series. linear direction section extracting means that divides the approximate point sequence and calculates the average direction change rate and linearity error of each linear direction section; and a position error due to line segment approximation of the approximate point sequence for each linear direction section, Determine whether the linear direction section is a line segment or a circular arc based on the position error due to circular arc approximation of the point sequence, the linearity error in the direction of the linear direction section, and the ratio of the linear direction section length to the approximate point sequence length. A line image approximation device comprising: line segment/arc determining means.