Projects

This page includes summaries, manuscripts and multimedia materials for previously published research projects I have worked on.
You can also find information on certain ongoing (in preparation/in review) projects here.

A Second-Order Virtual Node Algorithm for Nearly Incompressible Linear Elasticity in Irregular Domains
Y. Zhu, Y. Wang, J. Hellrung, A. Cantarero, E. Sifakis and J. Teran
Journal of Computational Physics (accepted, to appear), 2012

Abstract: We present a cut cell method in R2 for enforcing Dirichlet and Neumann boundary conditions with nearly incompressible linear elastic materials in irregular domains. Virtual nodes on cut uniform grid cells are used to provide geometric flexibility in the domain boundary shape without sacrificing accuracy. We use a mixed formulation utilizing a MACtype staggered grid with piecewise bilinear displacements centered at cell faces and piecewise constant pressures at cell centers. These discretization choices provide the necessary stability in the incompressible limit and the necessary accuracy in cut cells. Numerical experiments suggest second order accuracy in L1. We target high-resolution problems and present a class of geometric multigrid methods for solving the discrete equations for displacements and pressures that achieves nearly optimal convergence rates independent of grid resolution.

Paper: [PDF]

A Second-Order Virtual Node Method for Elliptic Problems with Interfaces and Irregular Domains in Three Dimensions
J. Hellrung, L. Wang, E. Sifakis and J. Teran
Journal of Computational Physics, 231(4), pp. 2015-2048, 2012

Abstract: We present a numerical method for the variable coefficient Poisson equation in three dimensional irregular domains and with interfacial discontinuities. The discretization embeds the domain and interface into a uniform Cartesian grid augmented with virtual degrees of freedom to provide accurate treatment of jump and boundary conditions. The matrix associated with the discretization is symmetric positive definite and equal to the standard 7-point finite difference stencil away from embedded interfaces and boundaries. Numerical evidence suggests second order accuracy in the L1-norm. Our approach improves the treatment of Dirichlet and jump constraints in the recent work of Bedrossian et al. and provides novel aspects necessary for problems in three dimensions. Specifically, we construct new constraint-based Lagrange multiplier spaces that significantly improve the conditioning of the associated linear system of equations; we provide a method for sub-cell polyhedral approximation to the zero isocontour surface of a level set needed for three dimensional embedding; and we show that the new Lagrange multiplier spaces naturally lead to a class of easy-to-implement multigrid methods that achieve near-optimal efficiency, as shown by numerical examples. For the specific case of a continuous Poisson coefficient in interface problems, we provide an expansive treatment of the construction of a particular solution that satisfies the value jump and flux jump constraints. As in Bedrossian et al 2010, this is used in a discontinuity removal technique that yields the standard 7-point Poisson stencil across the interface and only requires a modification to the right-hand side of the linear system.

Paper: [PDF]

Efficient elasticity for character skinning with contact and collisions
A. McAdams, Y. Zhu, A. Selle, M. Empey, R. Tamstorf, J. Teran and E. Sifakis
ACM Transactions on Graphics (SIGGRAPH 2011), 30(4), pp.37:1-37:12, 2011

Abstract: We present a new algorithm for near-interactive simulation of skeleton driven, high resolution elasticity models. Our methodology is used for soft tissue deformation in character animation. The algorithm is based on a novel discretization of corotational elasticity over a hexahedral lattice. Within this framework we enforce positive definiteness of the stiffness matrix to allow efficient quasistatics and dynamics. In addition, we present a multigrid method that converges with very high efficiency. Our design targets performance through parallelism using a fully vectorized and branch-free SVD algorithm as well as a stable one-point quadrature scheme. Since body collisions, self collisions and soft-constraints are necessary for real-world examples, we present a simple framework for enforcing them. The whole approach is demonstrated in an end-to-end production-level character skinning system. [Image (C) Disney Enterprises Inc.]

Paper : [PDF]
Supplemental Document: [PDF]

Related technical report:
A. McAdams, A. Selle, R. Tamstorf, J. Teran and E. Sifakis,
“Computing the Singular Value Decomposition of 3x3 matrices with minimal branching and elementary floating point operations”
University of Wisconsin - Madison, Computer Science technical report TR1690, May 2011 [PDF] [Source Code]

Videos:

An XFEM method for modelling geometrically elaborate crack propagation in brittle materials
C. L. Richardson, J. Hegeman, E. Sifakis, J. Hellrung and J. Teran
International Journal for Numerical Methods in Engineering, 88(10), pp. 1042-1065, 2011

