張尤賽,辛 莉

(江蘇科技大學(xué) 電子信息學(xué)院,江蘇 鎮(zhèn)江 212003)

體繪制是一種非常重要和靈活的體數(shù)據(jù)可視化技術(shù).由于用戶對體數(shù)據(jù)可視化的多樣性要求和體繪制過程中頻繁的人機(jī)交互操作,使體繪制的適應(yīng)性和效率大大降低,從而阻礙了體繪制技術(shù)的推廣應(yīng)用.利用智能算法為用戶提供最佳視點(diǎn)或一組被優(yōu)化的視點(diǎn)集,以便用戶準(zhǔn)確、快速地理解體數(shù)據(jù)中的重要信息,是提高體繪制效率的一種可行的途徑.

體繪制的最佳視點(diǎn)選擇可以歸結(jié)為優(yōu)化問題.首先需要解決的是視點(diǎn)的評價(jià)問題，即怎樣的視點(diǎn)是一個(gè)最佳視點(diǎn),目前為止,視點(diǎn)的評價(jià)尚沒有一個(gè)統(tǒng)一的標(biāo)準(zhǔn),一般認(rèn)為能夠最大限度地體現(xiàn)體數(shù)據(jù)內(nèi)部結(jié)構(gòu)信息的視點(diǎn),可以看作最佳視點(diǎn).在信息理論中,通常采用信息熵來表示信源所含信息量的程度,信息熵值愈高表明信源所含的信息量愈大.目前,已有研究采用信息熵的形式,從不同的角度和因素出發(fā),提出了體繪制最佳視點(diǎn)的評判方法,如文獻(xiàn)[1-2]利用體數(shù)據(jù)的等值面、梯度?；蚪Y(jié)構(gòu)特征集等結(jié)構(gòu)信息來構(gòu)造視點(diǎn)信息“熵”,以評價(jià)視點(diǎn)的質(zhì)量;文獻(xiàn)[3-4]則直接在3維體素上利用不透明度作為信息因素,定義視點(diǎn)信息“熵”來評價(jià)視點(diǎn)的質(zhì)量.由于這些方法一般都涉及到3維數(shù)據(jù)場的數(shù)據(jù)分析和特征提取,因此數(shù)據(jù)處理量大,步驟較為復(fù)雜.體繪制視點(diǎn)優(yōu)化問題需要解決的另一個(gè)問題是視點(diǎn)優(yōu)化算法,即如何高效、可靠地得到體繪制的最佳視點(diǎn)或一組優(yōu)化的視點(diǎn)集,以提高體繪制的繪制效果和效率.目前,在體繪制視點(diǎn)優(yōu)化中采用的算法主要有粒子群算法(particle swarm optimizatin,PSO)、單純形-粒子群混合算法(nelder-mead simplex search and particle swarm optimization,NM-PSO)和混合蛙跳算法(shuffled frog leaping algorithm,SFLA)等[5-7].從研究結(jié)果看,上述算法較好地解決了視點(diǎn)的優(yōu)化問題,實(shí)現(xiàn)了最優(yōu)視點(diǎn)的選擇.但從總體研究來看,體繪制視點(diǎn)優(yōu)化算法的研究還不夠充分,有許多優(yōu)秀的智能算法尚未涉足到該領(lǐng)域.

文中提出了一種基于蟻群算法(ant colony algorithm,ACA)的體繪制視點(diǎn)優(yōu)化方法.該方法利用體數(shù)據(jù)2維投影圖像的不透明度和結(jié)構(gòu)信息特征,用信息熵的形式構(gòu)造了視點(diǎn)評價(jià)函數(shù);在視點(diǎn)優(yōu)化的過程中,將視點(diǎn)評價(jià)函數(shù)作為ACA的目標(biāo)函數(shù),利用ACA自動地實(shí)現(xiàn)視點(diǎn)的優(yōu)化迭代,最終得到全局最優(yōu)視點(diǎn)或一組優(yōu)化的視點(diǎn)集,從而減少了體繪制過程中的交互操作,有效地提高了體繪制的效率.實(shí)驗(yàn)結(jié)果表明,該方法與基于SFLA的視點(diǎn)優(yōu)化算法具有相近似的性能,比基于PSO和NM-PSO的視點(diǎn)優(yōu)化算法具有更好的收斂穩(wěn)定性、收斂效率和收斂精度.

1 基于信息熵的視點(diǎn)評價(jià)

文獻(xiàn)[3]通過給每個(gè)體素j定義一個(gè)重要性因子Wj,并將體素j與視點(diǎn)V之間的透明度作為體素的可見性vj(V),采用式(1)來表示視點(diǎn)V的信息熵.

(1)

式中,H(V)為視點(diǎn)V的信息熵,J為體數(shù)據(jù)中體素的總數(shù).

由于式(1)需要在體數(shù)據(jù)的3維空間中對體數(shù)據(jù)的內(nèi)部結(jié)構(gòu)進(jìn)行分析,才能確定重要性因子Wj和可見性vj(V),所以往往會帶來大量復(fù)雜的數(shù)據(jù)計(jì)算和分析.為了克服這種不足,文中在體數(shù)據(jù)投影圖像的2維空間,利用像素的不透明度及其結(jié)構(gòu)信息因子來構(gòu)建視點(diǎn)的信息熵,作為視點(diǎn)質(zhì)量的評價(jià)函數(shù),如式(2)所示.

(2)

0≤wαi,wαj≤1

式中:J為體數(shù)據(jù)2維投影圖像中可見像素的總數(shù)；αi為像素i的不透明度；wαi為αi的結(jié)構(gòu)信息因子.通常在αi的結(jié)構(gòu)邊緣處wαi→1,非邊緣處wαi→0.

在視點(diǎn)優(yōu)化過程中每次計(jì)算視點(diǎn)信息熵時(shí),為了避免體數(shù)據(jù)2維投影圖像顯示所導(dǎo)致的不必要的時(shí)間損耗,采用了像素包裝和解包技術(shù)[8],即將體繪制所得到的2維投影圖像直接寫入到處理器內(nèi)存,并在內(nèi)存中直接進(jìn)行視點(diǎn)信息熵的計(jì)算和評價(jià),而不必將2維投影圖像通過圖形管線寫入幀緩沖區(qū)進(jìn)行實(shí)際顯示,從而避免了在圖形管線中所消耗的時(shí)間.

為了驗(yàn)證視點(diǎn)信息熵式(2)的評價(jià)效果,圖1給出了應(yīng)用3維紋理映射和Phong光照模型的體繪制技術(shù)[9],對人顱骨體數(shù)據(jù)進(jìn)行視點(diǎn)評價(jià)的實(shí)驗(yàn)結(jié)果.實(shí)驗(yàn)中讓視點(diǎn)圍繞人顱骨的3維重建圖像做360°的水平旋轉(zhuǎn),每隔1°進(jìn)行一次視點(diǎn)評價(jià).結(jié)構(gòu)信息因子wαi采用歸一化的Sobel算子對體繪制2維投影不透明度圖像進(jìn)行濾波來獲得.圖1a)為視角水平旋轉(zhuǎn)時(shí)視點(diǎn)信息熵的變化曲線,圖1b)，c)，d)，e)分別是視角θ為0°,90°,205°和330°下人顱骨的3維成像.其中,0°視角對應(yīng)于視點(diǎn)信息熵的最大值2.97,為最優(yōu)視點(diǎn),205°視角對應(yīng)于視點(diǎn)信息熵的最小值2.80,為最差視點(diǎn).

a) 視點(diǎn)評價(jià)函數(shù)值隨視點(diǎn)角度變化曲線

b) 視角0°

c) 視角90°

d) 視角205°

e) 視角330°

圖1人體顱骨體數(shù)據(jù)的視點(diǎn)評價(jià)實(shí)驗(yàn)
Fig.1ViewpointevaluationexperimentofCTvolumetricdataofhumanbrain

2 體繪制視點(diǎn)的蟻群優(yōu)化算法

2.1 蟻群算法的原理

蟻群算法是一種模擬螞蟻群體覓食行為方式的仿生優(yōu)化算法[10].該算法引入正反饋并行機(jī)制,具有較強(qiáng)的魯棒性、優(yōu)良的分布式機(jī)制和適用性強(qiáng)、易與其它算法相結(jié)合的特點(diǎn).目前蟻群算法已經(jīng)成功應(yīng)用于很多領(lǐng)域,可以解決一維或多維、連續(xù)或離散、靜態(tài)或動態(tài)等優(yōu)化問題[11-13].

