CN102819743B - Detection method for quickly identifying straight-line segments in digital image - Google Patents

Abstract

The present invention relates to a method for calibrating a specific figure in an image, in particular to a detection method for quickly identifying a straight line segment in a digital image, comprising the following steps: a. inputting a binary image with a unit pixel width; b. setting Determine the length parameter, change parameter, pixel parameter and range parameter of the straight line segment to be detected; c, obtain the rough straight line segment; d, subdivide the detected straight line segment; e, the difference between the direction value of the adjacent link and the current straight line segment is less than Straight line segment of the difference threshold: the direction value is the quantitative definition of the direction of the neighborhood of the foreground pixel relative to its center position; the difference threshold refers to the threshold value of the difference between the direction values, which is used to determine whether the direction of two straight line segments is the same. Standard; f. Return the found straight line segment. The detection speed of the present invention is better than that of currently known TODIS with better detection accuracy; the detection accuracy is higher than that of KHT and EDLines, and the accuracy of the present invention is not lower than that of TOIDS.

Description

A Detection Method for Rapid Recognition of Straight Lines in Digital Images

technical field

The invention relates to a calibration method for a specific figure in an image, in particular to a detection method for quickly identifying a straight line segment in a digital image.

Background technique

In computer vision and machine vision disciplines, line segment detection is a line detection method that can simultaneously give the length and position of a line in a digital image. It has a wide range of applications, such as: image compression, material gap detection, stereo vision, road detection, robot navigation, etc. At the same time, it is also a basic point feature used in the target recognition method based on graph theory. Therefore, line segment detection not only has practical application value in industrial production, but also constitutes an important basis for more complex algorithms.

At present, there are three mainstream line segment detection methods at home and abroad: line segment detection based on line detection, line segment detection based on gradient information, and line segment detection based on boundary tracking.

(1) The line segment detection based on the line detection is based on the line detection, and the line segment has been given in the image according to the distribution of the boundary pixels on the line that has been identified by the line detection. The advantage of this method is that it can directly use the existing mature line detection algorithm. Since the earliest line detection method came out in 1962, after years of development, the types and quantities of this method are amazing, but most of them are based on the Hough transform, and the calculation of the Hough transform is very large, due to the existence of quantization errors It leads to parameter uncertainty and spurious peaks in the parameter space, which is less fast. In response to the above problems of the Hough transform, Xu et al. proposed the randomized Hough transform (RHT for short) in 1990. The random Hough transform uses many-to-one mapping, which avoids the huge amount of calculation of the standard Hough transform (SHT) one-to-many mapping, and the random Hough transform algorithm uses a dynamic linked list structure, only for many-to-one The parameter allocation units obtained by mapping are accumulated, which reduces the memory requirement, and at the same time makes the random Hough transform have the characteristics of infinite parameter space and arbitrarily high parameter precision. However, when dealing with complex images, random sampling will introduce a large number of invalid sampling and accumulation, which greatly reduces the performance of the method. Although there have been innovations in line detection in recent years, for example, the KHT algorithm (Gaussian Kernel-based Hough Transform; Chinese name: Gaussian Kernel-based Hough Transform) proposed by Fernandes in 2008, see L.A.F.Fernandes, M.M.Oliveira, "Real-time line detection through an improved Houghtransform voting scheme", Pattern Recognition, vol.41, no.1, pp.299-314.Jan.2008) and the N-point random Hough algorithm proposed by Mochizuki in 2009 (see Y.Mochizuki for details, A.Torii, A.Imiya, "N-Point Hough transform for line detection", Journal of Visual Communication and Image Representation, vol.20, no.4, pp.242-253.May.2009). Through in-depth analysis, it is found that although these new methods adopt the new Hough transform form, these new transform methods are more and more dependent on the previous preprocessing process. For example, the KHT algorithm, although the statistical binary Gaussian distribution function is used to generate a straight line peak, but in fact the calculation of the parameters of this statistical function is completely dependent on the link and segmentation algorithm proposed by Pope in 1994 and Lowe in 1987, the KHT algorithm The sample space of each straight line is obtained through the algorithm of Pope and Lowe, and then the Gaussian function can be applied. Similar to the KHT algorithm, the N-point random Hough algorithm uses randomly combined points to generate peaks. In order to reduce the total number of possible combinations, Mochizuki also uses a pre-processing algorithm. These preprocessing processes are actually equivalent to simple line segment detection, because they provide a set of points with better collinearity for the subsequent Hough transform, rather than traditional discrete points that do not have geometric meaning. Although the accuracy and efficiency of the new algorithm for straight line detection have been improved compared to the past, these algorithms did not consider line segment detection at the beginning of the design, so an additional post-processing process needs to be added to segment the line segment from the detected straight line. And according to Akinlar's analysis in 2011 (see C.Akinlar, C.Topal, "EDLines: Areal-time line segment detector with a false detection control", Pattern Recognition Letters, vol.32, no.13, pp.1633- 1642.Oct.2011), these algorithms will fuse discontinuous line segments, resulting in a large number of wrong detection results, and it is difficult to apply in more complex graphic image detection. Therefore, line segment detection based on line detection is difficult to complete fast processing tasks, so the current line segment detection algorithm seldom uses this method.

(2) The basic principle of line segment detection based on gradient information is derived from the straight line detection method proposed by Burns in 1986 (J.B.Burns, A.R.Hanson, E.M.Riseman, "Extracting straight lines", IEEE Trans.PatternAnal.Machine Intell., vol .8, no.4, pp.425-455.1986), the key idea of this method is to use the gradient direction of the boundary pixels produced by the second-order differential operator to identify the straight line. Over the decades, various gradient-based line segment detection methods have evolved. In 2008, Gioi proposed a fast line segment detection algorithm LSD (ALineSegment Detector, Chinese name: a line segment detection algorithm without adjusting parameters, see G.v.Gioi, R.Jakubowicz, J.Morel, J.M.Randall, "LSD : A Line Segment detector with a false detection control", CMLA.Centre de Mathematiques et de leurs Applications, Ecole Normale Superieure de Cachan (ENS-CACHAN), Germany.2008). LSD is the fastest line segment detection method with acceptable accuracy at that time. In 2011, Yang proposed the TODIS algorithm (A Line Segment Detector Using Two-orthogonal DirectionImage Scanning, Chinese name: A Line Segment Detection Algorithm Based on Dual Orthogonal Image Scanning, see K.Yang, S.S.Ge, H.He, "Robust line detection using two-orthogonal direction image scanning", Computer Vision and Image Understanding, vol.115, no.8, pp.1207-1222.Aug.2011), the accuracy of TODIS exceeds that of LSD, and it can more accurately identify multiple line segments , but its speed is only 1/8 of that of LSD. The speed of the EDLines algorithm proposed by Akinlar in 2011 (A Real-time Line Segment Detector with a False Detection Control Based on EdgeDrawing Algorithm, Chinese name: a real-time line segment detection algorithm based on edge drawing algorithm, error detection and controllable) Close to 10 times of LSD. Compared with the previous algorithms, the efficiency of EDLines has been greatly improved, and it already has the application value of rapid detection. By analyzing EDLines, it is found that the key to achieve the efficiency of this algorithm is to combine edge detection and line segment detection, that is, the input of EDLines is not discrete points, but preprocessed point sets with certain geometric information. This is similar to the KHT algorithm, except that the preprocessing of EDLines uses a new edge detection algorithm named Edgedrawing proposed by Topal in 2010 (see C.Topal, C.Akinlar, Y.Genc, "Edge drawing : a heuristic approach torobust real-time edge detection", ICPR, to be published). Since the input is the boundary of the link, EDLines only needs to divide or fuse it and add verification to complete line segment detection.

However, through analysis, it is found that the EDLines detection method has the following key problems.

First, for specific line segment detection in specific environments, the parameter-tuning-free nature of the method is essentially a drawback. In different applications, the line segment to be detected and the interference received in the detection are different. In a specific environment, in order to achieve a relatively ideal detection effect, it is necessary to conduct a large number of experiments in accordance with the detection requirements in this environment, and determine the parameters for the environment and its goals. Free parameter adjustment is a universal property, which is contrary to the practical optimization method.

Second, the least squares method with a threshold of 1 pixel is used for line segment detection, and the fixed threshold reduces the detection accuracy. Due to its parameter-free nature, the threshold of 1 pixel cannot be changed, which directly leads to the fact that the algorithm can only detect ideal straight lines with almost zero curvature changes. From its actual detection results, line segments with small changes in non-zero curvature are often segmented for multiple small line segments. If the detected line segment requires a certain length, this segmentation feature will greatly reduce the detection accuracy.

Third, the verification process of the algorithm depends on the gradient direction and skips the verification of long line segments. In fact, since the input is the point set generated by Edge drawing according to the gradient direction, the verification process still uses the gradient direction as the basis, which reduces the significance of verification. Moreover, the strategy of only verifying short line segments and not verifying long line segments reduces the amount of calculation, but reduces the verification effect. Therefore, the accuracy of this algorithm does not improve much compared to LSD.

(3) The concept of line segment detection based on boundary tracking was first proposed by Etemadi in 1992 (A. Etemadi, "Robustsegmentation of edge data", Conf. on Image Processing and its Applications, USA, 1992, pp.311-314), which The first method uses the boundary point information generated by edge detection to link adjacent boundary points into a curve by moving along the boundary composed of boundary points, and then divides the curve according to certain criteria to obtain line segments. The advantage of Etemadi's algorithm is that it is simple and fast, but the disadvantage is that the accuracy of line segment detection is low, and there are many short line segments with a length of only 5 or 6 pixels remaining in the resulting image. In recent years, although the Etemadi algorithm has been widely used in various visual tasks, it has not been improved much, and it still remains at the level of the 1990s.

At present, the development trend of line segment detection basically revolves around the gradient information. Although the accuracy and efficiency have been greatly improved compared with the past, the algorithms in recent years rely too much on the gradient information, ignore the geometric information of the boundary itself, and lack effective prediction. Processing and post-processing means, so there is still a lot of room for innovation and improvement in line segment detection. However, engineering applications still urgently need to improve the speed and accuracy of line segment detection methods.

Contents of the invention

The technical problem to be solved by the present invention is: in order to overcome the deficiencies in the prior art, the present invention provides a detection method for quickly identifying straight line segments in digital images. The different theories of the method combine the gradient information and geometric features of pixels in digital images, and apply statistical methods to quickly and accurately detect straight line segments with given geometric feature values in images. By analyzing and comparing the internationally popular line segment detection method in recent years and the computational complexity of this method, its recognition speed and accuracy have reached to a certain extent, even surpassed the currently known international similar methods, thus having a better Industrial application value and academic theoretical value.

(1) Since the current international mainstream straight line segment detection methods generally adopt non-parametric design, which reduces the degree of manual intervention, this design has certain advantages in some aspects, but in the actual application of industrial production, due to the wide variety of actual requirements, there is no The parametric design only detects according to its preset internal logic, which will generate a lot of useless information, which cannot meet the detection speed and accuracy requirements of industrial applications. The present invention automatically changes the internal logic and calculation amount of the algorithm according to external requirements and implementation conditions by requiring manual input or setting of four parameters, that is, the length of the line segment, the degree of curvature change of the line segment, the number of tentative link pixels and the fusion range of the line segment. Without parametric design, it can give accurate results at an appropriate speed in industrial applications that have specific requirements for the straight line segment to be detected.

(2) According to the theoretical classification used, the currently commonly used straight line segment detection methods roughly include three categories based on the Hough transform principle, gradient information and geometric information. Due to the large amount of calculation of the Hough transform, the method using this principle is inefficient and the accuracy is average. In recent years, the KHT method born in 2008 is more representative. The gradient information method has a great breakthrough in speed, but the accuracy is still not much different from the traditional Hough transform method. The recent typical method is the EDLines method that appeared in 2011. The geometric information method has not made a big breakthrough all the year round, and still stays at the level of the 1990s, a typical example is the Etemadi method born in 1992. The present invention combines two methods of gradient information and geometric features, and avoids the design idea of using single gradient information and integrating solidified early boundary detection methods in the EDLines method. By separating the early boundary detection and the late line segment detection, the present invention can be modularized It can be matched with any boundary detection method to complete the detection task, and the present invention does not rely on a single gradient information, but carries out the detection task in a targeted manner according to the given geometric parameters, and uses statistical methods to analyze the detection results during the detection process. Revised in real time. Through effect comparison and calculation complexity analysis, the speed of the present invention is obviously higher than the KHT method and the Etemadi method, slightly lower than the EDLines method; its accuracy is obviously higher than the KHT method and the Etemadi method, and higher than the EDLines method.

The technical solution adopted by the present invention to solve the technical problem is: a detection method for quickly identifying straight line segments in a digital image, comprising the following steps:

(a) Input a binary image with a unit pixel width. The binary image is composed of foreground pixels and background pixels. Foreground pixels refer to pixels containing certain graphic information, and background pixels refer to pixels that do not contain graphic information. Pixels: A binary image is provided by edge detection, and then a binary image with a unit pixel width is obtained by using the skeletalization method;

(b) Set the length parameter, change parameter, pixel parameter and range parameter of the straight line segment to be detected: the length parameter refers to the minimum length of the straight line segment acceptable in the final detection result; the change parameter refers to the tolerance to the degree of curvature change of the straight line segment, The greater the tolerance, the closer the detected straight line segment is to the curve segment, that is, the straight line segment is composed of several sub-line segments with obvious differences in direction; the pixel parameter refers to the number of pixels that are tentatively linked when the local curvature of the straight line segment changes significantly ;The range parameter refers to the line segment fusion range parameter;

(c) Obtain a rough straight line segment;

(d) Subdividing the detected straight line segments;

(e) Link the adjacent straight line segment whose direction value difference with the current straight line segment is less than the difference threshold: the direction value is a quantitative definition of the direction of the neighborhood of the foreground pixel relative to its center position; the difference threshold Value refers to the threshold value of the difference between the direction values, which is used to determine whether the directions of two straight line segments are the same;

(f) Return the line segment found.

The specific steps of the step (c) are

(c1) Define the direction value, the difference between the direction values and the difference threshold;

(c2) Scan the binary image input in step (a) in a certain order, and determine a specific direction value according to the current image scanning sequence, and the specific direction value means that the difference from the direction value representing the scanning direction does not exceed the difference Threshold values for all directions pointing to unscanned areas;

(c3) When a foreground pixel is found, pause the scan, center on the foreground pixel, and only detect the neighborhood pointed to by the specific direction value described in step (c2), if a foreground pixel is found, continue to detect in step (c2) The neighborhood pointed to by the specific direction value, repeating this process until no foreground pixel is found in the neighborhood or reaches the image boundary;

(c4) Tentative link: Determine the starting direction value, the starting direction value is the direction close to the scanning direction but pointing to the unscanned area after removing the specific direction value described in step (c2), the described Proximity means that there is no interval between two pixels in the image space; starting from the last foreground pixel found in step (c3), check whether the neighborhood pointed to by the starting direction value has a foreground pixel; if a new Foreground pixels, set the old foreground pixels as background pixels, record their orientation values and tentatively link new foreground pixels; repeat this process until the total number of linked foreground pixels is equal to the pixel parameter, or no new foreground is found before the total number does not reach the pixel parameter pixel;

(c5) During the tentative linking process, establish a temporary data structure and a permanent data structure for permanent storage, the permanent data structure includes a temporary area and a permanent area, record the number of pixels of each direction value and obtain it dynamically The maximum direction value at the current moment, the number of pixels of the direction value refers to the number of foreground pixels that take the direction value, and the maximum direction value refers to the direction value with the largest number of foreground pixels: all during the tentative linking process The number of pixels of each direction value generated in is recorded in an initialized temporary data structure;

In each tentative connection, if the number of linked foreground pixels does not reach the pixel parameter and no new foreground pixels are found around the current pixel, check whether the number of linked foreground pixels exceeds the length during the tentative linking process parameter, if it exceeds, record all the pixels that have been linked and identify them as a straight line segment, if not, discard these pixels;

If the number of linked foreground pixels reaches the pixel parameter and there are still new foreground pixels around the current pixel, record the direction value of the current pixel and the direction value of the last tentative link in the temporary area of the permanent data structure, and start According to the difference between the direction value of the foreground pixel to be linked and the maximum direction value, it is judged whether to continue the link;

(c6) If the difference between the maximum orientation value and the orientation value of the foreground pixel to be linked is less than the difference threshold, then link the pixel and record its orientation value in the temporary area of the permanent data structure, otherwise start the tentative link again at the current pixel position ;

(c7) At the end of the heuristic linking, compute the difference between the maximum orientation value in the temporary data structure and the maximum orientation value in the temporary area of the permanent data structure:

If the difference is less than the difference threshold, the foreground pixels and corresponding direction values saved by the tentative link in the temporary data structure are stored in the temporary area of the permanent data structure, and step (c6) is repeated until no new foreground pixels, Until the image boundary is reached; then judge whether to save the foreground pixels in the temporary area of the permanent data structure to the permanent area and re-initialize the temporary data structure according to the length parameter;

If the difference is greater than the difference threshold, stop the link, judge whether to save the foreground pixels in the temporary area of the permanent data structure to the permanent area and reinitialize the temporary data structure according to the length parameter.

Foreground and background pixels are defined as pixels with non-zero value and 0 value, or as pixels with value 255 and pixels with value less than 255, respectively.

In the step (c2), the image scanning sequence is performed from top to bottom and from left to right.

The definition of the direction value in the step (c1) is generated by the filtering window and the direction measurement unit. After the definition of the direction value and the difference between the direction values is completed, the difference threshold is defined.

In the step (c1), the number of discrete values of the two-dimensional filter function used in the digital image and its distribution shape are used as the filter window, the size of the filter window is 3×3, and the direction value can be defined by an integer value, Can also be an angle or radian value. After defining the direction value, the difference between different directions can be quantified, that is, the difference between the direction values is calculated according to the difference criterion. The difference criterion means that the direction deviation of two straight lines is within the difference threshold, that is, they are regarded as having the same direction , for example, calculates the smaller or larger angle between two directions, and takes one of them as the difference between the direction values.

Generally, when the direction value is an angle value or a radian value, the corresponding difference threshold can be 45° or That is, when the difference between the direction values of two straight lines is less than 45° or When , the two straight line segments are considered to have the same direction.

The direction value is defined by an integer value, which is defined as follows: Let the direction value of the positive direction of the x-axis be 0, and in the counterclockwise direction, the direction values at every 45° are 1, 2, 3, 4, 5, 6, 7; direction The difference in values is given by:

if|dir1-dir2|>4then difference=8-|dir1-dir2|; else difference=|dir1-dir2|.

Where dir1 and dir2 represent the direction values of the two straight line segments respectively, and difference represents the difference between dir1 and dir2; the difference threshold is defined as 2. That is, when the difference between the direction values of two straight line segments is less than 2, the two straight line segments are regarded as straight line segments with the same direction value.

In the step (c2), the specific direction values are 6, 7 and 0.

By running the experimental program based on Visual Studio development and adopting the step (c) method of the present invention on the computer, a large number of images are processed and by investigating the direction of each straight line segment in the permanent data structure permanent area generated by the step (c) It is found that the direction value information of the ideal straight line segment with small curvature changes generally has the characteristics of Gaussian distribution, that is, there is only one obvious peak and the peak is the maximum direction value; while the curve segment has at least two peaks.

According to this discovery, the direction value information corresponding to each straight line segment stored in the permanent area of the permanent data structure will be detected. The line segment is the curve segment and starts splitting. Therefore, the specific steps of the step (d) are

(d1) Detect the direction value information corresponding to each straight line segment stored in the permanent area of the permanent data structure. When the ratio of the largest direction value to the second largest direction value of the straight line segment exceeds the change parameter, the straight line segment is a curve segment and to divide;

(d2) For the curve segment found in step (d1), starting from any of its endpoints, check the direction value of each pixel one by one and record the direction value in the initialized temporary data structure, if the direction value is the same as that in the temporary data structure If the difference between the recorded arbitrary direction values is greater than the difference threshold, mark this pixel as a potential segmentation point and initialize the temporary data structure; repeat the above steps until all points on the curve segment have been detected;

(d3) Calculate the distance between every two potential split points, and if the distance is not less than the length parameter, split the curve segment at these two potential split points.

Through the detection and segmentation of steps (c) and (d), there may be straight line segments in the image where the difference in direction value is less than the difference threshold and the distance between the endpoints is less than the length parameter. The current subroutine will try to fuse multiple lines with these characteristics Line segments to form a single line segment. The biggest difficulty in step (e) is how to explore the nearby straight line segments according to the general trend of the current straight line segment. By running the experimental program based on Visual Studio development on the computer and adopting the method of step (c) and step (d) of the present invention, a large number of images are processed and by investigating the running results, it is found that the curvature of the straight line is relatively small near the midpoint Small, that is, the pixel direction value near the midpoint basically reflects the general trend of the straight line segment.

Therefore, the specific step of the step (e) is to take the midpoint or a point in the area not exceeding 50% of the length parameter near the midpoint as the center, and the sub-line segment that satisfies the length parameter, and use its direction as a sample, Start from the two endpoints of the current straight line segment, and search according to the direction of the sample. If the difference between the direction value of the current straight line segment and the direction value is less than the difference threshold, the two straight line segments will be fused; repeated several times, until there are no more fused line segments.

In the step (e), take a sub-line segment centered on the midpoint of the current straight line segment and satisfy the length parameter, and use the direction value of the sub-line segment as a sample.

The neighborhood described in the present invention is the same as the definition known to those skilled in the art, that is, it refers to a set composed of all pixels except the current pixel in the filtering window centered on the current pixel.

