Sunday, July 14, 2013

Sudoku Grabber and Solver - Part II

In this blog post I want to continue the work on the sudoku solver and use my webcam to grab the sudokus and show the solution right away in the grabbed picture.

Here is a video of a recent version of the application:



This video is in black and white from an earlier version:



And here is a screenshot:


Augmented reality display of a newspaper sudoku


What happened in addition to the last posting on the sudoku2go program is the following:


grabbed images of digits are reused when showing the solution


I thought it would be a nice idea to reuse the digits already available to show the solution. Like that there is no mismatch between the original font used and the fields which are to be filled in. In the screenshot above you can verify that the result really looks as if a solved sudoku was printed (well sort of ;-) )

live grabbing from a continuous stream of pictures


When showing the application to friends this was almost always the first question - here is the newspaper with the sudoku, now solve it! I've added a webcam functionality to the program (reusing code from my isight-java webcam project) which gives an immediate feedback to the user.

border around the whole puzzle


I thought some colored border would provide a better feedback to the user. Using JavaFX for painting such a border is far more powerful and less of a hassle than to use OpenCV's possibilities. Like that you get effects like DropShadow for free.

overlay of the solution on the original input image


Maybe you have a look into the source how I create the sudoku solution by reusing a digit "library" of grabbed images. I'm using JavaFX and its screenshot API to create a picture which then is "rewarped" again by openCV to fit in the original image. This could be improved by just using openCV's Mat class I suppose, which has to be faster, too. Anyway, the "blendMode" feature of JavaFX saved me much (development) time. ;-)


Improved speed


I've measured the performance bottlenecks of the sudoku program, and found some places to be optimized. Specifically I've introduced Scala Futures in order to decide which cell contains which digit (or no digit). After segmentation this is a nice example to apply parallel computation and it turns out this speeds up things considerably. Like this you get a parallel computation of your subtasks, and collect them as they finish.


Ideas to improve the application


Anyway, in its current state the program does what I originally wanted from it - show the webcam the newspaper, you get the solution back right away in augmented reality. As always, there are many ways to improve the application - for example a more intelligent way to recognize the digits, a more responsive ui, using an approach which reuses information collected in the past for the current measurement,  etc... maybe you want to fork the project and give it a spin?




1 comment: