JPS62108382A - Approximating system for polygonal line graphic - 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] [Summary] After thinning the binary image data of a line figure,
Extract the end points/branch points of the thinned image data, store their coordinates in a stack memory, select one connected point sequence (pixel sequence) from the stack memory, and select one point A.
Using point C as a starting point, trace the point sequence B, find the chord length d and arc length β, and when the difference Δ=l−d becomes larger than a certain threshold (D0), select the next point C and start the arc. Find a point P' between Ω and where the distance from the chord π exceeds the threshold H, consider the area up to this point P' as one broken line AP', and repeat the same process using this point P' as the starting point. , the thinned image is approximated by broken lines.

[Industrial application field]

The present invention relates to a graphic processing method, and in particular, uses a line thinning method and a one-point sequence linearization approximation method to achieve high speed and high quality patterns for binary image data of line shapes. Concerning line figure broken line approximation method.

With the recent advancement of computer systems, maps.

There are now many systems in which design drawings are read using, for example, a photoelectric reader and image processing is performed.

In this case, performing image processing on the data obtained by converting line figures into binary data increases the amount of data.

Generally, since the binarized image is image data with a random width, the binarized image is thinned to obtain a pixel string (dot string) of the center line of the binarized data. After compressing data, a method is often adopted in which the line image is approximated by a broken line.

When performing broken line approximation for this line figure, an effective broken line approximation method that can shorten the processing time and extract an accurate center line is required.

[Prior Art and Problems to be Solved by the Invention] A typical example of the conventional broken line approximation method is the "thinning-broken line approximation" method.

For example, Ramer, "Iterative Processing for Polygonal Approximation of Planar Curves," Computer Graphics and Image Processing, 1972, Volume 1, pp. 246-256 (Rame
r: rAn +interactive Proce
dure for the approximat
ion of Plane Curve J”Co
Mputer Graphics and Imag
eProcessing” VOL l+1972+
P244 to P256).

FIG. 4 is a diagram illustrating the conventional broken line approximation method shown in the above-mentioned literature.

First, when a part of the thinned image A-B is approximated by a broken line, in the conventional method described above, all the coordinates of the point sequence A-B are recorded, and the point P that is the maximum distance of the arc radius with respect to the chordal crystal is found. , the distance h
Calculate max.

This distance h max can be calculated by a method of determining the normal line from the point P (X, Y) to the -dimensional straight line when the chord i is represented by a linear straight line.

The distance h max found here is a certain fixed value (
If it is smaller than the threshold (H), the chordal crystal is adopted as an approximation of the arc Ω, and if it is larger than the threshold H, the arc Ω is replaced by the arc Ω and the arc Ω.
, and repeat the same process as above for each arc. In other words, if arc r- includes many inflection points, calculate the maximum distance h max for the sequence of points A to B. must be repeated many times.

Each time, it is necessary to record the coordinates of each point sequence again and repeat the same calculation, and experimentally, for each point sequence, the average
There are problems in that it is necessary to calculate the distance between the lines, which takes a lot of processing time, and that there is a lot of distortion in the pattern approximated by the broken line.

In view of the above-mentioned conventional drawbacks, the present invention provides a method for thinning images.
Less distortion without extra distance calculation (.

Moreover, it is an object of the present invention to provide a polygonal line approximation method that requires short processing time.

[Means for solving problems]

FIG. 1 is a diagram explaining the concept of the broken line approximation method according to the present invention.

■ In (A) of the figure, starting from point A, trace the point sequence in the direction of point B.

When tracking the point sequence, the length of the point sequence and the straight-line distance from one point A to that point are successively calculated and stored in a distance value memory.

In this way, when point C is reached, the length of the point sequence is l (= I
X 4 +, /'ix 3) Length d of 1st string M (=
5, i) Find.

Find the difference Δ=β−d between this black line length l and the straight line distance d (
In this example, Δ=4-2. i) When the Δ becomes larger than a certain value D0, move to the next process.

Let the point at this time be C.

■ Find the distance to the chordal crystal for the points between the arcs Ω, and define the point that first exceeds the threshold H as P'. The line up to this point P' is regarded as one broken line, and ■. is created.

Next, a search is made for a point between the arcs pc where the distance Nh to the chord 7c becomes greater than the threshold value 11 described above for the first time.

If there is no such point, move several points P゛ to the first point A.
Using the same starting point as , trace the point sequence from P゛ to C-8, find the aforementioned β and d, and find Δ-1! - Calculate d.

At this time, since the distance has already been calculated in the above process for the point sequence between P' and C, there is no need to calculate it again.

According to the above method, the distance calculation during the polygonal line approximation only needs to be performed twice for one point: the calculation of the straight-line distance l from the starting point and the calculation of the distance.

If the above steps are repeated, the result will be as shown in this figure (b), and the obtained point pHP21P31- will be the end point of the sought broken line.

[Effect]

That is, according to the present invention, after thinning the binary image data of a line figure,
Extract the end points/branch points of the thinned image data, store their coordinates in a stack memory, select one connected point sequence (pixel sequence) from the stack memory, and select one point A.
Using point C as a starting point, trace the point sequence B, find the chord length d and arc length β, and when the difference Δ = β − d becomes larger than a certain threshold (D0), select the next point C and start the arc. Find the point P'' between Ω and the distance from the chord π that exceeds the threshold H, and consider the line up to this point P° as one broken line AP'. From now on, using the chain point P° as the starting point,
By repeating the same process, the thinned image is approximated by a broken line, so distance calculations can be reduced, processing time can be shortened, and a broken line pattern with less distortion can be generated. be.

〔Example〕

Embodiments of the present invention will be described in detail below with reference to the drawings.

FIG. 2 is a block diagram illustrating an embodiment of the present invention. End point/branch point stack memory (Ms) 9° distance value memory (M!1Md) 10. Broken line approximation processing unit (PT,
PC) 7 is a functional block necessary to implement the present invention. FIG. 3 is a diagram showing the operation when h(at)≧H does not hold. Note that the same reference numerals indicate the same objects throughout the figures.

Step 1: The image data read by the photoelectric conversion device 1 is converted into binary data by the binarization device 2 and stored in the image memory 8, and the thin line is converted into a pixel column in units of 1 pixel by the thinning processing section (PT) 3. make a change.

Step 2: Extract end points and branch points from the line drawing data obtained by the thinning processing unit (Pa) 3, and set the coordinates of the end points and branch points.
Stored in branch point stack memory (Ms) 9.

The line thinning process and @point/branch point extraction process executed in step 1.2 above are, for example, the "line image broken line approximation process" disclosed in Japanese Patent Application No. 59-202830 filed earlier by the applicant of the present application. The process may be carried out according to the ``method'' or may be carried out by other methods.

Step 3: fl) The above end point/branch point stack memory (MS)
One connected point sequence (pixel sequence) is extracted from 9, that one point is selected as a starting point, and that point is designated as ao.

(2) Tracking processing unit (PTR) for points connected from point a0
I'll follow up with 5.

At this time, chord length d(a0)=0. Arc length 1 (a0)=O
shall be.

(3) From point a1 to point a1. ．． When moving toward: ・When moving diagonally to 45 degrees: l (a, ++) −jl' (ai
) +, n・Near when horizontal and vertical directions! (Mmm, +)
The distance calculation processing unit (PD) 71 performs a distance calculation of = 1 (ai) + 1.

