Maze Solving with Image Processing Algorithms Using MATLAB

Digital Image Processing was the most interesting course in my 7th semester, we were not only studying about digital image analysis but also its applications to human being to help their daily activities. In the end of this class we had to make a project about image processing, so we (Fajar, Yulia and I) wanted to make a project about Maze Solving with Image Processing Algorithm using MATLAB.

Why Maze Solving?

Do you know Maze Game?. yeah it is quite interesting, isn’t it?. Maze game is one of favorite “brain and puzzle” game in the world. it is played maybe more than a billion people in the world, all ages, with various level. we can solve the maze easily for a low level of difficulty, but it will takes a long time to solve for high level of difficulty.  If you take to long to solve the maze and you are so curious about the solution, we can solve the maze with image processing in very very short time. the maze puzzle can be solved using MATLAB program that created as *.m file and the solution will be displayed as *.fig file.

f74c1f1f6491ce9395e28882dfec9b4a
Diagram block system

How to Solve The Maze?

Before I explain how to solve the maze with Image Processing algorithms, would you mind to solve this maze to me?

SolOneit is very easy, isn’t it? You can solve it (maybe) under a minute.. and how about this one.MazeMedium0mm.. Interesting, you can solve it, but you need more time. it’s quite difficult. And, how about this one.

MazeExtraooh maan.. That’s crazy.. you’ll show me just-kill-me-already-look.

To solve those mazes, we use some of technique that we have just learned in the class, and we divided into several steps, there are:

  • Pre-Processing
This is the first step to solve the maze. we need to prepare the maze image which will be solved. When the program starts running, the dialog box appears on the screen and asks user to choose the maze image [1]. when user click “Open” button, maze image is ready to be process. look up this picture [2].
[1] Dialog box
[1] Dialog box
  • Image Enhancement
In this step, the maze image will be converted to monochrome image. monochrome image will be obtained by extraction each of color (RGB) that consists of Red, Green, and Blue channel color, and we choose one of these monochrome channels which have high contrast. After that, we need to prepare image for thresholding process with scaling the image become 0 – 255 range. we have to invert the binary image to become binary inverse. so the walls will become white, and the path is become black, you can see in this picture [3].
[2] Original image (left), [3] Binary image (right)
  • Image segmentation
in this step, the program will perform the segmentation process. in this process, we will determine which maze is connected or separated. to distinguish the wall are connected each other is done by random coloring to each connected wall. the result can be seen in this picture [4]. in that picture [4], we can see, we obtain two group connected-wall. It appears in two different color. we need to choose one of those walls to the next process and eliminate the other one. the following results after we eliminate one of the connected-wall is in this picture [5].
[4] Segmentation to distinguish between connected-wall and separated-wall
[4] Segmentation to distinguish between connected-wall and separated-wall, [5] Selection one the the connected-wall
  • Morphological Operation
after we obtain one connected-wall, we need to perform dilation process to close the unnecessary path. here the result of dilation by passing a large structure element with a particular pixel [6]. the result of dilation process is often still leaves holes that need to be closed. here the result of the closing holes [7]. after closing the holes, we have to perform erosion process, here the result [8]. after that, we need to do subtraction between the image from dilation process (+closed holes) and the image form erosion process in order to get the solution path in this picture [9].
lala
From left to right, [6] dilation process, [7] closing the holes, [8] erosion process, and [9] the path which is got by subtraction process between dilation (+ closing the holes) image and erosion image, is the solution path
  • Post-Processing
in this last process, we have to combine the solution path that we have been obtained with the initial image in the single image. the process is performed by merger from three monochrome channel into a single image (RGB). here the final result to solve the maze. the red object in this picture [10] is solution path of *.jpg file.
Path solution of the maze.
[10] Path solution of the maze.
Very simple, isn’t it?, and definitely very interesting.  you don’t need using some kind of advanced algorithm to solve maze problem. well, mmm, thanks to Fajar and Yulia have engaged me with this project. May the luck be here with us. #fingercross
[Update]
I was really proud of my team for this project.. We got an excellent response from our Lecturer, and I quoted “Very interesting idea, outstanding presentation, overwhelmed project”. Well, that’s big, really big. Thanks anyway.
Advertisements