基于Ｌｉｖｅ－Ｗｉｒｅ交互式醫(yī)學(xué)圖像分割算法研究及實(shí)現(xiàn)

收稿日期：2007-11-12；修回日期：2008-02-19

基金項(xiàng)目：國(guó)家“863”計(jì)劃資助項(xiàng)目（2006AA02Z499）

作者簡(jiǎn)介：黨建武（1963-），男，陜西渭南人，教授，博導(dǎo)，主要研究方向?yàn)橹悄苄畔⑻幚?dangjw@mail.lzjtu.cn)；張芳（1982-），女，內(nèi)蒙古集寧人，碩士研究生，主要研究方向?yàn)閿?shù)字圖像處理；胡鐵鈞（1958-），男，吉林長(zhǎng)春人，研究員，主要研究方向?yàn)橛?jì)算機(jī)應(yīng)用；晁穎（1982-），女，河南舞陽(yáng)人，碩士研究生，主要研究方向?yàn)閿?shù)字圖像處理

（1.蘭州交通大學(xué) 電子與信息工程學(xué)院， 蘭州 730070；2.甘肅省計(jì)算中心， 蘭州 730000）

摘 要：提出一種改進(jìn)的Live-Wire算法，結(jié)合迭代閾值分割算法對(duì)醫(yī)學(xué)圖像進(jìn)行交互式分割。改進(jìn)的算法避免了傳統(tǒng)的Live-Wire算法對(duì)噪聲敏感、不能有效地區(qū)分強(qiáng)弱邊緣的缺點(diǎn)，并且減少了動(dòng)態(tài)規(guī)劃尋找最優(yōu)路徑的時(shí)間和盲目性，在不增加算法復(fù)雜度的同時(shí)，提高了圖像分割的準(zhǔn)確性。

關(guān)鍵詞：交互式；醫(yī)學(xué)圖像分割；Live-Wire

中圖分類號(hào)：TP391

文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1001-3695(2008)10-3048-02

Research and improvement of Live-Wire interactive

algorithm for medical image segmentation

DANG Jian-wu¹，ZHANG Fang¹， HU Tie-jun²， CHAO Ying¹

(1. School of Electronics Communication Engineering， Lanzhou Jiaotong University， Lanzhou 730070， China; 2. Gansu Computing Center， Lanzhou 730000， China)

Abstract:This paper presented an improved Live-Wire algorithm， combined threshold segmentation approach to the interactive medical image segmentation. Improved algorithm avoided shortcomings ，which was the traditional Live-Wire algorithm sensitive to noise， not effectively distinguished between strong and weak edge. And reduced the dynamic programming to find the optimal path for the time and blindness， without increasing the complexity of the algorithm， improved the accuracy of image segmentation.

Key words：interactive; medical image segmentation; Live-Wire

醫(yī)學(xué)圖像分割是現(xiàn)代醫(yī)學(xué)圖像處理的一個(gè)主要研究方向，是病變區(qū)域提取、特定組織測(cè)量以及實(shí)現(xiàn)三維重建的基礎(chǔ)。因此醫(yī)學(xué)圖像分割一直受到人們的重視。目前大致有三種類型的分割算法，即自動(dòng)分割、手動(dòng)分割和交互式分割。

自動(dòng)分割包含一些常見的分割算法，如閾值分割、區(qū)域增長(zhǎng)分割等。雖然這些算法已經(jīng)成熟，運(yùn)算也簡(jiǎn)單，但是由于圖像的多樣性以及本身的一些特征，使得這些算法難以得到分割的準(zhǔn)確結(jié)果，造成分割的輪廓偏離。它適用于特征比較明顯的區(qū)域，如人的皮膚組織、心臟等。手動(dòng)分割是全部由人工對(duì)圖像進(jìn)行分割，是一項(xiàng)耗時(shí)和枯燥的工作，不僅要花費(fèi)大量的人力和時(shí)間，而且對(duì)醫(yī)生的經(jīng)驗(yàn)和技術(shù)要求非常高，分割結(jié)果是不精確、不可重復(fù)的。所以在對(duì)CT斷層圖像進(jìn)行分割時(shí)，這種方法是不可取的。

由于自動(dòng)分割和手動(dòng)分割的缺陷，人們就提出了交互式分割算法。交互式圖像分割算法與其他分割算法的不同之處在于：對(duì)圖像實(shí)施自動(dòng)分割的過程中，操作者對(duì)圖像分割進(jìn)行干預(yù)和控制。也就是說操作者和計(jì)算機(jī)協(xié)同完成圖像分割，充分地利用了計(jì)算機(jī)的強(qiáng)大運(yùn)算能力和人的實(shí)際操控經(jīng)驗(yàn)?zāi)芰Α?/p>

Live-Wire算法就是一種典型的交互式分割算法。傳統(tǒng)的Live-Wire算法對(duì)噪聲比較敏感、不能有效地區(qū)分強(qiáng)弱邊緣，動(dòng)態(tài)規(guī)劃尋找最短路徑耗時(shí)多，因此算法運(yùn)行時(shí)速度比較慢。本文提出了一種改進(jìn)的Live-Wire算法，提高了分割的性能。

1 改進(jìn)的Live-Wire算法

Live-Wire算法的基本思想是將預(yù)分割的圖像當(dāng)成一個(gè)連通圖，圖像中的像素當(dāng)做圖中的節(jié)點(diǎn)，相鄰像素點(diǎn)之間的邊當(dāng)做連接節(jié)點(diǎn)的邊。在每一個(gè)邊上定義一個(gè)代價(jià)函數(shù)，為強(qiáng)邊緣賦予較小的代價(jià)值，非強(qiáng)邊緣賦予較大的代價(jià)值，同時(shí)相鄰像素間的弧賦0代價(jià)，而非鄰接像素間的弧賦+∞代價(jià)，將分割轉(zhuǎn)換為起始點(diǎn)到目標(biāo)點(diǎn)之間的最優(yōu)路徑問題，然后通過圖搜索來尋找物體的邊界，將用戶指定的物體邊界上的兩點(diǎn)之間最短路徑當(dāng)做物體的邊界。

11 構(gòu)造代價(jià)函數(shù)

傳統(tǒng)的Live-Wire算法構(gòu)造了如下的代價(jià)函數(shù)：l(p，q)=ωG×fG(q)+ωZ×fZ(q)+ωD×fD(q)(1)其中：l(p，q)代表p到其鄰接像素q的局部代價(jià)；ωG、ωZ、ωD代表加權(quán)系數(shù)；fG(q)、 fZ(q)、fD(q)代表對(duì)應(yīng)像素q處的梯度特征函數(shù)、Laplace過零特征函數(shù)和光滑度約束函數(shù)fG(q)=1-G(q)/max(G)(2)

fZ(q)=0 L(q)=0

1L(q)≠0（3）

fD(q)=2/(3π){cos[D(p)×|p-q|]-1+

cos[D(q)×|p-q|]-1}（4）其中：G(q)和L(q)分別給出像素q處梯度的幅值和Laplace值；D(·)代表圖像中某點(diǎn)梯度的單位法向量。這樣，對(duì)p，q有0≤l(p，q)≤1。

12 圖搜索產(chǎn)生最優(yōu)路徑

Dijkstra于1959年提出了一個(gè)按路徑長(zhǎng)度遞增的順序逐步產(chǎn)生最短路徑的方法，稱之為Dijkstra算法。該算法的基本思想是將圖中頂點(diǎn)集合V分為兩組：a)已求出最短路徑的頂點(diǎn)集合（用S表示）;b)其余未確定最短路徑的頂點(diǎn)集合（用U表示）。按最短路徑長(zhǎng)度的遞增次序一次把b)組的頂點(diǎn)加入S中。在加入的過程中，總保持從源點(diǎn)v到S中各頂點(diǎn)的最短路徑長(zhǎng)度不大于從源點(diǎn)v到U的任何頂點(diǎn)最短路徑長(zhǎng)度。此外，每個(gè)頂點(diǎn)對(duì)應(yīng)的最短路徑長(zhǎng)度不大于從源點(diǎn)v到此頂點(diǎn)的最短路徑長(zhǎng)度，U中的頂點(diǎn)距離為從v到此頂點(diǎn)只包括S中的頂點(diǎn)為中心頂點(diǎn)的當(dāng)前最短路徑長(zhǎng)度。

對(duì)于上述基本思想，本文給出可實(shí)施的具體步驟如下：

a)初始時(shí)，S只包括源點(diǎn)，即S＝{v0}，v0的距離為0。U包括除v0外的其他頂點(diǎn)，U中頂點(diǎn)u距離為邊上的權(quán)（若v0與u有邊〈v0，u〉或∞，u不是v0的出邊鄰接點(diǎn)）。

b)從U中選取一個(gè)距離最小的頂點(diǎn)k，將k加入S中（該選定的距離就是v0到k的最短路徑長(zhǎng)度）。

c)以k作為新考慮的中間點(diǎn)，修改U中各頂點(diǎn)的距離：若從源點(diǎn)v0到頂點(diǎn)u（uU）的距離（經(jīng)過頂點(diǎn)k）比原來距離（不經(jīng)過頂點(diǎn)k）短，則修改頂點(diǎn)u的距離值，修改后的距離值為頂點(diǎn)k的距離加邊〈k，u〉上的權(quán)。

d)重復(fù)步驟b)和c)直到所有頂點(diǎn)都包含在S中。

圖搜索的過程完成后，就得到了一個(gè)有向連接圖。給定圖中的任何一個(gè)節(jié)點(diǎn)都可以通過有向連接直接找到該點(diǎn)到種子節(jié)點(diǎn)的惟一最小代價(jià)連通路徑。交互分割過程就是用戶通過拖拽鼠標(biāo)動(dòng)態(tài)地指定一個(gè)自由點(diǎn)，由計(jì)算機(jī)自動(dòng)找出連接該點(diǎn)到種子點(diǎn)的最小代價(jià)路徑。由于邊界點(diǎn)之間的連接代價(jià)小，用戶只要將自由點(diǎn)放在邊界附近，并沿著邊界變化的方向不斷調(diào)整自由點(diǎn)，就可以完成組織分割的工作。圖1為L(zhǎng)ive-Wire算法流程圖。

13 Live-Wire算法的性能評(píng)價(jià)

從上面分析可以看出，傳統(tǒng)的Live-Wire算法在進(jìn)行分割時(shí)采用的是拉普拉斯算子進(jìn)行預(yù)處理，而拉普拉斯算子對(duì)圖像平滑濾波的程度取決于高斯函數(shù)的參數(shù)δ。δ值越大，噪聲濾波效果越好，但是卻丟失了重要的邊緣信息，容易將相鄰的邊緣連接在一起形成一個(gè)邊緣；如果取的δ值小，又有可能平滑不完全而存在太多的噪聲。因此，傳統(tǒng)的Live-Wire算法對(duì)噪相當(dāng)敏感，而且不能有效地區(qū)分物體的強(qiáng)弱邊緣，對(duì)邊緣彎曲程度較大的圖像不能較精確地尋找到最優(yōu)邊界。

2 優(yōu)化的Live-Wire算法

傳統(tǒng)的Live-Wire算法在構(gòu)造代價(jià)函數(shù)時(shí)采用了Laplace算子，使得分割結(jié)果不是很精確。如果僅僅考慮減小噪聲干擾，可以選用LoG算子和DoG算子代替Laplace算子來構(gòu)造代價(jià)函數(shù)，但是這兩個(gè)算子在減小噪聲的同時(shí)，不能有效區(qū)分圖像中的強(qiáng)弱邊緣，提取的結(jié)果存在很大的誤差。

本文提出了用Canny算子來構(gòu)造代價(jià)函數(shù)。Canny算子證明了高斯函數(shù)的一階倒數(shù)可以在抗干擾和精確定位之間選擇一個(gè)折中的方案，并且在此基礎(chǔ)上提出了對(duì)信噪比與定位之乘積的最優(yōu)化逼近算子，可以在有效抑制噪聲的前提下，最大限度地保證邊緣的連續(xù)性。因此，筆者采用Canny算子代替Laplace算子對(duì)Live-Wire算法進(jìn)行改進(jìn)，使之更加符合醫(yī)學(xué)圖像分割的需要。

