基于顏色量化和密度峰聚類的彩色圖像分割

王鵬宇，游有鵬，楊雪峰

南京航空航天大學 機電學院，南京210001

1 引言

傳統簇絨地毯在簇絨前需要根據客戶提供的圖案在平面設計軟件中重新繪制，然后進行光照制版、印染、簇絨等工序，制作過程復雜。為了實現簇絨地毯的數字化制造，需要通過圖像處理和計算機圖形學方法來得到地毯填充路徑的矢量描述。整個過程需要經過圖像分割、邊緣提取、輪廓追蹤、曲線擬合和路徑填充等步驟。其中圖像分割的作用是提取圖像中的主要構成色，去除雜色點，得到邊界清晰的分割圖像，從而按顏色分離得到色塊圖。圖像分割質量的好壞，直接影響到后續圖像處理的效果。

傳統的圖像分割方法可分為基于閾值的分割方法[1]、基于區域的分割方法[2]和基于邊界的分割算法[3]。聚類理論在圖像分割中也取得了較好的效果，常用的聚類算法包括：K-means 聚類[4]、層次聚類[5]、譜聚類[6]、模糊C 均值[7]和蟻群聚類[8]。為了使分割算法適用于地毯制造，本文算法需要在不影響人眼感知的前提下，得到顏色種類少且邊界清晰的地毯分割圖像。本文先通過顏色量化算法對圖像進行預處理，合理減少顏色種類。本文首次將密度峰聚類算法應用于圖像分割，并結合應用背景對算法進行了改進。最終的實驗結果表明，改進后的算法能取得較好的彩色圖像分割效果。

2 Lab顏色空間

數字圖像通常是在RGB（紅、綠、藍）顏色空間對像素點進行描述，但人眼對RGB 顏色空間的感知是不均勻的。在表1 中，顏色2 與顏色1 在RGB 分量上的變化分別為30，-35，-35，顏色4 與顏色3 具有相同的變化量。但在人眼中，從顏色3 到顏色4 的變化更為強烈。因此需要將像素從RGB顏色空間變換到人眼感知均勻的顏色空間中。

表1 相同RGB差值下的顏色對比

Lab 顏色空間由國際照明委員會在1976 年提出。Lab 顏色空間是一種設備無關且人眼感知均勻的顏色空間。其中，L 為明度分量，a 和b 為顏色分量。從RGB顏色空間到Lab顏色空間的轉換公式[9]如下：

其中：

3 顏色量化

3.1 量化目的

圖1（a）按像素的RGB 值進行統計，顏色種類共有749種。圖像中的顏色種類過多會給聚類中心的選擇帶來困難。所以在進行聚類前，需要先在Lab顏色空間內對圖像進行顏色量化，合理減少圖像中的顏色種類。圖1（b）為圖像的局部放大圖，可以看到在色塊邊界處存在許多雜色點。通過顏色量化可以減少雜色點，有利于色塊的分離和減少地毯所需紗線的顏色種類。

圖1 簇絨地毯圖像

3.2 量化方法

常用的顏色量化方法有統一量化方法、頻度序列算法[10]、中位切割法[11]和八叉樹量化方法[12]。本文采用的顏色量化方法基于Lab顏色空間，根據色差最小原則對顏色種類進行歸并[13]。 X 和Y 是Lab顏色空間的兩種顏色，那么X 和Y 的色差定義如下：

式中，ΔL、Δa、Δb 為兩種顏色的Lab分量之差。根據色差最小原則，在地毯圖像中找出色差最小的兩個顏色A和B。假設用顏色C 來替代這兩種顏色，則替換后總的色差如下：

式中，NA、NB表示顏色A 和顏色B 在一幅圖像中的像素數。公式（8）又可以表示為：

為使總色差最小，三個分量應達到最小。令EL、Ea、Eb的導數為0，在導數為0 時總色差可取得最小值，求得顏色C 的Lab值：

根據上述顏色量化方法，可以得到將M 種顏色歸納合并為N 種顏色的量化方法：

步驟1 讀取圖像，將圖像中所有像素轉換到Lab顏色空間。得到圖像中的M 種顏色，以及每種顏色的像素數。

步驟2 遍歷所有的顏色，根據色差公式（7）找到色差最小的兩種顏色，并根據公式（13）～（15）求得替代顏色，用新顏色替換原有顏色，新顏色像素數為原先兩種顏色像素數之和。

步驟3 顏色更新完后，顏色種類M 減1。若M 大于N ，則跳回步驟2繼續執行，否則結束量化。

