JPS60201475A - Graphic data processing unit - Google Patents

Abstract

PURPOSE:To attain accurate polygonal line approximation without needing much labor and time by extracting a coordinate of a cross point where a distance with a straight line convecting two points on a line graphic is maximum and exceeds a prescribed reference value and extracting the coordinate values until the cross point is not detected where the distance with the obtained from the straight line exceeds a prescribed reference value. CONSTITUTION:A straight line generating circuit 2 extracts a coordinate a terminal point S (start point) of a line graphic stored in a picture memory 1 an a coordinate of other terminal point E (end point) at first, generates a straight line SE connecting the points S and E and the generated straight line SE is stored in a buffer 3. On the other hand, a boundary cross point extracting circuit 4 extracts coordinates of cross points 1, 2-6 being boundaries between the line drawing stored in the picture memory 1 and the square region and the extracted cross points are stored in buffer 5. Then coordinates of cross points having a maximum distance with a straight line connecting the point S and the cross point 3 and a stright line connecting the cross point 3 and the point E and satisfying the condition of specific Equation are outputted as to cross points 1, 2 and cross points 4-6 and stored in an output memory 7. After the processing above is conducted until the cross point satisfying the condition of specific Equation is not obtained, the line drawing SE is approximated by polygonal line with desired accuracy by tying the stored cross points in the output memory 7.

Description

DETAILED DESCRIPTION OF THE INVENTION (a) Technical Field of the Invention The present invention relates to a linear diagram expressed as binary data of a figure constituent pixel and a background constituent pixel for each pixel arranged in a matrix. The present invention relates to a graphic data processing device 5 used for dividing into line segments and performing broken line approximation.

(b) Background of the technology In the field of image processing technology using electronic computer systems, 1. Normally, the image to be processed is quantized and image information such as the density of each pixel arranged in a matrix is expressed as quantized data. Processing is in progress.

For example, if the image to be processed is a line figure such as a map, the pixels constituting one figure (black pixels) are set to "1" and the background pixels (white pixels)
It is represented by binary data with "0" as "0", and when storing this in a file memory, etc., the line figure is divided into several line segments and approximated by a broken line, and each divided line segment is By representing the data in vector data, the data is compressed and storage capacity is reduced.

(C) Prior Art and Problems In order to approximate the above-mentioned line figure with a broken line, conventionally, an input device called a tablet or digitights is used to trace the line figure with one look and extract the break points based on the operator's judgment. Alternatively, a device that scans a line figure expressed as binary data using a mask of, for example, 3×3 pixels and extracts a break point has been used.

However, the former method has the drawback of requiring labor and time, and in the latter method, line figures represented by binary data generally have a line width of several pixels, so line thinning processing must be performed before mask scanning. However, there is a drawback that errors are likely to occur as a result of the line thinning process.

(d) Object of the Invention An object of the present invention is to provide a graphic data processing device that can perform accurate polygonal line approximation without requiring labor and time.
It's about doing.

(e) Structure of the Invention The graphic data processing device according to the present invention has two pixels, a graphic constituent pixel and a background constituent pixel, for each pixel arranged in a matrix.
means for generating a straight line connecting two points on a line figure expressed as value data and separated by a plurality of sequentially adjacent rectangular areas having multiple pixel widths; and coordinates of the intersection of the line figure and the boundary of the rectangular area. means for extracting a value; and means for extracting a coordinate value of an intersection point having a maximum distance between the extracted plurality of intersection points and a straight line connecting two points on the line figure and exceeding a predetermined reference value; means for generating a straight line connecting the extracted coordinate values and two points on the line figure, and generating a straight line connecting the extracted coordinate values and two points on the line figure, and generating a straight line connecting the extracted coordinate values and the two points on the line figure, It is characterized by extracting values.

(f) Examples of the invention Next, the gist of the present invention will be specifically explained using examples.

FIG. 1 is a block diagram showing the configuration of an embodiment of the present invention, in which each pixel arranged in a matrix is represented as binary data of a figure constituent pixel and a background constituent pixel, and a plurality of sequentially adjacent pixels. An image memory 2 stores line figures separated by a plurality of rectangular areas of each width, and 2 connects any two points of both ends of the line figure stored in the image memory 1 and the break points obtained by the break point extraction circuit 6 described later. A straight line generation circuit generates a straight line; 3 is a buffer that stores the straight line obtained by the straight line generation circuit 2; 4 extracts the coordinate values of the intersection of the line figure stored in the image memory l and the boundary of the rectangular area; A boundary intersection extraction circuit; 5 is a buffer that stores the intersections extracted by the boundary intersection extraction circuit 4; 6 is a buffer whose distance between the intersections stored in the buffer 5 and the straight line stored in the buffer 3 is maximum and exceeds a predetermined value; A corner extraction circuit extracts the coordinate values of the intersection; 7 is an output memory that stores the coordinates of both ends of the line figure stored in the image memory 1 and the coordinates of the corner extracted by the corner extraction circuit 6; 8 is an image memory This is a read control circuit that controls reading between the output memory 1 and the output memory 7.

