基于Ｌｉｖｅ－Ｗｉｒｅ交互式醫學圖像分割算法研究及實現

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

基金項目：國家“863”計劃資助項目（2006AA02Z499）

作者簡介：黨建武（1963-），男，陜西渭南人，教授，博導，主要研究方向為智能信息處理(dangjw@mail.lzjtu.cn)；張芳（1982-），女，內蒙古集寧人，碩士研究生，主要研究方向為數字圖像處理；胡鐵鈞（1958-），男，吉林長春人，研究員，主要研究方向為計算機應用；晁穎（1982-），女，河南舞陽人，碩士研究生，主要研究方向為數字圖像處理

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

摘 要：提出一種改進的Live-Wire算法，結合迭代閾值分割算法對醫學圖像進行交互式分割。改進的算法避免了傳統的Live-Wire算法對噪聲敏感、不能有效地區分強弱邊緣的缺點，并且減少了動態規劃尋找最優路徑的時間和盲目性，在不增加算法復雜度的同時，提高了圖像分割的準確性。

關鍵詞：交互式；醫學圖像分割；Live-Wire

中圖分類號：TP391

文獻標志碼：A

文章編號：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

醫學圖像分割是現代醫學圖像處理的一個主要研究方向，是病變區域提取、特定組織測量以及實現三維重建的基礎。因此醫學圖像分割一直受到人們的重視。目前大致有三種類型的分割算法，即自動分割、手動分割和交互式分割。

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

由于自動分割和手動分割的缺陷，人們就提出了交互式分割算法。交互式圖像分割算法與其他分割算法的不同之處在于：對圖像實施自動分割的過程中，操作者對圖像分割進行干預和控制。也就是說操作者和計算機協同完成圖像分割，充分地利用了計算機的強大運算能力和人的實際操控經驗能力。

Live-Wire算法就是一種典型的交互式分割算法。傳統的Live-Wire算法對噪聲比較敏感、不能有效地區分強弱邊緣，動態規劃尋找最短路徑耗時多，因此算法運行時速度比較慢。本文提出了一種改進的Live-Wire算法，提高了分割的性能。

1 改進的Live-Wire算法

Live-Wire算法的基本思想是將預分割的圖像當成一個連通圖，圖像中的像素當做圖中的節點，相鄰像素點之間的邊當做連接節點的邊。在每一個邊上定義一個代價函數，為強邊緣賦予較小的代價值，非強邊緣賦予較大的代價值，同時相鄰像素間的弧賦0代價，而非鄰接像素間的弧賦+∞代價，將分割轉換為起始點到目標點之間的最優路徑問題，然后通過圖搜索來尋找物體的邊界，將用戶指定的物體邊界上的兩點之間最短路徑當做物體的邊界。

11 構造代價函數

傳統的Live-Wire算法構造了如下的代價函數：l(p，q)=ωG×fG(q)+ωZ×fZ(q)+ωD×fD(q)(1)其中：l(p，q)代表p到其鄰接像素q的局部代價；ωG、ωZ、ωD代表加權系數；fG(q)、 fZ(q)、fD(q)代表對應像素q處的梯度特征函數、Laplace過零特征函數和光滑度約束函數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(·)代表圖像中某點梯度的單位法向量。這樣，對p，q有0≤l(p，q)≤1。

12 圖搜索產生最優路徑

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

對于上述基本思想，本文給出可實施的具體步驟如下：

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

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

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

d)重復步驟b)和c)直到所有頂點都包含在S中。

圖搜索的過程完成后，就得到了一個有向連接圖。給定圖中的任何一個節點都可以通過有向連接直接找到該點到種子節點的惟一最小代價連通路徑。交互分割過程就是用戶通過拖拽鼠標動態地指定一個自由點，由計算機自動找出連接該點到種子點的最小代價路徑。由于邊界點之間的連接代價小，用戶只要將自由點放在邊界附近，并沿著邊界變化的方向不斷調整自由點，就可以完成組織分割的工作。圖1為Live-Wire算法流程圖。

