Cómo eliminar defectos de convexidad en un cuadrado de Sudoku?

La respuesta de Nikie resolvió mi problema, pero su respuesta estaba en Mathematica. Así que pensé que debería dar su adaptación OpenCV aquí. Pero después de implementar pude ver que el código OpenCV es mucho más grande que el código de Mathematica de Nikie. Y también, no pude encontrar el método de interpolación hecho por nikie en OpenCV (aunque se puede hacer usando scipy, lo diré cuando llegue el momento.)

1. Preprocesamiento de imagen (operación de cierre)

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)

Resultado :

2. Encontrar un Cuadrado de Sudoku y Crear una Imagen de Máscara

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)

Resultado:

3. Encontrar líneas 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()

Resultado:

4. Encontrar líneas 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()

Resultado:

Por supuesto, este no es tan bueno.

5. Encontrar Puntos de Cuadrícula

res = cv2.bitwise_and(closex,closey)

Resultado:

6. Correcto los defectos

Aquí, Nikie hace algún tipo de interpolación, sobre la cual no tengo mucho conocimiento. Y no pude encontrar ninguna función correspondiente para este OpenCV. (puede ser que esté ahí, no lo sé).

Echa un vistazo a este SOF que explica cómo hacer esto usando SciPy, que no quiero usar: Transformación de imagen en OpenCV

Entonces, aquí tomé 4 esquinas de cada sub-cuadrado y apliqué perspectiva de urdimbre a cada uno.

Para eso, primero encontramos la centroids.

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

Pero los centroides resultantes no se ordenarán. Echa un vistazo a la imagen de abajo para ver su orden:

Así que los ordenamos de izquierda a derecha, de arriba a abajo.

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

Ahora ver a continuación su orden:

Finalmente aplicamos la transformación y creamos una nueva imagen de tamaño 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()

Resultado:

El resultado es casi el mismo que el de nikie, pero la longitud del código es grande. Puede ser, mejores métodos son disponible por ahí, pero hasta entonces, esto funciona bien.

Saludos ARK.

Podría intentar usar algún tipo de modelado basado en cuadrícula de su deformación arbitraria. Y como el sudoku ya es una cuadrícula, no debería ser demasiado difícil.

Así que podrías intentar detectar los límites de cada subregión 3x3 y luego deformar cada región individualmente. Si la detección tiene éxito le daría una mejor aproximación.

Quiero agregar que el método anterior solo funciona cuando el tablero de sudoku está recto, de lo contrario, la prueba de relación altura/ancho (o viceversa) probablemente fallará y no podrá detectar los bordes del sudoku. (También quiero agregar que si las líneas que no son perpendiculares a los bordes de la imagen, las operaciones sobel (dx y dy) seguirán funcionando ya que las líneas seguirán teniendo bordes con respecto a ambos ejes.)

Para poder detectar líneas rectas se debe trabajar en el análisis de contorno o píxel tales como contourArea/boundingRectArea, arriba a la izquierda y abajo a la derecha...

Editar: Logré comprobar si un conjunto de contornos forman una línea o no aplicando regresión lineal y comprobando el error. Sin embargo, la regresión lineal se realiza mal cuando la pendiente de la línea es demasiado grande (es decir, >1000) o está muy cerca de 0. Por lo tanto, aplicar la prueba de relación anterior (en la respuesta más votada) antes de la regresión lineal es lógico y funcionó para mí.