JPH0136149B2 - - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION (1) Description of the field to which the invention pertains The present invention relates to a semicircle extraction processing method for extracting and encoding a semicircle on a drawing using an information processing device.

(2) Description of conventional technology There is a conventional method of inputting a drawing into an information processing device as black and white binary drawing data using an input device such as a facsimile transmitter, and automatically extracting a semicircle on the drawing. There is a method in which a semicircle to be extracted is expressed as a pit pattern sequence, this is used as a master pattern, and a comparison process is performed with original drawing data, and a pixel array that matches the master pattern is extracted as a semicircle. This method requires a process of matching the master pattern with all the pixel arrays in the drawing, which poses a problem in that the processing time becomes extremely long. Furthermore, for semicircles with different sizes and inclinations, it is necessary to replace the master pattern each time and repeat the matching process with the original drawing data. When trying to automatically extract a semicircle from a drawing, there is a problem in that an extremely large amount of processing time is required.

(3) Purpose of the Invention In order to solve these problems, the present invention calculates three intersection points on a chord constituting a semicircle based on intersection information between three parallel and equally spaced search lines and a figure line. This method realizes a semicircle extraction processing method that makes it possible to extract semicircles with arbitrary sizes and inclinations by finding three intersections on the circular arc and the three intersection points on the arc. It is. Hereinafter, it will be explained in detail using the drawings.

(4) Explanation of the structure and operation of the invention Figure 1 is an explanatory diagram of the principle of this method, in which 1 is a semicircle, 2 is a probe group consisting of three probe lines 2-1 to 2-3, 3 to 8 is the intersection of the search line and the figure line.

In this method, first, three parallel and equally spaced search lines 2-1, 2-2, and 2-3 are set, and intersection points 3 to 8 between the three search lines and the figure line are detected. The intersection detection process is performed by scanning the search line and setting the center pixel of the detected black run or a pixel close to the center as the intersection. Next, the intersection points 3, 4, 6, which are within a predetermined range based on the intersection point 5 on the exploration line 2-2,
7 and 8 are found, a group of intersection points of a semicircle configuration candidate consisting of the six intersection points is detected, and it is determined whether the six points in the group of intersections exist on the same semicircle. Specifically, first, the group of intersections is divided into left intersection groups 3, 5, and 7 consisting of intersections on the left side on each search line, and right intersection groups 4, 6, and 8 consisting of intersections on the right side, and the two For the intersection set, if the three intersection points in one intersection set exist on the same straight line, and the center point of the circle passing through the three intersection points in the other intersection set exists on the straight line, It is determined that the six intersection points are on the same semicircle. Next, a semicircle is extracted by determining the position, size, and inclination of the semicircle from the circle and the straight line.

Furthermore, based on the semicircle information extracted through such processing, such as position, size, and inclination,
If the semicircle is generated as a bit pattern sequence and this is used as a mask pattern for comparison with the original drawing data, it is possible to further improve the extraction accuracy.

FIG. 2 is an explanatory diagram showing the direction of the search line and the inclination range from which semicircles are extracted. 9 is a semicircle, 1
0,11 are exploration lines 10-1 to 10-3,1 respectively
The search line group consisting of 1-1 to 11-3, 12 to 23 are the intersections of the search lines and the figure lines.

In this method, as explained above, there must be three intersections between the search line and the semicircle on the chord and three on the arc. Therefore, a semicircle whose inclination, that is, the direction of the chord of the semicircle, is in the range of 45 degrees to 135 degrees with respect to the direction of the search line is targeted for extraction processing. The semicircle 9 intersects with the semicircle 12 to 17 in the search line group 10 in Figure 2a, and three intersections cannot be detected on the chord of the semicircle, making extraction impossible. be. On the other hand, if the search line group 11 is set in a direction perpendicular to the search line group 10 as shown in figure b, the intersections between the semicircle and the search line group 11 will be 18 to 23, and will be on the chord of the semicircle. Since three intersection points can be detected on the arc of the semicircle, extraction by the above process is possible.

Therefore, in order to extract all semicircles with arbitrary inclinations on a drawing, for example, first use a group of horizontal exploration lines and move them from the top to the bottom of the drawing.
Next, processing is performed using vertical search line groups while sequentially moving the search line groups in two orthogonal directions, such as from left to right in the drawing.

