skip to main content
US FlagAn official website of the United States government
dot gov icon
Official websites use .gov
A .gov website belongs to an official government organization in the United States.
https lock icon
Secure .gov websites use HTTPS
A lock ( lock ) or https:// means you've safely connected to the .gov website. Share sensitive information only on official, secure websites.


Title: Elastic Shape Analysis of Tree-Like 3D Objects Using Extended SRVF Representation
How can one analyze detailed 3D biological objects, such as neuronal and botanical trees, that exhibit complex geometrical and topological variation? In this paper, we develop a novel mathematical framework for representing, comparing, and computing geodesic deformations between the shapes of such tree-like 3D objects. A hierarchical organization of subtrees characterizes these objects - each subtree has a main branch with some side branches attached - and one needs to match these structures across objects for meaningful comparisons. We propose a novel representation that extends the Square-Root Velocity Function (SRVF), initially developed for Euclidean curves, to tree-shaped 3D objects. We then define a new metric that quantifies the bending, stretching, and branch sliding needed to deform one tree-shaped object into the other. Compared to the current metrics such as the Quotient Euclidean Distance (QED) and the Tree Edit Distance (TED), the proposed representation and metric capture the full elasticity of the branches (i.e., bending and stretching) as well as the topological variations (i.e., branch death/birth and sliding). It completely avoids the shrinkage that results from the edge collapse and node split operations of the QED and TED metrics. We demonstrate the utility of this framework in comparing, matching, and computing geodesics between biological objects such as neuronal and botanical trees. We also demonstrate its application to various shape analysis tasks such as (i) symmetry analysis and symmetrization of tree-shaped 3D objects, (ii) computing summary statistics (means and modes of variations) of populations of tree-shaped 3D objects, (iii) fitting parametric probability distributions to such populations, and (iv) finally synthesizing novel tree-shaped 3D objects through random sampling from estimated probability distributions.  more » « less
Award ID(s):
1953087
PAR ID:
10557169
Author(s) / Creator(s):
; ;
Publisher / Repository:
IEEE Transactions on Pattern Analysis and Machine Intelligence
Date Published:
Journal Name:
IEEE Transactions on Pattern Analysis and Machine Intelligence
Volume:
46
Issue:
4
ISSN:
0162-8828
Page Range / eLocation ID:
2475 to 2488
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. We introduce a novel method for reconstructing the 3D geometry of botanical trees from single photographs. Faithfully reconstructing a tree from single-view sensor data is a challenging and open problem because many possible 3D trees exist that fit the tree's shape observed from a single view. We address this challenge by defining a reconstruction pipeline based on three neural networks. The networks simultaneously mask out trees in input photographs, identify a tree's species, and obtain its 3D radial bounding volume - our novel 3D representation for botanical trees. Radial bounding volumes (RBV) are used to orchestrate a procedural model primed on learned parameters to grow a tree that matches the main branching structure and the overall shape of the captured tree. While the RBV allows us to faithfully reconstruct the main branching structure, we use the procedural model's morphological constraints to generate realistic branching for the tree crown. This constraints the number of solutions of tree models for a given photograph of a tree. We show that our method reconstructs various tree species even when the trees are captured in front of complex backgrounds. Moreover, although our neural networks have been trained on synthetic data with data augmentation, we show that our pipeline performs well for real tree photographs. We evaluate the reconstructed geometries with several metrics, including leaf area index and maximum radial tree distances. 
    more » « less
  2. null (Ed.)
    The voting patterns of the nine justices on the United States Supreme Court continue to fascinate and perplex observers of the Court. While it is commonly understood that the division of the justices into a liberal branch and a conservative branch inevitably drives many case outcomes, there are finer, less transparent divisions within these two main branches that have proven difficult to extract empirically. This study imports methods from evolutionary biology to help illuminate the intricate and often overlooked branching structure of the justices’ voting behavior. Specifically, phylogenetic tree estimation based on voting disagreement rates is used to extend ideal point estimation to the non-Euclidean setting of hyperbolic metrics. After introducing this framework, comparing it to one- and two-dimensional multidimensional scaling, and arguing that it flexibly captures important higher-dimensional voting behavior, a handful of potential ways to apply this tool are presented. The emphasis throughout is on interpreting these judicial trees and extracting qualitative insights from them. 
    more » « less
  3. A quasiconformal tree T is a (compact) metric tree that is doubling and of bounded turning. We call T trivalent if every branch point of T has exactly three branches. If the set of branch points is uniformly relatively separated and uniformly relatively dense, we say that T is uniformly branching. We prove that a metric space T is quasisymmetrically equivalent to the continuum self-similar tree if and only if it is a trivalent quasiconformal tree that is uniformly branching. In particular, any two trees of this type are quasisymmetrically equivalent. 
    more » « less
  4. Summary Rooted and ranked phylogenetic trees are mathematical objects that are useful in modelling hierarchical data and evolutionary relationships with applications to many fields such as evolutionary biology and genetic epidemiology. Bayesian phylogenetic inference usually explores the posterior distribution of trees via Markov chain Monte Carlo methods. However, assessing uncertainty and summarizing distributions remains challenging for these types of structures. While labelled phylogenetic trees have been extensively studied, relatively less literature exists for unlabelled trees that are increasingly useful, for example when one seeks to summarize samples of trees obtained with different methods, or from different samples and environments, and wishes to assess the stability and generalizability of these summaries. In our paper, we exploit recently proposed distance metrics of unlabelled ranked binary trees and unlabelled ranked genealogies, or trees equipped with branch lengths, to define the Fréchet mean, variance and interquartile sets as summaries of these tree distributions. We provide an efficient combinatorial optimization algorithm for computing the Fréchet mean of a sample or of distributions on unlabelled ranked tree shapes and unlabelled ranked genealogies. We show the applicability of our summary statistics for studying popular tree distributions and for comparing the SARS-CoV-2 evolutionary trees across different locations during the COVID-19 epidemic in 2020. Our current implementations are publicly available at https://github.com/RSamyak/fmatrix. 
    more » « less
  5. Abstract Dwarf mistletoes (Arceuthobiumspecies) are arboreal, hemiparasitic plants of conifers that can change the structure and function of the tree crown. Hemlock dwarf mistletoe (Arceuthobium tsugensesubsp.tsugense)principally parasitizes western hemlock (Tsuga heterophylla) and effects 10.8% of all western hemlock trees in Oregon, USA. In this study, we climbed 16 western hemlock trees (age 97–321 years, height 33–54.7 m) across a gradient of infection (0%–100% of branches infected) and measured occurrence of all dwarf mistletoe infections, dwarf mistletoe caused deformities, foliage, branch and crown metrics, and sapwood area. We then modelled over 25 different response variables using linear and generalized linear models with three metrics of severity as explanatory variables: total infection incidence, proportion of all live branches infected, and proportion of all live, infected branches with 33 per cent or more foliage distal to infection. A strong effect of dwarf mistletoe intensification was the reduction of branch foliage and an increase in the proportional amount of foliage distal to infections, with severely infected trees having the majority of foliage distal to infections. Increasing severity led to an apparent crown compaction as crown volumes decreased and became increasingly comprised of deformities. Sapwood area was unrelated to infection severity. Branch length and diameters were unrelated to increasing infection severity despite severely infected branches supporting 1–70 infections. The most severely infected tree had 3,615 individual plants in the crown. Our results suggested that shifts in crown structure and branch deformation, foliage amount, and foliage distal to infection, reflected a likely reduction of capacity for tree growth that coincided with a hypothesized increase in resource demand by dwarf mistletoe plants as infection severity intensified. 
    more » « less