基于圖搜索Ａ＊算法的估價(jià)函數(shù)比較

摘要：簡(jiǎn)單介紹了基于圖搜索A*算法原理，把該算法與常見的估價(jià)函數(shù)：曼哈頓距離、對(duì)角線距離、歐幾里德距離等結(jié)合，將其應(yīng)用于肺部圖像的邊緣跟蹤中，較系統(tǒng)地總結(jié)出選擇估價(jià)函數(shù)的原則及其各優(yōu)缺點(diǎn)，這將更有效地完成邊緣跟蹤的過程。

關(guān)鍵詞：圖搜索；A*算法；曼哈頓距離；對(duì)角線距離；歐幾里德距離

中圖分類號(hào)：TP391文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：1009-3044(2008)26-1778-03

The Analysis of A Star Algorithm's Evaluation Function Based on Graph Search

SHI Da-ya1， TENG Zhong-jian2， CHEN Qing-hua3

(Key Laboratory of OptoElectronic Science and Technology for Medicine， Ministry of Education，F(xiàn)ujian Normal University， Fuzhou 350007，China)

Abstract: The principle of A star algorithm based on graph search is introduced briefly。The algorithm combined with common evaluation function such as Manhattan distance、diagonal distance、Euclid distance is applied to tracing edge。Then summarize the principle of choosing the evaluation function， the advantage and disadvantage of common evaluation function which make the process of tracing edge effectively。

Key words: graph search; a star algorithm; manhattan distance; diagonal distance; euclid distance

1 引言

圖像分割在整個(gè)圖像處理領(lǐng)域占據(jù)著相當(dāng)重要的一部分，是后繼圖像分析﹑理解的先驅(qū)步驟。最近來關(guān)于圖像分割的方法漸漸趨于多樣化，分割方法根據(jù)所使用的主要特征可分為三組:第一組是有關(guān)圖像或圖像部分的全局知識(shí);第二組是基于邊緣的分割;第三組是基于區(qū)域的分割[1]?；谶吘壍姆指铍m然是最早出現(xiàn)在的分割方法之一，但是在現(xiàn)在仍起著舉足輕重的地位。

常見的基于邊緣的分割方法如閾值化，邊界跟蹤等所使用的建立最終邊界的策略相似，但是在其先驗(yàn)信息量方面存在不同；在分割處理時(shí)可獲得的先驗(yàn)知識(shí)越多，能達(dá)到的分割結(jié)果就越好。如果已知邊界的起點(diǎn)和終點(diǎn)和一些相對(duì)弱的額外要求，那么可以使用基于圖的A*算法[2]來檢測(cè)邊緣。邊界檢測(cè)過程被轉(zhuǎn)換為在加權(quán)圖中搜索最優(yōu)路徑的問題，目標(biāo)是找到連接兩個(gè)指定節(jié)點(diǎn)即起點(diǎn)和終點(diǎn)的最好路徑。

在本文中將以基于圖的A*算法為基礎(chǔ)，比較不同的估價(jià)函數(shù)下邊緣跟蹤的結(jié)果。

2 算法描述

2.1 圖搜索算法原理

圖(graph)是由若干給定的點(diǎn)及連接兩點(diǎn)的線所構(gòu)成的圖形，這種圖形通常用來描述某些事物之間的某種特定關(guān)系，用點(diǎn)代表事物，用連接兩點(diǎn)的線表示相應(yīng)兩個(gè)事物間具有這種關(guān)系。有權(quán)圖經(jīng)常出現(xiàn)在圖論的應(yīng)用中。如在通訊圖中，權(quán)可以表示各種通訊線路的建造或維修費(fèi)用；在交通圖中，權(quán)可以表示兩地的距離等等。