In addition, the radius of the arc of the smallest semicircle to be extracted is
If Rmin, the interval between the probe lines needs to be set smaller than Rmin/√2.

FIG. 3 is an explanatory diagram of the process of detecting a group of intersection points of semicircular configuration candidates.

24 is a semicircle, 25 is exploration line 25-1 to 25-
3, 26 to 31 are intersection points of the search lines and figure lines, 32 to 35 indicate ranges on the search lines, and 36 is the end point of the arc of the semicircle 24. In FIG. 3, the x and y coordinates are set as shown in the upper left corner. Also, the radius range of the arc of the semicircle to be extracted is
Rmin to Rmax (Rmin<Rmax), and the interval between the exploration lines is D.

First, focus on the intersection 28 on the exploration line 25-2, and move along the exploration line 25-2 in the x direction Rmin~ with this intersection as a reference.
An intersection point 29 within the range of Rmax is selected. Letting the x coordinates of the intersections 28 and 29 be X ₁ and X ₂ respectively, on the exploration line 25-1, {(X ₁ - D) ~ (X ₁ + D}, that is, the range 32 and {(X ₂ - D) ~ (X ₂ +D)}
In other words, in the range 33, and on the search line 25-3, {(X ₁ -D) to (X ₁ +D)}, that is, the range 34, and {(X ₂ -D) to (X ₂ +D)}, that is, the range 35, respectively. Existing intersection points 26, 27, 30, and 31 are selected. Through such processing, the intersection points 26, 27, 2
8, 29, 30, 31 are detected. In addition, the relevant range 3
If there are multiple intersections between points 2 to 35, all combinations are detected as a group of intersections.

Next, the six intersections in the intersection group are set as the left intersection set 26,
28, 30, right intersection set 27, 29, 31.

FIG. 4 is a classification table in which the relative positional relationships of three intersections in an intersection set are classified into types A to type A.
Classification is based on the x-coordinate value of the central point (indicated by a black dot in Fig. 4), and the x-coordinate values of the upper and lower points (indicated by white dots in Fig. 4). It depends on the combination of being larger, smaller, or the same.

Left intersection set 26, 2 detected by the above process
8, 30 and the right intersection set 27, 29, 31 are determined to which type of the classification table they correspond. Next, is there a possibility that the two intersection points constitute a left semicircle (a semicircle where the arc is on the left side with respect to the chord) or a right semicircle (a semicircle where the arc is on the right side with respect to the chord)? It is determined whether or not each intersection set corresponds to the type. Specifically, types A to C in Figure 4 use strings,
It is assumed that there is a possibility of forming a type D or arc, and the determination is made as follows.

(b) When there is a possibility of forming a left semicircle Left intersection group...any of G, H, or I, right intersection group...any of A, B, or C (b) Possibility of forming a right semicircle If there is a left intersection group...any one of A, B, or C, right intersection group...any one of D, E, or F (c) If there is no possibility of forming either a left or right semicircle, the above (b) , (b) In the example shown in Fig. 3, the left intersection groups 26, 28, and 30 are type B, and the right intersection groups 27, 29, and 31 are type D.
Since it corresponds to , it is determined that there is a possibility of forming a right semicircle.

Depending on the position of the exploration line, it may not be judged as (a) or (b) above even if it is actually a semicircle, but if you move the position of the exploration line one after another, it will definitely be (a), (B)
It is possible to detect a group of intersection points corresponding to . This will be explained using FIG.

FIG. 5 is an explanatory diagram showing the relationship between the search line position and the group of intersections detected by the search line. 37 is a semicircle, 38 and 39 are exploration lines 38-1 to 38, respectively.
- Exploration line group consisting of 3, 39-1 to 39-3,
40 to 51 are the intersection points of the search line and the figure line.

The intersection groups detected by the search line group 38 are the left intersection group 40, 42, 44 and the right intersection group 41, 43, 4.
5, it is determined that they correspond to type B and type C, respectively, and there is no possibility of forming a semicircle. However, the positions of the exploration line groups are sequentially moved, and for example, the intersection group detected by the exploration line group 39 is on the left. Intersection set 44, 48, 5
0 and right intersection sets 47, 49, and 51, which correspond to type B and type D, respectively, and are determined to have a possibility of forming a right semicircle.

Regarding the two intersection sets that have been determined to have the possibility of forming a semicircle, (1) the three (2) The set of intersections constituting the arc must be between the center point of the circle determined by the three intersections in the set of intersections and the straight line obtained in (1). the distance is within a predetermined range,
The following two conditions are determined. In the case of Figure 3, left intersection group 2
Condition (1) for 6, 28, 30, right intersection set 2
Condition (2) is determined for 7, 29, and 31, and if the two conditions are satisfied, the center position, radius, and chord slope of the arc are determined as information for determining the semicircle 24, and the semicircle is Extract. Note that instead of the information on the radius of the arc and the inclination of the chord, the position of the end point of the arc, for example 36, and the information that the arc extends clockwise from the end point may be used.

Note that the method for determining condition (2) is to first find the center point of a circle passing through the three intersection points 27, 29, and 31, and then find the distance between the center point and the straight line defined by condition (1) within a predetermined range. Although it may be determined whether the two intersection points 27 and 31 are at both ends, first find the intersection of the perpendicular bisector of the line segment whose ends are the two intersection points 27 and 31 and the straight line defined by condition (1), and then find the intersection point. Set as the center point of the arc,
The distance between the center point and the intersection 27 or 29,
It may be determined whether the difference in distance between the center point and the intersection point 28 is within a predetermined range.

FIG. 6 shows an example of the configuration of a device that implements this method. 52 is a drawing input device such as a facsimile transmitter, 53 is a frame memory for storing drawing data, 54 is a control unit, 55 is an intersection detection unit, and 56 is an intersection register for storing intersection information, which is based on the number of pixels on the search line. Consisting of three line registers having corresponding addresses, the contents of each line register correspond to the intersection information of the three search lines, 57 is an intersection group detection section, 58 is an intersection group judgment section,
59 is a semicircle determining section, and 60 is an output section.

To operate this, a drawing is first inputted using the drawing input device 52 and stored in the frame memory 53. The control unit 54 sends an instruction of the search line position to the intersection detection unit 55. Upon receiving this, the intersection detection unit 55 first clears the intersection register 56, and then
Pixel data on the search line is read from the frame memory 53, a black line on the search line is detected, and the center pixel of the black run or a pixel close to the center is detected as an intersection. For example, if the direction of the search line is taken as the x-axis, the intersection information is stored by setting "1" to the address of the line register corresponding to the x-coordinate of the intersection. This operation is performed on the pixel data on the three search lines, and the intersection information is obtained for each search line.
Each is stored in three line registers within the intersection register 56. The intersection point group detection unit 57 sends an instruction to the control unit 5 that the intersection information has been stored in the intersection register 56.
4, and from the intersection information in the intersection register 56, that is, the address value "1" in the line register, an intersection consisting of six intersections that becomes a semicircle configuration candidate is determined based on the procedure explained in FIG. 3 above. The group is detected, and the address values of the six intersections are sent to the intersection set determining section 58. In response to this, the intersection set determining unit 58 divides the intersection group into a left intersection group and a right intersection group by comparing the address values of the intersection points for each search line, that is, for each line register. Next, by comparing the address values of each of the three intersections in the two-intersection set, the type of the intersection set is detected based on the classification table shown in FIG. Determine whether or not there is a possibility of forming a semicircle. If it is determined that there is no possibility, an instruction is issued to the intersection point group detection unit 57 to detect a new intersection point group. If it is determined that there is a possibility, the intersection set information is sent to the semicircle determining section 59. The semicircle determination unit 59 determines the x of the intersection obtained from the intersection set information.
Based on the y-coordinate value of the intersection obtained from the coordinate value and the position information of the exploration line sent from the control unit 54,
It is determined whether the six intersection points in the intersection set are on the same semicircle. If it is determined no, an instruction is issued to the intersection point group detection unit 57 to detect a new intersection point group. If it is determined to be a semicircle, the semicircle information includes the coordinates of the center point of the arc of the semicircle, the coordinates of the starting point of the arc, and the direction in which the arc extends, ie, clockwise or counterclockwise. It is calculated and sent to the output section 60. Upon receiving this, the output unit 60 performs output processing such as storing it in an external storage device, and at the same time issues an instruction to the intersection point group detection unit 57 to detect a new intersection group. When the intersection point group detection unit 57 receives an instruction to detect a new intersection point group, it performs an intersection point group detection process on the intersection information in the intersection point register 55, and if an intersection point group can be detected, repeats the above process. , extract a semicircle. On the other hand, if a new group of intersections cannot be detected, an instruction indicating that there is no group of intersections is sent to the control unit 54. In response to this, the control unit 54 moves the search line and sends an instruction of the new search line position to the intersection detection unit 55. Hereinafter, the above processing is performed on pixel data on a new exploration line.

For example, this operation is performed by first setting the search line in the horizontal direction, moving sequentially from the top to the bottom of the drawing, and then setting the search line in the vertical direction.
By sequentially moving from left to right in the drawing, processing for one drawing is completed.

Figures 7a and 7b show the experimental results of this semicircle extraction process, which is a computer simulation of the device configuration shown in Figure 6.
is a part of the A1 drawing to be processed, and FIG. 7b is the extraction result of this part.

In this experiment, the radius of the arc was 2 to 3 mm in the original drawing.
The extraction target is a semicircle drawn with an arbitrary slope. In addition, the experiment processed binary drawing data that was read from a facsimile transmitter at a resolution of 8 lines/mm.

(5) Explanation of Effects As explained above, according to the present invention, a drawing is scanned using three search lines, and a semicircle is drawn using the intersection information of the three search lines and the figure line. As shown in Figures 7a and 7b, semicircles with varying inclinations and sizes can be extracted quickly and accurately. This method has the advantage that it is possible to automatically extract semicircles from drawings in which they are written.

[Brief explanation of drawings]

Figure 1 is an illustration of the principle of this method, Figure 2 is an illustration of the direction of the search line and the range of inclination of the semicircle to be extracted, Figure 3 is an illustration of the intersection group detection process, and Figure 4 is a classification table of intersection groups. , FIG. 5 is an explanatory diagram of the relationship between the search line position and the group of intersections, FIG. 6 is a block diagram of an example of a device configuration that implements this method, and FIGS. 7 a and 7 b are computer diagrams of this method. FIG. 2 is an explanatory diagram of experimental results based on simulation. In the figure, 1 is a semicircle, 2 is a group of exploration lines, 3 to 8 are the intersections of the figure line and the exploration line, 9 is a semicircle, 10 to 11 are the group of exploration lines, and 12 to 23 are the intersections of the figure line and the exploration line. , 24 is a semicircle, 25 is a group of exploration lines, 26 to 31
is the intersection of the figure line and the exploration line, 32 to 35 is the range on the exploration line, 36 is the end point of the arc, 37 is a semicircle, 38 to 39 are the exploration line group, 40 to 51 are the intersections of the figure line and the exploration line, 52 is a drawing input terminal, 53 is a frame memory, 54 is a control section, 55 is an intersection detection section, 56
is an intersection register, 57 is an intersection group detection section, 58 is an intersection set determination section, 59 is a semicircle determination section, and 60 is an output section.

Claims (1)

[Claims] 1. In a semicircle extraction processing method for extracting a semicircle on a drawing, means for scanning the drawing with a set of three parallel and equally spaced exploration lines to find the intersection of the exploration line and the figure line, and the intersection means for selecting six intersection points within a predetermined distance range from the search line, two each, and means for determining the center and radius of a circle passing through the three points, For the first set of three intersection points on the left side and the second set of three intersection points on the right side among the intersection points of each search line, the straight line defined by the two intersection points of each set and the other one Check to see if the distance to the intersection of is within a predetermined range, and if only one of the intersection points falls under this condition, the distance from the intersection of the straight line or the intersection of the pair is determined by the method of least squares. When the distance between the straight line and the center of the circle determined by the intersections of other pairs is within a predetermined range, the center position of the circle,
A semicircle extraction processing method characterized by extracting the radius, the slope of the straight line, and the direction of the straight line and the arc as semicircle information.