In this project, I will create a program that detect and solve sudoku puzzle. In this program, user can control sudoku screen with hand gesture and input numbers with fingers. When user inputs 'f' key, solve result and solution are displayed.
image
1. Flow Chart
Requirement
1. Hardware
Intel Core i5-7300HQ
GTX 1050 Ti
2. Software Installation
Follow the link below to see and install all the requirements
3. Control Sudoku Solving Screen with Hand Gesture (Move Mode)
In this mode, there are 4 hidden buttons(up, down, left, right) on the webcam screen. When the middle point of thumb is on button, the button is activated and user can click by folding index finger.
4. Input Numbers in Original Sudoku (Solve Mode)
In this mode, program detects number of fingers. When the number maintained for 20 frame, the number inputed in the selected position. When user inputs 0, the position is reset.
5. Get Keyboard Input (Mode Change)
When user inputs 'm' key, the mode is changed. One is move mode and the other is solve mode.
# Change mode
if inkey == 77 or inkey == 109:
moveMode = not moveMode
detector = htm.handDetector(maxHands=1+(not moveMode), detectionCon=0.75)
6. Get Keyboard Input (Finish Solving)
When user inputs 'f' key to finish solving, solve result and solution are displayed. 'Success!' is displayed when all the digits fit with solution. Otherwise, 'Fail!' is displayed.
# Finish and display result
elif inkey == 70 or inkey == 102:
if inNumbers == solNumbers:
imgResult = sm.inNumbers(imgResult, solNumbers, color = (0, 255, 0))
putText(Sudoku, "Success!", (50, 240), FONT_HERSHEY_PLAIN, 5, (0, 255, 0), 5)
else:
for i in range(81):
if solNumbers[i] == inNumbers[i]:
rightNumbers[i] = solNumbers[i]
else:
wrongNumbers[i] = solNumbers[i]
imgResult = sm.inNumbers(imgResult, rightNumbers, color = (0, 255, 0))
imgResult = sm.inNumbers(imgResult, wrongNumbers, color = (0, 0, 255))
putText(Sudoku, "Fail!", (150, 240), FONT_HERSHEY_PLAIN, 5, (0, 0, 255), 5)
imshow('Result', imgResult)
imshow('Sudoku', Sudoku)
waitKey()
break
Results and Analysis
For the number of fingers and hand gesture detection, it well works 100%
For the sudoku detection, it well works 5~6 times in 10 times with random sudoku image
import math
import numpy as np
import cv2
from cv2 import *
from cv2.cv2 import *
import time
import mediapipe as mp
import HandTrackingModule as htm
import sudokuMain as sm
pTime = 0
wCam, hCam = 640, 480
cap = VideoCapture(0)
cap.set(CAP_PROP_FRAME_WIDTH, wCam)
cap.set(CAP_PROP_FRAME_HEIGHT, hCam)
moveMode = True
detector = htm.handDetector(maxHands=1, detectionCon=0.75)
buttonArea = [[(280, 90), (360, 150)], [(280, 330), (360, 390)], [(80, 210), (160, 270)], [(480, 210), (560, 270)]] # 0: Up, 1: Down, 2: Left, 3: Right
moveDirection = 0 # 0: None, 1: Up, 2: Down, 3: Left, 4: Right
isClick = False
isMove = False
tipIds = [4, 8, 12, 16, 20, 25, 29, 33, 37, 41]
numStack = 0
pNum = 0
numbers, inNumbers, solNumbers, imgSudoku = sm.detectSudoku("1.jpg")
cPos = inNumbers.index(0)
imgResult = imgSudoku.copy()
rightNumbers = [0] * 81
wrongNumbers = [0] * 81
while True:
_, img = cap.read()
img = flip(img, 1)
img = detector.findHands(img)
lmList = detector.findPosition(img, draw=False)
if moveMode: # Move mode
if len(lmList) != 0:
# Find position of thumb middle point
if buttonArea[0][0][0] < lmList[3][1] < buttonArea[0][1][0] and buttonArea[0][0][1] < lmList[3][2] < buttonArea[0][1][1]:
moveDirection = 1
elif buttonArea[1][0][0] < lmList[3][1] < buttonArea[1][1][0] and buttonArea[1][0][1] < lmList[3][2] < buttonArea[1][1][1]:
moveDirection = 2
elif buttonArea[2][0][0] < lmList[3][1] < buttonArea[2][1][0] and buttonArea[2][0][1] < lmList[3][2] < buttonArea[2][1][1]:
moveDirection = 3
elif buttonArea[3][0][0] < lmList[3][1] < buttonArea[3][1][0] and buttonArea[3][0][1] < lmList[3][2] < buttonArea[3][1][1]:
moveDirection = 4
else:
moveDirection = 0
# Check click and move state
if (not isClick) and lmList[8][2] > lmList[6][2]:
isClick = True
isMove = True
elif (isClick) and lmList[8][2] > lmList[6][2]:
isMove = False
else:
isClick = False
isMove = False
# Display direction and click state
if moveDirection == 1:
if isMove:
img = rectangle(img, buttonArea[0][0], buttonArea[0][1], (0, 255, 0), 3)
cPos = cPos - 9
if cPos < 0:
cPos = cPos + 81
else:
img = rectangle(img, buttonArea[0][0], buttonArea[0][1], (255, 0, 0), 3)
elif moveDirection == 2:
if isMove:
img = rectangle(img, buttonArea[1][0], buttonArea[1][1], (0, 255, 0), 3)
cPos = cPos + 9
if cPos > 80:
cPos = cPos - 81
else:
img = rectangle(img, buttonArea[1][0], buttonArea[1][1], (255, 0, 0), 3)
elif moveDirection == 3:
if isMove:
img = rectangle(img, buttonArea[2][0], buttonArea[2][1], (0, 255, 0), 3)
cPos = cPos - 1
if cPos % 9 == 8:
cPos = cPos + 9
else:
img = rectangle(img, buttonArea[2][0], buttonArea[2][1], (255, 0, 0), 3)
elif moveDirection == 4:
if isMove:
img = rectangle(img, buttonArea[3][0], buttonArea[3][1], (0, 255, 0), 3)
cPos = cPos + 1
if cPos % 9 == 0:
cPos = cPos - 9
else:
img = rectangle(img, buttonArea[3][0], buttonArea[3][1], (255, 0, 0), 3)
putText(img, "Move Mode", (20, 40), FONT_HERSHEY_PLAIN, 2, (255, 0, 0), 2)
else: # Solve mode
# Detect fingers
fingers = []
if len(lmList) != 0:
for id, cx, cy in lmList[:]:
if id in tipIds:
if id in [4, 25]: # Thumb
if lmList[id - 1][1] < cx < lmList[id + 13][1] or lmList[id + 13][1] < cx < lmList[id - 1][1]:
fingers.append(0)
else:
fingers.append(1)
else: # 4 Fingers
if cy < lmList[id - 2][2]:
fingers.append(1)
else:
fingers.append(0)
totalFingers = fingers.count(1) # Count fingers
# Stack same number of fingers
if pNum == totalFingers:
numStack += 1
else:
numStack = 0
pNum = totalFingers
# Input the number when number of fingers maintained for 20 frame
if numStack == 20 and totalFingers != 10 and inNumbers[cPos] != -1:
inNumbers[cPos] = totalFingers
try:
cPos = inNumbers.index(0)
except:
pass
# Print number of fingers
rectangle(img, (0, 420), (80, 480), (0, 255, 0), FILLED)
putText(img, str(totalFingers), (20, 460), FONT_HERSHEY_PLAIN, 2, (255, 0, 0), 5)
putText(img, "Solve Mode", (20, 40), FONT_HERSHEY_PLAIN, 2, (255, 0, 0), 2)
# Display sudoku image
Sudoku = imgSudoku.copy()
Sudoku = sm.inNumbers(Sudoku, inNumbers)
Sudoku = sm.selectedGrid(Sudoku, cPos)
cTime = time.time()
fps = 1 / (cTime - pTime)
pTime = cTime
putText(img, f'FPS: {int(fps)}', (500, 40), FONT_HERSHEY_PLAIN, 2, (255, 0, 0), 2)
imshow('Sudoku', Sudoku)
imshow("Controller", img)
inkey = waitKey(1)
# Change mode
if inkey == 77 or inkey == 109:
moveMode = not moveMode
detector = htm.handDetector(maxHands=1+(not moveMode), detectionCon=0.75)
# Finish and display result
elif inkey == 70 or inkey == 102:
if inNumbers == solNumbers:
imgResult = sm.inNumbers(imgResult, solNumbers, color = (0, 255, 0))
putText(Sudoku, "Success!", (50, 240), FONT_HERSHEY_PLAIN, 5, (0, 255, 0), 5)
else:
for i in range(81):
if solNumbers[i] == inNumbers[i]:
rightNumbers[i] = solNumbers[i]
else:
wrongNumbers[i] = solNumbers[i]
imgResult = sm.inNumbers(imgResult, rightNumbers, color = (0, 255, 0))
imgResult = sm.inNumbers(imgResult, wrongNumbers, color = (0, 0, 255))
putText(Sudoku, "Fail!", (150, 240), FONT_HERSHEY_PLAIN, 5, (0, 0, 255), 5)
imshow('Result', imgResult)
imshow('Sudoku', Sudoku)
waitKey()
break
# Break
elif inkey == 27:
break
destroyAllWindows()
[HandTrackingModule.py]
import math
import numpy as np
import cv2
from cv2 import *
from cv2.cv2 import *
import mediapipe as mp
class handDetector():
def __init__(self, mode=False, maxHands=2, complexity=1, detectionCon=0.5, trackCon=0.5):
self.mode = mode
self.maxHands = maxHands
self.complexity = complexity
self.detectionCon = detectionCon
self.trackCon = trackCon
self.mpHands = mp.solutions.hands
self.hands = self.mpHands.Hands(self.mode, self.maxHands, self.complexity, self.detectionCon, self.trackCon)
self.mpDraw = mp.solutions.drawing_utils
def findHands(self, img, draw=True):
imgRGB = cvtColor(img, COLOR_BGR2RGB)
self.results = self.hands.process(imgRGB)
if self.results.multi_hand_landmarks:
for handLms in self.results.multi_hand_landmarks:
if draw:
self.mpDraw.draw_landmarks(img, handLms,
self.mpHands.HAND_CONNECTIONS)
return img
def findPosition(self, img, draw=True):
lmList = []
if self.results.multi_hand_landmarks:
for handNo, handLms in enumerate(self.results.multi_hand_landmarks):
for id, lm in enumerate(handLms.landmark):
h, w, _ = img.shape
cx, cy = int(lm.x * w), int(lm.y * h)
lmList.append([id + handNo*21, cx, cy])
if draw:
circle(img, (cx, cy), 15, (255, 0, 255), FILLED)
return lmList
[sudokuMain.py]
import os
import cv2
os.environ['TF_CPP_MIN_LOG_LEVEL'] = '3'
from sudokuSolver import *
def detectSudoku(pathImage):
heightImg = 450
widthImg = 450
model = intializePredectionModel() # Load the CNN model
img = cv2.imread(pathImage)
img = cv2.resize(img, (widthImg, heightImg))
imgThreshold = preProcess(img)
contours, hierarchy = cv2.findContours(imgThreshold, cv2.RETR_EXTERNAL, cv2.CHAIN_APPROX_SIMPLE)
biggest, maxArea = biggestContour(contours) # Find the biggest contour
if biggest.size != 0:
biggest = reorder(biggest)
pts1 = np.float32(biggest)
pts2 = np.float32([[0, 0],[widthImg, 0], [0, heightImg],[widthImg, heightImg]])
matrix = cv2.getPerspectiveTransform(pts1, pts2)
imgWarpColored = cv2.warpPerspective(img, matrix, (widthImg, heightImg))
imgWarpColored = cv2.cvtColor(imgWarpColored,cv2.COLOR_BGR2GRAY)
imgDetectedDigits = np.ones((heightImg, widthImg, 3), np.uint8) * 255
# Split the image and find each digit available
boxes = splitBoxes(imgWarpColored)
numbers = getPredection(boxes, model)
imgDetectedDigits = displayNumbers(imgDetectedDigits, numbers)
numbers = np.asarray(numbers)
posArray = np.where(numbers > 0, 0, 1)
inNumbers = np.where(numbers > 0, -1, 0)
# Find solution of the board
board = np.array_split(numbers, 9)
try:
solve(board)
except:
pass
# Save the solution
flatList = []
for sublist in board:
for item in sublist:
flatList.append(item)
solvedNumbers = flatList*posArray
solvedNumbers = np.where(solvedNumbers == 0, -1, solvedNumbers)
# Draw grid and Return
imgDetectedDigits = drawGrid(imgDetectedDigits)
return numbers.tolist(), inNumbers.tolist(), solvedNumbers.tolist(), imgDetectedDigits
else:
print("No Sudoku Found")
# Draw selected grid
def selectedGrid(img, pos):
secW = int(img.shape[1] / 9)
secH = int(img.shape[0] / 9)
xpos, ypos = pos % 9, pos // 9
pt1 = (xpos*secW+3, ypos*secH+3)
pt2 = ((xpos+1)*secW-3, (ypos+1)*secH-3)
cv2.rectangle(img, pt1, pt2, (0, 255, 0), 2)
return img
# Display input numbers
def inNumbers(img, numbers, color = (255, 0, 0)):
secW = int(img.shape[1]/9)
secH = int(img.shape[0]/9)
for x in range (0,9):
for y in range (0,9):
if numbers[(y*9)+x] not in [-1, 0] :
cv2.putText(img, str(numbers[(y*9)+x]),
(x*secW+int(secW/2)-12, int((y+0.8)*secH)), cv2.FONT_HERSHEY_COMPLEX_SMALL,
2, color, 2, cv2.LINE_AA)
return img
[sudokuSolver.py]
import cv2
import numpy as np
from tensorflow import keras
def solve(bo):
find = find_empty(bo)
if not find:
return True
else:
row, col = find
for i in range(1,10):
if valid(bo, i, (row, col)):
bo[row][col] = i
if solve(bo):
return True
bo[row][col] = 0
return False
def valid(bo, num, pos):
# Check row
for i in range(len(bo[0])):
if bo[pos[0]][i] == num and pos[1] != i:
return False
# Check column
for i in range(len(bo)):
if bo[i][pos[1]] == num and pos[0] != i:
return False
# Check box
box_x = pos[1] // 3
box_y = pos[0] // 3
for i in range(box_y*3, box_y*3 + 3):
for j in range(box_x * 3, box_x*3 + 3):
if bo[i][j] == num and (i,j) != pos:
return False
return True
def print_board(bo):
for i in range(len(bo)):
if i % 3 == 0 and i != 0:
print("- - - - - - - - - - - - - ")
for j in range(len(bo[0])):
if j % 3 == 0 and j != 0:
print(" | ", end="")
if j == 8:
print(bo[i][j])
else:
print(str(bo[i][j]) + " ", end="")
def find_empty(bo):
for i in range(len(bo)):
for j in range(len(bo[0])):
if bo[i][j] == 0:
return (i, j)
return None
# Read the model weights
def intializePredectionModel():
model = keras.models.load_model('myModel.h5')
return model
# Preprocessing image
def preProcess(img):
imgGray = cv2.cvtColor(img, cv2.COLOR_BGR2GRAY)
imgBlur = cv2.GaussianBlur(imgGray, (5, 5), 1)
imgThreshold = cv2.adaptiveThreshold(imgBlur, 255, 1, 1, 11, 2)
# _, imgThreshold = cv2.threshold(imgBlur, 120, 255, 1)
return imgThreshold
# Reorder points for Warp Perspective
def reorder(myPoints):
myPoints = myPoints.reshape((4, 2))
myPointsNew = np.zeros((4, 1, 2), dtype=np.int32)
add = myPoints.sum(1)
myPointsNew[0] = myPoints[np.argmin(add)]
myPointsNew[3] =myPoints[np.argmax(add)]
diff = np.diff(myPoints, axis=1)
myPointsNew[1] =myPoints[np.argmin(diff)]
myPointsNew[2] = myPoints[np.argmax(diff)]
return myPointsNew
# Finding the biggest contour
def biggestContour(contours):
biggest = np.array([])
max_area = 0
for i in contours:
area = cv2.contourArea(i)
if area > 50:
peri = cv2.arcLength(i, True)
approx = cv2.approxPolyDP(i, 0.02 * peri, True)
if area > max_area and len(approx) == 4:
biggest = approx
max_area = area
return biggest, max_area
# Split the image into 81 different images
def splitBoxes(img):
rows = np.vsplit(img, 9)
boxes=[]
for r in rows:
cols= np.hsplit(r, 9)
for box in cols:
boxes.append(box)
return boxes
# Get predections on all images
def getPredection(boxes, model):
result = []
for image in boxes:
# Prepare image
img = np.asarray(image)
img = img[4:img.shape[0] - 4, 4:img.shape[1] -4]
img = cv2.resize(img, (28, 28))
img = img / 255
img = img.reshape(1, 28, 28, 1)
# Get predection
predictions = model.predict(img)
classIndex = np.argmax(predictions, axis=1)
probabilityValue = np.amax(predictions)
# Save to result
if probabilityValue > 0.8:
result.append(classIndex[0])
else:
result.append(0)
return result
# Display the original sudoku
def displayNumbers(img, numbers, color = (0, 0, 0)):
secW = int(img.shape[1]/9)
secH = int(img.shape[0]/9)
for x in range (0,9):
for y in range (0,9):
if numbers[(y*9)+x] != 0 :
cv2.putText(img, str(numbers[(y*9)+x]),
(x*secW+int(secW/2)-12, int((y+0.8)*secH)), cv2.FONT_HERSHEY_COMPLEX_SMALL,
2, color, 2, cv2.LINE_AA)
return img
# Draw grid
def drawGrid(img):
secW = int(img.shape[1] / 9)
secH = int(img.shape[0] / 9)
for i in range (0, 9):
pt1 = (0, secH * i)
pt2 = (img.shape[1], secH * i)
pt3 = (secW * i, 0)
pt4 = (secW * i, img.shape[0])
if i % 3 == 0 and i > 0:
cv2.line(img, pt1, pt2, (0, 0, 0),3)
cv2.line(img, pt3, pt4, (0, 0, 0),3)
else:
cv2.line(img, pt1, pt2, (0, 0, 0),2)
cv2.line(img, pt3, pt4, (0, 0, 0),2)
return img
