Home
Bio
Teaching
Advising
Service
Projects
Software
Publications
Music
     

Tao Ju

Professor
Department of Computer Science and Engineering
Washington University in St. Louis
Office: McKelvey 2035
Phone: 314-935-6648
Email: taoju at wustl.edu
Bio Sketch
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 (now at Stanford) 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.
Teaching
Advising
Current
  • Gustavo Gratacos Hernandez (PhD)
  • Yiwen Ju (PhD)

Past
  • Sasakthi Abeysinghe (PhD, 2010, last known at OLiVE)
  • Lu Liu (PhD, 2011, last known at Meta)
  • Ming Zou (PhD, 2016, last known at Waymo)
  • Michelle Holloway (PhD, 2016, last known at Partek)
  • Hang Dou (PhD, 2017, now at Nvidia)
  • Yajie Yan (PhD, 2018, now at Apple)
  • Zhiyang Huang (PhD, 2019, now at Huawei)
  • Huayi Zeng (PhD, 2020, now at Waymo)
  • Dan Zeng (PhD, 2022, now at Meta Research)
  • Xingyi Du (PhD, 2023, now at Tencent Americas)

  • Tim Simpson (MS., 2008)
  • Trung D. Nguyen (MS, 2011, last known at Microsoft)
  • Stephen Schuh (MS, 2011, last known at Google)
  • Ruosi Li (MS, 2011, last known at Meta)
  • Derek Burrows (MS, 2013, last known at Boeing)
Service

University and Department Responsibilities
  • Associate Chair of Research, Department of Computer Science and Engineering (2022-2023)
  • Vice Dean of Research, McKelvey School of Engineering (2016-2021)
  • Ambassador to Tsinghua University, McDonnell International Scholars Academy (2013-present)
  • Technical Report Series Coordinator (2008-2016)
  • ACM chapter Faculty Advisor (2010-2016)
  • School of Engineering Undergraduate Board member (2006-2015)

Journal Editorial Boards
  • IEEE Transactions on Visualization and Computer Graphics (2015-2022; Associate EIC 2019-2022)
  • Computer Graphics Forum, Associate Editor (2011-2014; 2019-2022)
  • Computer-Aided Design, Associate Editor (2012-present)
  • Graphical Models, Associate Editor (2010-present)
  • Computational Visual Media, Associate Editor (2015-present)

Program Committees
  • Siggraph
  • Siggraph Asia
  • Eurographics
  • Symposium on Geometry Processing (PC Co-chair: 2018)
  • Pacific Graphics (PC Co-chair: 2007)
  • ACM Symposium on Solid and Physical Modeling
  • Geometric Modeling and Processing (PC Co-chair: 2019)
  • International Conference on Shape Modeling and Applications (PC Co-chair: 2024)
  • Sketch-Based Interfaces and Modeling
  • International Symposium on Visual Computing
  • Computer Graphics International Conference

Professional Societies
  • ACM, Member
  • IEEE, Senior Member
  • AsiaGraphics, executive committee member (2016-2021)
Software and Websites

Education
Computational Geometry Demos: A suite of Javascript-based, in-browser demos for learning computational geometry algorithms with step-by-step animations. Algorithms include convex hulls, Voronori diagrams, Delaunay triangulations, segment intersections, arrangements and k-D trees.
Research
VIPSS: A command-line tool for reconstructing an implicit surface from an unoriented point set. Based on Siggraph 2019 paper. (Developed by Zhiyang Huang)
Voxel Cores: A command-line tool for computing the medial axis of a 3D shape. Based on Siggraph 2018 paper. (Developed by Yajie Yan)
Erosion Thickness: A GUI program for creating a family of descriptive, clean skeletons from a possibly noisy medial axis. Based on Siggraph 2016 paper. (Developed by Yajie Yan)
TopoInterp: A software for reconstructing a closed surface from cross-section curves with topological guarantees. Based on Siggraph 2015 paper. (Developed by Ming Zou)
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 surface 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.

Biomedical applications
TopoRoot: A software pipeline for computing branching hierarchy and fine-grained traits of maize (corn) root crowns from X-ray CT images.
Gorgon: An interactive molecular modeling system specifically geared towards cryo-EM and other low resolution structures of macromolecular complexes.
StackAligner: A graphical toolkit for reconstructing smooth 3D volumes from serially sectioned tissue images. Based on Journal of Neuroscience Methods paper "3D Volume Reconstruction of a Mouse Brain from Histological Sections using Warp Filtering".
Selected Publications
2024
Adaptive Grid Generation for Discretizing Implicit Complexes
ACM Transactions on Graphics (Proc. ACM Siggraph 2024), 43(4): No. 82 (Paper, Project, Code and data)
Yiwen Ju, Xingyi Du, Qingnan Zhou, Nathan Carr, Tao Ju.

