How to detect Sudoku grid board in OpenCV

Question

I'm working on a personal project using opencv in python. Want to detect a sudoku grid.

The original image is:

So far I have created this:

Then tried to select a big blob. Result may be similar to this:

I got a black image as result:

The code is:

import cv2
import numpy as np

def find_biggest_blob(outerBox):
   max = -1
   maxPt = (0, 0)

   h, w = outerBox.shape[:2]
   mask = np.zeros((h + 2, w + 2), np.uint8)

   for y in range(0, h):
     for x in range(0, w):

       if outerBox[y, x] >= 128:

         area = cv2.floodFill(outerBox, mask, (x, y), (0, 0, 64))


   #cv2.floodFill(outerBox, mask, maxPt, (255, 255, 255))

   image_path = 'Images/Results/sudoku-find-biggest-blob.jpg'

   cv2.imwrite(image_path, outerBox)

   cv2.imshow(image_path, outerBox)


 def main():
   image = cv2.imread('Images/Test/sudoku-grid-detection.jpg', 0)

   find_biggest_blob(image)

   cv2.waitKey(0)

   cv2.destroyAllWindows() 


if __name__ == '__main__':
   main()

The code in repl is: https://repl.it/@gmunumel/SudokuSolver

Any idea?

Answer 1

Here is my solution that will generalize to any image whether it is warped or not.

• Convert the image to grayscale
• Apply adaptive thresholding to convert the image to binary (Adaptive thresholding works better than normal thresholding because the original image can have different lighting at different areas)
• Identify the Corners of the large square
• Perspective transform of the image to the final square image

Depending on the amount of skewness of the original image the corners identified may be out of order, do we need to arrange them in the correct order. the method used here is to identify the centroid of the large square and identify the order of the corners from there

Here is the code:

import cv2
import numpy as np



    # Helper functions for getting square image

def euclidian_distance(point1, point2):
    # Calcuates the euclidian distance between the point1 and point2
    #used to calculate the length of the four sides of the square 
    distance = np.sqrt((point1[0] - point2[0]) ** 2 + (point1[1] - point2[1]) ** 2)
    return distance


def order_corner_points(corners):
    # The points obtained from contours may not be in order because of the skewness  of the image, or
    # because of the camera angle. This function returns a list of corners in the right order 
    sort_corners = [(corner[0][0], corner[0][1]) for corner in corners]
    sort_corners = [list(ele) for ele in sort_corners]
    x, y = [], []

    for i in range(len(sort_corners[:])):
        x.append(sort_corners[i][0])
        y.append(sort_corners[i][1])

    centroid = [sum(x) / len(x), sum(y) / len(y)]

    for _, item in enumerate(sort_corners):
        if item[0] < centroid[0]:
            if item[1] < centroid[1]:
                top_left = item
            else:
                bottom_left = item
        elif item[0] > centroid[0]:
            if item[1] < centroid[1]:
                top_right = item
            else:
                bottom_right = item

    ordered_corners = [top_left, top_right, bottom_right, bottom_left]

    return np.array(ordered_corners, dtype="float32")
def image_preprocessing(image, corners):
    # This function undertakes all the preprocessing of the image and return  
    ordered_corners = order_corner_points(corners)
    print("ordered corners: ", ordered_corners)
    top_left, top_right, bottom_right, bottom_left = ordered_corners

    # Determine the widths and heights  ( Top and bottom ) of the image and find the max of them for transform 

    width1 = euclidian_distance(bottom_right, bottom_left)
    width2 = euclidian_distance(top_right, top_left)

    height1 = euclidian_distance(top_right, bottom_right)
    height2 = euclidian_distance(top_left, bottom_right)

    width = max(int(width1), int(width2))
    height = max(int(height1), int(height2))

    # To find the matrix for warp perspective function we need dimensions and matrix parameters
    dimensions = np.array([[0, 0], [width, 0], [width, width],
                           [0, width]], dtype="float32")

    matrix = cv2.getPerspectiveTransform(ordered_corners, dimensions)

    # Return the transformed image
    transformed_image = cv2.warpPerspective(image, matrix, (width, width))

    #Now, chances are, you may want to return your image into a specific size. If not, you may ignore the following line
    transformed_image = cv2.resize(transformed_image, (252, 252), interpolation=cv2.INTER_AREA)

    return transformed_image

    # main function

