一種基于加權(quán)切比雪夫距離的圖像分割方法

毛 鑫，蔡江輝，張素蘭

(太原科技大學 計算機科學與技術(shù)學院，太原 030024)

近年來計算機視覺受到了越來越多的關(guān)注，圖像分割作為計算機視覺的熱度也一度飆升。圖像分割的任務是將圖像分成若干個互不重疊的子區(qū)域，從而使得同一個子區(qū)域內(nèi)元素相似性較高，不同的子區(qū)域間元素相似性較低。傳統(tǒng)圖像分割方法[1]主要分為：基于區(qū)域、基于邊界、基于數(shù)學形態(tài)學、基于神經(jīng)網(wǎng)絡、基于活動輪廓模型、基于遺傳算法和基于圖論等。其中基于區(qū)域的分割方法，是按照對應的相似性度量將原始圖像分成不同的區(qū)域，主要包括種子區(qū)域生長法，區(qū)域分裂合并法、分水嶺算法等。

圖像分割技術(shù)得到了廣泛的應用，例如關(guān)于發(fā)現(xiàn)混合纖維網(wǎng)中纖維的分布情況，梁振江[2]在全局閾值法和局部自適應閾值法的基礎上對圖像分割算法進行了改進。王思怡[3]等人也針對井道圖像抽析問題提出了基于Grabcut算法的井道圖像抽析方法，它可以精確確定數(shù)據(jù)區(qū)域，同時可以迅速將目標和背景分離出來。肖曉明[4]等人也提出了一種基于圖像強度閾值和自適應切割的圖像增強方法。將圖像直方圖根據(jù)圖像亮度閾值信息分為亮區(qū)域直方圖和暗區(qū)域直方圖，使得增強后的圖像不僅有完整的細節(jié)像素信息，同時與原始圖像的內(nèi)容大程度一致。但上述算法都不同程度地存在一些局限性，例如基于Grabcut算法的井道圖像抽析方法使用Grabcut函數(shù)需要根據(jù)傳入的所需參數(shù)，進行前景與背景分離，并結(jié)合Otsu算法進行最終圖像分割，但是會因識別錯誤的邊界，產(chǎn)生誤分割現(xiàn)象。所以相似性度量方法的選取會直接影響整體圖像分割算法的效率。

在大多數(shù)圖像數(shù)據(jù)集采集過程中，往往會因為采集機器的材料屬性，工作環(huán)境，電子元器件等因素，或是周圍環(huán)境的亮度，潮濕度，背景等因素造成圖像中存在少量干擾真實圖像的噪聲信息。傳統(tǒng)濾波去噪方法例如算術(shù)平均濾波法和中位值平均濾波法，存在運行速度較慢，占用內(nèi)存較大等問題。并且傳統(tǒng)的圖像分割相似性度量僅僅局限于距離度量或是顏色空間的度量[5]，所獲得的圖像信息較為單一，使得一些重要的圖像信息容易被忽略。同時，相似性距離的度量方式會直接影響圖像分割算法的最后結(jié)果?；趥鹘y(tǒng)切比雪夫距離度量方式的圖像分割一般存在忽略各個像素信息分量的協(xié)方差，期望等不一致性的問題。

針對以上提出的局限性，本文提出了基于加權(quán)切比雪夫距離的圖像分割算法，解決了去噪過程中運行時間較長的問題，也在一定程度上改善了傳統(tǒng)切比雪夫距離的局限性。本文先將掃描到的像素矩陣進行閾值去噪，得到基于RGB顏色空間的特征向量，然后再使用加權(quán)切比雪夫距離公式進行相似性度量，其中權(quán)值被選擇為每個像素特征向量標準差的冪，標準差向量由GT數(shù)據(jù)[6]估算得到。最終將相似性度量得到的相似矩陣作為譜聚類算法的輸入，得出圖像分割結(jié)果圖像。

1 相關(guān)研究

1.1 加權(quán)切比雪夫距離

在數(shù)學中，切比雪夫距離是一種定義在向量空間上的度量方法。它也被稱為棋盤距離，即棋子從一個位置移到另一個位置需要走的步數(shù)大小。

切比雪夫距離可簡單理解為各坐標數(shù)值差的最大值。從數(shù)學的角度來說，一致范數(shù)(或上確界范數(shù))可以派生出切比雪夫距離。切比雪夫距離的應用場景十分廣泛，張琳[7]利用切比雪夫距離來建立模糊相似矩陣，并結(jié)合傳遞閉包法對學生的考試成績進行了聚類處理；楊威[8]等人提出了一種基于利用切比雪夫距離的密度計算方法與傳統(tǒng)Kmeans相結(jié)合，根據(jù)切比雪夫距離的計算方法來計算數(shù)據(jù)源中數(shù)據(jù)點的密度，不斷迭代，有效地提升了Kmeans算法的性能。傳統(tǒng)切比雪夫距離的公式如下：二維平面兩點A(x1,y1)與B(x2,y2)間的切比雪夫距離為式(1):

d12=max(|x1-x2|,|y1-y2|)

(1)

也可表示為式(2)：

(2)

加權(quán)切比雪夫距離在MS-VTA算法[9]中用于監(jiān)督分類處理，以最小切比雪夫距離確定了輸入像素的類別。本文將加權(quán)切比雪夫距離作為相似性度量方式，用于構(gòu)成對應圖像的相似矩陣。加權(quán)切比雪夫距離公式如下：

(3)

式(3)中，L代表圖像像素維數(shù),σ代表使用GT數(shù)據(jù)計算出的對應L維向量的標準差向量，dij為像素點i和像素點j的加權(quán)切比雪夫距離。

2 相似矩陣的構(gòu)造

相似矩陣的建立是ISWCD算法的核心步驟，包括兩個部分，第一部分是在RGB顏色空間中使用顏色空間的像素信息、梯度信息和鄰域信息進行閾值去噪處理，提取特征向量。第二部分中，使用加權(quán)切比雪夫距離對特征向量進行相似性度量。本文通過對去噪后RGB顏色空間上的像素特征向量進行加權(quán)切比雪夫距離的計算，得出最后的相似矩陣。

2.1 顏色空間

顏色空間是在標準情況下對色彩進行說明的一種方式，其獨立的三個特征r、g和b構(gòu)成了空間坐標。除RGB顏色空間之外，還有HSV、HSI、LAB等顏色空間，由于大多數(shù)的圖像信息保存在RGB顏色空間中，當使用其他顏色空間進行特征提取時，需要將空間模型相互轉(zhuǎn)換，從而增加實驗的計算成本。因此，選擇RGB顏色空間作為本文的顏色空間。

在RGB顏色空間中，首先將掃描到的數(shù)據(jù)圖像像素矩陣進行去噪處理；然后，根據(jù)輸入的mixb閾值分辨出梯度值突變的像素點的位置或是否為噪聲點。若像素點在鄰域內(nèi)或邊界上則保留；若為噪聲，則將該點刪除。

2.2 距離度量

為提高相似矩陣的精確性，對顏色空間的特征向量進行基于距離的相似性度量，常用的距離度量方式有歐式距離、曼哈頓距離、切比雪夫距離、歐式距離、馬氏距離、漢明距離、余弦距離等。本文選取了加權(quán)切比雪夫距離作為圖像分割距離度量方式，并與余弦距離和馬氏距離進行實驗結(jié)果的對比。

馬氏距離[10]D2是一種廣義的平方距離，基于多元正態(tài)分布理論，綜合考量三個參數(shù)：均方差、均值和協(xié)方差。馬氏距離能夠綜合整體的多元指標，從而對相應任務做出判定[11]，其在空氣檢測、材料資源探測、環(huán)境污染研究等方面有廣泛的應用。馬氏距離的核心計算公式為：

(4)

(5)

其中S為原始數(shù)據(jù)的協(xié)方差矩陣，表示為：

(6)

其中Skl計算公式為：

(7)

余弦距離[12]近年來廣泛應用于文本分類等多維空間中。例如將兩篇文章向量化，余弦距離可以生成兩篇文章向量的夾角，能夠避免較高維度下，由于文章長度不同而導致的計算距離不準確問題。兩個向量間的余弦距離公式如下：

