基于局部密度和偏移量的圖像自動(dòng)分割算法

劉娜　劉向陽(yáng)

摘? ?要：圖像分割是計(jì)算機(jī)視覺領(lǐng)域的傳統(tǒng)問題，也是圖像分析和模式識(shí)別的關(guān)鍵組成部分。提出了一種不依賴于圖像分割數(shù)參數(shù)的圖像自動(dòng)分割算法?；诔袼亻g的測(cè)地距離，根據(jù)其定義的局部密度和偏移量，結(jié)合K-S假設(shè)檢驗(yàn)來分析圖像最佳分割數(shù)，并給出了圖像自動(dòng)分割算法。大量圖像分割的實(shí)驗(yàn)結(jié)果表明：該方法可以準(zhǔn)確地對(duì)圖像進(jìn)行自動(dòng)分割，達(dá)到了較好的分割效果，相比其它方法，速度更快。

關(guān)鍵詞：測(cè)地距離;圖像分割數(shù);圖像自動(dòng)分割;局部密度;偏移量

中圖分類號(hào)：TP 391.41? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?文獻(xiàn)標(biāo)識(shí)碼：A

Automatic Image Segmentation Algorithm Based

on Local Density and Offset Distance

LIU Na？覮，LIU Xiang-yang

（School of Science，Hohai University，Nanjing，Jiangsu 211100，China）

Abstract：Image segmentation is a traditional problem in the field of computer vision and a key component of image analysis and pattern recognition. This paper proposes an automatic image segmentation algorithm that does not depend on the number of image segmentation parameters. Based on the geodesic distance between superpixels，according to its defined local density and offset distance，we combine the K-S hypothesis test to analyze the optimal segmentation number of the image and automatically segment the image. The experimental results of a large number of image segmentation show that the method can accurately segment the image automatically and achieve better segmentation effect. Compared with other methods，the speed is faster.

Key words：geodesic distance;image segmentation number ;automatic image segmentation;local density;offset distance

圖像分割是圖像處理的重要組成部分，其實(shí)質(zhì)就是按照像素的屬性進(jìn)行聚類的過程[1]。它將給定圖像分解成內(nèi)部特性相同、相互特征不同的區(qū)域并提取出感興趣的目標(biāo)的過程，在圖像工程中占有非常重要的位置?；诰垲惙治龅膱D像分割算法在圖像分割領(lǐng)域有著廣泛的應(yīng)用，在聚類分析中，最佳聚類數(shù)的確定問題一直是聚類有效性的關(guān)鍵問題。很多學(xué)者提出用聚類有效性指標(biāo)來評(píng)價(jià)聚類效果，并以此確定最佳聚類數(shù)。近年來，很多學(xué)者提出評(píng)估最佳聚類數(shù)的有效性指標(biāo)，比如，Calinski和Harabas提出了基于全部樣本的類內(nèi)離差矩陣和類間離差矩陣測(cè)度的CH指標(biāo)[2];Dudoit和Fridlyand提出了基于全部樣本的類內(nèi)離差矩陣測(cè)度的KL指標(biāo)[3];Kapp等人[4]基于概率統(tǒng)計(jì)思想，使用類內(nèi)數(shù)據(jù)點(diǎn)的in-group比例來評(píng)價(jià)聚類結(jié)果，提出了IGP指標(biāo);還有組內(nèi)平方誤差和BWP指標(biāo)[5]等。也有學(xué)者提出運(yùn)用一些信息準(zhǔn)則，如貝葉斯信息準(zhǔn)則（BIC）和Akiake信息準(zhǔn)則（AIC）[6]等確定分類數(shù)。Figueiredo和Jain[7]開發(fā)了一種估計(jì)K的新方法，使用最小信息長(zhǎng)度（MML）標(biāo)準(zhǔn)和高斯混合模型（GMM），這種方法的新穎之處在于它將估計(jì)和模型選擇集成在單個(gè)算法中，而不是使用模型選擇標(biāo)準(zhǔn)從一組預(yù)先估計(jì)的候選模型中選擇一個(gè)。2014年，Andr Fujita和Daniel[8]開發(fā)了一種名為斜率統(tǒng)計(jì)的新方法，它不需要使用剪影索引進(jìn)行密集計(jì)算，由于嚴(yán)格的數(shù)據(jù)分布假設(shè)，這僅適用于狹窄的應(yīng)用。雖然上述算法可以在一定程度上幫助找到適當(dāng)?shù)拇財(cái)?shù)，但時(shí)間成本相當(dāng)高，并且只有在導(dǎo)出聚類結(jié)果后，才能通過迭代此算法確定適當(dāng)?shù)木垲悢?shù)。 此外大多數(shù)方法假設(shè)數(shù)據(jù)符合高斯分布的混合，但是大多數(shù)數(shù)據(jù)集更復(fù)雜，導(dǎo)致這些方法的性能較弱。

針對(duì)不依賴于圖像分割數(shù)參數(shù)的圖像分割，提出了一種基于局部密度和偏移量的圖像自動(dòng)分割算法。首先給出了測(cè)地距離的定義及計(jì)算方法，然后定義了局部密度和偏移量這兩個(gè)指標(biāo)，通過K-S假設(shè)檢驗(yàn)找到滿足條件的劃分中心點(diǎn)，最后基于確定的劃分中心對(duì)圖像進(jìn)行分割。和傳統(tǒng)方法相比，這種方法的優(yōu)點(diǎn)在于：傳統(tǒng)方法需要通過對(duì)不同分割結(jié)果進(jìn)行比較才能得到圖像最佳分割數(shù)，而本文算法可以直接得到圖像最佳分割數(shù)，更好地減少了圖像分割算法中人為選取參數(shù)的麻煩，大大的減少了計(jì)算量。

1? ?算法思路

本算法是基于RGB彩色空間，對(duì)所有RGB圖像都可進(jìn)行分割。對(duì)RGB圖像的分割不再基于像素，而是以超像素為基本單元。超像素其實(shí)就是將具有相似紋理、顏色、亮度等特征的相鄰像素進(jìn)行合并后的圖像塊。采用超像素的圖像分割算法后，可以消除像素間的冗余，大大降低后續(xù)圖像處理任務(wù)的成本，加快圖像識(shí)別的速度。本文算法主要分為以下幾個(gè)步驟進(jìn)行，首先是對(duì)圖像進(jìn)行超像素預(yù)處理，生成近鄰圖，定義相鄰超像素之間的距離，計(jì)算兩兩超像素之間的測(cè)地距離[9];然后求出每個(gè)超像素點(diǎn)的局部密度和偏移量，再選取局部密度和偏移量的下限來確定劃分中心點(diǎn)，最后基于這些劃分中心對(duì)圖像進(jìn)行分割。本文算法的步驟如下：

第一步：超像素預(yù)處理;

第二步：使用超像素構(gòu)造近鄰圖，求出近鄰圖中任意兩兩超像素點(diǎn)之間的測(cè)地距離;

第三步：計(jì)算超像素點(diǎn)的局部密度和偏移量;

第四步：設(shè)置超像素局部密度下限，根據(jù)每個(gè)點(diǎn)的偏移量和K-S假設(shè)檢驗(yàn)確定偏移量下限;

第五步：確定局部密度和偏移量都大于下限的點(diǎn)就是劃分中心點(diǎn);

第六步：將其余點(diǎn)歸類到比它們局部密度更大、測(cè)地距離最近的超像素點(diǎn)所屬的類別中，完成圖像分割。

2? ?圖像自動(dòng)分割算法

2.1? ?生成超像素并計(jì)算超像素間的測(cè)地距離

