JPH043276A - Arc extraction method - Google Patents

Abstract

PURPOSE:To improve the extraction rate of a circular arc or a curve which intersects with another segment by comparing a radius and a center point of an average related to the whole candidate vector of the circular arc registered in a circular arc array, and a radius and a center point determined by each pair of adjacent candidate vectors. CONSTITUTION:An adjacent core vector is tracked in both the forward and the backward directions of a core vector, and an operation of searching the core vector of a circular arc candidate is repeated by deciding a condition between two core vectors, and the whole of the core vector derived as a circular arc candidate vector before that time. Subsequently, with regard to each vector in a series of circular arc candidate vector group which is obtained, a final condition decision is executed and an inappropriate vector is eliminated. In such a way, a circular arc or a curve which intersects (joins or branches) with other segment can also be extracted easily and exactly.

Description

[Detailed Description of the Invention] [Industrial Application Field] The present invention is a drawing recognition system, etc.
This paper relates to a method for extracting arcs from value images.

[Conventional technology]

In order to recognize symbols and figures on drawings, it is often necessary to extract arcs (curves) from input binary images.

Paper r Yamazaki, Imura; “Approximation of character axis outline using circular arcs and straight lines”, Journal of Information Processing Society of Japan, Vol. 26.

&4, July 1985, pp. 726-732J,
A method of scanning a binary image to extract blocks of contour lines, taking two sample points on each block sequentially, and approximating the space between them with an arc, and another sample beyond the two points to be approximated. A method of performing circular arc approximation between two points while also taking points into consideration is described.

The second approximation method is aimed at compressing the information of a single character image, but it can also be applied to extracting circular arcs from 52-value images.

[Problem to be solved by the invention]

Since the prior art described above is a method that directly uses dot data, there is a problem in that the amount of processing is too large for the purpose of extracting circular arcs (curves) in recognition systems for mechanical drawings and the like. In addition, although the three-point arc approximation method is superior in terms of approximation accuracy, it also significantly increases the amount of processing and also makes errors in extracting arcs that intersect with other line segments, which is not uncommon in single mechanical drawings. The problem is that the danger is actually increasing.

Furthermore, there is also the problem that it is not easy to identify the thickness of the line segment of the arc.

Therefore, an object of the present invention is to be able to increase the extraction rate of arcs or curves that intersect with other line segments, and to easily identify the thickness of the arc or curve.

Another object of the present invention is to provide a circular arc extraction method that is simple in processing content and suitable for application to a recognition system for one machine drawing or the like.

[a! Means to solve the problem]

The arc extraction method of the present invention traces black pixels of a binary image to extract a contour vector, extracts a skeleton vector from a pair of contour vectors, and, regarding the extracted skeleton vector, Search for a vector, and if the difference between the center point and radius of the circle determined by each adjacent vector and the vector of interest and the average center point and radius of the circle determined by the arc candidate vectors found so far is less than a certain threshold, A process of setting the adjacent vector as an arc candidate vector, and repeating a search for a similar arc candidate vector using this as the vector of interest, and two adjacent arc candidates in a group of one arc candidate vector obtained by this process. If the difference between the center point and radius of the circle determined by the vector and the average center point and radius of the circle determined by the group of arc candidate vectors is greater than or equal to a certain threshold, the two arc candidate vectors are deleted and the remaining arc candidate vectors are deleted. It is characterized by a process of extracting circular arc candidate vectors as core line vectors constituting the circular arc.

[For production]

In this way, the g-tangent vector is traced in both directions before and after the core vector, and the core vector of the arc candidate is searched for by determining the condition between the two core vectors and the entire core vector found as the arc candidate vector. This process is repeated, and a final conditional judgment is made for each vector in the resulting set of arc candidate vectors to eliminate inappropriate vectors, so it is possible to eliminate the possibility of intersecting (merging or branching) with other line segments. Arcs or curves can also be extracted easily and accurately.

In addition, the processing content is relatively simple, and 1 contour vector extraction and core line vector extraction are processes that are originally required as preprocessing in the case of recognition processing of 1 mechanical drawing, etc.
Furthermore, parameters for condition determination of arc candidate vectors can be easily changed as necessary. Furthermore, since the core line vectors extracted as arc candidate vectors are extracted by pairs of contour vectors, the line thickness of the arc or curve can be easily identified by referring to the corresponding pair of contour vectors. It is.

As described above, the arc processing method of the present invention is optimal and practical as a method for extracting arcs or curves in recognition systems such as mechanical drawings.

〔Example〕

FIG. 1 is a block diagram of a drawing recognition system according to an embodiment of the present invention. Reference numeral 6 denotes an image memory for storing binary image data such as mechanical drawings, and the binary image data is inputted manually via the input/output interface unit 2 from an external scanner or the like. 3 is the CPU that executes the process, 4 is the CP
This is a program memory that stores programs for processing executed by U3, and the programs stored here include programs for contour vector extraction, skeletonization, circular arc extraction, and other processing for drawing recognition.

5 is a data memory for storing intermediate data and result data of processing.

FIG. 2 is a flowchart showing the overall flow by the CPU 3.

It should be noted that the process ``■'' is a pre-process for the processing blocks ``--'' for practical circular arc extraction, but it is also a pre-process for the entire one-drawing recognition process. That is, the process ``■'' is not newly added for arc extraction according to the present invention.

Processing ■■ By adding black pixels of the binary image input to the image memory 1, a contour vector that linearly approximates the contour of the line segment is extracted, and the data is stored in the data memory 5. From this contour vector data, the center line of the pair of contour vectors is extracted as a skeleton vector, and the data is stored in the data memory 5 in correspondence with the contour vector.

In addition, such contour vector extraction (■) and skeletonization (
■) The paper ``Osawa et al.; ``Drawing processing using multidimensional data structure'', Transactions of the Institute of Electronics and Communication Engineers, Vol. J68-
D, Na4, April 1982 + Ri P-845-582J
The method described in the paper "Haka Osawa: ``Improvement of skeletonization method based on contour lines'', Information Processing Society of Japan, Vol. 3 may be used.

Processing (■ Refer to the skeleton vector data in the data memory 5 and search for skeleton vectors for which the processed flag is not set. Set the found skeleton vector as the vector of interest CVEC,
Proceed to processing ■. However, if a skeleton vector is longer than twice the character size, or if a vector of interest that is not selected as a vector of interest is not found, the one-arc extraction process is terminated.

Processing ■ Refer to the skeleton vector data and search for an adjacent vector NVEC ahead of the vector of interest CVEC from skeleton vectors for which the processed flag is not set.

FIG. 3 shows an example of the vector of interest and adjacent vectors. (A
) is a case where the adjacent point is a bending point, and (B) is a case where the adjacent point is a branch point or a confluence of line segments.

Note that the broken line in (B) is a connect vector for connecting the breaks at alternating points or branching points of the skeleton vector extracted from the contour vector, and is described in the above paper "Improvement of skeletonization method based on contour lines". Corresponds to "'glue vector".

Processing ■ Find the center point and radius of a temporary arc using each adjacent vector NVEC and the vector of interest CVEC. Specifically, for example, the intersection of the perpendicular bisector of the adjacent vector and the perpendicular bisector of the vector of interest is the center point, and the distance between this center point and the perpendicular bisector is the radius.

If this center point is within the range of the image and the radius is smaller than the number of vertical and horizontal pixels of the image, the points obtained up to that point are registered as curve (arc) candidates in the arc array in the data memory 5. The average radius and center point of the candidate vectors connected to the vector of interest are compared with the radius and center point obtained in the process, and if the difference is within a certain threshold, the adjacent vector NVEC is used as the candidate vector. L
Process as VEC and proceed to ■. If none of the adjacent vectors meet the above conditions, it is assumed that there is no candidate vector ahead of the vector of interest, and the process proceeds to process (2).

Processing ■ After registering (assigning) the arc candidate vector LVEC to the arc array in the data memory 5, this candidate vector LvEC
is newly selected as the vector of interest CVEC and returns to process (2). However, the search direction for adjacent vectors is the vector of interest CVEC.
It is fixed in front of the.

Processing (2) Since it is determined that there is no arc candidate vector ahead of the vector of interest CVEC, search for an adjacent vector NVEC behind the vector of interest CvEC. In other words, the same process as process (2) is performed in the opposite direction.

Processing ■ Similar to processing ■, candidate vector LVEC is calculated from adjacent vectors.
Search for. If it is not found, proceed to process dφ; if it is found, proceed to process (2).

Process (2) Assign the candidate vector LVEC to the circular arc array, set this candidate vector LVEC as a new vector of interest CVEC, and return to process (2). However, the direction in which candidate vectors are searched is fixed to the rear.

Processing [Phase] Find the average radius and center point for all the candidate vectors of the circular arcs obtained by the processes from ① to ② and registered in the circular arc array. Then, the radius and center point determined by each pair of adjacent candidate vectors are compared with the above-mentioned average radius and center point, and pairs of candidate vectors whose difference is greater than a certain threshold are excluded from the candidates (arc array (Delete from)
.

For example, in the case of a figure in which a straight line figure is connected to the left of a right semicircle, the core line vector shown by the arrow in Fig. 4 is extracted as a candidate vector for the circular arc, but the thick line Only the candidate vectors indicated by the arrows remain valid, and the candidate vectors indicated by the thin arrows are deleted.

Note that if the entire arc made up of the candidate vectors finally remaining in this way is smaller than the character size, the probability that it is a circular arc is low, so it is deleted from the candidates.

Then, the line thickness of one circular arc (curve) is determined by referring to the contour vector corresponding to the obtained circular arc candidate vector. The data on the thickness of the line and the center point and radius of the arc are stored in the arc array or in another predetermined area of the data memory 5.

Process 0: Set a processed flag on the core line vectors and the corresponding contour vectors constituting the arc, and return to process (2).

〔Effect of the invention〕

As is clear from the above description, the arc extraction method of the present invention can reliably extract arcs or curves that intersect with other line segments that often appear in mechanical drawings etc. through relatively simple processing. It is possible to easily change the judgment threshold for candidate vectors of circular arcs or curves depending on the purpose, and it is also possible to easily extract the line thickness of extracted circular arcs or curves.

This is an optimal and practical method for extracting arcs or curves in drawing recognition systems, etc.

[Brief explanation of the drawing]

Fig. 1 is a block diagram of a drawing recognition system according to an embodiment of the present invention, Fig. 2 is a flowchart showing the overall flow of arc extraction processing, Fig. 3 is an explanatory diagram of a vector of interest and adjacent vectors, and Fig. 4 is an explanatory diagram of the arc candidate vector finally obtained. 1... Image memory, 3... CPU, 4... Program memory, 5... Data memory, CVEC.
・Attention vector. NVEC: Neighboring vector.

Claims (1)

[Claims] (1) Extract the contour vector by tracing the black pixels of the binary image, extract the skeleton vector from the pair of contour vectors, search for adjacent vectors in front and behind the vector of interest for the extracted skeleton vector, and If the difference between the center point and radius of the circle determined by the adjacent vector and the vector of interest and the average center point and radius of the circle determined by the arc candidate vectors found so far is less than a certain threshold, then the adjacent vector is used as an arc. A process of repeating the search for similar arc candidate vectors using this vector as a candidate vector, and a process of repeating the search for a similar arc candidate vector using this as the vector of interest. If the difference between the center point and radius and the average center point and radius of the circle determined by the group of arc candidate vectors is greater than or equal to a certain threshold, the two arc candidate vectors are deleted and the remaining arc candidate vector is used as an arc. A circular arc extraction method characterized by comprising: a process of extracting as core line vectors constituting the arc;