{"id":954,"date":"2014-01-21T07:00:32","date_gmt":"2014-01-21T12:00:32","guid":{"rendered":"https:\/\/blogs.mathworks.com\/steve\/?p=954"},"modified":"2019-11-01T10:58:21","modified_gmt":"2019-11-01T14:58:21","slug":"solving-mazes-with-the-watershed-transform","status":"publish","type":"post","link":"https:\/\/blogs.mathworks.com\/steve\/2014\/01\/21\/solving-mazes-with-the-watershed-transform\/","title":{"rendered":"Solving mazes with the watershed transform"},"content":{"rendered":"\r\n

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<\/a> and homomorphic filtering<\/a>.<\/i><\/p>

A few weeks ago Steve wrote about watershed transform<\/a> 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<\/a> and showed a solution based on Geodesic distance transform (bwdistgeodesic<\/tt><\/a>). In this post I show another way for solving a maze using watershed transform.<\/p>

Here's a maze. We would like to find the solution<\/i> , i.e. a path between the two points (entry and exit points) shown in red.<\/p>

I = imread('https:\/\/blogs.mathworks.com\/images\/steve\/2011\/maze-51x51.png'<\/span>);\r\nI = logical(I);\r\nimshow(I)\r\nhold on<\/span>;\r\nplot([6 526], [497 517], 'ro'<\/span>, 'MarkerSize'<\/span>, 15,'LineWidth'<\/span>, 2);\r\nhold off<\/span>;\r\n<\/pre>\"\" 
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<\/i> mazes.<\/p>
L = watershed(I);\r\nimshow(L,[])\r\n<\/pre>\"\" 
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.<\/p>
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.<\/p>
First we create a new image retaining only the original image region from one of the catchment basins.<\/p>
L1 = L == 2;\r\nI1 = L1.*I;\r\nimshow(I1)\r\n<\/pre>\"\" 
Next we use watershed<\/tt> again to get catchment basins for this new image.<\/p>
L2 = watershed(I1);\r\nimshow(L2,[])\r\n<\/pre>\"\" 
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<\/tt>. It highlights the area where the images are different using color (green, in this case)<\/p>
imshowpair(L,L2)\r\n<\/pre>\"\" 
As the last step we just extract the path shown as the green region, which is the region where the two catchment basins differ.<\/p>
img1 = L == 2;\r\nimg2 = L2 == 2;\r\npath = img1 - img2;\r\n<\/pre>
We can visualize the path on the maze nicely using Steve's imoverlay<\/tt><\/a> function.<\/p>
P = imoverlay(I, path, [1 0 0]);\r\nimshow(P)\r\n<\/pre>\"\" 
Here are few other results on different mazes.<\/p>
\"\" <\/p>
\"\" <\/p>
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<\/i> and catchment basin<\/i> see Steve's newsletter article The Watershed Transform: Strategies for Image Segmentation<\/a>). Let's look at the catchment basins as produced by watershed<\/tt>.<\/p>