對(duì)于任一幅圖像來說，在處理的時(shí)候都可以把它表示成圖的數(shù)據(jù)結(jié)構(gòu)。圖G=(V，E)是一個(gè)代數(shù)結(jié)構(gòu)，由一組節(jié)點(diǎn)V={v1，v2，...，vn}和一組弧E={e1，e2，...，en}構(gòu)成，每條弧eK代表一對(duì)無次序的節(jié)點(diǎn){vi，vj}，節(jié)點(diǎn)不必有區(qū)別。對(duì)任一段弧eK都可定義一個(gè)代價(jià)(或稱為費(fèi)用)，記為c(vi，vj)。則通過在圖中搜索對(duì)應(yīng)最小代價(jià)的通道來找到閉合邊界的方法稱為圖搜索。如果有一系列結(jié)點(diǎn)v1，v2，...，vn，其中每個(gè)結(jié)點(diǎn)vn都是結(jié)點(diǎn)vn-1的子結(jié)點(diǎn)，則這個(gè)結(jié)點(diǎn)系列稱為v1到vk的一條通路，這條通路的代價(jià)為c=c(vi-1，vi) [3]。

下面以圖1為例闡述一下圖搜索的過程（以4-近鄰的為例）。

定義代價(jià)函數(shù)c(vi，vj)=f(p)-f(q)，其中的f(p)，f(q)表示像素p，q點(diǎn)的灰度值。則根據(jù)梯度的概念，灰度值差小表示梯度小，灰度值差大表示梯度大。

圖搜索一般是從左上角的第一個(gè)點(diǎn)開始，按從上到下的方向檢測(cè)。首先要計(jì)算與該結(jié)點(diǎn)相鄰的兩個(gè)點(diǎn)的代價(jià)函數(shù)， c(1，2)= f(1)-f(2)， c(1，i)= f(1)-f(i)，比較一下兩者的大小，如果c(1，2)大，則表示1，2點(diǎn)間的梯度大，所以根據(jù)12弧的方向作為下一次搜索的方向，2點(diǎn)作為下一次搜索的起始點(diǎn);若c(1，i)的值大，則這兩點(diǎn)間的梯度小，搜索方向要沿1i，作為下一次搜索的起點(diǎn)。

2.2 基于圖搜索的A*原理

設(shè)xA是開始的邊界元素，xB是結(jié)束的邊界元素。為了在區(qū)域邊界檢測(cè)中使用圖搜索技術(shù)，必須首先定義有向加權(quán)圖的擴(kuò)展方法，還必須定義一個(gè)費(fèi)用函數(shù)f(xi)作為通過中間節(jié)點(diǎn)ni的節(jié)點(diǎn)nA到nB的路徑的費(fèi)用估計(jì)。費(fèi)用函數(shù)f(xi)典型地由兩部分組成，在開始的邊界元素xA和xj之間的最小路徑費(fèi)用的估計(jì)g(xi) ，以及在Xi和結(jié)束的邊界元素XB 之間的最小路徑費(fèi)用的估計(jì)h(xi)。從開始節(jié)點(diǎn)到節(jié)點(diǎn)ni的路徑的費(fèi)用g(xi)一般是路徑中弧或節(jié)點(diǎn)費(fèi)用的和。費(fèi)用函數(shù)相對(duì)于路徑的長(zhǎng)度必須是可分離和單調(diào)的，因此每個(gè)弧的局部費(fèi)用必須是非負(fù)的。h(xi)的估計(jì)可以是xi 到xB的邊界的長(zhǎng)度，這有利于優(yōu)先選擇XA 和XB間較短的邊界作為費(fèi)用低的路徑[4]。

A*算法是基于寬度優(yōu)先搜索算法，但并不是每次都把所有可展的結(jié)點(diǎn)展開，而是對(duì)所有沒有展開的結(jié)點(diǎn)，利用一個(gè)自己確定的估價(jià)函數(shù)對(duì)所有沒展開的結(jié)點(diǎn)進(jìn)行估價(jià)，從而找出最應(yīng)該被展開的結(jié)點(diǎn)，把該結(jié)點(diǎn)展開，直至找到目標(biāo)結(jié)點(diǎn)為止。

算法步驟：

1）起始結(jié)點(diǎn)為XA，將其所有的后繼放入OPEN表中并帶有指向起始節(jié)點(diǎn)XA的指針，給每個(gè)展開的節(jié)點(diǎn)計(jì)算費(fèi)用函數(shù)f；

2）如果OPEN 表是空的，則失敗，確定OPEN表中具有最小費(fèi)用f(xi)的節(jié)點(diǎn)Xi，將它從表中除去。如果Xi=XB，則通過指針回溯得到最優(yōu)路徑，然后停止；

