Graph from medial axis skeleton

Question

I've a binary image whose foreground is white. Out of the branchpoints and endpoints of its medial-axis skeleton, I would like to build a graph. Ideally, with the following structure:

1. [nodes] having the format [ID X Y] where X,Y are the pixel locations of the branchpoints or endpoints, and ID is the node's ID - an integer number.
2. [edges] having the format [ID N1 N2] where N1 and N1 represent the node's IDs.

By using both [nodes] and [edges] I'll have then a mapping of the skeleton into an undirected graph representation.

With the code below, I can compute the branch and endpoints, but now I need to connect them properly:

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),'*');

An example of the input image (on the left), its skeleton (middle), and the corresponding branch- and end-points (right) is given below:

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

Answer 1

As the first step, I suggest using BFS variant. You nodes are white pixels, and there is an edge if the two pixels are neighbors. This will provide you a full graph with unneeded nodes, the points that are not branch-points/end-points.

Now, here is an important observation, each of the unneeded nodes contains exactly 2 edges, otherwise it would have been a branch-point or an end-point.

Thus, start removing all unneeded 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 consists in:

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 with networkx yields: