Sudoku

Autor: rubens
Data: 08/01/2010

Introdução

O objetivo dessa demonstração é mostrar a utilização de técnicas de processamento de imagens e reconhecimento de padrões para solucionar um quebra-cabeça conhecido como Sudoku, apresentado aqui através da imagem de uma página de jornal. Essa imagem deve ser processada para a extração dos caracteres numéricos que compõem o jogo. Em seguida os caracteres devem ser reconhecidos para que, então, o quebra-cabeça seja resolvido. Para a apresentação final, os caracteres da solução devem ser superpostos à imagem original.

------------------------------------------------------------
*** Exception while evaluating code:
  File "<string>", line 1, in <module>
NameError: name 'imgnb' is not defined

------------------------------------------------------------

Figura 1

Na sequência, apresentamos, passo a passo, a solução proposta para o problema.

Localizando o quebra-cabeça

Para determinar o local onde se encontra o quebra-cabeça, vamos tirar proveito das linhas que o cercam. Para tanto, em primeiro lugar, utilizamos um filtro top-hat para deixar na imagem apenas os componentes conexos com área menor que 10000 pixels, eliminando assim as grandes áreas claras da Fig. 2a. A imagem resultante (Fig. 2b) é submetida a um novo filtro conexo para eliminar os componentes cujo bounding-box tenha ambas as dimensões menores que 200 pixels (estamos trabalhando com imagens 800x600). Finalmente, a imagem é binarizada (Fig. 2d) e será utilizada a seguir para a determinação dos dígitos do sudoku.

Figura 2

Corrigindo a perspectiva

Visando localizar (e reconhecer) os caracteres do sudoku, procedemos, em seguida, a uma tranformação de perspectiva para colocar o plano que contém os caracteres em posição frontal. Utilizaremos para isso a transformada de Hough para determinar os parâmetros das quatro retas que envolvem o quebra-cabeça. Determinadas as retas (Fig. 3a), calculamos as coordenadas dos quatro vértices do quadrado (Fig. 3b). Esses pontos são, então, utilizados para a execução de uma transformação de perspectiva que faz com que o quadrado do jogo seja colocado em uma imagem quadrada, conforme mostra a Fig. 4a.

Nota

Note que o algoritmo aqui apresentado supõe que a página de jornal esteja plana na imagem, o que muitas vezes não ocorre.

Figura 3

Localizando os dígitos do jogo

A imagem normalizado é submetida a um top-hat conexo por bounding-box de forma a restar apenas os caracteres do jogo (Fig. 4b) que são, então, rotulados (Fig. 4c) para a extração de suas características estatísticas.

Figura 4

Reconhecendo os caracteres e resolvendo o jogo

A partir do centróide de cada caracter rotulado determinamos sua posição no jogo. Usando o respectivo bounding-box extraímos a imagem de cada caracter e usamos uma rede neural previamente treinada para efetuar o reconhecimento do dígito.

Dados os caracteres de entrada, um algorimo de busca em profundidade com backtracking resolve o quebra-cabeça.

------------------------------------------------------------
*** Exception while evaluating code:
  File "<string>", line 3, in <module>
  File "<string>", line 13, in __init__
NameError: global name 'DEBUG' is not defined

------------------------------------------------------------

Escrevendo a solução

Para finalizar, escrevemos os dígitos que compõem a solução em uma imagem compatível (Fig. 5a) e realizamos a transformação geométrica inversa (Fig. 5b) para em seguida superpor a solução à imagem de entrada (Fig. 5c), resultando na Fig. 5d.

------------------------------------------------------------
*** Exception while evaluating code:
  File "<string>", line 1, in <module>
NameError: name 'M' is not defined

------------------------------------------------------------

Figura 5