Abstract: We present a method for simulating quasistatic crack propagation in 2-D which combines the extended finite element method (XFEM) with a general algorithm for cutting triangulated domains, and introduce a simple yet general and flexible quadrature rule based on the same geometric algorithm. The combination of these methods gives several advantages. First, the cutting algorithm provides a flexible and systematic way of determining material connectivity, which is required by the XFEM enrichment functions. Also, our integration scheme is straightfoward to implement and accurate, without requiring a triangulation that incorporates the new crack edges or the addition of new degrees of freedom to the system. The use of this cutting algorithm and integration rule allows for geometrically complicated domains and complex crack patterns.

Paper: [PDF]

A parallel multigrid Poisson solver for fluids simulation on large grids
A. McAdams, E. Sifakis and J. Teran
ACM SIGGRAPH/Eurographics Symposium on Computer Animation (SCA), edited by M. Otaduy and Z. Popovic, 2010

Abstract: We present a highly efficient numerical solver for the Poisson equation on irregular voxelized domains supporting an arbitrary mix of Neumann and Dirichlet boundary conditions. Our approach employs a multigrid cycle as a preconditioner for the conjugate gradient method, which enables the use of a lightweight, purely geometric multigrid scheme while drastically improving convergence and robustness on irregular domains. Our method is designed for parallel execution on shared-memory platforms and poses modest requirements in terms of bandwidth and memory footprint. Our solver will accommodate as many as 768×768×1152 voxels with a memory footprint less than 16GB, while a full smoke simulation at this resolution fits in 32GB of RAM. Our preconditioned conjugate gradient solver typically reduces the residual by one order of magnitude every 2 iterations, while each PCG iteration requires approximately 6.1sec on a 16-core SMP at 768^3 resolution. We demonstrate the efficacy of our method on animations of smoke flow past solid objects and free surface water animations using Poisson pressure projection at unprecedented resolutions.

Paper: [PDF] [Source Code]

Videos:

A Second Order Virtual Node Method for Elliptic Problems with Interfaces and Irregular Domains
J. Bedrossian, J. H. von Brecht, S. Zhu, E. Sifakis and J. Teran
Journal of Computational Physics, 229, pp. 6405-6426, 2010

Abstract: We present a second order accurate, geometrically flexible and easy to implement method for solving the variable coefficient Poisson equation with interfacial discontinuities or on irregular domains, handling both cases with the same approach. We discretize the equations using an embedded approach on a uniform Cartesian grid employing virtual nodes at interfaces and boundaries. A variational method is used to define numerical stencils near these special virtual nodes and a Lagrange multiplier approach is used to enforce jump conditions and Dirichlet boundary conditions. Our combination of these two aspects yields a symmetric positive definite discretization. In the general case, we obtain the standard 5-point stencil away from the interface. For the specific case of interface problems with continuous coefficients, we present a discontinuity removal technique that admits use of the standard 5-point finite difference stencil everywhere in the domain. Numerical experiments indicate second order accuracy in L-infinity.

Paper: [PDF]

An efficient multigrid method for the simulation of high-resolution elastic solids
Y. Zhu, E. Sifakis, J. Teran and A. Brandt
ACM Transactions on Graphics 29(2), pp.16:1-16:18, 2010 (presented at SIGGRAPH 2010)

Abstract: We present a multigrid framework for the simulation of high resolution elastic deformable models, designed to facilitate scalability on shared memory multiprocessors. We incorporate several state-of-the-art techniques from multigrid theory, while adapting them to the specific requirements of graphics and animation applications, such as the ability to handle elaborate geometry and complex boundary conditions. Our method supports simulation of linear elasticity and co-rotational linear elasticity. The efficiency of our solver is practically independent of material parameters, even for nearincompressible materials. We achieve simulation rates as high as 6 frames per second for test models with 256K vertices on an 8-core SMP, and 1.6 frames per second for a 2M vertex object on a 16-core SMP.

Paper: [PDF]

Videos:

Comprehensive Biomechanical Modeling and Simulation of the Upper Body
S.-H. Lee, E. Sifakis and D. Terzopoulos
ACM Transactions on Graphics 28(4), pp.99:1-99:17 2009 (presented at SIGGRAPH 2010)

