How do I find the center of multiple boxes in OpenCV?

Question

I'm writing a python script that takes in a video input and should find the center of a tick tack toe board. As of right now I was able to find the contours of the board, but I don't know how to move forward in regards to finding the center of each little box.

Here's the code:

import numpy as np
import cv2

video = cv2.VideoCapture(0)
    
while 1:
    ret, frame = video.read()
    gray = cv2.cvtColor(frame, cv2.COLOR_BGR2GRAY)
    blur = cv2.medianBlur(gray, 3)
    thresh = cv2.adaptiveThreshold(blur, 255, 1, 1, 11, 2)
    contours, _ = cv2.findContours(thresh, cv2.RETR_TREE, cv2.CHAIN_APPROX_SIMPLE)

    c = 0
    for i in contours:
           area = cv2.contourArea(i)
           if area > 200:
                cv2.drawContours(frame, contours, c, (0, 255, 0), 3)
           c+=1
    cv2.imshow("frame", frame)
    if cv2.waitKey(1) & 0xFF == ord('q'):
       break

and here's the frames that I'm getting:

Answer 1

The Concept

1. Use a basic algorithm to find the contours in the image. In this case, only 2 contours will be detected; the entire tic-tac-toe grid, and the center box of the tic-tac-toe grid.

2. Get the convex hull of the 2 contours, and sort them so that we know where to access the top-left point, top-right point, etc. of each of the 2 sets of points:

3. With the information we can calculate the center of each box. For each of the 4 corner boxes, simply find the center of the tip of the 2 lines that make up the boxes. For the rest of the boxes, simply find the center of the 4 points that make up the boxes:

The Code

import cv2
import numpy as np

def process(img):
    img_gray = cv2.cvtColor(img, cv2.COLOR_BGR2GRAY)
    img_blur = cv2.GaussianBlur(img_gray, (5, 5), 0)
    img_canny = cv2.Canny(img_blur, 0, 100)
    kernel = np.ones((2, 2))
    img_dilate = cv2.dilate(img_canny, kernel, iterations=8)
    return cv2.erode(img_dilate, kernel, iterations=2)

def convex_hull(cnt):
    peri = cv2.arcLength(cnt, True)
    approx = cv2.approxPolyDP(cnt, peri * 0.02, True)
    return cv2.convexHull(approx).squeeze()

def centers(inner, outer):
    c = inner[..., 0].argsort()
    top_lef2, top_rit2 = sorted(inner[c][:2], key=list)
    bot_lef2, bot_rit2 = sorted(inner[c][-2:], key=list)
    c1 = outer[..., 0].argsort()
    c2 = outer[..., 1].argsort()
    top_lef, top_rit = sorted(outer[c1][:2], key=list)
    bot_lef, bot_rit = sorted(outer[c1][-2:], key=list)
    lef_top, lef_bot = sorted(outer[c2][:2], key=list)
    rit_top, rit_bot = sorted(outer[c2][-2:], key=list)
    yield inner.mean(0)
    yield np.mean([top_lef, top_rit, top_lef2, top_rit2], 0)
    yield np.mean([bot_lef, bot_rit, bot_lef2, bot_rit2], 0)
    yield np.mean([lef_top, lef_bot, top_lef2, bot_lef2], 0)
    yield np.mean([rit_top, rit_bot, top_rit2, bot_rit2], 0)
    yield np.mean([top_lef, lef_top], 0)
    yield np.mean([bot_lef, lef_bot], 0)
    yield np.mean([top_rit, rit_top], 0)
    yield np.mean([bot_rit, rit_bot], 0)
    
img = cv2.imread(r"D:/OpenCV Projects/TicTacToe centers/tictactoe.png")
contours, _ = cv2.findContours(process(img), cv2.RETR_LIST, cv2.CHAIN_APPROX_NONE)
inner, outer = sorted(map(convex_hull, contours), key=len)

for x, y in centers(inner, outer):
    cv2.circle(img, (int(x), int(y)), 5, (0, 0, 255), -1)

cv2.imshow("result", img)
cv2.waitKey(0)

The Output

The Explanation

1. Import the necessary libraries:

import cv2
import numpy as np

2. Define a function, process(), that takes in an image array and returns a binary image (that is the processed version of the image) that will allow proper contour detection on the image later on:

def process(img):
    img_gray = cv2.cvtColor(img, cv2.COLOR_BGR2GRAY)
    img_blur = cv2.GaussianBlur(img_gray, (5, 5), 0)
    img_canny = cv2.Canny(img_blur, 0, 100)
    kernel = np.ones((2, 2))
    img_dilate = cv2.dilate(img_canny, kernel, iterations=8)
    return cv2.erode(img_dilate, kernel, iterations=2)

3. Define a function, convex_hull(), that takes in a contour array and returns an array that is the convex hull of the approximated version of the contour:

def convex_hull(cnt):
    peri = cv2.arcLength(cnt, True)
    approx = cv2.approxPolyDP(cnt, peri * 0.02, True)
    return cv2.convexHull(approx).squeeze()

4. Define a function, centers(), that takes in two arrays; the convex hull of the inner box of the tic-tac-toe grid, and the convex hull of the entire tic-tac-toe grid. In the function, do the necessary sorting so that each individual point is in a variable with the variable name corresponding to the position of the point; this will allow for easy calculation of each center point:

def centers(inner, outer):
    c = inner[..., 0].argsort()
    top_lef2, top_rit2 = sorted(inner[c1][:2], key=list)
    bot_lef2, bot_rit2 = sorted(inner[c1][-2:], key=list)
    c1 = outer[..., 0].argsort()
    c2 = outer[..., 1].argsort()
    top_lef, top_rit = sorted(outer[c1][:2], key=list)
    bot_lef, bot_rit = sorted(outer[c1][-2:], key=list)
    lef_top, lef_bot = sorted(outer[c2][:2], key=list)
    rit_top, rit_bot = sorted(outer[c2][-2:], key=list)

5. Still within the center() function, yield the center of the boxes. The np.mean() method, when using 0 as the axis keyword argument, will return the center of the coordinates that are in the array of coordinates passed into the method:

    yield inner.mean(0)
    yield np.mean([top_lef, top_rit, top_lef2, top_rit2], 0)
    yield np.mean([bot_lef, bot_rit, bot_lef2, bot_rit2], 0)
    yield np.mean([lef_top, lef_bot, top_lef2, bot_lef2], 0)
    yield np.mean([rit_top, rit_bot, top_rit2, bot_rit2], 0)
    yield np.mean([top_lef, lef_top], 0)
    yield np.mean([bot_lef, lef_bot], 0)
    yield np.mean([top_rit, rit_top], 0)
    yield np.mean([bot_rit, rit_bot], 0)

6. Read in the image, find its contours (also using the process() function to process the image first), find the convex hulls of the contours, and draw on the center of the boxes with the centers() function:

img = cv2.imread(r"D:/OpenCV Projects/TicTacToe centers/tictactoe.png")
contours, _ = cv2.findContours(process(img), cv2.RETR_LIST, cv2.CHAIN_APPROX_NONE)
inner, outer = sorted(map(convex_hull, contours), key=len)

for x, y in centers(inner, outer):
    cv2.circle(img, (int(x), int(y)), 5, (0, 0, 255), -1)

7. Finally, show the resulting image:

cv2.imshow("result", img)
cv2.waitKey(0)

Answer 2

I don't think this is the right approach, since the tick-tack-toe board lines are connected, we will most likely always end up with a single large contour. To make things simple for your purpose, what you could try is detecting lines in the image.

You can try cv2.HoughLinesP or cv2.createLineSegmentDetector to identify lines. I am sure you can go ahead after detecting lines.

Also, you can go look into How to detect lines in OpenCV?, different use case which can be extended for your purpose as well.