Angle aided circle detection based on randomized Hough transform and its application in welding spots detection

1.   Introduction

The circle recognition and detection techniques play more and more crucial roles in machine vision, and novel circle detection methods are frequently proposed by researchers ^[1,2]. One of the most effective methods of circular object feature extraction is the Hough transform technique, which was invented by Duda and Hart in 1972 ^[3]. The purpose of the technique is to extract specific geometric shapes and characteristics in the region of interest (ROI) through space transforming and parameters accumulating ^[3]. For example, Cha et al. ^[4] used Hough transform to detect loosened bolts by using the Hough transform and support vector machines.

Conventional standard Hough Transform was concerned with the identification of arbitrary shape positions, while it takes a long time calculating and needs huge memory with the increasing dimensions of parameters ^[3]. In order to compensate for the defects of Hough Transform, Xu et al. ^[5] proposed the random Hough transform algorithm. The circle detection method aided with curvature was presented by Yao Z ^[6], and Yao & Gall ^[7] came up with an improvement of Hough transform based on a dynamic recognition voting mechanism. And a novel method based on the internal tangent angle variance was implemented by Xavier ^[8]. However, these methods will obtain confused results when detecting multiple and nearly circular objects. To overcome this shortcoming, researchers have proposed several improvement methods based on the clustering ^[9] and stochastic Hough transform such as Randomized Circle Detection ^[10]. Specifically, it randomly selects 3 points for circle fitting with the calculation of standard equations of the circle, then checks whether the circle exists and if there are enough edge points on the fitted circle.

On the other hand, researchers proposed a method based on adaptive cluster detection to locate circles ^[11], which behaves well when there is low noise in the image. Shen and Song ^[12] also came up with a way of recognizing overlapped circles. Most of these algorithms only worked with acceptable results in special cases, while their robustness and universality are insufficient. Moreover, the processing speeds of these algorithms are affected due to the random mining of invalid accumulation.

In this paper, we propose a novel angle aided circle detection approach based on the randomized Hough transform method by optimizing the random Hough transform and reducing its computation complexity. The circle detection accuracy is significantly improved with the proposed approach, which has been successfully applied in the welding spot detection application on automobile body. The machine vision technology was used to assist welding spot detection to improve the accuracy and speed of the detection. By avoiding invalid accumulation, the proposed method can detect the precise position of the welding spot under the circumstance with high noise. The proposed method has particular significance in welding spot detection of industrial bodywork.

2.   Angle aided circle detection based on Hough transform

The circle detection plays an important role in recognition and localization of welding spots. The proposed recognition and detection system consists of two stages. In particular, the first stage generates a list of edge points in the region proposals, and the second stage calculates the parameters of circles.

2.1.   Sampling of the edge points

Conventional circle detection methods rely on the random sampling of binary images, which will cause the invalid accumulation and calculation. The proposed AACD algorithm shortens the computation by reducing the number of invalid points in edge images, which has several parameters related to the range of sampling points. Images are preprocessed with the region proposal method to get the proposals of the object, and the parameters obtained by proposals are passed into the AACD algorithm. Then, the random sampling is performed only in the obtained region proposals.

As depicted in Figure 1, two points P₁ (x₁, y₁) and P₂ (x₂, y₂) are randomly chosen, and the third point is selected with the following condition:

Where r_max = p_Range × min(imgSize)/2, and the radius threshold parameter p_Range is set to 1 by default for different sizes of circles in the image, the r_max represents half of the smaller value in the image size, which effectively reduces the invalid sampling while simultaneously ensures high robustness and high detection speed. When selecting the third point, the following conditions should be satisfied:

The AACD algorithm limits the ranges of radius and sampling to be smaller fixed values when detecting the circle with known parameters. Thus, the processing speed is improved, and the computational complexity is decreased.

2.2.   Parameters of AACD

The angle of an inscribed triangle is half of a central angle that subtends the same arc. By using the relationship of θ = 2γ, the circles can be detected with angle aided. The advantages of the proposed AACD method is that the method avoids the use of gradients compared to other Hough transforms algorithms, and thus the error is reduced. The angle γ can be calculated according to the following expression:

Where k_P1P2 is the slope of line P₁P₂, and the perpendicular bisector of P₁P₂ passes through the center of circle C1. The distance between points O and P_M is defined as follows:

And it is obvious that coordinates x and y can be calculated as illustrated in Figure 2:

Where

Referring to Figure 2, one can obtain the following relationships:

Combining the Equation 6 with Equation 7, the length of $\Delta x$ and $\Delta y$ can be expressed as:

And coordinates of the circle center can be determined as:

In order to deal with the noise and deformation, the center of the circle should also be adjusted. Although the shape of the welding spot is not a perfect circular, the choice of the circular model of welding spots is sufficient and its reasonableness is discussed in Section 2.3. Therefore, the center of the circle can be formulated as:

The shortest distance $O{P_3}$, i.e., the circle radius, can be expressed as:

2.3.   Hypothesis rationality of circular model

Due to the presences of oil stains and weld marks on BIW (Body in White) during the welding process, as shown in Figure 3, the shape of the welding spot is similar to a circular shape, or only a partial circular contour. However, it is reasonable to choose a circular model to detect the position of the welding spot. The ultrasonic detecting and actual spot weld regions are marked with red and green dotted coils, respectively, as shown in Figure 3a. The working principle of the ultrasonic detection system for spot weld is shown in Figure 3b. As long as the Visual Location Region is larger than the Ultrasonic Detection Region, the ultrasonic detector can normally detect the welding spot.

In summary, the shape of the welding spot does not affect the detection operation of the ultrasonic detector. Therefore, in order to facilitate the study and the unification of the model, we modeling the spot weld with a circle due to the following reasons: (1) the shape of the welding spot is visually closer to a circle. (2) The AACD algorithm can improve the detection accuracy of welding spots by improving the round edge point sampling strategy, as the experimental results shown in Section 3.

3.   Results

The AACD algorithm was compared against the circle detection methods implemented with Open Source Computer Vision Library (OpenCV), Random Hough transform (RHT) ^[5], Randomized Circle Detection (RCD) ^[10] to verify the feasibility of the proposed method. Testing images are of size 256 × 256 pixels (a) and 512 × 384 pixels (b), as shown in Figure 4. An excessive noise is added in Figure 3a with a number of intersecting circles of different sizes. Two kinds of circles were drawn in Figure 3b, one is the target to be detected, while the other is an approximate circular interference. The images were repeatedly detected (20 times) with different threshold sets by the OpenCV, RHT, RCD, and AACD methods, respectively.

The comparison results were shown in Tables 1 and 2. The detection results in Table 1 demonstrated that the RHT and AACD are much faster than the OpenCV and RCD algorithms.

Particularly, RCD algorithm shows poor accuracy (less than 50%) in the circle detection when the image noise is excessive. The AACD algorithm roughly took the same time with the RHT method to process the testing images with the accuracy of 97.5%. It took much longer time for RCD algorithm to detect the real circles. It is obviously that the RCD algorithm cannot distinguish between approximate and real circles effectively. Specifically, the AACD algorithm took only half of the time as the RHT method consumed, and it reached an accuracy of 99%. The detection results for multi-circle detection with the proposed AADD algorithm are shown in Figure 5.

According to the experiment, the proposed AACD algorithm is a better choice in the following situations:

(1) Process images with high noise levels.

(2) Detect circles in a complex environment.

(3) Require a particularly short processing time.

3.1.   Application of the proposed AACD algorithm

BIW refers to the bodywork in automobile manufacturing in which sheet components of a vehicle has been welded together before coating. The quality of the welding spot in BIW directly affects the automotive safety level. To automatically detect the quality of the spot weld, the spots are located through machine vision technology and inspected by the ultrasonic detection system, as illustrated in Figure 6. During the detection of BIW welding spots, we found that the edges of welding spots were presented with high noise and fictitious circles due to the oil stain and weld mark. To solve these problems, we implemented a particular image preprocessing approach based on the proposed AACD algorithm and achieved satisfactory results.

3.1.1.   Preprocessing of the image

For preprocessing of the image with welding spots, a MATLAB program was used to draw contour of welding spots, as shown in Figure 7. The contours of the welding spots show that its gray values are unevenly distributed, which leads to the failure of canny detection, as shown in Figure 7f.

Images are often accompanied by high-density salt-and-pepper noise. In order to obtain the adaptive binary edge image, we eliminated the noise and reduced the effect of weld mark. Conservative smoothing is a noise reduction technique that sacrifices noise suppression power for preserving the high spatial frequency details such as sharp edges in an image. After the procedure of the conservative smoothing, edges of the welding spots were reserved and the majority of noise was removed.

Furthermore, Top-hat transforms are used for background equalization in this paper. Objects can be extracted separately from the background by using top-hat transforms. Additionally, the images were converted to binary images for further pre-processing to correct the effect of the non-uniform illumination. Practically, the images with welding spots were characterized by identical features. For instance, the gray-level values of the welding spots were less than 70. Through lots of experiments, it is found that the welding spots can be reliably separated (as shown in Figure 8) when the threshold value was set to T:

Where σ is the mean value of the gray images. Figure 8a shows the binary images after the processing with the conservative smoothing and adaptive threshold. It can be seen that many noise has been efficiently removed, but numerous noise caused by the oil stain and weld mark still remain. In order to reduce the amount of noise in images, we designed a convolutional kernel as following:

After the images are reversed and the convolution core is traversed, the noise in the images has been segmentally removed as shown in Figure 8b. Then the structures connected to the borders are suppressed through the morphological reconstruction and the holes in the binary images were filled through the mathematical morphology ^[13]. After completing the above-mentioned procedures, as shown in Figure 9b, almost all of the noise has been removed.

We also proposed an algorithm for the welding spot detection by using a region proposal method. Numerous papers have proposed methods for generating independent areas such as objectless ^[14], selective search ^[15], category independent object proposals ^[16] and Edge Boxes ^[17]. A novel method that can obtain a series of interconnected areas after traversing the entire image was designed. The method can generate several region proposals of interest to distinguish welding spots from other noise. As the area of welding spots is much larger than those of the noise points, targets can be separated from the noise by setting the threshold value of regions area. Firstly, the areas of region proposals were sorted in ascending order and the ratios between two adjacent values were calculated. These points are regarded as the welding spots if the ratio is less than 3. Then, the region proposals were plotted with bounding box in the binary images, as shown in Figure 9b. Finally, the edge of the image is extracted through the Canny edge detection with the algorithm proposed in Reference ^[18].

3.1.2.   The detection of the welding spots

In order to satisfy the real-time processing requirements in industrial environment, the computation time must be greatly decreased. We extracted the region proposals of welding spots in each image and detected the welding spots by the proposed AACD algorithm, as the edge points were only chosen in the bounding boxes. With this local detection method, the computation time is greatly decreased due to the neglect of interference, and the testing accuracy is apparently improved. We performed local and global detections 100 times, respectively. The average computation time is shown in Table 3. The difference between global and local detections is that the local detection uses a region proposal, while the former does not.

The comparison illustrates that the proposed method is efficient, and the speed has been greatly improved from seconds to milliseconds. The computation time significantly decreases compared with global detection, and the experimental results show that the local detection method can achieve satisfactory results in the industrial production, as shown in Figure 10.

The local AACD algorithm was applied to test 37 pictures of welding spots, including 54 welding spots. As shown in Table 4, the average time of welding spot detection is 0.089 s and the accuracy is 98.21%, which meets the requirements of production.

4.   Conclusion

An angle aided randomized Hough transform method for circle detection has been proposed in this paper. Its application experiment in welding spot detection illustrated that the proposed method can inspect the welding spots with higher accuracy and improved efficiency as well as satisfactory anti-interference ability. Moreover, the experimental results confirmed the effectiveness of the proposed region proposals method as well as its promising application in circle detection with high recognition accuracy and reduced processing time. One obvious advantage of the proposed method is that it uses the region proposal method for sampling edge points instead of the gradient of computing parameters, which means an extensive reduction in computational complexity and increase in detection accuracy. The results presented in this paper will be valuable for the development of general circle detection.

Through analysis of the experimental results, the detection efficiency of the proposed AACD algorithm can meet the requirements of industrial production. However, we found that much further improvement is also needed. As shown in Figure 11, the hole in the BIW was mistakenly identified as a welding spot. In recent years, deep learning ^[19,20] has received widespread attention from scholars and researchers. Therefore, our future work will focus on establishment of the database of BIW welding spots, and the welding spot detection based on the deep learning approach.

Acknowledgements

This work was supported in part by the National Nature Science Foundation of China (NSFC 61673163), Chang-Zhu-Tan National Indigenous Innovation Demonstration Zone Project (2017XK2102), Hunan Provincial Natural Science Foundation of China (2016JJ3045), and Hunan Key Laboratory of Intelligent Robot Technology in Electronic Manufacturing (IRT2018003).

Conflict of interest

The authors declare no conflict of interest in this paper.