Introduction

This year, an Othello Advent Calendar was planned and invited, so I decided to write an article. Actually, I wrote another article on Day 1, but I didn't know what I was doing and suddenly entered the article, so this time A little self-introduction.

I am developing an iOS app called [Game Record Box](https://itunes.apple.com/jp/app/Game Record box/id1434692901?mt=8). As one of the functions, we have incorporated a function to take a picture of the Othello board with a camera and display the evaluation value on the board in AR. Click the image below to see the introductory video. It also has the ability to take a picture of the board (or select the picture taken) and recognize the placement of the stones on the board. This also has an introductory video.

In this article, I would like to explain how these functions recognize the surface of the Othello board. When you input the image on the left side below, the goal is to recognize the position of black stones and white stones and the situation of empty squares as shown in the image on the right side. 認識結果

Prerequisite environment

Python3.7.1
OpenCV 4.1.0

Since the actual application is iOS, I implemented it with Objective C + OpenCV, but in this article I will explain it with the Python version. The content itself is almost the same as the app version.

Please refer to the entire Python version source code below. https://github.com/lavox/reversi_recognition

policy

There are two main approaches to recognizing images.

--How to use machine learning --How to create an algorithm by yourself

Regarding the former, it seemed difficult to collect a large number of teacher images for learning, and it seemed difficult to tune when things went wrong, so I decided to adopt the latter method. Image recognition is performed in the following steps.

Identify the range of the board
Convert to square
Identify the location of the stone
Determine the color of the stone

In the function to take a picture with the camera and capture the board, after performing 1, the range confirmation screen is displayed and then 2 to 4, but in the AR function, 1 to 4 are executed at once.

Preparation

import cv2
image = cv2.imread("./sample.jpg ")
image = cv2.blur(image,(3,3))

The image is read and smoothed (blurred) in a size of 3x3. When performing image analysis, it seems to be the established theory to smooth in advance, so I did so.

In case of Python, the loaded image will be an array of 3 elements NumPy for each pixel, but please note that the order of 3 elements is BGR instead of RGB. When displaying using matplotlib etc., the hue will be strange unless the format (color order) is changed.

rgbImage = cv2.cvtColor(image, cv2.COLOR_BGR2RGB)

Step1. Specifying the range of the board

Since the surface of the Othello board is green, I decided to proceed in the direction of extracting the green area. Since it is difficult to extract the color range in BGR format, convert it to HSV format.

hsv = cv2.cvtColor(image, cv2.COLOR_BGR2HSV)

Since it became HSV format, I decided to specify the range of the color area with H, and S and V consider the area above a certain value as green. 緑色領域

I really wanted to make it curved, but since the processing is troublesome, the area that combines the upper right side of the two areas is called "green". The boundary value was determined by trial and error while actually looking at the image.

lower = np.array([45,89,30])
upper = np.array([90,255,255])
green1 = cv2.inRange(hsv,lower,upper)

lower = np.array([45,64,89])
upper = np.array([90,255,255])
green2 = cv2.inRange(hsv,lower,upper)

green = cv2.bitwise_or(green1,green2)

In OpenCV you can specify the range with ʻinRange. bitwise_oris literally an OR between regions. <img width="480" alt="緑色領域抽出" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/202945/34dfef8d-c58a-ea8e-0e9f-3882702e7d11.png "> The green area has been extracted. From here, I would like to find the coordinates of the vertices at the four corners of the board, but how do I find them from this binarized image? I'm also worried that there are multiple boards. After searching various things, I found a function calledfindContours` that detects contours, so I will use it.

This function returned 3 return values in the V3 era, but please note that it seems that it has changed from V4 to 2.

contours, hierarchy = cv2.findContours(green, cv2.RETR_EXTERNAL, cv2.CHAIN_APPROX_SIMPLE)

As a result of doing this, more than 2000 contours were extracted. What happened? I drew some large outlines. 緑色領域抽出 It was separated by black lines and stones in the squares. Looking at the finer contours, I found that the contours were made up of only one pixel, and that this findContours judges the contours quite severely. When I searched the net for techniques to remove such obstacles such as black lines, [morphology conversion](http://labs.eecs.tottori-u.ac.jp/sd/Member/oyamada/OpenCV /html/py_tutorials/py_imgproc/py_morphological_ops/py_morphological_ops.html) I found it. By dilate the area once to make it larger, and then erode it, fine lines and dust can be erased.

So how much should it expand and contract? When I calculated it in the case where the board is full of images, the thickness of the line seems to be about 0.6 to 0.7% of the long side, so 0.35 on the long side to expand and erase this from both sides. I decided to make it%.

kernelSize = max(1, int(0.0035 * max(width, height))) * 2 + 1
kernel = np.ones((kernelSize, kernelSize), dtype=np.int)

green = cv2.dilate(green, kernel) #expansion
green = cv2.erode(green, kernel) #Shrink

There is a * 2 + 1 that I don't understand a little, but it seems that the size of expansion and contraction must be odd, so it is a correction to make it odd. 膨張・収縮 I succeeded in erasing the line. However, when the number of stones increases, it seems to be divided by stones, which is a bit dangerous. I couldn't help it, so I decided to take the plunge and consider not only the green part but also the white part as part of the board. (The black part is really black, so I stopped it because it spreads too much)

lower = np.array([0, 0, 128])
upper = np.array(([180, 50, 255])
white = cv2.inRange(hsv, lower, upper)
greenWhite = cv2.bitwise_or(green, white)

The table is white, so I'm a little worried, but the risk of division has decreased considerably, and the range of the board is clear, so I decided to proceed with this. Now let's re-extract the contour.

contours, hierarchy = cv2.findContours(greenWhite, cv2.RETR_EXTERNAL, cv2.CHAIN_APPROX_SIMPLE)

There is a dent in the stone around the side, but it is no longer divided. What I want to do is

――What can I do about the dent? ――How to select the contour of the board you are paying attention to when many contours are extracted

It is a place like that. When I searched for something to do with the first dent, I found that convex hull There was a method (/py_contour_features/py_contour_features.html#convex-hull).

If it can be made convex, it is the one that includes the center point of the image in the extracted contour (I assumed that it is in the center because it should be taken to recognize the board surface), and it is the second one. It seems that we can clear which contour to select, which was an issue.

for i, c in enumerate(contours):
    hull = cv2.convexHull(c) #Convex hull
    if cv2.pointPolygonTest(hull,(width / 2 , height / 2), False) > 0: #Determine if it contains the center
        mask = np.zeros((height, width),dtype=np.uint8)
        cv2.fillPoly(mask, pts=[hull], color=(255)) #Image filled within the contour range
        break

For the time being, the area of the board is obtained. However, since I added a white part to prevent division, I'm a little worried if it involves an extra area. So, I tried to extract the green part in this area, take the outline and connect all of them.

green = cv2.bitwise_and(green, green, mask=mask)
contours, hierarchy = cv2.findContours(green, cv2.RETR_EXTERNAL, cv2.CHAIN_APPROX_SIMPLE)
greenContours = functools.reduce(lambda x, y: np.append(x, y,axis=0),contours)
hull = cv2.convexHull(greenContours)

I thought that the outline could be extracted safely with this, but when I displayed the value, it was a 26-sided square.

> print(hull.shape)
(26, 1, 2)

Even though it looks almost straight, it seems that there are actually vertices in between. OpenCV also had a countermeasure for this situation. ʻApproxPolyDP` is a function that approximates a polygon.

epsilon = 0.004 * cv2.arcLength(hull, True)
approx = cv2.approxPolyDP(hull, epsilon, True)

As a result of trial and error, by making 0.4% of the circumference as an error, it seems that it becomes a quadrangle with a good feeling in most cases.

> print(approx)
[[[2723 2702]]
 [[ 675 2669]]
 [[1045 1639]]
 [[2418 1613]]]

With this, I was able to find the four vertices of the board, but I would like to touch on some details that could not be written here.

--If there is a stone near the corner, or if the corner is cut off from the image, the corner may be chipped and become a pentagon or hexagon. ――In such a case, the sides should match, so I chose four sides in the order of longest from the extracted polygons and decided to consider the intersection as the apex. This is a math problem rather than OpenCV, so if you are interested, please go to Source Code from lines 371 to 396. And look around the 99th to 107th lines. --Sometimes you select an area that is not a board ――This is unavoidable, but when it is judged that the original is not a square, it is regarded as a failure. This is also a math problem, so if you are interested, please go to Source Code from lines 438 to 485 and lines 125. Please refer to the 1st to 197th lines. As a by-product of this, the relative positional relationship between the board and the camera can be obtained, which will be used later. --Correction of board orientation --The vertices are retaken so that they are clockwise in order from the upper left of the image. ――Check if the board is not cut off --The border of the Othello board is slightly thicker on the outer circumference, so its correction --If the image size is too large, it will take time to process, so resize first.

Step2. Convert the board part to a square

I will convert the board obtained in Step 1 to a square, but for the convenience of later processing, I will give a margin (blue frame) around it. The purpose of the margin is as follows.

--When checking the color of the stone later, make sure that the check range does not extend beyond the image. --If the corner of the board is cut off, it can be treated the same as the cut-out part.

margin = 13 #Margin width
cell_size = 42 #1 square size
size = cell_size * 8 + margin * 2 #Edge length after conversion
outer = (254, 0, 0) #Margin part color

Converting to a square is actually easy, and if you know the vertices of the source and destination, you can do a projective transformation.

#4 vertices of the source
src = np.array([[1045,1639], [2418,1613], [2723,2702], [ 675,2669]], dtype=np.float32)
#4 vertices to move to
dst = np.array([
    [margin, margin],
    [size - 1 - margin, margin],
    [size - 1 - margin, size - 1 - margin],
    [margin, size - 1 - margin]
], dtype=np.float32)
#Transformation matrix
trans = cv2.getPerspectiveTransform(src, dst)
#Projection transformation
board = cv2.warpPerspective(image, trans, (int(size), int(size)), flags=cv2.INTER_LINEAR, borderMode=cv2.BORDER_CONSTANT, borderValue=outer)

As a note, the above projective transformation outer is a color to make up for the protruding part when the four vertices are protruding from the image. It does not fill the margins. So, I will also paint the margin part.

cv2.rectangle(board, (0, 0), (size - 1, margin), outer, -1)
cv2.rectangle(board, (0, 0), (margin, size - 1), outer, -1)
cv2.rectangle(board, (size - margin, 0), (size - 1, size - 1), outer, -1)
cv2.rectangle(board, (0, size - margin), (size - 1, size - 1), outer, -1)

You have now made the board square.

Step3. Identifying the position of the stone

In locating the stone, I was wondering whether to assume that the stone was in the center of the square. Since it is an actual board, there are cases where stones are placed off the center, and if the image is taken from an angle, the center may be off due to the thickness of the stone in the image after conversion to a square. So I decided to proceed without assuming that the stone is in the center of the square.

So, how to identify the position of the stone, at first I thought that it would be better to use a Hough transform that detects a circle because the stone is circular. However, when I actually tried it, I detected a large number of mysterious circles that were invisible to the human eye, and the adjustment was frustrated because there were many parameters. * In addition, in the application called ScoreNow, I heard from the developer that it uses the Hough transform to detect stones, so I adjusted it well. I think you can do it. *

After searching variously at a loss, I arrived at the article Details of the object segmentation algorithm "watershed" and decided to try this method. did. In this case, rather than finding the exact outline of the stone, we are looking for the center of the stone, so we are only executing part of the linked article.

First, in order to separate the board and the stone, extract the board part in the green part as in Step 1.

hsv = cv2.cvtColor(board, cv2.COLOR_BGR2HSV)
lower = np.array([45,89,30])
upper = np.array([90,255,255])
green1 = cv2.inRange(hsv,lower,upper)

lower = np.array([45,64,89])
upper = np.array([90,255,255])
green2 = cv2.inRange(hsv,lower,upper)

green = cv2.bitwise_or(green1,green2)

You can extract the stone part by adding the blue part of the margin and then flipping it.

outer = cv2.inRange(board, (254, 0, 0), (254, 0, 0))
green = cv2.bitwise_or(green, outer)
disc = cv2.bitwise_not(green)

The line of the square remains, but it will not affect the subsequent processing in particular, so leave it as it is this time.

Also, considering the possibility that human hands are actually reflected, there is a process that treats the part that is neither green, white, nor black as an "unknown" cell, but it will be long, so I will omit it. ..

Now, according to the previous Qiita article, find the distance from the outside of the stone to each point.

dist = cv2.distanceTransform(disc, cv2.DIST_L2, 5)

The point with the maximum value of each island (?) Is likely to be the center of the stone. However, since some of the islands are now connected, points above a certain value are extracted and separated. If the "some value" is too large, unrecognizable stones may occur, but if it is too small, the connection may not be separated, and as a result of trial and error, 13.0 was set as the threshold value.

_, distThr = cv2.threshold(dist, 13.0, 255.0, cv2.THRESH_BINARY)

The maximum point of each connection area should be the center of the stone, so find it.

distThr = np.uint8(distThr) #Type conversion required
#Get connected components
labelnum, labelimg, data, center = cv2.connectedComponentsWithStats(distThr)
for i in range(1, labelnum): # i =Exclude because 0 is the background
    x, y, w, h, s = data[i]
    distComponent = dist[y:y+h, x:x+w]
    maxCoord = np.unravel_index(distComponent.argmax(), distComponent.shape) + np.array([y, x])

In addition, since the islands are not separated well and become bimodal, in the actual source it is a little complicated to loop while erasing the vicinity of the maximum value, but here it is simple It has turned into. 石の分離 I was able to find the center of the stone with reasonable accuracy. As a concern, the stones are shaped like drums rather than circles because the photo taken from an angle is forced into a square, preferably the color of the stone is near the center of the top and the position of the stone is in the center of the bottom. I want to judge. In order to manage this, based on the camera position obtained at the time of board extraction, the center of the stone is shifted to the far side and the near side from the camera and regarded as the center of the top and bottom surfaces, but it becomes longer. So (although it's already long enough ...) I'll omit the explanation this time.

Step4. Judgment of stone color

Now it's time to judge the color of the stone. Basically, it seems good to judge by the brightness of the color near the center of the stone, but when I actually tried it, some problems came up.

――Since the accuracy of the center point is not perfect, if you widen the judgment range, it will pick up the color of the adjacent stone or the side of the stone and cause false detection. ――It is difficult to judge Kuroishi in a bright environment and Shiraishi in a dim environment only by the V (brightness) of HSV. --Kuroishi may look like white stone due to the reflection of light. This is as white as a real Shiraishi.

Regarding the second point, I initially made the condition by comparing the brightness with the surroundings, but after that I found a simpler method to judge using OpenCV. That is the process of binarizing based on the surrounding situation called adaptive threshold. With this, white stones turn white regardless of the brightness of the surroundings.

grayBoard = cv2.cvtColor(board, cv2.COLOR_BGR2GRAY)
binBoardWide = cv2.adaptiveThreshold(grayBoard, 255, cv2.ADAPTIVE_THRESH_GAUSSIAN_C, cv2.THRESH_BINARY, 127, -20)

After grayscale, we are running adaptive threshold. Now the white stones are quite white, but there are still some black stones that are whitish, so I would like to devise a little more. It is difficult to judge a stone that is completely reflected, but if you look closely at the image, it has become clear that there is some "color unevenness" if it is a black stone that is slightly reflected. It was found that this color unevenness can be picked up by narrowing the range considered as "surroundings" in the processing of adaptive threshold. The block is the range that is considered to be the "surroundings".

binBoardWide = cv2.adaptiveThreshold(grayBoard, 255, cv2.ADAPTIVE_THRESH_GAUSSIAN_C, cv2.THRESH_BINARY, 127, -20)

binBoardNarrow = cv2.adaptiveThreshold(grayBoard, 255, cv2.ADAPTIVE_THRESH_GAUSSIAN_C, cv2.THRESH_BINARY, 7, 2)
#As a result of trial and error, after blurring, it was binarized with a threshold value.
binBoardNarrow = cv2.blur(binBoardNarrow, (3, 3))
_, binBoardNarrow = cv2.threshold(binBoardNarrow, 168, 255, cv2.THRESH_BINARY)

If block = 127 is wide, a fairly wide area will be white, but if it is narrow as block = 7, color unevenness will appear. Moreover, it is good that Shiraishi remains white.

Therefore, I decided to decide the color of the stone as follows depending on how many black pixels there are in the area with a radius of 10 from the center point (top surface) of the stone obtained in Step 3.

―― 10 or more for "wide" or 26 or more for "narrow" → Kuroishi --Other than that → Shiraishi

This threshold was also determined from the tendency of the distribution by plotting the number of black pixels from the actual image with black stones and white stones.

Complete! ... what is the accuracy?

Now that you can recognize the board of Othello, what is the accuracy? When I recognized the 76 images I had, the results were as follows.

--67 sheets: Correctly judge all stones --1 sheet: Failed to detect the range of the board (the board was not shown in the center) ―― 8 sheets: Misjudgment of color with a total of 14 stones

However, since it contains many images used for trial and error when developing recognition logic, I think that the actual accuracy is a little lower.

Here are some cases that I couldn't recognize well. NG1 I have decided that a5 is an empty space and h3 is Shiraishi, but the correct answer is Kuroishi. It seems that it cannot be recognized well in the case of a photo that is slightly out of focus.

I have judged the stone of e3 as black, but the correct answer is Shiraishi as you can see. Depending on the material of the board, the board itself may reflect, but it seems that it is vulnerable to the reflection of the board probably because the board is judged in green. NG3

I have determined that the stones of e7, e8, and f8 are white stones, but all of these are reflected black stones. Since the reflection is so strong, it is difficult for human eyes to make a judgment, but this algorithm could not make a correct judgment.

Also, as for the recognition performance, by resizing the long side to 1024px and then recognizing it, the performance is reasonable, and as long as it is running on the iPhone 8, it seems that it can be recognized several times per second.

A story that could not be explained this time

That's all for recognizing the actual Othello board, but if you implement the function to recognize the Othello board in the app,

--You also want the ability to recognize screenshots on the board of other apps. ――I want a function to recognize the board of a black-and-white printed book

It means that. For screenshots, the same algorithm as the actual board can be used to some extent, but there were cases where it could not be recognized well without specific consideration. For books printed in black and white, the strategy of judging the board surface in green cannot be used fundamentally, so it is useless unless it is reviewed from there.

I've implemented these in another way, but I'm leaving it here as the sloppy articles are getting longer. The Source Code includes screenshots and books, so if you are interested, please have a look there.

Reversi board surface recognized by OpenCV