13 Live-Wire算法的性能評價

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

2 優化的Live-Wire算法

傳統的Live-Wire算法在構造代價函數時采用了Laplace算子，使得分割結果不是很精確。如果僅僅考慮減小噪聲干擾，可以選用LoG算子和DoG算子代替Laplace算子來構造代價函數，但是這兩個算子在減小噪聲的同時，不能有效區分圖像中的強弱邊緣，提取的結果存在很大的誤差。

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

21 Canny算子邊緣檢測原理

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

Canny算子是通過邊緣檢測應該滿足的三個基本準則出發，推導出來的最佳邊緣檢測算子。因此，它具有如下特點：a)好的信噪比，即非邊緣點判為邊緣點或將邊緣點判為非邊緣點的概率低；b)好的定位性能，即檢測出的邊緣點要盡可能在實際邊緣的中心；c)對單一邊緣具有惟一響應，并且對虛假邊緣響應得到最大抑制。22 Canny算子邊緣檢測結果比較

在圖2中，給出了用Laplace算子和Canny算子進行邊緣提取的結果。(a)是一幅典型的人體CT圖像，由于本身組成成分的復雜性，相鄰周圍組織的灰度值區別也不是很大，使得邊緣不是很明顯。(b)是采用Laplace算子進行邊緣檢測的結果。可以看到檢測的結果很不精確，組織的內部存在大量的偽邊緣并且邊緣存在大量間斷。這會嚴重影響算法交互式分割時的分割結果。一方面由于偽邊緣的吸引會使動態輪廓線不沿著真正的邊緣前進，需要用戶增加交互的次數并產生不正確的輪廓；另一方面由于邊緣的間斷，會導致輪廓線的準確性和光滑性嚴重下降。(c)是采用Canny算子進行邊緣檢測的結果。可以看到大部分的偽邊緣都被去掉了，而檢測出來的邊緣本身具有很好的連續性，這將大大有利于提高Live-Wire算法在分割醫學圖像時的準確性。

23 用Canny算子構造代價函數

改進的Live-Wire算法構造了如下的代價函數：l(p，q)=ωG×fG(q)+ωC×fC(q)+ωD×fD(q)(5)其中：l(p，q)代表p到其鄰接像素q的局部代價；ωG、ωC、ωD代表加權系數；fG(q)、fC(q)、fD(q)代表對應像素q處的梯度特征函數、Canny邊緣檢測特征函數和光滑度約束函數。fC(q)=0 q為邊緣點

1 q為非邊緣點(6)其中：代價函數中的fG(q)和fD(q)的計算同式(2)(4)。

另外，在傳統的Live-Wire算法中，在用戶指定一個邊界點后，動態規劃將找到這個點到圖像中其他點的最短路徑。這樣運行速度比較慢，所以在實驗中筆者采用了圖像分割中常用的迭代閾值分割算法對圖像進行一個過度分割，然后用改進的LiveWire算法來交互式分割圖像，使動態規劃搜索的范圍縮小，縮短了找到最短路徑的時間，速度就會大大提高，減少了搜索的盲目性，提高了分割的準確性。

3實驗結果與分析

為了驗證LiveWire改進算法的有效性，本文使用了大量的醫學圖像進行了交互式圖像分割的實驗。實驗結果表明：新算法對噪聲不再敏感，可以正確地區分圖像中的強弱邊緣，而且對含有強彎曲邊緣的圖像也適用。

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

4結束語

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

參考文獻：

[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]. 電子學報， 2003，31(1):29-32.

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

[8]田捷.集成化醫學影像算法平臺理論與實踐[M]. 北京：清華大學出版社， 2004.

[9]王磊，莫玉龍，戚飛虎. 基于Canny理論的邊緣提取改善方法[J]．中國圖象圖形學報，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.