Further, the chord length d(at) is calculated as the straight-line distance between the point a0 and the point 28. That is, the coordinates of point a0 and point a are (xa+y0)+(Xt, V
i), d(ai)=((xt-x0)2+(yt-y0)"
Find it as l ”2.

(4) Based on the above calculation results, Δ=1(a;) −d(ai) < or ≧0.
(Threshold value) is determined by the determination unit (Pc) 72.

(5) Δ−It (at) −d(a;) <[1
In the case of ゜: Next point a. Select 2 and return to the process of (3).

(6) Δ= 1! (a,) d(ai)≧00
In the case of: For the sequence of points between the arcs aΩ1, the distance (height) to the chord am h(a,), h(ax), h(a:+)
, ---1- are calculated by the distance calculation processing section (PT) 71.

If h(at)≧H holds for the first time at point a, the point a1 is regarded as the end point of the broken line, the chain point aj is recorded in the broken line data memory (ML) 11, and the next arc a'3H Repeat the same judgment for

Even from the end point aj of the above broken line to the point ai, h(a,)
If ≧H does not hold, the end point of the broken line (that is, aJ just before this point) is regarded as the starting point a0, and the process returns to step (2). Let a at this time be all.

However, for the ak -aiO point sequence, the arc length ii '
(at+)=.

1' (aJ)・j! (aJ)-11(aJ(j=
+1. −+i) Replace with Also, replace the string length with d(aJ)·l'(a;) (not subject to determination).

Therefore, the points a and subsequent points are actually subject to the determination in (4). (See Figure 3) In the above process, even if it reaches 80~a, h(a,)
If ≧H is not satisfied, consider a0 to aj as one broken line, and let a be the amount! ! Set it as the end point and return to (2).

(7) In the above process, the tracking of the point sequence is the end point.

Alternatively, when a branch point is reached, the next starting point is selected from the stack memory (MS) 9, and the process returns to step (2). Then, when the stack memory (MS) 9 becomes empty, the main fold line approximation process ends.

[Effects of the Invention] “As explained above in detail, the line figure broken line approximation method of the present invention thins the binary image data of the line figure, and then
Extract the end points/branch points of the thinned image data, store their coordinates in a stack memory, select one connected point sequence (pixel sequence) from the stack memory, and select one point A.
Using point C as a starting point, trace the point sequence B, find the chord length d and arc length l, and when the difference Δ=/-d becomes larger than a certain threshold (D0), select the next point C and start the arc. Find the point P' between Ω and the distance from the chord π that exceeds the threshold H, and consider the line up to this point P' as one broken line AP'.From now on, using several points P' as the starting point,
By repeating the same process, the thinned image is approximated by a broken line, so distance calculations can be reduced, processing time can be shortened, and a broken line pattern with less distortion can be generated. be.

[Brief explanation of drawings]

FIG. 1 is a diagram explaining the present invention in detail. FIG. 2 is a block diagram showing an embodiment of the present invention. FIG. 3 is a diagram for explaining the operation when h(a;)≧H does not hold. FIG. 4 is a diagram explaining the conventional broken line approximation method. It is. In the drawings, l is a photoelectric conversion device 1 and 2 is a binarization device. 3 is a thinning processing unit (PT). 4 is an end point/branch point processing unit (PT). 5 is a tracking processing unit (Pr, I). 7 is a broken line approximation processing unit (Po, Pc). 71 is a distance calculation processing unit (P0). 72 is a determination unit (PC), and 8 is an image memory. 9 is an end point/branch point stack memory (MS). lO is a distance value memory (MLMd). 11 is a broken line data memory (ML). 8. B, C, and P are point sequences (pixel sequences). P++Pz+P:++ '-・-・-・ are the end points of the broken line. are shown respectively. 12'')i Agent Patent attorney Igeta Sadao-゛) <A) C non-L, pregnant 5th month σtsu & 荊gu ``E, Saitun September 1st Rokugaku f
Figure t ○○○ (4) /) Zuisu elephant h (θε)≧H1 and 11 no 5ηJeI bottle i'fF)”
Φノ1も T1 and L to No. 2F Figure 3 Figure Otsusara jζ (The dog hole near the shoulder shape of the stubble is the moon Iro Figure 4

Claims (1)

[Claims] For binary image data of a line figure, a line thinning processing unit (P_T
) (3), a feature point extraction unit (P_S) (4) that extracts end points and branch points from the thinned image, and a point sequence (pixel sequence) connected from the end points or branch points. The point sequence processing unit (P_T_R) (5) sequentially calculates the arc length and chord length for the point sequence (pixel sequence) obtained above, and the difference (△) is set to a certain threshold ( D_0), a broken line approximation processing unit (P_D, P_C) (7) sets the end point of the broken line by comparing the distance (h) between each point and the chord with a threshold (H); A line figure broken line approximation method characterized in that a line drawing is approximated by broken lines.