The image memory 1 stores 5 line figures that are expressed as binary data of figure constituent pixels (black pixels) and background constituent pixels (white pixels) for each pixel arranged in a matrix with a pinch of 0.1 mm. As illustrated in Figure 2, the matrix is divided into 32 pixels (3, 2 + n + n) in the row and column directions, and one of the square areas thus obtained is divided into complex shapes such as branch line figures or intersecting line figures. Store seven square areas ■, ■, ...■ that are sandwiched between two square areas (marked with *) that contain figures, are sequentially adjacent, and do not contain the complex figure (see Figure 3). ).

Regarding the identification of whether or not such a complex figure as described above is included in each of the square areas divided as shown in FIG.
629 (October 25, 1988), the outer circumference of each square area is scanned once, the number of contact points between the four sides of the square area and the line figure is detected, and based on that number, , a simple figure area, a branch line figure area, an intersecting line figure area, etc.

The straight line generation circuit 2 first calculates the coordinate values (Xs, Y
s) and the coordinate value (Xe,
ve) and generates a straight line SE connecting #A point S and end point E, and the generated straight line SE is stored in the buffer 3.

On the other hand, the boundary intersection extraction circuit 4 extracts the coordinate values ( XI, Yl)・
(X2. Y2) ... (X6. Ye) is extracted,
The extracted intersection points are stored in the buffer 5. In extracting the intersection points, if the line width of the line figure is a plurality of pixels wide, one of the contour lines or the center of the line width is used.

The corner point extraction circuit 6 extracts the line according to the slope of the straight line SE stored in the buffer 3.

1χ5-Xe1≧IYs-Yel When.

Y-(Vs-Ye)+(Xs-Xe)X(ni-Xs)
10 YsDn-l Y -Yn l'------- (
Al again.

When l Xs-Xe l < l Vs -'le l.

X- (Xs- to e) ÷ (Ys-Ye) X (Yn -
J's) +X5On-l X -Xn l -----
---- As fbl, each of the above six intersections (11・
(2)...(nl...) Find the distance from (6) to the straight line SE, and all distances are determined from the target accuracy of the polygonal line approximation with respect to the reference value 01: On<Dt ----------1cj In this case, the line figure SR is approximated by a straight line SE.

In addition, if there is an On that does not satisfy On≧[1t -----1---1dl, take its maximum value, for example, D3, and calculate the coordinates of the corresponding intersection (3) (X3. Y3) is extracted and stored in the output memory 7.

Then, the intersections (1) and (2), and the intersection (4)
-For (5) and (6), the distances between the straight line connecting the end point S and the intersection point (3) obtained as above, and the straight line connecting the intersection point (3) and the end point E, respectively, are The coordinate value of the intersection that is the largest and satisfies the condition of the formula (C1) is extracted and stored in the output memory 7. After performing this process until no intersection that satisfies the condition of the formula (tC) is obtained, the coordinate value is extracted and stored in the output memory 7. By connecting the intersection points stored in , the line figure SR can be approximated as a polygonal line with desired accuracy.

In the above embodiment, some line figures as shown in FIG. 3 among the line figures illustrated in FIG. 2 are processed after being stored in the image memory 1. As illustrated, the above processing can also be performed on figures that include complex figures.

According to the above embodiment, by selecting the value of Dt in equation (C) to be a value corresponding to the target accuracy of the broken line approximation, the line figure SE is approximated as a broken line with arbitrary precision, and the broken line obtained in this way is By representing each line segment formed by a vector, data compression can be applied to the line figure sE.

Furthermore, although the line figure is divided into square areas each having a width of 32 pixels, the accuracy of the polygonal line approximation can also be changed by changing this width.

It should be noted that data compression is performed by other means for complex figures such as branch line figures or intersecting line figures in square areas marked with * in Fig. 2.

(g) Detailed Description of the Invention As described above, according to the present invention, a line figure can be accurately approximated to a polygonal line with a desired accuracy without requiring the labor and time required in the prior art.

[Brief explanation of the drawing]

1 is a block diagram of an embodiment of the present invention, FIG. 2 is an example of line figures to be processed, and FIG. 3 is an example of line figures to be stored in the image memory 1.

Claims (1)

[Claims] Each pixel arranged in a matrix is expressed as binary data of a figure constituent pixel and a background constituent pixel, and a straight line connecting two points on a line figure divided by a plurality of sequentially adjacent rectangular areas of multiple pixel widths is expressed. means for extracting the coordinate values of an intersection between the line figure and the boundary of the rectangular area;
means for extracting a coordinate value of an intersection point whose distance to a straight line connecting the points is maximum and exceeds a predetermined reference value; and means for generating a straight line connecting the extracted coordinate value and the two points of the line figure. 2. A graphic data processing device, comprising: (2) extracting the coordinate values until an intersection point whose distance from the obtained straight line exceeds a predetermined reference value cannot be extracted.