Skeletonization

Plants, tubes and curves

Sources

• [2007] Knowledge and Heuristic-Based Modeling of Laser-Scanned Trees: https://dl.acm.org/doi/pdf/10.1145/1289603.1289610
• [2008] Laplacian Contraction: https://www.cs.tau.ac.il/~dcor/articles/2008/Skeleton-Extraction.pdf
• [2010a] Automatic Reconstruction of Tree Skeletal Structures from Point Clouds: https://dl.acm.org/doi/pdf/10.1145/1866158.1866177
• [2010b] Point Cloud Skeletons via Laplacian-Based Contraction: https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=5521461
• [2014] DMset Distance Minimum Spanning Trees: https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=6693725&tag=1
• Read but not used [2014] A practical introduction to skeletons for the plant sciences: https://pubmed.ncbi.nlm.nih.gov/25202645/
• [2015] Deep Points Consolidation: https://dl.acm.org/doi/pdf/10.1145/2816795.2818073
• [2016] Local Structure and Direction-Aware Optimization Approach for 3D Tree Modeling: https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=7460948
• [2019] AdTree: Accurate, Detailed, and Automatic Modelling of Laser-Scanned Trees: https://3d.bk.tudelft.nl/liangliang/publications/2019/adtree/AdTree_RS-2019.pdf
• [2020] Skeletonization of Plant Point Cloud Data Using Stochastic Optimization: https://www.frontiersin.org/articles/10.3389/fpls.2020.00773/full
• [2021] Point2Skeleton: Learning Skeletal Representations from Point Clouds: https://openaccess.thecvf.com/content/CVPR2021/papers/Lin_Point2Skeleton_Learning_Skeletal_Representations_from_Point_Clouds_CVPR_2021_paper.pdf

What is a skeleton?

• “The curve skeleton of a 3D model is a 1D representation that intuitively captures the model’s topological characteristics” [2010b]
• “A natural approach to tree construction is to first reconstruct the skeleton… , then apply further geometric completion through appropriate rules” [2010a]
• “The common approach to obtain tree branch geometry is cylinder fitting” [2019]
• “Ideally, the skeleton should follow the exact centerline of the object” [2020]
• Meso-skeletons consist of “skeletal curves in cylindrical regions and skeletal sheets (i.e. medial axes) elsewhere” [2015]
• “The curve skeleton… is only empirically understood for tubular objects… skeletal mesh is an important extension to the curve skeleton.”[2021]

​

Who cares?

• Connecting occluded fragments of plants
• Modelling tree dynamics
• Forest scanning from drones
• Path Planning?
• Perhaps useful for traversability?
• Plant Sampling?
• Maybe having a skeleton of a plant could help determine the proper snipping place for a leaf sample
• Vine pruning

[2008 / 2010] Laplacian Contraction paper paper

1. Set curvature to zero, approximate stepping inwards along the surface normal
2. Contraction is fought against with an attraction force scaled “by its local one-ring area” so thinner things get more locked in place

You’re left with a collapsed pile of edges which become the skeleton.

[2008 / 2010] Laplacian Contraction paper paper

Updated to handle “point cloud models, meshes with boundaries, triangle soup inputs without global connectivity”.

Basically the same process but for each point you

1. Get k nearest neighbors
2. Calculate their PCA and use the smallest component to get the “in-plane” version of the neighbors
3. Do Delaunay triangulation
4. Use the one-ring points as “mesh neighbors”

Laplacian Contraction

Laplacian Contraction in Action

Exact

Plausible

Fill In Unknowns

Represent What’s There

Laplacian Contraction (mesh / points)

[2007] Xu et al. paper

Step one - get connected components

[2007] Xu et al. paper

Step two - skeletonize the root connected component.

[2007] Xu et al. paper

Step three - add in smaller connected components…

[2007] Xu et al. paper

Step three - add in smaller connected components up to a threshold

[2007] Xu et al. paper

Structure is copied to cover the leaf groups

[2007] Xu et al. paper

Results - plausible, first couple of big splits seem right, hard to evaluate after that.

Exact

Plausible

Fill In Unknowns

Represent What’s There

Laplacian Contraction (mesh / points)

Xu et al

(points)

[2010] Livny et al. paper

Initial assumptions, worth repeating because they may be useful.

1. The branch chains (subgraph) are smooth, as reflected by small bending angles between adjacent edges
2. The branch chains are longer and thicker near the root of the tree and shorter and thinner near the crown
3. The density of the branch chains is inversely proportional to their corresponding thickness

[2010] Livny et al. paper

Point cloud with all scanned points

Make a tree with Djikstra’s Algorithm

Weight parts with downstream length

Get point orientation based on child/parent

Strongly weighted parts pull others in

[2010] Livny et al. paper

Then there’s an iteration component where that smoothed tree is used with the original point clouds to make a better starter tree.

[2010] Livny et al. paper

Compares against what we just saw (Xu et al).

Exact

Plausible

Fill In Unknowns

Represent What’s There

Laplacian Contraction (mesh / points)

Livny et al

(points)

Xu et al

(points)

Livny et al

(points)

“While it is able to properly connect branches that are otherwise disconnected in the data due to small-scale occlusions, it is not designed to reconstruct or synthesize skeletal structure over large regions of missing data.”

[2016] Wang et al. paper

Thus far we haven’t really seen any reconstruction of missing areas, other than minimum spanning tree “space jumping”

[2016] Wang et al. paper

1. Initialize with a DMst tree, similar to what we’ve seen before
2. The points and the skeleton are drawn together. Based on branch direction along the tree and the density in a given spot points are diffused into open areas
3. There is something interesting with a local histogram of angles to encourage self-similarity, but it is unclear how that it used

[2016] Wang et al. paper

“Grow” into open areas based on branch direction

Make some sort of histogram of local angles and then do something with it

[2016] Wang et al. paper

Looks pretty good, but is hard to judge other than just “plausible”. Some big stuff appears to be there. Quantitative results are against their paper two years before.

Exact

Plausible

Fill In Unknowns

Represent What’s There

Laplacian Contraction (mesh / points)

Livny et al

(points)

Wang et al

(points)

Xu et al

(points)

Livny et al

(points)

Wang et al

(points)

[2019] AdTree paper

Simple minimum spanning trees can struggle with scattered points and not trace the centers of areas, so main branch point centralization (mean shift) is used before making the initial spanning tree. Mean shift is “a simple iterative procedure that shifts each data point to the average of data points in its neighborhood”.

Note this whole “make an initial okay spanning tree and then iterate on it” is very common

Bad

Good

[2019] AdTree paper

From that mean-shifted spanning tree they simplify matters heuristically.

The same trick from before is used where the weights come from the size of the sub-tree, removing barbed wire.

[2019] AdTree paper

Estimate trunk size, then at some point (unclear) use allometric guesses.

Idea for John - use allometric information to guide your probabilities?

[2019] AdTree paper

Compares against what we saw earlier (Livny et al), does seem a little better qualitatively.

[2019] AdTree paper

I didn’t love their quantitative metric of “the mean distance between the input points and the generated tree branch model”. It seems like an okay indicator variable, and they don’t use it to compare against other methods, but like an overfit polynomial it seems to reward point coverage, not branch correctness.

Exact

Plausible

Fill In Unknowns

Represent What’s There

Laplacian Contraction (mesh / points)

Wang et al

(points)

Xu et al

(points)

Livny et al

(points)

Wang et al

(points)

“As long as the input point clouds demonstrate clear branch structure, our method is capable of generating tree models of high quality.”

[2020] Chaudhury et al. paper

The problems that they identified were:

• Zigzagging: skeleton points usually deviate from the center towards junctions
• Inaccuracy: skeleton points get pulled outside the boundary
• Tiny things are sometimes missed

[2020] Chaudhury et al. paper

First, they start off by using the 2007 Xu et al. paper we looked at to make a starter tree! Then they do a nice clean job of describing how that initial skeleton is fit using Beta splines and broken up in axial trees/quotient graphs like so.

[2020] Chaudhury et al. paper

Characterized by tension (t) and skew (s) parameters.

[2020] Chaudhury et al. paper

Once you have curves and a point-cloud they go through quite an intricate locally informed minimization. I didn’t fully go through it, but in essence they were pushing and pulling the splines based on the original point cloud and the likelihood of the spline being in a certain area.

It was made more complicated with PCA-based weighting and membership probability of points to certain curves.

[2020] Chaudhury et al. paper

Interesting quantitative metric!

“We have generated ground truth of junction points of the branches (branching point) for 3 cases: synthetic data, Arabidopsis plant data, and Cherry tree data.”

Then they compared the ground truth junction locations and branch lengths between methods and did better than Xu et al. and space colonization.

[2020] Chaudhury et al. paper

Precision really seems like the name of the game here, and high-quality data seems required.

[2020] Chaudhury et al. paper.

Exact

Plausible

Fill In Unknowns

Represent What’s There

Laplacian Contraction (mesh / points)

Xu et al

(points)

Livny et al

(points)

Chaudhury et al

(precise points)

Wang et al

(points)

[2015] Deep Points (no learning involved…) paper

Just go to their website, it’s great

