基于Dip-dist算法的區(qū)域合并圖像分割*

張 亭 陳 柳 王嘉偉 文篤石

（西安郵電大學(xué)計算機學(xué)院 西安 710121）

1 引言

圖像分割是一項比較重要的圖像處理技術(shù)，其是模式識別、計算機視覺、圖像處理領(lǐng)域中的基礎(chǔ)和關(guān)鍵，在圖像處理領(lǐng)域占有舉足輕重的地位［1～2］。圖像分割的質(zhì)量直接影響到圖像分析與理解的效果［3］。圖像分割就是將目標(biāo)圖像劃分成若干個特定的具有獨特性質(zhì)的區(qū)域或模塊，并使這些特征在同一區(qū)域內(nèi)呈現(xiàn)相似性，而在不同區(qū)域間呈現(xiàn)出明顯的差異性，并且從這些區(qū)域中提取出有價值的或者感興趣內(nèi)容的技術(shù)與過程，基于此才可以進一步對它們進行理解以及對圖像進行分析［4～5］。圖像分割的最終目的是對圖像中不同區(qū)域的目標(biāo)對象進行檢測、特征提取以及分類識別。圖像分割是圖像處理技術(shù)領(lǐng)域中一個至關(guān)重要的技術(shù)［6～9］，因為它是作為圖像處理的前期步驟，分割的好壞直接影響到后續(xù)處理過程的結(jié)果，如特征提取，目標(biāo)識別等。在實際應(yīng)用中，圖像分割再眾多領(lǐng)域中起到了關(guān)鍵的作用，隨著人們對圖像分割技術(shù)越來越深入的研究，圖像分割技術(shù)已經(jīng)廣泛應(yīng)用于各個領(lǐng)域，如通信、軍事、遙感圖像分析、醫(yī)學(xué)診斷治療、智能交通、農(nóng)業(yè)現(xiàn)代化以及工業(yè)自動化等。同樣，在學(xué)術(shù)研究領(lǐng)域中，圖像分割也是一項比較前沿而且具有重大意義的研究課題，圖像分割技術(shù)的研究在很大程度上推進了人工智能，機器學(xué)習(xí)等學(xué)科的發(fā)展與成熟。

Dip-test算法是Dip-dist算法的前身，由Engelman和Hartigan（1969）［10］提出的相關(guān)測試將樣本分為兩個子集，最大化兩個子集，采用不同方法從法線采樣似然比，而零假設(shè)的均值相等。測試統(tǒng)計量最大的所有部門的似然比。該分布是漸近正態(tài)的（Hartigan，1978）［11］，統(tǒng)計量很容易計算，但當(dāng)雙峰替代方案不是正常混合時，測試將無法正常進行。

J.B.Kruskal（1971）［12］等提出了基于連續(xù)順序統(tǒng)計間隔的測試，但該測試要求事先規(guī)定兩種模式。基于間隔的另一種測試使用雙峰分布，有一個很大的間隔伴隨著任何一方的許多小間隔，在Hartigan（1977）［13］中描述過，在一維情況下，類似的想法打破了鏈路上的最小生成樹，使得大量的相鄰小鏈路將兩個數(shù)量相鄰的小鏈接中的至少一個用作檢驗統(tǒng)計量。同樣地，在所有不相交的單個連接集群對（Hartigan，1985）［14］之間取較小的集群的最大。

2 超像素

超像素由一些位置相鄰，顏色、亮度、紋理等一些特征相似的像素點組成的小區(qū)域，這些小區(qū)域都保留了進一步分割圖像的有效信息，且一般不會破壞圖像中物體的邊緣信息。一般用SLIC算法生成超像素。我們的方法初始階段需要計算大量的超像素，這些小的、緊湊的和視覺上同質(zhì)的區(qū)域中的圖像的超分割?；谖墨I［15］中的比較結(jié)果，SLIC超像素分割提供了一個快速有效的選擇，因此我們在本文使用此方法對圖像做初分割。

2.1 SLIC（Simple Linear Iterative Clustering）算法

首先將RGB顏色轉(zhuǎn)換為五維的CLE-LAB顏色空間，除了記錄LAB顏色空間下的像素點還有該像素點的坐標(biāo)（x，y）。

算法實現(xiàn)過程：對于包含有N個像素點的圖像而言，如果對這幅圖像聚類為K個超像素塊（該算法只設(shè)置一個參數(shù)，預(yù)分割的超像素塊的數(shù)量），每個超像素塊的大小為N/k，若每個超像素塊的長和寬分布均勻，那么每個超像素塊的邊長為（N/k）^0.5。

為了避免所選的像素中心點不在邊緣上或者噪聲點這中不合理的像素點，將找到的中心點和周圍8個像素點進行比較，找到其歐氏距離最小的點作為中心點。

接下來用K-means算法進行聚類。

將某一區(qū)域中獨立的像素點被標(biāo)記歸屬于某一快超像素中但是沒有合并，則需要重新歸類，找到與其相鄰的最大的超像素塊，來保證每個超像素快的完整性。

SLIC算法的優(yōu)點，生成的超像素如同細(xì)胞一樣緊湊整齊，鄰域特征比較容易表達(dá)；不僅可以分割彩色圖像還可以分割灰度圖像；默認(rèn)情況下只需要設(shè)置一個預(yù)分割的超像素的數(shù)量；在速度、生成超像素的緊湊度、輪廓保持方面都比較理想。

3 Dip-dist算法

Dip-dist算法用于評估數(shù)據(jù)集的聚類結(jié)構(gòu)［16］，即檢測一組數(shù)據(jù)是否為單峰分布，用于圖像分割則是將要合并區(qū)域的質(zhì)心被用來決定合并所產(chǎn)生區(qū)域的單峰性，最早的Dip-dist算法它首先要定義區(qū)域間的相似性（或距離）度量（例如基于平均顏色值）［17］。它的標(biāo)準(zhǔn)依賴于觀察者的概念，觀眾是一個數(shù)據(jù)對象，通過考慮觀察者到其他數(shù)據(jù)對象成對距離的集合來決定組的單峰性，然后使用單峰檢測來測試這組數(shù)據(jù)的密度以獲得單峰性。更具體地說，如果我們數(shù)據(jù)集的質(zhì)心視為觀察者并形成一個向量，其分量是觀察者與所有數(shù)據(jù)點的距離，那么這個距離向量的值的分布就可以揭示關(guān)于聚類結(jié)構(gòu)的信息。

在單一集群的情況下，距離的分布預(yù)計是單峰的，在兩個、甚至多個集群的情況下，距離的分布應(yīng)該呈現(xiàn)出兩種不同的模式，單峰或者多峰。每個模式包含每個集群的質(zhì)心到所有數(shù)據(jù)點的距離。因此對距離矢量的單峰性檢測將提供關(guān)于此集群的聚類結(jié)構(gòu)。

直觀地看，在邊界處的觀看者，其單峰性更明顯。所以我們將該集合數(shù)據(jù)集的質(zhì)心作為單獨的觀察者，計算其到每個觀眾的歐式距離。

本文中我們提出的是以四個觀察者開始，若四個不能合并，則減少為三個至兩個。以兩個觀察者為例，這兩個觀察者是被測試用于合并的兩個像素組的質(zhì)心（平均特征值），更具體地說是為了合并而測試的像素組，R是由R1和R2的并集得到的像素組。我們首先計算R1和R2的特征空間中相應(yīng)的質(zhì)心C1和C2。然后形成包含C1與R中的每個像素之間的特征空間中的距離的集合D1以及包含C2與R中的每個像素之間的特征空間中的距離的集合D2。接下來使用D1和D2檢查集合單峰性，如果兩個集合都是單峰的，則區(qū)域R被認(rèn)為是單峰的，并且R1和R2的合并認(rèn)為是成功的。若果發(fā)現(xiàn)集合D1和D2中至少有一個是多峰的，則區(qū)域R被認(rèn)為是多峰的，并且R1和R2的合并失敗。

4 實驗結(jié)果

圖1和圖2展示了兩塊圖像基于Dip-dist分割結(jié)果的單峰檢測，圖1檢測的結(jié)果是單峰，證明兩塊圖像可以合并，圖2檢測的結(jié)果是多峰則兩塊圖像不能合并。合并的過程是以增量聚類的過程進行合并，即通過增量聚類的過程導(dǎo)致更大的同質(zhì)區(qū)域。圖3和圖4展示的是三塊圖像合并的結(jié)果，圖5和圖6展示的是四塊圖像合并的結(jié)果。

圖7（a）和圖7（b），展示的是對一副圖像進行初分割和最終分割的結(jié)果。圖7的圖像來自眾所周知的Berkeley圖像數(shù)據(jù)集，為了測試我們所改進的方法，所選的圖像包含了各個顏色、物體。對于SLIC算法，從圖7（a）可以看出，SLIC分割算法在合并具有相似視覺物體的方面是很成功的。圖7（b）是我們所提出的基于Dip-dist算法的改進。

圖1 兩塊圖像合并檢測結(jié)果——可以合并

圖2 兩塊圖像合并檢測結(jié)果——不可以合并

圖3 三塊圖像合并檢測結(jié)果——可以合并

圖4 三塊圖像合并檢測結(jié)果——不可以合并

圖5 四塊圖像合并檢測結(jié)果——可以合并

圖6 四塊圖像合并檢測結(jié)果——不可以合并

5 結(jié)語

初始化做的超像素分割在速度和邊緣保持上都比較理想，所以為我們提供了一個快速有效的選擇，我們選擇的顏色空間是CLELAB，為我們提供五維的顏色的空間（l，a，b）以及像素點的坐標(biāo)值（x，y），超像素的數(shù)量作為SLIC顏色和空間差異的權(quán)重因字子。因此像素的特征向量是（l，a，b）向量，一個區(qū)域的質(zhì)心特征向量包括（l，a，b），質(zhì)心的特征向量到像素點的特征向量的距離是它們的歐氏距離。

圖7 圖像初始分割和最終分割結(jié)果

本文證明了相比于Dip-dist算法，速度上以及分割的正確性都有明顯的提升。本文將SLIC超像素分割的結(jié)果進行多塊區(qū)域合并，并將合并的結(jié)果以直方圖的形式表示，只需要檢測一次單峰性。首先進行四塊區(qū)域的合并，分別找到每塊區(qū)域的質(zhì)心，再計算其中一個質(zhì)心到整個四塊區(qū)域的像素點的歐氏距離，歐氏距離以直方圖的形式表示，更明顯地表達(dá)數(shù)據(jù)集的聚類結(jié)構(gòu)。若四個直方圖中有一個是呈多峰狀的則這四塊區(qū)域不是同質(zhì)性的。則接下來需要判斷三塊區(qū)域，同樣的方法，若三塊區(qū)域都呈現(xiàn)單峰狀，則通過聚類的過程導(dǎo)致更大的同質(zhì)區(qū)域。