What's a simple and efficient method for extracting line segments from a simple 2D image?

Question

Specifically, I'm trying to extract all of the relevant line segments from screenshots of the game 'asteroids'. I've looked through the various methods for edge detection, but none seem to fit my problem for two reasons:

1. They detect smooth contours, whereas I just need the detection of straight line segments, and only those within a certain range of length. Now, these constraints should make my task considerably easier than the general case, but I don't want to just use a full blown edge detector and then clear the result of curved lines, as that would be prohibitively costly. Speed is of the utmost importance for my purposes.

2. They output a modified image where the edges are highlights, whereas I want a set of pixel coordinates depicting the endpoints of the detected line segments. Alternatively, a list of all of the pixels included in each segment would work as well.

I have an inkling that one possible solution would involve a hough transform, but I don't know how to use this to get the actual locations of the line segments (i.e. endpoints in pixel space). Though even if I did, I have no idea if that would be the simplest or most efficient way of doing things, hence the general wording of the question title.

Lastly, here's a sample image:

Notice that all of the major lines are similar in length and density, and that the overall image contrast is very high. I'm hoping the solution to my problem will exploit these features, because again, efficiency is paramount.

One caveat: while most of the line segments in this context are part of a polygon, I don't want a solution that relies on this fact.

Answer 1

Have a look at the Line Segment Detector algorithm.

Here's what they do :

You can find an impressive video at the bottom of the page.

There's a C implementation (that works with C++ compilers) that works out of the box. There are just one or two files, and no additional dependencies

But, be warned, the algorithm is under the GNU Allegro GPL license.