jakteristics
jakteristics copied to clipboard
jakarto3d
geodesic graph distance
Geodesic Graph Distance
Why?
'Classic' (Euclidean distance) neighborhood search in point clouds has some downsides when it comes to structures that are thin in one dimension and close in proximity to the neighborhood radius (e.g., small twigs in a lidar scan of a tree). When computing geometric features using such a classic neighborhood approach, it is possible for adjacent twigs to interfere with each other in a way that the geometric features do not accurately represent an individual twig.
What?
The method to prevent that was well visualized here:
Fig. 4 from the paper: Jiang, Anling, et al. "Skeleton extraction from point clouds of trees with complex branches via graph contraction." The Visual Computer 37 (2021): 2235-2251.
and is also implemented in PyVista for single paths and meshes:
Image from: https://docs.pyvista.org/version/stable/examples/01-filter/geodesic.html
How?
The functionality is implemented to ensure backward compatibility. You can still utilize the compute_features method, and if you provide a max_graph_edge_length parameter that is smaller than the search_radius, the new functionality will be activated.
from jakteristics import compute_features
features = compute_features(xyz, search_radius=0.15, max_graph_edge_length=0.05, feature_names=['planarity', 'linearity'])
It will compute the classic neighborhood and filter out any points that cannot be reached with edges, where each individual edge must be smaller or equal to max_graph_edge_length, and the cumulative sum of the edges must be smaller or equal to search_radius.
Results
search_radius=0.5 (both)
max_graph_edge_length=0.1 (only for Geodesic distance)
| Feature | 'Classic' (only Euclidean distance) | Geodesic distance |
|---|---|---|
| number_of_neighbors | ||
| eigenvalue1 | ||
| PCA2 |
Why not?
- it's slow
- it requires more RAM (The best way to reduce RAM usage is to gradually decrease the value of
max_k_neighbors. In most cases, this will not affect the result.) - you have to decide on two parameters instead of one :smile:
There are still a few optional TODOs remaining, but everything should be functioning properly.
By the way: I think have a basic understanding of Python and C, but if you come across anything that appears unusual in Cython, it is likely because it is indeed strange. Please let me know!
Hey, sorry for the delay.
I think this looks very interesting, thanks for the detailed explanation.
I'll try to find the time to test this soon!
