Maze solving by image recognition

Question

I'm trying to do a project with some of my friends, and we came upon that:

Say I had to decipher this Labyrinth programmatically, how could I go on about that? My first decision when trying to solve labyrinths by image recognition is obviously simply painting the open path, this way the paint end (The arrow in the start of the labyrinth is there to provide a way for the recognition to see 'ok that's the start')would indicate the exit.

Problem is, with those filters in place, I can't paint it, nor I have any other idea on how to solve it. So, would there be any way of doing so with Open CV? (or any other option would be fine too, if possible)

I really don't know how to tackle this problem, so if possible, just point me in the direction of an option and I will research more on that.

Thanks a lot.

Answer 1

For simplicity, consider a colorspace which gives a channel where this kind of noise is rendered useless. For instance, if we take the S channel from HSB we get the image at left, which is easily binarized by Otsu -- image at right.

Note that at a higher manual threshold, we would obtain only the end points as well the starting point. By doing that, we can dilate these points (image at left) and add the result image to the top right image. Now if a geodesic dilation is performed in this resulting image using the image at left as a marker, we obtain the paths that connect at least two points -- image at right.

The starting point can be found by a simple template matching, thus you can eliminate the paths that do not contain the starting point. This gives the next image. Now all that you have to do is perform a flood fill in a breadth-first manner to obtain the minimal path from the starting point to some exit point.

Answer 2

An interesting way to solve the maze might be to look at the fact that the walls of any maze make connected components. If there is only one exit then the maze walls can be split into 2 components which join along the path between entrance and exit. As there are several exits this maze breaks into several connected components.

By performing some really basic thresholding on the image I was able to reduce it to a simplified version where the walls are black and the paths are white. By flood filling on each large connected part of wall I got something that looks like this.

You can find paths from one point to another by following paths that are bordered on either side by different colors. This seems to have a failure mode around the island you can see at the A exit but the path from entrance to D is quite clear.