introduction

Cette année, un calendrier de l'Avent Othello était prévu et invité, j'ai donc décidé d'écrire un article. En fait, j'ai écrit un autre article le Jour 1, mais je ne savais pas ce que je faisais et je suis soudainement entré dans l'article, donc cette fois Une petite auto-introduction.

Je développe une application pour iOS appelée [Kifu Box](https://itunes.apple.com/jp/app/Kifu box / id1434692901? Mt = 8). Comme l'une des fonctions, nous avons intégré une fonction pour prendre une photo de la carte Othello avec une caméra et superposer la valeur d'évaluation sur la carte avec AR. Cliquez sur l'image suivante pour voir la vidéo d'introduction. Il a également la capacité de prendre une photo de la planche (ou de sélectionner la photo prise) et de reconnaître le placement des pierres sur la planche. Cela a également une vidéo d'introduction.

Dans cet article, je voudrais expliquer comment ces fonctions reconnaissent la surface de la carte Othello. Lorsque vous entrez l'image à gauche ci-dessous, le but est de reconnaître la position des pierres noires et des pierres blanches et l'état des espaces vides comme indiqué dans l'image de droite. 認識結果

Environnement prérequis

Python3.7.1
OpenCV 4.1.0

Étant donné que l'application réelle est iOS, je l'ai implémentée avec Objective C + OpenCV, mais dans cet article je vais l'expliquer avec la version Python. Le contenu lui-même est presque le même que la version de l'application.

Veuillez vous référer à la version Python complète du code source ci-dessous. https://github.com/lavox/reversi_recognition

politique

Il existe deux approches principales pour reconnaître les images.

Comment utiliser l'apprentissage automatique
Comment créer un algorithme par vous-même

En ce qui concerne le premier, il semblait difficile de collecter une grande quantité d'images d'enseignants pour l'apprentissage, et il semblait difficile de régler quand les choses tournaient mal, j'ai donc décidé d'adopter la dernière méthode. La reconnaissance d'image est effectuée dans les étapes suivantes.

Identifiez la portée de la carte
Convertir en carré
Identifiez l'emplacement de la pierre
Déterminez la couleur de la pierre

Dans la fonction pour prendre une photo avec l'appareil photo et capturer le tableau, après avoir effectué 1, l'écran de confirmation de portée s'affiche puis 2 à 4, mais dans la fonction AR, 1 à 4 sont exécutés à la fois.

Préparation

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

L'image est lue et lissée (floue) dans une taille de 3x3. Lors de l'analyse d'images, il semble que la théorie établie consiste à lisser à l'avance, alors je l'ai fait.

Dans le cas de Python, l'image chargée sera un tableau de NumPy avec 3 éléments pour chaque pixel, mais veuillez noter que l'ordre des 3 éléments est BGR au lieu de RVB. Lors de l'affichage à l'aide de matplotlib etc., la teinte sera étrange à moins que le format (ordre des couleurs) ne soit changé.

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

Étape 1. Spécification de la plage de la carte

La surface de la planche d'Othello étant verte, j'ai décidé de procéder dans le sens de l'extraction de la zone verte. Comme il est difficile d'extraire la gamme de couleurs au format BGR, convertissez-la au format HSV.

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

Depuis qu'il est devenu le format HSV, j'ai décidé de spécifier la plage de la zone de couleur avec H, et S et V considèrent la zone au-dessus d'une certaine valeur comme verte. 緑色領域

Je voulais vraiment le rendre incurvé, mais comme le traitement est gênant, la zone où le côté supérieur droit des deux zones est combiné est appelée "verte". La valeur limite a été déterminée par essais et erreurs tout en regardant réellement l'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)

Dans OpenCV, vous pouvez spécifier la plage avec ʻin Range. bitwise_orest littéralement un OU entre les régions. <img width="480" alt="緑色領域抽出" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/202945/34dfef8d-c58a-ea8e-0e9f-3882702e7d11.png "> La zone verte a été extraite. De là, je voudrais trouver les coordonnées des sommets des quatre coins du plateau, mais comment les trouver à partir de cette image binarisée? Je suis également préoccupé par le fait qu'il existe plusieurs tableaux. Après avoir recherché diverses choses, j'ai trouvé une fonction appeléefindContours` qui détecte les contours, je vais donc l'utiliser.

Cette fonction a renvoyé 3 valeurs de retour à l'ère V3, mais veuillez noter qu'il semble qu'elle soit passée de V4 à 2.

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

En conséquence, plus de 2000 contours ont été extraits. Qu'est-il arrivé? J'ai dessiné quelques grandes lignes. 緑色領域抽出 Il était séparé par des lignes noires et des pierres dans les carrés. En regardant les contours plus fins, j'ai trouvé que les contours étaient constitués d'un seul pixel, et que ce findContours juge les contours assez sévèrement. Lorsque j'ai cherché sur le net des techniques pour supprimer les obstacles tels que les lignes noires, j'ai trouvé que conversion de morphologie /html/py_tutorials/py_imgproc/py_morphological_ops/py_morphological_ops.html) Je l'ai trouvé. C'est une méthode qui vous permet d'effacer les ridules et la poussière en dilatant la zone une fois pour l'agrandir, puis l'éroder.

Alors, dans quelle mesure devrait-il s'étendre et se contracter? Quand je l'ai calculé dans le cas où la planche est pleine d'images, l'épaisseur de la ligne semble être d'environ 0,6 à 0,7% du côté long, donc 0,35 sur le côté long pour agrandir et effacer cela des deux côtés J'ai décidé de le faire%.

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) #Rétrécir

Il y a un «* 2 + 1» qui est un peu flou, mais il semble que la taille de l'expansion et de la contraction doit être un nombre impair, donc c'est une correction pour en faire un nombre impair. 膨張・収縮 J'ai réussi à effacer la ligne. Cependant, lorsque le nombre de pierres augmente, il semble être divisé par des pierres, ce qui est un peu dangereux. Je n'ai pas pu m'en empêcher, j'ai donc décidé de franchir le pas et de considérer non seulement la partie verte mais aussi la partie blanche comme faisant partie du tableau. (La partie noire est vraiment noire, donc je l'ai arrêtée car elle se répand trop)

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

Le tableau est blanc, donc je suis un peu inquiet, mais le risque de division a considérablement diminué, et la portée du tableau est claire, alors j'ai décidé de procéder. Maintenant, réextrayons le contour.

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

Il y a une entaille dans la pierre sur le côté, mais elle n'est plus divisée. Ce que je veux faire c'est

―― Que puis-je faire pour la bosse? ――Comment sélectionner le contour de la planche auquel vous faites attention lorsque de nombreux contours sont extraits

C'est un endroit comme ça. Lorsque j'ai recherché quelque chose qui ne pouvait pas être fait pour la première bosse, [package convex](http://labs.eecs.tottori-u.ac.jp/sd/Member/oyamada/OpenCV/html/py_tutorials/py_imgproc/py_contours Il y avait une méthode (/py_contour_features/py_contour_features.html#convex-hull).

S'il peut être rendu convexe, c'est celui qui inclut le point central de l'image dans le contour extrait (j'ai supposé qu'il est au centre car il faut le prendre pour reconnaître la surface de la planche), le second Il semble qu'il sera possible de définir le contour à sélectionner, ce qui posait problème.

for i, c in enumerate(contours):
    hull = cv2.convexHull(c) #Paquet convexe
    if cv2.pointPolygonTest(hull,(width / 2 , height / 2), False) > 0: #Déterminez s'il contient le centre
        mask = np.zeros((height, width),dtype=np.uint8)
        cv2.fillPoly(mask, pts=[hull], color=(255)) #Image remplie dans la plage de contour
        break

Pour le moment, la surface de la planche est obtenue. Cependant, comme j'ai ajouté une partie blanche pour éviter la division, je suis un peu inquiet si cela implique une zone supplémentaire. J'ai donc essayé d'extraire la partie verte dans cette zone, de prendre le contour et de les connecter tous.

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)

Je pensais que le contour pouvait être extrait en toute sécurité avec cela, mais lorsque j'ai affiché la valeur, c'était un carré à 26 côtés.

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

Même si cela semble presque droit, il semble qu'il y ait réellement des sommets entre les deux. OpenCV avait également une contre-mesure pour cette situation. ʻApproxPolyDP` est une fonction qui se rapproche d'un polygone.

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

À la suite d'essais et d'erreurs, il semble que dans la plupart des cas, il devienne un carré avec une bonne sensation en définissant 0,4% de la circonférence comme une erreur.

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

Avec cela, j'ai pu trouver les quatre sommets du plateau, mais j'aimerais aborder certains détails qui n'ont pas pu être écrits ici.

S'il y a une pierre près du coin, ou si le coin est coupé de l'image, le coin peut être ébréché et devenir un pentagone ou un hexagone. Dans un tel cas, les côtés doivent correspondre, j'ai donc choisi quatre côtés dans l'ordre du plus long des polygones extraits et j'ai décidé de considérer l'intersection comme le sommet. Il s'agit d'un problème mathématique plutôt que d'un OpenCV, donc si vous êtes intéressé, veuillez vous rendre sur Code source des lignes 371 à 396. Et regardez autour de la 99e à la 107e lignes.
Parfois, vous sélectionnez une zone qui n'est pas un tableau «Ceci est inévitable en soi, mais quand on juge que l'original n'est pas un carré, cela est considéré comme un échec. C'est aussi un problème mathématique, donc si vous êtes intéressé, veuillez aller au Code source des lignes 438 à 485 et des lignes 125. Veuillez vous référer aux 1ère à 197ème lignes. En tant que sous-produit de ceci, la relation de position relative entre la carte et la caméra peut être obtenue, qui sera utilisée plus tard. --Correction de l'orientation de la carte --Les sommets sont repris de sorte qu'ils soient dans le sens des aiguilles d'une montre à partir du coin supérieur gauche de l'image. ――Vérifiez si la carte n'est pas coupée --La bordure de la planche Othello est légèrement plus épaisse sur la circonférence extérieure, donc sa correction
Si la taille de l'image est trop grande, le traitement prendra du temps, alors redimensionnez d'abord

Étape 2. Convertissez la partie de la planche en carré

Je vais convertir la planche obtenue à l'étape 1 en carré, mais pour faciliter le traitement ultérieur, je vais donner une marge (cadre bleu) autour d'elle. Le but de la marge est le suivant.

Lors de la vérification ultérieure de la couleur de la pierre, assurez-vous que la plage de contrôle ne dépasse pas l'image. --Si le coin de la planche est coupé, il peut être traité de la même manière que la partie découpée.

margin = 13 #Largeur de la marge
cell_size = 42 #1 taille carrée
size = cell_size * 8 + margin * 2 #Longueur de côté après conversion
outer = (254, 0, 0) #Couleur de la pièce de marge

La conversion en carré est en fait facile, et si vous connaissez les sommets source et de destination, vous pouvez effectuer une conversion de projection.

#4 sommets de la source
src = np.array([[1045,1639], [2418,1613], [2723,2702], [ 675,2669]], dtype=np.float32)
#4 sommets vers lesquels se déplacer
dst = np.array([
    [margin, margin],
    [size - 1 - margin, margin],
    [size - 1 - margin, size - 1 - margin],
    [margin, size - 1 - margin]
], dtype=np.float32)
#Matrice de transformation
trans = cv2.getPerspectiveTransform(src, dst)
#Conversion de projection
board = cv2.warpPerspective(image, trans, (int(size), int(size)), flags=cv2.INTER_LINEAR, borderMode=cv2.BORDER_CONSTANT, borderValue=outer)

En guise de mise en garde, la conversion de projection externe ci-dessus est une couleur pour compenser la partie en saillie lorsque les quatre sommets dépassent de l'image. Il ne remplit pas les marges. Donc, je vais également peindre la partie marge.

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)

Vous avez maintenant rendu le plateau carré.

Étape 3. Identifiez la position de la pierre

En localisant la pierre, je me demandais s'il fallait supposer que la pierre était au centre de la place. Puisqu'il s'agit d'une planche réelle, il y a des cas où les pierres sont placées hors du centre, et il y a des cas où le centre est décalé en raison de l'épaisseur des pierres dans l'image après l'avoir convertie en carré si elle est prise sous un angle. J'ai donc décidé de procéder sans supposer que la pierre est au centre de la place.

Alors, comment identifier la position de la pierre, j'ai d'abord pensé qu'il serait préférable d'utiliser une transformation de Huff qui détecte le cercle car la pierre est circulaire. Cependant, quand je l'ai essayé, j'ai détecté un grand nombre de cercles mystérieux invisibles à l'œil humain, et l'ajustement a été frustré car il y avait de nombreux paramètres. * De plus, dans l'application appelée ScoreNow, j'ai entendu du développeur qu'il utilise la conversion Huff pour détecter les pierres, donc je l'ai bien ajusté. Je pense que tu peux le faire. *

Après avoir cherché diversement à perte, je suis arrivé à l'article Détails sur l'algorithme de segmentation d'objets "Watershed" et j'ai décidé d'essayer cette méthode. fait. Dans ce cas, plutôt que de trouver le contour exact de la pierre, nous recherchons le centre de la pierre, nous n'exécutons donc qu'une partie de l'article lié.

