ECE497 Project Sudoku Solver

From eLinux.org
Revision as of 10:12, 14 November 2017 by Pierceja (talk | contribs) (Updated installation instructions)
Jump to: navigation, search

thumb‎ Embedded Linux Class by Mark A. Yoder


Team members: Joey Pierce, Donglai Guo

Grading Template

I'm using the following template to grade. Each slot is 10 points. 0 = Missing, 5=OK, 10=Wow!

00 Executive Summary
00 Installation Instructions 
00 User Instructions
00 Highlights
00 Theory of Operation
00 Work Breakdown
00 Future Work
00 Conclusions
00 Demo
00 Late
Comments: I'm looking forward to seeing this.

Score:  10/100

(Inline Comment)

Executive Summary

Our project is about implementing a sudoku solver on the BBB. We will first feed the picture of the unsolved 9x9 sudoku grid to the BeagleBone and display it onto the LCD. We are planning on using Google vision to convert the text (numbers) of the picture into a text file. Then we press a GPIO button to trigger the sudoku solver which takes a text file as an input and outputs the solved sudoku grid. The correct result will be shown on the LCD too.

What works: Right now we are using a PlayStation camera to take a picture of our Sudoku board that we send to the Google Vision API. We are now able to use a board with grid lines, but still need to put in zeros for the blank puzzle spots. We are using ImageMagick features to remove the grid lines on the board before sending it to API. We then take the API results and send it to our Sudoku solver. We can then take the final result and use ImageMagick to compose a blank grid onto the Sudoku answers to display a completed puzzle on the LCD Display. Our Sudoku solver came from GitHub: https://github.com/Sanahm/SudoCAM-Ku.

What doesn't work: Our main problem right now is increasing the accuracy of the Google Vision API. Since we are attempting to remove the grid lines with ImageMagick, we found that its a little harder to get a good quality picture that the API can easily detect.

Needed Hardware

In addition to BeagleBoneBlue and a breadboard, you will need:

Hardware Setup

Hardware setup






















  • Connect the SPI and GPIO jumper wires of the LCD screen to S1.1 and GP0 on BBB.
  • Connect GP1 jumper wires to a random spot on the breadboard.
  • Connect GP1_3 (white wire, also third wire from right to left) to one side of a pushbutton.
  • Connect the other side of the button to ground.
  • Connect your webcam to the Beaglebone's USB port.

Installation Instructions

The installation of this project is as follows:

Begin by cloning the the project github repository with the command below:

git clone https://github.com/pierceja/BeagleboneSudoku.git


Make sure you clone this into your home directory as some of the java code depends on specific directory paths and this will prevent you from having to change it. Next you will need to set up a Google Cloud Platform in order to use the Google Vision API. After you have that set up go to your console and select "Getting stated" on the left side of the page. Select "Create an empty project" to use the Vision API for. After you have created a project, you should receive a notification show at the top right of the screen. Select the notification icon and then select your project. This should bring you to the dashboard for your project. Next select "billing" on the right side of the screen and make sure billing is enabled for the project. Go back to the dashboard and select "APIs and services" on the right side of the screen. Search for google cloud vision API and select the option that comes up. Make sure this API is enabled for your project. This should bring you to the dashboard for the vision API. Select "credentials" on the right side of the screen. Select "Create credentials", then select "API key". This will generate an authorization key for your project which is needed when running the program.

To set up authorization for the project, cd into the boggle directory:

cd BeagleboneSudoku/boggle/

Open up the boggle.js file with an editor. Copy the generated key for your project and set it equal to the "key" variable at the top of the boggle.js file.

Next you will need to run the install and setup scripts. First set the permissions for the setup.sh script with the command below:

chmod +x setup.sh

Execute the install and setup script in the BeagleboneSudoku/boggle/ directory:

./install.sh
./setup.sh

Cd into the newly cloned adafruit directory and set up python3:

cd adafruit-beaglebone-io-python
sudo python3 setup.py install

Next cd into the java directory and set the permissions for the setup.sh script:

cd ~/BeagleboneSudoku/boggle/dddddd/src/
chmod +x setup.sh

Then run the setup script:

./setup.sh

Next you will have to set up the drivers for the LCD display. The install script will also install dependencies needed to display images on the LCD screen:

cd ~/BeagleboneSudoku/ili9341/
./install.sh

Finally you will have to change the policy rights for the Imagemagick application. You should have file "etc/ImageMagick-6/policy.xml" on your Beaglebone. Open up this policy file and remove the line that sets zero rights to the "@" command. You will need user permissions to edit this policy file. The line you are looking for should say some along the lines of:

<policy domain="path" rights="none" pattern="@*"/>

You should now be good to go to use this project.


User Instructions

Once everything is installed, how do you use the program? Give details here, so if you have a long user manual, link to it here.

Once everything is installed and set up, you can execute the capture.sh script by doing:

./capture.sh

When this begins to run, the camera will begin capturing frames which will be displayed on the LCD display. You need to capture a clear frame of the Sudoku puzzle you are trying to solve. The challenging part is capturing a frame which shows every row and column clearly. Once you see a frame you like on the LCD display, quickly press

CTRL+C on your keyboard. 

This will initiate the image processing functions on the frame. Once image processing is complete, the processed image will be displayed on the display. If you are satisfied with the image, you can press the GPIO push button to send it to the Google API. The detected digits will be shown on the LCD display. Once this occurs, you can press the push button again to send the digits to the solver. After the solver is complete, the final results will be shown on the display.

Highlights

Here is where you brag about what your project can do.

Our project can solve a Sudoku puzzle from a single frame. It uses some cool image processing features from ImageMagick to remove the grid lines of the Sudoku puzzle and can create a new puzzle grid to display the results. It is also pretty user friendly and just requires a couple GPIO button presses after the frame is captured. Below is video showcasing our project:

Here is a YouTube video of our demo.

Image before Line Removal
Image after Line Removal


The Imagemagick could perform a great job on Line Removal if the image is in good quality. However, it takes almost two minutes to do the processing and it does not work well with the images taken by the camera we are using.











Theory of Operation

Program Flow Chart

The flow of the program can be described as follows:

1. The program starts with a while loop that keeps taking photos until user presses "Ctrl+C" which will capture the image;

2. The image is then processed using ImageMagick to remove grid lines in order to achieve better results; Both orignial image and processed image will be seen on the LCD.

3. Google API will do Digits Recognition on the processed Image and send all numbers in a Json file back to the bone;

4. The program then will convert the json file into a text file from which Java program will get input. The Image from google will also be shown on the LCD;

5. Java program has two parts: The first part is correction.java which is written in an attempt to fix the spacing from Google API(such as spaces, brackets and etc) and make it compatible with the actual solver. The second part is Sukoku.java which is basically an algorithm that will be used to solve the Sudoku.

6. We actually have two versions of correction.java file(one for fixing spacing and the other one for adding 0s). The working one is the first one, the correctionV1.java was correct, but we were having trouble finding the reason why it does not write to output. So, just use the first one not V1 version for testing.

7. Finally, ImageMagick techniques are used to composite two picture (one from soluton.txt and the other one from a boundbox.png) and also final image will be shown on LCD;

Work Breakdown

List the major tasks in your project and who did what.

  • Google Vision API setup-Joey
  • Hardware interfacing-Joey
  • API and solver merging-Joey and Donglai
  • Solver setup and editing-Donglai
  • Image processing work-Donglai

Also list here what doesn't work yet and when you think it will be finished and who is finishing it.

As mentioned above, right now the API is completely accurate. This is being worked on by both of us and should by fixed by Tuesday November 14, 2017.

Future Work

Suggest addition things that could be done with this project.

There are a couple of neat ideas that we came up with that could be added to this project. One idea would be to get a stream from the camera so that it's a bit easier to capture a good frame. Another idea might be using image processing to append zeros to the Sudoku puzzle so that you didn't have to draw them by hand.

Conclusions

The project idea is from https://www.hackster.io because we thought it will be cool to solve a sudoku puzzle using BBB. We primarily thought the project will be just two parts: Acquiring image and Solving. However, as we delve further into this project, we found it quite challenging to get a perfect image using camera. Thus we decided to do some interesting pre-processing and post-processing to improve the results: Imagemagick tricks. We have successfully made the results significantly better with those tricks. For the future, we should probably add a live streaming video of the camera to the project and also use imagemagick to append 0s to empty grids.




thumb‎ Embedded Linux Class by Mark A. Yoder