Comment supprimer les défauts de convexité d'un carré de Sudoku ?

Question

Je faisais un projet amusant : Résoudre un Sudoku à partir d'une image d'entrée en utilisant OpenCV (comme dans les lunettes Google, etc.). Et j'ai terminé la tâche, mais à la fin j'ai trouvé un petit problème pour lequel je suis venu ici.

J'ai fait la programmation en utilisant l'API Python de OpenCV 2.3.1.

Voici ce que j'ai fait :

1. Lire l'image

2. Trouver les contours

3. Sélectionnez celui qui a la plus grande surface, ( et aussi un peu l'équivalent du carré).

4. Trouvez les points d'angle.

   Par exemple, le tableau ci-dessous :

   

   ( Remarquez ici que la ligne verte coïncide correctement avec la véritable limite du Sudoku, ce qui permet de déformer correctement le Sudoku. . Vérifier l'image suivante)

5. déformer l'image pour obtenir un carré parfait

   image eg :

   

6. Effectuez l'OCR (pour lequel j'ai utilisé la méthode que j'ai donnée dans Reconnaissance de chiffres simples OCR en OpenCV-Python )

Et la méthode a bien fonctionné.

Problème :

Vérifiez cette image.

L'exécution de l'étape 4 sur cette image donne le résultat ci-dessous :

La ligne rouge dessinée est le contour original qui est le véritable contour de la frontière du sudoku.

La ligne verte dessinée est un contour approximatif qui sera le contour de l'image déformée.

Il y a bien sûr une différence entre la ligne verte et la ligne rouge sur le bord supérieur du sudoku. Donc, en déformant, je n'obtiens pas la limite originale du Sudoku.

Ma question :

Comment puis-je déformer l'image sur la limite correcte du Sudoku, c'est-à-dire la ligne rouge OU comment puis-je supprimer la différence entre la ligne rouge et la ligne verte ? Existe-t-il une méthode pour cela dans OpenCV ?

Answer 1

J'ai une solution qui fonctionne, mais vous devrez la traduire vous-même en OpenCV. C'est écrit en Mathematica.

La première étape consiste à ajuster la luminosité de l'image, en divisant chaque pixel par le résultat d'une opération de fermeture :

src = ColorConvert[Import["http://davemark.com/images/sudoku.jpg"], "Grayscale"];
white = Closing[src, DiskMatrix[5]];
srcAdjusted = Image[ImageData[src]/ImageData[white]]

L'étape suivante consiste à trouver la zone du sudoku, afin de pouvoir ignorer (masquer) l'arrière-plan. Pour cela, j'utilise l'analyse en composantes connectées, et je sélectionne la composante qui a la plus grande surface convexe :

components = 
  ComponentMeasurements[
    ColorNegate@Binarize[srcAdjusted], {"ConvexArea", "Mask"}][[All, 
    2]];
largestComponent = Image[SortBy[components, First][[-1, 2]]]

En remplissant cette image, j'obtiens un masque pour la grille de sudoku :

mask = FillingTransform[largestComponent]

Maintenant, je peux utiliser un filtre dérivé de second ordre pour trouver les lignes verticales et horizontales dans deux images séparées :

lY = ImageMultiply[MorphologicalBinarize[GaussianFilter[srcAdjusted, 3, {2, 0}], {0.02, 0.05}], mask];
lX = ImageMultiply[MorphologicalBinarize[GaussianFilter[srcAdjusted, 3, {0, 2}], {0.02, 0.05}], mask];

J'utilise à nouveau l'analyse en composantes connectées pour extraire les lignes de la grille de ces images. Les lignes de grille sont beaucoup plus longues que les chiffres, je peux donc utiliser la longueur de l'étrier pour sélectionner uniquement les composants connectés aux lignes de grille. En les triant par position, j'obtiens 2x10 images de masque pour chacune des lignes de grille verticales/horizontales de l'image :

verticalGridLineMasks = 
  SortBy[ComponentMeasurements[
      lX, {"CaliperLength", "Centroid", "Mask"}, # > 100 &][[All, 
      2]], #[[2, 1]] &][[All, 3]];
horizontalGridLineMasks = 
  SortBy[ComponentMeasurements[
      lY, {"CaliperLength", "Centroid", "Mask"}, # > 100 &][[All, 
      2]], #[[2, 2]] &][[All, 3]];

Ensuite, je prends chaque paire de lignes de grille verticale/horizontale, je les dilate, je calcule l'intersection pixel par pixel, et je calcule le centre du résultat. Ces points sont les intersections des lignes de la grille :

centerOfGravity[l_] := 
 ComponentMeasurements[Image[l], "Centroid"][[1, 2]]
gridCenters = 
  Table[centerOfGravity[
    ImageData[Dilation[Image[h], DiskMatrix[2]]]*
     ImageData[Dilation[Image[v], DiskMatrix[2]]]], {h, 
    horizontalGridLineMasks}, {v, verticalGridLineMasks}];

La dernière étape consiste à définir deux fonctions d'interpolation pour le mappage X/Y à travers ces points, et à transformer l'image en utilisant ces fonctions :

fnX = ListInterpolation[gridCenters[[All, All, 1]]];
fnY = ListInterpolation[gridCenters[[All, All, 2]]];
transformed = 
 ImageTransformation[
  srcAdjusted, {fnX @@ Reverse[#], fnY @@ Reverse[#]} &, {9*50, 9*50},
   PlotRange -> {{1, 10}, {1, 10}}, DataRange -> Full]

Toutes les opérations sont des fonctions de traitement d'image de base, donc cela devrait être possible dans OpenCV aussi. La transformation d'image par spline pourrait être plus difficile, mais je ne pense pas que vous en ayez vraiment besoin. L'utilisation de la transformation de perspective que vous utilisez maintenant sur chaque cellule individuelle donnera probablement d'assez bons résultats.

Answer 2

La réponse de Nikie a résolu mon problème, mais sa réponse était en Mathematica. J'ai donc pensé que je devais donner son adaptation OpenCV ici. Mais après l'implémentation, j'ai pu voir que le code OpenCV est beaucoup plus gros que le code Mathematica de Nikie. Et aussi, je n'ai pas pu trouver la méthode d'interpolation faite par nikie dans OpenCV ( bien qu'elle puisse être faite en utilisant scipy, je le dirai en temps voulu).

1. Prétraitement de l'image (opération de fermeture)

import cv2
import numpy as np

img = cv2.imread('dave.jpg')
img = cv2.GaussianBlur(img,(5,5),0)
gray = cv2.cvtColor(img,cv2.COLOR_BGR2GRAY)
mask = np.zeros((gray.shape),np.uint8)
kernel1 = cv2.getStructuringElement(cv2.MORPH_ELLIPSE,(11,11))

close = cv2.morphologyEx(gray,cv2.MORPH_CLOSE,kernel1)
div = np.float32(gray)/(close)
res = np.uint8(cv2.normalize(div,div,0,255,cv2.NORM_MINMAX))
res2 = cv2.cvtColor(res,cv2.COLOR_GRAY2BGR)

Résultat :

2. Trouver le carré Sudoku et créer une image de masque

thresh = cv2.adaptiveThreshold(res,255,0,1,19,2)
contour,hier = cv2.findContours(thresh,cv2.RETR_TREE,cv2.CHAIN_APPROX_SIMPLE)

max_area = 0
best_cnt = None
for cnt in contour:
    area = cv2.contourArea(cnt)
    if area > 1000:
        if area > max_area:
            max_area = area
            best_cnt = cnt

cv2.drawContours(mask,[best_cnt],0,255,-1)
cv2.drawContours(mask,[best_cnt],0,0,2)

res = cv2.bitwise_and(res,mask)

Résultat :

3. Trouver des lignes verticales

kernelx = cv2.getStructuringElement(cv2.MORPH_RECT,(2,10))

dx = cv2.Sobel(res,cv2.CV_16S,1,0)
dx = cv2.convertScaleAbs(dx)
cv2.normalize(dx,dx,0,255,cv2.NORM_MINMAX)
ret,close = cv2.threshold(dx,0,255,cv2.THRESH_BINARY+cv2.THRESH_OTSU)
close = cv2.morphologyEx(close,cv2.MORPH_DILATE,kernelx,iterations = 1)

contour, hier = cv2.findContours(close,cv2.RETR_EXTERNAL,cv2.CHAIN_APPROX_SIMPLE)
for cnt in contour:
    x,y,w,h = cv2.boundingRect(cnt)
    if h/w > 5:
        cv2.drawContours(close,[cnt],0,255,-1)
    else:
        cv2.drawContours(close,[cnt],0,0,-1)
close = cv2.morphologyEx(close,cv2.MORPH_CLOSE,None,iterations = 2)
closex = close.copy()

Résultat :

4. Trouver des lignes horizontales

kernely = cv2.getStructuringElement(cv2.MORPH_RECT,(10,2))
dy = cv2.Sobel(res,cv2.CV_16S,0,2)
dy = cv2.convertScaleAbs(dy)
cv2.normalize(dy,dy,0,255,cv2.NORM_MINMAX)
ret,close = cv2.threshold(dy,0,255,cv2.THRESH_BINARY+cv2.THRESH_OTSU)
close = cv2.morphologyEx(close,cv2.MORPH_DILATE,kernely)

contour, hier = cv2.findContours(close,cv2.RETR_EXTERNAL,cv2.CHAIN_APPROX_SIMPLE)
for cnt in contour:
    x,y,w,h = cv2.boundingRect(cnt)
    if w/h > 5:
        cv2.drawContours(close,[cnt],0,255,-1)
    else:
        cv2.drawContours(close,[cnt],0,0,-1)

close = cv2.morphologyEx(close,cv2.MORPH_DILATE,None,iterations = 2)
closey = close.copy()

Résultat :

Bien sûr, celui-ci n'est pas si bon.

5. Trouver des points de grille

res = cv2.bitwise_and(closex,closey)

Résultat :

6. Corriger les défauts

Ici, nikie fait une sorte d'interpolation, sur laquelle je n'ai pas beaucoup de connaissances. Et je n'ai pas pu trouver de fonction correspondante pour cet OpenCV. (peut-être qu'elle existe, je ne sais pas).

Jetez un coup d'œil à ce SOF qui explique comment faire cela en utilisant SciPy, que je ne veux pas utiliser : Transformation d'images dans OpenCV

Donc, ici, j'ai pris 4 coins de chaque sous-carré et j'ai appliqué la Perspective de la chaîne sur chacun d'eux.

Pour cela, il faut d'abord trouver les centroïdes.

contour, hier = cv2.findContours(res,cv2.RETR_LIST,cv2.CHAIN_APPROX_SIMPLE)
centroids = []
for cnt in contour:
    mom = cv2.moments(cnt)
    (x,y) = int(mom['m10']/mom['m00']), int(mom['m01']/mom['m00'])
    cv2.circle(img,(x,y),4,(0,255,0),-1)
    centroids.append((x,y))

Mais les centroïdes résultants ne seront pas triés. Regardez l'image ci-dessous pour voir leur ordre :

Nous les trions donc de gauche à droite, de haut en bas.

centroids = np.array(centroids,dtype = np.float32)
c = centroids.reshape((100,2))
c2 = c[np.argsort(c[:,1])]

b = np.vstack([c2[i*10:(i+1)*10][np.argsort(c2[i*10:(i+1)*10,0])] for i in xrange(10)])
bm = b.reshape((10,10,2))

Maintenant voir ci-dessous leur ordre :

Enfin, nous appliquons la transformation et créons une nouvelle image de taille 450x450.

output = np.zeros((450,450,3),np.uint8)
for i,j in enumerate(b):
    ri = i/10
    ci = i%10
    if ci != 9 and ri!=9:
        src = bm[ri:ri+2, ci:ci+2 , :].reshape((4,2))
        dst = np.array( [ [ci*50,ri*50],[(ci+1)*50-1,ri*50],[ci*50,(ri+1)*50-1],[(ci+1)*50-1,(ri+1)*50-1] ], np.float32)
        retval = cv2.getPerspectiveTransform(src,dst)
        warp = cv2.warpPerspective(res2,retval,(450,450))
        output[ri*50:(ri+1)*50-1 , ci*50:(ci+1)*50-1] = warp[ri*50:(ri+1)*50-1 , ci*50:(ci+1)*50-1].copy()

Résultat :

Le résultat est presque le même que celui de Nikie, mais la longueur du code est grande. Peut-être que de meilleures méthodes sont disponibles, mais en attendant, cela fonctionne bien.

Salutations ARK.

Answer 3

Vous pourriez essayer d'utiliser une sorte de modélisation basée sur une grille pour votre déformation arbitraire. Et comme le sudoku est déjà une grille, cela ne devrait pas être trop difficile.

Vous pourriez donc essayer de détecter les limites de chaque sous-région 3x3, puis déformer chaque région individuellement. Si la détection réussit, vous obtiendrez une meilleure approximation.

Answer 4

J'ai trouvé que c'était un excellent article, et une excellente solution de la part d'ARK ; très bien présenté et expliqué.

Je travaillais sur un problème similaire, et j'ai construit l'ensemble. Il y a eu quelques changements (i.e. xrange en range, arguments dans cv2.findContours), mais cela devrait fonctionner sans problème (Python 3.5, Anaconda).

Il s'agit d'une compilation des éléments ci-dessus, à laquelle on a ajouté une partie du code manquant (c'est-à-dire l'étiquetage des points).

'''

https://stackoverflow.com/questions/10196198/how-to-remove-convexity-defects-in-a-sudoku-square

'''

import cv2
import numpy as np

img = cv2.imread('test.png')

winname="raw image"
cv2.namedWindow(winname)
cv2.imshow(winname, img)
cv2.moveWindow(winname, 100,100)

img = cv2.GaussianBlur(img,(5,5),0)

winname="blurred"
cv2.namedWindow(winname)
cv2.imshow(winname, img)
cv2.moveWindow(winname, 100,150)

gray = cv2.cvtColor(img,cv2.COLOR_BGR2GRAY)
mask = np.zeros((gray.shape),np.uint8)
kernel1 = cv2.getStructuringElement(cv2.MORPH_ELLIPSE,(11,11))

winname="gray"
cv2.namedWindow(winname)
cv2.imshow(winname, gray)
cv2.moveWindow(winname, 100,200)

close = cv2.morphologyEx(gray,cv2.MORPH_CLOSE,kernel1)
div = np.float32(gray)/(close)
res = np.uint8(cv2.normalize(div,div,0,255,cv2.NORM_MINMAX))
res2 = cv2.cvtColor(res,cv2.COLOR_GRAY2BGR)

winname="res2"
cv2.namedWindow(winname)
cv2.imshow(winname, res2)
cv2.moveWindow(winname, 100,250)

 #find elements
thresh = cv2.adaptiveThreshold(res,255,0,1,19,2)
img_c, contour,hier = cv2.findContours(thresh,cv2.RETR_TREE,cv2.CHAIN_APPROX_SIMPLE)

max_area = 0
best_cnt = None
for cnt in contour:
    area = cv2.contourArea(cnt)
    if area > 1000:
        if area > max_area:
            max_area = area
            best_cnt = cnt

cv2.drawContours(mask,[best_cnt],0,255,-1)
cv2.drawContours(mask,[best_cnt],0,0,2)

res = cv2.bitwise_and(res,mask)

winname="puzzle only"
cv2.namedWindow(winname)
cv2.imshow(winname, res)
cv2.moveWindow(winname, 100,300)

# vertical lines
kernelx = cv2.getStructuringElement(cv2.MORPH_RECT,(2,10))

dx = cv2.Sobel(res,cv2.CV_16S,1,0)
dx = cv2.convertScaleAbs(dx)
cv2.normalize(dx,dx,0,255,cv2.NORM_MINMAX)
ret,close = cv2.threshold(dx,0,255,cv2.THRESH_BINARY+cv2.THRESH_OTSU)
close = cv2.morphologyEx(close,cv2.MORPH_DILATE,kernelx,iterations = 1)

img_d, contour, hier = cv2.findContours(close,cv2.RETR_EXTERNAL,cv2.CHAIN_APPROX_SIMPLE)
for cnt in contour:
    x,y,w,h = cv2.boundingRect(cnt)
    if h/w > 5:
        cv2.drawContours(close,[cnt],0,255,-1)
    else:
        cv2.drawContours(close,[cnt],0,0,-1)
close = cv2.morphologyEx(close,cv2.MORPH_CLOSE,None,iterations = 2)
closex = close.copy()

winname="vertical lines"
cv2.namedWindow(winname)
cv2.imshow(winname, img_d)
cv2.moveWindow(winname, 100,350)

# find horizontal lines
kernely = cv2.getStructuringElement(cv2.MORPH_RECT,(10,2))
dy = cv2.Sobel(res,cv2.CV_16S,0,2)
dy = cv2.convertScaleAbs(dy)
cv2.normalize(dy,dy,0,255,cv2.NORM_MINMAX)
ret,close = cv2.threshold(dy,0,255,cv2.THRESH_BINARY+cv2.THRESH_OTSU)
close = cv2.morphologyEx(close,cv2.MORPH_DILATE,kernely)

img_e, contour, hier = cv2.findContours(close,cv2.RETR_EXTERNAL,cv2.CHAIN_APPROX_SIMPLE)

for cnt in contour:
    x,y,w,h = cv2.boundingRect(cnt)
    if w/h > 5:
        cv2.drawContours(close,[cnt],0,255,-1)
    else:
        cv2.drawContours(close,[cnt],0,0,-1)

close = cv2.morphologyEx(close,cv2.MORPH_DILATE,None,iterations = 2)
closey = close.copy()

winname="horizontal lines"
cv2.namedWindow(winname)
cv2.imshow(winname, img_e)
cv2.moveWindow(winname, 100,400)

# intersection of these two gives dots
res = cv2.bitwise_and(closex,closey)

winname="intersections"
cv2.namedWindow(winname)
cv2.imshow(winname, res)
cv2.moveWindow(winname, 100,450)

# text blue
textcolor=(0,255,0)
# points green
pointcolor=(255,0,0)

# find centroids and sort
img_f, contour, hier = cv2.findContours(res,cv2.RETR_LIST,cv2.CHAIN_APPROX_SIMPLE)
centroids = []
for cnt in contour:
    mom = cv2.moments(cnt)
    (x,y) = int(mom['m10']/mom['m00']), int(mom['m01']/mom['m00'])
    cv2.circle(img,(x,y),4,(0,255,0),-1)
    centroids.append((x,y))

# sorting
centroids = np.array(centroids,dtype = np.float32)
c = centroids.reshape((100,2))
c2 = c[np.argsort(c[:,1])]

b = np.vstack([c2[i*10:(i+1)*10][np.argsort(c2[i*10:(i+1)*10,0])] for i in range(10)])
bm = b.reshape((10,10,2))

# make copy
labeled_in_order=res2.copy()

for index, pt in enumerate(b):
    cv2.putText(labeled_in_order,str(index),tuple(pt),cv2.FONT_HERSHEY_DUPLEX, 0.75, textcolor)
    cv2.circle(labeled_in_order, tuple(pt), 5, pointcolor)

winname="labeled in order"
cv2.namedWindow(winname)
cv2.imshow(winname, labeled_in_order)
cv2.moveWindow(winname, 100,500)

# create final

output = np.zeros((450,450,3),np.uint8)
for i,j in enumerate(b):
    ri = int(i/10) # row index
    ci = i%10 # column index
    if ci != 9 and ri!=9:
        src = bm[ri:ri+2, ci:ci+2 , :].reshape((4,2))
        dst = np.array( [ [ci*50,ri*50],[(ci+1)*50-1,ri*50],[ci*50,(ri+1)*50-1],[(ci+1)*50-1,(ri+1)*50-1] ], np.float32)
        retval = cv2.getPerspectiveTransform(src,dst)
        warp = cv2.warpPerspective(res2,retval,(450,450))
        output[ri*50:(ri+1)*50-1 , ci*50:(ci+1)*50-1] = warp[ri*50:(ri+1)*50-1 , ci*50:(ci+1)*50-1].copy()

winname="final"
cv2.namedWindow(winname)
cv2.imshow(winname, output)
cv2.moveWindow(winname, 600,100)

cv2.waitKey(0)
cv2.destroyAllWindows()

Answer 5

Pour supprimer les coins non affectés, j'ai appliqué une correction gamma avec une valeur gamma de 0,8.

Le cercle rouge est dessiné pour montrer le coin manquant.

Le code est :

gamma = 0.8
invGamma = 1/gamma
table = np.array([((i / 255.0) ** invGamma) * 255
                  for i in np.arange(0, 256)]).astype("uint8")
cv2.LUT(img, table, img)

Ceci s'ajoute à la réponse d'Abid Rahman si certains points d'angle sont manquants.