3

I'm creating a Sudoku solving application on an Android platform and I've run into an issue when processing the image. I'm trying to find the horizontal lines of the puzzle using OpenCV using a Sobel filter and then thresholding with the Otsu algorithm:

Mat kernaly = Imgproc.getStructuringElement(Imgproc.MORPH_RECT, new Size(10,2));
Mat dy = new Mat();
Mat close = new Mat();
Imgproc.Sobel(img, dy, CvType.CV_16S, 0, 2);
Core.convertScaleAbs(dy, dy);
Core.normalize(dy,dy,0,255,Core.NORM_MINMAX);
Imgproc.threshold(dy, close, 0, 255, Imgproc.THRESH_BINARY|Imgproc.THRESH_OTSU);
Imgproc.morphologyEx(close, close, Imgproc.MORPH_DILATE, kernaly);

This method actually works well for most images, for example:

enter image description here

However, it fails for the following image:

enter image description here

Can someone explain why the results are so vastly different and the second image above returns only one line? Also, should I just use another methodology instead, such as Canny or Hough lines?

Thanks in advance!

Edit: Using marol's advice, I tried removing as much of the black border as possible without having to warp the image. This is the result when applying the same process above to these reworked images.

Image 1:

Image 1

Image 2:

Image 2

As you can see, the results are better as most lines have been detected. However, it's still not good enough. It can be improved by adding in a fixed threshold but that has to be different for each image.

I'll probably just use a new approach as this method does not seem to be robust enough. Any tips will be greatly appreciated.

user3577715
  • 31
  • 4
  • " should I just use another methodology instead, such as Canny or Hough lines"? Yes, of course. – Bull Aug 08 '14 at 13:22

3 Answers3

1

The problem might be caused due to intensity distribuition. If you look at the histogram after sobel operator:

enter image description here

compare it with histogram of image with successfull otsu detection:

enter image description here

you can easily see in the first histogram failed because computed threshold was rather moved to the right instead to the left (even though there is major peak on the left stands out for all black pixels). And in the second case, distribution is no so divided into the peak and the flat rest, rather than we have a situation that there are more white pixels that "carried" computed threshold to the right.

In other words, you have to get rid of domination of black pixels. In other words, try to scale the sudoku so that the black pixel border around is as minimal as possible. That will make distribution more like in the second case.

IMHO from those histograms you can say the method is quite sensitive, because the difference between "black" and "white" parts in the image so the computed threshold level is very sensitive to an image. I would not depend on this approach. What about some fixed threshold level? It might sound not good in general case, but here it might work more deterministic and still correct.

marol
  • 4,034
  • 3
  • 22
  • 31
  • Thanks, I will try to cut out as much of the black border as possible for both images and see how that works. I will edit the results into the original question. I did try to add a fixed threshold but the results were too different for each image so I decided it was too inconsistent to use. – user3577715 Aug 09 '14 at 06:42
1

An alternate suggestion instead of otsu:

You could search for local maxima in Y-direction in the sobel image.

  • Dilate the sobel image with a 1x10 rectangular kernel ('10' should be the minimum distance between grid lines in your images)
  • compare the dilated image with the original, setting all pixels to zero that are not equal ( cmp(dy,dilatedImg,comparisonImg,CMP_GE )
  • remove all areas without any local maxima ( threshold(dy, mask, 1, 255, THRESH_BINARY); And(comparisonImg, mask, comparisonImg); )

Now you have all the pixels that correspond to the strongest horizontal edge in the local area.

a sidenote, your usage of sobel is a little strange:

You take the second sobel derivate with Imgproc.Sobel(img, dy, CvType.CV_16S, 0, 2); I assume you do this because you want to identify the center of the black lines, and not their border. But in that case, the next step, convertScaleAbs, seems counterintuitive. That way you get the minima as well as the maxima of the second sobel derivate. The maxima should correspond to the centers of the black lines, but the minima introduce the weird 'tripple line' artifacts visible in your edge image. The Abs step would be more reasonable if you where using the first sobel derivate, but in you case it might work better to discard negative values.

HugoRune
  • 13,157
  • 7
  • 69
  • 144
  • Thanks for that, I'll try out that method and will post the results in the original question. The reason I use the second derivative and the Abs for Sobel was so that it could read the right most vertical line. I practically use the same method for both vertical and horizontal although maybe I shouldn't, I guess. If it helps, I basically followed the process here: [link](http://stackoverflow.com/questions/10196198/how-to-remove-convexity-defects-in-a-sudoku-square/11366549#11366549) – user3577715 Aug 10 '14 at 14:33
0

I found a quick fix that improves the results quite significantly by doing some image processing before running the code above:

  1. I just did as marol suggested above and cut as much of the black border out as possible.
  2. Resized the images, using warpPerspective, so that it became a square of a standard size.
  3. Ran the code above and then dilated the result.

Its not the most robust solution but it works for all 10 of my test image samples.

user3577715
  • 31
  • 4