其中dij為余弦距離，表示為：

(8)

其中φij計算公式為：

(9)

3 基于加權(quán)切比雪夫距離的圖像分割算法ISWCD

本節(jié)將對ISWCD圖像分割算法進行詳細介紹，3.1節(jié)闡述本算法的基本思想，并在3.2節(jié)詳細描述ISWCD算法步驟。

3.1 基本思想

本文提出一種基于加權(quán)切比雪夫距離的圖像分割算法，其步驟如下：首先，提取閾值去噪后的RGB顏色空間的特征向量；然后，使用加權(quán)切比雪夫距離計算相似矩陣；最后，將相似矩陣輸入到譜聚類算法中，得出圖像分割結(jié)果。

ISWCD算法的第一步是先將待處理原始圖像掃描至像素矩陣，同時獲得對應的梯度信息，因為梯度值突變的位置容易產(chǎn)生邊界點或噪聲點，所以當梯度值大于所設定的梯度閾值時，需要進行下一步識別，即將其鄰域空間分割成4*4的區(qū)域，然后，對鄰域內(nèi)的像素點個數(shù)進行統(tǒng)計，若大于所設定的鄰域閾值時，則說明該點位于區(qū)域內(nèi)；若等于閾值，則說明該點為邊界點；若小于閾值，則說明該點位噪聲點，需將這個點的像素信息刪除。遍歷處理過整個圖像之后，對得到的RGB像素矩陣進行特征提取，得到多個特征向量。其次將特征向量和加權(quán)切比雪夫距離計算公式(3)計算出對應的相似矩陣R.這里使用的是加權(quán)后的切比雪夫距離，相較于傳統(tǒng)的切比雪夫距離多了權(quán)值的計算。最后，對距離度量得到的相似矩陣進行譜聚類，得出圖像分割結(jié)果。聚類算法的輸入為相似矩陣R，其中rij代表i點與j點之間的相似性，數(shù)值的高低對應代表著相似程度的高低。

3.2 算法描述與分析

本文提出一種基于加權(quán)切比雪夫距離的圖像分割算法，第一步提取閾值去噪后的RGB顏色空間的特征向量，其中根據(jù)鄰域閾值mixb進行閾值去噪，第二步，將提取出的特征向量使用加權(quán)切比雪夫距離計算，得到對應的相似矩陣，最后，將相似矩陣輸入到譜聚類算法，使用knn計算相似矩陣R，由R計算度矩陣D和對應的拉普拉斯矩陣L，對L進行標準化處理D-1/2LD-1/2，對標準化后的矩陣進行特征值分解，然后將特征向量作為輸入進行K-means聚類，從而得到聚類結(jié)果即圖像分割結(jié)果。算法的偽代碼如下所示：

算法1 ISWCD算法(Image Segmentation based on Weighted Chebyshev Distance)輸入: 圖像D；鄰域閾值mixb

輸出：結(jié)果圖像ai

For給定圖像D像素點do

提取像素矩陣W

計算W中的梯度值h

IFh發(fā)生突變then

將附近區(qū)域按4*4鄰域進行分割，并計算鄰域內(nèi)像素個數(shù)q

IFq

該像素點為噪聲點，去除該點

得到處理后的像素矩陣W1

對W1進行特征提取，輸出由r值，g值和b值構(gòu)成的特征分量k.

For所有特征分量kdo

用公式(7)、(8)、(9)、(3)

計算出基于不同距離度量方式的三個相似矩陣R1,R2和R3；

將R1,R2和R3分別輸入到譜聚類中

ForR1,R2和R3do

Ri=Ri- diag(diag(R))

D=diag(sum(Ri)

L=D^(-.5)*R*D^(-.5)

找到前K個特征向量并排序，得到矩陣X

Xsq = Xuse.*Xuse

divmat=repmat(sqrt(sum(Xsq')'),1,2)

Y=Xuse./divmat

將歸一化后的矩陣Y輸入到Kmeans聚類中

輸出聚類結(jié)果圖像ai

本文提出的閾值去噪方法相較于常用的濾波去噪法計算速度更快，只需遍歷像素點并進行比對，若梯度突變則進行鄰域掃描，可以在完成任務的基礎上較大程度地減少計算難度。同時對RGB顏色空間進行特征提取也提高了整體算法的效率。為減少后續(xù)步驟的計算量，選取較大的像素矩陣中的對于圖像分割最有效的特征信息，從而實現(xiàn)對像素顏色空間的維數(shù)壓縮。

4 實驗分析

本文實驗環(huán)境為WINDOWS 10操作系統(tǒng)，Intel(R)Core(TM)i3-4030U的CPU和4.0GB內(nèi)存，從圖像分割的精確率和效率兩個方面對ISWCD算法進行評估。

4.1 數(shù)據(jù)描述

本文使用兩個數(shù)據(jù)集進行實驗,其中第一個數(shù)據(jù)集是Berkeley大學提供的BSDS300圖像數(shù)據(jù)集[13]，其中包含200張訓練圖，300張測試圖，分為color和gray兩個文件夾，保存格式為seg.第二個數(shù)據(jù)集是來自國際計算機競賽PASCAL VOC挑戰(zhàn)賽的VOC2012數(shù)據(jù)集，提供了類別層面和個體層面的標注，包含人、動物、交通工具等20個類別，該數(shù)據(jù)集適用于圖像分類，分割和檢測任務。BSDS300和VOC2012數(shù)據(jù)集描述如表1所示。

表1 數(shù)據(jù)集描述Tab.1 Descriptions of data sets

本文首先從兩個數(shù)據(jù)集中選出五張具有代表性的圖像如圖1所示，并利用其進行范例實驗。其中數(shù)據(jù)(a)是人像圖像，輪廓簡單，但亮度較低。數(shù)據(jù)(b)是動物圖像，皮色分布較為復雜，亮度中等。數(shù)據(jù)(c)、(d)和(e)都是環(huán)境圖像，但圖(c)側(cè)重于測試算法在圖像整體亮度低，輪廓較為模糊的情況下的魯棒性。圖(d)為光線正常的環(huán)境圖像，方便與其他環(huán)境系列圖像進行對比。圖(e)的圖像是受氣候影響較大時的數(shù)據(jù)圖像，測試的是有較多噪聲存在時算法的魯棒性。其圖像的具體數(shù)據(jù)描述如表2所示，包括數(shù)據(jù)的分辨率、位深度和圖像大小。

圖1 圖像A-EFig.1 ImageA-E

表2 五個圖像數(shù)據(jù)的描述Tab.2 Descriptions of five image data

4.2 精確率

本次實驗利用表1所示的兩個數(shù)據(jù)集將ISWCD算法與其他三個算法(Otsu、CDA、MDA)進行精確率比較。其中Otsu為圖像分割經(jīng)典算法，CDA和MDA是在ISWCD算法的基礎上使用不同的距離度量方式余弦距離(Cosine Distance Algorithm,CDA)和馬氏距離(Markov Distance Algorithm,MDA).參數(shù)mixb的初始化選取極大影響噪聲點識別的精確率，經(jīng)過多次實驗，mixb為15時去噪效果較好，所以將mixb初始值設為15.

精確率PA(Pixel Accuracy)表示分割正確的像素占總像素的比例，如公式(10)所示，其中，k表示分割區(qū)域的個數(shù)，Pij表示本屬于區(qū)域i但被分割為區(qū)域j的像素點數(shù)量，Pii表示分割正確的數(shù)量。

(10)

圖1中的五幅圖像數(shù)據(jù)在四種算法下的實驗結(jié)果如圖2-圖6所示，均包含四個子圖a、b、c和d，分別為對應圖像使用Otsu算法、MDA算法、CDA算法和ISWCD算法進行圖像分割的結(jié)果，圖6(e)為mixb=13時的ISWCD算法實驗結(jié)果。表4為四種算法在兩個數(shù)據(jù)集下的精確率均值。圖像A-E在四種算法下的分割精確率如表3和圖7所示，其中，ISWCD算法在數(shù)據(jù)C下分割的精確率較低，但是其精確率整體高于其他三個算法。由于圖像數(shù)據(jù)C整體亮度較低，圖像邊界較為模糊，因此在提取時像素信息時容易忽略接近于背景色的物體輪廓。

同時，由于圖像E中的干擾信息過多，ISWCD算法和Otsu算法都出現(xiàn)了不同程度的過分割現(xiàn)象，使得真正的目標信息受到一定程度的干擾。該圖像中的噪聲點較密集，需要降低mixb閾值的大小，將過于密集的區(qū)域進行鄰域去噪處理。而ISWCD算法可以通過重新設置閾值mixb，從而緩解過分割現(xiàn)象，同時體現(xiàn)出ISWCD算法的魯棒性。如圖6(e)所示，將mixb改為13后,過分割現(xiàn)象減輕，效果優(yōu)于mixb=15時的ISWCD算法和Otsu算法。

圖2-圖6中，因Otsu算法采用灰度處理，所以在最后的圖像分割結(jié)果中僅呈現(xiàn)出圖像輪廓和像素點位置信息。本文將RGB顏色空間的特征向量與距離度量方法綜合考量，保存了關(guān)鍵像素點的像素值大小，因此，ISWCD算法、CDA算法和MDA算法都在一定程度上保存了色彩信息。

圖2 圖像A的四種圖像分割算法結(jié)果Fig.2 Results of four image segmentation algorithms of image A

圖3 圖像B的四種圖像分割算法結(jié)果Fig.3 Results of four image segmentation algorithms of image B

圖4 圖像C的四種圖像分割算法結(jié)果Fig.4 Results of four image segmentation algorithms of image C

圖5 圖像D的四種圖像分割算法結(jié)果Fig.5 Results of four image segmentation algorithms of image D

圖6 圖像E的四種圖像分割算法結(jié)果Fig.6 Results of four image segmentation algorithms of image E

通過對比圖7、表3和表4中不同算法的精確率可知，加權(quán)切比雪夫距離呈現(xiàn)出的相似矩陣能夠更精確地提取出較多關(guān)鍵圖像信息，最終圖像分割的精確率較高。

表3 四種算法在圖像A-E下的精確率Tab.3 The accuracy of the four algorithms underimages A to E

圖7 四種算法在圖像A-E下的精確率Fig.7 The accuracy of four algorithms under images A to E

表4 四種算法在兩個數(shù)據(jù)集下的精確率Tab.4 The accuracy of four algorithms under two data sets

4.3 效率

為全方面評估圖像分割算法，本節(jié)將效率作為第二個評估參數(shù)。圖8和表5為四種算法在圖像A-D下的運行時間對比，表6為四種算法在數(shù)據(jù)集1、2下的運行時間對比。由統(tǒng)計結(jié)果可知，ISWCD算法的運行時間最短，效率明顯高于其它三種算法，CDA算法和MDA算法的圖像分割精確率較低，但其運行效率普遍高于Otsu算法。

由圖8和表5可知,圖像D的四種圖像分割算法運行時間普遍大于其他四幅圖像。圖像越大，掃描的像素矩陣越大，計算量增加，所以運行時間較長。因此，對像素矩陣進行特征提取能夠提高圖像分割速度。

圖8 四種算法在圖像A-E下的運行時間Fig.8 The running time of four algorithms under images A to E

表5 四種算法在圖像A-E下的運行時間(s)Tab.5 The running time of four algorithms under images A to E(s)

表6 四種算法在兩個數(shù)據(jù)集下的運行時間(s)Tab.6 The running time of four algorithms on two data sets(s)

5 結(jié)論

本文提出了一種基于加權(quán)切比雪夫距離的圖像分割算法，首先，對原始圖像進行閾值去噪處理，刪除檢測出的噪聲點；然后，在RGB顏色空間內(nèi)對像素矩陣進行特征提取，對提取出的特征向量進行加權(quán)切比雪夫距離度量，得出對應的相似矩陣；最后，根據(jù)相似矩陣通過譜聚類進行圖像分割，得到對應的結(jié)果圖像。實驗結(jié)果表明了本文方法的有效性,對部分圖像出現(xiàn)的過分割現(xiàn)象仍然需要進行進一步研究。