Interesting quote:

“Missing data, caused by self-occlusion, light absorption, or challenging surface materials is one of the most challenging problems in surface reconstruction. Diffusion based methods are able to fill small holes with complex boundaries. To fill large holes, context-based, and repetition-based methods are proposed, with the assumption that the missing parts can be replaced with other parts of the input itself.”

Quantitatively evaluated against synthetically scanned objects.

Exact

Plausible

Fill In Unknowns

Represent What’s There

Laplacian Contraction (mesh / points)

Xu et al

(points)

Livny et al

(points)

Chaudhury et al

(precise points)

Wang et al

(points)

[2021] Point2Skeleton paper

There’s an interesting case against all the skeletons we’ve seen so far, introducing skeletal meshes.

“We observe that the medial axis transform (MAT), one of the best known examples of skeletal representation, has a rigorous mathematical definition for arbitrary shapes, unlike the curve skeleton which is only empirically understood for tubular objects.”

MAT is too noisy, but it is expressed as a series of sheets (for general 3D blobs) and 1D lines (for cylinders only). That’s how skeletal meshes end up as well.

Of course, plants are often tubes.

[2021] Point2Skeleton paper

[2021] Point2Skeleton paper

[2021] Point2Skeleton paper

Step one - Calculate unconnected skeletal mesh points. Sort of complicated, three separate losses are used in combination, and ablation shows they all have use. Note that everything is unsupervised!

• Sampled points on the spheres should be near input points
• All inputs points should be on a sphere surface
• Spheres should be as large as possible (limited by convex combination)

Note that the radius is a key part of the skeletal mesh, though it isn’t always visualized

[2021] Point2Skeleton paper

Step two: produce predicted links. Initialization:

• A node is connected to its closest neighbor, and definitely not to k furthest
• For each input point the two closest skeletal points are connected

Train GAE to reproduce known graph, the rest comes automatically.

[2021] Point2Skeleton paper

Step three: very carefully use the raw GAE output to make a final graph. That means only filling holes and checking boundaries.

[2021] Point2Skeleton paper

Quantitative metrics: “Unfortunately, there are no existing metrics to evaluate if a skeletonization is reasonable, since the skeleton is a form of shape abstraction involving higher-level perceptions.”

They do end up comparing against a manually simplified medial axis filter, which is known to be subject to noise but generally captures the idea of a skeleton repeatably.

​

[2021] Point2Skeleton paper

Quantitatively they beat DPoints on their metrics, here’s a qualitative view:

Exact

Plausible

Fill In Unknowns

Represent What’s There

Laplacian Contraction (mesh / points)

Xu et al

(points)

Livny et al

(points)

Chaudhury et al

(precise points)

Wang et al

(points)

Conclusions

Exact

Plausible

Fill In Unknowns

Represent What’s There

Laplacian Contraction (mesh / points)

Xu et al

(points)

Livny et al

(points)

Chaudhury et al

(precise points)

Wang et al

(points)

How necessary is deep learning and how much can be done without it?

​

Point2Skeleton does seem like a strong choice for arbitrary extraction of skeletal meshes, but simpler graph-based methods on tubular objects seem perfectly fine. P2S assumes a single object! It doesn’t handle joining occluded skeleton sections.

Conclusions

Exact

Plausible

Fill In Unknowns

Represent What’s There

Laplacian Contraction (mesh / points)

Xu et al

(points)

Livny et al

(points)

Chaudhury et al

(precise points)

Wang et al

(points)

What is done for gap filling?

​

DPoints is the best I’ve seen for gap-filling at this point, or the stuff in Wang et al. about moving points along branch directions. Not much appears to have been done with this for plants, I didn’t see anything sophisticated about evaluating possible connection points. P2S doesn’t handle this.

Conclusions

Exact

Plausible

Fill In Unknowns

Represent What’s There

Laplacian Contraction (mesh / points)

Xu et al

(points)

Livny et al

(points)

Chaudhury et al

(precise points)

Wang et al

(points)

Are there related vine papers?

​

It looks like there may be 1 or 2 old papers about vine skeletonization that I missed but they seem fairly basic, I should check them out but I doubt it’ll be a radical change.

Conclusions

Exact

Plausible

Fill In Unknowns

Represent What’s There

Laplacian Contraction (mesh / points)

Xu et al

(points)

Livny et al

(points)

Chaudhury et al

(precise points)

Wang et al

(points)

Connected components with points, closest connection within a given angle range

1) Code available

2) Interesting complicated local shape weighting

1) Code available

2) Interesting graph connectivity approach

It’s an available tool

Did a pretty good job removing barbed wire and skeleton wiggle