Comparison of Object Region Segmentation Algorithms of PCB Defect Detection

2.1 Color space threshold segmentation algorithm

Histogram threshold segmentation algorithm is the most common segmentation algorithm. Significant gray difference exists between the object and background regions, and corresponds to different peaks in the gray distribution histogram, which is the theoretical basis of the algorithm. The threshold was selected between the peaks to segment the image into object and background regions. Although this method is intuitive and segments images with strong changes in brightness and darkness very well, it is sensitive to non-uniform color in the same region.

In the uniform color space, the color difference among all PCB image regions has obvious separability, as shown in Figure 1. Therefore, the threshold was set in the CIE L^*a^*b^* space and the pixels were classified in order to realize the object segmentation.

1.png

Figure 1. Distribution of PCB image pixels in the CIE L^*a^*b^* space

After calculating the components of L^*, a^* and b^*, corresponding to all pixels in the filtered image, they were mapped to the CIE L^*a^*b^* space, as shown in the following formula.

$RGB\left\{ f\left( x,y \right) \right\}\Rightarrow \left\{ \left( {{L}^{*}},{{a}^{*}},{{b}^{*}} \right) \right\}$                        (1)

The correspondence between the pixel $f(x, y)$ and the point (L^*a^*b^*) in the CIE L^*a^*b^* space was established. Although the pixels in the same region were far apart in the image, they concentrated in the CIE L^*a^*b^* space. However, due to color difference, the pixels in different regions were far apart in the space. After setting the threshold range of three dimensions $U_{L^*}, U_{a^*}$ and $U_{b^*}$, the spatial point set was divided into two categories, i.e. pixels in the object and background regions. The discriminant was as follows:

