Time to git it in
I’ve been working on a project for quite a while before I decided to make a blog for it so from here on in I will try to keep it updated. For a new project I thought of a topic that was thought to be, at the time, impossible for me to make. I came up with an idea of making a maze solver, a program where you could just point your camera at the maze and it will draw the solution over top of the image. I had no prior knowledge of any of the things needed to even know where to begin, I just dove in head first.
I tried to find a starting point by looking at the source code of open source barcode scanners, this yielded no success however. One day while I was going through wikipedia pages I came across computer vision and this is where everything changed for me. The beauty of CV is that there are infinitely many data sets you can input into the system and it’s up to your program to extract only the relevant things. Upon reading, I found that there were many algorithms already made for exactly what I needed to acomplish, it was just a matter of now setting up my IDE to use the library of my choice, OpenCV through JavaCV that provides wrappers to OpenCV.
Setting up the IDE took quite a while, but after working through many hair pulling bugs I finally got setup and ready to go. Immediately I got my android setup and ready to capture and decode the images, after that it was all up hill from there. After working with the android I found that the time it took at run the code and test it on the phone was taking up a lot of time so I decided to just program it for the computer then when I’m done, port it over to the phone to speed up development. At the beginning there were so many challenges it wasn’t even funny like how to distinguish the maze from objects around it.
After messing around with many functions I finally found that thresholding, canny edge detection and Houghlines were the answer to this problem, getting the right lines however definitely took a lot of time but many println’s later I finally found out which theta’s were needed to get the outer most lines. After getting those lines I took the intersections and warped the matrix containing the maze onto a new image with a fixed size. It is on this new image where a new problem arose, how to get where the entrance and exit lies.
Thinking and messing around for some bit lead me to grabbing the points of the contour that layed on the outer most lines and checking if the distance between points on the same line were roughly separated by the length of the maze lanes. After getting many points that satisfied that criteria I now had to filter them and get the correct two. Simply checking the locations of them and checking how many neighbours were close by, if if was surrounded on 3 sides by black lines and the distance from the edge grabs the right 2. Here is where I now am, the current problem is solving the maze.
To navigate the maze I will probably take the binary image and use K * to iterate through it, the problem lies in the fact that it could just go around the maze and not through it. I took a break from solving it because my school gave out free USB drives and I thought these would be perfect to have a local svn on that I can use to keep track of my changes to work on it at school and home. After encrypting the drive with Truecrypt, so if I lose it no one steals the code, I began to set it up. Like all things in life, it’s never as easy as it seems. I couldn’t install subclipse on eclipse indigo so I tried to update to juno and see if it would work. Nope. I tried installing subversive yet I kept getting errors upon errors when trying to install. After giving up and going to bed, next morning I uninstalled Java SE 7 u7 and went back to 6 u35 and it worked flawlessly. I now have my usb to carry around and keep track of changes. Now it’s time to get back to it and solve this maze.