I joined Washington University in 2005. I finished my undergraduate study in 2000 in Tsinghua
University (China) with a major in English and a minor in Computer Science, obtained my PhD degree in 2005 from Rice University in Computer Science under the supervision of Dr. Joe Warren, and pursued a short post-doctoral training in the summer of 2005 in the National Center for Macromolecular Imaging in Baylor College of Medicine directed by Dr. Wah Chiu.
My primary research area is computer graphics, with particular interests in geometric modeling, mesh processing, and shape understanding. The other focus of my research is on bio-medical applications, in particular geometric algorithms for analyzing bio-medical images and volumes. I have received a number of grant awards from NSF and NIH, including an NSF CAREER award in 2009.
- CSE 330: Rapid Prototyping and Creative Programming (Fall 2009)
- CSE 450: Video Game Programming I (Fall 2005, Fall 2007,
- CSE 451: Video Game Programming II (Spring 2006, Spring 2008)
- CSE 452: Computer Graphics (Fall 2006, Spring 2007, Spring
2008, Spring 2009, Spring 2010, Spring 2011, Spring 2013, Spring 2015)
- CSE 546: Computational Geometry (Spring 2014)
- CSE 554: Geometric Computing for Biomedicine (Fall 2010, Fall 2011, Fall 2012, Fall 2013, Fall 2014, Fall 2015)
- Seminar: Computer graphics and computer vision (since Spring 2006)
- Ming Zou (PhD)
- Michelle Vaughn (PhD, co-advised with Dr. Cindy Grimm)
- Yajie Yan (PhD)
- Hang Dou (PhD)
- Zhiyang Huang (PhD)
Lu Liu (PhD, graduated 2011, now at Google)
(PhD, graduated 2010, now at Google)
- Derek Burrows (MS, graduated 2013)
- Ruosi Li (MS, graduated 2011, now at Facebook)
- Trung D. Nguyen (MS, graduated 2011, now at Microsoft)
- Stephen Schuh (MS, graduated 2011, now at Google)
- Tim Simpson (MS., graduated 2008)
Journal Editorial Boards
- IEEE Transactions on Visualization and Computer Graphics (2015-present)
- Computer-Aided Design, Associate Editor (2012-present)
- Graphical Models, Associate Editor (2010-present)
- Computer Graphics Forum, Associate Editor (2011-2014)
- Siggraph Asia
- Symposium on Geometry Processing
- Pacific Graphics
- ACM Symposium on Solid and Physical Modeling .
- Geometric Modeling and Processing
- IEEE International Conference on Shape Modeling and Applications
- Sketch-Based Interfaces and Modeling
- International Symposium on Visual Computing
- Computer Graphics International Conference
University and Department Responsibilities
- Ambassador to Tsinghua University for McDonnell International Scholars Academy (2013-present)
- ACM chapter Faculty Advisor (2010-present)
- Technical Report Series Coordinator (2008-present)
- School of Engineering Undergraduate Board member (2006-present)
Here are some projects that I have worked on:
|Livewire3D: An interactive tool for curve drawing and segmentation on meshes. Based on Pacific Graphics 2014 paper. (Developed by Yixin Zhuang and Ming Zou)|
|CycleDisc: A graphical tool for finding possible cycles bounding surface patches in a 3D wireframe, optionally allowing user interaction and surfacing the found cycles. Based on Siggraph Asia 2013 paper. (Developed by Yixin Zhuang and Ming Zou)|
|TriMultPoly: A tool for optimally triangulating one or multiple 3D polygons. Based on SGP 2013 paper. (Developed by Ming Zou)|
|CC Skeleton: An efficient and robust tool for computing curve, surface and mixed curve-and-surface skeletons from a voxelized model. Based on Pacific Graphics 2011 paper. (Developed by Lu Liu)|
|Ctr2Suf: A tool for smooth
reconstruction from cross-section curves (or curve networks)
that lie on either parallel or non-parallel planes. Based on Eurographics 2008 paper. (Developed by Lu Liu)|
|PolyMender: A robust, efficient program for
removing cracks, holes, T-junctions and self-intersections from arbitrary polygonal models. Based on SIGGRAPH 2004 paper.|
Topology-Constrained Surface Reconstruction From Cross-sections
ACM Transactions on Graphics (Proc. ACM Siggraph 2015), 34(4): Article No. 128
Ming Zou, Michelle Holloway, Nathan Carr, Tao Ju.
In this work we detail the first algorithm that provides topological control during surface reconstruction from an input set of planar cross-sections. Our work has broad application in a number of fields including surface modeling and biomedical image analysis, where surfaces of known topology must be recovered. Given curves on arbitrarily oriented cross-sections, our method produces a manifold interpolating surface that exactly matches a user-specified genus. The key insight behind our approach is to formulate the topological search as a divide-and-conquer optimization process which scores local sets of topologies and combines them to satisfy the global topology constraint. We further extend our method to allow image data to guide the topological search, achieving even better results than relying on the curves alone. By simultaneously satisfying both geometric and topological constraints, we are able to produce accurate reconstructions with fewer input cross-sections, hence reducing the manual time needed to extract the desired shape.
Graph-based deformable matching of 3D line segments with application in protein fitting
The Visual Computer (Proc. Computer Graphics International 2015), 31: 967-977
Hang Dou, Matthew Baker, Tao Ju.
We present an algorithm for matching two sets of line segments in 3D that have undergone non-rigid deformations. This problem is motivated by a biology application that seeks a correspondence between the alpha-helices from two proteins, so that matching helices have similar lengths and these can be aligned by some low-distortion deformation. While matching between two feature sets have been extensively studied, particularly for point features, matching line segments has received little attention so far. As typical in point-matching methods, we formulate a graph matching problem and solve it using continuous relaxation. We make two technical contributions. First, we propose a graph construction for undirected line segments such that the optimal matching between two graphs represents an as-rigid-as-possible deformation between the two sets of segments. Second, we propose a novel heuristic for discretizing the continuous solution in graph matching. Our heuristic can be applied to matching problems (such as ours) that are not amenable to certain heuristics, and it produces better solutions than those applicable heuristics. Our method is compared with a state-of-art method motivated by the same biological application and demonstrates improved accuracy.
Fusing Heterogeneous Features for the Image-Guided Diagnosis of Intraductal Breast Lesions
International Symposium on Biomedical Imaging 2015, Oral presentation
Xiaofan Zhang, Hang Dou, Tao Ju, Shaoting Zhang.
In the analysis of histopathological images, both holistic (e.g., architecture features) and local appearance features demonstrate excellent performance, while their accuracy may vary dramatically among different inputs. This motivates us to investigate how to fuse results from these features to further enhance the accuracy. Particularly, we employ content-based image retrieval approaches to discover morphologically relevant images for image-guided diagnosis, using both holistic and local features. However, because of the dramatically different characteristics and representations of these heterogenous features, their resulting ranks may have no intersection among the top candidates, causing difficulties for traditional fusion methods. In this paper, we employ graph-based query-specific fusion approach where multiple retrieval ranks are integrated and reordered by conducting link analysis on a fused graph. The proposed method is capable of adaptively combining the strengths of local or holistic features for different queries, and does not need any supervision. We evaluate our method on a challenging clinical problem, i.e., histopathological image-guided diagnosis of intraductal breast lesions, and it achieves 91.67% classification accuracy on 120 breast tissue images from 40 patients.
A Robust Parity Test for Extracting Parallel Vectors in 3D
IEEE Transactions On Visualization and Computer Graphics (Proc. IEEE Vis 2014, Best Paper Honorable Mentioning), 20(12): 2526-2534
Tao Ju, Minxin Cheng, Xu Wang, Ye Duan.
Parallel vectors (PV), the loci where two vector fields are parallel, are commonly used to represent curvilinear features in
3D for data visualization. Methods for extracting PV usually operate on a 3D grid and start with detecting seed points on a cell face.
We propose, to the best of our knowledge, the first provably correct test that determines the parity of the number of PV points on a
cell face. The test only needs to sample along the face boundary and works for any choice of the two vector fields. A discretization
of the test is described, validated, and compared with existing tests that are also based on boundary sampling. The test can guide
PV-extraction algorithms to ensure closed curves wherever the input fields are continuous, which we exemplify in extracting ridges
and valleys of scalar functions.
Anisotropic geodesics for live-wire mesh segmentation
Computer Graphics Forum (Proc. Pacific Graphics 2014), 33(7): 111-120
(Paper, Video, Project)
Yixin Zhuang, Ming Zou, Nathan Carr, Tao Ju.
We present an interactive method for mesh segmentation that is inspired by the classical live-wire interaction for image segmentation. The core contribution of the work is the definition and computation of wires on surfaces that are likely to lie at segment boundaries. We define wires as geodesics in a new tensor-based anisotropic metric, which improves upon previous metrics in stability and feature-awareness. We further introduce a simple but effective mesh embedding approach that allows geodesic paths in an anisotropic path to be computed efficiently using existing algorithms designed for Euclidean geodesics. Our tool is particularly suited for delineating segmentation boundaries that are aligned with features or curvature directions, and we demonstrate its use in creating artist-guided segmentations.
Interactive Image-Guided Modeling of Extruded Shapes
Computer Graphics Forum (Proc. Pacific Graphics 2014, Best Paper), 33(7): 101-110
(Paper, Video, Project)
Yan-Pei Cao, Tao Ju, Zhao Fu, Shi-Min Hu.
A recent trend in interactive modeling of 3D shapes from a single image is designing minimal interfaces, and
accompanying algorithms, for modeling a specific class of objects. Expanding upon the range of shapes that
existing minimal interfaces can model, we present an interactive image-guided tool for modeling shapes made up
of extruded parts. An extruded part is represented by extruding a closed planar curve, called base, in the direction
orthogonal to the base. To model each extruded part, the user only needs to sketch the projected base shape in the
image. The main technical contribution is a novel optimization-based approach for recovering the 3D normal of
the base of an extruded object by exploring both geometric regularity of the sketched curve and image contents.
We developed a convenient interface for modeling multi-part shapes and a method for optimizing the relative
placement of the parts. Our tool is validated using synthetic data and tested on real-world images.
Computer-Assisted Shape Classification of Middle Cerebral Artery Aneurysms for Surgical Planning
International Symposium on Biomedical Imaging 2014, 1311-1315
Derek Burrows, Chad Washington, Ralph Dacey, Tao Ju.
We present a method for classifying the shape of middle cerebral artery (MCA) aneurysms using segmented surfaces from angiograms. The classification follows a set of visual criteria established by experienced surgeons to group aneurysms based on the clipping strategies used in surgery. Starting from a centerline representation of the input, our method automatically classifies the input into one of 4 types using a combination of graph analysis and supervised learning. When evaluated on a cohort of 84 subjects, our method achieves between 60% to 69% expected classification accuracy (p<0.001) with zero to a moderate amount of input from novice users.
An algorithm for suggesting delineation planes for interactive segmentation
IEEE International Symposium on Biomedical Imaging (ISBI), 361-364
Shahar Yifrah, Eyal Zadicario, Tao Ju, Daniel Cohen-Or.
In this paper we present a scheme to reduce the amount of user iterations required to segment an object by delineating on cross-section planes. Starting with an initial segmentation created from a small number of delineated curves, the algorithm progressively analyzes the uncertainty of segmentation with respect to the image features and suggests the "next plane" for delineation that would maximally resolve the uncertain regions. Compared with the few prior art on this problem, we adopt a simpler computational framework that is made up of an RBF-based curve interpolation method, a distance-based uncertainty metric, and a plane determination approach using density-based clustering. We demonstrate using both synthetic and real examples that our method uses less than 50% of the number planes than a random selection scheme to achieve 90% segmentation accuracy.
Inlier Detection in Thermal Sensitive Images
Eurographics Workshop on Visual Computing for Biology and Medicine (VCBM)
E. Zadicario, N. Carmi, T. Ju, D. Cohen-Or.
Image guidance of medical procedures may use thermal images to monitor
a treatment. Analysis of the thermal images by the physician may be time consuming and confusing because the thermal image includes multiple outliers.
We present a novel inlier detection method for thermal
images that results in reliable thermal information to support medical
decision making. Outliers in thermal images are particularly challenging to detect using conventional methods, because they are significantly more abundant than inliers and, like inliers, they may be temporally consistent. Our inlier detection method is physically-based: it is motivated by the fact that heat propagation in soft tissues can be modeled using the bio-heat equation. Pixels are classified as inliers only if the temperature pattern in a spatial and temporal neighborhood strongly correlates with the physical model. For improved robustness, the correlation process includes a 2D filter in the spatial domain and a 3D filter in both spatial and temporal domains. Experiments with real data have shown that our method produces results that agree with annotations provided by human experts even in outlier-laden images. Our results show inliers can be detected leaving true heat pixels for the physician to observe, while not overloading him with the need to analyze outliers. The technique has been integrated in a true clinical environment and is being used to aid physicians in analysis of thermal images
Middle cerebral artery bifurcation aneurysms: an anatomic classification scheme for planning optimal surgical strategies.
Operative Neurosurgery, 10(1): 145-155
(Pubmed link, video)
Chad Washington, Tao Ju, Gregory Zipfel, Ralph Dacey.
Changing landscapes in neurosurgical training and increasing use of endovascular therapy have led to decreasing exposure in open cerebrovascular neurosurgery. To ensure the effective transition of medical students into competent practitioners, new training paradigms must be developed. Using principles of pattern recognition, we created a classification scheme for middle cerebral artery (MCA) bifurcation aneurysms that allows their categorization into a small number of shape pattern groups, each associated with a clip solution. Implementing these principles within current neurosurgery training paradigms can provide a tool that allows more efficient transition from novice to cerebrovascular expert.
Reliability of clinically relevant 3D foot bone angles from quantitative computed tomography.
Journal of Foot and Ankle Research, 6(1): 38
David Gutekunst, Lu Liu, Tao Ju, Fred Prior, David Sinacore.
Surgical treatment and clinical management of foot pathology requires accurate, reliable assessment of foot deformities. Foot and ankle deformities are multi-planar and therefore difficult to quantify by standard radiographs. Three-dimensional (3D) imaging modalities have been used to define bone orientations using inertial axes based on bone shape, but these inertial axes can fail to mimic established bone angles used in orthopaedics and clinical biomechanics. To provide improved clinical relevance of 3D bone angles, we developed techniques to define bone axes using landmarks on quantitative computed tomography (QCT) bone surface meshes. We aimed to assess measurement precision of landmark-based, 3D bone-to-bone orientations of hind foot and lesser tarsal bones for expert raters and a template-based automated method.
A general and efficient method for finding cycles in 3D curve networks
ACM Transactions On Graphics (Proc. SIGGRAPH Asia 2013), 32(6): Article No. 180.
Yixin Zhuang, Ming Zou, Nathan Carr, Tao Ju.
Generating surfaces from 3D curve networks has been a longstanding problem in computer graphics. Recent attention to this area has resurfaced as a result of new sketch based modeling systems. In this work we present a new algorithm for finding cycles that bound surface patches. Unlike prior art in this area, the output of our technique is unrestricted, generating both manifold and non-manifold geometry with arbitrary genus. The novel insight behind our method is to formulate our problem as finding local mappings at the vertices and curves of our network, where each mapping describes how incident curves are grouped into cycles. This approach lends us the efficiency necessary to present our system in an interactive design modeler, whereby the user can adjust patch constraints and change the manifold properties of curves while the system automatically re-optimizes the solution.
Cubic Mean Value Coordinates
ACM Transactions On Graphics (Proc. SIGGRAPH 2013), 32(4): Article No. 126.
Xianying Li, Tao Ju, Shimin Hu.
We present a new method for interpolating both boundary values
and gradients over a 2D polygonal domain. Despite various previous
efforts, it remains challenging to define a closed-form interpolant
that produces natural-looking functions while allowing flexible
control of boundary constraints. Our method builds on an existing
transfinite interpolant over a continuous domain, which in turn
extends the classical mean value interpolant. We re-derive the interpolant
from the mean value property of biharmonic functions, and
prove that the interpolant indeed matches the gradient constraints
when the boundary is piece-wise linear. We then give closed-form
formula (as generalized barycentric coordinates) for boundary constraints
represented as polynomials up to degree 3 (for values) and
1 (for normal derivatives) over each polygon edge. We demonstrate
the flexibility and efficiency of our coordinates in two novel applications,
smooth image deformation using curved cage networks and
adaptive simplification of gradient meshes.
An algorithm for triangulating multiple 3D polygons
Computer Graphics Forum (Proc. SGP 2013), 32(5): 157-166.
Ming Zou, Tao Ju, Nathan Carr.
We present an algorithm for obtaining a triangulation of multiple, non-planar 3D polygons. The output minimizes additive weights, such as the total triangle areas or the total dihedral angles between adjacent triangles. Our algorithm generalizes a classical method for optimally triangulating a single polygon. The key novelty is a mechanism for avoiding non-manifold outputs for two and more input polygons without compromising optimality. For better performance on real-world data, we also propose an approximate solution by feeding the algorithm with a reduced set of triangles. In particular, we demonstrate experimentally that the triangles in the Delaunay tetrahedralization of the polygon vertices offer a reasonable trade off between performance and optimality.
Medial Residues of Piecewise Linear Manifolds
Proc. Canadian Conference on Computational Geometry (CCCG'13), accepted.
(Paper, Extended version)
Erin W. Chambers, Tao Ju, David Letscher
Skeleton structures of objects are used in a wide variety of applications such as shape analysis and path planning. One of the most widely used skeletons is the medial axis, which is a thin structure centered within and homotopy equivalent to the object. However, on piecewise linear surfaces, which are one of the most common outputs from surface reconstruction algorithms, natural generalizations of typical medial axis definitions may fail to have these desirable properties. In this paper, we propose a new extension of the medial axis, called the medial residue, and prove that it is a finite curve network homotopy equivalent to the original surface when the input is a piecewise linear surface with boundary. We also develop an efficient algorithm to compute the medial residue on a triangulated mesh, building on previously known work to compute geodesic distances.
Feature correspondences using Morse Smale complex
The Visual Computer, 29(1):53-67.
Wei Feng, Jin Huang, Tao Ju, Hujun Bao
Establishing corresponding features on two non-rigidly deformed 3D surfaces is a challenging and well-studied problem in computer graphics. Unlike previous approaches that constrain the matching between feature pairs using isometry-invariant distance metrics, we constrain the matching using a discrete connectivity graph derived from the Morse?Smale complex of the Auto Diffusion Function. We observed that the graph remains stable even for surfaces differing by topology or by significant deformation. This algorithm is simple to implement and efficient to run. When tested on a range of examples, our algorithm produces comparable results with state-of-art methods on surfaces with strong isometry but with greatly improved efficiency, and often gets better correspondences on surfaces with larger shape variances.
Does the gamma dose distribution comparison technique default to the distance to agreement test in clinical dose distributions?
Medical Physics, 40(7):071722.
Dan Low, Delphine Morele, Philip Chow, Hsiang-Tai Dou, Tao Ju.
The goal of this paper is to determine the validity of the assumption that the gamma dose distribution comparison tool defaults to the distance to agreement (DTA) test under conditions of clinically relevant steep dose gradients
and gamma test criteria. The assumption was tested by computing the angle between the dose axis and gamma vector for clinical treatment plans. We found that most published cases used ratio of the dose difference to DTA >= 1%/mm, and for these cases the assumption was
true. There were a few cases for which the ratio value was small enough to potentially invalidate this assumption. Care should be taken by investigators when selecting the gamma test criteria to assure that the gamma test will appropriately default to the DTA test in the steepest dose gradients being evaluated.
Automated, Foot-Bone Registration Using Subdivision-Embedded Atlases for Spatial Mapping of Bone Mineral Density
Journal of Digital Imaging, 26(3):554-562.
Lu Liu, Paul K. Commean, Charles Hildebolt, Dave Sinacore, Fred Prior, James P. Carson, Ioannis Kakadiaris, Tao Ju.
We present an atlas-based registration method for bones segmented from quantitative computed tomography (QCT) scans, with the goal of mapping their interior bone mineral densities (BMDs) volumetrically. We introduce a new type of deformable atlas, called subdivision-embedded atlas, which consists of a control grid represented as a tetrahedral subdivision mesh and a template bone surface embedded within the grid. Compared to a typical lattice-based deformation grid, the subdivision control grid possesses a relatively small degree of freedom tailored to the shape of the bone, which allows efficient fitting onto subjects. Compared with previous subdivision atlases, the novelty of our atlas lies in the addition of the embedded template surface, which further increases the accuracy of the fitting. Using this new atlas representation, we developed an efficient and fully automated pipeline for registering atlases of 12 tarsal and metatarsal bones to a segmented QCT scan of a human foot.
Region-based Line Field Design Using
IEEE Transactions on Visualization and Computer Graphics, 18(6):902-913.
(Paper, Supplementary material,
C.-Y. Yao, M.-T. Chi, T.-Y. Lee, T. Ju
Field design has wide applications in graphics and visualization. One of the main challenges in field design has been
how to provide users with both intuitive control over the directions in the field on one hand and robust management of its topology
on the other hand. In this paper, we present a design paradigm for line fields that addresses this challenge. Rather than asking
users to input all singularities as in most methods that offer topology control, we let the user provide a partitioning of the domain
and specify simple flow patterns within the partitions. Represented by a selected set of harmonic functions, the elementary
fields within the partitions are then combined to form continuous fields with rich appearances and well-determined topology.
Our method allows a user to conveniently design the flow patterns while having precise and robust control over the topological
structure. Based on the method, we developed an interactive tool for designing line fields from images, and demonstrated the
utility of the fields in image stylization.
Similarity-Based Appearance-Prior for Fitting a Subdivision Mesh in Gene Expression Images
Proceedings of the 15th International Conference on Medical Image Computing and Computer Assisted Intervention (MICCAI'12)
Y-H. Le, U. Kurkure, N. Paragios, T. Ju, J. P. Carson, I. A. Kakadiaris
Automated segmentation of multi-part anatomical objects in
images is a challenging task. In this paper, we propose a similarity-based
appearance-prior to fit a compartmental geometric atlas of the mouse
brain in gene expression images. A subdivision mesh which is used to
model the geometry is deformed using a Markov Random Field (MRF)
framework. The proposed appearance-prior is computed as a function
of the similarity between local patches at corresponding atlas locations
from two images. In addition, we introduce a similarity-saliency score
to select the mesh points that are relevant for the computation of the
proposed prior. Our method significantly improves the accuracy of the
atlas fitting, especially in the regions that are influenced by the selected
similarity-salient points, and outperforms the previous subdivision mesh
fitting methods for gene expression images.
Gorgon and pathwalking: Macromolecular modeling tools for subnanometer resolution density maps
M. L. baker, M. R. Baker, C. F. Hryc, T. Ju, W. Chiu.
The complex interplay of proteins and other molecules, often in the form of large transitory assemblies, are critical to cellular function. Today, X-ray crystallography and electron cryo-microscopy (cryo-EM) are routinely used to image these macromolecular complexes, though often at limited resolutions. Despite the rapidly growing number of macromolecular structures, few tools exist for modeling and annotating structures in the range of 3-10A resolution. To address this need, we have developed a number of utilities specifically targeting subnanometer resolution density maps. As part of the 2010 Cryo-EM Modeling Challenge, we demonstrated two of our latest de novo modeling tools, Pathwalking and Gorgon, as well as a tool for secondary structure identification (SSEHunter) and a new rigid-body/flexible fitting tool in Gorgon. In total, we submitted 30 structural models from ten different subnanometer resolution data sets in four of the six challenge categories. Each of our utilities produced accurate structural models and annotations across the various density maps. In the end, the utilities that we present here offer users a robust toolkit for analyzing and modeling protein structure in macromolecular assemblies at non-atomic resolutions.
Extended Grassfire Transform on Medial Axes of 2D Shapes
Computer Aided Design (Proceedings of SPM 2011), 43(11):1496-1505
Slides without video)
Lu Liu, Erin Chambers, David Letscher, Tao Ju
The medial axis is an important shape descriptor first introduced by Blum via a grassfire burning analogy. However, the medial
axes are sensitive to boundary perturbations, which calls for global shape measures to identify meaningful parts of a medial axis.
On the other hand, a more compact shape representation than the medial axis, such as a "center point", is needed in various
applications ranging from shape alignment to geography. In this paper, we present a uniform approach to define a global shape
measure (called extended distance function, or EDF) along the 2D medial axis as well as the center of a 2D shape (called extended
medial axis, or EMA). We reveal a number of properties of the EDF and EMA that resemble those of the boundary distance
function and the medial axis, and show that EDF and EMA can be generated using a fire propagation process similar to Blum's
grassfire analogy, which we call the extended grassfire transform. The EDF and EMA are demonstrated on many 2D examples, and
are related to and compared with existing formulations. Finally, we demonstrate the utility of EDF and EMA in pruning medial
axes, aligning shapes, and shape description.
Isotopic Frechet Distance
Proceedings of 23rd Canadian Conference on Computational Geometry, accepted
Erin Chambers, Tao Ju, David Letscher, Lu Liu
We are interested in defining a distance measure between two (homeomorphic) shapes, which has a
number of potential applications in computer graphics
and vision. We propose
a new distance measure which intuitively is the least
effort of morphing a source shape into a target shape,
such that each intermediate shape during the morph is
homeomorphic to the source. For a given morph, this
"effort" is measured as the maximum distance traveled
by any point on the source shape. Our measure is closely related to Frechet distance as well as the homotopic Frechet distance, yet can better characterize the dissimilarity between two curves. This paper discusses the formulation of the distance measure, compares with previous measures, and touches on the challenges in computing the measure.
View-independent Contour Culling of 3D Density Maps for Far-field Viewing of Iso-surfaces
Computer and Graphics (Proceedings of SMI'11), 35(3):561-568
P. Feng, T. Ju, J. Warren
In many applications, iso-surface is the primary method for visualizing the structure of 3D density maps. We consider
a common scenario where the user views the iso-surfaces from a distance and varies the level associated with the
iso-surface as well as the view direction to gain a sense of the general 3D structure of the density map. For many
types of density data, the iso-surfaces associated with a particular threshold may be nested and never visible during
this type of viewing. In this paper, we discuss a simple, conservative culling method that avoids the generation of
interior portions of iso-surfaces at the contouring stage. Unlike existing methods that perform culling based on the
current view direction, our culling is performed once for all views and requires no additional computation as the view
changes. By pre-computing a single visibility map, culling is done at any iso-value with little overhead in contouring.
We demonstrate the effectiveness of the algorithm on a range of bio-medical data and discuss a practical application
in online visualization.
Modeling protein structure at near atomic resolutions with Gorgon
Journal of Structural Biology, 174(2):360-373
(Paper, Journal cover,
M. Baker, S. Abeysinghe, S. Schuh, R. Coleman, A. Abrams,
M. Marsh, C. Hryc, T. Ruths, W. Chiu, T. Ju
Electron cryo-microscopy (cryo-EM) has played an increasingly important role in elucidating the structure
and function of macromolecular assemblies in near native solution conditions. Typically, however,
only non-atomic resolution reconstructions have been obtained for these large complexes, necessitating
computational tools for integrating and extracting structural details. With recent advances in cryo-EM,
maps at near-atomic resolutions have been achieved for several macromolecular assemblies from which
models have been manually constructed. In this work, we describe a new interactive modeling toolkit
called Gorgon targeted at intermediate to near-atomic resolution density maps (10-3.5A), particularly
from cryo-EM. Gorgon's de novo modeling procedure couples sequence-based secondary structure prediction
with feature detection and geometric modeling techniques to generate initial protein backbone models.
Beyond model building, Gorgon is an extensible interactive visualization platform with a variety of
computational tools for annotating a wide variety of 3D volumes. Examples from cryo-EM maps of Rotavirus
and Rice Dwarf Virus are used to demonstrate its applicability to modeling protein structure.
Landmark/Image-based Deformable Registration of Gene Expression Data
IEEE Computer Vision and Pattern Recognition (CVPR'11), 1089-1096
U. Kurkure, Y.-H. Le, N. Paragios, J. Carson, T. Ju, I. Kakadiaris
Analysis of gene expression patterns in brain images
obtained from high-throughput in situ hybridization requires
accurate and consistent annotations of anatomical
regions/subregions. Such annotations are obtained by mapping
an anatomical atlas onto the gene expression images
through intensity- and/or landmark-based registration
methods or deformable model-based segmentation methods.
Due to the complex appearance of the gene expression
images, these approaches require a pre-processing step
to determine landmark correspondences in order to incorporate
landmark-based geometric constraints. In this paper,
we propose a novel method for landmark-constrained,
intensity-based registration without determining landmark
correspondences a priori. The proposed method performs
dense image registration and identifies the landmark correspondences,
simultaneously, using a single higher-order
Markov Random Field model. In addition, a machine learning
technique is used to improve the discriminating properties
of local descriptors for landmark matching by projecting
them in a Hamming space of lower dimension. We qualitatively
show that our method achieves promising results
and also compares well, quantitatively, with the expert's annotations, outperforming previous methods.
A semi-automated approach for artifact removal in serial tissue cryosections
Journal of Microscopy, 241(2):200-206
L. Kindle, I. Kakadiaris, T. Ju, J. Carson
Thinly sliced serial tissue sections of an organ can be imaged using optical microscopy and then
reconstructed into three dimensional datasets with a resolution detailing individual cells. When
the tissue sections are first subjected to in situ hybridization or immunohistochemistry, these
datasets can be analyzed for changes in gene expression and gene products. Such spatial
information is important for understanding the functional effects of experimental or
environmental challenges to the organism. However, a critical step in processing these 3D
datasets is mitigating artifacts and defects that occur to the tissue during the sectioning process.
Here we describe a new method for detecting and addressing such artifacts including dust
particles, air bubbles, and tears.
Volumetric Quantitative Computed Tomography
Measurement Precision for Volumes and Densities of Tarsal
and Metatarsal Bones
Journal of Clinical Densitometry, 14(3):313-320
Paul Commean, Jared Kennedy, Karen Bahow, Charles Hildebolt,
Lu Liu, Kirk Smith, Mary Hastings, Tao Ju, Fred Prior,
Diabetic foot diseases, such as ulcerations, infections, and neuropathic (Charcot's) arthropathy, are major complications
of diabetes mellitus (DM) and peripheral neuropathy (PN) and may cause osteolysis (bone loss) in foot
bones. The purposes of our study were to make computed tomography (CT) measurements of foot-bone volumes and
densities and to determine measurement precision (percent coefficients of variation for root-mean-square standard
deviations) and least significant changes (LSCs) in these percentages that could be considered biologically real with
95% confidence. Our study shows that volumetric
quantitative CT provides precise measurements of volume and BMD for metatarsal and tarsal bones, where
diabetic foot diseases commonly occur.
A simple and robust thinning algorithm on cell complexes
Computer Graphics Forum (Proceedings of Pacific Graphics 2010), 29(7):2253-2260
(Paper, Video, Project)
L. Liu, E. Chambers, D. Letscher, T. Ju
Thinning is a commonly used approach for computing skeleton descriptors. Traditional thinning algorithms often
have a simple, iterative structure, yet producing skeletons that are overly sensitive to boundary perturbations.
We present a novel thinning algorithm, operating on objects represented as cell complexes, that preserves the
simplicity of typical thinning algorithms but generates skeletons that more robustly capture global shape features.
Our key insight is formulating a skeleton significance measure, called medial persistence, which identify skeleton
geometry at various dimensions (e.g., curves or surfaces) that represent object parts with different anisotropic
elongations (e.g., tubes or plates). The measure is generally defined in any dimensions, and can be easily computed
using a single thinning pass. Guided by medial persistence, our algorithm produces a family of topology and shape
preserving skeletons whose shape and composition can be flexible controlled by desired level of medial persistence.
Semi-isometric registration of line features for flexible fitting of protein structures
Computer Graphics Forum (Proceedings of Pacific Graphics 2010), 29(7):2243-2252
S. Abeysinghe, M. Baker, W. Chiu, T. Ju
In this paper, we study a registration problem that is motivated by a practical biology problem - fitting protein
structures to low-resolution density maps. We consider registration between two sets of lines features (e.g., helices
in the proteins) that have undergone not a single, but multiple isometric transformations (e.g., hinge-motions). The
problem is further complicated by the presence of symmetry in each set. We formulate the problem as a clique-search
problem in a product graph, and propose a heuristic solution that includes a fast clique-finding algorithm
unique to the structure of this graph. When tested on a suite of real protein structures, the algorithm achieved high
accuracy even for very large inputs containing hundreds of helices.
Instant Propagation of Sparse Edits on Images and Videos
Computer Graphics Forum (Proceedings of Pacific Graphics 2010), 29(7):2049-2054
Y. Li, T. Ju, S-M. Hu
The ability to quickly and intuitively edit digital contents has become increasingly important in our everyday life.
We propose a novel method for propagating a sparse set of user edits (e.g., changes in color, brightness, contrast,
etc.) expressed as casual strokes to nearby regions in an image or video with similar appearances. Existing
methods for edit propagation are typically based on optimization, whose computational cost can be prohibitive
for large inputs. We re-formulate propagation as a function interpolation problem in a high-dimensional space,
which we solve very efficiently using radial basis functions. While simple to implement, our method significantly
improves the speed and space cost of existing methods, and provides instant feedback of propagation results even
on large images and videos.
Polygonizing Extremal Surfaces with Manifold Guarantees
Proceedings of Symposium of Solid and Physical Modeling (SPM) 2010, 189-194
R-S. Li, L. Liu, L. Phan, S. Abeysinghe, C. Grimm, T. Ju
Extremal surfaces are a class of implicit surfaces that have
been found useful in a variety of geometry reconstruction
applications. Compared to iso-surfaces, extremal surfaces
are particularly challenging to construct in part due to the
presence of boundaries and the lack of a consistent orientation.
We present a novel, grid-based algorithm for constructing
polygonal approximations of extremal surfaces that may
be open or unorientable. The algorithm is simple to implement
and applicable to both uniform and adaptive grid
structures. More importantly, the resulting discrete surface
preserves the structural property of the extremal surface in
a grid-independent manner. The algorithm is applied to extract
ridge surfaces from intensity volumes and reconstruct
surfaces from point set with unoriented normals.
Piecewise Tri-linear Contouring for Multi-Material Volumes
Proceedings of Geometry Modeling and Processing (GMP) 2010, 43-56
P. Feng, T. Ju, J. Warren
The ability to model objects composed of multiple materials has become increasingly more demanded in
The visualization of a discrete multi-material volume often suffers from
voxelization of the boundary between materials. We propose a contouring method that can be efficiently implemented on the GPU to reduce
the artifacts and jaggedness along the material boundaries. Our method
extends naturally from the standard tri-linear contouring in a signed volume, and further provides sub-voxel accuracy for representing three or
Subdivision meshes for organizing spatial biomedical data
T. Ju, J. Carson, L. Liu, J. Warren, M. Bello, I. Kakadiaris
As biomedical images and volumes are being collected at an increasing speed, there is a growing demand
for efficient means to organize spatial information for comparative analysis. In many scenarios, such as
determining gene expression patterns by in situ hybridization, the images are collected from multiple
subjects over a common anatomical region, such as the brain. A fundamental challenge in comparing spatial
data from different images is how to account for the shape variations among subjects, which make
direct image-to-image comparisons meaningless. In this paper, we describe subdivision meshes as a geometric
means to efficiently organize 2D images and 3D volumes collected from different subjects for comparison.
The key advantages of a subdivision mesh for this purpose are its light-weight geometric
structure and its explicit modeling of anatomical boundaries, which enable efficient and accurate registration.
The multi-resolution structure of a subdivision mesh also allows development of fast comparison
algorithms among registered images and volumes.
Automated pipeline for atlas-based annotation of gene expression patterns:
Application to postnatal day 7 mouse brain
J. Carson, T. Ju, M. Bello, C. Thaller, J. Warren, I. A. Kakadiaris, W. Chiu, G. Eichele
Massive amounts of image data have been collected and continue to be generated for representing cellular
gene expression throughout the mouse brain. Critical to exploiting this key effort of the post-genomic
era is the ability to place these data into a common spatial reference that enables rapid interactive
queries, analysis, data sharing, and visualization. In this paper, we present a set of automated protocols
for generating and annotating gene expression patterns suitable for the establishment of a database. The
steps include imaging tissue slices, detecting cellular gene expression levels, spatial registration with an
atlas, and textual annotation. Using high-throughput in situ hybridization to generate serial sets of tissues
displaying gene expression, this process was applied toward the establishment of a database representing
over 200 genes in the postnatal day 7 mouse brain. These data using this protocol are now well-suited for
interactive comparisons, analysis, queries, and visualization.
Feature-Aligned Shape Texturing
ACM Transactions on Graphics (Proceedings of Siggraph Asia 2009), 28(5): article 108
K. Xu, D. Cohen-Or, T. Ju, L-G. Liu, H. Zhang, S-Z. Zhou, Y-S. Xiong
The essence of a 3D shape can often be well captured by its salient
feature curves. In this paper, we explore the use of salient curves
in synthesizing intuitive, shape-revealing textures on surfaces. Our
texture synthesis is guided by two principles: matching the direction
of the texture patterns to those of the salient curves, and aligning
the prominent feature lines in the texture to the salient curves
exactly. We have observed that textures synthesized by these principles
not only fit naturally to the surface geometry, but also visually
reveal, even reinforce, the shape's essential characteristics. We call
these feature-aligned shape texturing. Our technique is fully automatic,
and introduces two novel technical components in vector-field-
guided texture synthesis: an algorithm that orients the salient
curves on a surface for constrained vector field generation, and a
feature-to-feature texture optimization.
Efficient Affinity-based Edit Propagation using K-D Tree
ACM Transactions on Graphics (Proceedings of Siggraph Asia 2009), 28(5): article 118
K. Xu, Y. Li, T. Ju, S-M. Hu, T-Q. Liu
Image/video editing by strokes has become increasingly popular
due to the ease of interaction. Propagating the user inputs to the rest
of the image/video, however, is often time and memory consuming
especially for large data. We propose here an efficient scheme that
allows affinity-based edit propagation to be computed on data containing
tens of millions of pixels at interactive rate (in matter of seconds).
The key in our scheme is a novel means for approximately
solving the optimization problem involved in edit propagation, using
adaptive clustering in a high-dimensional, affinity space. Our
approximation significantly reduces the cost of existing affinity-based
propagation methods while maintaining visual fidelity, and
enables interactive stroke-based editing even on high resolution images
and long video sequences using commodity computers.
Compatible quadrangulation by
Computer Animation And Virtual Worlds (Proceedings of CASA'09), 23(2-3):101-109
C.-Y. Yao, H.-K. Chu, T. Ju and T.-Y. Lee.
Mesh quadrangulation has received increasing attention in the past decade. While previous
works have mostly focused on producing a high quality quad mesh of a single model, the
connectivity of the quadrangulation is typically difficult to control and varies among
models even with similar shapes. In this paper, we propose a novel interactive framework
for quadrangulating a set of models collectively with compatible connectivity. Furthermore,
we demonstrate its application to 3D mesh morphing. In our approach, the user
interactively sketches a skeleton within each model, and our method automatically
computes compatible base domains for all models from these skeletons, on which the
models are parameterized. With this novel parameterization, it is very easy to generate a
pleasing and smooth 3D morphing sequence among these compatible models. The method
yields quadrangulation with comparable quality to existing approaches, but greatly
simplifies compatible re-meshing among a group of topologically equivalent models, in
particular characters and animals models, with direct applications in shape blending and
VolumeViewer: An Interactive Tool for Fitting Surfaces to Volume Data
Sixth Eurographics Workshop on Sketch Based Interfaces and Modeling, 141-148
R. Sowell, L. Liu, T. Ju, C. Grimm, C. Abraham, G. Gokhroo, D. Low.
Recent advances in surface reconstruction algorithms allow
surfaces to be built from contours lying on non-parallel
planes. Such algorithms allow users to construct surfaces of
similar quality more efficiently by using a small set of
oblique contours, rather than many parallel contours.
However, current medical imaging systems do not provide tools
for sketching contours on oblique planes. In this paper, we
take the first steps towards bridging the gap between the new
surface reconstruction technologies and putting those methods
to use in practice. We develop a novel interface for modeling
surfaces from volume data by allowing the user to sketch
contours on arbitrarily oriented cross-sections of the
volume, and we examine the users' ability to contour the same
structures using oblique cross-sections with similar
consistency as they can using parallel cross-sections. We
measure the inter-observer and intra-observer variability of
trained physicians contouring on oblique cross-sections of
real patient data as compared to the traditional parallel
cross-sections, and show that the variation is much higher
for oblique contouring. We then show that this variability
can be greatly reduced by integrating a collection of
training images into the interface.
Interactive skeletonization of intensity volumes The Visual Computer (Proceedings of CGI'09), 25(5-7):627-635 (Paper, Video, Download)
S. Abeysinghe, T. Ju.
We present an interactive approach for
identifying skeletons (i.e. centerlines) in intensity volumes, such as those produced by biomedical imaging. While skeletons are very
useful for a range of image analysis tasks, it is extremely difficult to obtain skeletons with correct connectivity and shape from noisy
inputs using automatic skeletonization methods. In this paper we explore how easy-to-supply user inputs, such as simple mouse clicking
and scribbling, can guide the creation of satisfactory skeletons. Our contributions include formulating the task of drawing 3D
centerlines given 2D user inputs as a constrained optimization problem, solving this problem on a discrete graph using a shortest-path
algorithm, building a graphical interface for interactive skeletonization and testing it on a range of biomedical data.
Adaptive smooth surface fitting with manifolds
The Visual Computer (Proceedings of CGI'09), 25(5-7):589-597
C. Grimm, T. Ju, L. Phan, J. Hughes.
We present a smooth, everywhere C^k, analytic
surface representation for closed surfaces of arbitrary topology.
We demonstrate fitting this representation to meshes of
varying resolutions and sampling quality. The fitting process
is adaptive and provides controls for both the average and
the maximum allowable error. The representation is suitable
for applications which require consistent parameterizations
across different surfaces.
Fixing Geometric Errors on Polygonal Models: A Survey
Journal of Computer Science and Technology, 24(1):19-29
Polygonal models are popular representations of 3D objects. The use of polygonal models in computational applications often requires a model to properly bound a 3D solid. That is, the polygonal model needs to be closed, manifold, and free of self-intersections. This paper surveys a sizeable literature for repairing models that do not satisfy this criteria, focusing on categorizing them by their methodology and capability. We hope to offer pointers to further readings for researchers and practitioners, and suggestions of promising directions for future research endeavors.
Reusable Skinning Templates Using Cage-based Deformations
ACM Transactions on Graphics (Proceedings of Siggraph Asia 2008), 27(5):1-10
T. Ju, Q.-Y. Zhou, M. van de Panne, D. Cohen-Or, U. Neumann
Character skinning determines how the shape of the surface geometry
changes as a function of the pose of the underlying skeleton. In
this paper we describe skinning templates, which define common
deformation behaviors for common joint types. This abstraction allows
skinning solutions to be shared and reused, and they allow a
user to quickly explore many possible alternatives for the skinning
behavior of a character. The skinning templates are implemented
using cage-based deformations, which offer a flexible design space
within which to develop reusable skinning behaviors. We demonstrate
the interactive use of skinning templates to quickly explore
alternate skinning behaviors for 3D models.
Interactive Separation of Segmented Bones in CT Volumes Using Graph Cut
Lecture Notes in Computer Science (Proceedings of MICCAI 2008), 5241:296-304
L. Liu, D. Raber, D. Nopachai, P. Commean, D. Sinacore,
F. Prior, R. Pless, and T. Ju
We present a fast, interactive method for separating bones
that have been collectively segmented from a CT volume. Given userprovided
seed points, the method computes the separation as a multiway
cut on a weighted graph constructed from the binary, segmented
volume. By properly designing and weighting the graph, we show that
the resulting cut can accurately be placed at bone-interfaces using only a
small number of seed points even when the data is noisy. The method has
been implemented with an interactive graphical interface, and used to
separate the 12 human foot bones in 10 CT volumes. The interactive tool
produced compatible result with a ground-truth separation, generated
by a completely manual labelling procedure, while reducing the human
interaction time from a mean of 2.4 hours per volume in manual labelling
down to approximately 18 minutes.
Segmentation-free skeletonization of grayscale volumes for shape understanding.
IEEE International Conference on Shape Modeling and Applications 2008, pp. 63-71
S. Abeysinghe, M. Baker, W. Chiu, T. Ju
Medical imaging has produced a large number of volumetric
images capturing biological structures in 3D.
Computer-based understanding of these structures can often
benefit from the knowledge of shape components, particularly
rod-like and plate-like parts, in such volumes. Previously,
skeletons have been a common tool for identifying
these shape components in a solid object. However, obtaining
skeletons of a grayscale volume poses new challenges
due to the lack of a clear boundary between object and
background. In this paper, we present a new skeletonization
algorithm on grayscale volumes typical to medical imaging
(e.g., MRI, CT and EM scans), for the purpose of identifying
shape components. Our algorithm does not require an
explicit segmentation of the volume into object and background,
and is capable of producing skeletal curves and
surfaces that lie centered at rod-shaped and plate-shaped
parts in the grayscale volume. Our method is demonstrated
on both synthetic and medical data.
Surface Reconstruction From Non-parallel Curve Networks.
Computer Graphics Forum (Proceedings of Eurographics 2008), 27(2):155-163
L. Liu, C. Bajaj, J.O. Deasy, D.A. Low, T. Ju
Building surfaces from cross-section curves has wide applications including bio-medical modeling. Previous work
in this area has mostly focused on connecting simple closed curves on parallel cross-sections. Here we consider
the more general problem where input data may lie on non-parallel cross-sections and consist of curve networks
that represent the segmentation of the underlying object by different material or tissue types (e.g., skin, muscle,
bone, etc.) on each cross-section. The desired output is a surface network that models both the exterior surface
and the internal partitioning of the object. We introduce an algorithm that is capable of handling curve networks
of arbitrary shape and topology on cross-section planes with arbitrary orientations. Our algorithm is simple to
implement and is guaranteed to produce a closed surface network that interpolates the curve network on each
cross-section. Our method is demonstrated on both synthetic and bio-medical examples.
Geometric interpretation of the Gamma dose distribution comparison technique: interpolation-free
calculation Medical Physics, 35(3):879-887
(Paper, Program, Code)
T. Ju, T. Simpson, J.O. Deasy, D.A. Low
The Gamma dose distribution comparison tool has been used by numerous investigators to quantitatively
compare multidimensional dose distributions. The tool simultaneously evaluates the dose difference and
distance-to-agreement of two dose distributions. One of the weaknesses of the tool is that the comparison
requires one of the dose distributions to have a relatively high spatial resolution, due to the fact that
the Gamma tool measures the closest pixel in one of the dose distributions with individual pixels of
another, and this closest distance can not be accurately measured unless the pixels are finely spaced,
which requires time-consuming interpolation. We provide a reinterpretation of the Gamma distance as the
geometric distance between two 3D or 4D meshes representing the two 2D or 3D dose distributions.
The geometric approach avoids the drastic growth of calculation time incurred by interpolation and makes
the Gamma tool more practical and more accurate.
Shape modeling and matching in identifying 3D protein structures.
Computer Aided-Design, 40:708-720
S. Abeysinghe, T. Ju, M. L. Baker, W. Chiu
In this paper, we describe a novel geometric approach in the
process of recovering 3D protein structures from scalar
volumes. The input to our method is a sequence of
alpha-helices that make up a protein, and a low-resolution
protein density volume where possible locations of
alpha-helices have been detected. Our task is to identify
the correspondence between the two sets of helices, which
will shed light on how the protein folds in space. The
central theme of our approach is to cast the correspondence
problem as that of shape matching between the 3D volume and
the 1D sequence. We model both shapes as attributed
relational graphs, and formulate a constrained inexact graph
matching problem. To compute the matching, we developed an
optimal algorithm based on the A*-search with several choices
of heuristic functions. As demonstrated in a suite of
synthetic and authentic inputs, the shape-modeling approach
is capable of identifying helix correspondences in
noise-abundant volumes at high accuracy with minimal or no
Tarsal and Metatarsal Bone Mineral Density Measurement using Volumetric Quantitative Computed Tomography.
Journal of Digital Imaging, 22(5): 492-502
P. K. Commean, T. Ju, L. Liu, D. R. Sinacore, M. K. Hastings, M. J. Mueller
A new method for measuring bone mineral density (BMD) of the tarsal and metatarsals is described using volumetric quantitative computed tomography (VQCT) in conjunction with geometric subdivision in subjects with diabetes mellitus and peripheral neuropathy. In addition to whole-bone segmentation and measurement, we performed atlas-based partitioning of sub-regions within the second metatarsal for all subjects, from which the volumes and BMDs were obtained for each sub-region. The sub-region measurement BMD errors (root mean square coefficient of variation) within the shaft, proximal end and distal end were shown to vary by approximately 1% between the two scans of each subject. These methods can provide an important outcome measure for clinical research trials investigating the effects of interventions, aging or disease progression on bone loss or gain in individual foot bones.
Editing The Topology of 3D Models by Sketching.
ACM Transactions on Graphics (Proceedings of SIGGRAPH 2007), 26(3): 42
(Paper, Video (33MB),
T. Ju, Q-Y Zhou, S-M Hu
We present a method for modifying the topology of a 3D model
with user control. The heart of our method is a guided topology
editing algorithm. Given a source model and a user-provided target
shape, the algorithm modifies the source so that the resulting model
is topologically consistent with the target. Our algorithm permits
removing or adding various topological features (e.g., handles, cavities
and islands) in a common framework and ensures that each
topological change is made by minimal modification to the source
model. To create the target shape, we have also designed a convenient
2D sketching interface for drawing 3D line skeletons. As
demonstrated in a suite of examples, the use of sketching allows
more accurate removal of topological artifacts than previous methods,
and enables creative designs with specific topological goals.
Real-time homogenous translucent material editing.
Computer Graphics Forum (Proceedings of Eurographics 2007), 26(3):545-552
K. Xu, Y. Gao, Y. Li, T. Ju, S.-M. Hu
This paper presents a novel method for real-time homogenous translucent material editing under fixed illumination.
We consider the complete analytic BSSRDF model proposed by Jensen et al. [JMLH01], including both
multiple scattering and single scattering. Our method allows the user to adjust the analytic parameters of BSSRDF
and provides high-quality, real-time rendering feedback. Inspired by recently developed Precomputed Radiance
Transfer (PRT) techniques, we approximate both the multiple scattering diffuse reflectance function and the single
scattering exponential attenuation function in the analytic model using basis functions, so that re-computing
the outgoing radiance at each vertex as parameters change reduces to simple dot products. In addition, using a
non-uniform piecewise polynomial basis, we are able to achieve smaller approximation error than using bases
adopted in previous PRT-based works, such as spherical harmonics and wavelets. Using hardware acceleration,
we demonstrate that our system generates images comparable to [JMLH01] at real-time frame-rates.
Shape modeling and matching in identifying protein structure from
ACM Symposium on Solid and Physical Modeling 2007
S. Abeysinghe, T. Ju, M. Baker, W. Chiu
In this paper, we describe a novel, shape-modeling approach to recovering
3D protein structures from volumetric images. The input
to our method is a sequence of a-helices that make up a protein,
and a low-resolution volumetric image of the protein where possible
locations of a-helices have been detected. Our task is to identify
the correspondence between the two sets of helices, which will
shed light on how the protein folds in space. The central theme of
our approach is to cast the correspondence problem as that of shape
matching between the 3D volume and the 1D sequence. We model
both the shapes as attributed relational graphs, and formulate a constrained
inexact graph matching problem. To compute the matching,
we developed an optimal algorithm based on the A*-search
with several choices of heuristic functions. As demonstrated in a
suite of real protein data, the shape-modeling approach is capable of
correctly identifying helix correspondences in noise-abundant volumes
with minimal or no user intervention.
Computing a family of skeletons of volumetric
models for shape description
Computer-Aided Design, 39(5):352-360 (Paper)
T. Ju, M. Baker, W. Chiu
Skeletons are important shape descriptors in object representation and recognition.
Typically, skeletons of volumetric models are computed using iterative thinning.
However, traditional thinning methods often generate skeletons with complex structures
that are unsuitable for shape description, and appropriate pruning methods
are lacking. In this paper, we present a new method for computing skeletons of volumetric
models by alternating thinning and a novel skeleton pruning routine. Our
method creates a family of skeletons parameterized by two user-specified numbers
that determine respectively the size of curve and surface features on the skeleton.
As demonstrated on both real-world models and protein images in bio-medical research,
our method generates skeletons with simple and meaningful structures that
are particularly suitable for describing cylindrical and plate-like shapes.
Learning-based Segmentation Framework for Tissue
Gene Expression Data
IEEE Transactions on Medical Imaging, 26(5):728-744 (Paper)
M. Bello, T. Ju, J. Carson, J. Warren, W. Chiu, I.A. Kakadiaris
Associating specific gene activity with functional
locations in the brain results in a greater understanding of
the role of the gene. To perform such an association for the
over 20,000 genes in the mammalian genome, reliable automated
methods that characterize the distribution of gene expression in
relation to a standard anatomical model are required. In this
paper, we propose a new automatic method that results in the
segmentation of gene expression images into distinct anatomical
regions in which the expression can be quantified and compared
with other images. Our contribution is a novel hybrid atlas
that utilizes a statistical shape model based on a subdivision
mesh, texture differentiation at region boundaries, and features
of anatomical landmarks to delineate boundaries of anatomical
regions in gene expression images. This atlas, which provides a
common coordinate system for internal brain data, is being used
to create a searchable database of gene expression patterns in the
adult mouse brain. Our framework annotates the images about
four times faster and has achieved a median spatial overlap of up
to 0.92 compared with expert segmentation in 64 images tested.
This tool is intended to help scientists interpret large-scale gene
expression patterns more efficiently.
Topology Repair of Solid Models Using Skeletons
IEEE Transactions on Visualization and Computer Graphics, 13(4):675-685 (Paper,
Q-Y Zhou, T. Ju, S-M. Hu
We present a method for repairing topological errors
on solid models in the form of small surface handles,
which often arise from surface reconstruction algorithms. We
utilize a skeleton representation that offers a new mechanism
for identifying and measuring handles. Our method presents
two unique advantages over previous approaches. First, handle
removal is guaranteed not to introduce invalid geometry or
additional handles. Second, by using an adaptive grid structure,
our method is capable of processing huge models efficiently at
A general geometric construction of
coordinates in a convex simplicial polytope
Computer Aided Geometric Design, 24(3): 161-178 (Paper,
T. Ju, P. Liepa, J. Warren
Barycentric coordinates are a fundamental concept in computer graphics and geometric
modeling. We extend the geometric construction of Floater's mean value
coordinates to a general form that is capable of constructing a family of coordinates
in a convex 2D polygon, 3D triangular polyhedron, or a higher-dimensional
simplicial polytope. This family unifies previously known coordinates, including
Wachspress coordinates, mean value coordinates and discrete harmonic coordinates,
in a simple geometric framework. Using the construction, we are able to create a
new set of coordinates in 3D and higher dimensions and study its relation with
known coordinates. We show that our general construction is complete, that is, the
resulting family includes all possible coordinates in any convex simplicial polytope.
Manifold Dual Contouring
IEEE Transactions on Visualization and Computer Graphics, 13(3):610-619 (Paper)
S. Schaefer, T. Ju, J. Warren
Dual Contouring is a feature-preserving iso-surfacing
method that extracts crack-free surfaces from both uniform and
adaptive octree grids. We present an extension of Dual Contouring
that further guarantees that the mesh generated is a manifold
even under adaptive simplification. Our main contribution is
an octree-based, topology-preserving vertex clustering algorithm
for adaptive contouring. The contoured surface generated by
our method contains only manifold vertices and edges, preserves
sharp features, and possesses much better adaptivity than those
generated by other iso-surfacing methods under topologically safe
Identification of Secondary Structure Elements in
Intermediate Resolution Density Maps
Structure, 15(1):7-19, 2007 (Paper)
M. L. Baker, T. Ju, W. Chiu
An increasing number of structural studies of large macromolecular complexes, both in
X-ray crystallography and electron cryomicroscopy, have resulted in intermediate
resolution (5-10 A) structures. Despite being limited in resolution, significant structural
and functional information may be extractable from these maps. To aid in the analysis
and annotation of these complexes, we have developed SSEhunter, a tool for the
quantitative detection of alpha-helices and beta-sheets. Based on density skeletonization, local
geometry calculations and a template-based search, SSEhunter has been tested and
validated on a variety of simulated and authentic subnanometer resolution density maps.
The result is a robust, user-friendly approach that allows users to quickly visualize, assess
and annotate intermediate resolution density maps. Beyond secondary structure element
identification, the skeletonization algorithm in SSEhunter provides secondary structure
topology, potentially useful in leading to structural models of individual molecular
components directly from the density.
A Unified, Integral Construction For Coordinates Over Closed Curves
Computer-Aided Geometric Design, 24(8-9):481-493
S. Schaefer, T. Ju and J. Warren
We propose a simple generalization of Shephard's interpolation to piecewise smooth, convex closed curves that yields a family of
boundary interpolants with linear precision. Two instances of this family reduce to previously known interpolants: one based on a
generalization of Wachspress coordinates to smooth curves and the other an integral version of mean value coordinates for smooth
curves. A third instance of this family yields a previously unknown generalization of discrete harmonic coordinates to smooth
curves. For closed, piecewise linear curves, we prove that our interpolant reproduces a general family of barycentric coordinates
considered by Floater, Hormann and Kos that includes Wachspress coordinates, mean value coordinates and discrete harmonic
Probing 3'-ssDNA Loop Formation in E. coli RecBCD/RecBC-DNA
Complexes using Non-natural DNA: A Model for "Chi"
Journal of Molecular Biology, 362(1):26-43
C. Jason Wong, Rachel L. Rice, Nathan A. Baker, Tao Ju and Timothy M. Lohman
The equilibrium binding of E. coli RecBC and RecBCD helicases to duplex DNA ends containing varying lengths of polyethylene glycol
(PEG) spacers within pre-formed 3'-single-stranded (ss) DNA ((dT)n) tails were studied. These studies were designed to test a previous
proposal that the 3'-(dT)n tail can be looped out upon binding RecBC and RecBCD for 3'-ssDNA tails with n>=6 nucleotides.
Equilibrium binding of protein to unlabeled DNA substrates with ends containing PEG-substituted 3'-ssDNA tails was examined by
competition with a Cy3-labeled reference DNA which undergoes a Cy3 fluorescence enhancement upon protein binding. We find that the
binding affinities of both RecBC and RecBCD for a DNA end are unaffected upon substituting PEG for the ssDNA between the sixth and the
final two nucleotides of the 3'-(dT)n tail. However, placing PEG at the end of the 3'-(dT)n tail increases the binding affinities to
their maximum values (i.e. the same as binding constants for RecBC or RecBCD to a DNA end with only a 3'-(dT)6 tail). Equilibrium
binding studies of a RecBC mutant containing a nuclease domain deletion, RecBC suggest that looping of the 3'-tail (when n>=6
nucleotides) occurs even in the absence of the RecB nuclease domain, the nuclease domain stabilizes such loop formation. Computer
modeling of the RecBCD-DNA complexes suggests that the loop in the 3'-ssDNA tail may form at the RecB/RecC interface. Based on these
results we suggest a model for how a loop in the 3'-ssDNA tail might form upon encounter of a "Chi" recognition sequence during
unwinding of DNA by the RecBCD helicase.
Intersection-free Contouring on An Octree Grid
Proceedings of Pacific Graphics, 2006
(Paper, Code on Sourceforge)
T. Ju and T. Udeshi
A method for extracting intersection-free iso-surfaces
from volumetric data with an octree structure is presented.
Unlike contouring techniques designed for uniform grids
(such as Marching Cubes), adaptive contouring methods
(such as Dual Contouring) can and do often generate intersecting
polygons. Our main contribution is a polygon generation
algorithm that produces triangles enclosed in nonoverlapping
volumes, which guarantees an intersection-free
mesh. Like other adaptive contouring methods, this new
method generates crack-free and feature-preserving surfaces
on both uniform and octree grids. We demonstrate
the method on both scanned objects and industrial models.
Computing a family of skeletons of volumetric models
for shape description
Proceedings of Geometric Modeling and Processing 2006, pp. 235 - 247
T. Ju, M. Baker, and W. Chiu
Skeletons are important shape descriptors in object representation and
recognition. Typically, skeletons of volumetric models are computed via an iterative
thinning process. However, traditional thinning methods often generate
skeletons with complex structures that are unsuitable for shape description, and
appropriate pruning methods are lacking. In this paper, we present a new method
for computing skeletons on volumes by alternating thinning and a novel skeleton
pruning routine. Our method creates a family of skeletons parameterized by two
user-specified numbers that determine respectively the size of curve and surface
features on the skeleton. As demonstrated on both real-world models and medical
images, our method generates skeletons with simple and meaningful structures
that are particularly suitable for describing cylindrical and plate-like shapes.
3D Volume Reconstruction of a Mouse Brain
from Histological Sections using Warp
Journal of Neuroscience Methods, 156(1-2):84-100
T. Ju, J. Warren, J. Carson, M. Bello, I. Kakadiaris, W. Chiu, C. Thaller and G. Eichele
Sectioning tissues for optical microscopy often introduces upon the resulting sec-
tions distortions that make 3d reconstruction di??cult. Here we present an automatic
method for producing a smooth 3D volume from distorted 2D sections in the ab-
sence of any undistorted references. The method is based on pairwise elastic image
warps between successive tissue sections, which can be computed by 2D image reg-
istration. Using a Gaussian ??lter, an average warp is computed for each section
from the pairwise warps in a group of its neighboring sections. The average warps
deform each section to match its neighboring sections, thus creating a smooth vol-
ume where corresponding features on successive sections lie close to each other. The
proposed method can be used with any existing 2D image registration method for
3D reconstruction. In particular, we present a novel image warping algorithm based
on dynamic programming that extends Dynamic Time Warping in 1D speech recog-
nition to compute pairwise warps between high-resolution 2D images. The warping
algorithm e??ciently computes a restricted class of 2D local deformations that are
characteristic between successive tissue sections. Finally, a validation framework
is proposed and applied to evaluate the quality of reconstruction using both real
sections and a synthetic volume.
Building 3D surface networks from 2D curve networks with
application to anatomical modeling
Proceedings of Pacific Graphics 2005, 21(8-10):764-773
The Visual Computer,
T. Ju, J. Warren, J. Carson, G. Eichele, C. Thaller, W. Chiu, M. Bello and I. Kakadiaris
We present a novel method that automatically constructs
a surface network from curve networks with arbitrary
topology and partitioning an arbitrary number of materials.
The surface network exactly interpolates the curve
network on each plane and is guaranteed to be free of gaps
or self-intersections. In addition, our method provides a flexible
framework for user interaction so that the surface topology
can be modified conveniently when necessary. As an application,
we applied the method to build a high-resolution
3D model of the mouse brain from 2D anatomical boundaries
defined on 350 tissue sections.
A Digital Atlas to Characterize the Mouse Brain Transcriptome
PLoS Computational Biology, 1(4): e41, 2005
J. Carson, T. Ju, H. Lu, C. Thaller, M. Xu, S. Pallas, M. C. Crair, J. Warren, W. Chiu and G. Eichele
Here we have developed a computational method for annotating gene expression patterns in the context
of a digital atlas to facilitate custom user-queries and comparisons of this type of data.
This procedure has been applied to 200 genes in the postnatal mouse brain.
As an illustration of utility, we identify candidate genes that may be related to Parkinson's disease by
using the expression of a dopamine transporter in the substantia nigra as a search query pattern.
In addition, we discover that transcription factor Rorb is down-regulated in the barrelless mutant relative
to control mice by quantitative comparison of expression patterns in layer IV somatosensory cortex.
Hybrid Segmentation Framework for Tissue Images
Containing Gene Expression Data
Proceedings of the International Conference on Medical Image Computing and Computer Assisted
Intervention (MICCAI), p254-261, 2005
M. Bello, T. Ju, J. Warren, J. Carson, W. Chiu, C. Thaller, G. Eichele and I. Kakadiaris
this work, we propose a new automatic method that results in the segmentation of
gene expression images into distinct anatomical regions in which the expression
can be quantified and compared with other images. Our method utilizes models of
shape of training images, texture differentiation at region boundaries, and features
of anatomical landmarks to deform a subdivision mesh-based atlas to fit gene expression
Geometric Construction of
Coordinates for Convex Polyhedra using Polar Duals
Proceedings of Eurographics Symposium on Geometry Processing, p181-186, 2005
T. Ju, S. Schaefer, J. Warren, M.Desbrun
A fundamental problem in geometry processing is that of expressing a point inside a convex polyhedron as a
combination of the vertices of the polyhedron. In this paper, we present a uned geometric construction for building these weighted
combinations using the notion of polar duals. We show that our method yields a simple geometric construction
for Wachspress's barycentric coordinates, as well as for constructing Colin de Verdire matrices from convex
polyhedra, critical step in Lovasz's method with applications to parameterizations.
Mean value coordinates for closed triangular meshes
Proceedings of ACM SIGGRAPH, 2005
ACM Transactions on Graphics, 24(3):561-566
T. Ju, S. Schaefer, J. Warren
In this paper, we generalize mean
value coordinates from closed 2D polygons to closed triangular
meshes. Given such a mesh P, we show that these coordinates
are continuous everywhere and smooth on the interior of P. The
coordinates are linear on the triangles of P and can reproduce linear
functions on the interior of P. To illustrate their usefulness, we
conclude by considering several interesting applications including
constructing volumetric textures and surface deformation.
Robust Repair of Polygonal Models
Proceedings of ACM SIGGRAPH, 2004
ACM Transactions on Graphics, 23(3):888-895
We present a robust method for repairing arbitrary polygon models.
The method is guaranteed to produce a closed surface that
partitions the space into disjoint internal and external volumes.
Our novel algorithm can efficiently process
large models containing millions of polygons and is capable of reproducing
sharp features in the original geometry.
Automated Characterization of Gene Expression Patterns
with an Atlas of the Mouse Brain
Proceedings of IEEE International Conference of the
Engineering in Medicine and Biology Society (EMBS), p2917-2920, 2004 (Paper)
J. P. Carson, T. Ju, C. Thaller, J. Warren, M. Bello, I. Kakadiaris, W. Chiu, G. Eichele
A spatio-temporal map of gene activity in the
brain would be an important contribution to the understanding
of brain development, disease, and function. Such a resource is
now possible using high-throughput in situ hybridization, a
method for transcriptome-wide acquisition of cellular
resolution gene expression patterns in serial tissue sections.
However, querying an enormous quantity of image data
requires computational methods for describing and organizing
gene expression patterns in a consistent manner. In addressing
this, we have developed procedures for automated annotation
of gene expression patterns in the postnatal mouse brain.
Landmark-driven, Atlas-based Segmentation of Mouse
Brain Tissue Images Containing Gene Expression Data
Proceedings of the International Conference on Medical Image Computing and Computer Assisted
Intervention (MICCAI), p192-199, 2004
Kakadiaris, Musodiq Bello, Shiva Arunachalam, Wei Kang, Tao Ju,
Joe Warren, James Carson, Wah Chiu, Christina Thaller, and Gregor Eichele
In this paper, we present an
anatomical landmark detection method that has been incorporated into an atlasbased
segmentation. The addition of this technique significantly increases the accuracy
of automated atlas-deformation. The resulting large-scale annotation will
help scientists interpret gene expression patterns more rapidly and accurately.
Turtle Geometry in Computer Graphics and Computer Aided Design
Computer-Aided Design, 36(14): 1471-1482, 2004 (Paper)
Ron Goldman, Scott Schaefer, and Tao Ju
LOGO is a programming language incorporating turtle graphics, originally devised for
teaching computing to young children in elementary and middle schools. Here we advocate the use
of LOGO to help introduce some of the basic concepts of computer graphics and computer aided
design to undergraduate and graduate students in colleges and universities. We shall show how to
motivate affine coordinates and affine transformations, fractal curves and iterated function systems,
relaxation methods and subdivision schemes from elementary notions in turtle geometry and turtle
Recursive Turtle Programs and Iterated Affine Transformations
Computer and Graphics, 28(6): 991-1004, 2004.
Scott Schaefer and Ron Goldman.
Recursive turtle programs (RTP) and iterated affine transformations (IAT) are two popular methods
for generating fractals. We show that these two models are equivalent in their expressive power.
Conversion algorithms in both directions are presented explicitly from the structure of the RTP
and the affine transformations in the IAT.
A geometry database for gene expression data
Proceedings of Eurographics Symposium on Geomtry Processing, 2003.
Joe Warren, Gregor Eichele, Christina Thaller, Wah Chiu and James Carson
In this paper, we describe the structure of a geometric
database for the mouse brain that allows biologists to organize
and search gene expression data in the mouse brain. The central component of
this database is a standard atlas, represented as a subdivision mesh, that explicitly partitions the
mouse brain into key anatomical subregions.
Due to this
partitioning, user queries comparing
expression data between various genes can be restricted to
anatomical subregions without difficulty while the
multi-resolution structure of the subdivision mesh allows these
queries to be processed efficiently. The database and searching tools are available
Morphing of rational b-spline curves and surfaces using mass distributions
Proceedings of Eurographics, short papers, 2003.
Ju and Ron Goldman.
A rational B-spline curve or surface is a
collection of points associated with a mass (weight) distribution.
These mass distributions can be used to exert local control over
the morph between two rational B-spline curves or surfaces. Here
we propose a technique for designing customized morphs by
attaching appropriate mass distributions to target B-spline curves
and surfaces. We also develop a user interface for this morphing
method that is easy to use and requires no knowledge of B-splines
on the part of the user.
Convex Contouring on Volumetric Data
The Visual Computer, 19: 513-525, 2003.
Tao Ju, Scott
Schaefer, Joe Warren.
In this paper we present a fast, table-driven isosurface
extraction technique on volumetric data. Unlike Marching Cubes or
other cell-based algorithms, the proposed polygonization generates
convex negative space inside individual cells, enabling fast
collision detection on the triangulated isosurface. In our
implementation, we are able to perform over 2 million point
classifications per second. The algorithm is driven by an
automatically constructed look-up table that stores compact
decision trees by sign configurations.
Using the same technique, we can perform fast, crack-free
multi-resolution contouring on nested grids of volumetric data.
Dual Contouring on Hermite Data
Proceedings of ACM SIGGRAPH, 2002.
(Paper, Code on Sourceforge)
Tao Ju, Frank
Losasso, Scott Schaefer and Joe Warren
This paper describes a new method for contouring a signed grid
whose edges are tagged by Hermite data (i.e; exact intersection
points and normals). We extend this contouring method to the case of
multi-signed functions and demonstrate how to model textured contours
using multi-signed functions. Using a new, numerically stable
representation for quadratic error functions, we develop an octreebased
method for simplifying these contours and their textured regions.
We next extend our contouring method to these simplified
Modifying the shape of NURBS surfaces with geometric constraints
Computer Aided Design, 33(12): 903-912, 2001. (Paper)
Shi-Min Hu, You-Fu Li, Tao Ju and Xiang Zhu
NURBS surfaces are among the most commonly used parametric surfaces in CAGD and Computer Graphics. This
paper investigates shape modification of NURBS surfaces with geometric constraints, such as point, normal
vector, and curve constraints. Two new methods are presented by constrained optimization and energy
minimization. The former is based on minimizing changes in control net of surfaces, whereas the latter is
based on strain energy minimization. By these two methods, we change control points and weights of an
original surface, such that the modified surface satisfies the given constraints. Comparison results and
practical examples are also given.
Approximate merging of a pair of Bezier curves
Computer Aided Design, 33(2): 125-136, 2001. (Paper)
Hu Shi-Min, Tong Ruo-Feng, Ju Tao and Sun Jia-Guang
This paper deals with the merging problem, i.e. to approximate two adjacent Bezier curves by a single Bezier curve.
A novel approach for
approximate merging is introduced in the paper by using the constrained optimization method. The basic idea of this
method is to find
conditions for the precise merging of Bezier curves first, and then compute the constrained optimization solution by
moving the control
points. "Discrete" coefficient norm in L2 sense and "squared difference integral" norm are used in our method.
Continuity at the endpoints of
curves are considered in the merging process, and approximate merging with points constraints are also discussed.
Further, it is shown that
the degree elevation of original Bezier curves will reduce the merging error.