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

je faisais un projet amusant: résoudre un Sudoku à partir d'une image d'entrée en utilisant OpenCV (comme dans Google lunettes 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 D'OpenCV 2.3.1.

ci-dessous, c'est ce que j'ai fait:

  1. Lire l'image
  2. trouver les contours
  3. sélectionnez celui avec surface maximale, (et aussi un peu équivalente à carré).
  4. Trouvez les points d'angle.

    p.ex. indiqué ci-dessous:

    enter image description here

    ( noter ici que la ligne verte coïncide correctement avec la limite vraie du Sudoku, de sorte que le Sudoku peut être correctement Déformé . Vérifier l'image suivante)

  5. "151900920 de chaîne", l'image de l' carré parfait

    eg image:

    enter image description here

  6. effectuer OCR (pour lequel j'ai utilisé la méthode que j'ai donnée dans reconnaissance de chiffre simple OCR en OpenCV-Python )

et la méthode a bien fonctionné.

problème:

Check out this image.

exécuter l'étape 4 sur cette image donne le résultat suivant:

enter image description here

la ligne rouge tracée est le contour original qui est le vrai contour de la limite sudoku.

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

qui, bien sûr, il ya une différence entre la ligne verte et la ligne rouge à la bord supérieur du sudoku. Donc pendant que je déforme, Je n'obtiens pas la frontière 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? Y a-t-il une méthode pour cela dans OpenCV?

161
demandé sur Community 2012-04-17 21:39:18

4 réponses

j'ai une solution qui fonctionne, mais vous devrez la traduire pour OpenCV vous-même. 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]]

enter image description here

la prochaine étape est de trouver la zone sudoku, donc je peux ignorer (masquer) l'arrière-plan. Pour cela, j'utilise le composant connecté analyse, et de sélectionner 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]]]

enter image description here

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

mask = FillingTransform[largestComponent]

enter image description here

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];

enter image description here

j'utilise à nouveau l'analyse des composants connectés pour extraire les lignes de grille de ces images. Les lignes de grille sont beaucoup plus longues que les chiffres, donc je peux utiliser la longueur de caliper pour sélectionner seulement les lignes de grille-composants connectés. En les triant par position, j'obtiens des images de masque 2x10 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]];

enter image description here

ensuite je prends chaque paire de lignes de quadrillage verticales/horizontales, dilatez-les, calculez l'intersection pixel par pixel, et calculez le centre du résultat. Ces points sont les intersections de la ligne de quadrillage:

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}];

enter image description here

la dernière étape est de définir deux fonctions d'interpolation pour la cartographie X/Y à travers ces points, et de 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]

enter image description here

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 basée sur spline peut être plus difficile, mais je ne pense pas que vous en ayez vraiment besoin. Probablement en utilisant la transformation de perspective que vous utilisez maintenant sur chaque cellule individuelle donnera de bons résultats.

218
répondu Niki 2012-04-20 07:21:37

la réponse de Nikie a résolu mon problème, mais sa réponse était dans Mathematica. Donc j'ai pensé que je devrais donner son adaptation OpenCV ici. Mais après la mise en œuvre, je pouvais voir que le code OpenCV est beaucoup plus grand que le code mathematica de nikie. Et aussi, je n'ai pas pu trouver la méthode d'interpolation fait par nikie dans OpenCV ( bien que cela puisse être fait en utilisant scipy, je vais le dire quand vient le temps.)

1. Prétraitement d'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:

Result of closing

2. Trouver la place 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:

enter image description here

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:

enter image description here

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:

enter image description here

bien sûr, ce n'est pas si bon.

5. Trouver Les Points De Grille

res = cv2.bitwise_and(closex,closey)

résultat:

enter image description here

6. La correction de la défauts

ici, nikie fait une sorte d'interpolation, à propos de laquelle je n'ai pas beaucoup de connaissances. Et je n'ai trouvé aucune fonction correspondante pour cette OpenCV. (peut-être que c'est là, je ne sais pas).

découvrez ce SOF qui explique comment faire cela en utilisant SciPy, que je ne veux pas utiliser: transformation D'Image en OpenCV

donc, ici j'ai pris 4 coins de chaque sous-carré et appliqué warp point de vue de chacun.

pour cela, nous trouvons d'abord 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 ne seront pas triés. Voir l'image ci-dessous pour voir leur commande:

enter image description here

nous avons 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 :

enter image description here

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:

enter image description here

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

en ce qui Concerne ARCHE.

183
répondu Abid Rahman K 2017-05-23 10:31:10

vous pourriez essayer d'utiliser une sorte de modélisation basée sur la grille de vous gauchissement arbitraire. Et puisque le sudoku est déjà une grille, ça ne devrait pas être trop dur.

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

5
répondu sietschie 2012-04-18 06:54:09

je veux ajouter que la méthode ci-dessus ne fonctionne que lorsque la planche sudoku est droite, sinon le test de rapport hauteur/largeur (ou vice versa) échouera très probablement et vous ne serez pas en mesure de détecter les bords de sudoku. (Je tiens aussi à ajouter que si les lignes ne sont pas perpendiculaires aux bordures de l'image, les opérations de sobel (dx et dy) fonctionneront encore car les lignes auront toujours des bordures par rapport aux deux axes.)

pour pouvoir détecter les lignes droites, vous devez travailler sur le contour ou analyse au niveau des pixels tels que contourArea / boundingRectArea, points en haut à gauche et en bas à droite...

Edit: j'ai réussi à vérifier si un ensemble de contours forme une ligne ou non en appliquant la régression linéaire et en vérifiant l'erreur. Toutefois, la régression linéaire a mal fonctionné lorsque la pente de la ligne est trop grande (c.-à-d. >1000) ou très proche de 0. Par conséquent, l'application du test de ratio ci-dessus (dans la réponse la plus corrigée) avant la régression linéaire est logique et a fonctionné pour moi.

1
répondu Ali Eren Çelik 2018-10-11 11:10:54