桂露，何紹勇

（四川大學(xué)計(jì)算機(jī)學(xué)院，成都 610065）

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

桂露，何紹勇

（四川大學(xué)計(jì)算機(jī)學(xué)院，成都 610065）

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

圖像分割；特征；圖算法

0 引言

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

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

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

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

對于非鄰域的分支，如果是同一表現(xiàn)形式的話，應(yīng)該是屬于同一部分，卻不能分在一個(gè)區(qū)域，這里，采用了全局特征CEDD，計(jì)算不同分支的特征，如果特征是一樣的，這應(yīng)該是同一分支，反之不是。

2 邊界判定

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

外部差異：

這里，最小的內(nèi)部差異：

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

3 算法

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

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

②開始于S0，每一個(gè)頂點(diǎn)都是一個(gè)單獨(dú)的分支。

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

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

⑤返回S=Sm。

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

①～⑤同上。

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

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

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

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

（2）使用基于顏色的邊的權(quán)重計(jì)算方法

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

圖1

（3）獲取CEDD特征

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

圖2

圖1和圖2對比就可以知道，第二個(gè)運(yùn)動(dòng)員的兩個(gè)手套就分為了同一個(gè)分支。

5 結(jié)語

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

參考文獻(xiàn)：

[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-），女，湖北咸寧人，碩士研究生，研究方向?yàn)閳D像檢索

何紹勇（1984-），男，云南昆明人，碩士研究生，研究方向?yàn)闊o線傳感器網(wǎng)絡(luò)

2014-11-20

2014-12-16