## 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.

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!

## 27 Comments

So Cool! Can we apply a combination of this technique with FindShortestTour to real time traffic control? Or maybe you already did?

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.

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?

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?

thank you

can you help me ,i have a problem on difirent equoition

Very well done!

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/..

WOW, that is amazing, so now we can cheat in little maze that we find in magazines/newspaper.. hehehe

simply amazing ;)

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.

WTF??? unbelivebuuulll function of this program

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.

@ 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!

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).

@ 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.

Awesome!!!

Posting a link to Bing Maps? What a tool.

It’d be cool if we could apply to any kind of map and find short routes for car driving.

It’s SO COOL! I have never imaged that Mathematica can do this!

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.

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?

:) ;) :P wow that is cool

awesome

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

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….

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/