Abstract: We introduce a comprehensive biomechanical model of the human upper body. Our model confronts the combined challenge of modeling and controlling more or less all of the relevant articular bones and muscles, as well as simulating the physics-based deformations of the soft tissues. Its dynamic skeleton comprises 68 bones with 147 jointed degrees of freedom, including those of each vertebra and most of the ribs. To be properly actuated and controlled, the skeletal submodel requires comparable attention to detail with respect to muscle modeling. We incorporate 814 muscles, each of which is modeled as a piecewise uniaxial Hill-type force actuator. To simulate biomechanically-realistic flesh deformations, we also develop a coupled finite element model with the appropriate constitutive behavior, in which are embedded the detailed 3D anatomical geometries of the hard and soft tissues. Finally, we develop an associated physics-based animation controller that computes the muscle activation signals necessary to drive the elaborate musculoskeletal system in accordance with a sequence of target poses specified by an animator

Paper: [PDF]

Videos:

Detail preserving continuum simulation of straight hair
A. McAdams, A. Selle, K. Ward, E. Sifakis and J. Teran
ACM Transactions on Graphics (SIGGRAPH Proceedings), 28(3), 2009

Abstract: Hair simulation remains one of the most challenging aspects of creating virtual characters. Most research focuses on handling the massive geometric complexity of hundreds of thousands of interacting hairs. This is accomplished either by using brute force simulation or by reducing degrees of freedom with guide hairs. This paper presents a hybrid Eulerian/Lagrangian approach to handling both self and body collisions with hair efficiently while still maintaining detail. Bulk interactions and hair volume preservation is handled efficiently and effectively with a FLIP based fluid solver while intricate hair-hair interaction is handled with Lagrangian selfcollisions. Thus the method has the efficiency of continuum/guide based hair models with the high detail of Lagrangian self-collision approaches.

Paper: [PDF]

Geometric fracture modeling in BOLT
J. Hellrung, A. Selle, A. Shek, E. Sifakis and J. Teran
ACM SIGGRAPH Talks (Sketch), 2009

Abstract: Modeling the geometry of solid materials cracking and shattering into elaborately shaped pieces is a painstaking task, which is often impractical to tune by hand when a large number of fragments are produced. In Walt Disney’s animated feature film Bolt, cracking and shattering objects were prominent visual elements in a number of action sequences. We designed a system to facilitate the modeling of cracked and shattered objects, enabling the automatic generation of a large number of fragments while retaining the flexibility to artistically control the density and complexity of the crack formation, or even manually controlling the shape of the resulting pieces where necessary. Our method resolves every fragment exactly into a separate triangulated surface mesh, producing pieces that line up perfectly even upon close inspection, and allows straightforward transfer of texture and look properties from the un-fractured model.

Paper: [PDF]

Local Flaps: A Real-Time Finite Element Based Solution to the Plastic Surgery Defect Puzzle
E. Sifakis, J. Hellrung, J. Teran, A. Oliker and C. Cutting
Medicine Meets Virtual Reality 17, 2009

Abstract: One of the most fundamental challenges in plastic surgery is the alteration of the geometry and topology of the skin. The specific decisions made by the surgeon concerning the size and shape of the tissue to be removed and the subsequent closure of the resulting wound may have a dramatic affect on the quality of life for the patient after the procedure is completed. The plastic surgeon must look at the defect created as an organic puzzle, designing the optimal pattern to close the hole aesthetically and efficiently. In the past, such skills were the distillation of years of hands-on practice on live patients, while relevant reference material was limited to two-dimensional illustrations. Practicing this procedure on a personal computer has been largely impractical to date, but recent technological advances may come to challenge this limitation. We present a comprehensive real-time virtual surgical environment, built on finite element modeling and simulation of tissue cutting and manipulation. Our system demonstrates the fundamental building blocks of plastic surgery procedures on a localized tissue flap, and provides a proof of concept for larger simulation systems usable in the authoring of complex procedures on elaborate subject geometry.

Paper: [PDF]

Videos:

Globally Coupled Impulse-Based Collision Handling for Cloth Simulation
E. Sifakis, S. Marino and J. Teran
ACM SIGGRAPH/Eurographics Symposium on Computer Animation (SCA), edited by M. Gross and D. James, 2008

Abstract: We present a novel algorithm for collision processing on triangulated meshes. Our method robustly maintains a collision free state on complex geometries while resorting to collision resolution at time intervals often comparable to the frame rate. Our approach is motivated by the behavior of a thin layer of fluid inserted in the empty space between nearly-colliding parts of the simulated surface, acting as a cushioning mechanism. Point-triangle or edge-edge pairs on a collision course are naturally resolved by the incompressible response of this fluid buffer. This response is formulated into a globally coupled nonlinear system which we solve using Newton iteration and symmetric, positive definite solvers. The globally coupled treatment of collisions allows us to resolve up to two orders of magnitude more collisions than traditional greedy algorithms (e.g. Gauss-Seidel collision response) and take substantially larger time steps without compromising the visual quality of the simulation.

