Saturday, February 27, 2021
  • Setup menu at Appearance » Menus and assign menu to Top Bar Navigation
Advertisement
  • AI Development
    • Artificial Intelligence
    • Machine Learning
    • Neural Networks
    • Learn to Code
  • Data
    • Blockchain
    • Big Data
    • Data Science
  • IT Security
    • Internet Privacy
    • Internet Security
  • Marketing
    • Digital Marketing
    • Marketing Technology
  • Technology Companies
  • Crypto News
No Result
View All Result
NikolaNews
  • AI Development
    • Artificial Intelligence
    • Machine Learning
    • Neural Networks
    • Learn to Code
  • Data
    • Blockchain
    • Big Data
    • Data Science
  • IT Security
    • Internet Privacy
    • Internet Security
  • Marketing
    • Digital Marketing
    • Marketing Technology
  • Technology Companies
  • Crypto News
No Result
View All Result
NikolaNews
No Result
View All Result
Home Neural Networks

Part 2: Sudoku and Cell Extraction | by Aditi Jain | Jul, 2020

July 16, 2020
in Neural Networks
Part 2: Sudoku and Cell Extraction | by Aditi Jain | Jul, 2020
586
SHARES
3.3k
VIEWS
Share on FacebookShare on Twitter
Source

Sudoku Solver AI with OpenCV

We will be creating a Sudoku Solver AI using python and Open CV to read a Sudoku puzzle from an image and solving it. There a lot of methods to achieve this goal. Thus in this series, I have compiled the best methods I could find/research along with some hacks/tricks I learned along the way.

You might also like

How AI Can Be Used in Agriculture Sector for Higher Productivity? | by ANOLYTICS

Future Tech: Artificial Intelligence and the Singularity | by Jason Sherman | Feb, 2021

Tackling ethics in AI algorithms: the case of Salesforce | by Iflexion | Feb, 2021

This article is a part of the series Sudoku Solver with OpenCV.
Part 1: Image Processing
Part 2: Sudoku and Cell Extraction
Part 3: Solving the Sudoku

Before and After part 1: left and right respectively

I am trying to be as detailed as possible in listing the steps along with there descriptions. There are several ways to Extract sudoku and solve it. I will add alternate ways, but won’t go into detail about them.

  1. Import the image
  2. Pre Processing the Image
    2.1 Gaussian blur: We need to gaussian blur the image to reduce noise in thresholding algorithm
    2.2 Thresholding: Segmenting the regions of the image
    2.3 Dilating the image: In cases like noise removal, erosion is followed by dilation.
  3. Sudoku Extraction
    3.1 Find Contours
    3.2 Find Corners: Using Ramer Doughlas Peucker algorithm / approxPolyDP for finding corners
    3.3 Crop and Warp Image: We remove all the elements in the image except the sudoku
    3.4 Extract Cells

3.1 Find Contours:

We will find external contours and then sort by area in descending order. Thus, the largest polygon is stored in contours[0].

findContours: boundaries of shapes having the same intensity
CHAIN_APPROX_SIMPLE — stores only minimal information of points to describe the contour
RETR_EXTERNAL: gives “outer” contours.

for c in ext_contours:
peri = cv2.arcLength(c, True)
approx = cv2.approxPolyDP(c, 0.015 * peri, True)
if len(approx) == 4:
# Here we are looking for the largest 4 sided contour
return approx

Tip: If you want to see the contours, try drawcontour(..)

Big Data Jobs

3.2 Find Corners:

The largest contours is are the corners of the sudoku. There are several ways we can achieve this. Notable methods include Canny Edge Algorithm, Ramer Doughlas Peucker algorithm, Bounding Rectangle, and approxPolyDP.

A. approxPolyDP:
We approximate the curve given by the largest Contours. The largest 4-sided contour is the sudoku.

Function Deatils:
cv2.approxPolyDP(curve, epsilon, closed[, approxCurve])
Curve-> hers is the largest contour
epsilon -> Parameter specifying the approximation accuracy. This is the maximum distance between the original curve and its approximation.
closed -> If true, the approximated curve is closed. Otherwise, it is not closed.
return type: the same type as the input curve

peri = cv2.arcLength(c, True)
approx = cv2.approxPolyDP(c, 0.015 * peri, True)
if len(approx) == 4:
# Here we are looking for the largest 4 sided contour
return approx
# approx has the

In corners[0],… stores the points in format [[x y]].

# Extracting the points
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
# Index 0 - top-right
# 1 - top-left
# 2 - bottom-left
# 3 - bottom-right

B. Ramer Doughlas Peucker algorithm:
We will use max(list, key) for the right side corners as there x-value is greater. Likewise, we will use min(list, key) for the left side corners.

operator is a built-in module providing a set of convenient operators. In two words operator.itemgetter(n) constructs a callable that assumes an iterable object (e.g. list, tuple, set) as input, and fetches the n-th element out of it.

We will use max(list, key) for the right side corners as there x-value is greater. Likewise, we will use min(list, key) for the left side corners.

bottom_right, _ = max(enumerate([pt[0][0] + pt[0][1] for pt in
ext_contours[0]]), key=operator.itemgetter(1))
top_left, _ = min(enumerate([pt[0][0] + pt[0][1] for pt in
ext_contours[0]]), key=operator.itemgetter(1))
bottom_left, _ = min(enumerate([pt[0][0] - pt[0][1] for pt in
ext_contours[0]]), key=operator.itemgetter(1))
top_right, _ = max(enumerate([pt[0][0] - pt[0][1] for pt in
ext_contours[0]]), key=operator.itemgetter(1))

Natural Language Generation:
The Commercial State of the Art in 2020

This Entire Article Was Written by Open AI’s GPT2

Learning To Classify Images Without Labels

Becoming a Data Scientist, Data Analyst, Financial Analyst and Research Analyst

Corners of the sudoku

3.3 Crop and Warp Image

In order to crop the image, we need to know the dimensions of the sudoku. Although sudoku is a square and has equal dimensions, in order to ensure that we dont crop any part of the image we will calculate the height and width.

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))

Similarly, we can calculate height

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))

We need to construct dimensions for the cropped image. Since the index starts from 0, we start from the points are (0, 0) , (width-1,0) ,(width-1, height-1), and (0, height-1). We will then get the grid and warp the image.

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")
# calculate the perspective transform matrix and warp
# the perspective to grab the screen
grid = cv2.getPerspectiveTransform(ordered_corners, dimensions)
return cv2.warpPerspective(image, grid, (width, height))
Cropped Image

3.3 Extract Cells

So we need to process the image again suing adaptive threshold and bitwise_inversion.
Note: Don’t forget to convert the image to grey scale before processing. I made that mistake. The code seemed simple, didn’t make sense if it had any problem but it kept on showing error. It took 3 hrs for me to realize. During this time, I had my Software Engineer moment when we get a error, don’t understand why after trying everything and then when you realize you feel like breaking your laptop.😅

# here grid is the cropped image
grid = cv2.cvtColor(grid, cv2.COLOR_BGR2GRAY) # VERY IMPORTANT
# Adaptive thresholding the cropped grid and inverting it
grid = cv2.bitwise_not(cv2.adaptiveThreshold(grid, 255, cv2.ADAPTIVE_THRESH_GAUSSIAN_C, cv2.THRESH_BINARY, 101, 1))
Cropped and Processed image

Extracting every cell/square. Most sudoku are square, but not all of them. For instance, the sudoku used throughout this series is not a square so the cells are not also square. There will extract the celledge_h and college_w using np.shape(grid)

edge_h = np.shape(grid)[0]
edge_w = np.shape(grid)[1]
celledge_h = edge_h // 9
celledge_w = np.shape(grid)[1] // 9

We will iterate through the length and width of the cropped and processed image (grid), extract the cells and store them in a temporary grid.

tempgrid = []
for i in range(celledge_h, edge_h + 1, celledge_h):
for j in range(celledge_w, edge_w + 1, celledge_w):
rows = grid[i - celledge_h:i]
tempgrid.append([rows[k][j - celledge_w:j] for k in range(len(rows))])

Creating an 9×9 array of the images and converting it into a numpy array, so that it is easier to process.

# Creating the 9X9 grid of images
finalgrid = []
for i in range(0, len(tempgrid) - 8, 9):
finalgrid.append(tempgrid[i:i + 9])
# Converting all the cell images to np.array
for i in range(9):
for j in range(9):
finalgrid[i][j] = np.array(finalgrid[i][j])
try:
for i in range(9):
for j in range(9):
os.remove("BoardCells/cell" + str(i) + str(j) + ".jpg")
except:
pass
for i in range(9):
for j in range(9):
cv2.imwrite(str("BoardCells/cell" + str(i) + str(j) + ".jpg"), finalgrid[i][j])
return finalgrid
Extarcted cell stored in finalgrid[2][8]

Credit: BecomingHuman By: Aditi Jain

Previous Post

Top Skills for Marketers & Aspiring Marketers

Next Post

Machine Learning and Exception Management – A Logistics Tech Game-Changer

Related Posts

How AI Can Be Used in Agriculture Sector for Higher Productivity? | by ANOLYTICS
Neural Networks

How AI Can Be Used in Agriculture Sector for Higher Productivity? | by ANOLYTICS

February 27, 2021
Future Tech: Artificial Intelligence and the Singularity | by Jason Sherman | Feb, 2021
Neural Networks

Future Tech: Artificial Intelligence and the Singularity | by Jason Sherman | Feb, 2021

February 27, 2021
Tackling ethics in AI algorithms: the case of Salesforce | by Iflexion | Feb, 2021
Neural Networks

Tackling ethics in AI algorithms: the case of Salesforce | by Iflexion | Feb, 2021

February 27, 2021
Creative Destruction and Godlike Technology in the 21st Century | by Madhav Kunal
Neural Networks

Creative Destruction and Godlike Technology in the 21st Century | by Madhav Kunal

February 26, 2021
How 3D Cuboid Annotation Service is better than free Tool? | by ANOLYTICS
Neural Networks

How 3D Cuboid Annotation Service is better than free Tool? | by ANOLYTICS

February 26, 2021
Next Post
Machine Learning and Exception Management – A Logistics Tech Game-Changer

Machine Learning and Exception Management – A Logistics Tech Game-Changer

Leave a Reply Cancel reply

Your email address will not be published. Required fields are marked *

Recommended

Plasticity in Deep Learning: Dynamic Adaptations for AI Self-Driving Cars

Plasticity in Deep Learning: Dynamic Adaptations for AI Self-Driving Cars

January 6, 2019
Microsoft, Google Use Artificial Intelligence to Fight Hackers

Microsoft, Google Use Artificial Intelligence to Fight Hackers

January 6, 2019

Categories

  • Artificial Intelligence
  • Big Data
  • Blockchain
  • Crypto News
  • Data Science
  • Digital Marketing
  • Internet Privacy
  • Internet Security
  • Learn to Code
  • Machine Learning
  • Marketing Technology
  • Neural Networks
  • Technology Companies

Don't miss it

AI & ML Are Not Same. Here's Why – Analytics India Magazine
Machine Learning

AI & ML Are Not Same. Here's Why – Analytics India Magazine

February 27, 2021
Microsoft: We’ve open-sourced this tool we used to hunt for code by SolarWinds hackers
Internet Security

Microsoft: We’ve open-sourced this tool we used to hunt for code by SolarWinds hackers

February 27, 2021
Is Wattpad and its machine learning tool the future of TV? — Quartz
Machine Learning

Is Wattpad and its machine learning tool the future of TV? — Quartz

February 27, 2021
Oxford University lab with COVID-19 research links targeted by hackers
Internet Security

Oxford University lab with COVID-19 research links targeted by hackers

February 27, 2021
The Education Industrial Complex: The Hammer We Have
Data Science

The Education Industrial Complex: The Hammer We Have

February 27, 2021
New AI Machine Learning Reduces Mental Health Misdiagnosis
Machine Learning

New AI Machine Learning Reduces Mental Health Misdiagnosis

February 27, 2021
NikolaNews

NikolaNews.com is an online News Portal which aims to share news about blockchain, AI, Big Data, and Data Privacy and more!

What’s New Here?

  • AI & ML Are Not Same. Here's Why – Analytics India Magazine February 27, 2021
  • Microsoft: We’ve open-sourced this tool we used to hunt for code by SolarWinds hackers February 27, 2021
  • Is Wattpad and its machine learning tool the future of TV? — Quartz February 27, 2021
  • Oxford University lab with COVID-19 research links targeted by hackers February 27, 2021

Subscribe to get more!

© 2019 NikolaNews.com - Global Tech Updates

No Result
View All Result
  • AI Development
    • Artificial Intelligence
    • Machine Learning
    • Neural Networks
    • Learn to Code
  • Data
    • Blockchain
    • Big Data
    • Data Science
  • IT Security
    • Internet Privacy
    • Internet Security
  • Marketing
    • Digital Marketing
    • Marketing Technology
  • Technology Companies
  • Crypto News

© 2019 NikolaNews.com - Global Tech Updates