基于ICP和CPD的顱骨自動配準算法 - 圖文-

1、收稿日期:2010-06-27;修回日期:2010-09-08基金項目:國家自然科學(xué)基金重點項目(60736008;國家 863 高技術(shù)研究發(fā)展計劃項目基金(2008AA01Z301;北京市自然科學(xué)基金重點項目(4081002作者簡介:白茹意(1987-,女,山西榆社人,碩士研究生,研究方向為計算機圖形學(xué)、虛擬現(xiàn)實與可視化;周明全,博士生導(dǎo)師,教授,研究方向為計算機圖形學(xué)、數(shù)字圖像處理、科學(xué)計算可視化?；贗CP 和CPD 的顱骨自動配準算法白茹意,周明全,鄧擎瓊(北京師范大學(xué)信息科學(xué)與技術(shù)學(xué)院,北京100875摘 要:顱骨配準是計算機輔助的三維顱面復(fù)原技術(shù)的重要研究內(nèi)容之一。顱骨配準的準確與

2、否會直接影響到將來顱面復(fù)原的準確性。為此,提出一種新的3D 顱骨自動配準算法。該算法考慮到顱骨模型的特殊結(jié)構(gòu)與實現(xiàn)的簡便性,首先自動提取顱骨不光滑區(qū)域的脊線(Crest li nes以及光滑區(qū)域的頂點作為特征點,然后利用迭代最近點(I CP算法進行粗配準,在此基礎(chǔ)上,再采用CPD (Coherent Po i nt Dr ift算法對顱骨進行精確配準。實驗結(jié)果表明,該算法能有效提高顱骨配準的準確性并對缺損顱骨具有一定的魯棒性。關(guān)鍵詞:配準;特征點;Crest li nes ;CPD中圖分類號:TP301.6 文獻標識碼:A 文章編號:1673-629X (201102-0120-03A lgo

3、rith m for Auto mated Skull R egistration Based on I CP and CPDBA I Ru-y ,i ZHOU M i n g-quan ,DE NG Q i n g-q i o ng(Co lleg e o f Info r m ati on Sc ience and T echno l og y ,B e ijing N o r m a lU niver sit y,Be iji ng 100875,Ch i naA bstract :Sku ll registrati on is i m po rt an t i n com pu t e

4、r-a i ded t h ree-di m en si onal cran i ofaci a l recon structi on.The accuracy o f t he s ku ll reg ist rati on w ill d i rectl y affect t he vali d it y of the recon struction.In the paper ,an au t om aticm et hod for 3D s ku ll registration is p roposed .It cons i sts of t hree st ep s .F i rs,t

5、 so m e po i n ts on the crest li nes and t h e s m ooth s urfaces o f t he skull s are defi n ed as l andm arks i n considera ti on o f t he s p eci a l struct ure o f s ku lls .Then,I C P al gorith m is appli ed to rough l y ali gn t he t w o s ku lls .F i nally ,a fi ne registrati on bas ed on t

6、he CPD algo rit hm is i m p le m en t ed.E xperi m en t al res u lts de m onstrate t hat t he algo rit hm can effecti v el y i m p rove the accuracy of the s ku ll reg ist rati on and i s robust in t h e presence o f t h e parti al s ku l.l K ey words :reg istrati on;l andm ark;C rest li nes ;CPD0 引

7、 言顱面復(fù)原是對人類的顱骨進行面部容貌復(fù)原的技術(shù)?；陲B骨形態(tài)的顱面復(fù)原技術(shù)以顱骨的形狀特征為基礎(chǔ),以特定人群面部軟組織統(tǒng)計厚度為依據(jù),采用一定的算法適當添加顱骨之上的軟組織,從而達到面貌復(fù)原的目的1。軟組織的添加大致分為三種:一種是M ic hael 和Chen 提出的顱骨變形法2,用所謂的硬組織填軟組織;第二種是N elson 和M ic hael 研究的三維體積變形原理3,待復(fù)原顱骨的軟組織厚度值從與其相似的參考顱骨中得到;第三種是在人類學(xué)和法醫(yī)學(xué)的基礎(chǔ)上,建立軟組織厚度的數(shù)據(jù)庫4,根據(jù)具體的顱骨調(diào)用數(shù)據(jù)庫 中的資料,定量填充軟組織。目前,對前兩種方法的研究比較廣泛,而這兩種方法都要涉及

8、參考顱骨與目標顱骨的配準,因此,顱骨配準對顱骨面貌復(fù)原有著重要的意義。顱骨配準意味著參考顱骨上的每一點在目標顱骨上找到對應(yīng)的點,并且得到參考顱骨到目標顱骨的變換函數(shù)。然而,顱骨配準算法依賴于顱骨模型的數(shù)據(jù)表示,如體數(shù)據(jù)5或三角形網(wǎng)格模型6,7,使用小的離散的三角片明確的表示顱骨表面,文中實驗所用的數(shù)據(jù)采用三角形網(wǎng)格模型描述。目前,國內(nèi)外基于三維網(wǎng)格模型的顱骨配準算法研究還處于初級階段,如文獻6提出了基于Crest li nes 通過剛性變換和仿射變換進行配準,它只考慮了曲率變化大的點,因此對顱骨的不光滑區(qū)域能達到很好的配準效果,但對光滑區(qū)域則會存在很大的配準誤差;文獻7提出了基于Crest l

9、i nes 和顱骨表面部分光滑點采用I CP 8和TPS9進行配準,它進行了三次配準,每次配準又包含兩次I CP 與一次TPS 變換,雖然在配準時該算法能兼顧光滑和非光滑區(qū)域,但其配準過程復(fù)雜,耗時長,此外該算法沒有對缺損顱骨進行研究。因此,文中給出一種新的顱骨配準方法,通過自動提取C rest li nes 和第21卷 第2期2011年2月 計算機技術(shù)與發(fā)展COM P UTER TECHNOLOGY AND DEVELOP M ENTV o.l 21 N o .2Feb . 2011光滑表面的點作為特征點,采用I CP 和CP D 算法對完整和缺損顱骨都進行自動配準研究。相比較文獻7,它能同

10、時保證配準的效率和準確度,具有一定的魯棒性。1 CPD 基本原理CPD10是一種基于概率的點集非剛性配準算法。該算法被視為基于速度場運動一致性約束的最大似然估計問題,通過變分的方法表達運動一致性約束并得到規(guī)則化最大似然估計。在CP D 算法中,一個點集作為高斯混合模型的內(nèi)核,另一個點集作為高斯混合模型的數(shù)據(jù),采用確定性退火的EM 算法11,12對最大似然估計進行最優(yōu)化,從而找到兩個點集的對應(yīng)關(guān)系與非剛性變換,即內(nèi)核點集向數(shù)據(jù)點集配準。這種方法可以估計復(fù)雜的非線性非剛性變換,而且在含有噪聲和溢出點的情況下有較強的魯棒性。假設(shè)兩個點集,其中模板點集(內(nèi)核點集Y =(y 1, ,y M T(表示M

11、D 的矩陣,參考點集(數(shù)據(jù)點集X =(x 1, ,x N T(表示N D 的矩陣,M 與N 可以不相等,D 是點的維數(shù)。定義Y 0為內(nèi)核的初始位置,即內(nèi)核的當前位置定義為Y =v(Y 0+Y 0。高斯混合模型中點的概率密度為p (x =Mm =11mp (x |m ,其中x |m N (y m , 2I D 。使用貝葉斯理論,要得到參數(shù)Y 可以最大化后驗概率或最小化下面的能量函數(shù):E (W =-Nn=1logMm =1e -12x n -y 0m -Mk=1w k G (y 0k -y 0m 2+2tr (W TGW (1其中G M M 是對稱G ra m 方陣,元素g ij =e -12y

12、0i -y 0j2,W M D =(w 1, ,w M T是高斯內(nèi)核矩陣, 是常數(shù)。(1優(yōu)化:通過高斯混合模型聚類的E M 算法13推導(dǎo),能得到公式(1的上界(E -step:Q (W =N n =1 Mm =1Pold(m |x n x n -y 0m -G (m, W 222+ 2tr (W TGW (2其中P old表示由之前的參數(shù)值計算的后驗概率,G (m, 表示G 的第m 行。最小化Q 就相當于最小化公式(1的能量函數(shù)。將公式(2關(guān)于W 求導(dǎo),得到如下方程(M -step:Q W =12G (diag (P 1(Y 0+GW -PX + GW =0(3其中P 是后驗概率,p m n

13、=e-12 y old m -x n2/M m =1e-12y old m -x n2d i ag( 表示對角矩陣,1表示P 的列向量。兩邊同乘以 2G -1,得到方程的線性系統(tǒng):(d iag (P 1G + 2IW =PX -d iag (P 1Y 0(4從公式(4中解出W 就是EM 算法的M -step ,E-step 要求計算后驗概率矩陣P 。(2對噪聲的魯棒性:考慮到混合模型中的溢出點,改變后驗概率矩陣P (公式(4,p m n =e -12y o ld m -x n2/(2 2D 2+M m =1e -12y o ld m -x n2(5其中 =(1-out lier Nout li

14、er M,outlier 0,1表示噪聲的概率。CPD 算法流程如下: 初始化參數(shù) , ,構(gòu)建G 矩陣,初始化Y =Y 0 確定性退火 = ,直到收斂 E-step :計算PM -step :從公式(4中解出W 更新Y =Y 0+GW其中 表示退火率, 表示確定性退火算法中的溫度, 表示權(quán)值, 表示兩個點之間相互影響的力度。2 顱骨特征點的確定顱骨特征點是顱骨表面的一些在顱骨幾何形體上或解剖學(xué)上有意義并且容易定位的點,通過這些特征點,能夠唯一的標識特定的個體,并且滿足重建三維人臉造型的需要。2.1 C rest li nesCrest li nes14是顱骨表面的脊線,該脊線上點的最大主曲率(

15、絕對值沿主方向上局部最大,因此Crest lines 的計算與顱骨表面的偏導(dǎo)數(shù)有關(guān)。由于顱骨是網(wǎng)格模型,所以采用一種簡單的方法,通過兩個相鄰三角片的夾角大小來估計Crest li nes ,如果夾角大于設(shè)定的閾值,則將相鄰三角片的交線作為C rest li nes ,取Crest li ne 的兩個頂點作為顱骨特征點。如圖1所示為提取Crest lines 特征點的顱骨。圖中左側(cè)為參考顱骨提取的Crest li nes 特征點,右側(cè)為目標顱骨提取的Crest li nes 特征點。2.2 顱骨光滑表面特征點文中顱骨光滑表面特征點的提取與頂點的法線有121 第2期 白茹意等:基于ICP 和CPD

16、 的顱骨自動配準算法關(guān),如果某頂點的法線與其所有相鄰頂點的法線夾角都小于設(shè)定的閾值,則將該頂點作為顱骨光滑表面特征點。如圖2所示為提取光滑表面特征點的顱骨。圖中左側(cè)為參考顱骨提取的光滑表面特征點,右側(cè)為目標顱骨提取的光滑表面特征點。 3 算法步驟選取兩個顱骨模型,其中S Q 表示目標顱骨,S K 表示參考顱骨,參考顱骨向目標顱骨配準,即得到變換函數(shù)T 滿足S Q T (S K 。1分別提取參考顱骨和目標顱骨的Crest lines 對應(yīng)的頂點作為特征點,閾值為 1。2將S Q 與S K 利用從1中提取的特征點進行I CP 配準S Q SIc p 1K=r 1(S K 。3從I CP 配準后的特

17、征點中選取對應(yīng)特征點距離較近的點作為新的特征點,對S Q 與S K 進行CPD 配準S Q S 1K=d 1(SIcp 1K=T 1(S K 。4由于之前提出的Crest lines 都是曲率比較大的點,所以在Crest li nes 的基礎(chǔ)上增加顱骨光滑表面的點,閾值為 2,然后重復(fù)2和3的操作,最終得到S Q S 2K =d 2(S I cp 2K =d 2(r 2(S 1K =T 2(S 1K 。4 實驗結(jié)果文中算法在VS.NET 平臺下實現(xiàn),實驗所用的顱骨三維模型:參考顱骨由168604個頂點,335232個三角片構(gòu)成,目標顱骨由176567個頂點,351410個三角片構(gòu)成。如圖3所示

18、為兩次顱骨配準的結(jié)果,(a表示配準前兩個顱骨的重疊結(jié)果,(b表示以C rest li nes 為特征點的第一次配準結(jié)果,用于CPD 配準的特征點數(shù)為350,(c表示增加顱骨光滑表面特征點的第二次配準結(jié)果,用于CPD 配準的特征點數(shù)為500。實驗中,特征提取的閾值參數(shù)設(shè)置為 1=0.8, 2=0.9,CPD 算法參數(shù)設(shè)置為 =3.0, =1.0, =2.0,outlier =0 1,迭代次數(shù)為150。圖3 顱骨配準流程圖除此之外,將此算法作用于參考顱骨有缺損的情況,體現(xiàn)了CPD 算法的魯棒性,實驗結(jié)果如圖4所示。參考顱骨由151318個頂點,310755個三角片構(gòu)成。圖4 缺損顱骨配準結(jié)果圖中(

19、a表示有缺損的參考顱骨,(b 表示以Crest li nes 為特征點的第一次配準結(jié)果,(c表示增加顱骨表面光滑特征點的第二次配準結(jié)果。經(jīng)實驗證明,文中的優(yōu)勢在于:(1算法中涉及的特征點都采用自動提取方式,操作簡便易行。(2與文獻7相比,文中算法省去了第二次配準過程,即計算目標顱骨到參考顱骨的變換,將其逆變換作用于參考顱骨。這樣節(jié)省配準時間,提高了配準效率。(3由于CPD 算法的魯棒性,該算法在缺損顱骨中也得到很好的效果。但是,該算法中crest lines 的提取方法用相鄰三角片的夾角來估計,之后將對crest li nes 的提取方法進行進一步的研究。5 結(jié)束語闡述了一種基于CPD 的顱骨

20、自動配準算法,重點介紹了特征點的自動提取方法,CPD 算法的基本原理及配準算法流程。特征點采取自動提取方式,簡便易行,非剛性配準算法CPD 的引入使得該方法具有一定的魯棒性,實驗結(jié)果表明,文中的配準方法有效的提高了顱骨配準的準確性,基本達到預(yù)期效果。(下轉(zhuǎn)第126頁3 結(jié)束語針對在實際應(yīng)用Luce ne時可能存在的性能瓶頸問題,提出了一種以內(nèi)存為緩沖區(qū)建索引文件的分布式并行索引技術(shù),并對不同待索引文件數(shù)在不同索引技術(shù)下建立索引進行了對比實驗。實驗表明:隨著索引文件的不斷增多,以內(nèi)存為緩沖區(qū)建索引文件的分布式并行索引的優(yōu)勢越來越明顯。因此,以內(nèi)存為緩沖區(qū)建索引文件的分布式并行索引技術(shù)能夠有效緩解

21、在搜索引擎應(yīng)用中建索引的性能瓶頸問題。但該技術(shù)是以犧牲內(nèi)存為代價來換取時間的:內(nèi)存越大時間效率越高,故而對硬件要求相對較高,需要較高性能的計算機才能更好的實現(xiàn)該技術(shù)。參考文獻:1 吳寶貴.搜索引擎中索引技術(shù)研究與實現(xiàn)D.西安:西安電子科技大學(xué),2008.2 林 浩.基于綜合倒排索引的個性化搜索技術(shù)研究D.貴陽:貴州大學(xué),2008.3 張淳晟,鄭麗英.基于XML的搜索引擎倒排索引研究J.太原科技,2009(1:64-66.4 L i u Chun,Guo Q ing P i ng.Ana l ysis and R esearch of W ebCh i nese Retr i eva l Sys

22、t em Based LuneceJ.Co mputer society,2009(12:1051-1055.5 Zhang Y ong,L i Ji an-li n.R esearch and I mprove ment ofSearch Eng i ne Based on LuceneC Int ernati onal Conference on Intelli gentH u man-M achi ne Syste m s and Cybernetics.Zhejiang:s.n.,2009:270-273.6 Zhou N i ng,W u Jia X i n,Zhang ShaoL

23、ong,et a.l M i ni ngW eighted A ss oc i ati on Rul es w it h Lucene IndexJ.W ire l ess Co mmunicati ons,N et w orki ng and M ob il e Co m puti ng,2007(9:3697-3700.7 K m i M i n-Soo,W hang K yu-Young,L ee Jae-G i,l et a.l n-G ra m/2L:A Space and T m i e Efficient Two-Level n-G ra m Inverted Index Str

24、uct ureC Proceed i ngs o f the31stinternational conf erence on V ery large da t a bases.T rondhem i,N or w ay:s.n.,2005:325-336.8 H atcher E,Gospodnetic O.l ucene i n actionM.G reenw ich,CT,USA:M anni ng Publi cati ons Co,2004.9 Baeza-Ya t es R,G i onis A,Junqueira F P,et a.l Desi gnTrade-O ffs for

25、Search Eng i ne Cachi ngJ.AC M T ransacti ons on t he W eb,2008(10:1-28.10江毅銘.專業(yè)搜索引擎所以技術(shù)的設(shè)計與實現(xiàn)D.北京:北京化工大學(xué),2005.11樊景超,周國民.基于Lucene的 農(nóng)搜 并行索引技術(shù)研究J.農(nóng)業(yè)網(wǎng)絡(luò)信息,2009(8:30-31.12曾嘩垠.全文索引技術(shù)中索引歸并算法的研究與分析D.成都:電子科技大學(xué),2007.(上接第122頁參考文獻:1 王銀燕,梁榮華,吳福理,等.基于RBF插值的顱面復(fù)原算法J.系統(tǒng)仿真學(xué)報,2008,20(增刊:404-410.2 M i chael S D,Chen M.

26、The3D reconstructi on of f ac i al features usi ng vo l u me distorti onC i n:P roceedi ngs of t he14th Annual Conf erence o f Eurographics.UK Chapter,London:s.n.,1996:297-305.3 Ne l son L A,M ichae l S D.The applicati on of vo l u me defor mati on to3D faci a l reconstruction:a co mparis on w it h

27、prev i oustechniquesJ.F orensi c Sc.i In.t1998,94:167-181.4 Lan Yu w en,L iY ue w e,i Chen Shourong,et a.l The research of3D craniofac i a l reconstructi on s Indicati onC In:P roceedi ngs of t he11th B i enn i al Sci entifi cM ee ti ng of t he Internati ona lA ss oc i ati on for Crani o f acial Ide

28、ntificati on.DaL ian:s.n.,2004:102-121.5 J onesM W.F ac i a l reconstruction usi ng vo l u metr i c dataCi n:Ertl T,G i rod B,G re i ner G,et a.l Proceedi ngs o f t heV ision,M odeli ng,and V is uali zati on2001,G er many,N ove mber21-23,2001.Amst erda m:I O S P ress,2001:135-142. 6 Q ua treho mme G,Coti n S,Subsol G,e t a.l A full y3D me t hodfor faci a l reconstruction based on def or m able m odelsJ.J.Forensic Sc,i1997,42(4:649652.7 TurnerW D,Bro wn R E,Ke lli her T P,et a.l A n