Paper: [PDF]

Hybrid Simulation of Deformable Solids
E. Sifakis, T. Shinar, G. Irving and R. Fedkiw
ACM SIGGRAPH/Eurographics Symposium on Computer Animation (SCA), edited by D. Metaxas and J. Popovic, 2007

Abstract: Although mesh-based methods are efficient for simulating simple hyperelasticity, maintaining and adapting a mesh-based representation is less appealing in more complex scenarios, e.g. collision, plasticity and fracture. Thus, meshless or point-based methods have enjoyed recent popularity due to their added flexibility in dealing with these situations. Our approach begins with an initial mesh that is either conforming (as generated by one’s favorite meshing algorithm) or non-conforming (e.g. a BCC background lattice). We then propose a framework for embedding arbitrary sample points into this initial mesh allowing for the straightforward handling of collisions, plasticity and fracture without the need for complex remeshing. A straightforward consequence of this new framework is the ability to naturally handle T-junctions alleviating the requirement for a manifold initial mesh. The arbitrarily added embedded points are endowed with full simulation capability allowing them to collide, interact with each other, and interact with the parent geometry in the fashion of a particle-centric simulation system. We demonstrate how this formulation facilitates tasks such as arbitrary refinement or resampling for collision processing, the handling of multiple and possibly conflicting constraints (e.g. when cloth is nonphysically pinched between two objects), the straightforward treatment of fracture, and sub-element resolution of elasticity and plasticity.

Paper: [PDF]

Videos:

Arbitrary Cutting of Deformable Tetrahedralized Objects
E. Sifakis, K. Der, and R. Fedkiw
ACM SIGGRAPH/Eurographics Symposium on Computer Animation (SCA), edited by D. Metaxas and J. Popovic, 2007

Abstract: We propose a flexible geometric algorithm for placing arbitrary cracks and incisions on tetrahedralized deformable objects. Although techniques based on remeshing can also accommodate arbitrary fracture patterns, this flexibility comes at the risk of creating sliver elements leading to models that are inappropriate for subsequent simulation. Furthermore, interactive applications such as virtual surgery simulation require both a relatively low resolution mesh for efficient simulation of elastic deformation and highly detailed surface geometry to facilitate accurate manipulation and cut placement. Thus, we embed a high resolution material boundary mesh into a coarser tetrahedral mesh using our cutting algorithm as a meshing tool, obtaining meshes that can be efficiently simulated while preserving surface detail. Our algorithm is similar to the virtual node algorithm in that we avoid sliver elements and their associated stringent timestep restrictions, but it is significantly more general allowing for the arbitrary cutting of existing cuts, sub-tetrahedron resolution (e.g. we cut a single tetrahedron into over a thousand pieces), progressive introduction of cuts while the object is deforming, and moreover the ability to accurately cut the high resolution embedded mesh.

Paper: [PDF]

Videos:

Physical Simulation for Animation and Visual Effects: Parallelization and Characterization for Chip Multiprocessors
C. Hughes, R. Grzeszczuk, E. Sifakis, D. Kim, S. Kumar, A. Selle, J. Chhugani, M. Holliman, Y.-K. Chen
IEEE/ACM International Symposium on Computer Architecture (ISCA), 2007

Abstract: We explore the emerging application area of physics-based simulation for computer animation and visual special effects. In particular, we examine its parallelization potential and characterize its behavior on a chip multiprocessor (CMP). Applications in this domain model and simulate natural phenomena, and often direct visual components of motion pictures. We study a set of three workloads that exemplify the span and complexity of physical simulation applications used in a production environment: fluid dynamics, facial animation, and cloth simulation. They are computationally demanding, requiring from a few seconds to several minutes to simulate a single frame; therefore, they can benefit greatly from the acceleration possible with large scale CMPs. Starting with serial versions of these applications, we parallelize code accounting for at least 96% of the serial execution time, targeting a large number of threads. We then study the most expensive modules using a simulated 64-core CMP. For the code in key modules, we achieve parallel scaling of 45x, 50x, and 30x for fluid, face, and cloth simulations, respectively. The modules have a spectrum of task granularity and locking behavior, and all but one are dominated by loop-level parallelism. Many modules operate on streams of data. In some cases, modules iterate over their data, leading to significant temporal locality. This streaming behavior leads to very high on-die and main memory bandwidth requirements. Finally, most modules have little inter-thread communication since they are data-parallel, but a few require heavy communication between data-parallel operations.