The beneficial effect of the present invention is that the present invention is a detection method for quickly identifying straight line segments in digital images,

(1) Since the present invention is implemented with a computer program, the detection speed is mainly evaluated by analyzing the computational complexity of the program. In terms of computational complexity, step (c) of the present invention is the part that requires the most calculations. Since this part does not perform indiscriminate projection on each pixel like the Hough transform, this part only performs non-zero pixels and The adjacent pixels are analyzed, so its computational complexity is O(l s), where l is the length of the longest straight line segment, s is the total number of line segments, and the computational complexity of the Hough transform is O( n ² ), where n is one dimension of the image.

Further analysis shows that there is a very close relationship between l and s. If l, which represents the length of the line segment, is very large, then s, which represents the total number of line segments, will be very small. Because the longer the line segment is, the more image space it occupies, which generally leads to a decrease in the total number of line segments. Conversely, if the total number of line segments is large, the length of the longest line segment will not be large. Therefore, there is a mutual balancing relationship between l and s. Therefore, the amount of computation required for step (c) of the present invention is far less than O(n ² ).

The complexity of step (d) is Max(O(s), O(l·d)), where d represents the total number of curve segments found by performing a search with O(s) complexity. Since d cannot be greater than s, the computational complexity of step (d) is the same as that of step (c), which is O(l·s).

The complexity of step (e) is O(s).

In summary, the computational complexity of the computer program applicable to the present invention is O(l·s), and according to the document "Robust Line Detection Using Two-orthogonal Direction Image Scanning" (K.Yang, SSGe, H.He, ComputerVision and According to the analysis of BU-Scan process in Image Understanding, vol.115, no.8, pp.1207-1222, Aug.2011.), the complexity of TODIS is at least O(n ² ). In terms of complexity analysis, the detection speed of the present invention is better than the currently known TODIS with better detection accuracy.

(2) The accuracy of the present invention is intuitively reflected in the comparison of detection results of straight line segments in digital pictures. After a large number of comparisons, it is concluded that the detection accuracy of the present invention is higher than that of KHT and EDLines, and the accuracy of the present invention is not lower than that of TOIDS, and TODIS is the most accurate detection method for straight line segments currently known.

Description of drawings

The present invention will be further described below in conjunction with the accompanying drawings and embodiments.

Figure 1 is the main UML activity diagram of the present invention.

Fig. 2 is a definition diagram of direction values in a specific embodiment of the present invention.

Fig. 3 is a UML activity diagram of step (c) in the present invention.

Figure 4 is a UML activity diagram for tentatively linking m pixels in Figure 3 .

FIG. 5 is a UML activity diagram for recording relevant information of the current pixel in three temporary lists in FIG. 3 .

Figure 6 is a UML activity diagram for computing searchDir in Figure 3 .

FIG. 7 is a UML activity diagram recorded according to the length of straight line segments in FIG. 3 .

Fig. 8 is a UML activity diagram of step (d) in the present invention.

Fig. 9 is a UML activity diagram of step (e) in the present invention.

Figure 10 is a UML activity diagram of the link endpoint in Figure 9.

Figure 11 is a UML activity diagram for finding the endpoint in Figure 10.

Figure 12 is a comparison chart of the detection results of KHT and the present invention.

Fig. 13 is a comparison chart of the detection results of EDLines and the present invention.

Fig. 14 is a comparison chart of TODIS and the detection results of the present invention.

Figure 15 is a binary image labeled with orientation values.

Figure 16 is a binary image labeled with orientation values and paths.

Detailed ways

The present invention is described in further detail now in conjunction with accompanying drawing.

Figure 1 shows the main UML activity diagram of the present invention. The present invention comprises the following steps:

(a) Input a binary image with a unit pixel width. The binary image is composed of foreground pixels and background pixels. Foreground pixels refer to pixels containing certain graphic information, and background pixels refer to pixels that do not contain graphic information. Pixels: A binary image is provided by edge detection, and then a binary image with a unit pixel width is obtained by using the skeletalization method;

(b) Set the length parameter, change parameter, pixel parameter and range parameter of the straight line segment to be detected: the length parameter refers to the minimum length of the straight line segment acceptable in the final detection result; the change parameter refers to the tolerance to the degree of curvature change of the straight line segment, The greater the tolerance, the closer the detected straight line segment is to the curve segment, that is, the straight line segment is composed of several sub-line segments with obvious differences in direction; the pixel parameter refers to the number of pixels that are tentatively linked when the local curvature of the straight line segment changes significantly ;The range parameter refers to the line segment fusion range parameter;

(c) Obtain a rough straight line segment;

(d) Subdividing the detected straight line segments;

(e) Links are adjacent to straight line segments with similar direction values;

(f) Return the line segment found.

Step (c), step (d), and step (e) in the present invention will be described below in conjunction with the UML activity diagrams in FIG. 3 to FIG. 11 .

Here is a specific embodiment of the present invention under certain preconditions. Specific prerequisites include the following points: the image scanning sequence is from top to bottom and from left to right; the filter window size is 3×3. The direction values are defined by Fig. 2; the difference between the direction values is given by:

if|dir1-dir2|>4then difference=8-|dir1-dir2|; else difference=|dir1-dir2|.

Among them, dir1 and dir2 represent the direction values of two straight line segments respectively, and difference represents their difference; the difference threshold is defined as 2; foreground pixels and background pixels are defined as pixels with non-zero and zero values, respectively.

The UML activity diagram for step (c) includes Figures 3 to 7. In Figure 3, the variable m represents the pixel parameter, the variable minLength represents the length parameter, and the variable nextDirection is an array with a length of 8 that stores the direction value of the search starting point within the 3×3 neighborhood. When the program needs to check the neighborhood of the current pixel, it will determine the first neighborhood pixel to be checked in this array, and then use it as a starting point to check in the direction opposite to the current scanning direction. In this embodiment, The program will check counterclockwise at the start of the search. The index of nextDirection corresponds to the current pixel direction value. For example, if the current pixel value is dir, the starting point is stored in the array member nextDirection[dir] whose index is dir. The search starting point is represented by the variable searchDir in Figure 3, and its value is given by the following formula out:

if dir is even, then searchDir=(dir+7)mod 8; else searchDir=(dir+6)mod 8.

Among them, even represents an even number, and mod represents a modulo operation. According to the above formula, the starting points corresponding to all direction values can be calculated before the program runs, and then saved in the nextDirection array. In the order of index 0 to index 7, the values of the nextDirection member are 7, 7, 1, 1, 3, 3, 5, and 5. The variable Difference in Figure 3 is an 8×8 matrix, and the value of each member corresponds to the difference between a pair of direction values with the same value as its index value. For example, the member Difference[3,5] with the index (3,5) saves is the difference between a direction value of 3 and a direction value of 5, which is given by the difference between direction values formula above. Since the number of direction values is fixed at 8 quantities, the difference between them can be calculated in advance, and then stored in the 8×8 Difference matrix, eliminating the need for subsequent repeated calculations. The Difference is given by the following formula:

