Wolfram Blog
Jon McLoone

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.

Aerial photo of the maze

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.

Inputting the image
Code to remove the color information
The cleaned up image

Then I got rid of all the small bits of dither and exterior paths.

Getting rid of the small bits
Getting rid of the small bits

Next, I used the new morphological function Thinning to reduce lines down to a single pixel in thickness.

Thinning the lineThinning the line

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

Removing the dead ends of paths
Removing the dead ends of paths

Now, with all dead ends removed, we can overlay the solution onto the maze.

Overlay of the solution on the maze
Overlay of the solution on 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.

Fill in small holes
Fill in small holes

Then repeat the thin-and-prune solution. This automates the steps:

Repeat the thin-and-prune solution

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.

The new solution overlayed on the original image
The new solution overlayed on the original image

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.

Remove the bigger loops
Remove the bigger loops

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!

Posted in: Image Processing
Leave a Comment

27 Comments


Samuel Chen

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
Miroslav Štandera

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
Bo

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
Luboš Motl

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
sousou

thank you

Posted by sousou    November 16, 2010 at 3:24 pm
sousou

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

Posted by sousou    November 16, 2010 at 3:27 pm
Ricky

Very well done!

Posted by Ricky    March 2, 2011 at 5:03 pm
melchor idong

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
Pheng

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
Jim2

simply amazing ;)

Posted by Jim2    April 8, 2011 at 2:01 am
Vernon

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
Yuri Niitsuma

WTF??? unbelivebuuulll function of this program

Posted by Yuri Niitsuma    April 16, 2011 at 6:18 pm
Immo

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
Jon McLoone

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

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
Jon McLoone

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

Awesome!!!

Posted by Shams    May 25, 2011 at 4:40 am
a human

Posting a link to Bing Maps? What a tool.

Posted by a human    May 28, 2011 at 6:31 pm
Alan

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
Fleeting Years

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

Posted by Fleeting Years    June 8, 2011 at 8:04 am
Tai

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
Tai

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
lll

:) ;) :P wow that is cool

Posted by lll    July 12, 2011 at 10:05 am
Uma kant

awesome

Posted by Uma kant    August 4, 2011 at 10:18 am
Dan Reznik

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
Anchit Pantni

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
    Jon McLoone

    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


Leave a comment

Loading...

Or continue as a guest (your comment will be held for moderation):