Paper: [PDF]

Algorithmic Aspects of the Simulation and Control of Computer Generated Human Anatomy Models
E. Sifakis
Ph.D. Thesis, Stanford University, 2007

Abstract: Computer aided simulation of the appearance and function of the human body has found compelling applications in entertainment, biomechanics and medicine. Furthermore, recreating realistic humanlike behavior with a synthetic face or body model constitutes one of the most challenging benchmarks for physics-based simulation algorithms, due to the complexity and resolution of the utilized models. As a result, the quest for visual realism and biomechanical accuracy in virtual human simulation has often inspired novel algorithms with broader impact in the eld of physics-based simulation. Using realistic character animation as the underlying motivation, this thesis describes a host of new techniques that helped bring physics-based face and body models to life. These include a robust quasistatic nite element solver able to simulate meshes with over a million elements in the presence of inverted or degenerate elements, an optimization algorithm for the automatic extraction of facial muscle activations from motion captured performances, a hybrid solids simulation framework that allows the utilization of distinct representations for elastic simulation, collision handling and constraint resolution, and a exible geometric algorithm for placing cracks and incisions on deformable structures during simulation. Geometrical and constitutive modeling of active musculature is addressed for musculoskeletal and facial simulation tasks. Finally, the usability of these algorithms and models is illustrated both in human anatomy simulation scenarios as well as in more general physics-based simulation tasks for computer graphics applications.

Simulating Speech with a Physics-Based Facial Muscle Model
E. Sifakis, A. Selle, A. Robinson-Mosher and R. Fedkiw
ACM SIGGRAPH/Eurographics Symposium on Computer Animation (SCA), edited by M.-P. Cani and J. O’Brien, 2006

Abstract: We present a physically based system for creating animations of novel words and phrases from text and audio input based on the analysis of motion captured speech examples. Leading image based techniques exhibit photo-real quality, yet lack versatility especially with regard to interactions with the environment. Data driven approaches that use motion capture to deform a three dimensional surface often lack any anatomical or physically based structure, limiting their accuracy and realism. In contrast, muscle driven physics-based facial animation systems can trivially integrate external interacting objects and have the potential to produce very realistic animations as long as the underlying model and simulation framework are faithful to the anatomy of the face and the physics of facial tissue deformation. We start with a high resolution, anatomically accurate flesh and muscle model built for a specific subject. Then we translate a motion captured training set of speech examples into muscle activation signals, and subsequently segment those into intervals corresponding to individual phonemes. Finally, these samples are used to synthesize novel words and phrases. The versatility of our approach is illustrated by combining this novel speech content with various facial expressions, as well as interactions with external objects.

Paper: [PDF]

Videos:

Automatic Determination of Facial Muscle Activations from Sparse Motion Capture Marker Data
E. Sifakis, I. Neverov and R. Fedkiw
ACM Transactions on Graphics (SIGGRAPH Proceedings), TOG 24, pp. 417-425, 2005

Abstract: We built an anatomically accurate model of facial musculature, passive tissue and underlying skeletal structure using volumetric data acquired from a living male subject. The tissues are endowed with a highly nonlinear constitutive model including controllable anisotropic muscle activations based on fiber directions. Detailed models of this sort can be difficult to animate requiring complex coordinated stimulation of the underlying musculature. We propose a solution to this problem automatically determining muscle activations that track a sparse set of surface landmarks, e.g. acquired from motion capture marker data. Since the resulting animation is obtained via a three dimensional nonlinear finite element method, we obtain visually plausible and anatomically correct deformations with spatial and temporal coherence that provides robustness against outliers in the motion capture data. Moreover, the obtained muscle activations can be used in a robust simulation framework including contact and collision of the face with external objects.

Paper: [PDF]

Videos:

Robust Quasistatic Finite Elements and Flesh Simulation
J. Teran, E. Sifakis, G. Irving and R. Fedkiw
ACM/Eurographics Symposium on Computer Animation (SCA),  edited by K. Anjyo and P. Faloutsos, pp. 181-190, 2005

Abstract: Quasistatic and implicit time integration schemes are typically employed to alleviate the stringent time step restrictions imposed by their explicit counterparts. However, both quasistatic and implicit methods are subject to hidden time step restrictions associated with both the prevention of element inversion and the effects of discontinuous contact forces. Furthermore, although fast iterative solvers typically require a symmetric positive definite global stiffness matrix, a number of factors can lead to indefiniteness such as large jumps in boundary conditions, heavy compression, etc. We present a novel quasistatic algorithm that alleviates geometric and material indefiniteness allowing one to use fast conjugate gradient solvers during Newton-Raphson iteration. Additionally, we robustly compute smooth elastic forces in the presence of highly deformed, inverted elements alleviating artificial time step restrictions typically required to prevent such states. Finally, we propose a novel strategy for treating both collision and self-collision in this context.

Paper: [PDF]

Videos:

Creating and simulating skeletal muscle from the Visible Human Data Set
J. Teran, E. Sifakis, S. Blemker, V. Ng Thow Hing, C. Lau and R. Fedkiw
IEEE Transactions on Visualization and Computer Graphics, 11, pp. 317-328, 2005

Abstract: Simulation of the musculoskeletal system has important applications in biomechanics, biomedical engineering, surgery simulation and computer graphics. The accuracy of the muscle, bone and tendon geometry as well as the accuracy of muscle and tendon dynamic deformation are of paramount importance in all these applications. We present a framework for extracting and simulating high resolution musculoskeletal geometry from the segmented visible human data set. We simulate 30 contact/collision coupled muscles in the upper limb and describe a computationally tractable implementation using an embedded mesh framework. Muscle geometry is embedded in a non-manifold, connectivity preserving simulation mesh molded out of a lower resolution BCC lattice containing identical, well-shaped elements leading to a relaxed time step restriction for stability and thus reduced computational cost. The muscles are endowed with a transversely isotropic, quasi-incompressible constitutive model that incorporates muscle fiber fields as well as passive and active components. The simulation takes advantage of a new robust finite element technique that handles both degenerate and inverted tetrahedra.

Paper: [PDF]

Videos:

Facial Muscle Activations from Motion Capture
E. Sifakis and R. Fedkiw
in video proceedings of the Computer Vision and Pattern Recognition Conference (CVPR), 2005

Abstract: Biomechanically accurate finite element models of facial musculature offer a superior accuracy in reproducing facial expressions, the ability to adapt the simulation model to a particular subject as well as a compact and biophysically meaningful parameterization of expressions in terms of the muscle activations and bone motion that give rise to them. We employ such a finite element simulation model to determine the muscle activations and kinematic configuration of the rigid bones associated with an expression from a sparse sampling of the deformation of the face surface over time, acquired using a motion capture system. We use a hyperelastic, transversely isotropic constitutive model to simulate passive flesh and 32 dominant muscles of the face. Our simulation model, consisting of 840K tetrahedral elements, was created through non-rigid registration of a muscle geometry template derived from the Visible Human dataset to MRI volumetric data acquired from the motion capture subject.

Paper: [PDF]

Fast 3D Muscle Simulations Using a New Quasistatic Invertible Finite-Element Algorithm
S. Blemker, J. Teran, E. Sifakis, R. Fedkiw and S. Delp
International Symposium on Computer Simulation in Biomechanics, 2005

Abstract: A solid finite-element mesh representing the gluteus maximus muscle and triangulated surface meshes representing the pelvis and femur bones were created from magnetic resonance images. The muscle’s underlying fiber geometry was modeled by fitting a pennate fiber geometry template to the 3D model. A transversely-isotropic, incompressible, hyperelastic constitutive model was used to describe the stress-strain relationship in the muscle tissue. Flexion motion about the medial-lateral axis of the hip joint was prescribed as the boundary conditions, and penalty-based formulations were used to resolve muscle-bone contact. We ran simulations using a new quasi-static invertible algorithm as well as in NIKE3D, a nonlinear implicit finite-element program.

Paper: [PDF]

Fold Removal in CT Colonography (CTC): A Physics-based Approach
P. Sundaram, E. Sifakis , D. S. Paik, C. F. Beaulieu, S. Napel
Radiological Society of North America 91st Scientific Sessions, November, 2005. Scientific Assembly and Annual Meeting Program 2005:439

Selective Fold Removal in CT colonography using physically-based simulation
P. Sundaram, D.S. Paik, E.D. Sifakis, C.F. Beaulieu and S. Napel
Fifth International Symposium on Virtual Colonoscopy, Boston, MA October 28-29, 2004

