ѧ
JOURNAL OF SOFTWARE 
1999 10 5 Vol.10 No.5 1999



״֯-Ԫͷ
͡Ⱥ
ժҪͳҽѧͷڽݱΪǶеƬ,Ǽ򵥵άԪ.ʵ,Ľṹ൱,Щ򵥵ͷȻӦƵҪ.̽ܡѪܵȹ״֦ṹͷ,ɢ֦˽ṹ,ϻԪmetaballʽͷ״֯ģ.ͷʹ״֯ӵ˽ṹԱ,ұ֤˷֦֮ӵĹ⻬.
ؼʡ任,任,Ԫ,ʽ.
ͼšTP391
Modeling Technique Based on Media-axis and Metaball for Vessel Biomedical Structure
GUO Hong-hui1PENG Qun-sheng1LI Jie2
1State Key Laboratory of CAD & CGZhejiang UniversityHangzhou310027
1Department of Computer Science and TechnologyTsinghua UniversityBeijing100084
AbstractThe modeling of medical volume data has drawn public attention recently since traditional approaches, such as triangle tiling of the contour surface and 3D array of voxels, do not fit for the efficiently rendering, especially for rendering of vessel structure. In this paper, an algorithm for modeling vessel biomedical structure based on the extraction of medial-axis and the interaction of metaballs is proposed. The authors adopt distance transformation to extract the medial-axis, and use the metaball to describe the structure. The results show that this model not only remains the complicated topological structure, but also assures the smooth shape of rendering result.
Key wordsMedia-axis transform, distance transform, metaball modeling, implicit surface.
ҽѧӻо,Ѫܡ񾭵ϸ΢֯ĻһֱǸʮֵּ.ͳĻƷҶͶӰл,ַڼвûнκάģ,ϸ˵ⲻάؽ.Ѫڷֲ,֦ڶ,̬ϸС,ôͳͷ޴,ݲɼϵͳȷ,ϸС֦©,,ǳرѪܵ.ֻ΢ṹ,ѪѱŴͼ岿ʱ,ſԲƴʵӷлƣ1.ҽѧӻӦ÷ΧĲ,Ѫ̬ƵҪԽԽϸ,,ģжҪѪܡ񾭵̬λñ׼ȷ.,ϸṹʱ,״֯Ϊزٵһɲ.,״֯ͷʼܵע,,MoriṹѪֲܷ,ϳȡĵֵϢ,Marching Cubesлƣ2.ַֻԿɼ֦б,SGI(Silicon Graphics Incorporation)Ͽɴﵽʵʱ,Ҫڿϵͳ.KrieteTalhamiL-ϵͳ֦״ֲ3.Ge˲ϸ㷨õ󳦵ĹǼܽṹ4.Masutani˹ѡȡʼ,Ȼ̬ѧҵѪܵĹǼܵ5.ַԵõѪܵĹǼܵ,ҿԵõǼܵӹϵ,ûйǼܵİ뾶Ϣ,ƵѪܴϸͬ,ʵ.
ĽһʽϵѪܱ﷽,ԽϺõؽͻƸ֦״״֯.ͳʽͷʵηͶʵ໥÷.Ѫܰ뾶ϸС,֦ڶ,üʵȻԱƽ.öС໥ԵõѪܱǿе.ڶеmetaballͼ.һѵ,ȷСλ÷ǳ,ҪѪܵĴ˽ṹ.ͼеἼΪṩ˷.,ǽ֮ƹ㵽ά,ȡѪݵ˽ṹ.
1Ѫ˽ṹ
ѪǿȽխĶ֦״֯,,˽ṹΪ.
ȶxAľΪ
ds(x,A)=inf{d(x,z)|zA}.(1)
õľŷEuclidean,⻹г飨city/block롢̣chessboardȵ.Bĳ߽еļ,ԸеÿһPڱ߽Bϲĳ־ҳĵ,ֵΪԵ,Ǹо1ϵԵĵļ.ͨΪԪʽ(x,ds(x,B)),ds(x,B)϶ĵx߽ľ.ᶨбе㵽߽С,,λϵԲĲ߶Ӧ.ЩԲ̵Ϊ߽Զĵ.ЩԲ̳ΪԲ,ƹ㵽άΪ.ἴΪ.
ͳȡ:
 1ϸ,ȥı߽,ͬʱ뱣֤ͨԲƻ,ĵ.ַģ巽ʽʵ.ȡԱ˽ṹ,Ǽܴ,Ҷ̵ķ֦ױĨ.
 2Ϊ任ķ,ȶԭͼо任,ҳÿ߽ľ,ĵȡ,Ϊ.ַʵ,Чʸ.ɴ˷õɢֲܲͨ,߶ѵ.
ڲʽ,ڹʽǡÿѡЩɢ,ʹ,,õ2ַȡҪ.
Ϊȡ,ͨȽӱз,תɶֵͼ.ٲþ任,ҳ߽Զĵ,Ӷȷ.,任ƹ㵽ά.ҽѧݿɰƹķо任.
任RosenfeldPfaltz1966ģ6,ּڲ˲ķÿ߽С.ͼ֮ľжֶ巽.ŷΪֱ۵ľ붨巽.ŷļ,ҪĵϢ,,ͨС洢ҲСchamferͰ˽Σoctagonalбƽ.ѡһ㷨Χ.
ڶά,ԱڵؾΪd1,ԵڵؾΪd2ͼ1(a)ʾ,P1,P2x,yطֱΪm1,m2,ͼ1(c)ʾ,m1m2,ȡ

|P1P2|=m2d2+m1-m2d1.(2)

ŷ֮Ϊ

d1=1,d2=2ʱ,ϾΪ,󵼺֪,m1=m2=Mʱ,Dȡֵ0.41M
d1=1,d2=infinityʱ,ϾΪ(4-),ʽ(2),֪|P1P2|=m1+m2,,m1=m2=Mʱ,Dȡֵ
濼d2ȡʱ,DֵܴﵽС.
d1=1,d2=d2,ʽ(2)Ϊ


ʱ,dΪ.
ƹ㵽ά֪:d1d2d3=11.3141.628.
ɴ,ǵõһֱȽϼ򵥵ľ任㷨,333ģݽж.Ѫݱ־Ϊ1,Ϊ0,
(1) ǰ˲:ݰ¡Ӻǰҽ˲,㷨:
for i=top to bottom
for j=back to front
for k=left to right
vi,j,k=minvx,y,z+wx,y,z
(x,y,z)Ϊ(i,j,k)ǰ,ǰʱ,(i,j,k)֮ǰԪ.wx,y,zΪ(x,y,z)(i,j,k)ľȨֵ,ֱȡ1,1.3141.628.
(2) :ǰһ˲ͬ,ֻǷ෴,㷨:
for i=bottom to top
for j=front to back
for k=right to left
vi,j,k=minvi,j,k,vx,y,z+wx,y,z
(x,y,z)Ϊ(i,j,k)ĺ,ǰʱ,(i,j,k)֮Ԫ.wx,y,zΪ(x,y,z)(i,j,k)Ȩ,ֱȡ1,1.3141.628.
任,ĵ㱻Ϊ,

vx,y,zݣvi,j,k+wx,y,z.(7)
(x,y,z)ʾ(i,j,k)26,wx,y,zΪӦľȨֵ,һԲ.
ɴ˳ȡɢ,任ÿԪаľΪ߽ŷ.ʾΪ
(i,j,k),v(i,j,k).(8)
㷨ڳȡ,ҳ˹ϵ,Ȼؽ.һͼһѵ,ĿǰҲδԲ.ף5ⷽĹ.ĵؽǸλЩ໥õ.ǲܵŻѡȡ㷨,аС,ѡȡ뵽ģ,,֮ӱòҪ.
2Ѫܵʽؽ
ɼʵ,򡢳,츴״ʽ͵ķ2080,Ҫ.෽ͷ.
(1) ʡ,ͨȶ23.
(2) ɵԶǹ⻬,ŴԱֹ⻬.
(3) ڽбģ,Ķǳ.
(4) ʺϱ塢ٺҺ.
(5) ڸ˽ṹʺϲCSGķ.
µĶ巽7:
عS={PR3|f(P)=iso.}(9)

  (10)
Ƕƺĵ.ƺΪϵļ򵥴,亯ֵݼ,isoΪֵֵ.һ๤,ڶе,ǵҪƺĶĵͬ,Ƚϵ͵,Blinnָ8ݡMurakiġblobby9ݡWyvillġsoft object10ݵȵ.PerlinڱʾķֶζζʽҲص11.
⼸ƺ巽ûб,Ǵ뵥ݼĺ,ڷֶκ,ڷֶεϱ뱣n,״nƽҪ.һҪעص,÷ֶκֲ֧ŵ,عʱԽľֲа.
ϣ򵥵ķֶζκΪƺؽ,ͼ2ʾ.ҪСڵֵֵʱԺ,ڵֵֵʱöκ,RʱΪ0,ei,RҪC1.

ʽ(15)(16)(17)r,

ʽeiΪɼ뾶,RiΪЧ뾶(ҲΪӰ뾶).eiƺֵΪֵֵ,һȡΪ1.0.Ri̶ʱ,kiı仯Կཻ֮״,ͼ3ʾ.Ȼ,kiΪһֵʱ,kiľֵԽ,Ӱƺ仯Խ,֮ʲ״.֮,kiľֵԽС,Ӱƺ˥,֮ƽ.

ʽ湹ֵһѵ,ķֲȷ,ʹͽԿ,ʱ벻״.ʾֲһ.ѪݵϢ˺ݵֵڵļ뾶.Щķֲ,ѡɵֵʵ.۴ѡȡʵԼ뾶ԵŻ㷨.


(a) |ki|=1(b) |ki|=10 
ͼ3kiԵֵ״Ŀơ
ͼ4ʾѡiӦƺΪfӰľСӰ6뾶ķΧΪӰڵݵʾΪpiisoΪֵֵʳڵֵڵĵļϱʾΪSڵֵĵļϱʾΪSNѡ㱻ѡ,iΪ
(28)
Eiʱ,Աؽ.
㷨˼Ϊ:
Ƚгʼ,ݵΪδؽ,Ϊܵĺѡ.δﵽؽȻкѡδѡ,ʽ(28)ѡȼ,Խ,ȼԽ.ѡȡEiĵiΪѺѡģ,ȻŻѡеĺѡĲ.
㷨Ա:
modeling ()
{
initialize ();/* ʼ,Ϊѡ */
while (curcountprepcount) {/* ؽȲ */
choosebestprimitive(&p);
if (plist==NIL) break;
addprimitive(p);/* ģͱ */
prepcount=curcount;
adjustparameter(p);/* ԲŻ */
}
}
ڵ1ھ任,Ѿ㵽߽Ľŷ.ؽʱ,ʵ໥Ӱ,ʵе,ҵʹؽѵĲ.,kؽĹ⻬̶,뾶ʵӰ.ǲ㷨вŻ.
adjustparameter()
{searchradius(); /* Ż뾶 */
deleteprimitive(); /* ɾȥѡprimitive */
modifydatamask();/* ѱؽݵ */
}
,뾶㷨:
PΪ۵ʵ,뾶Χѡ0뾶v(i,j,k)֮䣨ʽ(8).count1¼Ӧؽȴؽݵ,count2¼¼ؽĸ.count1ԽСԽ,count2ԽԽ.
searchradius(P)
{
Lrad=0.0;/* С뾶Ϊ0.0 */
Hrad=Prad;/* 뾶 */
Last.count1=0;
Last.count2=1;
if (meet (Lrad,Hrad)) return; /*  */
computeeachcount (P,&Head); /* Pcount1,count2 */
while (Hrad-LradEPSILON) {
Rad=Prad=(Lrad+Hrad)/2.0;
compute-each-count (P,&Cur); /* Pcount1,count2 */
if (optimization-rule (Last,Cur,Head)){/* жӦ */
Lrad=Rad; /* ǰ*/ 
Last=Cur;
} else {
Hrad=Rad; /*  */
Head=Cur;
}
}
}
㷨ıԲϼϸ,ʵʱıƽԽԽȷ,ұ˲÷ѷ(Ȳһʵݵ,ٶԱƽϸڵķ)ĵЧ,жʱ,Ҳѷ,򽫳ʼǼܵڿնж㷨ʧЧ.ͬʱ,㷨ŻҲӺ.
3ʵ
ǲñķǻƬеܡѪܽ.ȶܡѪռݵԪз,Ȼ˲о任,ȨֵñƵŻ任.ͼ5Ϊģ,ͼ5(a)ΪбΪܵݵ,ͼ5(b)Ϊؽ.ͼ6ΪǻвѪܵ,аǻǻԼζȵѪ.ͼ6пԿ,-ԪͲ˴֦,һƽнǿ,ֻǶڽϴʵ壨ͼ6еͣ,ַ.


