# aMAZEing Image Processing in Mathematica

November 3, 2010 — Jon McLoone, Director, Technical Communication & Strategy

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.

Once back at my computer, I started by using Bing Maps to get the aerial photo (data created by Intermap, NAVTEQ, and Getmapping plc).

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!

 So Cool! Can we apply a combination of this technique with FindShortestTour to real time traffic control? Or maybe you already did? Posted by Samuel Chen    November 3, 2010 at 8:20 pm
 Great and very interesting. It would be nice to complete this report with an estimation of the length of this maze (of course if it is possible) and the most interesting thing would be finding of the shortest path. Posted by Miroslav Štandera    November 4, 2010 at 2:28 am
 Wow, that’s something! You never cease to amaze me, guys, the designers of Mathematica. So, will we finally be able to search for ETI with the next release? Posted by Bo    November 4, 2010 at 4:52 am
 Great functions! I would still have some problems to use the last step of the solution, however. ;-) Is there some particular problem to get from A to B? And if there’s one, does the picture really tell me where to go? Posted by Luboš Motl    November 4, 2010 at 5:43 am
 thank you Posted by sousou    November 16, 2010 at 3:24 pm
 can you help me ,i have a problem on difirent equoition Posted by sousou    November 16, 2010 at 3:27 pm
 Very well done! Posted by Ricky    March 2, 2011 at 5:03 pm
 i agree. theres no specific task on where should i go. point a-b-or to somewhere.. is that MATH?? its good but its not thst helpful/.. Posted by melchor idong    March 11, 2011 at 12:16 am
 WOW, that is amazing, so now we can cheat in little maze that we find in magazines/newspaper.. hehehe Posted by Pheng    March 16, 2011 at 8:59 pm
 simply amazing ;) Posted by Jim2    April 8, 2011 at 2:01 am
 Wow, amazing. Do you think this technique could be used in translating text from a photograph? Well to be more specific, in character recognition from photographs. I think it’s well and truly possible, since signs have standardized writing in most cases. Posted by Vernon    April 14, 2011 at 7:46 pm
 WTF??? unbelivebuuulll function of this program Posted by Yuri Niitsuma    April 16, 2011 at 6:18 pm
 Nice tools. Still we can see that the real big problem in image processing is the binarization. Half of the cannon balls are unclosed, and so is a big loop next to the cannon-ball stack on the left-hand side of the maze. Thus, the pruning function removes these loops, because it sees them as dead ends. Here, it’s not as bad since they were loops anyway; but imagine that your maze has only one way through, and somewhere in between the way is not recognized during the binarization process. Then you’d end up with no result. Posted by Immo    May 3, 2011 at 10:24 am
 @ Immo There is plenty that you can do to improve the initial binarization step. I did the simplest thing of using an automatically selected brightness threshold, because it was sort-of good enough for this example. But Mathematica provides plenty of nice filters that could have pre-processed the image to take advantage of the color difference between path and hedge, and also more sophisticated binarization tools such as http://reference.wolfram.com/mathematica/ref/ChanVeseBinarize.html But I was trying to keep it simple! Posted by Jon McLoone    May 4, 2011 at 4:15 am
 How disappointing; I expected you’d just designate two points and it would find you the shortest path through the maze (using, perhaps, Dijkstra’s algorithm or something). Posted by Timwi    May 9, 2011 at 7:00 pm
 @ Timwi I revisited this subject in December with a much better approach. http://blog.wolfram.com/2010/12/21/the-battle-of-the-marlborough-maze-at-blenheim-palace-continues/ The approach I take there finds the shortest path between the specific start and end points, and with minor modifications would find the shortest route between any two points. Posted by Jon McLoone    May 11, 2011 at 8:11 am
 Awesome!!! Posted by Shams    May 25, 2011 at 4:40 am
 Posting a link to Bing Maps? What a tool. Posted by a human    May 28, 2011 at 6:31 pm
 It’d be cool if we could apply to any kind of map and find short routes for car driving. Posted by Alan    June 7, 2011 at 8:15 pm
 It’s SO COOL! I have never imaged that Mathematica can do this! Posted by Fleeting Years    June 8, 2011 at 8:04 am
 I’m not family with Mathematica. Does it have tools for modeling thinMaze as a graph? If so, the solutions (shortest path, longest path, etc.) would be simple to find. Posted by Tai    July 8, 2011 at 10:06 am
 Found the function I was looking for, MorphologicalGraph[]. http://reference.wolfram.com/mathematica/ref/MorphologicalGraph.html Now, how to translate the solution back into a nice visual map? Posted by Tai    July 8, 2011 at 10:21 am
 :) ;) :P wow that is cool Posted by lll    July 12, 2011 at 10:05 am
 awesome Posted by Uma kant    August 4, 2011 at 10:18 am
 How would you use mathematica’s Img processing toolbox to do the following: given an image, with a few simple 2d shapes in it (e.g., capital letters), i would like to report the (in general concave) polygon vertices which tightly enclose every shape. for example — if i start with letter L in an image I would like to return a 7-vertex polygon; in brief, how do i go from an image representation to a vector (polygonal) representation Posted by Dan Reznik    September 14, 2011 at 3:19 pm
 Heyy….can u pleas hlp me as my matlab showing that no function exist like Thining and pruning. So, how can i do this in matlab Help plzz…. Posted by Anchit Pantni    June 6, 2014 at 2:34 am
 Well the obvious answer is to switch to Mathematica! But if you really must work from within Matlab, short of implementing those functions yourself, all I can suggest is to call Mathematica from Matlab for those parts that Matlab can’t handle. The is a link at http://matlink.org/ Posted by Jon McLoone    June 6, 2014 at 10:09 am