萬 君,吳旻倩

（1.江西廣播電視大學(xué) 江西 南昌 330046；2.南昌廣播電視大學(xué) 江西 南昌 330003）

淺析多層次自適應(yīng)算法在數(shù)字圖像分割中的應(yīng)用

萬 君1,吳旻倩2

（1.江西廣播電視大學(xué) 江西 南昌 330046；2.南昌廣播電視大學(xué) 江西 南昌 330003）

本文簡要的介紹了一種新的圖像分割方法，該方法對于分割灰度圖像有較高的效率和準(zhǔn)確率。

代數(shù)多層網(wǎng)格；數(shù)字圖像處理；圖像分割；AMG

1 序言

圖像分割是指把一幅圖像分成彼此不相交的若干個(gè)區(qū)域，其中每個(gè)區(qū)域內(nèi)的像素均有相似或一致的性質(zhì)，而任何兩個(gè)相鄰接的區(qū)域都不具有類似的性質(zhì)。圖像分割的目的就是要將目標(biāo)物體與背景區(qū)分開來，也就是找出圖像中物體與背景的邊界線。圖像分割鄰域的技術(shù)發(fā)展至今，已經(jīng)提出了多種分割算法。如基于形態(tài)學(xué)的分水嶺方法、基于梯度的圖像分割方法、區(qū)域增長等。本文著重介紹一種多層次自適應(yīng)圖象分割算法[1]。該算法是在一個(gè)來自于物理學(xué)的概念代數(shù)多層網(wǎng)格的基礎(chǔ)上提出的。

2 代數(shù)多層網(wǎng)格簡介

代數(shù)多層網(wǎng)格(AMG)[2]是一種近乎最優(yōu)的特殊的迭代途徑，在偏微分方程數(shù)值解中，當(dāng)離散網(wǎng)格步長h變小時(shí)，它的收斂速度并不減慢，而經(jīng)典的迭代法隨h的變小而變慢。因此，代數(shù)多重網(wǎng)格法的計(jì)算工作量僅與未知量的個(gè)數(shù)N成正比，比一般迭代法有效得多。

下面簡要的介紹代數(shù)多層網(wǎng)格的內(nèi)容。

考慮線性代數(shù)方程組

AU＝G,(1)式中:A是一個(gè)n×n矩陣,G是已知右端向量;U是未知向量。通過對矩陣A和向量U和G進(jìn)行重排,系統(tǒng)(1)可以表示為,(2)稱為虛擬細(xì)網(wǎng)格方程,其中下標(biāo)F和 C分別表示“細(xì)網(wǎng)格”和“粗網(wǎng)格”。為了實(shí)現(xiàn)標(biāo)準(zhǔn)的多重網(wǎng)格循環(huán),需要網(wǎng)格之間的轉(zhuǎn)換算子

以及粗網(wǎng)格算子A2。

在代數(shù)多重網(wǎng)格方法中,一般細(xì)網(wǎng)格方程表示為

粗網(wǎng)格方程表示為Am+1Um+1=Gm+1

其中,上標(biāo) m和 m+1分別相應(yīng)于“細(xì)網(wǎng)格”和“粗網(wǎng)格”。插值算子為

3 多層次自適應(yīng)算法簡介

多層次自適應(yīng)算法[3]是由Eitan Sharon和Achi Brandt在2006年在自然雜志上發(fā)表的針對分割灰度圖像而言的算法。該算法是自頂向下，由細(xì)到粗的執(zhí)行過程。具體流程如下圖1所示。

圖1 多層次自適應(yīng)算法流程圖

由上圖可知，這種算法是將圖像看成是節(jié)點(diǎn)的集合，每個(gè)節(jié)點(diǎn)代表一個(gè)像素。然后在這些節(jié)點(diǎn)中選取一些節(jié)點(diǎn)作為種子。根據(jù)種子和周圍節(jié)點(diǎn)的關(guān)聯(lián)權(quán)值劃分一部分節(jié)點(diǎn)到種子的集合中，其中，關(guān)聯(lián)權(quán)值和像素的亮度和強(qiáng)度有關(guān)。這樣形成一個(gè)小集合后，集合內(nèi)的節(jié)點(diǎn)都是強(qiáng)關(guān)聯(lián)的。然后繼續(xù)尋找與集合內(nèi)性質(zhì)類似的節(jié)點(diǎn)，擴(kuò)大集合。注意，種子不是只選一個(gè)，而是有幾個(gè)甚至更多，不同的種子開始根據(jù)不同的關(guān)聯(lián)權(quán)值生成不同的集合，集合和集合之間是弱關(guān)聯(lián)。這樣重復(fù)迭代執(zhí)行后，就會出現(xiàn)幾個(gè)或者更多的差異很大的集合 （重復(fù)執(zhí)行的停止條件是剩余節(jié)點(diǎn)小于1）。一般處理后剩2個(gè)集合差異最大（背景和目標(biāo)景物）。最后根據(jù)算法評估判斷出的突出部分就是需要分割出的目標(biāo)圖像了。

因代數(shù)多重網(wǎng)格法的計(jì)算工作量僅與未知量的個(gè)數(shù)N成正比，即O(N)。所以基于AMG快速算法的多層次自適應(yīng)算法相比過去的那些圖像處理方法要快的多，比一般的之前提出的算法都要高效，其時(shí)間復(fù)雜度隨著圖像像素的增大呈線性增長。這一優(yōu)點(diǎn)在介紹AMG法時(shí)已經(jīng)闡明。

4 展望

圖像分割技術(shù)一直是數(shù)字圖像處理的關(guān)鍵技術(shù)和經(jīng)典的難題。目前還沒有一個(gè)算法可以很好的在任意情況下把目標(biāo)從圖像中不費(fèi)力地分割出來，所以依然有許多是圖像工作者投身于圖像分割方法的研究中?？梢灶A(yù)見，在以后圖像分割算法的研究仍將是社會的熱點(diǎn)研究課題之一，特別是那些針對實(shí)際應(yīng)用領(lǐng)域，如醫(yī)學(xué)圖像、工業(yè)應(yīng)用及遙感應(yīng)用等領(lǐng)域。

[1]Eitan Sharon,Achi Brandt.Hierarchy and adaptivity in segmenting visual scenes.[J].Nature,2006

[2] Brandt, A. Algebraic multigrid theory: the symmetric case.[J]Appl.Math.Comput.19,23–-56 1986.

[3]楊暉,曲秀杰.圖像分割方法綜述[J].電腦開發(fā)與應(yīng)用.2005

TP317.48

A

1008-3537（2012）03-0076-02

2012-05-30

萬 君，男，江西廣播電視大學(xué)助理工程師，研究方向：教務(wù)管理；

吳旻倩，女，南昌廣播電視大學(xué)信息中心講師，研究方向：計(jì)算機(jī)教學(xué)。

劉石玉

校 對：紅 農(nóng)