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

張 亭 陳 柳 王嘉偉 文篤石

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

1 引言

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

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

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

2 超像素

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

2.1 SLIC（Simple Linear Iterative Clustering）算法

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

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

為了避免所選的像素中心點(diǎn)不在邊緣上或者噪聲點(diǎn)這中不合理的像素點(diǎn)，將找到的中心點(diǎn)和周?chē)?個(gè)像素點(diǎn)進(jìn)行比較，找到其歐氏距離最小的點(diǎn)作為中心點(diǎn)。

接下來(lái)用K-means算法進(jìn)行聚類(lèi)。

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

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

3 Dip-dist算法

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

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

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

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

4 實(shí)驗(yàn)結(jié)果

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

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

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

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

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

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

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

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

5 結(jié)語(yǔ)

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

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

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