3）如果第2步?jīng)]有停止，展開是到的節(jié)點(diǎn)Xi，將其后繼放入OPEN表中并帶有指向xi 的指針，計(jì)算它們的費(fèi)用f，返回第2步。

2.3 費(fèi)用函數(shù)

A*算法最關(guān)鍵的問題就是如何確定費(fèi)用函數(shù)，費(fèi)用函數(shù)越準(zhǔn)則越快找到答案。A*算法實(shí)現(xiàn)起來并不難，只不過難在找準(zhǔn)費(fèi)用函數(shù)。費(fèi)用函數(shù)f(xi)是A*算法中的核心函數(shù)，構(gòu)造一個(gè)好的費(fèi)用函數(shù)很難，難就在于沒有什么規(guī)律可循。費(fèi)用函數(shù)原則上只要有利于問題的求解，可以隨意定義。f(xi)必須可采納，否則A*算法就只能稱作A算法。A算法不能保證最后的結(jié)果是最優(yōu)的，但它的速度可能是非常快。然而有些搜索中的實(shí)時(shí)性要求高，也不一定非要得到最優(yōu)解。在這種情況下，設(shè)計(jì)費(fèi)用函數(shù)可不拘泥于f(xi)的可采納性限制。

估價(jià)函數(shù)h(xi)告訴A*從任意結(jié)點(diǎn)n到目標(biāo)結(jié)點(diǎn)的最小代價(jià)評(píng)估值。選擇一個(gè)好的估價(jià)函數(shù)是重要的。構(gòu)造精確估價(jià)函數(shù)的一種方法是預(yù)先計(jì)算任意一對(duì)結(jié)點(diǎn)之間最短路徑的長(zhǎng)度。有幾種方法可以近似模擬這種估價(jià)函數(shù)：

常用估價(jià)函數(shù)：

設(shè)xi點(diǎn)的坐標(biāo)為(x，y)，結(jié)束點(diǎn)xB的坐標(biāo)為(xB，yB)

1）曼哈頓距離：

標(biāo)準(zhǔn)的啟發(fā)式函數(shù)是曼哈頓距離（Manhattan distance）即：兩點(diǎn)在南北方向上的距離加上在東西方向上的距離。

h(xi)=abs(x-xB)+abs(y-yB )

2）對(duì)角線距離：

如果在搜索中允許對(duì)角運(yùn)動(dòng)，那么需要一個(gè)不同的啟發(fā)函數(shù)。(4 east，4 north)的曼哈頓距離將變成8*D。然而，可以簡(jiǎn)單地移動(dòng)(4 northeast)代替，所以啟發(fā)函數(shù)應(yīng)該是4*D。

h(xi)=max(abs(x-xB)，abs(y-yB))

3）歐幾里德(Euclid)距離：

如果單位可以沿著任意角度移動(dòng)（而不是網(wǎng)格方向），那么可以使用直線距離。

h(xi)=sqrt((x-xB)^2 +(y-yB)^2)

然而，如果是這樣的話，直接使用A*時(shí)將會(huì)遇到麻煩，因?yàn)榇鷥r(jià)函數(shù)g不匹配啟發(fā)函數(shù)h。因?yàn)闅W幾里德距離比曼哈頓距離和對(duì)角線距離都短，不過仍然可以得到最短路徑，只是A*將運(yùn)行得更久一些。

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

為了比較不同的估價(jià)函數(shù)在圖像邊緣跟蹤的效果上的區(qū)別，本文結(jié)合實(shí)際肺部圖像分割需要，構(gòu)造四種啟發(fā)式函數(shù)h(xi)。顯然，h(xi)定了，g(xi)已求出，f(xi)=g(xi)+ h(xi)也定下來了。如下：（x1，y1；x2 ，y2為實(shí)際像素點(diǎn)的值）

①h(xi)=0

②h(xi)=[(x1-x2)^2+(y1-y2)^2]^0.5

③h(xi)=Abs[x1-x2]+Abs[y1-y2]

④h(xi) =max(abs(x1 - x2)， abs(y1-y2))

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

本實(shí)驗(yàn)結(jié)果在vc++環(huán)境下，針對(duì)同一肺部圖像，采用4種不同的估價(jià)函數(shù)，所得出的結(jié)果如下：

