3

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).

Start (binary image) End result I want

Binary file for testing

Daniel Åkesson
  • 1,330
  • 1
  • 12
  • 21
  • Skeletonization + finding pixels with `num_neighrbours != 2` (refeering to *green* / 1 neighbours in your image) should give you the connection points. Can you upload the image in a B&W format without the `B` on it for testing? – Imanol Luengo Sep 22 '15 at 08:57
  • I uploaded the image as .mat file, see edited post. Not the one on the image but one that I want the approach to work on. Thanks for your reply! – Daniel Åkesson Sep 22 '15 at 12:09
  • Is the second image is what you try to achieve from the first image? May you elaborate a bit what problems you have with hough transform? – Alexander B Sep 29 '15 at 07:35

2 Answers2

3

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:

enter image description here

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:

enter image description here

With more steps intersection points can be identified more precisely:

enter image description here

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.

enter image description here

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:

enter image description here

Renat Gilmanov
  • 17,735
  • 5
  • 39
  • 56
  • Nice work, thanks for sharing. The end result looks really promising. However, would this approach work if the figure did not have a majority of vertical and horizontal lines? – Daniel Åkesson Oct 08 '15 at 13:19
0

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):

Skeletonization the original data.

Results in the following graph:

enter image description here

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)

Trimmed graph

timlukins
  • 2,694
  • 21
  • 35