Tout d'abord, afin de séparer la planche et la pierre, extrayez la partie planche dans la partie verte comme à l'étape 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)

Vous pouvez extraire la partie en pierre en ajoutant la partie bleue de la marge, puis en la retournant.

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

La ligne du carré reste, mais elle n'affectera pas en particulier le traitement ultérieur, alors laissez-la telle quelle cette fois.

Aussi, considérant la possibilité que des mains humaines soient réellement réfléchies, il existe également un processus qui traite la partie qui n'est ni verte, ni blanche, ni noire comme une cellule "inconnue", mais elle sera longue, je vais donc l'omettre. ..

Maintenant, selon l'article de Qiita plus tôt, trouvez la distance entre l'extérieur de la pierre et chaque point.

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

Le point avec la valeur maximale de chaque île (?) Est susceptible d'être le centre de la pierre. Cependant, comme certaines îles sont désormais connectées, les points au-dessus d'une certaine valeur sont extraits et séparés. Si «une valeur» est trop grande, des pierres méconnaissables peuvent se produire, mais si elle est trop petite, la connexion peut ne pas être séparée, et à la suite d'essais et d'erreurs, 13,0 a été défini comme seuil.

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

Le point maximum de chaque zone de connexion doit être le centre de la pierre, alors trouvez-le.

distThr = np.uint8(distThr) #Conversion de type requise
#Obtenez le composant de liaison
labelnum, labelimg, data, center = cv2.connectedComponentsWithStats(distThr)
for i in range(1, labelnum): # i =Exclure car 0 est l'arrière-plan
    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])

De plus, comme les îles ne sont pas bien séparées et deviennent bimodales, la source réelle fait une chose un peu compliquée de bouclage tout en effaçant le voisinage de la valeur maximale, mais ici c'est simple Il est devenu. 石の分離 J'ai pu trouver le centre de la pierre avec une précision raisonnable. En guise de souci, les pierres ont la forme de tambours au lieu de cercles car les photos diagonales sont forcées en carrés, de préférence la couleur de la pierre est proche du centre du haut et la position de la pierre est au centre du bas. Je veux juger. Pour gérer cela, en fonction de la position de la caméra obtenue au moment de l'extraction de la planche, le centre de la pierre est décalé vers le côté éloigné et le côté proche de la caméra et considéré comme le centre de la surface supérieure et de la surface inférieure, mais il devient plus long. Donc (même si c'est déjà assez long ...) je vais omettre l'explication cette fois.

Étape 4. Jugement de la couleur de la pierre

Il est maintenant temps de juger de la couleur de la pierre. Fondamentalement, il semble bon de juger par la luminosité de la couleur près du centre de la pierre, mais lorsque je l'ai essayé, des problèmes sont survenus.

Puisque la précision du point central n'est pas parfaite, si vous élargissez la plage de jugement, cela prendra la couleur de la pierre adjacente ou du côté de la pierre et provoquera une fausse détection. ――Il est difficile de juger Kuroishi dans un environnement lumineux et Shiraishi dans un environnement sombre uniquement par le V (luminosité) du HSV. --Kuroishi peut ressembler à Shiraishi en raison de la réflexion de la lumière. C'est aussi blanc qu'un vrai Shiraishi.

En ce qui concerne le deuxième point, j'ai d'abord fait la condition en comparant la luminosité avec l'environnement, mais après cela j'ai trouvé une méthode plus simple pour juger en utilisant OpenCV. C'est le processus de binarisation basé sur la situation environnante appelée seuil adaptatif. Avec cela, les pierres blanches deviennent blanches quelle que soit la luminosité de l'environnement.

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

