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: