I'd like to welcome back guest blogger Spandan Tiwari for today's post. Spandan, a developer on the Image Processing Toolbox team, posted here previously about circle finding and homomorphic filtering.
A few weeks ago Steve wrote about watershed transform and how to use it for image segmentation. I thought I would continue the topic and highlight another neat application for watershed transform - Maze Solving. Steve discussed this problem in his earlier post on Exploring Shortest Paths and showed a solution based on Geodesic distance transform (bwdistgeodesic). In this post I show another way for solving a maze using watershed transform.
Here's a maze. We would like to find the solution , i.e. a path between the two points (entry and exit points) shown in red.
I = imread('http://blogs.mathworks.com/images/steve/2011/maze-51x51.png'); I = logical(I); imshow(I) hold on; plot([6 526], [497 517], 'ro', 'MarkerSize', 15,'LineWidth', 2); hold off;
I should mention that in my approach I am considering only 'standard' or 'perfect' mazes that have one and only one path from the entry point to the exit point, and some other nice properties such as absence of loops. I will call these mazes well-behaved mazes.
Here is the key idea behind using watershed transform for solving a maze. The landscape (or surface) of the image of a well-behaved maze has two catchment basins. The watershed between those catchment basins is the solution path for the maze! (For more details on the definition of watershed and catchment basin see Steve's newsletter article The Watershed Transform: Strategies for Image Segmentation). Let's look at the catchment basins as produced by watershed.
L = watershed(I); imshow(L,)
The two basins are shown in grey and white. If you follow the interface (boundary) between the two basins (grey and white regions), you can see notice that it is the solution (path) to the maze.
The good news is that at this point we have already solved the bulk of the problem. All we need to do now is to extract the interface between the two basins. There are different ways to do this. Here's the one that I like, mainly because I find it to be robust. Another minor reason I like it is that the final path stays parallel to the maze lines which gives it a nice clean look.
First we create a new image retaining only the original image region from one of the catchment basins.
L1 = L == 2; I1 = L1.*I; imshow(I1)
Next we use watershed again to get catchment basins for this new image.
L2 = watershed(I1); imshow(L2,)
Notice that the catchment basin in this new image has shrunk roughly by half the width of the maze paths as compared to the same catchment basin in the original image. This can be seen clearly using imshowpair. It highlights the area where the images are different using color (green, in this case)
As the last step we just extract the path shown as the green region, which is the region where the two catchment basins differ.
img1 = L == 2; img2 = L2 == 2; path = img1 - img2;
We can visualize the path on the maze nicely using Steve's imoverlay function.
P = imoverlay(I, path, [1 0 0]); imshow(P)
Here are few other results on different mazes.
Get the MATLAB code
Published with MATLAB® R2013b
4 CommentsOldest to Newest
Readers may be interested in the related File Exchange utility “Maze solution” by Image Analyst: http://www.mathworks.com/matlabcentral/fileexchange/27175-mazesolution
This utility was chosen as pick of the week 4 years ago: http://blogs.mathworks.com/pick/2010/04/30/solving-mazes-with-image-processing-algorithms/ and was also discussed by Loren: http://blogs.mathworks.com/loren/2010/04/21/a-mazing-way-to-learn-some-image-processing/
Steve – I wanted to write a comment on a non-guest blog entry, but it won’t let me go that far back.
Anyway, I wanted to thank you (and your guests) for going over the watershed function. I had been dealing with images that had…a decent amount of noise. I had been trying many things to remove the noise, and it turns out the watershed function works the best. Of course, I had to combine it with multiple other filters.
So I have a working code, albeit a bit slow (5 seconds per image, applied to a total of about 37,000 images). My code ended up being very convoluted, complicated, and has a lot of “user-defined parameters” that can be changed to get better results.
Given all that, I’m really, really curious as to how you’d go about filtering the images that I have. I’m going to look to upload them through the file exchange here if I can if you are interested in taking a look. The images are schlieren grayscale images of a fluid jet. I’m trying to separate the fluid jet from the background, which is easy in some cases, hard in others, and may be impossible for still others. With your experience, I’m just interested in seeing how you’d go about solving the issue of removing the background noise. If you want to contact me directly, feel free.
Paul—I don’t know exactly when I might get to look at these. Perhaps you could post your question on MATLAB Answers? Image uploading is now supported there.
please help me to solve maze puzzle like this using image processing in matlab