Threshold of blurry image - part 2

Question

How can I threshold this blurry image to make the digits as clear as possible?

In a previous post, I tried adaptively thresholding a blurry image (left), which resulted in distorted and disconnected digits (right):

Since then, I've tried using a morphological closing operation as described in this post to make the brightness of the image uniform:

If I adaptively threshold this image, I don't get significantly better results. However, because the brightness is approximately uniform, I can now use an ordinary threshold:

This is a lot better than before, but I have two problems:

1. I had to manually choose the threshold value. Although the closing operation results in uniform brightness, the level of brightness might be different for other images.
2. Different parts of the image would do better with slight variations in the threshold level. For instance, the 9 and 7 in the top left come out partially faded and should have a lower threshold, while some of the 6s have fused into 8s and should have a higher threshold.

I thought that going back to an adaptive threshold, but with a very large block size (1/9th of the image) would solve both problems. Instead, I end up with a weird "halo effect" where the centre of the image is a lot brighter, but the edges are about the same as the normally-thresholded image:

Edit: remi suggested morphologically opening the thresholded image at the top right of this post. This doesn't work too well. Using elliptical kernels, only a 3x3 is small enough to avoid obliterating the image entirely, and even then there are significant breakages in the digits:

Edit2: mmgp suggested using a Wiener filter to remove blur. I adapted this code for Wiener filtering in OpenCV to OpenCV4Android, but it makes the image even blurrier! Here's the image before (left) and after filtering with my code and a 5x5 kernel:

Here is my adapted code, which filters in-place:

private void wiener(Mat input, int nRows, int nCols) { // I tried nRows=5 and nCols=5

    Mat localMean = new Mat(input.rows(), input.cols(), input.type());
    Mat temp = new Mat(input.rows(), input.cols(), input.type());
    Mat temp2 = new Mat(input.rows(), input.cols(), input.type());

    // Create the kernel for convolution: a constant matrix with nRows rows 
    // and nCols cols, normalized so that the sum of the pixels is 1.
    Mat kernel = new Mat(nRows, nCols, CvType.CV_32F, new Scalar(1.0 / (double) (nRows * nCols)));

    // Get the local mean of the input.  localMean = convolution(input, kernel)
    Imgproc.filter2D(input, localMean, -1, kernel, new Point(nCols/2, nRows/2), 0); 

    // Get the local variance of the input.  localVariance = convolution(input^2, kernel) - localMean^2 
    Core.multiply(input, input, temp);  // temp = input^2
    Imgproc.filter2D(temp, temp, -1, kernel, new Point(nCols/2, nRows/2), 0); // temp = convolution(input^2, kernel)
    Core.multiply(localMean, localMean, temp2); //temp2 = localMean^2
    Core.subtract(temp, temp2, temp); // temp = localVariance = convolution(input^2, kernel) - localMean^2  

    // Estimate the noise as mean(localVariance)
    Scalar noise = Core.mean(temp);

    // Compute the result.  result = localMean + max(0, localVariance - noise) / max(localVariance, noise) * (input - localMean)

    Core.max(temp, noise, temp2); // temp2 = max(localVariance, noise)

    Core.subtract(temp, noise, temp); // temp = localVariance - noise
    Core.max(temp, new Scalar(0), temp); // temp = max(0, localVariance - noise)

    Core.divide(temp, temp2, temp);  // temp = max(0, localVar-noise) / max(localVariance, noise)

    Core.subtract(input, localMean, input);  // input = input - localMean
    Core.multiply(temp, input, input); // input = max(0, localVariance - noise) / max(localVariance, noise) * (input - localMean)
    Core.add(input, localMean, input); // input = localMean + max(0, localVariance - noise) / max(localVariance, noise) * (input - localMean)
}

Answer 1

Some hints that you might try out:

• Apply the morphological opening in your original thresholded image (the one which is noisy at the right of the first picture). You should get rid of most of the background noise and be able to reconnect the digits.

• Use a different preprocessing of your original image instead of morpho closing, such as median filter (tends to blur the edges) or bilateral filtering which will preserve better the edges but is slower to compute.

• As far as threshold is concerned, you can use CV_OTSU flag in the cv::threshold to determine an optimal value for a global threshold. Local thresholding might still be better, but should work better with the bilateral or median filter

Answer 2

I've tried thresholding each 3x3 box separately, using Otsu's algorithm (CV_OTSU - thanks remi!) to determine an optimal threshold value for each box. This works a bit better than thresholding the entire image, and is probably a bit more robust.

Better solutions are welcome, though.

Answer 3

If you're willing to spend some cycles on it there are de-blurring techniques that could be used to sharpen up the picture prior to processing. Nothing in OpenCV yet but if this is a make-or-break kind of thing you could add it.

There's a bunch of literature on the subject: http://www.cse.cuhk.edu.hk/~leojia/projects/motion_deblurring/index.html http://www.google.com/search?q=motion+deblurring

And some chatter on the OpenCV mailing list: http://tech.groups.yahoo.com/group/OpenCV/message/20938

The weird "halo effect" that you're seeing is likely due to OpenCV assuming black for the color when the adaptive threshold is at/near the edge of the image and the window that it's using "hangs over" the edge into non-image territory. There are ways to correct for this, most likely you would make an temporary image that's at least two full block-sizes taller and wider than the image from the camera. Then copy the camera image into the middle of it. Then set the surrounding "blank" portion of the temp image to be the average color of the image from the camera. Now when you perform the adaptive threshold the data at/near the edges will be much closer to accurate. It won't be perfect since its not a real picture but it will yield better results than the black that OpenCV is assuming is there.

Answer 4

My proposal assumes you can identify the sudoku cells, which I think, is not asking too much. Trying to apply morphological operators (although I really like them) and/or binarization methods as a first step is the wrong way here, in my opinion of course. Your image is at least partially blurry, for whatever reason (original camera angle and/or movement, among other reasons). So what you need is to revert that, by performing a deconvolution. Of course asking for a perfect deconvolution is too much, but we can try some things.

One of these "things" is the Wiener filter, and in Matlab, for instance, the function is named deconvwnr. I noticed the blurry to be in the vertical direction, so we can perform a deconvolution with a vertical kernel of certain length (10 in the following example) and also assume the input is not noise free (assumption of 5%) -- I'm just trying to give a very superficial view here, take it easy. In Matlab, your problem is at least partially solved by doing:

f = imread('some_sudoku_cell.png');
g = deconvwnr(f, fspecial('motion', 10, 90), 0.05));
h = im2bw(g, graythresh(g)); % graythresh is the Otsu method

Here are the results from some of your cells (original, otsu, otsu of region growing, morphological enhanced image, otsu from morphological enhanced image with region growing, otsu of deconvolution):

The enhanced image was produced by performing original + tophat(original) - bottomhat(original) with a flat disk of radius 3. I manually picked the seed point for region growing and manually picked the best threshold.

For empty cells you get weird results (original and otsu of deconvlution):

But I don't think you would have trouble to detect whether a cell is empty or not (the global threshold already solves it).

EDIT:

Added the best results I could get with a different approach: region growing. I also attempted some other approaches, but this was the second best one.