¿Cómo eliminar los defectos de convexidad en una plaza de Sudoku?

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

Hice la progtwigción utilizando la API de Python de OpenCV 2.3.1.

A continuación se muestra lo que hice:

  1. Lee la imagen
  2. Encontrar los contornos
  3. Seleccione el que tenga el área máxima (y también algo equivalente al cuadrado).
  4. Encuentra los puntos de la esquina.

    por ejemplo, a continuación:

      introduzca la descripción de la imagen aquí

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

    • deformar la imagen a un cuadrado perfecto

      por ejemplo, imagen:

      introduzca la descripción de la imagen aquí

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

    Y el método funcionó bien.

    Problema:

    Echa un vistazo a esta imagen.

    Al realizar el paso 4 en esta imagen se obtiene el siguiente resultado:

    introduzca la descripción de la imagen aquí

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

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

    Por supuesto, hay una diferencia entre la línea verde y la línea roja en el borde superior del sudoku. Entonces, mientras combando, no estoy obteniendo 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?

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

    El primer paso es ajustar el brillo de 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]] 

    introduzca la descripción de la imagen aquí

    El siguiente paso es encontrar el área de sudoku, así que puedo ignorar (enmascarar) el fondo. Para eso, uso el 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]]] 

    introduzca la descripción de la imagen aquí

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

     mask = FillingTransform[largestComponent] 

    introduzca la descripción de la imagen aquí

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

    introduzca la descripción de la imagen aquí

    Utilizo nuevamente el análisis de componentes conectados para extraer las líneas de la cuadrícula de estas imágenes. Las líneas de cuadrícula son mucho más largas que los dígitos, por lo que puedo usar la longitud del calibrador para seleccionar solo los componentes conectados a las líneas de cuadrícula. Clasificándolos por posición, obtengo 2×10 imágenes de máscara para cada una de las líneas verticales / horizontales de 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]]; 

    introduzca la descripción de la imagen aquí

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

    introduzca la descripción de la imagen aquí

    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] 

    introduzca la descripción de la imagen aquí

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

    La respuesta de Nikie resolvió mi problema, pero su respuesta fue en Mathematica. Así que pensé que debería dar su adaptación a 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. Además, no pude encontrar el método de interpolación realizado 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:

    Resultado de cierre

    2. Encontrar la Plaza 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:

    introduzca la descripción de la imagen aquí

    3. Encontrando 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:

    introduzca la descripción de la imagen aquí

    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:

    introduzca la descripción de la imagen aquí

    Por supuesto, este no es tan bueno.

    5. Encontrar puntos de cuadrícula

     res = cv2.bitwise_and(closex,closey) 

    Resultado:

    introduzca la descripción de la imagen aquí

    6. Corrigiendo 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 hacerlo usando SciPy, que no quiero usar: Transformación de imagen en OpenCV

    Entonces, aquí tomé 4 esquinas de cada sub-cuadrado y apliqué la perspectiva de deformació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. Echa un vistazo a la imagen de abajo para ver su orden:

    introduzca la descripción de la imagen aquí

    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 vea abajo su orden:

    introduzca la descripción de la imagen aquí

    Finalmente aplicamos la transformación y creamos una nueva imagen de tamaño 450×450.

     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:

    introduzca la descripción de la imagen aquí

    El resultado es casi el mismo que el de nikie, pero la longitud del código es grande. Puede haber mejores métodos disponibles, pero hasta entonces, esto funciona bien.

    Saludos ARCA.

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

    Entonces, podría intentar detectar los límites de cada subregión 3×3 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á derecho, de lo contrario, la prueba de la relación altura / anchura (o viceversa) probablemente fallará y no podrá detectar los bordes del sudoku. (También quiero agregar que si las líneas no son perpendiculares a los bordes de la imagen, las operaciones sobel (dx y dy) todavía funcionarán, ya que las líneas seguirán teniendo bordes con respecto a ambos ejes).

    Para poder detectar líneas rectas, debe trabajar en el análisis de contorno o píxel, como contourArea / boundingRectArea, puntos superior izquierda e inferior derecha …

    Edición: logré comprobar si un conjunto de contornos forman una línea o no aplicando una regresión lineal y verificando el error. Sin embargo, la regresión lineal se realizó de manera deficiente cuando la pendiente de la línea es demasiado grande (es decir,> 1000) o está muy cerca de 0. Por lo tanto, la aplicación de la prueba de relación anterior (en la mayoría de las respuestas con votos superiores) antes de la regresión lineal es lógica y me funcionó.

    Para eliminar las esquinas no detectadas, apliqué la corrección gamma con un valor gamma de 0,8.

    Antes de la corrección gamma

    El círculo rojo se dibuja para mostrar la esquina que falta.

    Después de la corrección de gamma

    El código es:

     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) 

    Esto se sum a la respuesta de Abid Rahman si faltan algunos puntos de esquina.