How to find the joints and endpoints of medial axis

Question

I was able to get the medial axis using

image = Image.open('path/to/img.png')
image = (np.array(image) / 255).astype(np.uint8)
medial = skeletonize(image)
medial_x, medial_y = np.where(medial == 1)

But how can I find the endpoints and the joints of the medial axis using python as the coordinates I get from medial_x, medial_y = np.where(medial == 1) are not ordered in a way that I can easily get endpoints or joints?

The original silhouette is attached below.

Answer 1

i treat the skeleton as a graph, and construct its adjacency matrix. using the adjacency matrix you can find the end points really easily. the nodes in the graph with one neighbor are end points and those with more than two neighbors are what you call "joints". I like to call them intersections. The way i create the adjacency matrix is i initiate an NxN array with zeros and set the [i, j] value in the array to one if the Euclidian distance from node i to node j is less than 2, meaning that they are neighboring pixels in the image.

# create an adjacency matrix 
xx, yy = np.where(skeleton)
n = len(xx)

dist_mat = ((xx[:, None]-xx[None, :])**2 + (yy[:, None]-yy[None, :])**2)
adj_mat  = (dist_mat <= 2).astype(int)
# joints will have more than 2 neighbors and endpoints
# will have only one.
ends = np.where(adj_mat.sum(1)==1)[0]
intersections = np.where(adj_mat.sum(1)>2)[0]

at the end, the variable 'ends' will hold the indices of the end points such that the [x, y] location of end point k in the image will be [xx[ends[k]], yy[ends[k]]]. and the same is true for the intersections.

Answer 2

I did this using wand - which is derived from ImageMagick. It has a skeletonise method and "Hit and Miss Morphology" for looking for specific shapes such as line-ends or junctions.

There is an excellent discussion by Anthony Thyssen here, but if I may summarise, you are looking for the following shapes when trying to find line-ends:

and this when looking for junctions:

The black squares mean the image must be black at that location and are represented as zeroes in the kernel in the code. The white squares mean the image must be white at that location and are represented as ones in the kernel in the code. The blank squares mean we "don't care" what is at that location and are represented as dashes (minus signs) in the code.

The code looks like this:

#!/usr/bin/env python3

import numpy as np
from wand.image import Image

# Use 'wand' to:
# 1 skeletonize
# 2 find line-ends using Top-Hat Morphology
# 3 find line-junctions using Top-Hat Morphology

with Image(filename='Q4J0l.png') as img:
    # Skeletonize
    img.morphology(method='thinning',
                   kernel='skeleton',
                   iterations=-1)
    img.save(filename='DEBUG-skeleton.png')

    # Find line-ends using Top-Hat Morphology
    # There are two kernels here, separated by a semi-colon
    # Each is rotated through 90 degress to form all 4 orientations
    # The first 3x3 kernel is the one tinted red in the diagram above.
    # The second 3x3 kernel is the one tinted green in the diagram above
    lineEnds = """
    3>:
        0,0,-
        0,1,1
        0,0,-;
    3>:
        0,0,0
        0,1,0
        0,0,1
    """
    # Clone the original image as we are about to destroy it
    with img.clone() as endsImage:
        endsImage.morphology(method='hit_and_miss', kernel=lineEnds)
        endsImage.save(filename='DEBUG-ends.png')

    # Find line-junctions using Top-Hat Morphology
    # There are three kernels here, separated by a semi-colon
    # Each is rotated through 90 degress to form all 4 orientations
    # The first 3x3 kernel is the one tinted yellow in the diagram above
    # The second 3x3 kernel is the one tinted magenta in the diagram above 
    # The third 3x3 kernel is the one tinted cyan in the diagram above
    lineJunctions = """
    3>:
        1,-,1
        -,1,-
        -,1,-;
    3>:
        -,1,-
        -,1,1
        1,-,-;
    3>:
        1,-,-
        -,1,-
        1,-,1
    """
    # Clone the original image as we are about to destroy it
    with img.clone() as junctionsImage:
        junctionsImage.morphology(method='hit_and_miss', kernel=lineJunctions)
        junctionsImage.save(filename='DEBUG-junctions.png')

The DEBUG-images are as follows:

DEBUG-skeleton

DEBUG-lineends

DEBUG-junctions

---

It's actually all a lot simpler in the Terminal with ImageMagick:

magick Q4J0l.png -morphology Thinning:-1 Skeleton skeleton.png
magick skeleton.png -morphology HMT lineends ends.png
magick skeleton.png -morphology HMT linejunctions junctions.png

Or you can produce all 3 images in a single command:

magick Q4J0l.png \
    -morphology Thinning:-1 Skeleton -write S.png              \
    \( +clone -morphology HMT lineends -write E.png +delete \) \
    -morphology HMT linejunctions J.png