基于圖論和特征的圖像分割

桂露，何紹勇

（四川大學計算機學院，成都 610065）

基于圖論和特征的圖像分割

桂露，何紹勇

（四川大學計算機學院，成都 610065）

傳統的基于圖論的特征分割方法，使用圖的表示方法，定義一個量去測量兩個鄰域間是否有邊界，然后產生基于此量的分割算法，盡管此算法是貪心的，但它滿足全局要求。算法是線性的，在實際中運行速度很快。在此基礎上，提出用特征去處理所有的這些分支，計算分支之間的歐式距離，解決相同的非鄰域分支無法正確處理的問題。

圖像分割；特征；圖算法

0 引言

圖像分割的問題仍然是計算機視覺的巨大挑戰，它是對圖像中的每個像素加標簽的一個過程，這一過程使得具有相同標簽的像素具有某種共同視覺特性；簡化或改變圖像的表示形式，根據灰度、顏色、紋理和形狀等特征把圖像劃分成若干互不交迭的區域，并使這些特征在同一區域內呈現出相似性，而在不同區域間呈現出明顯的差異性，使得圖像更容易理解和分析。圖像分割通常用于定位圖像中的物體和邊界。

1 基于圖和特征提取的圖像分割

使用基于圖的方法去分割，無向圖G=（V，E），Vi∈V表示要被分割的點的集合，邊（Vi，Vj）∈E表示相鄰的點組成的邊，每條邊都有一個對應的邊的權重W（Vi，Vj），這是一個非負數，它代表兩個相鄰的元素Vi和Vj的相似度。

在圖像分割的方法中，分割S是對點V的分割，使得分割得到的每一部分C∈S，且C為連通的組件，形成了G'=（V，E'）。換句話說，任何分割都是由邊的集合E的子集形成的。有多種不同的方式去測量分割的質量，總體而言，我們希望的是在同一部分相同，在不同部分不同，這意味著，在相同部分，每兩個頂點之間的邊的權重相對而言小，在不同部分的邊相對而言大。

對于非鄰域的分支，如果是同一表現形式的話，應該是屬于同一部分，卻不能分在一個區域，這里，采用了全局特征CEDD，計算不同分支的特征，如果特征是一樣的，這應該是同一分支，反之不是。

2 邊界判定

在這一節中，我們定義了D，評估是否有證據表明邊界的兩個組成部分之間存在邊界。D是基于測量同一邊界的兩部分外部的差異相對于其兩部分內部各自的差異。我們定義內部差異：

外部差異：

這里，最小的內部差異：

|C|表示C的大小，K是一個常量。對于小的分量而言，我們需要邊界的更強烈的跡象。在實際中，K設置了一個觀量尺度，在這里，一個更大的K引起較大的部件的偏好。然而，K并不是一個最小的分支的大小，如果在兩個相鄰分支之間有較大的差異，更小的部分是被允許的。

3 算法

輸入是圖G=（V，E），有n個頂點，和m條邊，輸出是分割后的圖像的各個部分S=（C1，…，Cr）

①將圖中的所有邊按照非遞減的順序排列成（O1，…，Om）。

②開始于S0，每一個頂點都是一個單獨的分支。

③重復步驟④，對于q=1，2，…，m。

④由Sq-1建立Sq。讓Vi和=Vj表示第q條邊Oq=（vi，vj），如果vi和vj在Sq-1不同的分支，并且w（Oq）比它們分支內部的差異小，合并。

⑤返回S=Sm。

以上是傳統的方法，基于圖的圖像分割方法。然而，實際意義中，不是鄰域的兩個分支也可能屬于同一分支，但以上方法卻無法解決，因此，本文提出了一種新方法，在上面方法的基礎上，對每一個分支提取CEDD特征，將每一分支映射到特征空間，計算其相似度。

①～⑤同上。

⑥提取所有分支的CEDD特征。

⑦計算兩兩分支之間的歐式距離，若小于閾值k，這是同一分支。反之，輸出最后的分支。

4 實驗及結果

（1）數據結構，我們用圖的方法去表示要分割的圖片，同一個區域的點擁有同一個根節點，每個區域都用一顆樹去代替，多個區域就是多棵樹的森林。屬于同一個區域的像素點擁有同一個根節點。在判斷兩個區域是否合并的時候，使用了貪心策略，這個算法第一部分執行的時間與圖的邊是呈線性的。

（2）使用基于顏色的邊的權重計算方法

W（vi，vj）=|I（pi）-I（pj）|，這里I（pi）是每個像素的強度，一般而言，為了彌補數字化偽影，在計算邊的權重之前，采用高斯濾波器平滑圖像。通常采用高斯參數d=0.8，這對圖像并不會產生視覺上的變化，但可以幫助移除偽影。對于彩色圖片的第一部分，執行3次，分別為紅、綠、藍。本文認為若兩個像素點相鄰，它們在這3個平面都在同一分支，就認為其為同一分支，反之不是。如圖1所示。

圖1

（3）獲取CEDD特征

對于每一分支，分別獲取CEDD特征。如圖2所示。

圖2

圖1和圖2對比就可以知道，第二個運動員的兩個手套就分為了同一個分支。

5 結語

基于圖的圖像分割方法，只能對鄰域進行區分，對不相鄰的分支，無法計算。本文提出了一種新方法，在基于圖的圖像分割方法上，提取特征，將每一個分支映射到特征空間中，對每兩分支進行相似度計算，使得在不相鄰區域的相同分支有可能分到同一分支，得出的結果更加符合實際意義，為圖像分割算法開辟了新徑。

參考文獻：

[1] Jordi Freixenet，Xavier Mu，Joan Mart and Xavier Llad.Colour Texture Segmentation by Region-Boundary Cooperation[C].8th European Conference on Computer Vision，May 11～14，2004

[2] David R.Martin，Charless Fowlkes and Jitendra Malik.Learning to Detect Natural Image Boundaries Using Local Brightness，Color，and Texture

[3] Pedro F.Felzenszwalb，Daniel P.Huttenlocher.Efficient Graph-Based Image Segmentation.International Journal of Computer Vision September 2004，59（2）：167～181

[4] S.Arya and D.M.Mount.Approximate Nearest Neighbor Searching.Proc.4th Annual ACM-SIAM Symposium on Discrete Algorithms，1993：271～280

[5] G.Ausiello，P.Crescenzi，G.Gambosi，V.Kann，A.Marchetti Spaccamela and M.Protasi.Complexity and Approximation.Combinatorial Optimization Problems and their Approximability Properties，to Appear，Springer-Verlag，Berlin

Image Segmentation Based on Efficient Graph and Feature

GUI Lu，HE Shao-yong
（College of Computer Science,Sichuan University，Chengdu 610065）

Defines a predicate for measuring the evidence for a boundary between two regions using a traditional graph-based representation of the image.Develops an efficient segmentation algorithm based on this predicate,and shows that although this algorithm makes greedy decisions,it produces segmentations that satisfy global properties.The algorithm runs in time nearly linear in the number of graph edges and is also fast in practice.Extracts feature to deal with all of the components,then calculates the distance of the components,which can solve the similar components which is not neighboring can not be classified.

Image Segmentation;Feature;Graph

1007-1423（2015）02-0070-03

10.3969/j.issn.1007-1423.2015.02.018

桂露（1990-），女，湖北咸寧人，碩士研究生，研究方向為圖像檢索

何紹勇（1984-），男，云南昆明人，碩士研究生，研究方向為無線傳感器網絡

2014-11-20

2014-12-16