Wolfram Computation Meets Knowledge

aMAZEing Image Processing in Mathematica

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!

Comments

Join the discussion

!Please enter your comment (at least 5 characters).

!Please enter your name.

!Please enter a valid email address.

27 comments

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

    Reply
  2. 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.

    Reply
  3. 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?

    Reply
  4. 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?

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

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

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

    Reply
  8. 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.

    Reply
  9. WTF??? unbelivebuuulll function of this program

    Reply
  10. 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.

    Reply
  11. @ 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!

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

    Reply
  13. @ Timwi
    I revisited this subject in December with a much better approach.
    https://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.

    Reply
  14. Posting a link to Bing Maps? What a tool.

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

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

    Reply
  17. 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.

    Reply
  18. 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?

    Reply
  19. 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

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

    Reply