# Defect Contour Detection of Complex Structural Chips

Authors: Bin Lin; Jie Wang; Xia Yang; Zhangdong Tang; Xuan Li; Cenlin Duan; Xiaohu Zhang
Journal: Mathematical Problems in Engineering
 (2021)

---

## Abstract

In the manufacture of chips, it is important to detect defects to assess whether the chip is potentially damageable that could cause unnecessary cost. Most assessment rules are set in light of characteristics determined by defect contours, such as area and range. However, conventional image process methods seldom show a satisfactory performance on chips with complex structures because they are difficult to distinguish defect contours from edges of structures. To solve this issue, this study proposes a method based on region segmentation search. The positions of structures in the image are calculated by edge matching to obtain the number of structure layers in each pixel. Regions whose pixels have the same number are divided into subregions which are coded by the two-pass algorithm. The edges in each subregion are then extracted by the Canny operator to construct edge information of the whole image. Interpolation is used to correct incomplete defect edges according to their endpoints. The remaining interference contours are eliminated on the basis of their shapes. A study of a certain kind of chips is presented. Different illumination situations were simulated to verify the robustness of the proposed method. Most bubbles in the images were detected successfully with their contours coded accurately. Because of this, more than 92% of assessment results of chips were identical to the ones in reality engineering, which proves that the method proposed by this study can efficiently detect the defect contours and improve the ability obviously relative to the current approaches.


---

## Body

## 1. Introduction

With the rapid advancement of chip manufacturing, structures of chips are in the direction of increasing complexity and elaboration. Therefore, automated visual inspection (AVI) has received great attention in chip detection due to its nondestructiveness and reliability [1]. Among all the characteristics of defects, edge detection is one of the most important aspects because it is the basis of many quality assessments. However, the edges of defects are blurred by noise in the image. Moreover, there is no definite criterion to distinguish the edges of defects from those of structures in the image, which results in false detection.In recent decades, many traditional approaches such as projection and filtering have been applied in the chip inspection field. Teoh et al. [2] developed five separate algorithms to deal with, namely, missing components, misalignment, wrong orientation of IC chips, wrong parts, and poor solder joints on surface mount PCBs. Gallegos et al. [3] detected the presence or absence of surface-mounted devices (SMDs) in the inspection of printed circuit boards based on linear projection and other processing. Lin [4] used wavelet characteristic to inspect ripple defects in the surface barrier layer (SBL) chips of ceramic capacitors and used discrete cosine transform (DCT) to restore image for inspection of tiny pinhole defects in randomly textured surfaces of surface barrier layer (SBL) chips. Wu et al. [5] proposed a two-stage inspection process which analyzed the features of the components under three colors (red, greed, and blue) structure light source for surface mounted components after they have been placed in wet solder paste on a printed circuit board (PCB). And the next year (2010), they gave out another way which combined an adaptive segmentation method, the sliding location window algorithm, and the Bayes classifier to solve this problem. Wu et al. [6] calculated the geometrical parameters of the chip components by means of vision-based methods such as the maximum external rectangle method, the Canny operator, the Zernike moment operator, and the fast Fourier transform (FFT). Huang et al. [7] used an improved Canny operator to inspect the IC chip pin. Zheng et al. [8] also used the Canny operator to inspect the appearance of QFP chip lead. Chen and Perng [9] combined many digital image processing including normalization, shrinking, segmenting, and Fourier-based image restoration and defect identification on the basis of characteristics of statistical textures of the molding surface. Nurhadiyatna et al. [10] proposed a method which consisted of K-means clustering, Gabor filter, and Canny edge filter to detect surface defects on chip pad area. However, most of these research studies focused on detecting the existence of different types of defects rather than confirming the contours of defects. Furthermore, the studies on contour detection could hardly be applied in complex structural chips for two reasons: first, these methods strongly depend on threshold setting, which makes blurred edge detection an open technical challenge. A low threshold may cause false detection while a high one may lead to missed detection of weak edges. Second, the edges abstracted in the whole image belong to not only defects but also structures, which sometimes are almost indistinguishable.In addition to traditional methods, some studies based on machine learning and hybrid method have been applied in this field. Chen and Liu [11] adopted a neural network architecture named adaptive resonance theory network 1 (ART1) to recognize defect spatial patterns. The neural network and derived methods were also applied in semiconductor wafer postsawing inspection [12]and light-emitting diode (LED) inspection [13–16]. Wang [17] integrated spatial statistics, kernel-based eigendecomposition, and support vector clustering to extract and separate four kinds of composite defect patterns. Li [18] proposed a method based on wavelet transform, rough set theory, and support vector machine to classify copper clad laminate defects. Xie et al. [19] developed a scheme to simulate datasets of these 4 patterns including rings, semicircles, scratches, and clusters for classifiers’ training and testing. After that, defects in real optical images were resized and detected based on image processing operations and the trained support vector machine. Lin et al. [20] proposed the application of convolutional neural network- (CNN-) based defect inspector named LEDNet for LED chip defect inspection and achieved a low inaccuracy and localized exact defect regions as well. The central issue of learning-based methods can be distilled to the following: first, traditional networks and SVM cannot realize the defect localization and edge detection but the classification of defects. Second, unfixed shapes of defects increase the cost of time and energy on image annotation excessively. Third, many digital image processes before classification such as image segmentation, feature extraction, and description artificially will bring the same problems with traditional methods. Fourth, the universality of trained models is so poor that new models should be designed and trained for different types or batches of productions.In order to address these problems, it is necessary to derive a more effective and efficient way to detect the defect edge of complex structural chips. This paper proposes a method based on multiregion segmentation and edge correction as shown in Figure1. As all structures of a chip are determined, the contours of them can be regarded as priori information to locate their position, which is the basis of image segmentation. An edge correction technique is used to modify the incomplete edges. The remaining fault edges caused by noise and structure are removed according to their shape feature while the right ones are preserved completely.Figure 1
Flowchat of the proposed method.The remainder of this paper is organized as follows. Section2 presents the proposed model that combines region segmentation search and edge correction for defect contour detection. Section 3 utilizes a kind of chip to demonstrate the capability of the proposed method. Section 4 presents the conclusion and directions for future work.