def get_square_box_from_image(image):
    # This function returns the top-down view of the puzzle in grayscale.
    # 

    gray = cv2.cvtColor(image, cv2.COLOR_BGR2GRAY)
    blur = cv2.medianBlur(gray, 3)
    adaptive_threshold = cv2.adaptiveThreshold(blur, 255, cv2.ADAPTIVE_THRESH_MEAN_C, cv2.THRESH_BINARY_INV, 11, 3)
    corners = cv2.findContours(adaptive_threshold, cv2.RETR_EXTERNAL, cv2.CHAIN_APPROX_SIMPLE)
    corners = corners[0] if len(corners) == 2 else corners[1]
    corners = sorted(corners, key=cv2.contourArea, reverse=True)
    for corner in corners:
        length = cv2.arcLength(corner, True)
        approx = cv2.approxPolyDP(corner, 0.015 * length, True)
        print(approx)

        puzzle_image = image_preprocessing(image, approx)
        break
    return puzzle_image

    # Call the get_square_box_from_image method on any sudoku image to get the top view of the puzzle

original = cv2.imread("large_puzzle.jpg")

sudoku = get_square_box_from_image(original)

Here are the results from the given image and a custom example

Answer 2

Here's an approach:

• Convert image to grayscale and median blur to smooth image
• Adaptive threshold to obtain binary image
• Find contours and filter for largest contour
• Perform perspective transform to obtain top-down view

---

After converting to grayscale and median blurring, we adaptive threshold to obtain a binary image

Next we find contours and filter using contour area. Here's the detected board

Now to get a top-down view of the image, we perform a perspective transform. Here's the result

import cv2
import numpy as np

def perspective_transform(image, corners):
    def order_corner_points(corners):
        # Separate corners into individual points
        # Index 0 - top-right
        #       1 - top-left
        #       2 - bottom-left
        #       3 - bottom-right
        corners = [(corner[0][0], corner[0][1]) for corner in corners]
        top_r, top_l, bottom_l, bottom_r = corners[0], corners[1], corners[2], corners[3]
        return (top_l, top_r, bottom_r, bottom_l)

    # Order points in clockwise order
    ordered_corners = order_corner_points(corners)
    top_l, top_r, bottom_r, bottom_l = ordered_corners

    # Determine width of new image which is the max distance between 
    # (bottom right and bottom left) or (top right and top left) x-coordinates
    width_A = np.sqrt(((bottom_r[0] - bottom_l[0]) ** 2) + ((bottom_r[1] - bottom_l[1]) ** 2))
    width_B = np.sqrt(((top_r[0] - top_l[0]) ** 2) + ((top_r[1] - top_l[1]) ** 2))
    width = max(int(width_A), int(width_B))

    # Determine height of new image which is the max distance between 
    # (top right and bottom right) or (top left and bottom left) y-coordinates
    height_A = np.sqrt(((top_r[0] - bottom_r[0]) ** 2) + ((top_r[1] - bottom_r[1]) ** 2))
    height_B = np.sqrt(((top_l[0] - bottom_l[0]) ** 2) + ((top_l[1] - bottom_l[1]) ** 2))
    height = max(int(height_A), int(height_B))

    # Construct new points to obtain top-down view of image in 
    # top_r, top_l, bottom_l, bottom_r order
    dimensions = np.array([[0, 0], [width - 1, 0], [width - 1, height - 1], 
                    [0, height - 1]], dtype = "float32")

    # Convert to Numpy format
    ordered_corners = np.array(ordered_corners, dtype="float32")

    # Find perspective transform matrix
    matrix = cv2.getPerspectiveTransform(ordered_corners, dimensions)

    # Return the transformed image
    return cv2.warpPerspective(image, matrix, (width, height))

image = cv2.imread('1.jpg')
original = image.copy()
gray = cv2.cvtColor(image, cv2.COLOR_BGR2GRAY)
blur = cv2.medianBlur(gray, 3)
thresh = cv2.adaptiveThreshold(blur,255,cv2.ADAPTIVE_THRESH_GAUSSIAN_C, cv2.THRESH_BINARY_INV,11,3)

cnts = cv2.findContours(thresh, cv2.RETR_EXTERNAL, cv2.CHAIN_APPROX_SIMPLE)
cnts = cnts[0] if len(cnts) == 2 else cnts[1]
cnts = sorted(cnts, key=cv2.contourArea, reverse=True)

for c in cnts:
    peri = cv2.arcLength(c, True)
    approx = cv2.approxPolyDP(c, 0.015 * peri, True)
    transformed = perspective_transform(original, approx)
    break

cv2.imshow('transformed', transformed)
cv2.imwrite('board.png', transformed)
cv2.waitKey()