aMAZEing Image Processing in Mathematica
November 3, 2010 — Jon McLoone, International Business & Strategic Development
A little over a mile from the Wolfram Research Europe Ltd. office, where I work, lies Blenheim Palace, which has a rather nice hedge maze. As I was walking around it on the weekend, I remembered a map solving example by Peter Overmann using new image processing features in an upcoming version of Mathematica. I was excited to apply the idea to this real-world example.
The maze is meant to depict a cannon with cannon balls below it and flags and trumpets above.
Often the first task in any image processing is to clean up the image and get rid of random detail that we don’t care about, so first I got rid of the color.
Then I got rid of all the small bits of dither and exterior paths.
Next, I used the new morphological function Thinning to reduce lines down to a single pixel in thickness.
Then I applied Pruning to remove the dead ends of paths, so that we are left only with paths that go somewhere (including in a loop).
Now, with all dead ends removed, we can overlay the solution onto the maze.
You can see that the maze is not very difficult, in that there are multiple solutions and few paths that really are dead ends.
There are, however, some loops that while perfectly pleasant to walk round, take us on unnecessary, and potentially infinite, detours. One rough-and-ready way to remove those is to fill in small holes.
Then repeat the thin-and-prune solution. This automates the steps:
The solution now starts to be a bit approximate as it shortcuts through the middle of the loop, but in the case of small loops, this is good enough.
If we want to accept a greater level of drift, we can remove bigger loops. This is still acceptable for long, thin loops and loops on the edge of a route, but starts to be misleading for wide or complicated loops. Still, not bad for 10 lines of code.
The bottom half looks like it still has two big, unnecessary loops, but of course, image processing can’t help with the things that we can’t see. There are bridges on either side of the central circle that look like paths from the sky. We pass under the bridge on the right before looping round and crossing over the same point on top of the bridge. And on the left side of the maze, we can choose to take the inner route over the bridge or the outer route under the bridge.
If you haven’t remembered to bring my map with you, then these bridges are also your only chance to look down on the maze and plan your escape!