## 2. Research Method

As the chip contains many various structures inside, there are many overlap regions with different gray levels in the image, which are the basis to divide a chip image into different regions which change related to the position of structures. WE propose a novel region segmentation method using a contour matching method and a two-pass algorithm.


### 2.1. Region Segmentation Search Methodology

#### 2.1.1. Structural Location Based on Contour Matching

Although all the structures certainly appear in the chip image, the image brightness is irregular and structures may occlude mutually. Therefore, this paper used a contour matching method based on the Canny operator to solve these two problems [21].(1) Template Edge Model Building. Each structure has a respective image as a template whose edges are used to build its model. The models are built by following the below-mentioned steps:Step 1. Image graying: each Canny is only used to process the gray image. Thus, the template image should be grayed if it is a color image. Taking an RGB color image as an example, the formula used for graying is as follows:(1)Igrayx,y=0.299∗Iredx,y+0.587∗Igreenx,y+0.114∗Ibluex,y,whereIgrayx,y is the gray image value, Iredx,y is the red channel value, Igreenx,y is the green channel value, and Ibluex,y is the blue channel value.Step 2. Image smoothing: each image is convoluted by Gauss filter to eliminate noise.(2)Ix,y=Gx,y∗fx,y,Gx,y=12πσ2exp−x2+y22σ2,whereIx,y is the filtered image, fx,y is the original image, and Gx,y is the two-dimensional Gauss function.Step 3. Gradient calculation: gradient magnitudes and directions of an image are determined by Sobel operator:(3)Pxx,y=fx+1,y−1+2fx+1,y+fx+1,y+1−fx−1,y−1−2fx−1,y−fx−1,y+1,Pyx,y=fx−1,y−1+2fx,y−1+fx+1,y−1−fx−1,y+1−2fx,y+1−fx+1,y−1,Mx,y=Pxx,y2+Pyx,y2,θx,y=arctanPyx,yPxx,y.Step 4. Nonmaximum suppression: in order to ensure the accuracy of edge location, the gradient magnitude at each edge pixel should be compared with those at its two neighbors in the gradient direction. If it is larger, the pixel will be marked as a maximum edge point; otherwise, it will be marked as the background.Step 5. Double threshold determination and edge connection: two thresholds Thigh and Tlow are required to classify the gradients of the remaining pixels that have not been suppressed. Thigh is usually set twice as high as Tlow. The gradients higher than Thigh are definitely strong edge points, while those lower than Tlow are definitely nonedge points. The weak edges which are higher than Tlow but lower than Thigh are determined depending on whether there is more than one strong edge point in its neighborhood.Step 6. Model building: because the model image may have some parts without any edge information, the coordinates of the confirmed points need to be rearranged to reflect the start point as the center of gravity:(4)xpi=xpi−xgravity,ypi=ypi−ygravity,xgravity=∑i=1Nxpin,ygravity=∑i=1Nypin,wherexpi is the x-coordinate of the ith point, ypi is the y-coordinate of the ith point, xGrowity is the x-coordinate of gravity, yGrowity is the y-coordinate of gravity, and n is the total number of edge points.Step 7. Model storage: the coordinates along with their gradient magnitude and direction information are saved as the template models.(2) Model Matching. The template models built are applied to search the structures in the chip image. Each model consists of a set of points PiT=xiT,yiT, gradients in X and Y directions GiT=GxiT,GyiT, and directions DiTxi,yi, where i=1,2,…,n, in which n is the number of elements in the Template (T) dataset. The gradient magnitudes need to be normalized for reducing the influence of illumination.The gradient magnitudes and the direction of the search image (i.e., the chip image) are also calculated by the Canny operator, which are denoted byGu,vS=Gxu,vS,Gyuu,vS and Du,vSu,v, where u,v is the coordinate in the image, u=1,2,…,p, in which p is the number of rows in the search image, and v=1,2,…,q, in which q is the number of columns in the search image.In the matching process, the template model is shifted in the search image to compare with the subimage using a similarity evaluation:(5)Su,v=12Sdiru,v+Smagu,v,Sdiru,v=∑i=1nDTxi,yi⋅Dsu+xi,v+yi∑i=1nDTxi,yi2⋅∑i=1nDsu+xi,v+yi2,Smagu,y=1n∑i=1nGxiT⋅Gxu+xi,v+yiS+GyiT⋅Gyu+xi,v+yiSGxiT2+GyiT2⋅Gxu+xi,v+yiS2+Gu+xi,v+yi2,where Su,v is the score of similarity at point u,v in the search image, Sdiru,v is the score of direction similarity, and Smagu,v is the score of magnitude similarity. The score is related to the portion of the structure visible in the search image. If the template model and the search image match perfectly, the score is 1; if the structure is not present in the search image, the score is 0.In the process of calculatingSu,v at a point, the partial score Spu,v (i.e., equation (6)) is introduced to improve the algorithm efficiency. If Spu,v is lower than a minimum score (Smin), the calculation of Su,v will be stopped and the matching evaluation of the next point will be started.(6)Spu,v=1m∑i=1mGxiT⋅Gxu+xi,v+yiS+GyiT⋅Gyu+xi,v+yiSGxiT2+GyiT2⋅Gxu+xi,v+yiS2+Gu+xi,v+yi2,where m is the number of points used for match. It is evident that Spu,v is smaller or equal to 1, so the first restriction is Sm>Smin−1+m/n.If there is a perfect match between the template and the model, the partial score at any point should be greater than the minimum scoreSmin, i.e., m/nSpu,v≥Smin. However, there are still some situations where the missing part of the object is checked first, the partial sum will be low that the structure in the chip image may not be considered as a match. So a new criterion which takes into account both restrictions is set that the evaluation of the partial score will be stopped at(7)Sm<minSmin−1+1−g⋅Smin1−g⋅mn,Smin⋅mn,where g is a greediness parameter which determines the fraction of the second restriction.This similarity measure combines several insights: the similarity measure is invariant to nonlinear illumination changes because all gradient vectors are normalized. More importantly, this similarity measure is robust when the object is partially visible or mixed with other objects.


#### 2.1.2. Automatic Region Segmentation

After determining the position of each structure in the image, it is necessary to segment the image into several subregions according to the locations and the overlap relationships of the structures. In this paper, the two-pass algorithm is used to encode each overlap region class, for automatic segmentation of chip image.(1) Two-Pass Algorithms. A connected region consists of adjacent pixels with the same pixel value. Therefore, the connected region can be found in the image by these two conditions. For each connected region found, a unique label is given to distinguish the other connected regions. In this paper, a two-pass connected domain labelling algorithm for 8 neighborhoods is used [22]. As shown in Figure 2, the specific steps are as follows:Step 1. First pass: the image is scanned from left to right and from top to bottom. If the point scanned is the effective pixel (nonzero), the situation of the leftmost, upper left, top-right points in the eight neighborhoods of this point will be judged. If none of them are effective points, the point is the beginning of a new label.Step 2. Second pass: in the first pass, the points in the same connected region may have different labels. Therefore, the image should be scanned in the same way to merge these labels as the following rules:(1)
If the leftmost point and the upper right point of a labelled point are effective points, the label of all three points will be set to the smaller label of them(2)
If the upper left point and the upper right point of a labelled point are effective points, the label of all three points will be set to the smaller label of them(3)
Otherwise, the label of point will be set to one of four in the order of leftmost, upper left, topmost, and upper rightThe points with the same label form a cluster.Figure 2
Two-pass algorithm illustration: (a) original image; (b) first pass; (c) second pass.
(a)(b)(c)(2) Region Segmentation. According to the positions of the structures in the image, the number of layers of structures on each pixel is determined. The pixels with the same amount of layers are regarded as an overlap region class. A chip image can be separated into target (class) regions and nontarget regions. At the same time, the target region contains several connected regions which are regarded as subregion of this class. A unique label is given to each subregion. The steps are as follows:Step 1. Each pixel is determined which class it belongs toStep 2. For each class, the pixels of this class are set to 1, and the others are set to 0Step 3. The Two-pass algorithm is used to encode the binary image, so as to segment the image into different sub-region of different classAn illustration is shown in Figure3. There are 3 classes in the image, in which the class 3 region is marked in deep gray. After image binarization and two-pass coding, the target region is divided into two subregions whose edges are marked in red and yellow, respectively.Figure 3
Region segmentation illustration: (a) class determination of image; (b) target region (class 3); (c) image binarization; (d) subregion coding.
(a)(b)(c)(d)


### 2.2. Edge Correction

#### 2.2.1. Incomplete Edge Correction

The edges of the whole image are extracted from each subregion and encoded to form the defect contour information. However, it is difficult to set a proper threshold to extract all the defect contours perfectly. There are two cases in the incomplete defect contours as shown in Figure4: (1) a contour is divided into several edges and stored in different labelled point sets and (2) some parts of a contour are undetected.Figure 4
Incomplete edge illustration: (a) complete edge; (b) incomplete edge (situation 1); (c) incomplete edge (situation 2).
(a)(b)(c)The beginning and end points of these incomplete contours are defined as endpoints, as shown in Figure5. There are two cases of endpoints: (1) only one edge point is in the 8-neighborhood of endpoint and (2) only two adjacent edge points are in the 8-neighborhood of endpoint, as shown in Figure 6.Figure 5
Endpoint of incomplete edge: (a) endpoint in situation 1; (b) endpoint in situation 2.
(a)(b)Figure 6
Endpoint in different situations: (a) endpoint in situation 1; (b) endpoint in situation 2.
(a)(b)The steps for endpoint connections are as follows:Step 1. If the distance between two endpoints of a set is less than the threshold T1, the set will be considered as case 1 with its endpoints connected using interpolation. The interpolated points are marked as the same label. The endpoint information of this edge will be updated.Step 2. The minimum endpoint distance of every two set is calculated. If the distance is less than the threshold T2, the two sets will be considered as case 2 with their endpoints connected using interpolation. The interpolated points and the set with a bigger label are merged to the other set. The endpoint information of the two sets will be updated. This step will be repeated until the set will not change. The flowchart is shown in Figure 7.Figure 7
Flowchart of incomplete edge correct.


#### 2.2.2. Interference Contour Elimination

It is noteworthy that some of the edges extracted are not defect contours. These interference contours are usually the edges of some structures and appear as line segments. Thereby, linear fitting is applied on all the contours corrected.Assuming that the polynomial of the line in which a contour lies ispx=ao+a1x, all points in this contour are substituted into the polynomial:(8)a0+a1x1=y1,a0+a1x2=y2,⋮a0+a1xn=yn,where n is the number of points. Equation (8) can be converted to obtain the least square solution of a0 and a1 through equation (9). If the residual norm of the fitted polynomial is less than the threshold value, the edge is considered as a line segment that needs to be eliminated.(9)n∑xi∑xi∑xi2a0a1=∑yi∑xiyi.


## 2.1. Region Segmentation Search Methodology

### 2.1.1. Structural Location Based on Contour Matching

Although all the structures certainly appear in the chip image, the image brightness is irregular and structures may occlude mutually. Therefore, this paper used a contour matching method based on the Canny operator to solve these two problems [21].(1) Template Edge Model Building. Each structure has a respective image as a template whose edges are used to build its model. The models are built by following the below-mentioned steps:Step 1. Image graying: each Canny is only used to process the gray image. Thus, the template image should be grayed if it is a color image. Taking an RGB color image as an example, the formula used for graying is as follows:(1)Igrayx,y=0.299∗Iredx,y+0.587∗Igreenx,y+0.114∗Ibluex,y,whereIgrayx,y is the gray image value, Iredx,y is the red channel value, Igreenx,y is the green channel value, and Ibluex,y is the blue channel value.Step 2. Image smoothing: each image is convoluted by Gauss filter to eliminate noise.(2)Ix,y=Gx,y∗fx,y,Gx,y=12πσ2exp−x2+y22σ2,whereIx,y is the filtered image, fx,y is the original image, and Gx,y is the two-dimensional Gauss function.Step 3. Gradient calculation: gradient magnitudes and directions of an image are determined by Sobel operator:(3)Pxx,y=fx+1,y−1+2fx+1,y+fx+1,y+1−fx−1,y−1−2fx−1,y−fx−1,y+1,Pyx,y=fx−1,y−1+2fx,y−1+fx+1,y−1−fx−1,y+1−2fx,y+1−fx+1,y−1,Mx,y=Pxx,y2+Pyx,y2,θx,y=arctanPyx,yPxx,y.Step 4. Nonmaximum suppression: in order to ensure the accuracy of edge location, the gradient magnitude at each edge pixel should be compared with those at its two neighbors in the gradient direction. If it is larger, the pixel will be marked as a maximum edge point; otherwise, it will be marked as the background.Step 5. Double threshold determination and edge connection: two thresholds Thigh and Tlow are required to classify the gradients of the remaining pixels that have not been suppressed. Thigh is usually set twice as high as Tlow. The gradients higher than Thigh are definitely strong edge points, while those lower than Tlow are definitely nonedge points. The weak edges which are higher than Tlow but lower than Thigh are determined depending on whether there is more than one strong edge point in its neighborhood.Step 6. Model building: because the model image may have some parts without any edge information, the coordinates of the confirmed points need to be rearranged to reflect the start point as the center of gravity:(4)xpi=xpi−xgravity,ypi=ypi−ygravity,xgravity=∑i=1Nxpin,ygravity=∑i=1Nypin,wherexpi is the x-coordinate of the ith point, ypi is the y-coordinate of the ith point, xGrowity is the x-coordinate of gravity, yGrowity is the y-coordinate of gravity, and n is the total number of edge points.Step 7. Model storage: the coordinates along with their gradient magnitude and direction information are saved as the template models.(2) Model Matching. The template models built are applied to search the structures in the chip image. Each model consists of a set of points PiT=xiT,yiT, gradients in X and Y directions GiT=GxiT,GyiT, and directions DiTxi,yi, where i=1,2,…,n, in which n is the number of elements in the Template (T) dataset. The gradient magnitudes need to be normalized for reducing the influence of illumination.The gradient magnitudes and the direction of the search image (i.e., the chip image) are also calculated by the Canny operator, which are denoted byGu,vS=Gxu,vS,Gyuu,vS and Du,vSu,v, where u,v is the coordinate in the image, u=1,2,…,p, in which p is the number of rows in the search image, and v=1,2,…,q, in which q is the number of columns in the search image.In the matching process, the template model is shifted in the search image to compare with the subimage using a similarity evaluation:(5)Su,v=12Sdiru,v+Smagu,v,Sdiru,v=∑i=1nDTxi,yi⋅Dsu+xi,v+yi∑i=1nDTxi,yi2⋅∑i=1nDsu+xi,v+yi2,Smagu,y=1n∑i=1nGxiT⋅Gxu+xi,v+yiS+GyiT⋅Gyu+xi,v+yiSGxiT2+GyiT2⋅Gxu+xi,v+yiS2+Gu+xi,v+yi2,where Su,v is the score of similarity at point u,v in the search image, Sdiru,v is the score of direction similarity, and Smagu,v is the score of magnitude similarity. The score is related to the portion of the structure visible in the search image. If the template model and the search image match perfectly, the score is 1; if the structure is not present in the search image, the score is 0.In the process of calculatingSu,v at a point, the partial score Spu,v (i.e., equation (6)) is introduced to improve the algorithm efficiency. If Spu,v is lower than a minimum score (Smin), the calculation of Su,v will be stopped and the matching evaluation of the next point will be started.(6)Spu,v=1m∑i=1mGxiT⋅Gxu+xi,v+yiS+GyiT⋅Gyu+xi,v+yiSGxiT2+GyiT2⋅Gxu+xi,v+yiS2+Gu+xi,v+yi2,where m is the number of points used for match. It is evident that Spu,v is smaller or equal to 1, so the first restriction is Sm>Smin−1+m/n.If there is a perfect match between the template and the model, the partial score at any point should be greater than the minimum scoreSmin, i.e., m/nSpu,v≥Smin. However, there are still some situations where the missing part of the object is checked first, the partial sum will be low that the structure in the chip image may not be considered as a match. So a new criterion which takes into account both restrictions is set that the evaluation of the partial score will be stopped at(7)Sm<minSmin−1+1−g⋅Smin1−g⋅mn,Smin⋅mn,where g is a greediness parameter which determines the fraction of the second restriction.This similarity measure combines several insights: the similarity measure is invariant to nonlinear illumination changes because all gradient vectors are normalized. More importantly, this similarity measure is robust when the object is partially visible or mixed with other objects.


### 2.1.2. Automatic Region Segmentation

After determining the position of each structure in the image, it is necessary to segment the image into several subregions according to the locations and the overlap relationships of the structures. In this paper, the two-pass algorithm is used to encode each overlap region class, for automatic segmentation of chip image.(1) Two-Pass Algorithms. A connected region consists of adjacent pixels with the same pixel value. Therefore, the connected region can be found in the image by these two conditions. For each connected region found, a unique label is given to distinguish the other connected regions. In this paper, a two-pass connected domain labelling algorithm for 8 neighborhoods is used [22]. As shown in Figure 2, the specific steps are as follows:Step 1. First pass: the image is scanned from left to right and from top to bottom. If the point scanned is the effective pixel (nonzero), the situation of the leftmost, upper left, top-right points in the eight neighborhoods of this point will be judged. If none of them are effective points, the point is the beginning of a new label.Step 2. Second pass: in the first pass, the points in the same connected region may have different labels. Therefore, the image should be scanned in the same way to merge these labels as the following rules:(1)
If the leftmost point and the upper right point of a labelled point are effective points, the label of all three points will be set to the smaller label of them(2)
If the upper left point and the upper right point of a labelled point are effective points, the label of all three points will be set to the smaller label of them(3)
Otherwise, the label of point will be set to one of four in the order of leftmost, upper left, topmost, and upper rightThe points with the same label form a cluster.Figure 2
Two-pass algorithm illustration: (a) original image; (b) first pass; (c) second pass.
(a)(b)(c)(2) Region Segmentation. According to the positions of the structures in the image, the number of layers of structures on each pixel is determined. The pixels with the same amount of layers are regarded as an overlap region class. A chip image can be separated into target (class) regions and nontarget regions. At the same time, the target region contains several connected regions which are regarded as subregion of this class. A unique label is given to each subregion. The steps are as follows:Step 1. Each pixel is determined which class it belongs toStep 2. For each class, the pixels of this class are set to 1, and the others are set to 0Step 3. The Two-pass algorithm is used to encode the binary image, so as to segment the image into different sub-region of different classAn illustration is shown in Figure3. There are 3 classes in the image, in which the class 3 region is marked in deep gray. After image binarization and two-pass coding, the target region is divided into two subregions whose edges are marked in red and yellow, respectively.Figure 3
Region segmentation illustration: (a) class determination of image; (b) target region (class 3); (c) image binarization; (d) subregion coding.
(a)(b)(c)(d)


