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:
- Lire l'image
- trouver les contours
- sélectionnez celui avec surface maximale, (et aussi un peu équivalente à carré).
-
Trouvez les points d'angle.
p.ex. indiqué ci-dessous:
( 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)
- "151900920 de chaîne", l'image de l' carré parfait
eg image:
-
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:
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?
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]]
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]]]
en remplissant cette image, j'obtiens un masque pour la grille 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 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]];
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}];
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]
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.
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:
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:
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, ce n'est pas si bon.
5. Trouver Les Points De Grille
res = cv2.bitwise_and(closex,closey)
résultat:
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:
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 :
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, de meilleures méthodes sont disponibles là-bas, mais en attendant, cela fonctionne bien.
en ce qui Concerne ARCHE.
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.
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.