蟻群算法的原理:根據(jù)問題的性質(zhì)估計(jì)出各變量的取值范圍,對取值范圍進(jìn)行N等分.則每個(gè)變量對應(yīng)于N+1個(gè)節(jié)點(diǎn),M個(gè)變量即為M級,構(gòu)成了共有M×(N+1)個(gè)節(jié)點(diǎn)組成的解空間.蟻群在優(yōu)化過程中,每只螞蟻在第1級到第M級各節(jié)點(diǎn)之間移動,形成一條行進(jìn)路徑,并在所經(jīng)歷的節(jié)點(diǎn)上根據(jù)目標(biāo)函數(shù)值留下一定的信息素,并利用信息素的積累和揮發(fā)作用產(chǎn)生節(jié)點(diǎn)的轉(zhuǎn)移概率,以影響整個(gè)蟻群的尋優(yōu)路徑,使得目標(biāo)函數(shù)值大的節(jié)點(diǎn)積累的信息素值較大.整個(gè)蟻群通過不斷的循環(huán)優(yōu)化,每次循環(huán)都可得到一個(gè)信息素最大的節(jié)點(diǎn),作為當(dāng)前最優(yōu)解,并據(jù)此逐漸收縮搜索范圍,直至變量節(jié)點(diǎn)之間的距離滿足預(yù)先設(shè)定的精度為止,算法結(jié)束.最后將信息素最大的節(jié)點(diǎn)及其對應(yīng)的目標(biāo)函數(shù)值作為最優(yōu)解輸出.

2.2 體繪制視點(diǎn)優(yōu)化的蟻群算法實(shí)現(xiàn)

體繪制視點(diǎn)的蟻群優(yōu)化算法的基本原理是利用ACA在整個(gè)視域內(nèi),尋找出視點(diǎn)信息熵值最大的視點(diǎn)或若干視點(diǎn)信息熵值較大的視點(diǎn),作為觀察體數(shù)據(jù)的最優(yōu)視點(diǎn)或一組優(yōu)化的視點(diǎn)集.在基于ACA的視點(diǎn)優(yōu)化問題中,假設(shè)利用體繪制重建的3維圖像中心位于坐標(biāo)的原點(diǎn),視點(diǎn)位于以坐標(biāo)原點(diǎn)為球心的單位球面上(為方便起見,將該單位球面稱為視域球),整個(gè)視域球構(gòu)成了視點(diǎn)優(yōu)化的解空間.視點(diǎn)k的坐標(biāo)可以用位于視域球上的單位矢量V(k)=[α(k),β(k)]來表示,其中α(k)∈[0°,360°]為V(k)在XZ平面上投影矢量與X坐標(biāo)軸的夾角,β(k)∈[0°,180°]為V(k)與Y坐標(biāo)軸之間的夾角.在蟻群算法中,每個(gè)螞蟻的一條行進(jìn)路徑代表一個(gè)可選的視點(diǎn),可以用V(k)來表示,整個(gè)蟻群的路徑構(gòu)成了一個(gè)視點(diǎn)集{V(k)};蟻群算法的目標(biāo)函數(shù)則可以用節(jié)點(diǎn)上的視點(diǎn)信息熵H[V(k)]表示.

圖2為基于蟻群算法的體繪制視點(diǎn)優(yōu)化流程.

圖2 基于蟻群算法的體繪制視點(diǎn)優(yōu)化流程Fig.2 Flow chart of viewpoint optimization based on ant colony algorithm for volume rendering

算法的具體實(shí)現(xiàn)如下:

1)設(shè)置信息素常量Q,信息素?fù)]發(fā)系數(shù)ρ,各節(jié)點(diǎn)的初始信息素τconst和螞蟻總數(shù)Nants等蟻群算法參數(shù);調(diào)整視點(diǎn)角度變量α,β的取值范圍,αl≤α≤αu,βl≤β≤βu;初始迭代時(shí),αl=0°,αu=360°,βl=0°,βu=180°;設(shè)算法迭代次數(shù)n=0.