We present a method for generating a simplicial (e.g., triangular or tetrahedral) grid to enable adaptive discretization of implicit shapes defined by a vector function. Such shapes, which we call implicit complexes, are generalizations of implicit surfaces and useful for representing non-smooth and non-manifold structures. While adaptive grid generation has been extensively studied for polygonizing implicit surfaces, few methods are designed for implicit complexes. Our method can generate adaptive grids for several implicit complexes, including arrangements of implicit surfaces, CSG shapes, material interfaces, and curve networks. Importantly, our method adapts the grid to the geometry of not only the implicit surfaces but also their lower-dimensional intersections. We demonstrate how our method enables efficient and detail-preserving discretization of non-trivial implicit shapes.
TopoRoot+: Computing Whorl and Soil Line Traits of Field-Excavated Maize Roots from CT Imaging
Plant Methods, accepted (Paper link, data and code)
Yiwen Ju, Alexander E. Liu, Kenan Oestreich, Tina Wang, Christopher N. Topp, Tao Ju

TopoRoot+ is a computational pipeline that computes architectural traits from 3D X-ray CT volumes of excavated maize root crowns. TopoRoot+ builds upon the TopoRoot software, which computes a skeleton representation of the root system and produces a suite of fine-grained traits including the number, geometry, connectivity, and hierarchy level of individual roots. TopoRoot+ adds new algorithms on top of TopoRoot to detect whorls, their associated nodal roots, and the soil line location. These algorithms offer a new set of traits related to whorls and soil lines, such as internode distances, root traits at every hierarchy level associated with a whorl, and aggregate root traits above or below the ground. TopoRoot+ is validated on a diverse collection of field-grown maize root crowns consisting of nine genotypes and spanning across three years, and it exhibits reasonable accuracy against manual measurements for both whorl and soil line detection.
2023
Tree Recovery by Dynamic Programming
IEEE Trans. Pattern. Anal. Mach. Intell. 45(12): 15870-15882. (Paper, Appendices, Code and data)
Gustavo Gratacos, Ayan Chakrabarti, Tao Ju.

Tree-like structures are common, naturally occurring objects that are of interest to many fields of study, such as plant science and biomedicine. Analysis of these structures is typically based on skeletons extracted from captured data, which often contain spurious cycles that need to be removed. We propose a dynamic programming algorithm for solving the NP-hard tree recovery problem formulated by Estrada et al., which seeks a least-cost partitioning of the graph nodes that yields a directed tree. Our algorithm finds the optimal solution by iteratively contracting the graph via node-merging until the problem can be trivially solved. By carefully designing the merging sequence, our algorithm can efficiently recover optimal trees for many real-world data where Estrada et al. only produces sub-optimal solutions. We also propose an approximate variant of dynamic programming using beam search, which can process graphs containing thousands of cycles with significantly improved optimality and efficiency compared with Estrada et al.
Variational Pruning of Medial Axes of Planar Shapes
Computer Graphics Forum 42(5):e14902 (Proc. SGP'23) (Paper, Project)
Peter Rong and Tao Ju.

Medial axis (MA) is a classical shape descriptor in graphics and vision. The practical utility of MA, however, is hampered by its sensitivity to boundary noise. To prune unwanted branches from MA, many definitions of significance measures over MA have been proposed. However, pruning MA using these measures often comes at the cost of shrinking desirable MA branches and losing shape features at fine scales. We propose a novel significance measure that addresses these shortcomings. Our measure is derived from a variational pruning process, where the goal is to find a connected subset of MA that includes as many points that are as parallel to the shape boundary as possible. We formulate our measure both in the continuous and discrete settings, and present an efficient algorithm on a discrete MA. We demonstrate on many examples that our measure is not only resistant to boundary noise but also excels over existing measures in preventing MA shrinking and recovering features across scales.
XCheck: Verifying Integrity of 3D Printed Patient-Specific Devices via Computing Tomography
Proc. 32nd USENIX Security Symposium (Paper, Project, Code)
Z. Yu, Y. Chang, S. Zhai, N. Deily, T. Ju, X. Wang, U. Jammalamadaka, N. Zhang.

3D printing is bringing revolutionary changes to the field of medicine, with applications ranging from hearing aids to regrowing organs. As our society increasingly relies on this technology to save lives, the security of these systems is a growing concern. However, existing defense approaches that leverage side channels may require domain knowledge from computer security to fully understand the impact of the attack. To bridge the gap, we propose XCheck, which leverages medical imaging to verify the integrity of the printed patientspecific device (PSD). XCheck follows a defense-in-depth approach and directly compares the computed tomography (CT) scan of the printed device to its original design. XCheck utilizes a voxel-based approach to build multiple layers of defense involving both 3D geometric verification and multivariate material analysis. To further enhance usability, XCheck also provides an adjustable visualization scheme that allows practitioners’ inspection of the printed object with varying tolerance thresholds to meet the needs of different applications. We evaluated the system with 47 PSDs representing different medical applications to validate the efficacy.
2022
Isometric Energies for Recovering Injectivity in Constrained Mapping
Proc. ACM Siggraph Asia 2022, No. 36 (Paper, Project)
Xingyi Du, Danny M. Kaufman, Qingnan Zhou, Shahar Kovalsky, Yajie Yan, Noam Aigerman, Tao Ju.

Computing injective maps with low distortions is a long-standing problem in computer graphics. Such maps are particularly challenging to obtain in the presence of positional constraints, because an injective initial map is often not available. Recently, several energies were proposed and shown to be highly successful in optimizing injectivity from non-injective initial maps while satisfying positional constraints. However, minimizing these energies tends to produce elements with significant isometric distortions. This paper presents simple variants of these energies that retain their desirable traits while promoting isometry. While our method is not guaranteed to provide an injective map, we observe that, on large-scale 2D and 3D data sets, minimizing the proposed isometric variants results in a similar level of success in recovering injectivity as the original energies but a significantly lower isometric distortion.
RFEPS: Reconstructing Feature-Line Equipped Polygonal Surface
ACM Transactions on Graphics (Proc. ACM Siggraph Asia 2022), 41(6): No. 228 (Paper)
Rui Xu, Zixiong Wang, Zhiyang Dou, Chen Zong, Shiqing Xin, Mingyan Jiang, Tao Ju, Changhe Tu.

Feature lines are important geometric cues in characterizing the structure of a CAD model. Despite great progress in both explicit reconstruction and implicit reconstruction, it remains a challenging task to reconstruct a polygonal surface equipped with feature lines, especially when the input point cloud is noisy and lacks faithful normal vectors. In this paper, we develop a multistage algorithm, named RFEPS, to address this challenge. The key steps include (1) denoising the point cloud based on the assumption of local planarity, (2) identifying the feature-line zone by optimization of discrete optimal transport, (3) augmenting the point set so that sufficiently many additional points are generated on potential geometry edges, and (4) generating a polygonal surface that interpolates the augmented point set based on restricted power diagram. We demonstrate through extensive experiments that RFEPS, benefiting from the edge-point augmentation and the feature preserving explicit reconstruction, outperforms state of the art methods in terms of the reconstruction quality, especially in terms of the ability to reconstruct missing feature lines.
Robust Computation of Implicit Surface Networks for Piecewise Linear Functions
ACM Transactions on Graphics (Proc. ACM Siggraph 2022), 41(4): No. 41 (Paper, Project)
Xingyi Du, Qingnan Zhou, Nathan Carr, Tao Ju.

Implicit surface networks, such as arrangements of implicit surfaces and materials interfaces, are used for modeling piecewise smooth or partitioned shapes. However, accurate and numerically robust algorithms for discretizing either structure on a grid are still lacking. We present a unified approach for computing both types of surface networks for piecewise linear functions defined on a tetrahedral grid. Both algorithms are guaranteed to produce a correct combinatorial structure for any number of functions. Our main contribution is an exact and efficient method for partitioning a tetrahedron using the level sets of linear functions defined by barycentric interpolation. To further improve performance, we designed look-up tables to speed up processing of tetrahedra involving few functions and introduced an efficient algorithm for identifying nested 3D regions.
Topological Simplification of Nested Shapes
Computer Graphics Forum (Proc. SGP 2022), 41(5): 161-173. (Paper, Project)
Dan Zeng, Erin Chambers, David Letscher, Tao Ju.

We present a method for removing unwanted topological features (e.g., islands, handles, cavities) from a sequence of shapes where each shape is nested in the next. Such sequences can be found in nature, such as a multi-layered material or a growing plant root. Existing topology simplification methods are designed for single shapes, and applying them independently to shapes in a sequence may lose the nesting property. We formulate the nesting-constrained simplification task as an optimal labelling problem on a set of candidate shape deletions (``cuts'') and additions (``fills''). We explored several optimization strategies, including a greedy heuristic that sequentially propagates labels, a state-space search algorithm that is provably optimal, and a beam-search variant with controllable complexity. Evaluation on synthetic and real-world data shows that our method is as effective as single-shape simplification methods in reducing topological complexity and minimizing geometric changes, and it additionally ensures nesting. Also, the beam-search strategy is found to strike the best balance between optimality and efficiency.
2021
TopoRoot: a method for computing hierarchy and fine-grained traits of maize roots from 3D imaging
Plant Methods, 17: No. 127 (Paper link, data and code)
Dan Zeng, Mao Li, Ni Jiang, Yiwen Ju, Hannah Schreiber, Erin Chambers, David Letscher, Tao Ju, Christopher N. Topp

TopoRoot is a high-throughput computational method that computes fine-grained architectural traits from 3D images of maize root crowns or root systems. These traits include the number, length, thickness, angle, tortuosity, and number of children for the roots at each level of the hierarchy. TopoRoot combines state-of-the-art algorithms in computer graphics, such as topological simplification and geometric skeletonization, with customized heuristics for robustly obtaining the branching structure and hierarchical information. TopoRoot is validated on both CT scans of excavated field-grown root crowns and simulated images of root systems, and in both cases, it was shown to improve the accuracy of traits over existing methods.
Optimizing Global Injectivity for Constrained Parameterization
ACM Transactions on Graphics (Proc. ACM Siggraph Asia 2021), 40(6): No. 260 (Paper, Project)
Xingyi Du, Danny M. Kaufman, Qingnan Zhou, Shahar Z. Kovalsky, Yajie Yan, Noam Aigerman, Tao Ju

Injective parameterizations of triangulated meshes are critical across applications but remain challenging to compute. Existing algorithms to find injectivity either require initialization from an injective starting state, which is currently only possible without positional constraints, or else can only prevent triangle inversion, which is insufficient to ensure injectivity. Here we present, to our knowledge, the first algorithm for recovering a globally injective parameterization from an arbitrary non-injective initial mesh subject to stationary constraints. These initial meshes can be inverted, wound about interior vertices and/or overlapping. Our algorithm in turn enables globally injective mapping for meshes with arbitrary positional constraints. Our key contribution is a new energy, called smooth excess area (SEA), that measures non-injectivity in a map. This energy is well-defined across both injective and non-injective maps and is smooth almost everywhere, making it readily minimizable using standard gradient-based solvers starting from a non-injective initial state. Importantly, we show that maps minimizing SEA are guaranteed to be locally injective and almost globally injective, in the sense that the overlapping area can be made arbitrarily small.
Boundary-Sampled Halfspaces: A New Representation for Constructive Solid Modeling
ACM Transactions on Graphics (Proc. ACM Siggraph 2021), 40(4): No. 53 (Paper, Project)
Xingyi Du, Qingnan Zhou, Nathan Carr, Tao Ju

We present a novel representation of solid models for shape design. Like Constructive Solid Geometry (CSG), the solid shape is constructed from a set of halfspaces without the need for an explicit boundary structure. Instead of using Boolean expressions as in CSG, the shape is defined by sparsely placed samples on the boundary of each halfspace. This representation, called Boundary-Sampled Halfspaces (BSH), affords greater agility and expressiveness than CSG while simplifying the reverse engineering process. We discuss theoretical properties of the representation and present practical algorithms for boundary extraction and conversion from other representations. Our algorithms are demonstrated on both 2D and 3D examples.
2020
To cut or to fill: a global optimization approach to topological simplification
ACM Transactions on Graphics (Proc. ACM Siggraph Asia 2020), 39(6): No. 201 (Paper, Project)
Dan Zeng, Erin Chambers, David Letscher, Tao Ju.

We present a novel algorithm for simplifying the topology of a 3D shape, which is characterized by the number of connected components, handles, and cavities. Existing methods either limit their modifications to be only cutting or only filling, or take a heuristic approach to decide where to cut or fill. We consider the problem of finding a globally optimal set of cuts and fills that achieve the simplest topology while minimizing geometric changes. We show that the problem can be formulated as graph labelling, and we solve it by a transformation to the Node-Weighted Steiner Tree problem. When tested on examples with varying levels of topological complexity, the algorithm shows notable improvement over existing simplification methods in both topological simplicity and geometric distortions.
Lifting Simplices to Find Injectivity
ACM Transactions on Graphics (Proc. ACM Siggraph 2020), 39(4): No. 120 (Paper, Project)
Xingyi Du, Noam Aigerman, Qingnan Zhou, Shahar Kovalsky, Yajie Yan, Danny Kaufman, Tao Ju.

Mapping a source mesh into a target domain while preserving local injectivity is an important but highly non-trivial task. Existing methods either require an already-injective starting configuration, which is often not available, or rely on sophisticated solving schemes. We propose a novel energy form, called Total Lifted Content (TLC), that is equipped with theoretical properties desirable for injectivity optimization. By lifting the simplices of the mesh into a higher dimension and measuring their contents (2D area or 3D volume) there, TLC is smooth over the entire embedding space and its global minima are always injective. The energy is simple to minimize using standard gradient-based solvers. Our method achieved 100% success rate on an extensive benchmark of embedding problems for triangular and tetrahedral meshes, on which existing methods only have varied success.
Comprehensive 3D phenotyping reveals continuous morphological variation across genetically diverse sorghum inflorescences
New Phytologist, 226: 1873-1885 (Paper link, Journal cover, News coverage in Danforth and WashU)
Mao Li, Mon-Ray Shao, Dan Zeng, Tao Ju, Elizabeth A. Kellogg, Christopher N. Topp.

Inflorescence architecture in plants is often complex and challenging to quantify, particularly for inflorescences of cereal grasses. Methods for capturing inflorescence architecture and for analyzing the resulting data are limited to a few easily captured parameters that may miss the rich underlying diversity. Here, we apply X-ray computed tomography combined with detailed morphometrics, offering new imaging and computational tools to analyze three-dimensional inflorescence architecture. To show the power of this approach, we focus on the panicles of Sorghum bicolor, which vary extensively in numbers, lengths, and angles of primary branches, as well as the three-dimensional shape, size, and distribution of the seed.
2019
Variational Implicit Point Set Surface
ACM Transactions on Graphics (Proc. ACM Siggraph 2019), 38(4): No. 124 (Paper, Code with Reproducibility Stamp, Project)
Zhiyang Huang, Nathan Carr, Tao Ju.

We propose a new method for reconstructing an implicit surface from an un-oriented point set. While existing methods often involve non-trivial heuristics and require additional constraints, such as normals or labelled points, we introduce a direct definition of the function from the points as the solution to a constrained quadratic optimization problem. The definition has a number of appealing features: it uses a single parameter (parameter-free for exact interpolation), applies to any dimensions, commutes with similarity transformations, and can be easily implemented without discretizing the space. More importantly, the use of a global smoothness energy allows our definition to be much more resilient to sampling imperfections than existing methods, making it particularly suited for sparse and non-uniform inputs.
Long-Term Characterization of Cranial Defects After Surgical Correction for Single-Suture Craniosynostosis
Annals of Plastic Surgery, 82(6):679-685 (Paper link)
G. Skolnick, S. Murthy, K. Patel, Z. Huang, S. Naidoo, T. Ju, M. Smyth, A. Woo

We describe and make available a novel validated method of measuring cranial defects. A graphical tool was developed to detect cranial defects from segmented CT images and analyze their location, surface area, and circularity. We find that the large majority of initial defects greater than 9 cm2 remain at least 1 in2 in size (2.5 cm2) 1 year postoperatively. In addition, there appear to be regional differences in closure rates across the cranium, with frontoparietal defects closing more slowly than those in the parietal region. This information will aid surgeons in the decision-making process regarding cranioplasty after craniosynostosis correction.
2018
Voxel Cores: Efficient, robust, and provably good approximation of 3D medial axes
ACM Transactions on Graphics (Proc. ACM Siggraph 2018), 37(4): No. 44 (Paper, Supplement, Project)
Yajie Yan, David Letscher, Tao Ju.

We present a novel algorithm for computing the medial axes of 3D shapes. We make the observation that the medial axis of a voxel shape can be simply yet faithfully approximated by the interior Voronoi diagram of the boundary vertices, which we call the voxel core. We further show that voxel cores can approximate the medial axes of any smooth shape with homotopy equivalence and geometric convergence. These insights motivate an algorithm that is simple, efficient, numerically stable, and equipped with theoretical guarantees. Compared with existing voxel-based methods, our method inherits their simplicity but is more scalable and can process significantly larger inputs. Compared with sampling-based methods that offer similar theoretical guarantees, our method produces visually comparable results but more robustly captures the topology of the input shape.
Robust Optimization for Topological Surface Reconstruction
ACM Transactions on Graphics (Proc. ACM Siggraph 2018), 37(4): No. 46 (Paper)
Roee Lazar, Nadav Dym, Yam Kushinksy, Zhiyang Huang, Tao Ju, Yaron Lipman.

Surface reconstruction is one of the central problems in computer graphics. Existing research on this problem has primarily focused on improving the geometric aspects of the reconstruction (e.g., smoothness, features, element quality, etc.), and little attention has been paid to ensure it also has desired topological properties (e.g., connectedness and genus). In this paper, we propose a novel and general optimization method for surface reconstruction under topological constraints. The input to our method is a prescribed genus for the reconstructed surface, a partition of the ambient volume into cells, and a set of possible surface candidates and their associated energy within each cell. Our method computes one candidate per cell so that their union is a connected surface with the prescribed genus that minimizes the total energy. We formulate the task as an integer program, and propose a novel solution that combines convex relaxations within a branch and bound framework. As our method is oblivious of the type of input cells, surface candidates, and energy, it can be applied to a variety of reconstruction scenarios, and we explore two of them in the paper: reconstruction from cross-section slices and iso-surfacing an intensity volume. In the first scenario, our method outperforms an existing topology-aware method particularly for complex inputs and higher genus constraints. In the second scenario, we demonstrate the benefit of topology control over classical topology-oblivious methods such as Marching Cubes.
Some Heuristics for the Homological Simplification Problem
Proc. Canadian Conference on Computational Geometry (CCCG'18) (Paper, code)
Erin W. Chambers, Tao Ju, David Letscher, Mao Li, Christopher Topp, Yajie Yan

In this paper, we consider heuristic approaches for solving the homological simplification problem. While NP-Hard in general, we propose an algorithm that in practice significantly reduces topological noise from large datasets, such as those from medical or biological imaging.
Repairing Inconsistent Curve Networks on Non-parallel Cross-sections
Computer Graphics Forum (Proc. Eurographics 2018), 37(2): 25-35 (Paper, Code, Project)
Zhiyang Huang, Michelle Holloway, Nathan Carr, Tao Ju.

In this work we present the first algorithm for restoring consistency between curve networks on non-parallel cross-sections. Our method addresses a critical but overlooked challenge in the reconstruction process from cross-sections that stems from the fact that cross-sectional slices are often generated independently of one another, such as in interactive volume segmentation. As a result, the curve networks on two non-parallel slices may disagree where the slices intersect, which makes these cross- sections an invalid input for surfacing. We propose a method that takes as input an arbitrary number of non-parallel slices, each partitioned into two or more labels by a curve network, and outputs a modified set of curve networks on these slices that are guaranteed to be consistent. We formulate the task of restoring consistency while preserving the shape of input curves as a constrained optimization problem, and we propose an effective solution framework. We demonstrate our method on a data-set of complex multi-labeled input cross-sections. Our technique efficiently produces consistent curve networks even in the presence of large errors.
2017
Topology-controlled Reconstruction of Multi-labelled Domains from Cross-sections
ACM Transactions on Graphics (Proc. ACM Siggraph 2017), 36(4): No. 76 (Paper, Code, Project)
Zhiyang Huang, Ming Zou, Nathan Carr, Tao Ju.

In this work we present the first algorithm for reconstructing multi-labeled material interfaces the allows for explicit topology control. Our algorithm takes in a set of 2D cross-sectional slices (not necessarily parallel), each partitioned by a curve network into labeled regions representing different material types. For each label, the user has the option to constrain the number of connected components and genus. Our algorithm is able to not only produce a material interface that interpolates the curve networks but also simultaneously satisfy the topological requirements. Our key innovation is defining a space of topology-varying material interfaces, which extends the family of level sets in a scalar function, and developing discrete methods for sampling distinct topologies in this space. Besides specifying topological constraints, the user can steer the algorithm interactively, such as by scribbling. We demonstrate, on synthetic and biological shapes, how our algorithm opens up new opportunities for topology-aware modeling in the multi-labeled context.
FlowRep: Descriptive Curve Networks for Free-Form Design Shapes
ACM Transactions on Graphics (Proc. ACM Siggraph 2017), 36(4): No. 59 (Paper)
Giorgio Gori, Alla Sheffer, Nicholas Vining, Enrique Rosales, Nathan Carr, Tao Ju.

We present FlowRep, an algorithm for extracting descriptive compact 3D curve networks from meshes of free-form man-made shapes. We infer the desired compact curve network from complex 3D geometries by using a series of insights derived from perception, computer graphics, and design literature. These sources suggest that visually descriptive networks are cycle-descriptive, i.e their cycles unambiguously describe the geometry of the surface patches they surround. They also indicate that such networks are designed to be projectable, or easy to envision when observed from a static general viewpoint; in other words, 2D projections of the network should be strongly indicative of its 3D geometry. Research suggests that both properties are best achieved by using networks dominated by flowlines, surface curves aligned with principal curvature directions across anisotropic regions and strategically extended across sharp-features and isotropic areas. Our algorithm leverages these observation in the construction of a compact descriptive curve network. We validate our method by demonstrating a range of networks computed from diverse inputs, using them for surface reconstruction, and showing extensive comparisons with prior work and artist generated networks.
Extracting Sharp Features from RGB-D Images
Computer Graphics Forum, 36(8): 138-152 (Paper)
Yanpei Cao, Tao Ju, J. Xu, Shimin Hu.

Sharp edges are important shape features and their extraction has been extensively studied both on point clouds and surfaces. We consider the problem of extracting sharp edges from a sparse set of color-and-depth (RGB-D) images. The noise-ridden depth measurements are challenging for existing feature extraction methods that work solely in the geometric domain (e.g., points or meshes). By utilizing both color and depth information, we propose a novel feature extraction method that produces much cleaner and more coherent feature lines. We make two technical contributions. First, we show that intensity edges can augment the depth map to improve normal estimation and feature localization from a single RGB-D image. Second, we designed a novel algorithm for consolidating feature points obtained from multiple RGB-D images. By utilizing normals and ridge/valley types associated with the feature points, our algorithm is effective in suppressing noise without smearing nearby features.
Feature-aligned segmentation using correlation clustering
Computational Visual Media, 3(2): 147-160. (Paper, Project)
Yixin Zhuang, Hang Dou, Nathan Carr, Tao Ju.

We present an algorithm for segmenting a mesh into patches whose boundaries are aligned with prominent ridge and valley lines of the shape. Our key insight is that this problem can be formulated as Correlation Clustering (CC), a graph partitioning problem originated from the data mining community. The formulation lends two unique advantages to our method over existing segmentation methods. First, since CC is non-parametric, our method requires few parameters to tune. Second, as CC is governed by edge weights in the graph, our method offers users direct and local control over the segmentation result. Our technical contributions include the construction of the weighted graph on which CC is defined, a speed-up strategy for computing CC on this graph, and an interactive tool for editing the segmentation. Our experiments showed that our method produces qualitatively better segmentations than existing methods on a wide range of inputs.
Flexible Fitting of Atomic Models into Cryo-EM Density Maps Guided by Helix Correspondences
Biophysical Journal, 112: 2479-2493 (Paper, Supplement)
Hang Dou, Derek Burrows, Matthew Baker, Tao Ju.

Although electron cryo-microscopy (cryo-EM) has recently achieved resolutions of better than 3A, at which point molecular modeling can be done directly from the density map, analysis and annotation of a cryo-EM density map still primarily rely on fitting atomic or homology models to the density map. In this article, we present, to our knowledge, a new method for flexible fitting of known or modeled protein structures into cryo-EM density maps. Unlike existing methods that are guided by local density gradients, our method is guided by correspondences between the a-helices in the density map and model, and does not require an initial rigid-body fitting step. Compared with current methods on both simulated and experimental density maps, our method not only achieves greater accuracy for proteins with large deformations but also runs as fast or faster than many of the other flexible fitting routines.
2016
Erosion Thickness on Medial Axes of 3D Shapes
ACM Transactions on Graphics (Proc. ACM Siggraph 2016), 35(4): Article No. 38 (Paper, Supplement, Project)
Yajie Yan, Kyle Sykes, Erin Chambers, David Letscher, Tao Ju.

While playing a fundamental role in shape understanding, the medial axis is known to be sensitive to small boundary perturbations. Methods for pruning the medial axis are usually guided by some measure of significance. The majority of significance measures over the medial axes of 3D shapes are locally defined and hence unable to capture the scale of features. We introduce a global significance measure that generalizes in 3D the classical Erosion Thickness (ET) measure over the medial axes of 2D shapes. We give precise definition of ET in 3D, analyze its properties, and present an efficient approximation algorithm with bounded error on a piece-wise linear medial axis. Experiments showed that ET outperforms local measures in differentiating small boundary noise from prominent shape features, and it is significantly faster to compute than existing global measures. We demonstrate the utility of ET in extracting clean, shape-revealing and topology-preserving skeletons of 3D shapes.
Extrinsically Smooth Direction Fields
Computer & Graphics (Proc. SMI 2016), 58: 109-117 (Paper, Code&data with Reproducibility Stamp, Project)
Zhiyang Huang, Tao Ju.

We consider the problem of finding a unit vector field (i.e., a direction field) over a domain that balances two competing objectives, smoothness and conformity to the shape of the domain. Common examples of this problem are finding normal directions along a curve and tangent directions over a surface. In a recent work, Jakob et al. observed that minimizing \emph{extrinsic variation} of a tangent direction field on a surface achieves both objectives without the need for parameter-tuning or the use of additional constraints. Inspired by their empirical observations, we analyze the relation between extrinsic smoothness, intrinsic smoothness, and shape conformity in a continuous and general setting. Our analysis not only explains their observations but also suggest that an extrinsically smooth normal field along a curve can strike a similar balance between smoothness and shape-awareness. Our second contribution is offering extension of, justification for and improvement over the optimization framework of Jakob et al. In our experiments, we demonstrate the suitability of extrinsically smooth field in a variety of applications and compared with existing solutions.
Template-based Surface Reconstruction from Cross-sections
Computer & Graphics (Proc. SMI 2016), 58: 84-91 (Paper)
Michelle Holloway, Cindy Grimm, Tao Ju.

In this work we explore a new approach to solving the problem of surface reconstruction from cross-section curves. Existing reconstruction methods focus on producing smooth interpolations and may require a large number of cross-sections to recreate feature-rich objects. In the context of medical image segmentation, we make the observation that anatomical structures usually share a common overall shape across subjects. This observation motivates taking a template-based approach that can better capture geometric features, instead of solving for the surface from the cross-sectional curves alone. We deform an existing template, whose shape represents the structure of interest, to fit a set of target curves. We describe our algorithm with the main focus on finding a correspondence between a mesh and a cross-section curve network. We show our results with real medical data and compare to current reconstruction methods.
2015
Topology-Constrained Surface Reconstruction From Cross-sections
ACM Transactions on Graphics (Proc. ACM Siggraph 2015), 34(4): Article No. 128 (Paper, Project)
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 (Paper)
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 (Paper link)
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.
2014
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 (Paper, Slides)
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 (Paper)
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 (Paper)
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) (Paper)
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 (Pubmed link)
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.
2013
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. (Paper, Project)
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. (Paper, Project)
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. (Paper, Project)
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. (Paper)
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. (Paper link)
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.
2012
Region-based Line Field Design Using Harmonic Functions
IEEE Transactions on Visualization and Computer Graphics, 18(6):902-913. (Paper, Supplementary material, Video)
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) (Paper)
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
Biopolymers, 97(9):655-668 (Paper link)
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.
2011
Extended Grassfire Transform on Medial Axes of 2D Shapes
Computer Aided Design (Proceedings of SPM 2011), 43(11):1496-1505 (Paper, Slides (168MB), 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 (Paper)
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.
A Geometric Study of V-style Pop-ups: Theories and Algorithms
ACM Transactions on Graphics (Proceedings of Siggraph 2011), 30(4), article 98. (Paper, Video, Project)
X-Y. Li, T. Ju, Y. Gu, S-M. Hu

Pop-up books are a fascinating form of paper art with intriguing geometric properties. In this paper, we present a systematic study of a simple but common class of pop-ups consisting of patches falling into four parallel groups, which we call v-style pop-ups. We give sufficient conditions for a v-style paper structure to be pop-uppable. That is, it can be closed flat while maintaining the rigidity of the patches, the closing and opening do not need extra force besides holding two patches and are free of intersections, and the closed paper is contained within the page border. These conditions allow us to identify novel mechanisms for making pop-ups. Based on the theory and mechanisms, we developed an interactive tool for designing v-style pop-ups and an automated construction algorithm from a given geometry, both of which guaranteeing the popuppability of the results.
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 (Paper)
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, Project)
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 (Paper)
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 (Paper Link)
Paul Commean, Jared Kennedy, Karen Bahow, Charles Hildebolt, Lu Liu, Kirk Smith, Mary Hastings, Tao Ju, Fred Prior, David Sinacore

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.
2010
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 (Paper)
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 (Paper)
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 (Paper)
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 (Paper)
P. Feng, T. Ju, J. Warren

The ability to model objects composed of multiple materials has become increasingly more demanded in scientific applications. 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 more materials.
Subdivision meshes for organizing spatial biomedical data
Method, 50(2):70-76 (Paper)
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
Method, 50(2):85-95 (Paper)
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.
2009
Feature-Aligned Shape Texturing
ACM Transactions on Graphics (Proceedings of Siggraph Asia 2009), 28(5): article 108 (Paper, Project)
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 (Paper)
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 sketching
Computer Animation And Virtual Worlds (Proceedings of CASA'09), 23(2-3):101-109 (Paper, Video)
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 morphing.
VolumeViewer: An Interactive Tool for Fitting Surfaces to Volume Data
Sixth Eurographics Workshop on Sketch Based Interfaces and Modeling, 141-148 (Paper, Video, Project)
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 (Paper)
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 (Paper)
T. Ju

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.

2008
Reusable Skinning Templates Using Cage-based Deformations
ACM Transactions on Graphics (Proceedings of Siggraph Asia 2008), 27(5):1-10 (Paper, Video)
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 (Paper, Poster)
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 (Paper)
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 (Paper, Project)
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 (Paper)
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 user intervention.
Tarsal and Metatarsal Bone Mineral Density Measurement using Volumetric Quantitative Computed Tomography.
Journal of Digital Imaging, 22(5): 492-502 (Paper)
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.
2007
Editing The Topology of 3D Models by Sketching.
ACM Transactions on Graphics (Proceedings of SIGGRAPH 2007), 26(3): 42 (Paper, Video (33MB), Project)
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 (Paper)
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 low-resolution images.
ACM Symposium on Solid and Physical Modeling 2007 (Paper,Talk)
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 Images Containing 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, Project)
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 high resolutions.
A general geometric construction of coordinates in a convex simplicial polytope
Computer Aided Geometric Design, 24(3): 161-178 (Paper, Talk)
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 simplification.
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.
2006
A Unified, Integral Construction For Coordinates Over Closed Curves
Computer-Aided Geometric Design, 24(8-9):481-493 (Paper)
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 coordinates.
Probing 3'-ssDNA Loop Formation in E. coli RecBCD/RecBC-DNA Complexes using Non-natural DNA: A Model for "Chi" Recognition Complexes
Journal of Molecular Biology, 362(1):26-43 (Paper)
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 (Paper,Talk)
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 Filtering
Journal of Neuroscience Methods, 156(1-2):84-100 (Paper,Program)
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.
2005
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, (Paper)
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 (Paper)
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 (Paper)
M. Bello, T. Ju, J. Warren, J. Carson, W. Chiu, C. Thaller, G. Eichele and I. Kakadiaris

In 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 images.
Geometric Construction of Coordinates for Convex Polyhedra using Polar Duals
Proceedings of Eurographics Symposium on Geometry Processing, p181-186, 2005 (Paper)
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 (Paper)
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.


2004
Robust Repair of Polygonal Models
Proceedings of ACM SIGGRAPH, 2004
ACM Transactions on Graphics, 23(3):888-895 (Paper, Slides, Program)
Tao Ju

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 (Paper)
Ioannis A. 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 programming.
Recursive Turtle Programs and Iterated Affine Transformations
Computer and Graphics, 28(6): 991-1004, 2004. (Paper)
Tao Ju, 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.
2003
A geometry database for gene expression data
Proceedings of Eurographics Symposium on Geomtry Processing, 2003. (Paper, Slides)
Tao Ju, 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 at www.geneatlas.org.
Morphing of rational b-spline curves and surfaces using mass distributions
Proceedings of Eurographics, short papers, 2003. (Paper, Slides)
Tao 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. (Paper, Slides)
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.
2002
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 octrees.
2001
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.

Comments or suggestions: taoju at cs.wustl.edu