Find lines in shape

Question

I have a binary image and I'm looking for a robust way to find the lines in the shape and the topology (how the lines connect).

I have experimented in matlab (although what I'm asking for is which methods to use).

I've tried using skeletonization on the binary image and then used hough-transform, works sometimes but not a robust solution. I struggled with boundary disturbance.

Could anyone point me in a direction of which methods to use here (and in what order).

Binary file for testing

Answer 1

Frankly speaking, I've been monitoring this question for some time in the hope to see useful answer. The task itself does not seem to be really complex (and I'll try to prove that), but elegant solution is still a bit far from me.

Some time ago I solved similar task and it does look like with my very basic home-grown solution your initial example is easily traceable:

It is just a simple scan (1), vertical and horizontal lines identification(2) along with further analysis of the more complex areas (3). Having all areas analysed (3) it is not that hard to find intersection points and optimise them as well (4).

The result is pretty rough, but it confirms the feasibility if this approach.

I do understand this is a bit far from Matlab, but I just want to highlight several important moments:

• skeletonization will potentially break the initial geometry
• further analysis of the skeleton seems to be a bit tricky and unreliable
• with a bit of enhanced quality your images can be traced with way more simple approach

BTW, in my approach different operations can be performed in parallel. Scan step is adjustable and even with reduced number of scans result is pretty good:

With more steps intersection points can be identified more precisely:

I came to conclusion it is really important to use all information provided by an initial image. All simplifications, etc will remove valuable facts increasing overall complexity of the task.

Update

Would this approach work if the figure did not have a majority of vertical and horizontal lines?

Those steps are pretty independent, so there is no strict requirement to have vertical or horizontal lines. Naturally, it is more complex task to identify intersections and do some additional tweaking in order to enhance accuracy.

Easy to see there are some significant errors introduced by vertical lines at the beginning and at the end of the shape. Very straightforward optimisation gives us better results:

Answer 2

This is indeed a tricky problem, going from a binary image to a graph (i.e. topology). Fundamentally involving crossing from the discrete world of pixels and 2D image data, to a abstract data structure of nodes and connectivity...

But what can provide the “glue” between? Quite an open question I’m afraid, requiring a complex interpretation of visual data.

Fortunately, someone else has shared a good attempt here in python: http://planet.lengrand.fr/?post_id=267

(This obviously assumes a full python installation NetworkX and any other dependencies. I did this on Mac with homebrew via a few call such as > brew install opencv; pip install networkx; brew install graph-tool; brew install graphviz. The ipython notebook below also makes use of http://scikit-image.org and http://mahotas.readthedocs.org/en/latest/ - so quite a heady cocktail of Computer Vision and Image Processing code! Finally: you’ll of course need ipython installed...)

Here is an example (which first loads in the downloaded notebook from above - all run from: > ipython —pylab):

%run C8Skeleton_to_graph-01.ipynb

import scipy.io as sio # Need this to load matlab files...

mat = sio.loadmat('bw.mat')

img = np.zeros((30,70),np.uint8) # Buffered image border

img[5:25,5:65] = mat['BW'] # Insert matrix data into middle

skeleton = mh.thin(img) # Do skeletonization... 

graph = nx.MultiGraph() # Graph we’ll create

C8_Skeleton_To_Graph_01(graph, skeleton) # Do it!

figure(1)
subplot(211)
plt.imshow(img,plt.get_cmap('gray'), vmin=0, vmax=1, origin='upper');
subplot(212)
plt.imshow(skeleton,plt.get_cmap('gray'), vmin=0, vmax=1, origin='upper');

figure(2)
nx.draw(graph)

Showing that skeletonization of your originally provided Matlab data (with buffer around edges):

Results in the following graph:

Notice the graph topology and layout correspond with the structure of the thinned image - including the "spurs" created at the end. This is an ongoing problem/research area with such an approach...

EDIT: but could be possibly solved by removing stray arcs (leading to leaf nodes with degree==1) in the graph. e.g.

remove = [node for node,degree in graph.degree().items() if degree == 1]

graph.remove_nodes_from(remove)

nx.draw(graph)