1 Introduction
With the increasing automation of industrial production, the demand for automated workpiece inspection is also growing. Machine vision measurement technology, due to its advantages of non-contact operation, high precision, and high speed, is widely used in workpiece measurement on production lines. Because of the inherent rigidity and regularity of workpieces, the contour of the workpiece image can effectively reflect the characteristics of the target object. However, workpiece stacking and occlusion in industrial settings can lead to missing or broken workpiece contours. Therefore, the inspection of local workpiece contours has become a research hotspot.
In 1996, Ianni et al. described the matching problem of partial contours on template contours as a combinatorial optimization problem and solved it using an improved search algorithm based on simulated annealing and genetic algorithms. Subsequently, van Kaick et al. proposed a local shape matching method based on ant colony optimization, which solved the combinatorial optimization problem of local contour matching to obtain the probabilistically optimal path and the best matching result. Since then, various local contour matching methods utilizing shape feature descriptors have been proposed. These mainly include shape context descriptors based on contour point region distribution histograms, inner-distance shape context descriptors based on in-contour distances, and exact height function descriptors that integrate global and local contour information. Wang Yanni et al., in their work on building contour recognition, proposed a local contour recognition algorithm based on various vector descriptions and local contour features. This algorithm, based on the vector information of different buildings, formulated a similarity criterion and mapping function for arbitrary shape contour matching, effectively solving the local contour matching problem. Huang Hao et al. proposed using shape descriptors to convert contours into signal data, training a backpropagation neural network, and successfully recognizing complex pipeline network images. Another paper utilizes the characteristic that most local contours of objects are open contours to propose a feature descriptor based on the intra-contour distance. This descriptor is rotation, scale, and translation invariant, and also possesses good affine invariance. Yang et al. proposed the Triangular Centroid Distances (TCDs) operator in 2018. The TCDs operator exhibits reliable invariance to translation, rotation, scaling, and significant shape deformation. Sun Guodong et al. fused the TCDs descriptor and the EHF1 (Exact Height Function 1) descriptor, leveraging the advantages of the EHF1 operator in fusing global and local contour information to propose a new TCDs descriptor. However, to effectively describe contours, the TCDs descriptor requires dense sampling points at the contour. When matching with a template contour, the local contour slides sequentially on the template contour according to the sampling point order, and similarity calculations are performed. This approach suffers from excessive computation time during algorithm matching and the invariance of sampling point starting points. To address these issues, this paper preliminarily divides the template contour based on the corner characteristics of the workpiece contour, using the number of corner points to obtain potential contour segments in the template image. Then, sampling points are reselected based on the corner point positions to resolve the invariance of sampling point starting points. Finally, the local contour is matched with the potential contours of the template to complete the local contour recognition. Results show that, with the same number of sampling points, the proposed algorithm achieves a higher recognition rate than traditional TCDs algorithms, while reducing computation time by 86%.
2. Contour Corner Extraction
Traditional methods for extracting corner points of contours involve extracting the curvature of each point on the contour. Since corner points are typically points with extremely high curvature values, extracting these extreme curvature points can be used to extract the corner points of the contour image. This paper employs a method of constructing front and rear triangles around each contour point to calculate the curvature value of each point on the contour curve. Specifically, each point on the contour is paired with two points at a certain distance before and after it to form a triangle. The angle of the contour point within each front and rear triangle is then calculated as the curvature value of that point. This method of calculating curvature values is time-efficient and can significantly smooth even small protrusions in the contour. The principle of this algorithm is shown in Figure 1.
As shown in Figure 1, for a sequence of contours, each point P on the sequence can form ΔP-PP+ as shown in Figure 1. If we denote the distance to PP as b, the distance to PP+ as a, and the distance to P-P+ as c, then the magnitude α of ∠P-PP+ can represent the curvature of point P. Since the cosine of the angle monotonically decreases in the range [0, 180], it can be used to represent the magnitude of ∠P-PP+.
After obtaining the triangle formed by each contour point, the curvature value sequence of the local contour as shown in Figure 2 can be obtained. The local maxima of the curvature value sequence are the corner points of the contour.
Figure 1. Schematic diagram of contour point curvature.
3. Triangle Inner Spacing Descriptor
The TCDs descriptor, proposed in 2018, can effectively describe two-dimensional shapes. The authors also proposed a matching method between local contours and template contours, the principle of which is shown in Figure 3.
First, assuming the red segment in Figure 3 is a local contour segment of the overall contour, denoted as contour P, we calculate the centroid G of contour P. We then uniformly select N sampling points on P. For each sampling point Pi, it can form N-1 triangles with other sampling points P (jj ∈ [1,N] j ≠ i) and centroid G, denoted as ΔPiPPj. Next, we calculate the centroid of each ΔPiPPj, denoted as gij. Then, for each sampling point Pi, we calculate the Euclidean distance between Pi and gij, obtaining a set of feature vectors of length N-1. This feature vector is the TCDs feature vector of sampling point Pi, denoted as li. Finally, we extract the TCDs feature vectors of all sampling points on contour P according to the order of the contour points, denoted as L=(l1,…,ln). At this point, the TCDs descriptor extraction of contour P is complete. For the matching problem between local contours and template contours, firstly, based on the length of contour P, a contour segment of the same length is taken on the template contour; then, the contour segment is slid on the template contour, and the TCDs feature matrix of the contour segment is calculated after each slid, and the similarity between the feature matrix and L is calculated; finally, the contour segment with the highest similarity in the template contour is selected as the matching result.
Figure 2. Contour point curvature value sequence
4. Triangle Inner Spacing Descriptor with Fused Corner Information
Generally, TCD descriptor extraction samples points uniformly across the contour segment. To accurately describe the contour, the spacing between sampling points cannot be too large. However, this sampling method leads to excessive sliding of the template contour segment during template contour matching, resulting in a large computational load. Furthermore, changes in the starting point of local contour sampling points during TCD descriptor calculation cause changes in the feature matrix. Therefore, a Discrete Fourier Transform is typically performed on each row of the extracted feature matrix, ignoring the phase information after the Fourier Transform and using only the magnitude of the coefficients to ensure the invariance of the starting point of the descriptor. However, this increases the extraction time of the TCD descriptor, and the invariance of the starting point is mainly used for matching two complete closed shapes, making it less practical for matching local contours.
(1)
Figure 3. Schematic diagram of TCDs algorithm
Figure 4 Sampling point distribution
Figure 5. Partial contour of the workpiece
This paper proposes to use corner features to filter template contour segments, then use corner coordinates to lock sampling points, and then extract TCDs feature matrices from local contours, which reduces the amount of computation and computation steps. The specific method is as follows.
First, for a local contour of length n, let it be denoted as P={pi=(xi， yi), i=1，2， …，n}, where (xi，yi) are the coordinates of the contour points in the two-dimensional image. Then, according to formula (1), corner points are extracted from P. Assuming that contour P has N corner points, let the sequence position of each corner point in the contour sequence P be denoted as kj, j ∈ [1,N]. Then, the corner point Pkj can divide the contour into N+1 segments, and let the contour P={p1…pk1…pkj…pkn…pn}.
Using corner points to segment the contour, the contour segments exhibit smooth and stable structural characteristics. Therefore, uniformly sampling points are taken from the contour segments between corner points to effectively reflect the overall contour features. As shown in formula (2), each of the N+1 contour segments is uniformly divided into S parts to obtain the sampling points of the entire contour, denoted as L. The distribution of sampling points is shown in Figure 4.
(2)
Then, the TCDs feature matrix of contour P is obtained based on the sampling point set L. First, the centroid G(xG, yG) of contour P is extracted. To simplify the calculation, the coordinates of the sampling points are used to calculate the centroid. The calculation formula is as follows:
(3)
For each sampling point li, it can form n-1 triangles with the centroid G and the remaining n-1 sampling points. Let the centroid of these n-1 triangles be gij.
Figure 6. Template outline suspected outline segment
The distance between sampling point li and gij in the image is the contour point feature of point li at that location, denoted as , and the calculation formula is as follows:
(4)
For the entire contour P, a feature matrix of size (n - 1) × n can be extracted, denoted as TCDsP.
(5)
To obtain the scaling invariance of the contour descriptor, each row of the TCDsP matrix is divided by the maximum value of that row, as shown in formula (6):
Figure 7 Special contour segments
(6)
At this point, the extraction of the TCDs feature matrix is basically complete. Subsequently, suspected contour segments are extracted from the template contour based on the corner information of the local contours. Since the descriptor algorithm in this paper simplifies direction invariance, the direction of the local contours must be determined from the outset.
As shown in Figure 5, for the local contour of an image, if A is the starting point, the traversal direction of the contour sequence is counterclockwise; if B is the starting point, the traversal direction of the contour sequence is clockwise. It is evident that different starting points lead to different contour traversal directions. To determine the sequence direction of the local contour, we can first consider the local contour as a closed image and calculate the line integral of the contour points with respect to their two-dimensional coordinates in the direction of A → B → A or B → A → B. If the obtained value is positive, the contour direction is counterclockwise; if the obtained value is negative, the contour direction is clockwise. To save computation time, the algorithm in this paper does not calculate all contour points, but only the corner points of the contour. Let the sequence J = [ji = (xi, yi), i = 1, 2, ..., n], where j1 and jn represent the starting and ending points of the local contour, respectively, and the other points are the corner points of the local contour. (xi, yi) are the two-dimensional coordinates of the corresponding corner point ji in the image. Let the parameter F be:
(7)
If F > 0, the traversal direction of the local contour is counterclockwise; if F < 0, the traversal direction of the local contour is clockwise; if F = 0, it means that the local contour is a straight line.
After obtaining the traversal direction of the local contour, a suspected contour segment can be generated on the template contour according to the direction of the local contour. Let the template contour be D, the number of corner points be M, the local contour be P, and the number of corner points be N. Then, obviously, N ≤ M. In this way, the template contour can be divided into M groups, each group containing a suspected contour segment with N corner points. The local contour shown in Figure 5 has 4 corner points. Let the distance between the contour start point A and the first corner point be L1, and the distance between the contour end point B and the last corner point be L2. Select any corner point on the template contour as the starting point, and according to the traversal direction determined by formula (6), select a contour segment containing 4 corner points on the template contour in sequence. At the first corner point and the last corner point of the contour segment, extend the template contour by distances L1 and L2 respectively to obtain a suspected contour segment of the template contour. Then, move the starting corner point in sequence according to the determined traversal direction to obtain the remaining suspected contour segments, forming a set of suspected contour segments of the template, as shown in Figure 6.
Figure 8 Matching results of similar parts
The TCDs feature matrix of the suspected contour segment set is extracted according to the method described above, and the difference degree is calculated with the TCDs feature matrix of the local contour P. The contour segment with the smallest difference degree is the matching result between the local contour P and the template contour.
After extracting the suspected contours of the template, a special case needs to be considered: when the L1 and L2 of a local contour are too long, the length of some suspected contour segments of the template will exceed the length of the entire template contour. As shown in Figure 7, these suspected contour segments are obviously not the most similar. To save computation time, this paper directly calculates the length of the suspected contour segments. If the length of a suspected contour segment exceeds the length of the entire template contour, it can be directly removed.
Figure 9 Algorithm Flowchart
Since the sampling directions of contour P and template contours have been unified, and the positions of the sampling points have been locked through corner points, the size and direction of the TCDs feature matrix of contour P are consistent with those of each suspected contour segment of the template. Therefore, by directly calculating the cosine similarity of the feature vectors of each sampling point in the TCDs feature matrix of each contour segment in sequence, and then taking the average of these cosine similarities, the similarity of the TCDs feature matrices of the two contour segments can be obtained. Let the number of sampling points of contour P be n, then the TCDs feature matrix of contour P is: TCDsP=[TCDsp1…TCDspn]. Let contour C be a suspected contour segment of contour P, and the TCDs feature matrix of contour C is: TCDsC=[TCDsc1…TCDscn]. Where TCDspi and TCDsci are one-dimensional feature vectors of length n-1. The similarity Dist(P,C) between the two is:
(8)
From formula (8), we can see that the range of Dist(P,C) is [0, 1], where the closer the value is to 0, the better the match, and the closer it is to 1, the worse the match. Although TCDs descriptors have good scale invariance, there are many similar shapes in the actual workpiece inspection process. Therefore, it will be difficult to distinguish workpieces of different sizes using TCDs descriptors, as shown in Figure 8.
Figure 8(a) shows the target contour segment highlighted in red, while Figures 8(b) and 8(a) show the matching results of two template contours with similar shapes but different sizes. Figure 8(b) shows the correct matching result, but the target contour segment is also very similar to the matching result in Figure 8(c). To correctly distinguish workpieces of different sizes, this paper modifies the calculation formula for the two contours based on the length characteristics of the contours. Let the length of contour P be lP and the length of contour C be lC, then the modified contour similarity is Dis(tP,C):
(9)
Here, δ is the control coefficient for length difference, mainly to control the impact of length difference on contour similarity. Generally, the value of δ is in the range of [0, 1], mainly reflecting the priority of shape contour similarity. After multiple experiments, the experimental results are most ideal when δ is 0.1. The algorithm flow of this paper is shown in Figure 9.
5. Experimental Results
This paper verifies the performance of the detection algorithm from the aspects of detection speed and detection accuracy. First, six different shapes and sizes of workpieces are selected, and 11 contour images of each workpiece are taken from different angles and perspectives. Six local contour segments of the workpiece are randomly selected from each workpiece image, and a total of 600 local contour samples of the workpiece are extracted. For each workpiece, three images from different perspectives are used as templates, and the contour segment with the closest similarity value among the three templates is taken as the template matching result. The specific process is shown in Figure 10.
Figure 10 Matching Flowchart
Figure 11 Matching results of local workpiece contours
Figure 11 shows the experimental matching results. In Figure 11, the contours highlighted in red in the first column represent the matching results, and the green boxes indicate the workpiece contours most similar to the one to be detected. For the partial contours to be detected, even if they do not correspond to the correct workpiece, the most similar suspected contour segment can be found in the corresponding workpiece contour, which well demonstrates the sensitivity of TCDs descriptors to shape. It is evident that the algorithm in this paper can also correctly identify local contours of workpieces that are similar in shape but different in size.
Figure 12 shows the matching results of the algorithm in this paper on stacked workpiece images. Different colors represent different recognition results. For example, if the workpiece outline is marked in purple, it means that the workpiece is recognized as the template workpiece below which is purple, and the matching outline segment and similarity are given on the template workpiece.
When the stacking situation is complex, as shown in Figure 13, the outline segments highlighted in red represent areas where the workpieces are severely stacked. The outlines of the stacked objects overlap, altering the corner positions and number of local outline segments, leading to situations where these segments cannot be identified or are misidentified. In areas where the influence of the outlines is not severe, the effect of overlapping outlines is generally ignored, and overlapping outline segments are treated as independent target outline segments for matching. The matching results are shown in Figure 14. However, for images where the outlines of stacked objects are severely affected, the algorithm in this paper struggles to identify the extracted local outline segments, which is a limitation of our proposed algorithm.
As can be seen from formula (2), for a local contour to be detected, the sampling points of the algorithm in this paper are selected by dividing the contour segment into corner points and then sampling evenly in the corner point segment. This sampling method can make full use of the smoothness of the contour segment between corner points, and a small number of points can also describe the contour well. The influence of different sampling points in the corner contour segment on the recognition accuracy is shown in Figure 15.
As shown in Figure 15, the recognition rate reaches a high value when the number of sampling points between each corner is 6, and the number of sampling points is the minimum. Therefore, the number of sampling points for the contour in this paper's algorithm is (n + 1) × 6 (n is the number of corner points on the local contour).
Table 1 shows the matching time of different local contour matching algorithms for a single template.
Figure 12 Matching results of local workpiece contours
Figure 13. Image of complex stacked workpieces
Figure 14. Matching results of complex stacked workpieces
Figure 15. The effect of the number of sampling points on accuracy.
Since the number of sampling points in our algorithm is related to the number of corner points within the contour, while traditional TCDs algorithms use a fixed number of sampling points, the number of sampling points in the TCDs algorithm is limited to (n + 1) × 6 to ensure fairness in the algorithm comparison. As shown in Table 1, compared with the traditional TCDs contour matching method, the computational efficiency of our algorithm is significantly improved.
To demonstrate the recognition accuracy of the proposed algorithm, the recognition rates of the traditional TCDs matching algorithm, the Shape Context matching algorithm, the Back Propagation (BP) neural network algorithm based on Shape Context descriptors, and the proposed algorithm were calculated under different occlusion ratios. As mentioned above, since the proposed algorithm determines the number of sampling points based on the number of corner points of the target's local contour, the TCDs matching algorithm and the SC (Shape Context) matching algorithm both use (n + 1) × 6 sampling points, while the SC + BP neural network algorithm uses a fixed number of sampling points for network training and recognition, with a size similar to that of the proposed algorithm. The experimental comparison results are shown in Table 2. As can be seen from Table 2,
The algorithm presented in this paper outperforms the three algorithms mentioned above in recognition rates across different local contour proportions. When the number of sampling points is small, the algorithm in this paper significantly improves the accuracy of contour description by using a sampling method based on the contour corner positions.
6. Conclusion
This paper addresses the problem of only being able to extract partial contours when a workpiece is occluded, proposing an improved local contour matching algorithm based on TCDs descriptors. First, the corner information of the local contour is used to find corresponding suspected contours on the template contour, significantly reducing the computation time of sliding matching in traditional TCDs algorithms. Second, based on the corner distribution of the contour, sampling is performed uniformly between corner points of the contour segment, fully utilizing the smoothness of the contour segment between corner points and greatly reducing the number of sampling points. Furthermore, this paper simplifies the steps of solving the invariance of the starting point in the traditional TCDs algorithm. Finally, by unifying the traversal direction of the local contour and the template contour, the consistency of the direction of suspected contours in both is ensured. By comparing the similarity of suspected contour segments between the workpiece's local contour and the template contour, the matching results of the local contour under different template contours are obtained, achieving target matching of the local workpiece contour. Experimental results show that the proposed algorithm has a significant improvement in time efficiency compared to the traditional TCDs algorithm. Under different local contour ratios and with a small number of samples, the proposed algorithm outperforms the traditional algorithm in terms of local contour recognition rate. When the proportion of local contours is 60%, the recognition rate of the algorithm in this paper is still higher than 90%. However, the algorithm also has shortcomings: when the contour lines of stacked objects have a significant impact, the algorithm has difficulty recognizing the local contour because the corner information of the local contour segment is destroyed.
Table 1 Algorithm Computation Time
Table 2 Recognition rates for different occlusion ratios
Authors: Shen Zheng1, Hu Chao2
1. School of Electrical Engineering and Automation, Jiangxi University of Science and Technology
2. Reprinted from "Integrated Technology" by the School of Information Science and Engineering, Zhejiang University Ningbo Institute of Technology.
