Graph from axial axial skeleton

Question

I have a binary image whose foreground is white. From the branch points and end points of its axial axial coordinate, I would like to build a graph. Ideally, with the following structure:

• [nodes] having the format [ID XY], where X, Y are the pixel locations of the branch points or end points, and ID is the node identifier is an integer.
• [edge], which has the format [ID N1 N2], where N1 and N1 represent node identifiers.

Using both [nodes] and [edges], I will map the skeleton to an undirected representation of the graph.

In the code below, I can calculate the branch and end points, but now I need to connect them correctly:

skelImg = bwmorph(im, 'thin', 'inf'); branchImg = bwmorph(skelImg, 'branchpoints'); endImg = bwmorph(skelImg, 'endpoints'); [row, column] = find(endImg); endPts = [row column]; [row, column] = find(branchImg); branchPts = [row column]; figure; imshow(skelImg); hold on; plot(branchPts(:,2),branchPts(:,1),'r*'); hold on; plot(endPts(:,2),endPts(:,1),'*'); 

The following is an example of the input image (left), its skeleton (middle) and the corresponding branches and end points (right):

Or also in full resolution at the following URL: http://imgur.com/a/a3s4F/

Answer 1

As a first step, I suggest using the BFS option. You nodes are white pixels, and there is an edge if two pixels are neighbors. This will give you a complete graph with unnecessary nodes, points that are not branch points / end points.

Now, here's an important note, each of the unnecessary nodes contains exactly 2 edges, otherwise it would be a branch point or an end point.

So, start deleting all unnecessary nodes recursively:

 While there are nodes that are not branchpoints/endpoints Select one of these nodes. Merge its two edges into one by removing the node. 

Answer 2

A possible solution is as follows:

 getting branched points (bp) from skeleton getting edges : edges=skeleton-bp getting end points from edges adding branched points in a graph getting endpoints neighbouring branched points and linking adding remaining endpoints in the graph linking endpoints 

A python implementation using networkx gives: