劉娜　劉向陽

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

關鍵詞：測地距離;圖像分割數(shù);圖像自動分割;局部密度;偏移量

中圖分類號：TP 391.41? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?文獻標識碼：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

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

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

1? ?算法思路

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

第一步：超像素預處理;

第二步：使用超像素構造近鄰圖，求出近鄰圖中任意兩兩超像素點之間的測地距離;

第三步：計算超像素點的局部密度和偏移量;

第四步：設置超像素局部密度下限，根據每個點的偏移量和K-S假設檢驗確定偏移量下限;

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

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

2? ?圖像自動分割算法

2.1? ?生成超像素并計算超像素間的測地距離

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

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

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

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

2.2? ?局部密度和偏移量

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

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

其中dc為截斷距離，是算法中的可變參數(shù)，實驗中取數(shù)據集中所有兩點間距離值的1%-2%。當局部密度ρi的值算出后，令{ρ1，ρ2，…，ρn}是按從大到小排序的結果，偏移量δi定義為：

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

即當xi的局部密度最大時，δi表示D中與xi距離最大的超像素點到xi之間的距離;否則，δi表示在所有局部密度大于xi的超像素點中，與xi距離最小的那個超像素點到xi之間的距離。

因為劃分中心具有“與同一個區(qū)域中的大部分點距離較近”和“距離其他劃分中心較遠”的特點[10]，而ρ和δ這兩個指標恰好對應了這兩個特點。因此可以確定，劃分中心的ρ和δ指標的值均較大。本文算法先計算出每個超像素點的ρ，δ值，并從中選出ρ，δ值均明顯大于ρmin，δmin的超像素點作為劃分中心，確定了圖像最佳分割數(shù)，最后基于得到的劃分中心對圖像進行分割。

2.3? ?劃分中心的定義

DP算法[12]中提到了用γ = ρ × δ的值來確定劃分中心，因為劃分中心的ρ和δ指標的值均較大，所以DP算法中認為γ值異常大的點為劃分中心。圖1（g）為超像素點的γ值從大到小的排序圖，顯然從圖1（g）中只能看到一個γ值異常大的點，但是圖1（a）明顯分為前景和背景兩個部分。圖1（c）中紅星為原圖基于γ值確定的兩個劃分中心，而這兩個劃分中心都在背景上。這是因為原圖前景中超像素點的局部密度值小，導致它們的γ值較小，所以識別不出來前景中的劃分中心。本文算法單獨分析了ρ和δ指標，判斷超像素點是否為劃分中心。圖1（f）為δ分布圖，可以看出很多局部密度大的點偏移量卻很小，一些局部密度小的點偏移量卻很大。本文算法通過單獨分析ρ和δ指標之后，確定了原圖的劃分中心并進行圖像分割，如圖1（d）所示，可以看出能準確找到劃分中心點并且圖像的分割效果也很好。

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

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

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

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

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

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

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

2.4? ?K-S假設檢驗

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

δn（x）的經驗分布函數(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。

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

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

計算出數(shù)據集D當中每一個樣本點xi的局部

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

假設劃分中心有k個，定義每個劃分中心的標簽為L（xj），j = 1，…，k先將其余點按局部密度值大小排序，再依次將它們的標簽定義為：

L（xi ） = ■

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

3? ?試驗結果及分析

為了驗證本文圖像自動分割算法的性能，針對紋理圖像和自然圖像（如圖2）進行了圖像分割。

3.1? ?算法分析

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

圖2? ?原始圖像

圖3? ?偏移量 分布圖

圖4? ?超像素處理及劃分中心結果

圖5? ?圖像分割結果（其中白色線條為圖像分割邊界，紅星的編號是劃分中心點次序）

3.2? ?實驗結果及分析

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

圖6? ?部分實驗圖像及分割結果

表2? ?本文利用評價性指標確定圖像最佳分割數(shù)所得結果

4? ?結 論

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

參考文獻

[1]? ? 何俊，葛紅，王玉峰. 圖像分割算法研究綜述[J]. 計算機工程與科學，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.