Après l'échelle de gris, j'exécute le seuil adaptatif. adaptive threshold Maintenant, les pierres blanches sont assez blanches, mais il y a encore des pierres noires qui sont blanchâtres, alors j'aimerais en imaginer un peu plus. Il est difficile de juger une pierre qui est complètement réfléchie, mais si vous regardez de près l'image, il est devenu clair qu'il y a une certaine «inégalité de couleur» s'il s'agit d'une pierre noire légèrement réfléchie. Il a été constaté que cette inégalité de couleur peut être détectée en rétrécissant la plage considérée comme «environnement» dans le traitement du seuil adaptatif. Le bloc est la plage qui est considérée comme «l'environnement».

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)
#À la suite d'essais et d'erreurs, après le flou, il a été binarisé avec un seuil.
binBoardNarrow = cv2.blur(binBoardNarrow, (3, 3))
_, binBoardNarrow = cv2.threshold(binBoardNarrow, 168, 255, cv2.THRESH_BINARY)

Si block = 127 est large, une zone assez large sera blanche, mais si elle est étroite comme block = 7, des irrégularités de couleur apparaîtront. De plus, il est bon que Shiraishi reste blanc.

Par conséquent, j'ai décidé de décider de la couleur de la pierre comme suit en fonction du nombre de pixels noirs dans la zone avec un rayon de 10 à partir du point central (surface supérieure) de la pierre obtenue à l'étape 3.

―― 10 ou plus pour "large" ou 26 ou plus pour "étroit" → Kuroishi --Autre que ça → Shiraishi

Ce seuil a également été déterminé à partir de la tendance de la distribution en traçant le nombre de pixels noirs de l'image réelle avec des pierres noires et des pierres blanches.

Achevée! ... quelle est la précision?

Maintenant que vous pouvez reconnaître la carte Othello, quelle est la précision? Lorsque j'ai reconnu les 76 images que j'avais, les résultats étaient les suivants.

--67 feuilles: juger correctement toutes les pierres -1 feuille: Impossible de détecter la portée de la carte (la carte n'était pas affichée au centre) ―― 8 feuilles: mauvaise appréciation de la couleur avec un total de 14 pierres

Cependant, comme il contient de nombreuses images utilisées à des fins d'essais et d'erreurs lors du développement de la logique de reconnaissance, je pense que la précision réelle est un peu inférieure.

Voici quelques cas que je n'ai pas bien reconnu. NG1 J'ai déterminé que a5 est un espace vide et h3 est Shiraishi, mais les bonnes réponses sont à la fois Kuroishi. Il semble que cela ne soit pas bien reconnu dans le cas d'une photo légèrement floue.

J'ai jugé la pierre de e3 comme noire, mais la bonne réponse est Shiraishi comme vous pouvez le voir. Selon le matériau de la planche, la planche elle-même peut refléter, mais il semble qu'elle soit vulnérable au reflet de la planche probablement parce que la planche est jugée en vert. NG3

J'ai déterminé que les pierres de e7, e8 et f8 sont des pierres blanches, mais la bonne réponse est les pierres noires réfléchies. Étant donné que la réflexion est si intense, il est difficile pour les yeux humains de porter un jugement, mais cet algorithme n'a pas pu faire un jugement correct.

Aussi, en ce qui concerne les performances de reconnaissance, en redimensionnant le côté long à 1024px puis en le reconnaissant, les performances sont raisonnables, et tant qu'il fonctionne sur iPhone 8, il semble qu'il puisse être reconnu plusieurs fois par seconde.

Une histoire qui ne s'explique pas cette fois

C'est tout pour reconnaître la carte Othello réelle, mais si vous implémentez la fonction pour reconnaître la carte Othello dans l'application,

――Je souhaite également pouvoir reconnaître les captures d'écran d'autres applications ――Je veux une fonction pour reconnaître le tableau des livres imprimés en noir et blanc

Cela signifie que. Pour les captures d'écran, le même algorithme que la carte réelle peut être utilisé dans une certaine mesure, mais il y avait des cas où il ne pouvait pas être bien reconnu sans considération spécifique. En ce qui concerne les livres imprimés en noir et blanc, la stratégie consistant à juger la surface du tableau en vert ne peut pas être utilisée fondamentalement, elle est donc inutile à moins qu'elle ne soit revue à partir de là.

Je les ai implémentés d'une autre manière, mais les articles bâclés s'allongent, je vais donc le laisser ici. Le Code source comprend des captures d'écran et des livres, donc si vous êtes intéressé, veuillez y jeter un œil.

Reconnaissez la carte Othello avec OpenCV