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:
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/
Lateral – Away from the medial line or central axis of the body.
The medial axis is calculated as follows: at first, reconstructing bitmap image from contour information, then, thinning the bitmap image, finally, creating the line segment information of the resulting skeleton. Now. the medial axis shows a broad shape of the target.
Medial Axis Transform (MAT) is a representation that encodes an object with symmetric (medial) axes in the object interior. MAT has been employed in a variety of applications such as pattern recognition of digital images, biological shape analysis and robotic motion planning.
The medial axis of an object is the set of all points having more than one closest point on the object's boundary. Originally referred to as the topological skeleton, it was introduced in 1967 by Harry Blum as a tool for biological shape recognition.
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.
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:
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With