Jak usunąć defekty wypukłości w kwadracie Sudoku?

Robiłem zabawny projekt: Rozwiązywanie sudoku z obrazu wejściowego za pomocą OpenCV (jak w goglach Google itp.). I wykonałem zadanie, ale na koniec znalazłem mały problem, po który tu przyjechałem.

Programowałem za pomocą API Python OpenCV 2.3.1.

Poniżej jest to, co zrobiłem:

1. Przeczytaj obraz
2. Znajdź kontury
3. Wybierz ten z maksymalnym obszarem (a także nieco równym kwadratowi).

4. Znajdź punkty narożne.

   np. podane poniżej:

   

   ( Zauważ tutaj, że zielona linia prawidłowo pokrywa się z prawdziwą granicą Sudoku, więc Sudoku można poprawnie wypaczyć . Sprawdź następny obraz)

5. wypacz obraz do idealnego kwadratu

   np. obraz:

   

6. Wykonaj OCR (dla którego użyłem metody, którą podałem w OCR dla Simple Digit Recognition w OpenCV-Python )

Metoda zadziałała dobrze.

Problem:

Sprawdzić ten obraz.

Wykonanie kroku 4 na tym obrazie daje wynik poniżej:

Narysowana czerwona linia jest oryginalnym konturem, który jest prawdziwym konturem granicy sudoku.

Narysowana zielona linia jest przybliżonym konturem, który będzie konturem wypaczonego obrazu.

Która oczywiście jest różnica między zieloną linią a czerwoną linią na górnej krawędzi sudoku. Więc podczas wypaczania nie otrzymuję oryginalnej granicy Sudoku.

Moje pytanie :

Jak mogę wypaczyć obraz na prawidłowej granicy Sudoku, tj. Czerwoną linię LUB jak usunąć różnicę między czerwoną linią a zieloną linią? Czy jest jakaś metoda na to w OpenCV?

Mam rozwiązanie, które działa, ale sam musisz je przetłumaczyć na OpenCV. Jest napisane w Mathematica.

Pierwszym krokiem jest dostosowanie jasności obrazu, dzieląc każdy piksel w wyniku operacji zamykania:

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

Następnym krokiem jest znalezienie obszaru sudoku, dzięki czemu mogę zignorować (maskować) tło. W tym celu korzystam z analizy połączonych komponentów i wybieram komponent, który ma największy obszar wypukły:

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

Wypełniając ten obraz, otrzymuję maskę dla siatki sudoku:

mask = FillingTransform[largestComponent]

Teraz mogę użyć filtra pochodnego drugiego rzędu, aby znaleźć pionowe i poziome linie na dwóch osobnych obrazach:

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

Ponownie używam analizy połączonych komponentów, aby wyodrębnić linie siatki z tych obrazów. Linie siatki są znacznie dłuższe niż cyfry, więc mogę użyć długości suwmiarki, aby wybrać tylko komponenty połączone z liniami siatki. Sortując je według pozycji, otrzymuję 2x10 obrazów maski dla każdej pionowej / poziomej linii siatki na obrazie:

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

Następnie biorę każdą parę pionowych / poziomych linii siatki, rozszerzam je, obliczam przecięcie piksel po pikselu i obliczam środek wyniku. Te punkty to przecięcia linii siatki:

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

Ostatnim krokiem jest zdefiniowanie dwóch funkcji interpolacji dla mapowania X / Y przez te punkty i przekształcenie obrazu za pomocą tych funkcji:

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]

Wszystkie operacje są podstawową funkcją przetwarzania obrazu, więc powinno to być również możliwe w OpenCV. Transformacja obrazu oparta na splajnie może być trudniejsza, ale nie sądzę, żebyś jej naprawdę potrzebował. Prawdopodobnie użycie transformacji perspektywy, której używasz teraz w każdej komórce, da wystarczająco dobre wyniki.

Odpowiedź Nikie rozwiązała mój problem, ale jego odpowiedź brzmiała Mathematica. Pomyślałem więc, że powinienem tutaj dostosować adaptację OpenCV. Ale po wdrożeniu zauważyłem, że kod OpenCV jest znacznie większy niż kod matematyczny Nikie. Poza tym nie mogłem znaleźć metody interpolacji wykonanej przez Nikie w OpenCV (chociaż można to zrobić za pomocą scipy, powiem to, gdy nadejdzie czas).

1. Wstępne przetwarzanie obrazu (operacja zamykania)

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)

Wynik:

2. Znajdowanie placu Sudoku i tworzenie obrazu maski

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)

Wynik:

3. Znajdowanie linii pionowych

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

Wynik:

4. Znajdowanie linii poziomych

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

Wynik:

Oczywiście ten nie jest tak dobry.

5. Znajdowanie punktów siatki

res = cv2.bitwise_and(closex,closey)

Wynik:

6. Korygowanie wad

Tutaj nikie dokonuje interpolacji, o której nie mam dużej wiedzy. I nie mogłem znaleźć żadnej odpowiedniej funkcji dla tego OpenCV. (być może tam jest, nie wiem).

Sprawdź ten SOF, który wyjaśnia, jak to zrobić za pomocą SciPy, którego nie chcę używać: Transformacja obrazu w OpenCV

Więc tutaj wziąłem 4 rogi każdego kwadratu i zastosowałem perspektywę wypaczenia dla każdego.

W tym celu najpierw znajdziemy centroidy.

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

Ale powstałe centroidy nie zostaną posortowane. Sprawdź poniższe zdjęcie, aby zobaczyć ich kolejność:

Więc sortujemy je od lewej do prawej, od góry do dołu.

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

Teraz zobacz poniżej ich kolejność:

Na koniec stosujemy transformację i tworzymy nowy obraz o rozmiarze 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()

Wynik:

Wynik jest prawie taki sam jak w przypadku nikie, ale długość kodu jest duża. Być może dostępne są lepsze metody, ale do tego czasu działa to poprawnie.

Pozdrawiam ARK.

Możesz spróbować użyć pewnego rodzaju modelowania opartego na siatce twojego arbitralnego wypaczania. A ponieważ sudoku już jest siatką, nie powinno to być zbyt trudne.

Możesz więc spróbować wykryć granice każdego podregionu 3x3, a następnie wypaczać każdy region osobno. Jeśli wykrycie się powiedzie, da ci to lepsze przybliżenie.

Chcę dodać, że powyższa metoda działa tylko wtedy, gdy plansza sudoku stoi prosto, w przeciwnym razie test stosunku wysokości do szerokości (lub odwrotnie) najprawdopodobniej się nie powiedzie i nie będzie można wykryć krawędzi sudoku. (Chcę również dodać, że jeśli linie, które nie są prostopadłe do granic obrazu, operacje sobel (dx i dy) będą nadal działać, ponieważ linie będą miały krawędzie względem obu osi.)

Aby móc wykryć linie proste, powinieneś pracować nad analizą konturową lub pikselową, taką jak contourArea / boundingRectArea, lewy górny i prawy dolny punkt ...

Edycja: Udało mi się sprawdzić, czy zestaw konturów tworzy linię, czy nie, stosując regresję liniową i sprawdzając błąd. Jednak regresja liniowa działała słabo, gdy nachylenie linii jest zbyt duże (tj.> 1000) lub jest bardzo bliskie 0. Dlatego zastosowanie powyższego testu proporcji (w najbardziej pozytywnej odpowiedzi) przed regresją liniową jest logiczne i zadziałało dla mnie.

Aby usunąć niezauważone rogi zastosowałem korekcję gamma o wartości gamma 0,8.

Narysowane jest czerwone kółko, aby pokazać brakujący narożnik.

Kod to:

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)

Jest to dodatek do odpowiedzi Abida Rahmana, jeśli brakuje niektórych punktów narożnych.

Myślałem, że to świetny post i świetne rozwiązanie ARK; bardzo dobrze rozplanowane i wyjaśnione.

Pracowałem nad podobnym problemem i zbudowałem całość. Były pewne zmiany (tj. Xrange do zakresu, argumenty w cv2.findContours), ale powinno to działać od razu (Python 3.5, Anaconda).

Jest to kompilacja powyższych elementów z dodanym brakującym kodem (tj. Etykietowaniem punktów).

'''

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