HDM: an heterogeneous structures deformation mode

HDM: AN HETEROGENEOUS STRUCTURES DEFORMATION MODEL Montse Bigorda Dani Tost 27th March 1998 Keywords: Volume deformations - FFD - Medical ApplicationsVolume Data 1 Intro duction In the last decade Computer Graphics applications in medicine havegrown due to the advances of input technologies such asMRAandCTwhich enable the construction of three-dimensional representation of anatomical structures and their visualization. Volume data representation schemes have b een studied, particularly the voxel mo del for regular input data Kau90] and, for non-regular data sets, the tetrahedral cell mo del CFM + 94] along with more compact representations such as o ctrees WG92], multitetras, and frequency domain representations, as wavelettes Mur93]. Ma jor attention has b een paid to the problems of the accuracy of the representations, their memory requirements and their adequacy for the visualization. However, these mo dels are generally static: the representation of the temp oral evolution of volume data, particularly their deformation has b een less addressed. Dierent medical applications need the simulation of deformations of the shap e of anatomical structures. As an example, in oncological studies, it is often necessary to simulate or to predict the growth of a tumor whichmay pro duce the deformation of the surrounding structures and therefore provoke secondary pathologies. A particular case of this, are the emb olisms caused by the stenosis of a cerebral vessel due to the pressure of a brain tumor. Other examples of deformations in medicine are those pro duced by external forces, such as the bisturi pressure. In this pap er, the problem of the deformation of heterogeneous volume data sets is analyzed. A general metho d is prop osed, enabling the simultaneous deformation of b oth the interior and the shap e of various imbricated structures. The metho d supp orts dierent deformation mo dels according to the particular hyp othesis of each structure elastic b ehavior. The pap er is structured into three sections: rst the previous work is reviewed, next the prop osed metho d is describ ed and nally some simulation examples are discussed b efore the conclusions. 1 2 Background 2.1 Previous work Shap e deformation consists in the mo dication of either the geometry or the top ology of a surface. There are two main deformation b ehaviors: elastic ones, which are asso ciated to geometrical mo dications, and non-elastic ones, which corresp ond to structural changes such as fractures. Most of the deformation literature has fo cused at shap es represented explicitly either as p olygonal meshes or smo oth sculptured surfaces, although, recently, some pap ers address the deformation of discrete, voxel-based, surfaces. Surface deformation has b een mainly used for the following purp oses:  Simulation of physically realistic deformations such as those pro duced by ob jects collisions and material heating and fusion. TW88], KT91].  Smo oth surfaces interactive design by successive deformations of an initial rough shap e SP86], Co q90], HHK92] and sculpturing of discrete surfaces in binary voxel mo dels (GH91],WK95])  Animation of non-rigid structures, such as articulated or legged gures GVP91] and blobby mo dels (WMW86]).  Morphing b etween twoshapes KCP92], BN92], CSB95] and morphing between twovolume data sets Hug92], LGL95].  Segmentation of regions of interest in 2D images and 3D volume data by successive deformations of a temptative curve (snake) KWT88]or a p olyhedral approximation MBL + 91](GW92]) of the shap e of the region.  Matching b etween two geometrical or volume mo dels in order, for instance, to compare the anatomy of a patient with a previously created representation of an anatomical atlas mo del (BK89]) or to matchtwo dierent mo dalities of registration Dav97]  Reconstruction of a binary discrete 3D mo del from a set of semi-transparent image pro jections of it (Mur91]). Shap e deformation mo dels fall into three main categories: kinematic, dynamic and mo dular mo dels. The kinematic mo dels enable to compute the deformed mo del on the basis of geometrical information only,typically byinterp olating new p ositions using a user-sp ecied subset of displacements. Two main dierent kinematic approaches have b een published: the application of non-linear geometrical transformations such as b ending, tap ering and twisting (Bar84], CR94]and Free-Form-Deformations (SP86]) along with their numerous extensions (Co q90], CJ91], HHK92]). Dynamical mo dels simulate physically realistic b ehaviors and mo del the deformations pro duced by forces and torques according to physical laws of elasticity and materials resistance TF88]. Mo dular mo dels, also called layered mo dels, are based on a multi-level representation of the ob jects: a rst simplied layer, to which dynamical deformations can b e applied, and a second layer, comp osed by the surface or skin of the structure tied to the kernel layer according to kinematic constraints GVP91]. 2 2.2 Statement of the problem Most of the previously cited deformation mo dels are surface-based , i.e. they assume that the ob jects are empty and they do not address the impact of the surface deformation on their internal structure CEO + 93]). This hyp othesis, valid in numerous cases, is no longer acceptable in many medical applications where the real b ehavior of the ob jects should b e simulated. Several attempts have b een done to mo del the 3-D volumetric nature of the ob jects suchas CEO + 93] and BNC96] which generalize to 3D the elastic deformation mo del, using a 3D nite element mesh, in order to b etter simulate surgical cuts. However, these mo dels assume that the interior of the ob jects is homogeneous or, at least, that the prop ertyvalues in their interior remains unmo died under deformation. In addition, the deformation is applied to a single 3D anatomical structure mo del extracted from medical images. Nevertheless, anatomical regions are comp osed of various homogeneous and heterogeneous imbricated structures. The surface of an anatomical structure cannot always b e deformed aside from the surrounding regions, b ecause its deformation mayprovoke the deformation of the external and the internal structures as well. Figure 1 illustrates this idea. In gure 1.a a mo del comp osed of two-regions is represented schematically with two dierent ll-area patterns. The surface of the internal region has b een identied. In gure 1.b, this surface has b een deformed indep endently from the prop ertyvalues of the surrounding volume. The eect pro duced is that the b oundary no longer encloses the circle-pattern region. Figure 1.c illustrates the desirable result, in which the volume prop erties have b een mo died in accordance to the surface displacement. Figure 1: Interrelationship b etween volume and surface deformations Herein a general framework for the deformation of volume mo dels is prop osed. Its main feature is that it is hybrid : it enables deformations of b oth the surfaces and the volume. This is accomplished by propagating the surfaces displacements to their internal and to their surrounding volume and therefore, to the other emb edded structure b oundaries. This general framework is suitable for any deformation mo del, kinematic as well as dynamic. Herein however, a sp ecic development is analyzed, based on a kinematic mo del with constraints. This mo del will b e referred as HDM (Hybrid Deformation Model) in the rest of the pap er. 3 3 The Hybrid Deformation Mo del 3.1 General framework The pip eline of the prop osed framework is illustrated in gure 2. The representation mo del is a grey-level, heterogeneous voxel mo del emb edding dierent regions corresp onding to various anatomical structures: organs, b ones etc. This mo del is obtained by registration of data using medical devices suchasCTsand MRs and by applying ltering and segmentation pro cesses whicheventually remove the noise of the input slices and enable the identication of the anatomical regions. The b oundary surfaces of the structures are not represented explicitly but they can b e extracted from the voxel mo del either using a marching cub es algorithm or bycontour extraction and tiling b etween successivecontours. The application receives as an input a set of displacements of p oints b elonging to the surface of one or more anatomical structures interior to the voxel mo del. These input p oints can b e obtained in dierentways: they can b e, for instance, the co ordinates of an electronical scalp el pressing the surface of an organ, or they can b e interactively sampled on the surface of a tumor contiguous to anatomical structures, whose deformation is b eing studied. With these input data and the original mo del, the application computes the shap e deformation and the resulting mo dication of the prop erties of the voxels inside and outside the structure. The output of the application is a new grey-level voxel mo del emb edding the deformed regions. This new mo del can b e manipulated as the original one, i.e., it can b e visualized, the deformed surfaces of the inner regions can b e extracted from it, etc. model voxel model Deformation Voxel displacements Surface points Deformed voxel model structures identification Structures Segmented classified Figure 2: Pip eline of the prop osed metho d 3.2 Description of the metho d 3.2.1 The data As mentioned ab ove, the discrete representation of the volumetric mo del b efore the deformation, V ,is avoxel mo del such that: V = f v ij k j pr op ( v ij k )=  ij k g (1) where the voxel v ij k is characterized by its prop ertyvalues, for instance, its density  ij k . 4 The dierent regions, or anatomical structures, inside the voxel mo del have b een previously segmented in suchaway that each region has an unambiguous prop ertyvalue range. 1 . The region surface pass through the b oundary voxels characterized by a non-homogeneous neighb orho o d. In addition to the classical transfer functions which asso ciate to the dierent prop erty ranges opacityand color values, new transfer functions have b een designed which provide elastical prop erties for each range. These functions are empirical, based on the physicians knowledge. The input data of the deformation, D , are pairs of homologous p oints of the region surfaces b efore and after the deformation: D = f ( p 1 p 0 1 )  ::: ( p n p 0 n ) j8 i =1 ::n p i 2 Sp 0 i 2 S 0 p 0 i = Def orm ( p i ) g (2) where S is the initial surface structure and S 0 is the deformed surface structure. 3.2.2 The deformation The prop osed metho d is comp osed of three consecutive steps, called Identication , Deformation and Restructuring . At the rst stage, the surface of interest is identied inside the voxel mo del V .From the input data D of the desired deformations and, applying a surface deformation technique, the deformation stage deforms the whole voxel mo del, obtaining a non-regular lattice mo del. The restructuring step computes a regular voxel mo del equivalent to the non-regular lattice mo del. Eachstepmay b e p erformed according dierent strategies. Next a particular implementation of this pip eline is describ ed. However, any other surface identication and surface deformation could have b een applied as well. Identication As mentioned ab ove, the HDM deforms b oth the surface and the volume. Therefore, b oth information must b e represented simultaneously and p oint one to each other. Thus, the requirement of the surface identication is to create a p olygonal mo del of the surface, to which a surface deformation mo del could b e applied, while preserving information of the voxels to which the surface faces b elong. The technique most used to extract a surface from a voxel mo del, is the Marching Cubes technique LC87], which gives an approximation of the surface as a set of up to three p olygons inside eachvoxel, using trilinear interp olations of the prop ertyvalues to compute the surface vertices. The marching-cub es surface mo del is complex, made of many small faces, and it lo oses the information of the voxels to which the vertices b elong, unless sp ecic data structures are designed to keep this information. Herein, a simpler approximation of the surface is used: the cub erille mo del UG93] which is comp osed of the b oundary faces of the b oundary voxels. Before 1 In MRA data, representingvascular information, this range segmentation is not always feasible, as vascular structures do not corresp ond to sp ecic ranges but to lo cal maxima. In this case, the volume mo del is constructed after the segmentation using lab elling prop erty values instead of the original data. 5 the deformation, this surface is comp osed by isothetic faces which are parallel to the co ordinate planes. After the deformation, these faces are obviously no longer isothetic. Although the surface representation is rough, it has a lower memory requirement than the marching cub es mo del, b ecause it needs to store only one vertex p er voxel. Boundary voxels and their b oundary faces can b e computed on the y. Deformation The deformation stage itself p erforms two related pro cesses: the computation of the displacements of the vertices of the voxels under deformation surfacedeformation and the computation of the new prop ertyvalues of the deformed voxels volume deformation . The surface-deformation implemented herein is an extended kinematic mo del based on the Free-Form deformation (FFD) SP86] metho d. It consists of three steps: 1.- Creation of parallelepip ed regular lattice enclosing the cub erille surface of the whole anatomical structure. A lo cal co ordinate system is asso ciated to this lattice, having a vertex of the lattice P 0 as the new origin and b eing the main directions S , T , U parallel to the lattice. The vertices V ij k of the lattice cells ( control points ) b efore the deformation are: V ij k = P 0 + i l S + j m T + k n U (3) where l, m, n are the numb er of sub divisions of the mesh in each direction. 2.- Sp ecication of the deformation in terms of displacements of the control p oints of the lattice. As the input deformations D are p oints of one or more cub erille surfaces b eing deformed, the displacements of the control p oints should rst b e computed. This problem has b een addressed in HHK92]. It requires the computation of the pseudo-inverse of a matrix to derive the displacements of the control p oints that minimize the error between the sp ecied displacements and the actual deformation using a squared dierence error metrics. As p ointed out in LWCS96], the pseudoinverse matrix computational cost is very high when the number of points that should b e moved is large. Therefore, the prop osed metho d uses the approachofLWCS96] which pro duces similar results to HHK92] without calculating the pseudo-inverse matrix. The interface of the p oints deformation sp ecication restricts the range of the allowable displacements and guarantees that the FFD lattice is still structured and that its cells do not auto-intersect. In addition, some simple dynamic constraints can b e taken into account, preventing the vertices of some structures interior to the deformed cub erille surfaces from b eing mo died. This enables, for instance, to deform structures such as the skin while keeping the b one unmo died. In order to keep rigid structures, the closest lattice vertices enclosing them are xed and again the interface prevents the sp ecied deformations to break the regular structure of the lattice. 6 3.- Computation of the displacements of the vertices of the cub erille surface and of the vertices of the inner structure voxels. All the vertices are deformed except those b elonging to rigid structures. The regular deformation of a vertex is computed according to the formula prop osed in SP86]: P ffd = l X i =0  l i  (1 ; s ) l ; i s i 2 4 m X j =0  m j  (1 ; t ) m ; j t j " n X k =0  n k  (1 ; u ) n ; k u k V ij k # 3 5 (4) The volume deformation consists of computing the prop ertyvalues of the deformed voxels. The volume is considered as an heterogeneous set of various structures which are themselves homogeneous b efore and after the deformation. Rigid structure voxels remain unmo died, whereas voxels interior to deformed shap es haveaconstant mo died value. In the deformation, the volume of the structures either increases, decreases or remains constant. The density computation is based on the hyp othesis that the matter quantity remains constant through deformation and thus, the changes in the densityvalues are prop ortional to the mo dication of the volumes. Finally, as a result of the deformation stage a non-regular deformed lattice mo del is obtained. Restructuring At this p oint of the pip eline, the original voxel mo del has b een deformed and it is now non-regular although it is still structured and top ologically equivalentto its initial shap e. The restructuring stage allows to regularize it, while keeping the deformations of the inner structures. This stage is thus essentially equivalent to a re-voxelization Han90], although, by opp osite to other re-voxelizations pro duced by ane transformations such as rotations of the volume it has to deal with a non-ane transformation. The equivalentregularvoxel mo del is computed as the same resolution as the original one. However it may b e computed at any resolution as well. The restructuring stage consists thus in a scanning the regular voxel mo del and computing for eachvoxel whichvoxels of the deformed mo del have a non-zero intersection with it. It should b e noticed that a voxel of the lattice mo del can corresp ond to one o more voxels in the voxel mo del. If the corresp ondence is unique, the regular voxel prop erty is simply set to the deformed voxel prop erty.However if more than one deformed voxel intersects the regular one, their resp ective prop erty value are weighted and accumulated (see gure 3). 4 Simulations and results Color Plates 1 to 8 show the results of a 2D prototyp e simulation of the deformation mo del. Being a 2D, it would b e more prop er to talk in terms of pixels 7 Figure 3: Restructuring rather than voxels, however, for coherence with the rest of the pap er, the term voxel has b een preferred. In Color Plate 1 the original image data of a CT scan of a head are visualized. Two cub erille surfaces are identied in the image: the external surface of the brain and the surface of a tumor, depicted in blue and red resp ectively in Color Plate 2. The elastic b ehavior of b oth surfaces is considered identical. The FFD net computed as the b ounding b ox of the whole ob ject is shown in Color Plate 3. From sp ecied values of displacements of several p oints of the brain surface, the deformation of the control vertices of the FFD are computed and represented in Color Plate 4. Color Plate 5 shows the results of the deformation on the volume. In order to allow a b etter understanding of the image, macro-pixels of 10x10 are represented. It can b e observed that the original voxel mo del is no longer isothetic. The deformed cells b ehave as closed compartments which drag the matter inside them in their deformation. The color of the cells changes according to the mo dication of the densityvalue inside the cell. The new density is computed as the previous value of densitymultiplied by the ration b etween the previous voxel area and the new voxel area. The deformation has b een applied only at the voxels which are inside and on the cub erille surface of the brain. Being inside the brain, the tumor is also deformed. Color Plate 6 shows the volume once the restructuring step has b een p erformed. The general asp ect of the image is quite similar to Color Plate 5. However the voxels are now parallel to the co ordinate axis. The voxels which fall completely inside a deformed structure are considered homogeneous and therefore they are not mo died. The voxels which exhibit dierences with Color Plate 5 are those that intersect the surface, b ecause their value is computed as a weighted average of the deformed voxels whichcover them. Finally Color Plates 7 and 8 show a more complex deformation. 5 Conclusions and future trends A general framework for the 3D deformation of multiple structures represented implicitly in a volumetric voxel mo del has b een prop osed. The mo del is hybrid in the sense that it enables the deformation of a surface inside the volume 8 mo del and the mo dication of the internal prop ertyvalues as a result of the compression or expansion of the deformed surface. The surrounding volume is also mo died in relation to the deformation. A rst kinematic prototyp e implementation of the mo del on 2D images, based on the use of FFD has b een describ ed. The results of the simulations are encouraging and make it necessary to implement the three-dimensional version of the mo del. This implementation is currently b eing done. The integration of dynamic constraints to the mo del is another research line under progress. Up to know only homogeneous and rigid b ehavior are allowed. The use of the true elastic prop erties should b e enabled. Non-homogeneous propagation of the deformation though the volumes prop erties should also b e studied. Finally, a future extension of the metho d is its application at dierentlevels of resolution of the voxel structure, enabling higher precision in zones of interests and coarse deformation in areas of less relevance. References Bar84] A. H. Barr. Global and lo cal deformations of solid primitives. ACM Computer Graphics , 18(3):21{30, July 1984. BK89] R. Ba jcsy and S. Kovacic. Multiresolution elastic matching. Computer Vision, Graphics and Image Processing , 46:1{21, 1989. BN92] T. Beier and S. Neely.Feature-based image metamorphosis. ACM Computer Graphics , 2:35{42, July 1992. BNC96] M. Bro-Nielsen and S. Cotin. Real-time volumetric deformable mo dels for surgery simulation using nite elements and condensations. Eurographics96 , 15(3):57{66, 1996. CEO + 93] S.A. Cover, N.F. Ezquerra, J. O'Brien, R.Rowe, T.Gadacz, and E. Palm. Interactively deformable mo dels for surgery simulation. IEEE Computer Graphics and Applications , pages 68{75, November 1993. CFM + 94] P. Cignoni, L. De Floriani, C. Montani, E. Pupp o, and R. Scopigno. Multiresolution volume dataset mo deling and visualization based on simplicial complexes. INRIA , 1994. CJ91] S. Co quillart and P. Jancene. Animated free-form deformation: An interactive animation technique. ACM Computer Graphics , 25(4):23{26, July 1991. Co q90] S. Co quillart. Extended free-form deformation: A sculpturing to ol for 3d geometric mo deling. ACM Computer Graphics , 24(4):187{ 196, August 1990. 9