6

I'm writing an app that recognizes Sudoku puzzles from a camera input. I'd like to remove camera blur from the images to improve recognition. Here is an example image:

enter image description here

Since I'm processing a continuous camera feed, I'm concerned about speed, since slow algorithms will degrade my frame rate. On the other hand, the technique doesn't have to be super-accurate, since I will be thresholding/binarizing the image afterwards. The deblurring algorithm I use only needs to be accurate enough so that the digits will be clear after thresholding. Here is what the image currently looks like after a segmented Otsu threshold (the threshold level is selected independently for each 3x3 grid of cells):

enter image description here

I'm looking to write an implementation that's compatible with OpenCV data structures. This means that an off-the-shelf Matlab solution isn't an option. However, I found the Matlab documentation on image deblurring to be quite helpful in understanding the general principles, as well as this site. The Matlab functions are all computationally-intensive in any case, and I wasn't able to pick an estimated point-spread function (PSR) that gave good results.

What are your suggestions for a fast deblurring algorithm that allows features to be distinguished easily by a subsequent threshold?

1''
  • 113
  • 6
  • 3
    Are you sure deblurring is necessary? A neural network-based OCR should be able to recognise those blurred digits just fine. – finnw May 10 '13 at 18:52
  • I'm using a Support Vector Machine, using Histograms of Oriented Gradients as feature vectors. The recognition accuracy is low, even if the SVM is trained on blurry digits like these. – 1'' May 10 '13 at 19:23
  • You don't need to deblur, and I don't think you need to do continuous processing either. I assume you want to do some kind of augmented reality thing - take one good frame, process it in the background, then when it is done, overlay information adjusting the projection by just tracking the lines. – geometrikal May 11 '13 at 12:24
  • @geometrikal I only continuously process until I find a single valid (solvable) frame, but often I can't even do that, even if my hand is as still as possible. – 1'' May 11 '13 at 14:39
  • 2
    Some inspiration (solving sudoku using matlab and a webcam): http://www.mathworks.com.au/videos/solving-a-sudoku-puzzle-using-a-webcam-68773.html http://www.mathworks.com.au/matlabcentral/fileexchange/30088?s_iid=ovp_custom1_1363799529001-68773_rr – geometrikal May 13 '13 at 03:17
  • I would try median filtering. See http://en.wikipedia.org/wiki/Median_filter and http://www.mathworks.se/help/images/ref/medfilt2.html – dsp-guy May 17 '13 at 19:18
  • @dsp-guy Wouldn't that just make the image blurrier? I'm not having an issue with noise, since I already Gaussian blur in a previous step. – 1'' May 17 '13 at 19:35
  • Can you post the image prior to the gaussian blurring step, straight out of the camera? It sounds like you are Gaussian blurring to remove noise, then want to deblur to threshold. There might be other ways to do this. – geometrikal May 18 '13 at 06:17
  • I'm sorry, I was inexact. I use the Gaussian blur in the very first step, before the images shown above, to find the contour of the Sudoku puzzle so I can warp it to a square. The images above haven't been Gaussian blurred. – 1'' May 18 '13 at 17:34

1 Answers1

1

You only need to find and report positions of nine specific symbols. You can do this by computing correlations (done quickly by multiplying in Fourier space) with samples of the nine digits snipped from a typical puzzle image, blurred as it is. All blurred '9' will look the same, and likewise all other digits. I'm assuming puzzle images are taken with the same camera the same way.

It might work better working on high-pass filtered versions of the input puzzle image and image snips, by subtracting from each a more-blurred copy.

DarenW
  • 206
  • 1
  • 6