$\mathrm{<span\; class="notranslate">\; difference</span>}<span\; class="notranslate">\; =</span>\left[\begin{array}{cccccccc}\mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 1</span>}& \mathrm{<span\; class="notranslate">\; 2</span>}& \mathrm{<span\; class="notranslate">\; 2</span>}& \mathrm{<span\; class="notranslate">\; 4</span>}& \mathrm{<span\; class="notranslate">\; 3</span>}& \mathrm{<span\; class="notranslate">\; 2</span>}& \mathrm{<span\; class="notranslate">\; 1</span>}\\ \mathrm{<span\; class="notranslate">\; 1</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 1</span>}& \mathrm{<span\; class="notranslate">\; 2</span>}& \mathrm{<span\; class="notranslate">\; 3</span>}& \mathrm{<span\; class="notranslate">\; 4</span>}& \mathrm{<span\; class="notranslate">\; 3</span>}& \mathrm{<span\; class="notranslate">\; 2</span>}\\ \mathrm{<span\; class="notranslate">\; 2</span>}& \mathrm{<span\; class="notranslate">\; 1</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 1</span>}& \mathrm{<span\; class="notranslate">\; 2</span>}& \mathrm{<span\; class="notranslate">\; 3</span>}& \mathrm{<span\; class="notranslate">\; 4</span>}& \mathrm{<span\; class="notranslate">\; 3</span>}\\ \mathrm{<span\; class="notranslate">\; 3</span>}& \mathrm{<span\; class="notranslate">\; 2</span>}& \mathrm{<span\; class="notranslate">\; 3</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 1</span>}& \mathrm{<span\; class="notranslate">\; 2</span>}& \mathrm{<span\; class="notranslate">\; 3</span>}& \mathrm{<span\; class="notranslate">\; 4</span>}\\ \mathrm{<span\; class="notranslate">\; 4</span>}& \mathrm{<span\; class="notranslate">\; 3</span>}& \mathrm{<span\; class="notranslate">\; 2</span>}& \mathrm{<span\; class="notranslate">\; 1</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 1</span>}& \mathrm{<span\; class="notranslate">\; 2</span>}& \mathrm{<span\; class="notranslate">\; 3</span>}\\ \mathrm{<span\; class="notranslate">\; 3</span>}& \mathrm{<span\; class="notranslate">\; 4</span>}& \mathrm{<span\; class="notranslate">\; 3</span>}& \mathrm{<span\; class="notranslate">\; 2</span>}& \mathrm{<span\; class="notranslate">\; 1</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 1</span>}& \mathrm{<span\; class="notranslate">\; 2</span>}\\ \mathrm{<span\; class="notranslate">\; 2</span>}& \mathrm{<span\; class="notranslate">\; 3</span>}& \mathrm{<span\; class="notranslate">\; 4</span>}& \mathrm{<span\; class="notranslate">\; 3</span>}& \mathrm{<span\; class="notranslate">\; 2</span>}& \mathrm{<span\; class="notranslate">\; 1</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; 1</span>}\end{array}\right]$

The variables ListOfStrings and ListOfDirections in Figure 3 are index-based, respectively saving the pixel coordinates of the corresponding straight line segment and its pixel direction value. For example, if n straight line segments are currently detected, the members ListOfStrings[i] and ListOfDirections with the same index i [i] respectively save the coordinate information and direction value information of the pixels contained in a straight line segment. The variable ListOfOccurences in Figure 3 stores the number of pixels corresponding to each direction value of each straight line segment. Taking the binary image shown in Figure 15 as an example, the numbers on the foreground pixels in the figure represent their orientation values. Table 1 shows the values corresponding to the three variables ListOfStrings, ListOfDirections and ListOfOccurences in the binary image corresponding to Figure 15 .

Index 0 of the three variables corresponds to the left line segment in Figure 15, and index 1 corresponds to the right line segment. The left line segment contains 9 pixels and the right one contains 8 pixels. The 8 values of ListOfStrings[1] store the offset of each pixel from top to bottom relative to the upper left corner of Figure 15, and the ninth member of ListOfStrings[1], ListOfStrings[0][8] is empty, because The line segment on the right is only 8 pixels long. ListOfDirections[1] saves the direction value of each pixel, and the ninth member of ListOfDirections[0] is correspondingly empty, and its member order is consistent with ListOfStrings[1], that is, ListOfStrings[1][i] and ListOfDirections[1] [i] corresponds to the same pixel in the right segment. Therefore, the storage order of the values in ListOfDirections[1] is consistent with the pixel order corresponding to ListOfStrings[1], that is, the direction value identification order of the left line segment from top to bottom in Figure 15. The first 8 members of ListOfOccurences[1] store the number of pixels of direction values from 0 to 7 respectively, and its ninth member stores the direction value with the most number of pixels in the current state. Observe Figure 15, for the line segment on the right In other words, the value is obviously 7, and the number of pixels corresponding to it is 5, that is, the direction value of the 5 pixels on the right line segment is 7.

Figure 3 also contains the following variables: dir, tempString, tempDirections, and tempOccurences. The variable dir represents the direction value of the current pixel, which is initialized to 7, that is, the first foreground pixel found on the straight line segment is given a direction value of 7, and the direction value of the foreground pixel found later is determined by its adjacent pixel value in the previous pixel. After the current pixel is updated to the new foreground pixel, the value of dir is also updated to the direction value of the new pixel. The variables tempString, tempDirections, and tempOccurences have the same functions as the variables ListOfStrings, ListOfDirections, and ListOfOccurences respectively. The difference is that the first three will be reinitialized as needed, while the latter three are only initialized once and store data permanently.

A brief description of the flow in Fig. 3 is now given. After the program runs and the variables are initialized, the outermost three layers of pixels of the image will be set as the background pixels, and then the image will be scanned line by line and pixel by pixel. After the foreground pixel is found, the image scanning will pause, and the program will check the neighborhood of the foreground pixel according to the scanning direction, that is, the neighborhood with the current pixel as the center and the value of 6, 7, and 0 directions. If a new foreground pixel is found in the neighborhood, The program will continue to check the 6, 7, 0 direction of the new pixel to see if there are still foreground pixels, and this process continues until no new foreground pixel is found in the 6, 7, 0 direction. Since the 6, 7, 0 direction is the lower right corner of the current pixel, this process is actually looking for the rightmost endpoint of the line segment.

After finding the rightmost endpoint, the heuristic link shown in Figure 4 is run. The linking actually does not consider the direction of m pixels, heuristically links these pixels, and then checks whether the maximum direction value of the linked m pixels is the same as the maximum direction value of the line segment before the heuristic linking started. The variable searchDir in Figure 4 has the same meaning as the variable with the same name in Figure 3, representing the starting point of the search. The variable length indicates the number of points for tentative linking. The variable suspiciousDirs is only used inside Figure 4, and its role is the same as ListOfOccurences in Figure 3. Since the variables tempString, tempDirections and tempOccurences have already recorded some pixels in the line segment in Figure 3, these pixels may eventually become part of the line segment, but it is still uncertain during tentative linking, and the data in the three variables can neither be saved in Variables ListOfStrings, ListOfDirections and ListOfOccurences cannot be cleared, so suspiciousDirs is initialized to count the distribution of pixel direction values in tentative links, and tempString and tempDirections continue to add tentativeness under the condition that the original data is not cleared. Links the found points. If there are no m points found, or the difference between suspiciousDirs[8] and tempOccurences[8] is greater than or equal to 2, that is, the direction value of the tentative link has the largest number of pixels and the line segment linked before the tentative link has the largest number of pixels If the difference of direction value is greater than 45°, the tentative link fails, and the tentative link pixel coordinates and direction values saved in tempString and tempDirections will be deleted according to the value of length. If the tentative link is successful, tempString and tempDirections remain unchanged, and the value of suspiciousDirs member except index 8 is added to the value of tempOccurences member with the same index, and stored in tempOccurences.

Figure 3 After the first tentative link is successfully completed, the normal link starts. Different from the tentative link, when the normal link finds a new foreground pixel, it will calculate the difference between the direction value of the new pixel and tempOccurences[8], that is, check whether the direction of the new pixel is consistent with the general trend of the line segment. If the difference is less than 2, Then save the new pixel information in the three temporary lists, and continue the normal link; if the difference is greater than or equal to 2, start the tentative link described above, if the link is successful, continue the normal link, if the link fails, check the tentative link Before the start of the link, if the length of the found line segment is greater than minLength, the data in the three temporary lists will be saved to ListOfStrings, ListOfDirections and ListOfOccurences respectively; if it is less than minlength, the three temporary lists will be reinitialized. After a link ends, all the foreground pixels found in this link will be set as background pixels, and the paused image scanning will continue to scan the previously suspended pixels until new foreground pixels are found, and then the above linking process will be repeated. When the last pixel in the image is scanned, the algorithm shown in Figure 3 will stop, and step (d) shown in Figure 8 will start to run.

The UML activity diagram for step (d) is Figure 8. The main variables defined in Figure 8 are thresholdRatio, length, strings ToRemove, firstDir, secondDir, possibleSplitPositions, actualSplitPositions, groupsOfSimilarDirs, curStr, curDirs and curOccurs. The variable thresholdRatio represents a change parameter manually input, and in FIG. 8, this value is preset as 0.1. The variable length represents the total number of straight line segments found in Figure 3. The variable stringsToRemove is used to record the index of the segment being divided. The variable firstDir and the variable secondDir represent the maximum direction value and the second maximum direction value of a line segment respectively. The variable possibleSplitPositions indicates possible split positions. The variable actualSplitPositions represents the determined split positions. The variable groupsOfSimilarDirs represents a list of sets with similar direction values. The variables curStr, curDirs and curOccurs respectively indicate the corresponding members of the line segment currently being processed in the lists ListOfStrings, ListOfDirections and ListOfOccurences.

The program shown in Figure 8 transfers the references of the members corresponding to the current straight line segment in ListOfStrings, ListOfDirections and ListOfOccurences to curStr, curDirs and curOccurs respectively, and then finds firstDir and secondDir in curOccurs. If the difference between firstDir and secondDir is less than 2, it means that most points on the straight line segment have the same direction value, and there is no need to split; if the difference is greater than or equal to 2 and the ratio of the two exceeds thresholdRatio, it means that the straight line segment has at least Contains two sub-line segments with obvious direction differences. The program starts to look at curDirs and initializes the variables possibleSplitPositions and groupsOfSimilarDirs, adds the index of the first point of curStr to possibleSplitPositions, and then checks the line segment except for the first and last pixel. Orientation values for other pixels. Because the direction value of the first pixel is always set to 7 in Figure 3, and the last pixel is often the point where the direction value fluctuates the most before the end of the tentative link, so these two points are removed. Add a new group in groupsOfSimilarDirs and add the direction value of the second point to the group. Look at the next member of curDirs and compare its value with all direction values contained in the last group added in groupsOfSimilarDirs, if the group does not contain the value and the difference is less than 2, add the value to the group; if the group contains This value and its difference is less than 2, do nothing; if the difference is greater than or equal to 2, add a new group in groupsOfSimilarDirs and add this value to the new group, and record the index of the current pixel in curStr in possibleSplitPositions. Repeat the above steps for each pixel up to the second-to-last pixel. Finally add the index of the last point of curStr to possibleSplitPositions.

After checking curDirs, initialize the variable actualSplitPositions. Calculate the difference between each two members of the possibleSplitPositions line segment in turn. If the difference between two members is greater than or equal to minLength, add these two members to actualSplitPositions. After checking all members of possibleSplitPositions, if actualSplitPositions is non-empty, split curStr and curDirs according to the members of actualSplitPositions, save the split sub-line segments in ListOfStrings and ListOfDirections, calculate and save the corresponding ListOfOccurences members, in ListOfStrings, ListOfDirections and Save the split line segment in ListOfOccurences; if actualSplitPositions is empty, do nothing. Repeat the above steps in Figure 8 for each straight line segment found in Figure 3 in ListOfStrings until all the straight line segments in Figure 3 have been checked. So far step (d) is over, and step (e) starts to run.

The UML activity diagram of step (e) includes Figures 9 to 11. The main variables involved are detectRadius, curIndex, curStr, maxDir, isLeftConnected, isRightConnected, leftIndices, leftTerminals, rightIndice, rightTerminals, leftPattern, rightPattern, nodesOfConnection, segments, nodeCollection , segmentCollection and stringsToRemove. The variable detectRadius stores the value of the manually input range parameter, which is preset to 8 in FIG. 9 . The variable curIndex represents the index value of the straight line segment currently being processed in ListOfStrings. The variables curStr and stringsToRemove have the same meaning as the variables of the same name in step (d). The variable maxDir represents the maximum direction value for the line segment with index curIndex. The variables isLeftConnected and isRightConnected respectively indicate whether the endpoints on the left and right sides of curStr are connected to the corresponding endpoints of other straight line segments. The variables leftIndices, rightTerminals, rightIndice, and leftTerminals represent the index of the straight line segment on the left side of curStr and its right endpoint, and the index of the straight line segment on its right side and its left endpoint, respectively. The variables leftPattern and rightPattern respectively represent the path of repeating or negating the midpoint of curStr, minLength direction values. The variable nodesOfConnection holds the determined left or right endpoints of the line segments to be merged. The variable segments saves the effective path from an endpoint of curStr to the endpoint saved by nodesOfConnection. The variables nodeCollection and segmentCollection respectively contain all nodesOfConnection members and segments generated by cyclically running the program shown in Figure 10 in Figure 9 .

The image scanning order and the linking method of step (c) will lead to the situation that the first and last members of curStr are opposite to the left and right endpoints of the actual line segment. Assuming that the left and right line segments in Figure 15 have indexes 0 and 1 respectively, then press from top to Next, in the scanning method from left to right, the uppermost right endpoint of the left line segment is found first, so it is the first member in ListOfStrings[0], and its left endpoint is found last, so it is also in ListOfStrings[0] The last member, and the first and last members of the straight line segment on the right in Figure 15 are consistent with the left and right endpoints. Now assuming that the right end point of the left line segment and the left end point of the right line segment in Figure 15 are to be linked, then the first half of the fused straight line segment includes members in ListOfStrings[0] arranged in reverse order, and the second half includes members in order Members in ListOfStrings[1]. Combined with the direction value in Figure 2, the program shown in Figure 11 can be used to divide the first and last members of curStr into left and right endpoints.

Figure 9 first runs the link endpoint program shown in Figure 10. The variable detectRadius determines the range of the straight line segment to be fused, that is, for curStr, the program in Figure 10 only detects that the index value in ListOfStrings is located in the left interval [curIndex-detectRadius, curIndex-1] and the right interval [curIndex+1, curIndex+detectRadius] to see if there is a straight line segment that can be merged with curStr. The maximum direction value of the fused line segment is the same as curStr, or completely opposite. For example, the maximum direction value of curStr is 4, then the maximum direction value of the fused line segment can only be 4 or 0. Note that in Figure 2, 0 and 4 actually represent straight line segments in the horizontal direction. If straight segments are found on both sides of curStr, only the straight segments on one side will be merged by subsequent procedures. Although it is found that there are straight line segments that can be fused on both sides of curStr, the fusion process cannot be carried out immediately, because once fused, the three fused straight line segments must be deleted from the ListOfStrings, thus destroying the order of the ListOfStrings index, so that the fused The line segment loses the possibility of being merged by other line segments. Therefore, first, the program only checks whether the left endpoint of each straight line can be merged with the right endpoints of other straight lines. If so, record the left and right endpoints. After all the line segments are checked, the recorded endpoints and line segments are used at one time. information for fusion.

On the premise that leftIndices and rightIndice are not empty, the program shown in Figure 10 starts to try to fuse curStr with the corresponding straight line segment. The method is to take the midpoint of ListOfDirections[curIndex] as the center, and the left and right directions of length minLength/2 as the path, check the 3×3 neighborhood of each point on the path, and see the fusion of straight line segments stored in rightTerminals and leftTerminals Whether the endpoint exists. According to the maximum direction value of curStr, the paths of the two endpoints have opposite direction values, and the variables leftPattern and rightPattern correspond to the paths of the left endpoint and the right endpoint, respectively. Take Figure 16 as an example, its central part is a straight line segment with 7 pixels, the center of the straight line segment is marked by a light-colored square with a value of 5, the left and right end points are dark-colored squares marked with a value of 5 and 7, and the left end point is on the left side The gray square in is the left path, and the gray square to the right of the right endpoint is the right path. Assuming that minLength is 5, leftPattern contains the direction values [5, 3, 5, 4, 4] in turn, and leftPattern actually repeats each of the straight line segments with the midpoint as the center and the length of 5 in the order from right to left. The direction value of the point, and the path of the left end point of the straight line segment starts from the left end point, and expands according to the value of the member in leftPattern as the moving direction. The variable rightPattern is obtained by first reversing the order of the members in leftPattern, that is, [4, 4, 5, 3, 5], and then reversing its value according to the direction value in Figure 2. In Figure 2, the inverses of direction values 3, 4, and 5 are 7, 0, and 1 in turn, so the final rightPattern is [0, 0, 1, 7, 1].

After determining the path, when isLeftConnected is true, the program will check whether the neighborhood of each point in leftPattern contains the right endpoint of the fusionable line segment recorded in rightTerminals, or if isRightConnected is true, it will check whether the neighborhood of each point in rightPattern exists The endpoints in leftTerminals. If the end point of the fused line segment is found in the path, the index of the corresponding line segment, the end point, the end point corresponding to curIndex and curStr are saved in nodesOfConnection, for example, when the neighborhood of a point in leftPattern includes the end point in rightTerminals, The program will store the line segment index in leftIndices corresponding to the endpoint, the endpoint, the left endpoint of curIndex and curStr as elements of a four-dimensional vector, and this vector is stored in nodesOfConnection. Note that the order of the elements in this vector is always the index of line segment α, the right endpoint of line segment α, the index of line segment β, and the left endpoint of line segment β, so for the endpoints in leftTerminals, it will follow curIndex, right endpoint of curStr, rightIndices The line segment indices in and the order of the endpoints in leftTerminals are saved as a four-dimensional vector. After this process ends, if nodesOfConnection is not empty, the part of the path from the starting point to the end point of the fused line segment will be saved in segments, and finally the program shown in Figure 10 will return nodesOfConnection and segments, and the "link endpoint" process ends. The program returns to Figure 9 .

After the variables nodeCollection and segmentCollection respectively save the nodesOfConnection members and segments generated by the program in Figure 10, the program in Figure 9 will repeat the program in Figure 10 until all members in ListOfStrings are traversed. Since nodeCollection stores the information of the fused endpoints and their straight segments saved in the four-dimensional vector mentioned above, the program will record the index of the fused line segment in stringsToRemove, and then use the segmentCollection of the two line segments in sequence according to the members of nodeCollection Corresponding member connection in , add newly fused line segment information to ListOfStrings, ListOfDirections and ListOfOccurences, and delete the original two line segment information according to the index information in stringsToRemove. Repeat this process until all members of nodeCollection are traversed. Step (e) ends.

So far, the variables ListOfStrings, ListOfDirections and ListOfOccurences respectively save the found straight line segment, its direction value record and direction value statistical information.

Fig. 12, Fig. 13 and Fig. 14 have shown KHT, EDLines, TODIS and the comparison figure of the detection result of the present invention respectively, and wherein, what the first row all shows is unprocessed image, and what the second row shows is the processing of existing method As a result, the third column shows the detection results of the present invention. In Fig. 12, it can be clearly found that the F02 detection result of the present invention successfully detects the straight edge of the utility pole and the transformer on the left side of the image, but KHT does not detect it. The F22 detection result of the present invention successfully detects the upper edge of the dish-shaped building in the image, but KHT does not. The F32 detection result of the present invention successfully detects the edge of the enclosure wall of the building in the lower right corner of the image, but KHT does not. All straight line segments detected by KHT can be found to be detected by the present invention by observing the pictures. Therefore, the detection accuracy of the present invention is higher than that of KHT.

In Fig. 13, G12 and G22 respectively show that the present invention successfully detects the gap between the tiles above the building in the G10 image, and the linear dividing line between high light and low light on the woman's arm in the G20 image. These are not detected by EDLines, by observation, all straight line segments detected by EDLines are basically detected by the present invention.

In Figure 14, since TODIS is currently known as the most accurate detection method for straight line segments, the present invention is not far behind it. However, in the detection results shown in H22, it can still be found that the present invention has successfully detected the high-end glass of skyscrapers. gaps, while TODIS does not. Through observation, the present invention has detected basically all straight line segments detected by TODIS. Therefore, in a sense, the accuracy of the present invention is not lower than that of TOIDS, but the detection speed of the present invention is obviously higher than that of TODIS.

Inspired by the above-mentioned ideal embodiment according to the present invention, through the above-mentioned description content, relevant workers can make various changes and modifications within the scope of not departing from the technical idea of the present invention. The technical scope of the present invention is not limited to the content in the specification, but must be determined according to the scope of the claims.

Table 1

Claims (9)

1. A detection method for fast recognition of straight line segments in digital images, characterized in that it may further comprise the steps: (a) Input a binary image with a unit pixel width. The binary image is composed of foreground pixels and background pixels. Foreground pixels refer to pixels that contain graphic information, and background pixels refer to pixels that do not contain graphic information. : A binary image is provided by edge detection, and then a binary image with a unit pixel width is obtained by using the skeletonization method; (b) Set the length parameter, change parameter, pixel parameter and range parameter of the straight line segment to be detected: the length parameter refers to the minimum length of the straight line segment acceptable in the final detection result; the change parameter refers to the tolerance to the degree of curvature change of the straight line segment, The greater the tolerance, the closer the detected straight line segment is to the curve segment, that is, the straight line segment is composed of several sub-line segments with obvious differences in direction; the pixel parameter refers to the unscanned area when the local curvature of the straight line segment changes significantly. The number of pixels of sexual links; the range parameter refers to the line segment fusion range parameter; (c) Obtain a rough straight line segment; (d) Subdividing the detected straight line segments; (e) Link the adjacent straight line segment whose direction value difference with the current straight line segment is less than the difference threshold: the direction value is a quantitative definition of the direction of the neighborhood of the foreground pixel relative to its center position; the difference threshold Value refers to the threshold value of the difference between the direction values, which is used to determine whether the directions of two straight line segments are the same; (f) Return the found line segment; The specific steps of the step (c) are (c1) Define the direction value, the difference between the direction values and the difference threshold; (c2) Scan the binary image input in step (a) in a certain order, and determine a specific direction value according to the current image scanning sequence, and the specific direction value means that the difference from the direction value representing the scanning direction does not exceed the difference Threshold values for all directions pointing to unscanned areas; (c3) When a foreground pixel is found, pause the scan, center on the foreground pixel, and only detect the neighborhood pointed to by the specific direction value described in step (c2), if a foreground pixel is found, continue to detect in step (c2) The neighborhood pointed to by the specific direction value, repeating this process until no foreground pixel is found in the neighborhood or reaches the image boundary; (c4) Tentative link: Determine the starting direction value, the starting direction value is the direction close to the scanning direction but pointing to the unscanned area after removing the specific direction value described in step (c2), the described Proximity means that there is no interval between two pixels in the image space; starting from the last foreground pixel found in step (c3), check whether the neighborhood pointed to by the starting direction value has a foreground pixel; if a new Foreground pixels, set the old foreground pixels as background pixels, record their orientation values and tentatively link new foreground pixels; repeat this process until the total number of linked foreground pixels is equal to the pixel parameter, or no new foreground is found before the total number does not reach the pixel parameter pixel; (c5) During the tentative linking process, establish a temporary data structure and a permanent data structure for permanent storage, the permanent data structure includes a temporary area and a permanent area, record the number of pixels of each direction value and obtain it dynamically The maximum direction value at the current moment, the number of pixels of the direction value refers to the number of foreground pixels that take the direction value, and the maximum direction value refers to the direction value with the largest number of foreground pixels: all during the tentative linking process The number of pixels of each direction value generated in is recorded in an initialized temporary data structure; In each tentative connection, if the number of linked foreground pixels does not reach the pixel parameter and no new foreground pixels are found around the current pixel, check whether the number of linked foreground pixels exceeds the length during the tentative linking process parameter, if it exceeds, record all the pixels that have been linked and identify them as a straight line segment, if not, discard these pixels; If the number of linked foreground pixels reaches the pixel parameter and there are still new foreground pixels around the current pixel, record the direction value of the current pixel and the direction value of the last tentative link in the temporary area of the permanent data structure, and start According to the difference between the direction value of the foreground pixel to be linked and the maximum direction value, it is judged whether to continue the link; (c6) If the difference between the maximum orientation value and the orientation value of the foreground pixel to be linked is less than the difference threshold, then link the pixel and record its orientation value in the temporary area of the permanent data structure, otherwise start the tentative link again at the current pixel position ; (c7) At the end of the heuristic linking, compute the difference between the maximum orientation value in the temporary data structure and the maximum orientation value in the temporary area of the permanent data structure: If the difference is less than the difference threshold, the foreground pixels and corresponding direction values saved by the tentative link in the temporary data structure are stored in the temporary area of the permanent data structure, and step (c6) is repeated until no new foreground pixels, Until the image boundary is reached; then judge whether to save the foreground pixels in the temporary area of the permanent data structure to the permanent area and re-initialize the temporary data structure according to the length parameter; If the difference is greater than the difference threshold, stop the link, judge whether to save the foreground pixels in the temporary area of the permanent data structure to the permanent area and reinitialize the temporary data structure according to the length parameter; The specific steps of the step (d) are (d1) Detect the direction value information corresponding to each straight line segment stored in the permanent area of the permanent data structure. When the ratio of the largest direction value to the second largest direction value of the straight line segment exceeds the change parameter, the straight line segment is a curve segment and to divide; (d2) For the curve segment found in step (d1), starting from any of its endpoints, check the direction value of each pixel one by one and record the direction value in the initialized temporary data structure, if the direction value is the same as that in the temporary data structure If the difference between the recorded arbitrary direction values is greater than the difference threshold, mark this pixel as a potential segmentation point and initialize the temporary data structure; repeat the above steps until all points on the curve segment have been detected; (d3) Calculate the distance between every two potential segmentation points, if the distance is not less than the length parameter, then segment the curve segment at these two potential segmentation points; The specific steps of the step (e) are Take the midpoint of the current straight line segment or a point in the area not exceeding 50% of the length parameter near the midpoint as the center, and the sub-line segment that satisfies the length parameter, take its direction as a sample, and start from the two endpoints of the current straight line segment respectively , search according to the direction of the sample, if the difference between the direction value of the current straight line segment and the direction value is less than the difference threshold value, the two straight line segments will be fused; repeat multiple times until there is no more straight line segment that can be fused until. 2. the detection method of a kind of fast recognition straight line segment in digital image as claimed in claim 1, is characterized in that: foreground pixel and background pixel are defined as having non-zero value pixel and 0 value pixel respectively, or are respectively defined as value 255 pixels and pixels with values less than 255. 3. A detection method for quickly identifying straight line segments in digital images as claimed in claim 1, characterized in that: in the step (c2), the image scanning sequence is from top to bottom and from left to right . 4. A detection method for quickly identifying straight line segments in digital images as claimed in claim 1, characterized in that: the definition of the direction value in the step (c1) is generated by the filter window and the direction measurement unit, and the direction value is completed After the definition of the difference between and the direction value, define the difference threshold. 5. A detection method for quickly identifying straight line segments in a digital image as claimed in claim 4, characterized in that: in the step (c1), the discrete value of the two-dimensional filter function used in the digital image is The number and its distribution shape are used as the filter window. The size of the filter window is 3×3. The direction value can be defined by an integer value, or an angle value or a radian value. 6. A kind of detection method for quickly identifying straight line segments in digital images as claimed in claim 5, characterized in that: when the direction value is an angle value or a radian value, the corresponding difference threshold is 45 ° or, that is, when two Two straight line segments are considered to have the same direction when the difference between the direction values of the two straight lines is less than 45° or . 7. a kind of detection method of fast recognition straight line segment in digital image as claimed in claim 5 is characterized in that: direction value is defined by integer value, is defined as follows: set the direction value of x-axis positive direction to be 0, press counterclockwise Direction, the direction values at intervals of 45° are 1, 2, 3, 4, 5, 6, 7 in turn; the difference between the direction values is given by the following formula: If | dir 1- dir 2|＞4, then difference =8-| dir 1- dir 2|; otherwise difference =| dir 1- dir 2|; Where dir1 and dir2 represent the direction values of the two straight line segments respectively, and difference represents the difference between dir1 and dir2 ; the difference threshold is defined as 2. 8. A detection method for quickly identifying straight line segments in digital images according to claim 7, characterized in that: in the step (c2), the specific direction values are 6, 7 and 0. 9. A detection method for quickly identifying a straight line segment in a digital image as claimed in claim 1, characterized in that: in the step (e), take the midpoint of the current straight line segment as the center and satisfy the length parameter Sub-segment, take the direction value of this sub-segment as a sample.