JPH044479A - Method for extracting straight line - Google Patents

Abstract

PURPOSE:To reduce the occurring number of wrong extraction by discriminating whether or not the adjacent vector of a marked vector is a candidate vector for a straight line by using the angle and line width between the marked and adjacent vectors. CONSTITUTION:The angle and line width between a marked vector and its adjacent vector are used as discriminating conditions for discriminating whether or not the adjacent vector is a candidate vector for a straight line. Accordingly, it is possible to reduce such an error of extracting a large-diameter circular arc, etc., as a straight line. In case a plurality of adjacent vectors meeting the discriminating conditions exists, one of the vectors having the minimum angle and line width is selected as the candidate vector for the same straight line together with the marked vector. Therefore, the number of wrong selection of candidate vectors at the junction or diverging point of a plurality of vectors is reduced and the extracting accuracy of a straight line intersecting other segments can be raised. Therefore, the number of wrong extraction can be reduced.

Description

DETAILED DESCRIPTION OF THE INVENTION [Field of Industrial Application] The present invention relates to a method for extracting straight lines from a binary image input in a drawing recognition system or the like.

[Conventional technology]

Regarding this type of straight line extraction, please refer to Japanese Patent Application Laid-Open No. 1-269185.
A straight line component extraction method described in the publication is known. In this method, as shown in FIG. 6, the vector of interest v
A straight line PIP2 connecting 1 and the vector v2 connected to this
If the distance t□ between the vector and the intersection of both vectors is less than or equal to the threshold T, then the vector V1. If V2 is integrated and replaced with a straight line P□P2, and there is a vector ■3 connected to vector v2, then similarly straight line P□P3 and vector v1. ■ Compare the distance t2 from the intersection point of 2 with the threshold value T, and if t2≦T, by repeating the integration process of integrating the vector V3 into vectors 1 to V2 and replacing them with the straight line PiP3, the straight line This is a method to extract.

[Problem to be solved by the invention]

However, at the intersection of line segments, that is, the confluence or branching point of multiple vectors, extraction errors are likely to occur due to erroneous integration of vectors, and it is also easy to mistakenly extract arcs with large radii as straight lines. There were problems in applications that involved processing complex drawings.

An object of the present invention is to provide a practical straight line extraction method that can reduce such erroneous extraction.

[Means to solve the problem]

The invention described in claim (1) of the claims relates to a vector obtained by a broken line approximation of a line segment on a binary image, and searches for adjacent vectors of a vector of interest, and determines the angle and line width between the vector and the vector of interest. Adjacent vectors each having a threshold value or less are determined to be candidate vectors for the same straight line as the vector of interest, and if there are multiple adjacent vectors whose angle and line width with the vector of interest are each less than the threshold value, the vector with the smallest angle and line width is determined. A straight line is constructed by determining the adjacent vector of - as the candidate vector, and repeating the same process of searching for adjacent vectors and determining the candidate vector, using the adjacent vector determined as the candidate vector as the vector of interest. The invention according to claim (2), which is characterized in that a group of candidate vectors is extracted, extracts a contour vector by tracing black pixels of a binary image, and extracts a pair of contour vectors. The present invention is characterized in that a skeleton vector is extracted from the skeleton vector, the straight line extraction process as described above is performed on the skeleton vector, and the line width of the straight line is determined by referring to a contour vector corresponding to the extracted skeleton vector as a candidate vector.

[For production]

The conditions for determining whether a vector adjacent to a vector of interest is a straight line candidate vector are the angle between the two vectors and the line width (
(see FIG. 4), it is possible to reduce errors in extracting circular arcs with large diameters as straight lines. Also,
When there are multiple adjacent vectors that meet the criteria, the one with the smallest angle and line width is selected as the candidate vector for the same straight line as the vector of interest. It is possible to reduce selection mistakes in candidate vectors and improve the accuracy of extracting straight lines that intersect with other line segments.

Further, according to the invention described in claim (2), the accurate line width (thickness) of the extracted line segment can be easily determined.

Furthermore, the processing content is relatively simple, and by changing the judgment threshold for candidate vectors, it can easily be applied to drawings that have been made up or drawn by hand, and contour vector extraction and core line vector extraction are This is a process that is originally required as preprocessing in the case of recognition processing of mechanical drawings, etc.

As described above, the straight line extraction method of the present invention is optimal and practical as a straight line extraction method in a recognition system for mechanical drawings and the like.

〔Example〕

FIG. 1 is a block diagram of a drawing recognition system according to an embodiment. Reference numeral 1 denotes an image memory for storing binary image data such as mechanical drawings, and the binary image data is inputted from an external scanner or the like via an input/output interface section 2. 3 is a CPU that executes processing, and 4 is a program memory that stores programs for processing executed by CPU 3. The programs stored here include contour vector extraction, skeletonization, straight line extraction, and other drawing recognition. Contains processing programs. 5 is a data memory for storing intermediate data and result data of processing.

FIG. 2 is a flowchart showing the overall flow of straight line extraction processing by the CP'U 3.

In addition, processing ■■ is a process for practical straight line extraction ~
0 preprocessing, but it is also preprocessing for the entire drawing recognition process. In other words, processing (1) and (2) is not necessary only for straight line extraction according to the present invention.

Processing ■■ By tracing the black pixels of the binary image input to the image memory 1, a contour vector that approximates the contour of a line segment as a broken line 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. This core line vector is a vector obtained by approximating a line segment to a broken line.

Note that such contour vector extraction (■) and skeletonization (■) are described, for example, in the paper ``Osawa et al.; ``Drawing processing using multidimensional data structure'', Transactions of the Institute of Electronics and Communication Engineers, Vol. J
68-D, No. 4. April 1982.

pp. 845-582J and the paper "Osawa et al.; ``Improvement of skeletonization method based on contour lines'', Information Processing Society of Japan Vol. 3 01" 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 has not been set. Let the found core vector be the attention vector CVEC,
Proceed to processing ■. If the vector of interest is not found, the process ends.

Processing ■ Refer to the skeleton vector data and search for an adjacent vector NVEC ahead of the target vector CVEC from skeleton vectors for which the processed flag has not been 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 that connects the breaks at alternating current points or branching points of the skeleton vector extracted from the contour vector, and is based on the above-mentioned paper ``Improvement of the skeletonization method based on contour lines.'' “glue” in “
Corresponds to the vector ″.

Processing ■ Find the angle and line spacing (see Figure 4) between each adjacent vector NVEC and the vector of interest CVEC, and if the angle and line spacing are each less than the threshold, use that adjacent vector as a candidate for the same straight line as the vector of interest. It is determined that the vector is LVEC, and the process proceeds to process (2).

At intersections where multiple core line vectors merge or diverge,
There are cases where there are a plurality of adjacent vectors to the vector of interest, and the angles and line widths of the plurality of vectors are equal to or less than the threshold value. In this case, among the plurality of adjacent vectors, one adjacent vector with the smallest angle and line width with respect to the vector of interest is determined to be the candidate vector LVEC.

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 (substituting) the straight line candidate vector LVEC in the straight line candidate array in the data memory 5, this candidate vector LV
EC is newly selected as the vector of interest CVEC and the process returns to process (2). However, the search direction for adjacent vectors is the attention vector CV.
It is fixed in front of the EC.

Processing ■ Since it is determined that there is no straight line 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 [phase]; if it is found, proceed to process ■.

Process (2) Substitute the candidate vector LVEC into the linear candidate array, and return to process (2) with this candidate vector LVEC as the new vector of interest CVEC. However, the direction in which candidate vectors are searched is fixed to the rear.

Processing [Phase] Confirm the entire candidate vectors obtained by the processes from ① to ② and registered in the straight line candidate array using the line width threshold. That is, among the series of candidate vectors shown by arrows in FIG. Select only the candidate vectors 1 to 1 (candidate vectors indicated by thick arrows) that are not . If the length from one end to the other end of the candidate vector group selected here is greater than the character size, this candidate vector group is determined to be a straight line vector. That is, in the example of FIG. 5, a straight line with P□ as the starting point and P2 as the ending point is extracted.

Furthermore, the accurate line width (thickness) of the straight line is determined by referring to the contour vector corresponding to the determined vector.

Process 0: Set a processed flag on the skeleton vector determined to be a straight line and the corresponding contour vector, and return to process (2).

〔Effect of the invention〕

As is clear from the above description, the straight line extraction method of the present invention can reliably extract straight lines that intersect with other line segments that often appear in mechanical drawings etc. through relatively simple processing, and can extract circular arcs with small curvature. It is possible to reduce incorrect extraction of curves such as, and it is also possible to accurately extract the thickness of straight lines.
Furthermore, it is possible to handle everything from clean-cut drawings to hand-drawn drawings by simply changing the determination threshold for straight line candidate vectors, making it an optimal and practical straight line extraction method for mechanical drawing recognition systems and the like.

[Brief Description of the Drawings] Fig. 1 is a block diagram of a drawing recognition system according to an embodiment of the present invention, Fig. 2 is a flowchart 1 showing the overall flow of straight line extraction processing, and Fig. 3 is a vector of interest. FIG. 4 is an explanatory diagram of the angle and line width between the vector of interest and the adjacent vector, FIG. 5 is an explanatory diagram of the method for determining a straight line candidate vector using a line width threshold, and FIG. FIG. 2 is an explanatory diagram of a conventional method. 1... Image memory, 3... CPU, 4... Program memory, 5... Data memory, CVEC・
...Attention vector, NVEC...Adjacent vector.

Claims (2)

[Claims] (1) Regarding vectors that are a line segment on a binary image that is approximated by a broken line, search for adjacent vectors to the vector of interest, and find adjacent vectors whose angles and line widths with the vector of interest are less than the threshold, respectively, using the same straight line as the vector of interest. If there are multiple adjacent vectors whose angle and line width with the vector of interest are each less than the threshold, the one adjacent vector with the minimum angle and line width is determined to be the candidate vector, and the candidate vector is determined to be the candidate vector. Straight line extraction is characterized by extracting a group of candidate vectors constituting a straight line by repeating the process of searching for similar adjacent vectors and determining candidate vectors using an adjacent vector that has been determined to be a vector as a vector of interest. Method. (2) Extract the contour vector by tracing the black pixels of the binary image, extract the skeleton vector from the pair of contour vectors, perform the straight line extraction process described in claim (1) on the skeleton vector, and use it as a candidate vector. A straight line extraction method characterized by determining the line width of a straight line by referring to a contour vector corresponding to an extracted core line vector.