Technical Articles and Newsletters

Tips and Tricks: Solving a Maze with the Watershed Transform

The watershed transform finds “catchment basins” and “watershed ridge lines” in an image by treating the image as a surface where light pixels are high and dark pixels are low. It is a powerful tool for solving segmentation problems in densely packed objects and other difficult images, such as an image of biological tissue or a container full of objects.

Using a watershed transform to solve a maze—that is, to find a path between the entry and exit points1—is a straightforward process, but it involves several steps. All the steps must be completed to get the best results.

To illustrate this process, we will use the watershed function in Image Processing Toolbox™ to “solve” the maze (Figure 1).

Figure 1. Original maze.

The landscape (surface) of the maze image has two catchment basins. The solution path is the watershed between those catchment basins. Let’s compute the catchment basins produced by watershed.

L = watershed(I);

We can visualize the catchment basins using imshow. The interface (boundary) between the two basins is the solution (path) to the maze.

At this point we have already solved the bulk of the problem. All we need to do now is extract the interface between the two basins.

First we create a new image, retaining only the original image region from one of the catchment basins (Figure 2).

L1 = L == 2;
I1 = L1.*I;
imshow(I1)
Figure 2. Part of maze corresponding to a catchment basin.

Next we use watershed again to get catchment basins for this new image.

L2 = watershed(I1);

Using imshowpair we compare the new image to the original. We see in Figure 3 that the catchment basin in the new image has shrunk by roughly half the width of the maze paths (shown in green) compared with the same catchment basin in the original image.

imshowpair(L,L2)

Figure 3. Path (green) extracted by shrinking the catchment basin.

Finally, we extract the path shown in green, which is the region where the two catchment basins differ.

img1 = L == 2;
img2 = L2 == 2;
path = img1 - img2;

Using the imoverlay2 function we can visualize the path on the maze (Figure 4).

P = imoverlay(I, path, [1 0 0]); 
imshow(P) 
Figure 4. Solution path overlaid on maze.

The watershed transform is also useful for image segmentation. It can be applied to many images where traditional techniques fall short—for example, images where objects are densely packed, such as cells in a tissue sample. Any image where you can visually identify high or low intensity areas between objects will be a good candidate for watershed segmentation.

1We are considering only a "standard" or "perfect" maze that has one path from entry to exit.

2Available on the File Exchange

Published 2014 - 92203v00