Goal

• From an image of a Sudoku puzzle, extract and (optional) solve the puzzle.

Goal elements

• Extract the puzzle from the image (reshape image).
• Identify the numbers in each cell. – Correlate the numbers to their respective cell position.

• (optional) Solve the puzzle and display solution over image (projectin solution to image)

Step 1: Basic Info

The main taks of this project is to use Intel Edison to recognize digits on sudoku images which are captured from standard digital camera.

The program accepts an image of Sudoku as input, returns recognized sudoku digits, and (optional) you can use those digits to solve Sudoku.

The mathematical tool I use here is Template Matching (known also as Matched filter).

The software used here is Ubilinux, which is basically based on debian.

Step 2: Software

The Ubilinux is basically based on debian, so that means it use a standard Debian package repositories.It is targeted at embedded devices that have limited memory and storage capabilities.

The distribution contains C, C++ compilers, Perl, Python, Node.JS, as well as a sketch downloader for

compatibility with the Edison Arduino IDE.

Further more, you install programs like on Debian/Ubuntu simply by writting in terminal apt-get .

I used GNU Octave for the recognition of numbers from sudoku images. The Octave is a software alternative to Matlab.

Octave has a lot of functions, and also normxcorr2() function. This function implements normalizes cross-corelation between two images. You can see more info on this function here: http://octave.sourceforge.net/image/function/normxcorr2.html.

Step 3: How to Install Ubilinux on Intel® Edison

If you have been playing with the Edison, you already saw that it comes with preinstalled Yocto Linux which can be difficult to work with. Clearly, you need to re-build Linux from scratch every time you need to enable a package. Besides that, Ubilinux on Edison enables a few important features (for example WiFi).

This is a summary of the ubilinux image features for Intel® Edison platform.

* ubilinux is based on Debian 7 "Wheezy"

* Included latest Intel® kernel patches for Edison with the following changes, added: FTDI, USB Video Class (UVC), USD Audio, USB modem

* WiFi client and AP mode including CRDA module

* Bluez 5.28 with Gatttools

* git

* out of the box support for the following programming/scripting languages: C, C++, Python, Perl, Javascript (nodejs), Shell

*MRAA

*Swig

This instruction describes how to install ubilinux on your Intel® Edison platform.

Requirements: Intel® Edison with mini breakout board or Intel® Edison with Arduino baseboard

Host PC with Linux OS and software to flash Edison boards (dfu-util), please refer to the tutorial on the Intel DocumentationPower supply (only for Edison with Arduino baseboard)

*2 x USB 2.0 A To Micro B cable,

Default credentials are needed for the installed system

*username: root

*password: edison

You need (optional) to update the password once the system has been installed using the passwd command.

Note

*The host machine must be capable of running the flashall script in the distribution package.

*This will involve installing device drivers as described in the Getting Started section on the Intel website http://www.intel.com/support/maker/edison.htm#how

Installation instructions:

1. Extract the content of ubilinux-edison-yymmdd.tar.gz into a directory on your host machine.

From the terminal tar xvfz ubilinux-edison-yymmdd.tar.gz

Move to the "toFlash" folder, You should see the flashall.sh (or flashall.bat) script along with all the other files for the image.

2. Power down the Edison. You may need to disconnect one of the USB cables.

3. Run ‘flashall.sh’ on the host machine.

4. Connect the Edison to the host machine using the usb cables. If you are using an arduino baseboard, it is recommended that you also connect an external power supply shortly after connecting the USB cable.

5. The flash process should now start, and you can see the progress on the host machine terminal. You can monitor the console output on the second USB connection, and also get a login console once the flashing process is complete.

6. When the flashing process is complete, the Edison will reboot twice. The first time it sets up partitions, ssh keys, WiFi ssid, etc. The second time it will boot normally, and present a login prompt on the serial console.

7. To connect to the serial console, use putty on windows or a terminal (linux or mac), changing the baudrate to 115200 and specify the serial port as recognised by your system.

8. You can login providing the default credentials (username: root, password: edison).

9. Ethernet over USB functionality is available, and the default IP of the Edison is 192.168.2.15

Installing new software

apt-get update

apt-get install name_of_the_package

WiFi Support

Wifi drivers are installed, just edit ./etc/network/interfaces appropriately and run ‘ifup wlan0’

Enable WiFi

After logging into Ubilinux, you will probably want an Internet connection so you can download and install packages easily. There will be shown the simplest way, but the drawback of this method is that your WiFi password is unencrypted and stored in plain text in a file.

If you are logged in as a regular user, run the command: su ,and enter the password for root to gain superuser abilities.

The easiest way to get on a local WiFi Access Point is to store the SSID and password in a file. The problem is that your password will be stored in plain text, so it is not very secure. Use your favorite Linux text editor to open the interfaces file: vi /etc/network/interfaces Find “auto usb0” and add a “#” in front of the line to comment it out. Navigate down and remove the “#” in front of “auto wlan0” so that our Edison will try to automatically connect to WiFi on boot. Go down to the “wpa-ssid” and “wpa-psk” lines. Change the default SSID and password (PSK) to your desired WiFi SSID and password. Save changes you've made to your file, and that's it. Voila, you have now internet connection.

Step 4: Algorithm and Installing GNU Octave

This step doesn't require too much time. You just enter: apt-get install octave (assuming you are still logged in as administrator). The code and all test files are in code.rar file.

A little explanation: The sudoku image is preprocessed, reshaped into a track of numbers and the matched filter is applied, so template digits are matched on original image.

You run the code by typing at terminal: octave run

code.rar
Download

Step 5: Recognized Sudoku and Further Work

You can see that the algorithm works perfectly. Further work could be solving sudoku, and using neural networks, and creating "real-time" algorithm, interfacing webcam with Intel Edison,which could recognize digits and project a solution of sudoku, and show the solution in browser (this can be done using node.js).

If you are interested more in this topic, the references are below.

References:

Lewis, J. P., "Fast Normalized Cross-Correlation," Industrial Light & Magic

Haralick, Robert M., and Linda G. Shapiro, Computer and Robot Vision, Volume II, Addison-Wesley, 1992, pp. 316-317.

Smart Sudoku Solver, Agarwal Vinayak, Kamat Tarcar Anand, Kurian Shalini Deparmtent of Electrical Engineering, Stanford Univeristy

Martin Byröd, An Optical Sudoku Solver

Jennifer Ding, Omar Turk, Sean Peters, Sai Supreeth Mannava, License Plate Recognition Matched Filter Technique