## 2.1.1. Structural Location Based on Contour Matching

Although all the structures certainly appear in the chip image, the image brightness is irregular and structures may occlude mutually. Therefore, this paper used a contour matching method based on the Canny operator to solve these two problems [21].(1) Template Edge Model Building. Each structure has a respective image as a template whose edges are used to build its model. The models are built by following the below-mentioned steps:Step 1. Image graying: each Canny is only used to process the gray image. Thus, the template image should be grayed if it is a color image. Taking an RGB color image as an example, the formula used for graying is as follows:(1)Igrayx,y=0.299∗Iredx,y+0.587∗Igreenx,y+0.114∗Ibluex,y,whereIgrayx,y is the gray image value, Iredx,y is the red channel value, Igreenx,y is the green channel value, and Ibluex,y is the blue channel value.Step 2. Image smoothing: each image is convoluted by Gauss filter to eliminate noise.(2)Ix,y=Gx,y∗fx,y,Gx,y=12πσ2exp−x2+y22σ2,whereIx,y is the filtered image, fx,y is the original image, and Gx,y is the two-dimensional Gauss function.Step 3. Gradient calculation: gradient magnitudes and directions of an image are determined by Sobel operator:(3)Pxx,y=fx+1,y−1+2fx+1,y+fx+1,y+1−fx−1,y−1−2fx−1,y−fx−1,y+1,Pyx,y=fx−1,y−1+2fx,y−1+fx+1,y−1−fx−1,y+1−2fx,y+1−fx+1,y−1,Mx,y=Pxx,y2+Pyx,y2,θx,y=arctanPyx,yPxx,y.Step 4. Nonmaximum suppression: in order to ensure the accuracy of edge location, the gradient magnitude at each edge pixel should be compared with those at its two neighbors in the gradient direction. If it is larger, the pixel will be marked as a maximum edge point; otherwise, it will be marked as the background.Step 5. Double threshold determination and edge connection: two thresholds Thigh and Tlow are required to classify the gradients of the remaining pixels that have not been suppressed. Thigh is usually set twice as high as Tlow. The gradients higher than Thigh are definitely strong edge points, while those lower than Tlow are definitely nonedge points. The weak edges which are higher than Tlow but lower than Thigh are determined depending on whether there is more than one strong edge point in its neighborhood.Step 6. Model building: because the model image may have some parts without any edge information, the coordinates of the confirmed points need to be rearranged to reflect the start point as the center of gravity:(4)xpi=xpi−xgravity,ypi=ypi−ygravity,xgravity=∑i=1Nxpin,ygravity=∑i=1Nypin,wherexpi is the x-coordinate of the ith point, ypi is the y-coordinate of the ith point, xGrowity is the x-coordinate of gravity, yGrowity is the y-coordinate of gravity, and n is the total number of edge points.Step 7. Model storage: the coordinates along with their gradient magnitude and direction information are saved as the template models.(2) Model Matching. The template models built are applied to search the structures in the chip image. Each model consists of a set of points PiT=xiT,yiT, gradients in X and Y directions GiT=GxiT,GyiT, and directions DiTxi,yi, where i=1,2,…,n, in which n is the number of elements in the Template (T) dataset. The gradient magnitudes need to be normalized for reducing the influence of illumination.The gradient magnitudes and the direction of the search image (i.e., the chip image) are also calculated by the Canny operator, which are denoted byGu,vS=Gxu,vS,Gyuu,vS and Du,vSu,v, where u,v is the coordinate in the image, u=1,2,…,p, in which p is the number of rows in the search image, and v=1,2,…,q, in which q is the number of columns in the search image.In the matching process, the template model is shifted in the search image to compare with the subimage using a similarity evaluation:(5)Su,v=12Sdiru,v+Smagu,v,Sdiru,v=∑i=1nDTxi,yi⋅Dsu+xi,v+yi∑i=1nDTxi,yi2⋅∑i=1nDsu+xi,v+yi2,Smagu,y=1n∑i=1nGxiT⋅Gxu+xi,v+yiS+GyiT⋅Gyu+xi,v+yiSGxiT2+GyiT2⋅Gxu+xi,v+yiS2+Gu+xi,v+yi2,where Su,v is the score of similarity at point u,v in the search image, Sdiru,v is the score of direction similarity, and Smagu,v is the score of magnitude similarity. The score is related to the portion of the structure visible in the search image. If the template model and the search image match perfectly, the score is 1; if the structure is not present in the search image, the score is 0.In the process of calculatingSu,v at a point, the partial score Spu,v (i.e., equation (6)) is introduced to improve the algorithm efficiency. If Spu,v is lower than a minimum score (Smin), the calculation of Su,v will be stopped and the matching evaluation of the next point will be started.(6)Spu,v=1m∑i=1mGxiT⋅Gxu+xi,v+yiS+GyiT⋅Gyu+xi,v+yiSGxiT2+GyiT2⋅Gxu+xi,v+yiS2+Gu+xi,v+yi2,where m is the number of points used for match. It is evident that Spu,v is smaller or equal to 1, so the first restriction is Sm>Smin−1+m/n.If there is a perfect match between the template and the model, the partial score at any point should be greater than the minimum scoreSmin, i.e., m/nSpu,v≥Smin. However, there are still some situations where the missing part of the object is checked first, the partial sum will be low that the structure in the chip image may not be considered as a match. So a new criterion which takes into account both restrictions is set that the evaluation of the partial score will be stopped at(7)Sm<minSmin−1+1−g⋅Smin1−g⋅mn,Smin⋅mn,where g is a greediness parameter which determines the fraction of the second restriction.This similarity measure combines several insights: the similarity measure is invariant to nonlinear illumination changes because all gradient vectors are normalized. More importantly, this similarity measure is robust when the object is partially visible or mixed with other objects.