Physically based approach to removal of folds in CT Colonography: Proof of concept
P. Sundaram, E. Sifakis, D.S. Paik, C.F. Beaulieu, S. Napel
Radiological Society of North America 90th Scientific Sessions, November 2004

Abstract: Computed Tomographic Colonography (CTC) produces 2-d and 3-d images of the colon using computed tomography (CT). The main goal of CTC is to detect small lumps on the colon surface called polyps, which are known to be precursors to colon cancer. Radiologists are therefore interested in exploring the inner surface of the colon to detect polyps. Polyps may be detected by visual inspection of colon CT images and also by using computer-aided detection. The colon surface is abundant with folds that occlude polyps during visual inspection and also contribute to false positives in computer-aided polyp detection. Removal of folds should therefore improve visualization and could also improve polyp detection sensitivity. In this paper, we present a physics-based method to unfold the colon surface. The output of our algorithm is a surface in 3-d, with the folds flattened out, leaving only polyps behind. Preliminary tests of our method in mathematical phantoms and actual patient data show reductions in fold height and curvature ranging from 54.4% to 70.3%, and 36.3% to 86.1% respectively. Polyp size and curvature were reduced by only 0 to 16%, and 0 to 20%, respectively. Our method, thus, demonstrates potential for improving both visual and computer-aided detection of colonic polyps from CTC examinations.

Paper: [PDF]

Color and texture segmentation using wavelet frame analysis, deterministic relaxation and fast marching algorithms
S. Liapis, E. Sifakis and G. Tziritas
Journal of Visual Communication and Image Representation, 15:1, pp. 1-26, March 2004

Abstract: Luminance, colour, and/or texture features may be used, either alone or in combination, for segmentation. In this paper luminance and colour classes are described using the corresponding empirical probability distributions. For texture analysis and characterisation a multichannel scale/orientation decomposition is performed using wavelet frame analysis. Knowing only the number of the different classes of the image, regions of homogeneous patterns are identified. On these regions the features characterising and describing the different classes are estimated. Two labelling algorithms are proposed. The first, a deterministic relaxation algorithm using a quadratic distance measure, yields the labelling of pixels to the different colour– texture classes. The second is a new Multi-label Fast Marching algorithm utilising a level set boundary determination.

Paper: [PDF]

Robust object boundary determination using a locally adaptive level set algorithm
E. Sifakis and G. Tziritas
Intl. Conference on Image Processing, 2003

Abstract: This paper introduces a level set methodology for the precise boundary localization of image objects within an indicated region, designed to be particularly robust against weak or spurious edges, triple points or inhomogeneity of object features in the proximity of the actual interface. The proposed technique requires a reliable classification for a subset of the object interiors, which is propagated towards the unclassified space using a competitive, statistically motivated fast marching region growing algorithm. Color and texture features are used on a locally adaptive, dynamically updated fashion to allow for the robust discrimination of inhomogeneous objects and an efficient implementation. Applications are illustrated in the context of moving object localization and semiautomatic object extraction.

Paper: [PDF]

Fast Marching techniques for Visual Grouping
E. Sifakis and G. Tziritas
in Geometric Level Set Methods in Imaging, Vision and Graphics, by S. Osher and N. Paragios (eds), Springer Verlag, July 2003

Abstract: A new region growing method is proposed for segmenting images. The region boundaries are formulated as level sets and the pixel labeling process is implemented using a new multi-label fast marching al- gorithm. The region contours are propagated with a velocity proportional to the a posteriori probability of the respective label. Statistical tests are performed to generate the initially labeled sets. Any image feature, given it is semantically relevant, can be considered for the segmentation process. Illustrations are given for combined luminance, chrominance and texture classication and segmentation in natural scenes. Moving object extrac- tion based on change detection is also considered, which is performed as a two-label classication.

Bayesian level sets for image segmentation
E. Sifakis, C. Garcia and G. Tziritas
Journal of Visual Communication and Image Representation, 13:1-2, pp. 44-64, March 2002

Abstract: This paper presents a new general framework for image segmentation. A level set formulation is used to model the boundaries of the image regions and a new Multi-Label Fast Marching is introduced for the evolution of the region contours towards the segmentation result. Statistical tests are performed to yield an initial estimate of high-condence subsets of the im- age regions. Furthermore, the velocities for the propagation of the region contours are dened in accordance with the a posteriori probability of the respective regions, leading to the Bayesian Level Set methodology de- scribed in this paper. Typical segmentation problems are considered and experimental results are given to illustrate the robustness of the method against noise and its performance in precise region boundary localization.