2012年Achanta等人提出了簡(jiǎn)單的線性迭代聚類算法（SLIC）[10]，本算法利用SLIC算法將圖像分割成超像素圖像，將每個(gè)超像素看成圖像處理的基本單元。認(rèn)為相鄰的超像素間有邊相鄰，所有超像素點(diǎn)就可以構(gòu)成近鄰圖，在近鄰圖中相鄰的兩兩超像素點(diǎn)之間的距離dij定義如下：

dij = （d1 + λd2） × g? ? ? ?（1）

其中d1，d2分別表示超像素Ci和Cj之間的顏色距離、紋理距離（采用Hausdorff距離），為紋理距離的權(quán)重，g為超像素Ci和Cj之間的方向梯度，本文算法是用RGB圖像函數(shù)的一階差商近似代替方向梯度，方向梯度反映了相鄰超像素間的邊界。

針對(duì)圖像分割定義中區(qū)域的連通性要求，以及更好的度量?jī)蓛沙袼亻g的相似性，引入了測(cè)地距離[9]?；谙噜彸袼攸c(diǎn)之間的距離，對(duì)于不相鄰的超像素點(diǎn)，是計(jì)算它們之間的測(cè)地距離。首先將相鄰超像素間的距離作為它們之間邊的權(quán)重，再使用Dijkstra算法[11]找出不相鄰超像素點(diǎn)間的最短路徑，最后將計(jì)算出這個(gè)最短路徑的長(zhǎng)度作為它們之間的測(cè)地距離?；诔袼亻g的測(cè)地距離，下一步就要計(jì)算每個(gè)超像素點(diǎn)的局部密度和偏移量。

2.2? ?局部密度和偏移量

2014年Alex Rodriguez在新聚類算法（DP算法）中提出了局部密度ρ和偏移量δ的概念[12]。對(duì)于局部密度和偏移量這兩個(gè)指標(biāo)的計(jì)算，首先要計(jì)算出超像素點(diǎn)集D = {x1，x2，…，xn}中任意兩點(diǎn)間測(cè)地距離dij，再將超像素點(diǎn)的局部密度ρi定義為“數(shù)據(jù)集中到該點(diǎn)距離小于截?cái)嗑嚯xdc的數(shù)據(jù)點(diǎn)個(gè)數(shù)”，最后根據(jù)高斯核函數(shù)計(jì)算局部密度值。本文采用高斯核函數(shù)計(jì)算局部密度，這樣計(jì)算不同數(shù)據(jù)點(diǎn)具有相同的局部密度值的概率會(huì)更小。具體計(jì)算公式為：

ρi = ■e■? ? ? ? （2）

其中dc為截?cái)嗑嚯x，是算法中的可變參數(shù)，實(shí)驗(yàn)中取數(shù)據(jù)集中所有兩點(diǎn)間距離值的1%-2%。當(dāng)局部密度ρi的值算出后，令{ρ1，ρ2，…，ρn}是按從大到小排序的結(jié)果，偏移量δi定義為：

δi = ■（dij），i = 1■（dij），i > 1? ? ? ? （3）

即當(dāng)xi的局部密度最大時(shí)，δi表示D中與xi距離最大的超像素點(diǎn)到xi之間的距離;否則，δi表示在所有局部密度大于xi的超像素點(diǎn)中，與xi距離最小的那個(gè)超像素點(diǎn)到xi之間的距離。

因?yàn)閯澐种行木哂小芭c同一個(gè)區(qū)域中的大部分點(diǎn)距離較近”和“距離其他劃分中心較遠(yuǎn)”的特點(diǎn)[10]，而ρ和δ這兩個(gè)指標(biāo)恰好對(duì)應(yīng)了這兩個(gè)特點(diǎn)。因此可以確定，劃分中心的ρ和δ指標(biāo)的值均較大。本文算法先計(jì)算出每個(gè)超像素點(diǎn)的ρ，δ值，并從中選出ρ，δ值均明顯大于ρmin，δmin的超像素點(diǎn)作為劃分中心，確定了圖像最佳分割數(shù)，最后基于得到的劃分中心對(duì)圖像進(jìn)行分割。

2.3? ?劃分中心的定義

DP算法[12]中提到了用γ = ρ × δ的值來確定劃分中心，因?yàn)閯澐种行牡摩押挺闹笜?biāo)的值均較大，所以DP算法中認(rèn)為γ值異常大的點(diǎn)為劃分中心。圖1（g）為超像素點(diǎn)的γ值從大到小的排序圖，顯然從圖1（g）中只能看到一個(gè)γ值異常大的點(diǎn)，但是圖1（a）明顯分為前景和背景兩個(gè)部分。圖1（c）中紅星為原圖基于γ值確定的兩個(gè)劃分中心，而這兩個(gè)劃分中心都在背景上。這是因?yàn)樵瓐D前景中超像素點(diǎn)的局部密度值小，導(dǎo)致它們的γ值較小，所以識(shí)別不出來前景中的劃分中心。本文算法單獨(dú)分析了ρ和δ指標(biāo)，判斷超像素點(diǎn)是否為劃分中心。圖1（f）為δ分布圖，可以看出很多局部密度大的點(diǎn)偏移量卻很小，一些局部密度小的點(diǎn)偏移量卻很大。本文算法通過單獨(dú)分析ρ和δ指標(biāo)之后，確定了原圖的劃分中心并進(jìn)行圖像分割，如圖1（d）所示，可以看出能準(zhǔn)確找到劃分中心點(diǎn)并且圖像的分割效果也很好。

（a）原圖;（b）超像素預(yù)處理（其中白色紋理是超像素邊界）;

（c）基于γ值確定的劃分中心點(diǎn)（其中紅星表示中心點(diǎn)）;

（d）本文算法確定的劃分中心（其中白色線條為圖像分割邊界）;

（e）原圖的ρ值（從大到小排序）;（f）原圖的δ值（按ρ值大小排序）;

（g）原圖的γ值（從大到小排序）;（h）原圖的δ值（從大到小排序）

圖1? ?基于不同方法的劃分中心定義

對(duì)于ρmin的選取，應(yīng)該比大部分超像素點(diǎn)的ρ值大。因?yàn)閳D像中有些區(qū)域比較小，超像素點(diǎn)局部密度也較小，如圖1（a）中的飛機(jī)區(qū)域。但ρ值特別小的超像素點(diǎn)可能是噪聲點(diǎn)，不能作為劃分中心。本文算法取數(shù)據(jù)集中所有點(diǎn)的局部密度值的a%作為ρmin，通過實(shí)驗(yàn)得出a%的取值大約在50%-75%。對(duì)于δmin的選取，首先經(jīng)過大量數(shù)據(jù)分析可得，數(shù)據(jù)點(diǎn)的δ值大致服從指數(shù)分布。我們將δ值從大到小排序，再使用柯爾莫哥洛夫假設(shè)檢驗(yàn)（K-S假設(shè)檢驗(yàn)）做統(tǒng)計(jì)量分析選取δmin。即：選取δmin使得在區(qū)間[0，δmin]上所有數(shù)據(jù)點(diǎn)的δ值都滿足指數(shù)分布，大于δmin的數(shù)據(jù)點(diǎn)的性質(zhì)顯然與其他數(shù)據(jù)點(diǎn)不同，因此這些點(diǎn)可以作為劃分中心。

2.4? ?K-S假設(shè)檢驗(yàn)

將K-S假設(shè)檢驗(yàn)應(yīng)用在δmin的選取上，通過假設(shè)檢驗(yàn)找到不符合指數(shù)分布的數(shù)據(jù)點(diǎn)，確定臨界點(diǎn)δmin。設(shè)δn（x）是隨機(jī)樣本觀察值經(jīng)驗(yàn)分布函數(shù)，樣本量為n;F0（x）是一個(gè)特定的理論分布函數(shù)。定義D = δn（x） - F0（x），如果對(duì)于每一個(gè)x值，δn（x）與F0（x）都十分接近，則表明經(jīng)驗(yàn)分布函數(shù)的擬合程度很高，認(rèn)為樣本數(shù)據(jù)來自服從該理論分布的總體。

δn（x）的經(jīng)驗(yàn)分布函數(shù)為：

δn（x） = ■■I{xi ≤x}? ? ? ? （4）

其中I{xi ≤x} = 1，xi≤x0，otherwise。

δn（x）的理論分布函數(shù)為：

F0（x） = F（x;λ）n = （1 - eλx）n? ? ? ?（5）

其中λ = [E（δ）]-1。

再計(jì)算統(tǒng)計(jì)量Dmax = maxδn（x） - F0（x），根據(jù)給定的顯著性水平α和樣本數(shù)據(jù)個(gè)數(shù)n確定樣本的臨界值Dα，最后確定符合條件的δmin。

2.5? ?確定劃分中心及圖像分割

計(jì)算出數(shù)據(jù)集D當(dāng)中每一個(gè)樣本點(diǎn)xi的局部

密度ρi和偏移量δi。根據(jù)分布圖，我們可以直觀地了解每個(gè)數(shù)據(jù)點(diǎn)符合劃分中心性質(zhì)的程度，ρ和δ均較大的點(diǎn)則是符合劃分中心性質(zhì)的點(diǎn)。因此選取ρmin和δmin后，就可以確定劃分中心集為C = {xj | ρj > ρmin，δj > δmin}，該集合中的點(diǎn)被稱為劃分中心。

假設(shè)劃分中心有k個(gè)，定義每個(gè)劃分中心的標(biāo)簽為L(zhǎng)（xj），j = 1，…，k先將其余點(diǎn)按局部密度值大小排序，再依次將它們的標(biāo)簽定義為：

L（xi ） = ■

將其余點(diǎn)按照局部密度大小依次歸類到比它們局部密度更大、測(cè)地距離最短的超像素點(diǎn)所屬的類別中，即可完成圖像的分割。

3? ?試驗(yàn)結(jié)果及分析

為了驗(yàn)證本文圖像自動(dòng)分割算法的性能，針對(duì)紋理圖像和自然圖像（如圖2）進(jìn)行了圖像分割。

3.1? ?算法分析

實(shí)驗(yàn)中將圖2（a）超像素個(gè)數(shù)設(shè)為K=800，圖2（b）超像素個(gè)數(shù)設(shè)為K=3000，選取原始圖像中局部密度值前65%的超像素點(diǎn)，將它們的 值從大到小排列得到散點(diǎn)圖，如圖3所示。然后通過K-S假設(shè)檢驗(yàn)對(duì)δ值做統(tǒng)計(jì)量分析。將δ值在bins（實(shí)驗(yàn)中取值為8至100 ）個(gè)區(qū)間中計(jì)算直方圖分布，確定偏移量下限δmin。圖4顯示了圖像的劃分中心。圖5顯示了圖像分割結(jié)果，可以看出本文算法可以準(zhǔn)確地得到劃分中心，并且分割效果較好。

圖2? ?原始圖像

圖3? ?偏移量 分布圖

圖4? ?超像素處理及劃分中心結(jié)果

圖5? ?圖像分割結(jié)果（其中白色線條為圖像分割邊界，紅星的編號(hào)是劃分中心點(diǎn)次序）

3.2? ?實(shí)驗(yàn)結(jié)果及分析

為了驗(yàn)證本文算法的可行性和有效性，選取了大量的圖像進(jìn)行了分割實(shí)驗(yàn)，同時(shí)還利用了評(píng)價(jià)性指標(biāo)來確定圖像最佳分割數(shù)，實(shí)驗(yàn)中采用CH指標(biāo)[2]和Dunn指標(biāo)[13]，最后再與本算法結(jié)果進(jìn)行比較。圖6為本算法部分實(shí)驗(yàn)圖像及分割結(jié)果，從圖6中可以看出本算法能比較準(zhǔn)確的找到劃分中心，分割效果也比較好，分割邊界也比較清楚。從表1中可以看出，本算法的實(shí)驗(yàn)結(jié)果與評(píng)價(jià)性指標(biāo)的實(shí)驗(yàn)結(jié)果相比較，確定的最佳分割數(shù)更準(zhǔn)確，計(jì)算時(shí)間比用評(píng)價(jià)性指標(biāo)算法也少很多。

圖6? ?部分實(shí)驗(yàn)圖像及分割結(jié)果

表2? ?本文利用評(píng)價(jià)性指標(biāo)確定圖像最佳分割數(shù)所得結(jié)果

4? ?結(jié) 論

提出了一種基于局部密度和偏移量圖像分割算法。實(shí)驗(yàn)仿真結(jié)果表明，提出的方法有較好的分割效果。綜合來看，本算法比傳統(tǒng)方法計(jì)算量小，偶然性小，且省去了使用多種算法、多種指標(biāo)和必須分析一些分割結(jié)果的麻煩。但也存在許多難以解決的異常結(jié)果，例如紋理差別特別大的圖像無法準(zhǔn)確確定分割數(shù)。下一步需改進(jìn)該算法，使算法所得的圖像分割更準(zhǔn)確。

參考文獻(xiàn)

[1]? ? 何俊，葛紅，王玉峰. 圖像分割算法研究綜述[J]. 計(jì)算機(jī)工程與科學(xué)，2009，31（12）：58—61.

[2]? ?CALINSKI R B，HARABASZ J. A dendrite method for cluster analysis[J]. Communications in Statistics，1974，3（1）：1—27.

[3]? ?DUDOIT S，F(xiàn)RIDLYAND J. A prediction-based resampling method for estimating the number of clusters in a dataset[J]. Genome Biology，2002，3（7）：1—21.

[4]? ? KAPP A V，TIBSHIRANI R. Are clusters found in one dataset present in another dataset[J].Biostatistics，2007，8（ 1）：9—31.

[5]? ? ZHOU S B，ZHEN X U. New method for determining optimal number of clusters in K-means clustering algorithm [J]. Journal of Computer Applications，2010，30（8），1995—1998.

[6]? ? XIE C H，CHANG J Y，LIU Y J. Estimating the number of components in gaussian mixture models adaptively for medical image[J].Optik-International Journal for Light and Electron Optics，2013，124（ 23）：6216—6221.

[7]? ? FIGUEIREDO M A，JAIN A K.Unsupervised learning of finite mixture models[J]. Pattern Analysis and Machine Intelligence，2002，24（3）：381—396.

[8]? ? FUJITA A，TAKAHASHI D Y，Patriota A G.. A non-parametric method to estimate the number of clusters[J]. Computational Statistics & Data Analysis，2014（73）：27—39.

[9]? ? CRIMINISI A，SHARP T，ROTHER C，et al. Geodesic image and video editing[J].ACM Transactions on Graphics，2010，29（5）：1—5.

[10]? ACHANTA R，SHAJI A，SMITH K，et al. SLIC? superpixels compared to state-of-the-art superpixel methods[J]. IEEE Transactions on Pattern Analysis & Machine Intelligence，2012，34（11）：2274—2282.

[11]? DIJKSTRA E W . A note on two problems in connexion with graphs[J]. Numerische Math，1959，（1）：269—271.

[12]? RODRIGUEZ A，Alessandro. Supplementary materials for clustering by fast search and find of density peaks[J]. Science，2014，344（6191）：1492—1498.

[13]? DEXNER H，HORN M，STREEK A，et al. Laser micro sintering：a new method to generate metal and ceramic parts of high resolution with sub-micrometer powder[J]. Virtual and Physical Prototyping，2008，3（1）：3—11.