## 2 Materials and Methods
### Minimum Spanning Tree Clustering  
An image can be converted to an undirected graph \(\mathcal{G}=(\mathcal{V},\mathcal{E})\), whose pixels in the image \(v\in\mathcal{V}\) are the vertices and the value of each edge \(e_{ij}=\left(v_{i},v_{j}\right)\) evaluates the similarity between the two vertices \(e\in\mathcal{E}\subseteq\mathcal{V}\times\mathcal{V}\). Let \(k\) be the number of superpixels to be divided, the superpixel segmentation task is broken up the undirected graph \(\mathcal{G}\) into \(k\) disjoint subgraphs \(\mathcal{G}^{\prime}=(\mathcal{V}^{\prime},\mathcal{E}^{\prime})\), where \(\mathcal{V}^{\prime}\subseteq\mathcal{V}\) and \(\mathcal{E}^{\prime}\subseteq\mathcal{E}\).  
The proposed algorithm is a kind of bottom-up pixel aggregation method, which grows regions based on the Prim method [34]. The Prim algorithm is a greedy algorithm that finds the minimum spanning tree for a weighted undirected graph. Suppose a graph has \(n\) vertices, and the goal is to aggregate the vertices into a forest with \(k\) trees. Starting from the initial seeds, the algorithm adds the least cost connection from the tree to the vertex in each step. Similar to SLIC [26], a distance measure was adopted in five-dimensional space. In the spatial space \(\mathbf{x}=\left[\begin{array}{cc}x&y\end{array}\right]^{T}\) and CIELAB color space \(\mathbf{c}=\left[\begin{array}{cc}l&a&b\end{array}\right]^{T}\), the distance of two vertices \(v_{1}\) and \(v_{2}\) is defined as  
\[D(v_{1},v_{2})=\sqrt{\lambda^{2}\frac{\left\|\mathbf{x}_{1}-\mathbf{x}_{2} \right\|_{2}^{2}}{N_{x}^{2}}+\left\|\mathbf{c}_{1}-\mathbf{c}_{2}\right\|_{2} ^{2}} \tag{5}\]  
where \(N_{x}\) is a normalization parameter. For an image of \(n\) pixels, the value of \(N_{x}\) is set to be \(\sqrt{n/k}\). The value of \(\lambda\) is set by the user. \(\lambda\) weighs the relative importance of the color distance term and spatial distance term. The larger the \(\lambda\) value is, the more regular the generated superpixels are. The smaller the \(\lambda\) value is, the boundary adherence better the generated superpixels are.  
The Prim algorithm only considers the distance between two vertices on the tree border during the aggregation process. This metric is extremely sensitive to noise. The average attributes of the tree are used to calculate the distance, which not only simplifies the calculation of the shortest path distance in the neighbor, but also improves the robustness of the Prim algorithm. After running the Prim algorithm, \(k\) trees representing \(k\) superpixels are generated. For a superpixel \(S_{i}\), its average attribute \(C_{i}=\left[\begin{array}{cc}\mathbf{x}_{i}&\mathbf{c}_{i}\end{array}\right]\) is given by  
\[C_{i}=\frac{\int_{v\in S_{i}}{\mathit{d}v}}{\int_{v\in S_{i}}{\mathit{1}dv}} \tag{6}\]  
The average attribute replaces the seed to calculate the distance. Figure 1 illustrates this aggregation process of superpixels. The process of minimum spanning tree clustering is summarized in Algorithm 2.  
```
Input: An image \(I\) of \(n\) pixels, \(k\) initial locations \(\mathbf{x}_{i}\) generated in Algorithm 1 and the weight parameter \(\lambda\) Output: Initial Superpixel label map \(L\)  Initialize \(L[:]\leftarrow-1\)  Initialize \(C_{i}=\left[\begin{array}{cc}\mathbf{x}_{i}&\mathbf{c}_{i}\end{array}\right]\) by extracting the features of the initial locations \(\mathbf{x}_{i}\) for each centroid \(C_{i}\)do  Vertex \(v\leftarrow\left\{\begin{array}{cc}C_{i}&k&0\end{array}\right\}\)  Push \(v\) on priority queue \(Q\) endfor while\(Q\
eq\varnothing\)do  remove \(v_{i}\) from the priority queue \(Q\) \(L[v_{i}]=k_{i}\)  Update the centroid \(C_{i}\) using Equation (6) for Each connected neighbor \(v_{j}\) of \(v_{i}\)do  Calculated distance of \(v_{j}\) and \(v_{i}\) using Equation (5)  Create the Vertex \(v_{j}\leftarrow\left\{\begin{array}{cc}C_{j}&k_{i}&d_{ij}\end{array}\right\}\) if\(L[:]\leftarrow-1\)then  Push \(v_{j}\) on \(Q\) endif endfor endwhile
```  
**Algorithm 2**Minimum Spanning Tree Clustering