webentwicklung-frage-antwort-db.com.de

Wie entferne ich Konvexitätsfehler in einem Sudoku-Quadrat?

Ich habe ein lustiges Projekt gemacht: Ein Sudoku aus einem Eingabebild mit OpenCV lösen (wie in Google-Brillen usw.). Und ich habe die Aufgabe erledigt, aber am Ende habe ich ein kleines Problem gefunden, für das ich hierher gekommen bin.

Ich habe die Programmierung mit der Python API von OpenCV 2.3.1.

Unten ist was ich getan habe:

  1. Lesen Sie das Bild
  2. Finde die Konturen
  3. Wählen Sie diejenige mit der maximalen Fläche (und auch etwas äquivalent zum Quadrat).
  4. Finde die Eckpunkte.

    z.B. unten angegeben:

    enter image description here

    ( Beachten Sie hier, dass die grüne Linie korrekt mit der wahren Grenze des Sudoku übereinstimmt, so dass das Sudoku korrekt verzogen werden kann . Nächstes Bild prüfen)

  5. verwerfe das Bild zu einem perfekten Quadrat

    zB Bild:

    enter image description here

  6. OCR ausführen (für die ich die Methode verwendet habe, die ich in Simple Digit Recognition OCR in OpenCV-Python angegeben habe)

Und die Methode hat gut funktioniert.

Problem:

Schauen Sie sich dieses Bild an .

Wenn Sie Schritt 4 für dieses Bild ausführen, erhalten Sie das folgende Ergebnis:

enter image description here

Die gezeichnete rote Linie ist die ursprüngliche Kontur, die den wahren Umriss der Sudoku-Grenze darstellt.

Die gezeichnete grüne Linie ist eine ungefähre Kontur, die den Umriss des verzerrten Bildes darstellt.

Was natürlich den Unterschied zwischen der grünen und der roten Linie am oberen Rand des Sudoku ausmacht. Beim Verziehen erreiche ich also nicht die ursprüngliche Grenze des Sudoku.

Meine Frage:

Wie kann ich das Bild an der korrekten Grenze des Sudoku verziehen, d. H. An der roten Linie OR wie kann ich den Unterschied zwischen der roten und der grünen Linie beseitigen? Gibt es in OpenCV eine Methode dafür?

176
Abid Rahman K

Ich habe eine Lösung, die funktioniert, aber Sie müssen sie selbst in OpenCV übersetzen. Es ist in Mathematica geschrieben.

Der erste Schritt besteht darin, die Helligkeit im Bild anzupassen, indem jedes Pixel mit dem Ergebnis eines Schließvorgangs geteilt wird:

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

Der nächste Schritt ist, den Sudoku-Bereich zu finden, damit ich den Hintergrund ignorieren (maskieren) kann. Dazu verwende ich die Analyse verbundener Komponenten und wähle die Komponente mit der größten konvexen Fläche aus:

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

enter image description here

Wenn ich dieses Bild ausfülle, erhalte ich eine Maske für das Sudoku-Gitter:

mask = FillingTransform[largestComponent]

enter image description here

Jetzt kann ich einen Ableitungsfilter 2. Ordnung verwenden, um die vertikalen und horizontalen Linien in zwei separaten Bildern zu finden:

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

Ich verwende erneut die Analyse verbundener Komponenten, um die Gitterlinien aus diesen Bildern zu extrahieren. Die Gitterlinien sind viel länger als die Ziffern, sodass ich mit der Messschieberlänge nur die mit den Gitterlinien verbundenen Komponenten auswählen kann. Durch Sortieren nach Position erhalte ich 2x10 Maskenbilder für jede der vertikalen/horizontalen Gitterlinien im Bild:

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

Als nächstes nehme ich jedes Paar vertikaler/horizontaler Gitterlinien, dilatiere sie, berechne den pixelweisen Schnittpunkt und berechne die Mitte des Ergebnisses. Diese Punkte sind die Schnittpunkte der Gitterlinien:

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

Der letzte Schritt besteht darin, zwei Interpolationsfunktionen für das X/Y-Mapping durch diese Punkte zu definieren und das Bild mit diesen Funktionen zu transformieren:

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

Alle Operationen sind grundlegende Bildverarbeitungsfunktionen, daher sollte dies auch in OpenCV möglich sein. Die spline-basierte Bildtransformation mag schwieriger sein, aber ich glaube nicht, dass Sie sie wirklich brauchen. Wenn Sie die Perspektiventransformation verwenden, die Sie jetzt für jede einzelne Zelle verwenden, erhalten Sie wahrscheinlich ausreichend gute Ergebnisse.

