How to remove convexity defects in a Sudoku square?
I have a solution that works, but you'll have to translate it to OpenCV yourself. It's written in Mathematica.
The first step is to adjust the brightness in the image, by dividing each pixel with the result of a closing operation:
src = ColorConvert[Import["http://davemark.com/images/sudoku.jpg"], "Grayscale"];
white = Closing[src, DiskMatrix[5]];
srcAdjusted = Image[ImageData[src]/ImageData[white]]
The next step is to find the sudoku area, so I can ignore (mask out) the background. For that, I use connected component analysis, and select the component that's got the largest convex area:
components =
ComponentMeasurements[
ColorNegate@Binarize[srcAdjusted], {"ConvexArea", "Mask"}][[All,
2]];
largestComponent = Image[SortBy[components, First][[-1, 2]]]
By filling this image, I get a mask for the sudoku grid:
mask = FillingTransform[largestComponent]
Now, I can use a 2nd order derivative filter to find the vertical and horizontal lines in two separate images:
lY = ImageMultiply[MorphologicalBinarize[GaussianFilter[srcAdjusted, 3, {2, 0}], {0.02, 0.05}], mask];
lX = ImageMultiply[MorphologicalBinarize[GaussianFilter[srcAdjusted, 3, {0, 2}], {0.02, 0.05}], mask];
I use connected component analysis again to extract the grid lines from these images. The grid lines are much longer than the digits, so I can use caliper length to select only the grid lines-connected components. Sorting them by position, I get 2x10 mask images for each of the vertical/horizontal grid lines in the image:
verticalGridLineMasks =
SortBy[ComponentMeasurements[
lX, {"CaliperLength", "Centroid", "Mask"}, # > 100 &][[All,
2]], #[[2, 1]] &][[All, 3]];
horizontalGridLineMasks =
SortBy[ComponentMeasurements[
lY, {"CaliperLength", "Centroid", "Mask"}, # > 100 &][[All,
2]], #[[2, 2]] &][[All, 3]];
Next I take each pair of vertical/horizontal grid lines, dilate them, calculate the pixel-by-pixel intersection, and calculate the center of the result. These points are the grid line intersections:
centerOfGravity[l_] :=
ComponentMeasurements[Image[l], "Centroid"][[1, 2]]
gridCenters =
Table[centerOfGravity[
ImageData[Dilation[Image[h], DiskMatrix[2]]]*
ImageData[Dilation[Image[v], DiskMatrix[2]]]], {h,
horizontalGridLineMasks}, {v, verticalGridLineMasks}];
The last step is to define two interpolation functions for X/Y mapping through these points, and transform the image using these functions:
fnX = ListInterpolation[gridCenters[[All, All, 1]]];
fnY = ListInterpolation[gridCenters[[All, All, 2]]];
transformed =
ImageTransformation[
srcAdjusted, {fnX @@ Reverse[#], fnY @@ Reverse[#]} &, {9*50, 9*50},
PlotRange -> {{1, 10}, {1, 10}}, DataRange -> Full]
All of the operations are basic image processing function, so this should be possible in OpenCV, too. The spline-based image transformation might be harder, but I don't think you really need it. Probably using the perspective transformation you use now on each individual cell will give good enough results.
OpenCV - remove gridlines from Sudoku puzzle
If you don't want to make a proper unwarp, it's probably worthwhile to use smaller cells for the digit_present test.
Let's say the top left cell has coordinates (x1,y1,x2,y1)==(0,0,10,10). You could define a new cell as (x1+k,y1+k,x2-k,y2-k), k=min(x2-x1,y2-y1)/4
Another strategy that may work is to use erode before the test, depending on the thickness of the grid lines vs the digits'.
At last, you could feed all the cells to your classifier, and use its confidence indexes, if any; if the classifier confidence is too low, it's probably not a digit.
If all these approaches fails, in order to do a fill you'll have to obtain the warping of the grid lines anyway, so you might as well do the unwarping
How to get the cells of a sudoku grid with OpenCV?
Here's a potential solution:
Obtain binary image. Convert image to grayscale
and adaptive thresholdFilter out all numbers and noise to isolate only boxes. We filter using contour area to remove the numbers since we only want each individual cell
Fix grid lines. Perform morphological closing
with a horizontal and vertical kernel
to repair grid lines.Sort each cell in top-to-bottom and left-to-right order. We organize each cell into a sequential order using
imutils.contours.sort_contours()
with thetop-to-bottom
andleft-to-right
parameter
Here's the initial binary image (left) and filtered out numbers + repaired grid lines + inverted image (right)
Here's a visualization of the iteration of each cell
The detected numbers in each cell
Code
import cv2
from imutils import contours
import numpy as np
# Load image, grayscale, and adaptive threshold
image = cv2.imread('1.png')
gray = cv2.cvtColor(image, cv2.COLOR_BGR2GRAY)
thresh = cv2.adaptiveThreshold(gray,255,cv2.ADAPTIVE_THRESH_GAUSSIAN_C, cv2.THRESH_BINARY_INV,57,5)
# Filter out all numbers and noise to isolate only boxes
cnts = cv2.findContours(thresh, cv2.RETR_TREE, cv2.CHAIN_APPROX_SIMPLE)
cnts = cnts[0] if len(cnts) == 2 else cnts[1]
for c in cnts:
area = cv2.contourArea(c)
if area < 1000:
cv2.drawContours(thresh, [c], -1, (0,0,0), -1)
# Fix horizontal and vertical lines
vertical_kernel = cv2.getStructuringElement(cv2.MORPH_RECT, (1,5))
thresh = cv2.morphologyEx(thresh, cv2.MORPH_CLOSE, vertical_kernel, iterations=9)
horizontal_kernel = cv2.getStructuringElement(cv2.MORPH_RECT, (5,1))
thresh = cv2.morphologyEx(thresh, cv2.MORPH_CLOSE, horizontal_kernel, iterations=4)
# Sort by top to bottom and each row by left to right
invert = 255 - thresh
cnts = cv2.findContours(invert, cv2.RETR_TREE, cv2.CHAIN_APPROX_SIMPLE)
cnts = cnts[0] if len(cnts) == 2 else cnts[1]
(cnts, _) = contours.sort_contours(cnts, method="top-to-bottom")
sudoku_rows = []
row = []
for (i, c) in enumerate(cnts, 1):
area = cv2.contourArea(c)
if area < 50000:
row.append(c)
if i % 9 == 0:
(cnts, _) = contours.sort_contours(row, method="left-to-right")
sudoku_rows.append(cnts)
row = []
# Iterate through each box
for row in sudoku_rows:
for c in row:
mask = np.zeros(image.shape, dtype=np.uint8)
cv2.drawContours(mask, [c], -1, (255,255,255), -1)
result = cv2.bitwise_and(image, mask)
result[mask==0] = 255
cv2.imshow('result', result)
cv2.waitKey(175)
cv2.imshow('thresh', thresh)
cv2.imshow('invert', invert)
cv2.waitKey()
Note: The sorting idea was adapted from an old previous answer in Rubrik cube solver color extraction.
Related Topics
Python Error "Importerror: No Module Named"
Determine Whether Integer Is Between Two Other Integers
Fast Punctuation Removal with Pandas
Convert Pyspark String to Date Format
Getting Python Error "From: Can't Read /Var/Mail/Bio"
Python List in SQL Query as Parameter
Regular Expression to Return Text Between Parenthesis
Regular Expression to Match a Dot
Pip Install MySQL-Python Fails with Environmenterror: MySQL_Config Not Found
Is There a Simple Way to Delete a List Element by Value
Extract First Item of Each Sublist
How to Add Group Labels for Bar Charts in Matplotlib
Replace Values in a Pandas Series via Dictionary Efficiently
How to Include a Folder with Cx_Freeze
What's the Difference Between a Python Module and a Python Package
How to Open Multiple Files Using "With Open" in Python