## 2 The Proposed Method
### Die Pattern Detection and Clustering  
Die patterns that are similar to the standard template are expected to be detected from the original SAT image. Following steps 6-9 described in the template size estimation of Section 2.1, regions that  
Figure 6: Binarized image of the initial template in Figure 3.  
Figure 7: Patches: (a) extracted from the initial template; (b) used as a standard template. are highly similar to the template are obtainable. The yellow dot in Figure 8 indicates that there is a die pattern found at that location, that is, a region similar to the template exists. Notably, some die patterns are not detected because their similarity is insufficiently high. They possibly result from imaging anomalies, wafer fabrication defects, and belonging to other pattern types such as alignment marks. From Figure 8, it is evident that the detected die patterns are arranged in rows and columns, and the mis-detected die patterns (dark holes inside the wafer) are possibly retrieved from their neighboring dies. Therefore, this subsection presents a clustering method for obtaining the columns and rows in the arrangement by using the detected die patterns and predicting the coordinates of these rows and columns. Eventually, the positions of these mis-detected patterns can be obtained via interpolation or extrapolation approaches. Let \(P_{k}\) be the \(k\)-th detected die pattern and \(\left(x_{k}^{\text{TL}},y_{k}^{\text{TL}}\right)\) be its top-left corner for \(1\leq k\leq N_{\text{D}}\), where \(N_{\text{D}}\) is the total number of detected patterns. In general, the wafer is well aligned during the SAT imaging process; consequently, die patterns are neatly arranged in rows and columns. The die patterns in the same column (or row) possess almost the same horizontal (or vertical) location \(x_{k}^{\text{TL}}\) (or \(y_{k}^{\text{TL}}\)). Hence, a simple clustering method using a distance metric is used for grouping \(\left\{x_{k}^{\text{TL}}\mid k=1,2,\ldots,N_{\text{D}}\right\}\) along the horizontal direction, and then find the number of columns. The criterion is to produce clusters with short intra-cluster distances and long inter-cluster distances. Let us first define a distance threshold as \(T_{\text{d}}=w_{\text{Tpl}}^{*}/2\), the index set of which is \(\mathcal{K}=\{1,2,\ldots,N_{\text{D}}\}\), the selected set \(\mathcal{S}\) is empty, and the cluster set \(\mathcal{C}\) is empty. The proposed algorithm for clustering \(\left\{x_{k}^{\text{TL}}\right\}\) is briefly introduced as follows. 1. Let the first coordinate point \(x_{1}^{\text{TL}}\) be taken as the first cluster center \(\mu_{1}\). Let the selected set be \(\mathcal{S}=\{1\}\), and the cluster set \(\mathcal{C}=\{c_{1}\}\). 2. Select the next point from \(\left\{x_{l}^{\text{TL}}\mid l\in\mathcal{K}\backslash\mathcal{S}\right\}\), and compute the distance \(d_{c}\left(x_{l}^{\text{TL}}\right)\) for every \(c\in\mathcal{C}\). Apply index \(l\) into set \(\mathcal{S}\). 3. Compare this distance \(d_{c}\left(x_{l}^{\text{TL}}\right)\) with the threshold \(T_{\text{d}}\). If \(d_{c}\left(x_{l}^{\text{TL}}\right)<T_{\text{d}}\), then set \(x_{l}^{\text{TL}}\) belonging to cluster \(c\). Next, update center \(\mu_{c}\) by averaging all coordinate points belonging to cluster \(c\). In contrast, let \(x_{l}^{\text{TL}}\) become a new prototype point, and add a new cluster \(c_{\#(\mathcal{C})+1}\) with its center \(\mu_{\#(\mathcal{C})+1}=x_{l}^{\text{TL}}\). Here, \(\#(\mathcal{C})\) denotes the number of clusters in \(\mathcal{C}\). 4. Repeat steps 2-3 until all coordinate points belong to their corresponding clusters. Figure 8: Die detection result of original SAT image. The four steps above form an iteration obtaining the clusters with centers. Based on these clusters, a new iteration is created to assign all coordinate points \(\left\{x_{k}^{\text{TL}}\right\}\) to their nearest cluster in the same manner. This clustering algorithm will terminate when the clustered results of two consecutive iterations are the same.