簡介：最近項目使用到了超像素分割，是以順道研究了以下SLIC這一算法。超像素分割這類low-level vision問題已經在CVPR，ICCV這種頂級會議上逐漸銷聲匿迹，越來越流行的learning method漸漸占據了這些頂級會議90%的篇幅。本文講解的SLIC是2010年提出的一種十分簡單的超分辨分割算法，原理簡單、便于實作。
一.SLIC(simple linear iterative clustering）原理分析
- 初始化種子點（聚類中心）：按照設定的超像素個數，在圖像内均勻的配置設定種子點。假設圖檔總共有 N 個像素點，預分割為 K 個相同尺寸的超像素，那麼每個超像素的大小為N/ K ，則相鄰種子點的距離（步長）近似為S=sqrt(N/K)。
- 在種子點的n*n鄰域内重新選擇種子點（一般取n=3）。具體方法為：計算該鄰域内所有像素點的梯度值，将種子點移到該鄰域内梯度最小的地方。這樣做的目的是為了避免種子點落在梯度較大的輪廓邊界上，以免影響後續聚類效果。
- 在每個種子點周圍的鄰域内為每個像素點配置設定類标簽（即屬于哪個聚類中心）。和标準的k-means在整張圖中搜尋不同，SLIC的搜尋範圍限制為2S2S，可以加速算法收斂，如下圖。在此注意一點：期望的超像素尺寸為SS，但是搜尋的範圍是2S*2S。
超像素分割算法研究：SLIC分割算法原理講解一.SLIC(simple linear iterative clustering）原理分析二.僞算法描述三.參考博文 - 距離度量。包括顔色距離和空間距離。對于每個搜尋到的像素點，分别計算它和該種子點的距離。距離計算方法如下：
其中，dc代表顔色距離，ds代表空間距離，Ns是類内最大空間距離，定義為Ns=S=sqrt(N/K)，适用于每個聚類。最大的顔色距離Nc既随圖檔不同而不同，也随聚類不同而不同，是以我們取一個固定常數m（取值範圍[1,40],一般取10）代替。最終的距離度量D’如下：
由于每個像素點都會被多個種子點搜尋到，是以每個像素點都會有一個與周圍種子點的距離，取最小值對應的種子點作為該像素點的聚類中心。
- 疊代優化。理論上上述步驟不斷疊代直到誤差收斂（可以了解為每個像素點聚類中心不再發生變化為止），實踐發現10次疊代對絕大部分圖檔都可以得到較理想效果，是以一般疊代次數取10。
- 增強連通性。經過上述疊代優化可能出現以下瑕疵：出現多連通情況、超像素尺寸過小，單個超像素被切割成多個不連續超像素等，這些情況可以通過增強連通性解決。主要思路是：建立一張标記表，表内元素均為-1，按照“Z”型走向（從左到右，從上到下順序）将不連續的超像素、尺寸過小超像素重新配置設定給鄰近的超像素，周遊過的像素點配置設定給相應的标簽，直到所有點周遊完畢為止。
二.僞算法描述
/∗ Initialization ∗/
Initialize cluster centers Ck = [lk , ak , bk , xk , yk ]T by sampling pixels at regular grid steps S.
Move cluster centers to the lowest gradient position in a 3 × 3 neighborhood.
Set label l(i) = −1 for each pixel i. Set distance d(i) = ∞ for each pixel i.
repeat
/∗ Assignment ∗/
for each cluster center Ck do
for each pixel i in a 2S × 2S region around Ck do
Compute the distance D between Ck and i.
if D < d(i) then
set d(i) = D
set l(i) = k
end if
end for
end for
/∗ Update ∗/
Compute new cluster centers. Compute residual error E.
until E ≤ threshold
三.參考博文
1.https://github.com/laixintao/slic-python-implementation
2.https://blog.csdn.net/zhj_matlab/article/details/52986700
3.https://blog.csdn.net/electech6/article/details/45509779