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.

Diaconal

I retagged to make it easier for image processing folks to find your post and provide help. Good luck! – Carman

I wrote maze solver with image morphology some time ago. Perhaps it could help. – Karlise

Thanks for the tagging, Rethunk! Will take a look at your maze solver morphology, bsdnoobz, thanks! – Diaconal

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.

Beattie

OH--- Wow, that looks amazing, absolutely amazing, thanks a lot!! I have to go to work in literally 5 minutes, so I'm going to upvote you and when I come back I'm going to read this with more time and research the terms I still don't know. Really thanks! – Diaconal

+1 - Nice work. One question. How did you understand taking S channel will remove the noise ? – Nonie

@AbidRahmanK while it doesn't remove the noise per se, it highlights the fact that the walking paths in this maze are represented by a more vivid color (yellow, which noise doesn't mischaracterize) than walls (dark red, and with noise looks almost like a gray). Then the saturation channel gives something that resembles a mixture of two gaussians, which is the intended operation situation for Otsu. – Beattie

Hey MMG, could you maybe inform me of what tool you used to do that? I've been having problems to reproduce your beautiful solution. – Diaconal

@Diaconal do you mean the first step or something else ? Any tool that correctly converts RGB to HSB (or HSV) and allows you to pick the channel S and apply Otsu on it will give the same results for the first step. This includes, for example, OpenCV, Matlab, and Mathematica. – Beattie

Hello again MMG, i'm not sure on how I'm supposed to message people here in stackoverflow, so I apologize if I shouldn't be replying to comments like that. That being said, let me move on to what I want to say: Thanks a lot for everything, I've been working like crazy on that for the last week and managed to do what you recommended, plus generated a path: prntscr.com/umkzb (Using Matlab, by the way) The problem is, if the image I choose has different contrasts, I can't do the same thing, let me show you what I mean: IMG(goo.gl/OtK4G), S (goo.gl/oo8h6),Otsu(http://goo.gl/cnfxU) – Diaconal

@Diaconal to apply the method to different situations you need to understand the method. First, here is the actual S channel: i.imgur.com/qtDE7Wv.png. Then, by considering its histogram it is clear that Otsu will have trouble with it. Simpler methods work fine here (as well in the image included in the original question), like mean or median value in the histogram. The result of ColorNegate[Closing[Opening[Binarize[s, Method -> "Median"], 1], 2]] on this new image you linked in the comment is shown at i.imgur.com/yVz3NOJ.png. – Beattie

@Beattie Thanks! This worked great, as you showed, I also could solve my problem a few hours ago using a bilinear fifilter, converting to LAB and picking the A channel. But your method is actually way faster! Additionaly, I did convert your commands to use in Matlab, but I also have wolfram here, I couldn't figure out how to get only the S channel using Wolfram, is it possible? (I thought hue[h,s,v] was supposed to do that, but had no success) – Diaconal

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.

Feune

It looks like you are walking over the walls. – Beattie

@Beattie I guess it is cheating to do this. I figured some processing of the maze appearance was allowed. – Feune

Whoa, thanks a lot! That looks VERY good and seems to lead in the correct direction, could you please expand on 'basic tresholding' ? I tried everything I could, and my 'best' result was transforming the maze in a great mass of messy walls and paths. PS: Of course processing of the mage image is allowed, it's actually the main objective – Diaconal

Answer 3

This answer is only a complementary to the answers above: There is an easy way to solve a maze. It is called "the rule of the right hand". When you enter a maze, you put your right hand on the right wall and just go. Never let go of the right wall and you will eventually find a way out. In other words, when there is an intersection, always turn right (otherwise your right hand will lose the grip of a wall). When you come to a dead end, make U turn to the left (thus always touching the right wall).

Implement an algorithm according to this principle. When you face forward always make sure that your neighbor pixel on the right is a maze wall.

Brazzaville

If there is a loop you will go around it. The only case it doesn't work is if you have 3D maze (few floors) with 3D loop. – Brazzaville

He is asking about how to recognize the maze from the image, using computer vision. He is not asking how to solve the maze once it is in a readable format. – Prochronism

Answer 4

I believe you are talking about 'path finding'

Wikipedia entry has a simple algorthm for finding paths on a grid: http://en.wikipedia.org/wiki/Pathfinding but googling should provide some code samples in your language of choice.

Calebcaledonia

Yes, indeed! But as I said, the filters that are in place simply make every pathfinding research I made invalid so far. Would there be a way to 'unfilter' or something like that? That's what I'm trying to discover. – Diaconal

a contrast filter perhaps? light and dark becomes white and black – Calebcaledonia