21 Canny算子邊緣檢測(cè)原理

Canny算子的基本思想是：先對(duì)處理的圖像選擇一定的Guass濾波器進(jìn)行平滑濾波；然后采用一種稱之為非極值抑制(nonmaxima suppression)的技術(shù)，對(duì)平滑后的圖像進(jìn)行處理，得到最后所需的邊緣圖像。

Canny算子是通過邊緣檢測(cè)應(yīng)該滿足的三個(gè)基本準(zhǔn)則出發(fā)，推導(dǎo)出來的最佳邊緣檢測(cè)算子。因此，它具有如下特點(diǎn)：a)好的信噪比，即非邊緣點(diǎn)判為邊緣點(diǎn)或?qū)⑦吘夵c(diǎn)判為非邊緣點(diǎn)的概率低；b)好的定位性能，即檢測(cè)出的邊緣點(diǎn)要盡可能在實(shí)際邊緣的中心；c)對(duì)單一邊緣具有惟一響應(yīng)，并且對(duì)虛假邊緣響應(yīng)得到最大抑制。22 Canny算子邊緣檢測(cè)結(jié)果比較

在圖2中，給出了用Laplace算子和Canny算子進(jìn)行邊緣提取的結(jié)果。(a)是一幅典型的人體CT圖像，由于本身組成成分的復(fù)雜性，相鄰周圍組織的灰度值區(qū)別也不是很大，使得邊緣不是很明顯。(b)是采用Laplace算子進(jìn)行邊緣檢測(cè)的結(jié)果?？梢钥吹綑z測(cè)的結(jié)果很不精確，組織的內(nèi)部存在大量的偽邊緣并且邊緣存在大量間斷。這會(huì)嚴(yán)重影響算法交互式分割時(shí)的分割結(jié)果。一方面由于偽邊緣的吸引會(huì)使動(dòng)態(tài)輪廓線不沿著真正的邊緣前進(jìn)，需要用戶增加交互的次數(shù)并產(chǎn)生不正確的輪廓；另一方面由于邊緣的間斷，會(huì)導(dǎo)致輪廓線的準(zhǔn)確性和光滑性嚴(yán)重下降。(c)是采用Canny算子進(jìn)行邊緣檢測(cè)的結(jié)果?？梢钥吹酱蟛糠值膫芜吘壎急蝗サ袅耍鴻z測(cè)出來的邊緣本身具有很好的連續(xù)性，這將大大有利于提高Live-Wire算法在分割醫(yī)學(xué)圖像時(shí)的準(zhǔn)確性。

23 用Canny算子構(gòu)造代價(jià)函數(shù)

改進(jìn)的Live-Wire算法構(gòu)造了如下的代價(jià)函數(shù)：l(p，q)=ωG×fG(q)+ωC×fC(q)+ωD×fD(q)(5)其中：l(p，q)代表p到其鄰接像素q的局部代價(jià)；ωG、ωC、ωD代表加權(quán)系數(shù)；fG(q)、fC(q)、fD(q)代表對(duì)應(yīng)像素q處的梯度特征函數(shù)、Canny邊緣檢測(cè)特征函數(shù)和光滑度約束函數(shù)。fC(q)=0 q為邊緣點(diǎn)

1 q為非邊緣點(diǎn)(6)其中：代價(jià)函數(shù)中的fG(q)和fD(q)的計(jì)算同式(2)(4)。

另外，在傳統(tǒng)的Live-Wire算法中，在用戶指定一個(gè)邊界點(diǎn)后，動(dòng)態(tài)規(guī)劃將找到這個(gè)點(diǎn)到圖像中其他點(diǎn)的最短路徑。這樣運(yùn)行速度比較慢，所以在實(shí)驗(yàn)中筆者采用了圖像分割中常用的迭代閾值分割算法對(duì)圖像進(jìn)行一個(gè)過度分割，然后用改進(jìn)的LiveWire算法來交互式分割圖像，使動(dòng)態(tài)規(guī)劃搜索的范圍縮小，縮短了找到最短路徑的時(shí)間，速度就會(huì)大大提高，減少了搜索的盲目性，提高了分割的準(zhǔn)確性。

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

為了驗(yàn)證LiveWire改進(jìn)算法的有效性，本文使用了大量的醫(yī)學(xué)圖像進(jìn)行了交互式圖像分割的實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果表明：新算法對(duì)噪聲不再敏感，可以正確地區(qū)分圖像中的強(qiáng)弱邊緣，而且對(duì)含有強(qiáng)彎曲邊緣的圖像也適用。

實(shí)驗(yàn)結(jié)果如圖3所示，給出了先用迭代閾值分割的結(jié)果。在此基礎(chǔ)上，用改進(jìn)的LiveWire算法進(jìn)行分割。(a)為噪聲干擾下的人體CT圖。(b)為用迭代閾值分割出來的結(jié)果。可以看出，經(jīng)過迭代閾值進(jìn)行過分割，使得圖像中區(qū)別較大的部分分割出來，這樣就減少了動(dòng)態(tài)規(guī)劃尋找最優(yōu)路徑的盲目性。(c)是用傳統(tǒng)的LiveWire算法進(jìn)行分割的結(jié)果。(d)是用改進(jìn)的LiveWire算法分割的結(jié)果。

4結(jié)束語(yǔ)

本文針對(duì)LiveWire算法的不足提出了改進(jìn)方法。通過分析該算法，從構(gòu)造代價(jià)函數(shù)出發(fā)，運(yùn)用Canny算子代替Laplace算子，從而使得算法可以正確地區(qū)分圖像中的強(qiáng)弱邊緣，不再對(duì)噪聲敏感。在沒有增加復(fù)雜度的前提下，提高了邊緣提取的精度，得到了較好的分割效果，并且用迭代閾值分割算法先對(duì)原圖像進(jìn)行預(yù)處理，減少了尋找最短路徑的盲目性，提高了分割的效率，為醫(yī)學(xué)圖像的分割提供了一種更加有效的方法。

參考文獻(xiàn)：

[1]BARRETT W A， MORTENSEN E N. Interaction LiveWire boundary extraction[J]. Medical Image Analysis，1997，1(4):331-341.

[2]TIAN Jie. An interactive segmentation method based on dynamic programming and its application in medical image analysis[C]//Proc of the 14th ICPR. Australia:[s.n.]，1998.

[3]FALCAO A X， UDUPA J K. Usersteered image segmentation paradigms: live wire and live lane[J].Graphical Models and Image Processing， 1998，60(4):233-260.

[4]AMINI A A，TEHRANI S，WEYMOUTH T E．Using dynamic programming for minimizing the energy of active contours in the presence of hard contrains[C]//Proc of the 2nd International Conference of Computer Vision. 1988:95-99.

[5]CANNY J. A computational approach to edge detection U[J]. IEEE Trans on Pattern Analysis and Machine Intelligence， 1986，8(6):679-698.

[6]羅希平， 田捷. 一種改進(jìn)的交互式醫(yī)學(xué)圖像序列分割方法[J]. 電子學(xué)報(bào)， 2003，31(1):29-32.

[7]廖志軍.交互式圖像分割算法研究[D].北京：中國(guó)科學(xué)研究院，2006.

[8]田捷.集成化醫(yī)學(xué)影像算法平臺(tái)理論與實(shí)踐[M]. 北京：清華大學(xué)出版社， 2004.

[9]王磊，莫玉龍，戚飛虎. 基于Canny理論的邊緣提取改善方法[J]．中國(guó)圖象圖形學(xué)報(bào)，1996，1（3）:191195.

[10]SALIH B G， CARLO T， BERND G. Medical image compression based on region of interest， with application to colon CT images[C]//Proc of the 23rd International Conference of IEEE Engineering in Medicine and Biology Society. 2001.