SN-Graph: a graph skeletonisation algorithm.

A Python implementation of an SN-Graph skeletonisation algorithm. Based on the article SN-Graph: a Minimalist 3D Object Representation for Classification arXiv:2105.14784.

Description

Given a binary image/volume representing a shape, SN-Graph works by:

1. Creating vertices as centres of spheres inscribed in the shape, where one balances the size of the spheres with their coverage of the shape, and pariwise distances from one another.
2. Adding edges between the neighbouring spheres, subject to a few common-sense criteria.

The resulting graph serves as a lightweight 1-dimensional representation of the original image, potentially useful for further analysis.

Documentation

For documentation see docs.

For API reference see api_reference.

Bug reports, improvements, and pull requests are welcome. See CONTRIBUTING.md to get started.

Installation

pip install sn-graph

or

poetry add sn-graph

Basic Usage

See notebooks demo_sn-graph and 3d_demo for 2D and 3D demo, respectively. Notebook mnist_classification has some good stuff too!

import numpy as np
import sn_graph as sn

# Create a simple square image
img = np.zeros((256, 256))
img[20:236, 20:236] = 1  # Create a square region

# Generate the SN graph
centers, edges, sdf_array = sn.create_sn_graph(
    img,
    max_num_vertices=15,
    minimal_sphere_radius=1.0,
    return_sdf=True
)

import matplotlib.pyplot as plt

#Draw graph on top of the image and plot it
graph_image=sn.draw_sn_graph(centers, edges, sdf_array, background_image=img)

plt.imshow(graph_image)
plt.show()

Key Parameters

• max_num_vertices: Maximum number of vertices in the graph
• max_edge_length: Maximum allowed edge length
• edge_threshold: Threshold for determining what portion of an edge must be contained within the shape
• minimal_sphere_radius: Minimum radius allowed for spheres
• edge_sphere_threshold: Threshold value for deciding how close can an edge be to non-enpdpoint spheres
• return_sdf: Whether to return signed distance field array computed by the algorithm (neccessary to extract radii of spheres)

Authors

• Tomasz Prytuła (tomasz.prytula@alexandra.dk)