Skip to content

Instantly share code, notes, and snippets.

@jrudolph

jrudolph/fiber-graph.md

Last active February 28, 2025 13:57
Show Gist options
  • Save jrudolph/3e0ebbd6e731f794733c236a86ff39fb to your computer and use it in GitHub Desktop.
Save jrudolph/3e0ebbd6e731f794733c236a86ff39fb to your computer and use it in GitHub Desktop.
Download ZIP
Notes on creating a mesh from fiber crosspoints
Raw
fiber-graph.md

Creating segments from intersecting horizontal and vertical fibers

Sean published results of his volume segmentation models that can detect and distinguish horizontal and vertical fibers (first in Ostober 2024 and later in January 2025)

Idea: recreate the fiber mesh by finding and connecting crosspoint between horizontal and vertical fibers

Process

  • Separate the fibers by running a connected component analysis over the model output, separately for horizontal and vertical fibers
  • Find the intersection of the two sets of fibers, i.e. for each pair of horizontal and vertical fibers, find the intersection set of the two fibers and if non-empty, record that the two fibers are connected at that point (and record the medoid of the intersection set). The result is a graph that describes which fibers are connected to each other, however it is missing the spatial structure needed to create a mesh.
  • In particular, different crosspoints on a single fiber are not yet put into a relation with each other. Since a fiber used to be a tube-like linear piece of structure, you want to connect crosspoints in a simple path along the structure.
  • To do this, I looked at every fiber in isolation and created an adjacency matrix between all the crosspoints on that fiber measuring the geodesic distance between each pair of crosspoints.
  • Using the adjacency matrix, for each crosspoint on the fiber, we find the two nearest neighbors and connect them to form a graph. This poor man's skeletonization works ok-ish but is far from perfect:
    • even in the best case of the shape actually being tube-like, a fiber might be split into multiple pieces when crosspoints are not evenly distributed
    • when two or more fibers touch, they will be connected, the graph will have branches that need to be separated
  • For those reasons, post-processing steps are needed to clean up the graph erring on the side of removing nodes and edges and losing some connectivity
  • After these steps, you have a huge graph that contains all the crosspoints on all the fibers.
  • So far, I did not manage to automate extracting a mesh from the resulting graph. What I did instead was starting from a single fiber, selectively adding new adjacent fibers to the graph, manually inspecting the full graph after each step, pruning some nodes and edges manually when the graph started to look "messy".
  • With these manual steps, I found a small grid-like mesh inside the graph that was naively converted to a mesh by mapping the nodes to a fixed-distance grid

Conclusions

  • Following fibers seems like a worthwhile approach to generate a mesh from a volume segmentation model.
  • The approach of creating a graph of crosspoints and then simplifying it to a mesh is not yet fully automated and currently requires manual intervention.

Open questions

  • How to create better skeletonization/graphs of the fibers? Maybe just apply a skeletonization algorithm instead and then estimate the relative positions of the crosspoints?
  • How to find clean grid-like meshes in the graph automatically ? Or provide manual tooling to grow the mesh from the graph interactively?

Media

Sean's fiber data: image

Grid-like subgraph:

image

Cleaned up:

image

Small segment corresponding to the grid:

image

Interactive graph editing:

interactive-graph-edit.mp4

Data

Preliminary results can be downloaded at https://dl.ash2txt.org/community-uploads/jrudolph/fiber-graph

Data format

Data generated by analyzing fibers from

https://dl.ash2txt.org/community-uploads/bruniss/scrolls/s1/fibers/hz_regular.zarr/
https://dl.ash2txt.org/community-uploads/bruniss/scrolls/s1/fibers/vt_regular.zarr/

in this subregion:

TOP_LEFT  = [2400, 3000, 7500]
CROP_SIZE = [2000, 2000, 4000]

fiber-graph.zip

  • collisions: one line for every crosspoint between fibers h<id> v<id> x y z
  • fiber-graph-adjacency:
    • for h.txt: one entry for each pair of crosspoint on this fiber <v_id1> <v_id2> <distance>, where v_id1 corresponds to the crosspoint h_<v_id1> (as seen in the collision file)
    • for v.txt: same for vertical fibers, each line has the format <h_id1> <h_id2> <distance>
  • fiber-graph:
    • {h,v}/.txt: contains the graph of connections inside of a single fiber in the same format as the fiber-graph-adjacency files (basically a cleaned subset of the full adjacency inside of a single fiber)
  • fiber-dot: contains a graphviz dot file with a dot formatted graph for each fiber
  • global.dot: the full set of edges for the mesh graph

classes.zip

  • classes
    • class-1: vertical fiber point clouds as a flat binary file with <u16_le><u16_le><u16_le> x/y/z entries for every voxel of a fiber
    • class-2: horizontal fibers

Code

Ongoing development efforts at https://github.com/jrudolph/vesuvius-gui/blob/grid-maker/src/zarr/test.rs

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment