王鵬宇，游有鵬，楊雪峰

南京航空航天大學(xué) 機電學(xué)院，南京210001

1 引言

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

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

2 Lab顏色空間

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

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

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

其中：

3 顏色量化

3.1 量化目的

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

圖1 簇絨地毯圖像

3.2 量化方法

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

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

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

為使總色差最小，三個分量應(yīng)達到最小。令EL、Ea、Eb的導(dǎo)數(shù)為0，在導(dǎo)數(shù)為0 時總色差可取得最小值，求得顏色C 的Lab值：

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

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

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

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

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

圖2 量化后簇絨地毯圖像

4 密度峰聚類應(yīng)用與改進

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

4.1 NBS距離

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

表2 NBS距離與人眼感知關(guān)系

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

其中：

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

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

其中：

4.2 算法分析

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

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

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

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

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

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

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

圖3 決策圖

4.3 算法改進

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

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

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

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

圖4 λ 值排序圖

5 實驗與結(jié)果分析

5.1 算法實現(xiàn)

整個算法實現(xiàn)可以分為以下幾個步驟：

步驟1 將圖像中所有像素轉(zhuǎn)換到Lab顏色空間。

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

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

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

5.2 圖像分割效果對比

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

圖5 聚類結(jié)果分析

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

6 結(jié)束語

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