2)對變量的取值范圍進(jìn)行N等分,hα,hβ表示變量各等份的長度:

(3)

3)判斷是否滿足算法終止條件:

max(hα,hβ)≤ε

(4)

若滿足,輸出最優(yōu)視點(diǎn)Vbest=[αbest,βbest]和最優(yōu)視點(diǎn)信息熵值H[Vbest];否則,轉(zhuǎn)步驟4).

(5)

4)將蟻群隨機(jī)撒放在第一個(gè)變量的N+1個(gè)節(jié)點(diǎn)上.每只螞蟻按轉(zhuǎn)移概率Pij選擇路徑(下一個(gè)節(jié)點(diǎn)),并按式(7)對各節(jié)點(diǎn)信息素進(jìn)行更新.

(6)

(7)

式中：τij表示第i個(gè)變量的第j個(gè)節(jié)點(diǎn)的信息素;H[V(k)]為螞蟻k的目標(biāo)函數(shù)值.

5)所有螞蟻循環(huán)若干遍后,找出τij矩陣中每列最大的元素對應(yīng)的行rowα,rowβ,即得出本次迭代的最優(yōu)視點(diǎn)Vb,并按式(9,10)縮小變量的取值范圍.

Vb=(αb,βb)=(αl+hα×rowα,βl+hβ×rowβ)

(8)

(9)

(10)

式中：Δ為變量取值范圍的縮小步長,其更新公式為:Δ=ceil[N/(n+1)],n為蟻群優(yōu)化的迭代次數(shù).

6)n=n+1,轉(zhuǎn)步驟2).

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

實(shí)驗(yàn)選擇了一組典型的體數(shù)據(jù)集,利用基于3維紋理映射的體繪制方法,將文中算法分別與基于PSO，NM-PSO和SFLA的視點(diǎn)優(yōu)化算法進(jìn)行了性能比較,以驗(yàn)證文中算法的性能.實(shí)驗(yàn)的硬件環(huán)境為Intel Pentium(R) Dual-Core CPU E5400 2.7 GHz，內(nèi)存2.0 GB，Nvida GeForce 210圖形卡(顯存1 GB),軟件平臺為Visual C++6.0，OpenGL 2.0.

為了便于對上述4種算法的性能進(jìn)行比較,實(shí)驗(yàn)中PSO，NM-PSO，SFLA和ACA4種算法的群體規(guī)模都取12.PSO算法的加速度系數(shù)c1=c2=2,慣性權(quán)重ω隨著迭代次數(shù)在0.9～0.4之間線性遞減;NM-PSO算法將5個(gè)最優(yōu)粒子構(gòu)成一組,進(jìn)行NM單純形局部搜索,NM的擴(kuò)張系數(shù)γ=2,壓縮系數(shù)β=0.5,剩余的7個(gè)粒子構(gòu)成另一組,利用PSO算法進(jìn)行全局優(yōu)化;SFLA將蛙群分為3個(gè)模因組,每組模因組有4個(gè)青蛙,局部深度搜索6次;ACA算法的N"=12,Δ=ceil[N/(n+1)],ρ=0.2,Q=10,τconst=20～30.圖3為利用文中方法對人腳趾、顱骨醫(yī)學(xué)體數(shù)據(jù)、茶壺、原子核體數(shù)據(jù)進(jìn)行實(shí)驗(yàn)所得的最優(yōu)視點(diǎn)和最差視點(diǎn)的體繪制圖像.圖4給出了4種算法分別對上述4種體數(shù)據(jù)進(jìn)行6次視點(diǎn)優(yōu)化實(shí)驗(yàn),完成30次迭代后所得到的視點(diǎn)信息熵的平均進(jìn)化曲線.

最優(yōu)視點(diǎn) 最差視點(diǎn)

最優(yōu)視點(diǎn) 最差視點(diǎn)

最優(yōu)視點(diǎn) 最差視點(diǎn)

最優(yōu)視點(diǎn) 最差視點(diǎn)

a) 人腳趾視點(diǎn)信息熵的平均進(jìn)化曲線

b) 人顱骨視點(diǎn)信息熵的平均進(jìn)化曲線