$T\left\{ \xi  \right\}=\left\{ \begin{matrix}   \begin{matrix}   A & {{\xi }_{{{L}^{*}}}}\in {{U}_{{{L}^{*}}}},{{\xi }_{{{a}^{*}}}}\in {{U}_{{{a}^{*}}}},{{\xi }_{{{b}^{*}}}}\in {{U}_{{{b}^{*}}}}  \\\end{matrix}  \\   \begin{matrix}   B\text{                                  } & other  \\\end{matrix}  \\\end{matrix} \right.$                    (2)

The points, with all three spatial components within the threshold range, were the object points, and the corresponding pixels were the object region pixels and labeled as category A points. The remaining points were background points, and the corresponding pixels were labeled as category B points.

The threshold range should be determined based on the object region pixel distribution of the PCB image in the CIE L^*a^*b^* space. After obtaining the mean point coordinates of spatial distribution $\left(\overline{L^*}, \overline{a^*}, \overline{b^*}\right)$ and the distribution variances in all dimensions $\sigma_{L^*}, \sigma_{a^*}$ and $\sigma_{b^*}$, the threshold range was determined according to the $\sigma$ principle, as shown in Formula (5). For image detection of PCBs in the same batch, the obtained threshold range was used as a fixed value.

$\left\{ \begin{matrix}   \overline{{{L}^{*}}}=\frac{\sum\limits_{i=1}^{n}{{{L}_{i}}^{*}}}{n}  \\   \overline{{{a}^{*}}}=\frac{\sum\limits_{i=1}^{n}{{{a}_{i}}^{*}}}{n}  \\   \overline{{{b}^{*}}}=\frac{\sum\limits_{i=1}^{n}{{{b}_{i}}^{*}}}{n}  \\\end{matrix} \right.$                      (3)

$\left\{ \begin{matrix}   {{\sigma }_{{{L}^{*}}}}=\sqrt{\frac{\sum\limits_{i=1}^{n}{{{\left( {{L}_{i}}^{*}-\overline{{{L}^{*}}} \right)}^{2}}}}{n-1}}  \\   {{\sigma }_{{{a}^{*}}}}=\sqrt{\frac{\sum\limits_{i=1}^{n}{{{\left( {{a}_{i}}^{*}-\overline{{{a}^{*}}} \right)}^{2}}}}{n-1}}  \\   {{\sigma }_{{{b}^{*}}}}=\sqrt{\frac{\sum\limits_{i=1}^{n}{{{\left( {{b}_{i}}^{*}-\overline{{{b}^{*}}} \right)}^{2}}}}{n-1}}  \\\end{matrix} \right.$                        (4)

$\left\{ \begin{matrix}   {{U}_{{{L}^{*}}}}=\left[ \overline{{{L}^{*}}}-6{{\sigma }_{{{L}^{*}}}},\overline{{{L}^{*}}}+6{{\sigma }_{{{L}^{*}}}} \right]  \\   {{U}_{{{a}^{*}}}}=\left[ \overline{{{a}^{*}}}-6{{\sigma }_{{{a}^{*}}}},\overline{{{a}^{*}}}+6{{\sigma }_{{{a}^{*}}}} \right]  \\   {{U}_{{{b}^{*}}}}=\left[ \overline{{{b}^{*}}}-6{{\sigma }_{{{b}^{*}}}},\overline{{{b}^{*}}}+6{{\sigma }_{{{b}^{*}}}} \right]  \\\end{matrix} \right.$                     (5)

To enhance the separability of pixels among regions, the image linear contrast was enhanced simply in the RGB (red, green and blue) space before segmentation, as shown in Formula (6).

${{f}_{E}}\left( \xi  \right)=\left\{ \begin{matrix}   \begin{matrix}   0 & \alpha f\left( \xi  \right)+\beta \prec 0  \\\end{matrix}  \\   \begin{matrix}   \alpha f\left( \xi  \right)+\beta  & 0\le \alpha f\left( \xi  \right)+\beta \le 255  \\\end{matrix}  \\   \begin{matrix}   255 & \alpha f\left( \xi  \right)+\beta \succ 255  \\\end{matrix}  \\\end{matrix} \right.$                      (6)

where, $f(\xi)$ is the R, G, and B components of the pixel $\xi$. The amplification coefficient α and the translation coefficient β were determined through experiment.

The color space threshold segmentation algorithm had a simple principle, a small amount of calculation, and fast execution speed. However, the threshold range process parameters were selected based on a large number of experiments. At the same time, the threshold selection lacked the adaptive ability and the algorithm had poor robustness.

2.2 Morphological edge detection segmentation algorithm

Edge detection of a grayscale image is generally realized by calculating the first or second derivative of the image. However, the image gradient is generally calculated in practical operation, by considering that the image does not meet the continuous derivable condition.

In the edge detection algorithm, the derivative or gradient information of the image is used to judge the edge, which leads to a contradiction between noise resistance and detection precision. In addition, the algorithm is highly complex.

The two basic operations of morphology are corrosion and expansion, which are the basis of many morphological treatments. The mathematical expressions of corrosion and expansion operations are shown in Formulas (7) and (8).

$A\Theta B=\left\{ \forall b\in B,\exists a\in A:x=a-b \right\}=\left\{ x|{{\left( B \right)}_{x}}\subseteq A \right\}$                       (7)

$A\oplus B=\left\{ \exists a\in A,b\in B:x=a+b \right\}=\left\{ x|\left[ {{\left( \overset{\wedge }{\mathop{B}}\, \right)}_{x}}\bigcap A \right]\ne \varnothing  \right\}$               (8)

where, A is the pixel set, B is the structuring element, $\widehat{B}$ is the complementary set of B, and $\varnothing$ is an empty set. Corrosion can be understood as the set of x that remains in A after B has successively translated x on A. Expansion can be understood as the set of all translations x of B on A, which satisfies the condition that the intersection between $\widehat{B}$ and A is not empty. Figure 2 is a schematic diagram of corrosion and expansion operations, with the 3×3 rectangle as the structuring element B.

2.png

Figure 2. Principle of corrosion and expansion operations

Expansion expands the region contour in the image, while corrosion reduces the region contour, leading to the following conclusion.

$A\Theta B\le A\le A\oplus B$                    (9)

The difference between the two was the edge contour of the image, which was defined as the gradient operator in morphology and was described below.

$Gra{{d}_{M}}=A\oplus B-A\Theta B$                      (10)

Brightness component map of the image in the CIE L^*a^*b^* space was first separated, and the image edge contour was obtained according to Formula (10), which segmented the object region. The morphological edge detection obtained clear edge, because differentiation and others were not needed to be calculated. The noise interference on the results was eliminated by changing the size of the structuring element. At the same time, the edge obtained by subtraction operation retained edge details very well. Therefore, the edge detection effects of PCB images were significantly better than that of the gradient operation-based edge detection algorithm. However, the edge detected by this method was greatly influenced by the shape and size of the structuring element, which may lead to "over-processed" defect edge details during corrosion and expansion operations due to the structuring element selection, resulting in a certain degree of information distortion and affecting the defect feature extraction.

2.3 K-means clustering segmentation algorithm

The color space threshold segmentation algorithm needs to be supported by prior knowledge, while the shape and size of the structuring element needs to be set according to the actual situation in the morphological edge segmentation algorithm. Due to human intervention, the segmentation results of these methods were influenced by subjective factors. However, the clustering means data self-organizing into several meaningful clusters using certain similarity measure, and is an unsupervised learning method. The entire process is completely driven by the data itself, without the information involvement of known clusters.

The K-means clustering algorithm is a partition-based clustering method, which aims to find K cluster centers c₁, c₂, …, c_k, and enable the quadratic sum of the distance between each data point x_i and its nearest cluster center c_v to be minimized [15].

PCB image pixels have good separability in the CIE L^*a^*b^* space, and the region types of the PCB image are definite, including wiring layer, solder mask, silk screen layer, pad, plated through hole and so on. The selection of K cluster centers is clear, when the PCB image is segmented using the K-means clustering algorithm.

Based on the above considerations, the K-means clustering algorithm was used to segment the PCB image. The specific steps were as follows:

1. After all pixels of the PCB image were mapped to the CIE L^*a^*b^* space to form the data point set $P=\left\{x_1, x_2, \cdots x_n\right\}$, the index relationships of coordinate positions between the data points and corresponding pixels in the image were established;

2. According to the situation in Figure 1, three initial cluster centers were selected, and labeled as c₁, c₂ and c₃;

3. After calculating the distance between each data point x_i and each cluster center, the data point was categorized into the cluster C_v of the nearest cluster center. The distance was calculated according to Formula (11), and the classification of clusters met the following conditions:

$\left\| \left. f\left( x,y \right)-f\left( m,n \right) \right\| \right.=\sqrt{{{\left( {{L}^{*}}_{x,y}-{{L}^{*}}_{m,n} \right)}^{2}}+{{\left( {{a}^{*}}_{x,y}-{{a}^{*}}_{m,n} \right)}^{2}}+{{\left( {{b}^{*}}_{x,y}-{{b}^{*}}_{m,n} \right)}^{2}}}$                       (11)

$\bigcup _{v=1,2,3}^{3}{{C}_{v}}=P$                    (12)

${{C}_{i}}\bigcap {{C}_{j}}=\varnothing \left( \begin{matrix}   i,j=1,2,3, & i\ne j  \\\end{matrix} \right)$                     (13)

4. Positions of cluster centers were updated based on the classification results. That is, the centers of all clusters were recalculated and used as new cluster centers $C_1{ }^{(k)}, C_2{ }^{(k)}$ and $C_3{ }^{(k)}$, with the upper right corner mark as the number of updates. The center position was calculated using the means of all data point coordinates in each cluster;

5. The quadratic sum D of the distance between each data point and its nearest cluster center was calculated using the following formula:

$D={{\sum\limits_{i=1}^{n}{\left( {{\min }_{v=1,2,3}}\left\| \left. {{x}_{i}}-{{c}_{v}} \right\| \right. \right)}}^{2}}$                     (14)

where, $\left\|x_i-c_v\right\|$ is calculated according to Formula (11);

6. It was determined whether the D value converged. If it did not converge, the execution should be returned to Step 3 and continue. If the D value converged, the calculation was terminated, and all data points were classified according to the latest cluster centers to obtain the final clustering results. According to the index relationships between data points and corresponding pixel coordinates, the pixels were classified and labeled, thus dividing the PCB image into three different regions, namely, solder mask region, wiring layer region, and pad region.

Selection of initial cluster centers in the above Step 2 was crucial, because different choices led to completely different results and affected the convergence speed of D. To avoid the clustering results falling into the local optimal solution, the initial cluster centers were selected using the K-means++ algorithm, which aimed to make the distance among the initial cluster centers as far as possible. The specific selection rules were as follows:

1. A data point was randomly selected as the center;

2. The distance d(x_i) between all points and their nearest center points was calculated, and saved in an array to calculate the sum of all distances sum;

3. The next center point was calculated using the reference weight. After selecting a random number γ within the range [0,sum], each distance d(x_i) in the array was subtracted successively by γ until γ was less than or equal to 0. At this time, the corresponding data point was the next center point, which effectively ensured that larger data points in d(x_i) had a high probability of being selected as the new center point;

4. Steps 2 and 3 were repeated until K center points were selected;

5. These K center points were used as the initial cluster centers, and then the standard K-means clustering algorithm was operated.

The K-means clustering segmentation was used for the PCB image using the above method, which obtained three cluster centers, i.e., the distribution centers of pixels in different regions in the CIE L^*a^*b^* space. Due to different materials, the brightness components of different regions in the CIE L^*a^*b^* space in the PCB images always maintained certain size relationships. Specifically, the pad region was the brightest, which was followed by the wiring layer region, and then the solder mask. After sorting the three cluster centers according to their brightness components, the wiring layer and pad regions, in which the algorithm was interested, were extracted, with the rest as the background region.

As an unsupervised learning mechanism, the segmentation results of the K-means clustering algorithm were more objective and best reflected the true boundary information among regions. Meanwhile, the algorithm had significantly better robustness than the color space threshold segmentation algorithm, because its calculation results were completely controlled by the data itself.

Combined with the characteristics of PCB color images, this study analyzed the limitations of RGB color model on image processing, and chose to preprocess the images in the CIE L^*a^*b^* color space. Bilateral filtering algorithm was used to reduce the image noise, which effectively protected the image edge details. The K-means clustering algorithm was chosen to accurately segment the wiring layer and pad regions in the image to reduce the subsequent amount of calculation, after comparing the three segmentation algorithms, namely, color space threshold segmentation, morphological edge detection segmentation, and K-means clustering segmentation. The experiments showed that the K-means clustering segmentation algorithm obtained the optimal segmentation results of PCB images, which classified and labeled all pixels according to the clustering results, extracted regions of interest as the research objects of subsequent defect feature extraction and detection, thus reducing the amount of calculation. However, the image itself was still a color image, i.e., all pixels still retained complete color information. Therefore, the image was used by the defect feature extraction algorithm, which effectively segmented regions of interest, such as the wiring layer and pad regions, thus ensuring that high quality images were used as the input of the defect detection algorithm.