## 2.1.2. Automatic Region Segmentation

After determining the position of each structure in the image, it is necessary to segment the image into several subregions according to the locations and the overlap relationships of the structures. In this paper, the two-pass algorithm is used to encode each overlap region class, for automatic segmentation of chip image.(1) Two-Pass Algorithms. A connected region consists of adjacent pixels with the same pixel value. Therefore, the connected region can be found in the image by these two conditions. For each connected region found, a unique label is given to distinguish the other connected regions. In this paper, a two-pass connected domain labelling algorithm for 8 neighborhoods is used [22]. As shown in Figure 2, the specific steps are as follows:Step 1. First pass: the image is scanned from left to right and from top to bottom. If the point scanned is the effective pixel (nonzero), the situation of the leftmost, upper left, top-right points in the eight neighborhoods of this point will be judged. If none of them are effective points, the point is the beginning of a new label.Step 2. Second pass: in the first pass, the points in the same connected region may have different labels. Therefore, the image should be scanned in the same way to merge these labels as the following rules:(1)
If the leftmost point and the upper right point of a labelled point are effective points, the label of all three points will be set to the smaller label of them(2)
If the upper left point and the upper right point of a labelled point are effective points, the label of all three points will be set to the smaller label of them(3)
Otherwise, the label of point will be set to one of four in the order of leftmost, upper left, topmost, and upper rightThe points with the same label form a cluster.Figure 2
Two-pass algorithm illustration: (a) original image; (b) first pass; (c) second pass.
(a)(b)(c)(2) Region Segmentation. According to the positions of the structures in the image, the number of layers of structures on each pixel is determined. The pixels with the same amount of layers are regarded as an overlap region class. A chip image can be separated into target (class) regions and nontarget regions. At the same time, the target region contains several connected regions which are regarded as subregion of this class. A unique label is given to each subregion. The steps are as follows:Step 1. Each pixel is determined which class it belongs toStep 2. For each class, the pixels of this class are set to 1, and the others are set to 0Step 3. The Two-pass algorithm is used to encode the binary image, so as to segment the image into different sub-region of different classAn illustration is shown in Figure3. There are 3 classes in the image, in which the class 3 region is marked in deep gray. After image binarization and two-pass coding, the target region is divided into two subregions whose edges are marked in red and yellow, respectively.Figure 3
Region segmentation illustration: (a) class determination of image; (b) target region (class 3); (c) image binarization; (d) subregion coding.
(a)(b)(c)(d)


## 2.2. Edge Correction

### 2.2.1. Incomplete Edge Correction

The edges of the whole image are extracted from each subregion and encoded to form the defect contour information. However, it is difficult to set a proper threshold to extract all the defect contours perfectly. There are two cases in the incomplete defect contours as shown in Figure4: (1) a contour is divided into several edges and stored in different labelled point sets and (2) some parts of a contour are undetected.Figure 4
Incomplete edge illustration: (a) complete edge; (b) incomplete edge (situation 1); (c) incomplete edge (situation 2).
(a)(b)(c)The beginning and end points of these incomplete contours are defined as endpoints, as shown in Figure5. There are two cases of endpoints: (1) only one edge point is in the 8-neighborhood of endpoint and (2) only two adjacent edge points are in the 8-neighborhood of endpoint, as shown in Figure 6.Figure 5
Endpoint of incomplete edge: (a) endpoint in situation 1; (b) endpoint in situation 2.
(a)(b)Figure 6
Endpoint in different situations: (a) endpoint in situation 1; (b) endpoint in situation 2.
(a)(b)The steps for endpoint connections are as follows:Step 1. If the distance between two endpoints of a set is less than the threshold T1, the set will be considered as case 1 with its endpoints connected using interpolation. The interpolated points are marked as the same label. The endpoint information of this edge will be updated.Step 2. The minimum endpoint distance of every two set is calculated. If the distance is less than the threshold T2, the two sets will be considered as case 2 with their endpoints connected using interpolation. The interpolated points and the set with a bigger label are merged to the other set. The endpoint information of the two sets will be updated. This step will be repeated until the set will not change. The flowchart is shown in Figure 7.Figure 7
Flowchart of incomplete edge correct.


### 2.2.2. Interference Contour Elimination

It is noteworthy that some of the edges extracted are not defect contours. These interference contours are usually the edges of some structures and appear as line segments. Thereby, linear fitting is applied on all the contours corrected.Assuming that the polynomial of the line in which a contour lies ispx=ao+a1x, all points in this contour are substituted into the polynomial:(8)a0+a1x1=y1,a0+a1x2=y2,⋮a0+a1xn=yn,where n is the number of points. Equation (8) can be converted to obtain the least square solution of a0 and a1 through equation (9). If the residual norm of the fitted polynomial is less than the threshold value, the edge is considered as a line segment that needs to be eliminated.(9)n∑xi∑xi∑xi2a0a1=∑yi∑xiyi.


## 2.2.1. Incomplete Edge Correction

The edges of the whole image are extracted from each subregion and encoded to form the defect contour information. However, it is difficult to set a proper threshold to extract all the defect contours perfectly. There are two cases in the incomplete defect contours as shown in Figure4: (1) a contour is divided into several edges and stored in different labelled point sets and (2) some parts of a contour are undetected.Figure 4
Incomplete edge illustration: (a) complete edge; (b) incomplete edge (situation 1); (c) incomplete edge (situation 2).
(a)(b)(c)The beginning and end points of these incomplete contours are defined as endpoints, as shown in Figure5. There are two cases of endpoints: (1) only one edge point is in the 8-neighborhood of endpoint and (2) only two adjacent edge points are in the 8-neighborhood of endpoint, as shown in Figure 6.Figure 5
Endpoint of incomplete edge: (a) endpoint in situation 1; (b) endpoint in situation 2.
(a)(b)Figure 6
Endpoint in different situations: (a) endpoint in situation 1; (b) endpoint in situation 2.
(a)(b)The steps for endpoint connections are as follows:Step 1. If the distance between two endpoints of a set is less than the threshold T1, the set will be considered as case 1 with its endpoints connected using interpolation. The interpolated points are marked as the same label. The endpoint information of this edge will be updated.Step 2. The minimum endpoint distance of every two set is calculated. If the distance is less than the threshold T2, the two sets will be considered as case 2 with their endpoints connected using interpolation. The interpolated points and the set with a bigger label are merged to the other set. The endpoint information of the two sets will be updated. This step will be repeated until the set will not change. The flowchart is shown in Figure 7.Figure 7
Flowchart of incomplete edge correct.


## 2.2.2. Interference Contour Elimination

It is noteworthy that some of the edges extracted are not defect contours. These interference contours are usually the edges of some structures and appear as line segments. Thereby, linear fitting is applied on all the contours corrected.Assuming that the polynomial of the line in which a contour lies ispx=ao+a1x, all points in this contour are substituted into the polynomial:(8)a0+a1x1=y1,a0+a1x2=y2,⋮a0+a1xn=yn,where n is the number of points. Equation (8) can be converted to obtain the least square solution of a0 and a1 through equation (9). If the residual norm of the fitted polynomial is less than the threshold value, the edge is considered as a line segment that needs to be eliminated.(9)n∑xi∑xi∑xi2a0a1=∑yi∑xiyi.


## 3. Result and Discussion

### 3.1. Defect Contour Detection

In this study, a certain kind of chip is presented to demonstrate the feasibility of the proposed method. The X-ray photos of chips selected randomly were taken for the purpose of bubble (defect) contour detection. Considering that the chips were placed in the same container, not only the angle between them and thex-axis but also the sizes of them in images were identical. However, the places of structures were slightly different in each chip, and this paper set the structures of a chip as template images to realize multiregion segmentation.The original images of 110 chips form the normal illumination set. The color channel properties of the above photos were adjusted artificially to simulate different illumination situations. First, the images are converted from the RGB model to HSV (hue, saturation, value) model. Then, the V values of some original images were increased or decreased stochastically and reconverted to the RGB model finally. These processed images were used to simulate the situation under strong or weak illumination. The original images together with the processed ones formed the whole image set. The chip images were subjected to noise; hence, the median filter is used to reduce the noise effect as image preprocessing.Each structure of the chip was utilized to build a corresponding model which was matched in the chip image with the minimum scoreSmin (=0.4) and the greediness parameter g (=0.9). As an illustration, the matching results of structure 1 and structure 2 in one chip image under different illumination conditions are shown in Figure 8. According to the matching results, the multiregion segmentation was realized as shown in Figure 9.Figure 8
Structural location: (a) normal illumination; (b) weak illumination; (c) strong illumination.
(a)(b)(c)Figure 9
Automatic region segmentation.
(a)(b)(c)(d)(e)(f)(g)(h)(i)(j)(k)(l)The edges in each subregion were extracted by the Canny operator, which formed the uncorrected edges in the whole image. After incomplete contour correction and interference contour elimination with the same thresholdT1 (=10) and T2 (=10), the contours of bubbles were detected accurately and marked in the right label as shown in Figure 10(b).Figure 10
Detection result: (a) original image; (b) detected image of the proposed method; (c) detected image of YOLO v4.
(a)(b)(c)


### 3.2. Qualification Assessment

In engineering applications, the qualification of a chip was assessed by humans so that the artificial assessment result of it was used as true value. In order to further prove the reliability of our method, the artificial assessment was adopted to evaluate the qualifications of the chips. The qualification of a chip is judged with the rule whether the range of any bubble is over half the distance between the external cavity where it is in.Table1 shows the comparison between the assessment results of our method and the artificial assessment. Another assessment method based on a deep learning method (YOLO v4) [23] is also used for comparison. The detection result of bubbles is shown in Figure 10(c) and the assessment results of it are compared with the artificial assessment in Table 1. For each illumination situation, 40 images are chosen randomly as a test set while the rest are used as a training set. There were three outcomes: qualified, unqualified, and uncertain. When humans cannot judge whether the defects reach the distance threshold, the artificial assessment will be uncertain. However, the machine assessment will be uncertain if the distance is between the 95% and 100% threshold. Accuracy rate and precision rate are chosen as indicators to verify the proposed method. Accuracy rate reflects the similarity degree between assessments. Precision rate shows the accuracy when machine assessment is qualified. Once a chip is judged as unqualified or uncertain, it will be rechecked by humans or instruments; otherwise, no action will be taken on it. So, the latter indicator gets more important than the former one. The proposed method performed the best at normal illumination with the highest rate, while both two indicators had slight declines in other situations. One reason was that the same parameter was difficult to apply to all the changes of image contrast caused by the process of the HSV model. Even so, the precision rate was still higher than 92%. For comparison, because the size of the training set is small and the appearance of bubbles is infinite, the detection capability of YOLO v4 for bubbles is poor. To sum up, the experimental results demonstrated the effectiveness of the proposed method.Table 1
Comparison of assessment results.
Illumination situationMethodMachine assessmentArtificial assessmentTotalAccuracy rate (%)Precision rate (%)QualifiedUnqualifiedUncertainNormalOursQualified190011097.27100.00Unqualified0822Uncertain106YOLO v4Qualified19904075.0067.86Unqualified0111Uncertain000WeakOursQualified503011392.0494.34Unqualified0492Uncertain045YOLO v4Qualified171404060.0054.84Unqualified070Uncertain020StrongOursQualified424011592.1791.30Unqualified0540Uncertain3210YOLO v4Qualified201104072.5064.52Unqualified080Uncertain001Table2 shows the comparison on cost time of the above assessment methods. Compared to the previous way, the proposed method improves the efficiency by 3-4 times. Even the method based on YOLO v4 has the fastest speed, and it has other time costs for its long-time training and poor portability for other kinds of chips. The cost time of artificial assessment depended strongly on the amount of uncertain chips which took more time to confirm than qualified and unqualified ones. The efficiency of machine assessment was stable for its unique relevance to the amount of chips. Considering the accuracy and precision, the proposed method can play a better role in actual engineering application.Table 2
Comparison on cost time.
Illumination situationMachine assessmentArtificial assessment (s)YOLO v4 (s)Ours (s)Normal illumination9.815.257.2Weak illumination9.415.960.7Strong illumination9.516.161.3


## 3.1. Defect Contour Detection

In this study, a certain kind of chip is presented to demonstrate the feasibility of the proposed method. The X-ray photos of chips selected randomly were taken for the purpose of bubble (defect) contour detection. Considering that the chips were placed in the same container, not only the angle between them and thex-axis but also the sizes of them in images were identical. However, the places of structures were slightly different in each chip, and this paper set the structures of a chip as template images to realize multiregion segmentation.The original images of 110 chips form the normal illumination set. The color channel properties of the above photos were adjusted artificially to simulate different illumination situations. First, the images are converted from the RGB model to HSV (hue, saturation, value) model. Then, the V values of some original images were increased or decreased stochastically and reconverted to the RGB model finally. These processed images were used to simulate the situation under strong or weak illumination. The original images together with the processed ones formed the whole image set. The chip images were subjected to noise; hence, the median filter is used to reduce the noise effect as image preprocessing.Each structure of the chip was utilized to build a corresponding model which was matched in the chip image with the minimum scoreSmin (=0.4) and the greediness parameter g (=0.9). As an illustration, the matching results of structure 1 and structure 2 in one chip image under different illumination conditions are shown in Figure 8. According to the matching results, the multiregion segmentation was realized as shown in Figure 9.Figure 8
Structural location: (a) normal illumination; (b) weak illumination; (c) strong illumination.
(a)(b)(c)Figure 9
Automatic region segmentation.
(a)(b)(c)(d)(e)(f)(g)(h)(i)(j)(k)(l)The edges in each subregion were extracted by the Canny operator, which formed the uncorrected edges in the whole image. After incomplete contour correction and interference contour elimination with the same thresholdT1 (=10) and T2 (=10), the contours of bubbles were detected accurately and marked in the right label as shown in Figure 10(b).Figure 10
Detection result: (a) original image; (b) detected image of the proposed method; (c) detected image of YOLO v4.
(a)(b)(c)


## 3.2. Qualification Assessment

In engineering applications, the qualification of a chip was assessed by humans so that the artificial assessment result of it was used as true value. In order to further prove the reliability of our method, the artificial assessment was adopted to evaluate the qualifications of the chips. The qualification of a chip is judged with the rule whether the range of any bubble is over half the distance between the external cavity where it is in.Table1 shows the comparison between the assessment results of our method and the artificial assessment. Another assessment method based on a deep learning method (YOLO v4) [23] is also used for comparison. The detection result of bubbles is shown in Figure 10(c) and the assessment results of it are compared with the artificial assessment in Table 1. For each illumination situation, 40 images are chosen randomly as a test set while the rest are used as a training set. There were three outcomes: qualified, unqualified, and uncertain. When humans cannot judge whether the defects reach the distance threshold, the artificial assessment will be uncertain. However, the machine assessment will be uncertain if the distance is between the 95% and 100% threshold. Accuracy rate and precision rate are chosen as indicators to verify the proposed method. Accuracy rate reflects the similarity degree between assessments. Precision rate shows the accuracy when machine assessment is qualified. Once a chip is judged as unqualified or uncertain, it will be rechecked by humans or instruments; otherwise, no action will be taken on it. So, the latter indicator gets more important than the former one. The proposed method performed the best at normal illumination with the highest rate, while both two indicators had slight declines in other situations. One reason was that the same parameter was difficult to apply to all the changes of image contrast caused by the process of the HSV model. Even so, the precision rate was still higher than 92%. For comparison, because the size of the training set is small and the appearance of bubbles is infinite, the detection capability of YOLO v4 for bubbles is poor. To sum up, the experimental results demonstrated the effectiveness of the proposed method.Table 1
Comparison of assessment results.
Illumination situationMethodMachine assessmentArtificial assessmentTotalAccuracy rate (%)Precision rate (%)QualifiedUnqualifiedUncertainNormalOursQualified190011097.27100.00Unqualified0822Uncertain106YOLO v4Qualified19904075.0067.86Unqualified0111Uncertain000WeakOursQualified503011392.0494.34Unqualified0492Uncertain045YOLO v4Qualified171404060.0054.84Unqualified070Uncertain020StrongOursQualified424011592.1791.30Unqualified0540Uncertain3210YOLO v4Qualified201104072.5064.52Unqualified080Uncertain001Table2 shows the comparison on cost time of the above assessment methods. Compared to the previous way, the proposed method improves the efficiency by 3-4 times. Even the method based on YOLO v4 has the fastest speed, and it has other time costs for its long-time training and poor portability for other kinds of chips. The cost time of artificial assessment depended strongly on the amount of uncertain chips which took more time to confirm than qualified and unqualified ones. The efficiency of machine assessment was stable for its unique relevance to the amount of chips. Considering the accuracy and precision, the proposed method can play a better role in actual engineering application.Table 2
Comparison on cost time.
Illumination situationMachine assessmentArtificial assessment (s)YOLO v4 (s)Ours (s)Normal illumination9.815.257.2Weak illumination9.415.960.7Strong illumination9.516.161.3


## 4. Conclusion Remarks

This paper presented a method to address the interference of structures when detecting defect contours of complex structural chips. Meanwhile, the information of every contour was coded for further usage. The method consisted of two parts: region segmentation search and edge correction. The Canny operator and two-pass were utilized to segment the image into regions automatically according to the location of structures. The edges inside each region were extracted, respectively, in order to reduce the interference of structures. Among all the edges, the incomplete ones were corrected on the basis of criteria. The remaining interference contours were eliminated based on their shape afterwards. The experimental validation on the case study using the X-ray photos of a set of chips successfully demonstrated the effectiveness of the method. The high performance in detection compared to the traditional method could contribute to improving the accuracy of the subsequent qualification assessment.



---

*Source: 5518675-2021-05-28.xml*