c) 茶壺視點(diǎn)信息熵的平均進(jìn)化曲線

d) 原子核視點(diǎn)信息熵的平均進(jìn)化曲線

綜合上述實(shí)驗(yàn)結(jié)果,可以得出如下結(jié)論:

1)在算法的收斂效率方面,在初始的幾次算法迭代中,基于SFLA的視點(diǎn)優(yōu)化算法的收斂速度最快,文中算法其次,基于NM-PSO和PSO的視點(diǎn)優(yōu)化算法的收斂速度較慢.體現(xiàn)出文中算法和基于SFLA的視點(diǎn)優(yōu)化算法具有更好的算法迭代收斂效率.

2)在算法的實(shí)時(shí)性方面,由于算法的復(fù)雜度不同,SFLA算法每次迭代所需的時(shí)間較長,文中算法其次,PSO算法最快.但是由于算法每次迭代的收斂效率不同,SFLA算法和文中算法一般經(jīng)過3～4次迭代即能接近最優(yōu)解,經(jīng)過7～12次迭代達(dá)到最優(yōu)解;PSO和NM-PSO算法則需要經(jīng)過25次以上的迭代才能接近或達(dá)到最優(yōu)解.所以,文中算法和SFLA算法在視點(diǎn)優(yōu)化的起始階段,相比PSO和NM-PSO算法具有更好的實(shí)時(shí)性,但是在視點(diǎn)優(yōu)化的后階段在實(shí)時(shí)性上并不占有優(yōu)勢.

3)在算法的收斂精度方面,相比基于NM-PSO和PSO的視點(diǎn)優(yōu)化算法,文中算法和基于SFLA的視點(diǎn)優(yōu)化算法都可以得到更高的視點(diǎn)信息熵值,即具有更高的算法收斂精度.

4)蟻群算法中,蟻群運(yùn)動時(shí)能根據(jù)目標(biāo)函數(shù)值在所經(jīng)歷的節(jié)點(diǎn)上留下一定的信息素,并利用信息素的積累和揮發(fā)作用產(chǎn)生節(jié)點(diǎn)的轉(zhuǎn)移概率,形成了一種正反饋并行機(jī)制,使蟻群個(gè)體之間可以交換局部優(yōu)化信息,從而保證了整個(gè)蟻群對視點(diǎn)的全局優(yōu)化能力和算法收斂的穩(wěn)定性.

5)蟻群算法的參數(shù)較多,選擇一組合適的參數(shù),對蟻群算法的收斂性能有重要作用.文中算法在蟻群優(yōu)化過程中,采用了一種非線性的變量縮小步長Δ=ceil[N/(n+1)],對避免小規(guī)模蟻群陷入局部最優(yōu)解,提高蟻群算法的收斂性能具有很好的效果.

4 結(jié)論

利用反映體數(shù)據(jù)中體素重要性的不透明度和結(jié)構(gòu)信息因子構(gòu)建視點(diǎn)信息熵來評價(jià)視點(diǎn)的質(zhì)量,在一定程度上反映了人類視覺系統(tǒng)的特性;文中利用蟻群算法進(jìn)行體繪制的視點(diǎn)優(yōu)化,較好地解決了體繪制最佳視點(diǎn)的選擇問題,具有自動化和智能化的特點(diǎn).但是,其不足的是在視點(diǎn)評價(jià)過程中,沒有充分地體現(xiàn)出用戶對最佳視點(diǎn)的個(gè)性化和多樣性的要求,在視點(diǎn)優(yōu)化過程中沒有充分體現(xiàn)用戶的偏好和習(xí)慣與智能算法的有機(jī)結(jié)合.

近年來,隨著“大數(shù)據(jù)“概念的提出,大數(shù)據(jù)可視化問題必將成為新的研究熱點(diǎn).體繪制作為一種重要的體數(shù)據(jù)可視化技術(shù),在數(shù)據(jù)簡約可視化、高可擴(kuò)展的數(shù)據(jù)投影、維度降解和高清晰顯示等方面都面臨著新的挑戰(zhàn),引入創(chuàng)新的視覺表現(xiàn)方式和用戶交互手段,設(shè)計(jì)基于視覺感知的體繪制高效智能算法,都是值得進(jìn)一步深入研究的課題.