3.2 不同估價(jià)函數(shù)結(jié)果比較

不同估價(jià)函數(shù)結(jié)果比較如表1所示：

3.3 實(shí)驗(yàn)結(jié)果分析

設(shè)H(xi)為真實(shí)費(fèi)用的啟發(fā)式函數(shù)，從上面實(shí)驗(yàn)可得出如下的分析結(jié)果：

當(dāng)h(xi)=0時(shí)，產(chǎn)生最小路徑耗散；

當(dāng)h(xi)> H(xi)時(shí)，展開節(jié)點(diǎn)數(shù)少，速度較快但是不會(huì)保證得到最優(yōu)結(jié)果；

當(dāng)h(xi)< H(xi)時(shí)，產(chǎn)生最小費(fèi)用路徑，即有最優(yōu)解，但是速度相對(duì)較慢；

因此，尋找A*算法的估價(jià)函數(shù)即要在最優(yōu)解與速度之間尋找一個(gè)平衡點(diǎn)，在某些應(yīng)用中，快速得到解比得到最優(yōu)解更為重要。如果選擇h(xi)> H(xi)其展開的結(jié)點(diǎn)數(shù)一般比較少，因此所花費(fèi)的時(shí)間也較少，運(yùn)行速度快，但不能保證找到一條最優(yōu)路徑;如果選擇h(xi)< H(xi)，能得最優(yōu)解，但是展開節(jié)點(diǎn)數(shù)較多，花費(fèi)時(shí)間多;如果h(xi)精確地等于從xi移動(dòng)到目標(biāo)的代價(jià)，則A*將會(huì)僅僅尋找最佳路徑而不擴(kuò)展別的任何結(jié)點(diǎn)，這將運(yùn)行得非常快。

存在兩種極端情況:

一種極端情況，如果h(xi)=0，則只有g(shù)(n)起作用，此時(shí)A*演變成Dijkstra算法，這保證能找到最短路徑。

另一種極端情況，如果h(xi)比g(xi)大很多，則只有h(xi)起作用，A*演變成BFS算法。

由以上的分析可以看出，不同的估價(jià)函數(shù)在檢測(cè)邊緣的過程中性能不一樣。對(duì)于本實(shí)驗(yàn)中使用的這張肺部結(jié)節(jié)的圖片來說，各種估價(jià)函數(shù)都能檢測(cè)出其病變部位， c卻展開了10%左右的節(jié)點(diǎn)， 但是圖a僅展開了1%左右的節(jié)點(diǎn)，且檢測(cè)速度上顯著地加快了[5] 。

從上面的分析我們可知啟發(fā)式函數(shù)可以控制A*的行為。

4 結(jié)束語

本文介紹了基于圖搜索A*算法的原理，針對(duì)控制A*行為的啟發(fā)式函數(shù)進(jìn)行探究。討論了基于圖搜索A*算法中常見的幾種估價(jià)函數(shù)在邊緣跟蹤中的性能，由此得出選擇估價(jià)函數(shù)時(shí)的一些依據(jù)。在今后的工作中，要注意到估價(jià)函數(shù)的選擇需與具體的任務(wù)相結(jié)合，根據(jù)實(shí)際要求，以真實(shí)費(fèi)用為標(biāo)準(zhǔn)，合理地選擇估價(jià)函數(shù)，從速度或效果方面優(yōu)先考慮。

參考文獻(xiàn)：

[1] Sonka M， Hlavac V. 圖像處理﹑分析與機(jī)器視覺[M].2版.北京：人民郵電出版社，2003:83.

[2] Nilsson N J. Principles of Artificial Intelligence[M]. Berlin:Springer Verlag，1982.

[3] 章毓晉.圖像工程(中冊(cè))-圖像分析[M].2版.北京:清華大學(xué)出版社，2005:87-88．

[4] Martelli A. Edge detection using heuristic search methods[J]. Computer Graphics and Image Processing，1972，(1):168-192.

[5] Tadikonda S K， Sonka M， Collins S M.Efficient coronary border detection using heuristic graph searching[C].Paris:In Proceeding of the Annual International Conference of the IEEE EMBS，1992，(14):1897-1899.