# Superpixel Segmentation Using Weighted Coplanar Feature Clustering on RGBD Images
## 3 Algorithm Framework
### Overview and Workflow  
To generate superpixels that cover the entire image area, WCFC first fills in the raw depth map using a cross-bilateral filter [30]. Then, the pixels are projected onto 3D space to form the point cloud to compute the normal map (**n**) and PPL map (\(p\)), which will be discussed in detail in Section 4. Subsequently, we perform the linear iterative clustering algorithm, where the similar pixels in the image are clustered into superpixels.  
Weighted coplanar feature clustering uses a desired number of approximately equally sized superpixels (\(K\)) as the input. For an image with \(N\) pixels, the approximate size of each superpixel is therefore \(N/K\) pixels. For roughly equally sized superpixels, there would be a superpixel center at every grid interval, \(S=\sqrt{N/K}\).  
At the onset of our algorithm, we chose \(K\) superpixel cluster centers \(C_{k}=[l_{k},a_{k},b_{k},x_{k},y_{k},\mathbf{n}_{k},p_{k}]^{T}\), whose parameters will be explained in Section 4, with \(k=[1,K]\) at regular grid intervals (\(S\)). Since the spatial extent of any superpixel is approximately \(S^{2}\), we can safely assume that pixels associated with this cluster center lie within a \(25\times 25\) area around the superpixel center on the \(xy\)-plane. This becomes the search area for the pixels nearest to each cluster center.  
Each pixel in the image is associated with the nearest cluster center whose search area overlaps this pixel. After all of the pixels have been associated with the nearest cluster center, a new center is computed as the average vector of all pixels belonging to the cluster. We then iteratively repeat the process of associating pixels with the nearest cluster center and recalculate the cluster center until convergence. The entire algorithm is summarized in Algorithm 1. Here, an L1 distance between the last cluster center and the recalculated one of this iteration is computed for each cluster center, and their sum is termed the residual error (\(E\)), which is used to determine whether the clustering process is convergent by comparing it with the threshold. In fact, we have found that 10 or 20 iterations suffices for most color images or RGBD images, so we set the number of iterations, instead of setting the threshold.  
```
1: Fill in the depth image with a cross-bilateral filter.
2: Compute the normal map of point cloud \(\mathbf{n}_{k}\).
3: Compute the plane projection length of each pixel \(p_{k}\).
4: Initialize cluster centers, \(C_{k}=[l_{k},a_{k},b_{k},x_{k},y_{k},\mathbf{n}_{k},p_{k}]^{T}\), by sampling pixels at regular grid steps (\(S\)).
5:repeat
6:for each cluster center (\(C_{k}\)) do
7: Assign the best matching pixels from a \(2S\times 2S\) square neighborhood around the cluster center according to the distance measure (\(D\)).
8:endfor
9: Compute new cluster centers and the residual error \(E\) [\(L1\) distance between previous centers and recalculated centers].
10:until\(E\leq\) threshold
11: Enforce connectivity.
```  
**Algorithm 1**Weighted coplanar feature clustering  
At the end of this process, a few stray labels may remain; that is, a few pixels in the vicinity of a larger segment having the same label but not connected to it. Finally, connectivity is enforced by reassigning disjoint segments to the largest neighboring cluster.