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

opencv computer-vision

Question

Estaba haciendo un proyecto divertido: resolviendo un Sudoku a partir de una imagen de entrada usando OpenCV (como en Google goggles, etc.). Y he completado la tarea, pero al final encontré un pequeño problema por el que vine aquí.

Hice la programación usando Python API de OpenCV 2.3.1.

Debajo está lo que hice:

1. Lee la imagen
2. Encuentra los contornos
3. Seleccione el que tiene el área máxima, (y también algo equivalente al cuadrado).

4. Encuentra los puntos de esquina.

   por ejemplo, a continuación:

   ( Observe que la línea verde coincide correctamente con el límite verdadero del Sudoku, por lo que el Sudoku puede deformarse correctamente . Verifique la siguiente imagen)

5. deformar la imagen a un cuadrado perfecto

   por ejemplo, imagen:

6. Realizar OCR (para lo cual utilicé el método que he dado en reconocimiento de dígitos simples OCR en OpenCV-Python )

Y el método funcionó bien.

Problema:

Mira esta imagen

Realizar el paso 4 en esta imagen da el resultado a continuación:

La línea roja dibujada es el contorno original que es el verdadero contorno del límite del sudoku.

La línea verde dibujada es el contorno aproximado que será el contorno de la imagen deformada.

Lo cual, por supuesto, hay una diferencia entre la línea verde y la línea roja en el borde superior del sudoku. Por lo tanto, al deformarme, no obtengo el límite original del Sudoku.

Mi pregunta :

¿Cómo puedo deformar la imagen en el límite correcto del Sudoku, es decir, la línea roja O cómo puedo eliminar la diferencia entre la línea roja y la línea verde? ¿Hay algún método para esto en OpenCV?

Answer 1

La respuesta de Nikie resolvió mi problema, pero su respuesta fue en Mathematica. Así que pensé que debería dar su adaptación OpenCV aquí. Pero después de la implementación pude ver que el código OpenCV es mucho más grande que el código matemático de nikie. Y también, no pude encontrar el método de interpolación hecho por Nikki en OpenCV (aunque se puede hacer usando scipy, lo contaré 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 el cuadrado Sudoku y crear la imagen de la 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. Corregir 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é allí, no sé).

Mira esta SOF que explica cómo hacer esto usando SciPy, que no quiero usar: transformación de imágenes en OpenCV

Entonces, aquí tomé 4 esquinas de cada subcuadro y apliqué Perspectiva de distorsión a cada una.

Para eso, primero encontramos los centroides.

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 serán ordenados. Mira la imagen de abajo para ver su orden:

Así que los clasificamos 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 mira debajo de 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 Nikki, pero la longitud del código es grande. Puede ser, mejores métodos están disponibles, pero hasta entonces, esto funciona bien.

Saludos ARK.

Answer 2

Podrías tratar de usar algún tipo de modelado basado en grillas de tu deformación arbitraria. Y como el sudoku ya es una grilla, no debería ser demasiado difícil.

De modo que podría tratar de detectar los límites de cada subregión 3x3 y luego urdir cada región individualmente. Si la detección tiene éxito, te daría una mejor aproximación.

Answer 3

Tengo una solución que funciona, pero tendrás que traducirla a OpenCV tú mismo. Está escrito en Mathematica.

El primer paso es ajustar el brillo en la imagen, dividiendo cada píxel con el resultado de una operación de cierre:

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

El siguiente paso es encontrar el área de sudoku, por lo que puedo ignorar (enmascarar) el fondo. Para eso, uso análisis de componentes conectados y selecciono el componente que tiene el área convexa más grande:

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

Al completar esta imagen, obtengo una máscara para la cuadrícula de sudoku:

mask = FillingTransform[largestComponent]

Ahora, puedo usar un filtro derivado de segundo orden para encontrar las líneas verticales y horizontales en dos imágenes separadas:

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

Uso nuevamente el análisis de componentes conectados para extraer las líneas de cuadrícula de estas imágenes. Las líneas de la cuadrícula son mucho más largas que los dígitos, por lo que puedo usar la longitud de la pinza para seleccionar solo los componentes conectados a las líneas de la cuadrícula. Al ordenarlos por posición, obtengo 2x10 imágenes de máscara para cada una de las líneas verticales / horizontales de la cuadrícula en la imagen:

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

A continuación, tomo cada par de líneas de cuadrícula verticales / horizontales, las dilato, calculo la intersección píxel por píxel y calculo el centro del resultado. Estos puntos son las intersecciones de la línea de cuadrícula:

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

El último paso es definir dos funciones de interpolación para el mapeo X / Y a través de estos puntos, y transformar la imagen usando estas funciones:

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]

Todas las operaciones son funciones básicas de procesamiento de imágenes, por lo que esto también debería ser posible en OpenCV. La transformación de imágenes basada en splines puede ser más difícil, pero no creo que realmente lo necesite. Probablemente usar la transformación de perspectiva que usa ahora en cada celda individual dará buenos resultados.