本文在對圖像進行量化時，將N 設為256。對圖1進行量化后得到的結果如圖2所示，圖像的顏色種類從749 減為256 種。由圖2（b）可知，量化后圖像還存在大量雜色點，需要通過聚類去除。

圖2 量化后簇絨地毯圖像

4 密度峰聚類應用與改進

聚類是指根據數據的相似性，將數據集劃分為不同的簇或類，是一種無監督的數據分類方法，在分類時沒有類別標簽。聚類算法在機器學習、模式識別等領域得到廣泛使用?；诿芏鹊拿芏确寰垲悾―ensity Peaks Clustering，DPC）算法是Rodriguez A 等人新提出的一種聚類算法[14]。密度峰聚類算法不需要指定聚類中心的數目和對聚類中心進行初始化，且不存在收斂速度慢等問題。該算法基于數據點間的歐氏距離進行計算，不受數據的維度影響，可以用來處理高維數據。鑒于密度峰聚類的以上優點，本文首次將密度峰聚類應用于圖像分割，并結合具體應用對算法進行了改進。

4.1 NBS距離

在介紹密度峰聚類算法前，首先需要引入NBS 距離的概念。為了衡量人眼對色差的感知程度，Miyahara等人提出了NBS 距離概念[15]。表2 給出了NBS 距離與人眼對色差感知的對應關系。當兩種顏色的NBS距離大于3.0時，人眼即認為兩種顏色色差是明顯的。

表2 NBS距離與人眼感知關系

NBS距離的計算需要先將RGB顏色空間中的點轉換到XYZ空間中，轉換的方法見公式（1）。再從XYZ空間變換到HVC空間，轉換到HVC空間的過程如下：

其中：

在計算兩種顏色A 和B 的NBS 值前，先根據上述計算方法轉化為HVC 值，分別記為( )

HAVACA和(HBVBCB)。則NBS距離的計算公式可以表示如下：

其中：

4.2 算法分析

密度峰聚類算法一共可以分為3 步：（1）計算所有的數據點得到決策圖；（2）通過決策圖人工找出數據集的密度峰，即聚類中心；（3）將數據集中的數據點分配到距離最近的聚類中心，得到聚類結果。作為密度峰的數據點應該具有以下2 個特點：（1）作為密度峰的數據點被密度相對較低的鄰近數據點包圍；（2）與密度更高的數據點之間存在較大的距離。所以尋找密度峰時主要是用到距離特征和密度特征。對于每個數據點i，只需要計算數據點i 自身密度和到達具有更高密度的數據點的最小距離。

通常DPC 算法在計算數據點間的距離時，采用的是歐氏距離。本文結合應用背景，為了符合人眼對色差的感知，計算數據點間的距離時采用的是NBS 距離。顏色節點i 的密度ρi定義為：

其中，dij是兩顏色節點i 和j 之間的NBS 距離，dNBS是人眼能明顯分辨色差的閾值，由表2 可知該值取3。從公式（22）可以看出在計算顏色節點i 的密度時，需要計算顏色節點i 和其余所有顏色節點間的NBS 距離。對于一幅有n 個像素點的圖像，計算完所有像素點的密度需要計算n(n-1)次，時間復雜度為O(n2)。而在一幅圖像中存在著許多RGB值重復的像素點。為了減少計算量，在計算密度前先建立關于顏色的鏈表，每個鏈表節點中含有顏色的RGB值和該顏色的像素數。在計算密度時就無需逐像素計算，只需要先統計像素信息再逐顏色節點計算。所以密度計算的相關公式（23）相應地修改如下：

其中Nj為顏色j 的像素個數。在計算完每種顏色的密度后，對所有的顏色節點按密度值進行降序排列。對排序完成后的顏色節點，還需要計算每個顏色節點的更高密度最小距離δi，定義如下：

距離δi是指比顏色節點i 具有更高密度的所有顏色節點與i 的最小距離。對于節點i，密度更高的顏色節點一定排在i 的前面。只需從第1個節點開始到第i-1 個節點結束，依次計算與節點i 的NBS距離，并取NBS距離的最小值即可。對于排在第一個的顏色節點，δi值取與其余顏色節點NBS距離的最大值，即max(dij)。

DPC 算法將密度和更高密度最小距離都相對較大的點作為聚類中心。為了更直觀地找到聚類中心，根據數據點繪制出決策圖。決策圖的橫軸為密度，縱軸為更高密度最小距離。由于圖像中的像素數較多，密度軸的數值會遠大于距離軸的數值，更高密度最小距離的權重過小，使得決策圖在選取聚類中心較為困難。因此對需要對密度進行歸一化處理，密度歸一化更新公式如下：

其中，K 是常數，取20，width 和height 為圖像寬度和高度方向的像素數。對量化后的圖2進行DPC聚類，得到圖3所示的決策圖。在決策圖中，右上角的數據點同時具有較大的密度和較大的更高密度最小距離，可以作為圖像的聚類中心。將這些數據點標記為相應的顏色，發現與圖像主要構成色一致。

圖3 決策圖

4.3 算法改進

決策圖上除了一些很明顯的密度峰外，一些數據點具有較大的ρ 和較小的δ ，或者是較小的ρ 和較大的δ。人工指定聚類中心容易多選或少選密度峰。為了使聚類中心被準確找出，改進后的算法引入了優先級變量λ，λ 的定義如下：

對每個顏色節點計算λ 的值，并按λ 的值進行降序排列。λ 值越大的顏色節點，成為聚類中心的可能性越大。將所有顏色節點關于λ 值的排序結果繪制成圖4，并將成為聚類中心可能性較大的顏色節點標記為相應的顏色。λ 值排序圖的排序結果如圖4所示，與圖1（a）主要構成色一致。本文利用排序圖，通過以下步驟自動確定出圖像的聚類中心：

步驟1 將λ值最大的顏色節點作為第一個聚類中心。

步驟2 按照λ 值排序的順序，計算下一個顏色節點與已確定為聚類中心的所有顏色節點的NBS距離。若該顏色節點與已有聚類中心的NBS距離均大于3，則添加到聚類中心，然后繼續重復步驟2。若顏色節點與已有聚類中心的存在NBS距離小于等于3，聚類中心尋找結束。

圖4 λ 值排序圖

5 實驗與結果分析

5.1 算法實現

整個算法實現可以分為以下幾個步驟：

步驟1 將圖像中所有像素轉換到Lab顏色空間。

步驟2 基于色差最小的原則，在Lab顏色空間內對圖像進行顏色量化。

步驟3 采用改進后的密度峰聚類方法對量化后的圖像進行聚類，找到聚類中心。

步驟4 將圖像所有像素值替換為NBS距離最小的聚類中心的像素值，得到最終的分割圖像。

5.2 圖像分割效果對比

K 均值聚類是彩色圖像分割最常用的算法，因此實驗將隨機K 均值聚類結果和DPC 聚類結果進行對比。K 均值算法存在著聚類中心數目需要人工指定和對初始聚類中心敏感的問題。為了使K 均值聚類取得較好效果，聚類中心數目均根據人眼感知到的顏色種類來確定，聚類中心的初始值則隨機生成。由圖5（b）的實驗結果可知，隨機初始化的K 均值聚類算法在進行色彩分割時，算法的圖像分割性能并不穩定，很大程度上依賴于初始聚類中心的初始化好壞。圖5（b）中除了第三和第四幅圖獲得了較為滿意的彩色圖像分割效果外，其余圖像都存在著聚類中心偏移的問題。K 均值算法雖然有時能獲得理想的彩色分割效果，但需要人工指定聚類中心數目且算法的性能不穩定。圖5（c）是使用本文方法的圖像分割聚類結果，首先利用最小色差顏色量化算法對圖像進行量化，再對量化后的圖像進行DPC 聚類分析。實驗結果顯示，改進后DPC 聚類算法能自動確定聚類中心數目，且具有穩定的彩色圖像分割性能，不存在對初始聚類中心敏感的問題。表3是對圖5中原圖和DPC 分割圖像的顏色種類統計，DPC 分割圖像的顏色種類與人眼感知的顏色種類一致，說明本文算法能有效減少圖像的顏色種類，從而減少地毯制造過程中所需的紗線顏色種類。

圖5 聚類結果分析

表3 圖5中原圖和DPC圖像顏色種類分析

6 結束語

本文針對簇絨地毯的彩色圖像，提出了一種基于顏色量化和密度峰聚類的圖像分割方法。首先在人眼均勻感知的Lab 顏色空間中基于色差最小原則對圖像進行量化。然后使用改進后的密度峰聚類DPC 算法，對地毯圖案進行圖像分割。實驗結果表明，DPC算法在對彩色圖像進行顏色分割時，能夠在不影響人眼感知的前提下有效減少圖像中的顏色。與經典的K 均值圖像分割算法相比，本文的圖像分割算法不需要人工指定聚類中心數目，并且圖像分割性能穩定，能夠滿足地毯圖案有效減少顏色種類的需求。