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.

(a) Imagem #5

(b) Imagem solução

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.

(a) Imagem original invertida

(b) Primeiro filtro (imagem invertida para melhor visualização)

(c) Segundo filtro (imagem invertida)

(d) Imagem binarizada

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.

(a) Retas determinadas pela transf. Hough

(b) Pontos para transformação de perspectiva

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.

(a) Imagem normalizada

(b) Imagem depois do filtro conexo

(c) Imagem rotulada

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.

Training the neural network...
Sudoku Solution:

+-----------------------+          +-----------------------+
| . . .   . . .   . . . |          | 6 3 5   9 8 7   4 1 2 |
| 1 . 4   2 5 3   . . . |          | 1 7 4   2 5 3   9 6 8 |
| 9 8 .   . . 1   . . . |          | 9 8 2   6 4 1   7 5 3 |
|                       |
| 5 . .   . 3 .   6 4 9 |          | 5 1 7   8 3 2   6 4 9 |
| . . .   . . .   . . . |   ===>   | 3 2 9   1 6 4   5 8 7 |
| 4 6 8   . 7 .   . . 1 |          | 4 6 8   5 7 9   2 3 1 |
|                       |
| . . .   7 . .   . 2 5 |          | 8 4 3   7 9 6   1 2 5 |
| . . .   4 2 8   3 . 6 |          | 7 5 1   4 2 8   3 9 6 |
| . . .   . . .   8 . . |          | 2 9 6   3 1 5   8 7 4 |
+-----------------------+          +-----------------------+

55 searches in 36.8 ms

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.

(a) Os números da solução

(b) Perspectiva inversa

(c) O quebra-cabeça original

(d) O quebra-cabeça resolvido

Figura 5