Paper: [PDF]

Video segmentation using fast marching and region growing algorithms
E. Sifakis, I. Grinias and G. Tziritas
EURASIP Journal on Applied Signal Processing, pp. 379-388, Apr 2002

Abstract: The algorithm presented in this paper is comprised of threemain stages: (1) classification of the image sequence and, in the case of a moving camera, parametric motion estimation, (2) change detection having as reference a fixed frame, an appropriately selected frame or a displaced frame, and (3) object localization using local colour features. The image sequence classification is based on statistical tests on the frame difference. The change detection module uses a two-label fast marching algorithm. Finally, the object localization uses a region growing algorithm based on the colour similarity. Video object segmentation results are shown using the COST 211 data set.

Paper: [PDF]

Moving object localization using a multi-label fast marching algorithm
E. Sifakis and G. Tziritas
Signal Processing: Image Communication, 16:10, pp. 963-976, 2001

Abstract: In this paper we address two problems crucial to motion analysis: the detection of moving objects and their localisation. Statistical and level set approaches are adopted in formulating these problems. For the change detection problem, the inter-frame dierence is modelled by a mixture of two zero-mean Laplacian distributions. At rst, statistical tests using criteria with negligible error probability are used for labelling as changed or unchanged as many sites as possible. All the connected components of the labelled sites are used thereafter as region seeds, which give the initial level sets for which velocity elds for label propagation are provided. We introduce a new multi-label fast marching algorithm for expanding competitive regions. The solution of the localisation problem is based on the map of changed pixels previously extracted. The boundary of the moving object is determined by a level set algorithm, which is initialised by two curves evolving in converging opposite directions. The sites of curve contact determine the position of the object boundary. Experimental results using real video sequences are presented, illustrating the eciency of the proposed approach.

Paper: [PDF]

Video segmentation using fast marching and region growing algorithms
E. Sifakis, I. Grinias and G. Tziritas
3rd European Workshop on Image Analysis for Multimedia Interactive Services, 2001 (invited)

Abstract: The algorithm presented in this paper was proposed for comparisons using the COST 211 data set. It is com- prised of three main stages: (1) classication of the im- age sequence, and parametric motion estimation in case of a moving camera, (2) change detection having as ref- erence a xed frame, an appropriately selected frame or a displaced frame, and (3) object localisation using lo- cal colour features. The image sequence classication is based on statistical tests on the frame dierence. The change detection module uses the two-label fast march- ing algorithm. Finally, the object localisation uses a region growing algorithm based on the colour similarity.

Paper: [PDF]
Video benchmarks: [URL]

Color and/or texture segmentation using deterministic relaxation and fast marching algorithms
S. Liapis, E. Sifakis and G. Tziritas
Intl. Conference on Pattern Recognition, 2000

Abstract: The segmentation of colored texture images is considered. Either luminance, color, and/or texture features could be used for segmentation. For luminance and color the classes are described using the corresponding empirical probability distributions. The Discrete Wavelet Frames analysis is used for obtaining features of texture patterns. At a first stage, pattern analysis is performed for extracting the features using the Bhattacharya distance. Two labeling algorithms are proposed. A deterministic relaxation algorithmusing a likelihoodbased distance yields the labeling of pixels to the different color-texture patterns. In addition, a new multi-label fast marching level set algorithmis utilized for the determination of the segment boundaries.

Paper: [PDF]

Fast marching to moving object location
E. Sifakis and G. Tziritas
Intl. Conference on Scale-Space Theories in Computer Vision, 1999

Abstract: In this paper we address two important problems in motion analysis: the detection of moving objects and their localization. Statis- tical and level set approaches are adopted in order to formulate these problems. For the change detection problem, the inter-frame dierence is modeled by a mixture of two zero-mean Laplacian distributions. At rst, statistical tests using criteria with negligible error probability are used for labeling as many as possible sites as changed or unchanged. All the connected components of the labeled sites are seed regions, which give the initial level sets, for which velocity elds for label propagation are provided. We introduce a new multi-label fast marching algorithm for expanding competitive regions. The solution of the localization problem is based on the map of changed pixels previously extracted. The bound- ary of the moving object is determined by a level set algorithm, which is initialized by two curves evolving in converging opposite directions. The sites of curve contact determine the position of the object boundary. For illustrating the eciency of the proposed approach, experimental results are presented using real video sequences.

Paper: [PDF]