實現SLIC算法生成像素畫

2021 年 6 月 24 日
筆記

前言

像素風最早出現在8bit的電子遊戲中，受制於電腦內存大小以及顯示色彩單一，只能使用少量像素來呈現內容，卻成就了不少經典的像素遊戲。隨着內存容量與屏幕分辨率的提升，內存與顯示媒介的限制不再是問題，而像素風也慢慢演變成一種獨特的創作風格。

像素畫的一般的繪製流程包括了勾線、填色等，而逐個像素的繪製需要大量時間。一些流行的藝術方式，比如線描與繪畫領域，都逐漸出現了自動化或半自動化生成的方法。本文將從零開始實現SLIC[1]算法，並實現一款生成像素畫工具。

什麼是SLIC算法

像素畫的繪製之所以不簡單，是因為直接的下採樣並不能準確的捕獲關鍵像素，且容易導致丟失邊緣信息，生成的像素畫往往不盡人意。手工的勾線、填色，都是為了選取合適的像素點。由此，我們的問題變成了如何選取合適的像素點進行填色。

首先，引入一個概念——超像素。超像素是 2003 年 Xiaofeng Ren 提出和發展起來的圖像分割技術，是指具有相似紋理、顏色、亮度等特徵的相鄰像素構成的有一定視覺意義的不規則像素塊[1]。

通過將圖片分割為超像素，可以得到相似的像素簇，相似的像素使用同一個顏色進行填充，得到的像素畫會更合理。

超像素點分割的方法包括了提取輪廓、聚類、梯度上升等多種。論文[1]提出的SLIC超像素點分割算法（簡單線性迭代聚類，simple linear iterative clustering）就是其中一種，它基於K-means聚類算法，根據像素的顏色和距離特徵進行聚類來實現良好的分割結果，與若干種超像素點分割算法相比，SLIC具有簡單靈活、效果好、處理速度快等優勢。

如何實現SLIC算法

SLIC的基本流程如下：

圖像預處理。

將圖像從RGB顏色空間轉換到CIE-Lab顏色空間，Lab顏色空間更符合人類對顏色的視覺感知。這個空間里的距離能反映人感覺到的顏色差別，相關計算更為準確。

Lab顏色空間同樣具有三個通道，分別是l，a，b，其中l代表亮度，數值範圍為[0,100]，a表示從綠色到紅色的分量，數值範圍為[-128,127]，b表示藍色到黃色的分量，數值範圍為[-128,127]。

RGB和LAB之間沒有直接的轉換公式，需要將RGB轉為XYZ顏色空間再轉為LAB，代碼見文末完整代碼。
初始化聚類中心。

根據參數確定超像素的數目，也就是需要劃分為多少個區域。假設圖片有N個像素點，預計分割為K個超像素，每個超像素大小為N/K，相鄰中心距離為S=Sqr(N/K)，得到K個聚類坐標。
優化初始聚類中心。在聚類中心的3*3鄰域內選擇梯度最小的像素點作為新的聚類中心。

把圖像看成二維離散函數，梯度也就是這個函數的求導，當相鄰像素值有變化就會存在梯度，而在邊緣上的像素點的梯度最大。將聚類中心挪到梯度最小的地方可以避免其落到邊緣輪廓上，影響聚類效果。

離散梯度的梯度計算這裡不做詳細推導了，由於其中包含了若干*方與開方，計算量較大，一般會簡化為用絕對值來*似*方和*方根的操作。簡化後的計算坐標為(i,j)的像素點的梯度公式為：

其中（i+1,j）與（i,j+1）為像素右側點與像素下方點的坐標。l(a,b)為（a，b）坐標上像素的亮度通道值l。
計算像素點與聚類中心的距離。

在聚類中心距離S的區域內 2S*2S的鄰域內計算像素點與每個聚類中心的距離。

這裡的距離使用的是歐式距離，總距離D由dc顏色距離與ds空間距離兩部分組成。公式如下：

如果直接將l，a，b，x，y拼接成一個矢量計算距離，當超像素的大小變化時，x，y的值可以取到非常大，比如如果一張圖1000*1000，空間距離可以達到1000*Sqr(2)，而顏色距離最大僅10*Sqr(2)，導致最終計算得到的距離值中，空間距離ds權重佔比過大。

所以需要進行歸一化，除以最大值即超像素點的初始寬度S，將值映射到[0,1]。

而顏色空間距離也會給到一個固定的值m來調節顏色距離與空間距離的影響權重，m取值範圍為[1,40]。

距離公式即變成了

當m越大，顏色空間除以m後的值越小，即空間距離的權重越大，生成的像素會更為形狀規則，當m越小，顏色距離權重更大，超像素會在邊緣更為緊湊，而形狀大小較為不規則。
像素點分類。

標記每個像素點的類別為距離其最小的聚類中心的類別。
重新計算聚類中心。

計算屬於同一個聚類的所有像素點的*均向量值，重新得到聚類中心。
迭代4～6的過程。

直到舊聚類中心與新聚類中心的距離小於一定閾值或者達到一定迭代次數，一般來說，當迭代次數到達10，算法能夠達到收斂。
聚類優化。

迭代到最後，可能會出現與聚類中心不屬於同一連通域的孤立像素點，可以使用到連通算法將其分配到最*的聚類標籤。

論文中並未給出具體的實現算法。而本文的應用場景是生成像素畫，會對像素進行下取樣，並不會細化到每個像素，由此，本文不做聚類優化處理。

小小總結一下，SLIC算法流程大體與K-means是一致的，不斷迭代計算距離最小的聚類簇，不同的是只對聚類中心的S距離內像素點進行計算，減少了不少的計算量。

生成像素畫

基於SLIC算法，我們已經可以把一張圖劃分為N個超像素點。每個超像素中像素都是相*的。也就是說，每個像素都被歸類為一個超像素，有一個聚類中心。那麼將像素的顏色賦值為其聚類中心的顏色即得到我們想要的效果。

設定一定步長stride，使用Canvas，每隔stride個像素，將像素賦值為其聚類中心的顏色，即得到最終的像素化結果。

而每個人對於像素畫的主觀感受是不一致的，為了讓用戶有更多的選擇，得到自己滿意的結果。可以暴露更多的人工干預參數，比如取消聚類優化的終止條件，改為由用戶來設置迭代次數，以及最終取像素值的步長。人工設定的參數包括了

超像素點大小blocksize；blocksize越小，超像素點分割越細膩。
迭代次數iters；iters越大，分割結果更精準，計算時間越長。
顏色空間權重weight；weight越大，顏色對於分割結果的影響越大。
取像素點步長stride；stride越小，生成的像素圖越接*超像素點，也就越細膩。

實現用戶交互界面

作為一個工具，自然需要用戶交互界面，前端界面基於HTML/Javascript/CSS搭建，使用Canvas API繪製圖像內容，而用戶交互面板選擇的是dat.gui [3] 庫。dat.gui是一個輕量級的圖像化界面庫，非常適用於參數的修改，常用作可視化 Demo 的演示。支持的參數類型包括了Number、String、Boolean、自定義函數等。可以為不同的屬性綁定相應的響應事件，當屬性值改變時自動觸發事件。

為生成像素化工具添加以下屬性與事件：