[1] Takahashi S,Fujishiro I,Takeshima Y,et al.A feature-driven approach to locating optimal viewpoints for volume visualization[C]//Proceedingsofthe16thIEEEVisualization.Washington DC,USA: IEEE Press,2005: 495-502.

[2] Tao Yubo,Lin Hai,Bao Hujun,et al.Structure-aware viewpoint selection for volume visualization[C]//IEEEPacificVisualizationSymposium.Beijing,China: IEEE Computer Society,2009:193-200.

[3] Bordoloi U D,Shen H W.View selection for volume rendering[C]//Proceedingsofthe16thIEEEVisualization.Washington DC,USA: IEEE Computer Society,2005: 487-494.

[4] Ji Guangfeng,Shen Hanwei.Dynamic view selection for time-varying volumes[J].IEEETransactionsonVisualizationandComputerGraphics,2006,12 (5): 1109-1116.

[5] Wang Yanni,Zhou Dibin,Zheng Yao,et al.Viewpoint selection using PSO algorithms for volume rendering[C]//ProceedingsoftheSecondInternationalMulti-SymposiumsonComputerandComputationalSciences.Washington DC,USA: IEEE Press,2007: 286-291.

[6] Zhang Yousai,Wang Bin,Dai Changjiang.Viewpoint selection based on NM-PSO for volume rendering[C]//LectureNotesinComputerScience,7390LNAI,IntelligentComputingTheoriesandApplications-8thInternationalConference,ICIC2012Proceedings.Huangshan,China: Springer Verlag Press,July 2012: 487-494.

[7] 張尤賽,王彬.應(yīng)用混合蛙跳算法的體繪制最佳視點(diǎn)選擇[J].中國圖象圖形學(xué)報(bào),2011,16(9): 1670-1675.

Zhang Yousai,Wang Bin.Optimal viewpoint selection for volume rendering using shuffled frog leaping algorithm[J].JournalofImageandGraphics,2011,16(9): 1670-1675.(in Chinese)

[8] Shreiner D,The Khronos OpenGL ARB Woring Group.OpenGL編程指南[M].7版.李軍,徐波,譯.北京: 機(jī)械工業(yè)出版社,2010:209-224.

[9] 張尤賽,陳福民.基于紋理映射與Phong光照模型的體繪制加速算法[J].中國圖象圖形學(xué)報(bào),2003,8(9):1048-1054.

Zhang Yousai,Chen Fumin.Accelerated volume rendering using texture mapping with phong shading [J].JournalofImageandGraphics,2003,8 (9): 1048-1054.(in Chinese)

[10] Colorni A,Dorigo M,Maniezzo V.Distributed optimization by ant colonies[C]//ProceedingsofEuropeanConferenceonArtificialLife.Paris,France:Elsevier Publishing,1991:134-142.

[11] 段海濱,馬冠軍,王道波,等.一種求解連續(xù)空間優(yōu)化問題的改進(jìn)蟻群算法[J].系統(tǒng)仿真學(xué)報(bào),2007,19(5): 974-977.

Duan Haibin,Ma Guanjun,Wang Daobo,et al.Improved ant colony algorithm for solving continuous space optimization problems[J].JournalofSystemSimulation,2007,19(5): 974-977.(in Chinese)

[12] 陳琪,寧博.MMAS在帶時(shí)間窗的車輛路線問題中的應(yīng)用[J].江蘇科技大學(xué)學(xué)報(bào):自然科學(xué)版,2009,23(3): 263-266.

Chen Qi,Ning Bo.Application of MMAS on vehicle routing problem with time window[J].JournalofJiangsuUniversityofScienceandTechnology:NaturalScienceEdition,2009,23(3): 263-266.(in Chinese)

[13] 陳立偉,唐權(quán)華.基于蟻群算法的離散救援問題出救點(diǎn)選址研究[J].計(jì)算機(jī)應(yīng)用研究,2010,27(11): 4152-4154.

Chen Liwei,Tang Quanhua.Research on depot location of discrete emergency aid based on ACO[J].ApplicationResearchofComputers,2010,27(11): 4152-4154.(in Chinese)