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.
3D imaging, such as X-ray CT and MRI, has been widely deployed to study plant root structures. Many computational tools exist to extract coarse-grained features from 3D root images, such as total ...volume, root number and total root length. However, methods that can accurately and efficiently compute fine-grained root traits, such as root number and geometry at each hierarchy level, are still lacking. These traits would allow biologists to gain deeper insights into the root system architecture.
We present TopoRoot, 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. TopoRoot runs within a few minutes on a desktop workstation for images at the resolution range of 400^3, with minimal need for human intervention in the form of setting three intensity thresholds per image.
TopoRoot improves the state-of-the-art methods in obtaining more accurate and comprehensive fine-grained traits of maize roots from 3D imaging. The automation and efficiency make TopoRoot suitable for batch processing on large numbers of root images. Our method is thus useful for phenomic studies aimed at finding the genetic basis behind root system architecture and the subsequent development of more productive crops.
Voxel cores Yan, Yajie; Letscher, David; Ju, Tao
ACM transactions on graphics,
08/2018, Letnik:
37, Številka:
4
Journal Article
Recenzirano
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.
To cut or to fill Zeng, Dan; Chambers, Erin; Letscher, David ...
ACM transactions on graphics,
11/2020, Letnik:
39, Številka:
6
Journal Article
Recenzirano
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.
We formalize a notion of topological simplification within the framework of a filtration, which is the history of a growing complex. We classify a topological change that happens during growth as ...either a feature or noise depending on its lifetime or persistence within the filtration. We give fast algorithms for computing persistence and experimental evidence for their speed and utility. PUBLICATION ABSTRACT
In this paper techniques from persistent homology are generalized to homotopy groups and to algebraic invariants from knot theory. We define the persistent Alexander module, which can be used to ...detect knotting in a complex and determine when the knotting changes when viewed from different scales. Algorithms that use the persistent Alexander module are also presented and applied to examples including protein structures. While the basic definition of persistent homotopy is known, this is the first work to use it successfully for computations.
Cellular metabolism is most often described and interpreted in terms of the biochemical reactions that make up the metabolic network. Genomics is providing near complete information regarding the ...genes/gene products participating in cellular metabolism for a growing number of organisms. As the true functional units of metabolic systems are its pathways, the time has arrived to define metabolic pathways in the context of whole-cell metabolism for the analysis of the structural design and capabilities of the metabolic network. In this study, we present the theoretical foundations for the identification of the unique set of systemically independent biochemical pathways, termed extreme pathways, based on system stochiometry and limited thermodynamics. These pathways represent the edges of the steady-state flux cone derived from convex analysis, and they can be used to represent any flux distribution achievable by the metabolic network. An algorithm is presented to determine the set of extreme pathways for a system of any complexity and a classification scheme is introduced for the characterization of these pathways. The property of systemic independence is discussed along with its implications for issues related to metabolic regulation and the evolution of cellular metabolic networks. The underlying pathway structure that is determined from the set of extreme pathways now provides us with the ability to analyse, interpret, and perhaps predict metabolic function from a pathway-based perspective in addition to the traditional reaction-based perspective. The algorithm and classification scheme developed can be used to describe the pathway structure in annotated genomes to explore the capabilities of an organism.
Every fall, millions of Americans enter betting pools to pick winners of the weekly NFL football games. In the spring, NCAA tournament basketball pools are even more popular. In both cases, teams ...that are popularly perceived as "favorites" gain a disproportionate share of entries. In large pools there can be a significant advantage to picking upsets that differentiate your picks from the crowd.
In this paper, we present a model of betting pools that incorporates pool participant behavior. We use the model to derive strategies that maximize the expected return on a bet in both football pools and tournament-style pools. These strategies significantly outperform strategies based on maximizing score or number of correct picks—often by orders of magnitude.
Extended grassfire transform on medial axes of 2D shapes Liu, Lu; Chambers, Erin W.; Letscher, David ...
Computer Aided Design/Computer-aided design,
November 2011, 2011-11-00, 20111101, Letnik:
43, Številka:
11
Journal Article
Recenzirano
Odprti dostop
The medial axis is an important shape descriptor first introduced by Blum (1967) 1 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.
This paper presents a new hybrid split-and-merge image segmentation method based on computational geometry and topology using persistent homology. The algorithm uses edge-directed topology to ...initially split the image into a set of regions based on the Delaunay triangulations of the points in the edge map. Persistent homology is used to generate three types of regions: p-persistent regions, p-transient regions, and d-triangles. The p-persistent regions correspond to core objects in the image, while p-transient regions and d-triangles are smaller regions that may be combined in the merge phase, either with p-persistent regions to refine the core or with other p-transient and d-triangles regions to potentially form new core objects. Performing image segmentation based on topology and persistent homology guarantees several nice properties, and initial results demonstrate high quality image segmentation.
PDF