(a) ݵ㡡(b) ͺؽͼ6ǻѪܵ
ͼ5ܵ
4ᡡ
ʽѪܡܵȹ״֦֯͵ķ.Ƚĳȡ,ȻƵ򵥵ܺ,ؽеŻ.ؽĹ״֯ƽ,˽ṹ.ؽ˻ؽеӦ⡢֦.ʽ﷽ʽ,ڻ.
оõȻѧ.
߹,Ů,1969,ʿ,ҪоΪҽѧϢӻ,ҽѧͼ,ͼѧ.
Ⱥ,1947,ʿ,,ʿʦ,ҪоΪʵͼ,,ά,ͼֽɨʶ.
,1973,ʿ,ҪоΪʵʱͼʾ,ֱ,ѧӻ.
ͨѶϵˣȺ, 310027,㽭ѧCAD&CGصʵ
ߵλ͡Ⱥ㽭ѧCAD&CGصʵҡݡ310027
ݣ廪ѧѧ뼼ϵ100084
ο
[1]Suto Y, Kato M et al. Three dimensional display of X-Ray CT image extraction and display of cerebral ventricle. The Visual Computer, 1986,2(2):9096
[2]Mori K, Hasegawa J et al. A fast rendering method using the tree structure of objects in visualized bronchus endoscope system. In: Hohne K H ed. Proceedings of Visualization in Biomedical Computing'96. Hamburg: Springer-Verlag, 1996. 3342
[3]Kriete A. Hierarchical data representation of lung to model morphology and function. In: Hohne K H ed. Proceedings of Visualization in Biomedical Computing'96. Hamburg: Springer-Verlag, 1996. 399404
[4]Ge Y, Stelts D et al. 3D skeleton for virtual colonoscopy. In: Hohne K H ed. Proceedings of Visualization in Biomedical Computing'96. Hamburg: Springer-Verlag, 1996. 449454
[5]Masotani Y, Masamune K et al. Region-growing based reature extraction algorithm for tree-like objects. In: Hohne K H ed. Proceedings of Visualization in Biomedical Computing'96. Hamburg: Springer-Verlag, 1996. 161171
[6]Borgefors G. Distance transformations in arbitrary dimensions. Computer Vision, Graphics, and Image Processing, 1984,27(3):321345
[7]Bittar E, Tsingos N et al. Automatic reconstruction of unstructured 3D data: combining a medial axis and implicit surfaces. Computer Graphics Forum, 1995,14(3):457468
[8]Blinn J. A generalization of algebraic surface drawing. ACM Transactions on Graphics, 1982,1(3):235256
[9]Muraki S. Volumetric shape description of range data using blobby model. Computer Graphics, 1991,25(4):227235
[10]Wyvill G, McPheeters C et al. Data structure for soft objects. The Visual Computer, 1986,2(8):227234
[11]Perlin K. Hypertexture. Computer Graphics, 1989,23(3):253262

1997-08-22յԭ,1998-05-19յ޸ĸ
