Como remover defeitos de convexidade em um quadrado de Sudoku?

Eu estava fazendo um projeto divertido: resolvendo um Sudoku a partir de uma imagem de entrada usando o OpenCV (como no Google Goggles etc.). E concluí a tarefa, mas no final encontrei um pequeno problema para o qual vim aqui.

Fiz a programação usando a API Python do OpenCV 2.3.1.

Abaixo está o que eu fiz:

1. Leia a imagem
2. Encontre os contornos
3. Selecione aquele com a área máxima (e também um pouco equivalente ao quadrado).

4. Encontre os pontos de canto.

   por exemplo, dado abaixo:

   

   ( Observe aqui que a linha verde coincide corretamente com o verdadeiro limite do Sudoku, para que o Sudoku possa ser corretamente distorcido . Verifique a próxima imagem)

5. distorça a imagem para um quadrado perfeito

   por exemplo, imagem:

   

6. Executar OCR (pelo qual usei o método que forneci no OCR de reconhecimento de dígito simples no OpenCV-Python )

E o método funcionou bem.

Problema:

Confira esta imagem.

A execução do passo 4 nesta imagem fornece o resultado abaixo:

A linha vermelha desenhada é o contorno original, que é o verdadeiro contorno do limite do sudoku.

A linha verde desenhada é um contorno aproximado, que será o contorno da imagem distorcida.

O que, é claro, existe diferença entre a linha verde e a linha vermelha na borda superior do sudoku. Portanto, enquanto estou empenado, não estou conseguindo o limite original do Sudoku.

Minha pergunta :

Como posso distorcer a imagem no limite correto do Sudoku, ou seja, a linha vermelha OU como posso remover a diferença entre a linha vermelha e a linha verde? Existe algum método para isso no OpenCV?

Eu tenho uma solução que funciona, mas você terá que traduzi-la para o OpenCV. Está escrito no Mathematica.

O primeiro passo é ajustar o brilho da imagem, dividindo cada pixel com o resultado de uma operação de fechamento:

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

O próximo passo é encontrar a área de sudoku, para que eu possa ignorar (mascarar) o fundo. Para isso, uso a análise de componentes conectados e seleciono o componente que possui a maior área convexa:

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

Ao preencher esta imagem, recebo uma máscara para a grade do sudoku:

mask = FillingTransform[largestComponent]

Agora, posso usar um filtro derivativo de segunda ordem para encontrar as linhas verticais e horizontais em duas imagens 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 a análise de componentes conectados novamente para extrair as linhas de grade dessas imagens. As linhas de grade são muito maiores que os dígitos, portanto, posso usar o comprimento do cursor para selecionar apenas os componentes conectados às linhas de grade. Classificando-os por posição, recebo imagens de máscara 2x10 para cada uma das linhas de grade verticais / horizontais da imagem:

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

Em seguida, pego cada par de linhas de grade verticais / horizontais, as dilato, calculo a interseção pixel por pixel e calculo o centro do resultado. Estes pontos são as interseções da linha de grade:

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

O último passo é definir duas funções de interpolação para mapeamento X / Y através desses pontos e transformar a imagem usando estas funções:

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 as operações são funções básicas de processamento de imagem, portanto, isso também deve ser possível no OpenCV. A transformação de imagem baseada em splines pode ser mais difícil, mas não acho que você realmente precise. Provavelmente, o uso da transformação de perspectiva que você usa agora em cada célula individual dará bons resultados o suficiente.

A resposta de Nikie resolveu meu problema, mas sua resposta estava no Mathematica. Então, pensei em dar sua adaptação ao OpenCV aqui. Mas, após a implementação, pude ver que o código OpenCV é muito maior que o código mathematica da nikie. E também, não consegui encontrar o método de interpolação feito pelo nikie no OpenCV (embora possa ser feito usando o scipy, vou dizer quando chegar a hora).

1. Pré-processamento de imagem (operação de fechamento)

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. Localizando o Sudoku Square e criando a imagem da 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 linhas verticais

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. Localizando linhas horizontais

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:

Claro, este não é tão bom.

5. Encontrar pontos de grade

res = cv2.bitwise_and(closex,closey)

Resultado:

6. Corrigindo os defeitos

Aqui, o nikie faz algum tipo de interpolação, sobre a qual não tenho muito conhecimento. E eu não consegui encontrar nenhuma função correspondente para este OpenCV. (pode estar lá, eu não sei).

Confira este SOF, que explica como fazer isso usando o SciPy, que eu não quero usar: Transformação de imagem no OpenCV

Então, aqui eu peguei 4 cantos de cada sub-quadrado e apliquei a Perspectiva de distorção a cada um.

Para isso, primeiro encontramos os centróides.

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

Mas os centróides resultantes não serão classificados. Confira abaixo a imagem para ver sua ordem:

Então, nós as classificamos da esquerda para a direita, de cima para baixo.

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

Agora veja abaixo a ordem deles:

Por fim, aplicamos a transformação e criamos uma nova imagem de tamanho 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:

O resultado é quase o mesmo que o da nikie, mas o tamanho do código é grande. Pode ser que métodos melhores estejam disponíveis por aí, mas até então, isso funcionará bem.

Atenciosamente ARK.

Você pode tentar usar algum tipo de modelagem baseada em grade de sua distorção arbitrária. E como o sudoku já é uma grade, isso não deve ser muito difícil.

Portanto, você pode tentar detectar os limites de cada sub-região 3x3 e distorcer cada região individualmente. Se a detecção for bem-sucedida, você obterá uma melhor aproximação.

Quero acrescentar que o método acima funciona somente quando a placa do sudoku permanece reta, caso contrário, o teste de relação altura / largura (ou vice-versa) provavelmente falhará e você não poderá detectar as bordas do sudoku. (Também quero acrescentar que, se as linhas que não são perpendiculares às bordas da imagem, as operações sobel (dx e dy) continuarão funcionando, pois as linhas ainda terão arestas em relação aos dois eixos.

Para poder detectar linhas retas, você deve trabalhar na análise de contorno ou pixel, como contourArea / boundingRectArea, pontos superior esquerdo e inferior direito ...

Edit: Consegui verificar se um conjunto de contornos forma uma linha ou não, aplicando regressão linear e verificando o erro. No entanto, a regressão linear teve um desempenho ruim quando a inclinação da linha é muito grande (ou seja,> 1000) ou muito próxima de 0. Portanto, a aplicação do teste de razão acima (na resposta mais votada) antes da regressão linear é lógica e funcionou para mim.

Para remover cantos não detectados, apliquei a correção gama com um valor gama de 0,8.

O círculo vermelho é desenhado para mostrar o canto que falta.

O código é:

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)

Isso é um complemento à resposta de Abid Rahman, se faltam alguns pontos de canto.

Eu pensei que este era um ótimo post e uma ótima solução do ARK; muito bem definido e explicado.

Eu estava trabalhando em um problema semelhante e construí a coisa toda. Houve algumas mudanças (ou seja, intervalo x para intervalo, argumentos em cv2.findContours), mas isso deve funcionar imediatamente (Python 3.5, Anaconda).

Esta é uma compilação dos elementos acima, com parte do código ausente adicionado (ou seja, rotulagem de pontos).

'''

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