236
Niki

Nikies Antwort löste mein Problem, aber seine Antwort war in Mathematica. Also dachte ich, ich sollte hier seine OpenCV-Anpassung geben. Aber nach der Implementierung konnte ich feststellen, dass OpenCV-Code viel größer ist als Nikies Mathematica-Code. Außerdem konnte ich in OpenCV keine Interpolationsmethode von nikie finden (obwohl dies mit scipy möglich ist, werde ich es zu gegebener Zeit mitteilen.)

1. Bildvorverarbeitung (Schließvorgang)

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)

Ergebnis:

Result of closing

2. Sudoku-Quadrat finden und Maskenbild erstellen

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)

Ergebnis:

enter image description here

3. Vertikale Linien finden

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()

Ergebnis:

enter image description here

4. Horizontale Linien finden

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()

Ergebnis:

enter image description here

Natürlich ist dieser nicht so gut.

5. Rasterpunkte finden

res = cv2.bitwise_and(closex,closey)

Ergebnis:

enter image description here

6. Behebung der Mängel

Hier interpoliert nikie, über die ich nicht viel weiß. Und ich konnte keine entsprechende Funktion für dieses OpenCV finden. (Vielleicht ist es dort, ich weiß es nicht).

Schauen Sie sich diesen SOF an, der erklärt, wie dies mit SciPy gemacht wird, den ich nicht verwenden möchte: Bildtransformation in OpenCV

Also nahm ich hier 4 Ecken von jedem Unterquadrat und wendete Warp-Perspektive auf jedes an.

Dazu finden wir zuerst die Zentroide.

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))

Die resultierenden Zentroide werden jedoch nicht sortiert. Schauen Sie sich das folgende Bild an, um die Bestellung zu sehen:

enter image description here

Also sortieren wir sie von links nach rechts, von oben nach unten.

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))

Nun siehe unten ihre Reihenfolge:

enter image description here

Zuletzt wenden wir die Transformation an und erstellen ein neues Bild der Größe 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()

Ergebnis:

enter image description here

Das Ergebnis ist fast das gleiche wie bei nikie's, aber die Codelänge ist groß. Möglicherweise gibt es bessere Methoden, aber bis dahin funktioniert dies in Ordnung.

Grüße ARCHE.

198
Abid Rahman K

Sie könnten versuchen, eine Art gitterbasierte Modellierung Ihrer willkürlichen Verzerrung zu verwenden. Und da das Sudoku bereits ein Raster ist, sollte das nicht zu schwer sein.

Sie könnten also versuchen, die Grenzen jeder 3x3-Unterregion zu erkennen und dann jede Region einzeln zu verzerren. Wenn die Erkennung erfolgreich ist, erhalten Sie eine bessere Annäherung.

5
sietschie

Ich möchte hinzufügen, dass die obige Methode nur funktioniert, wenn das Sudoku-Board gerade steht, da sonst der Test des Verhältnisses Höhe/Breite (oder umgekehrt) höchstwahrscheinlich fehlschlägt und Sie keine Kanten des Sudoku erkennen können. (Ich möchte auch hinzufügen, dass Sobel-Operationen (dx und dy) weiterhin funktionieren, wenn Linien, die nicht senkrecht zu den Bildrändern sind, Kanten in Bezug auf beide Achsen aufweisen.)

Um gerade Linien erkennen zu können, sollten Sie Kontur- oder pixelweise Analysen durchführen, z. B. contourArea/boundingRectArea, Punkte oben links und unten rechts ...

Bearbeiten: Ich habe es geschafft zu überprüfen, ob eine Reihe von Konturen eine Linie bilden oder nicht, indem ich eine lineare Regression angewendet und den Fehler überprüft habe. Die lineare Regression wird jedoch schlecht ausgeführt, wenn die Steigung der Linie zu groß ist (d. H.> 1000) oder sehr nahe bei 0 liegt. Daher ist es logisch, den obigen Ratio-Test (in der am häufigsten gestellten Antwort) vor der linearen Regression anzuwenden, und hat bei mir funktioniert.

1
Ali Eren Çelik

Um nicht erkannte Ecken zu entfernen, habe ich eine Gammakorrektur mit einem Gammawert von 0,8 durchgeführt.

Before gamma correction

Der rote Kreis wird gezeichnet, um die fehlende Ecke anzuzeigen.

After gamma correction

Der Code lautet:

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)

Dies ist zusätzlich zu Abid Rahmans Antwort, wenn einige Eckpunkte fehlen.

1
Vardan Agarwal