Trabalho final do curso Realidade Aumentada e Colaborativa de 2003.2
Feito por Frederico Rodrigues Abraham e Otávio Braga
Sob a orientação dos professores Marcelo Gattass, Paulo Cezar Carvalho, Flávio Szenberg e Alberto Raposo
PUC-Rio, Dezembro de 2003
Introdução Descrição do sistema Técnicas e algoritmos utilizados Conclusões Downloads e instruções de uso
O objetivo do nosso trabalho foi desenvolver um sistema de jogo de xadrez em que:
Neste documento será descrito o projeto, a arquitetura do sistema e as técnicas utilizadas. O resultados serão mostrados e a implementação disponibilizada sobre a forma de código fonte e binários para Linux. Uma breve descrição dos módulos criados e e o modo de uso do programa serão feitos.
O nosso sistema possui três componentes principais: o reconhecedor de jogadas, o sistema de realidade aumentada e o gerenciador de jogos.
O reconhecedor de jogadas é o componente que deve, a partir de um stream de uma câmera digital, extrair qual foi a jogada feita pelo usuário. Para isto, deve ser utilizada alguma técnica de reconhecimento do tabuleiro e percepção da mudança do estado de uma (ou mais) casas.
Se uma casa A que em um certo tempo 't' possuía uma peça e no tempo 't+1' deixa de possuir e uma casa B que em 't' não possuia peça alguma e em 't+1' passa a possuir, muito provavelmente o jogador moveu uma peça da casa A para a casa B.
É a partir deste princípio que o nosso reconhecedor de jogadas funciona. Algumas jogadas especiais como roque e promoção de peões devem ser tratadas à parte (não tendo sido tratadas neste primeiro protótipo). Para reduzir problemas com oclusão de casas do tabuleiro por peças, o tabuleiro deve ser filmado de cima (o que minimiza porém não elimina completamente esse problema, conforme será descrito a seguir).
O sistema de realidade aumentada deve ser capaz de, a partir do estado de jogo atual, posicionar as peças virtuais do adversário sobre a imagem do tabuleiro real. A câmera que produz esta imagem não deve ter restrição quanto à sua posição, sendo, se possível, apenas necessária uma imagem com uma possível interpretação do tabuleiro por parte do usuário. É desejado que isto aconteça em tempo real (atualização a cada quadro), porém isto não foi atingido neste nosso primeiro protótipo.
O gerenciador de jogos deve manter o estado de jogo atual, recebendo as jogadas de cada adversário e indicando se o jogo acabou, seja por xeque-mate ou por empate. Em eventuais problemas de desconexão da rede por parte de um dos usuários, o jogo pode ser continuado sem maiores problemas. A figura do gerenciador de jogos também possibilita servidores de jogos, com múltiplos jogos ocorrendo ao mesmo tempo e com a possibilidade de campeonatos, espectadores, aprendizado online, chat, etc. Neste primeiro protótipo foi apenas implementado um jogo ativo por gerenciador.
Apesar da existência de um gerenciador de jogos, cada jogador mantém o estado atual do jogo, validando as jogadas feitas antes de elas serem enviadas ao gerenciador de jogos e por consequência ao adversário.
Nesta seção serão descritas as técnicas e algoritmos utilizados para os três componentes do projeto.
Para o reconhecimento das jogadas, é necessário reconhecer o tabuleiro de jogo e perceber a variação do estado de uma ou mais casas (com ou sem peça).
Este algoritmo serve para a detecção do tabuleiro quadriculado no qual o jogo de xadrez é jogado, servindo também para reconhecimento de jogadas de outros jogos baseados no mesmo tabuleiro, como o jogo de damas.
Para a identificação do tabuleiro, foi pensado que as suas linhas seriam bons delimitadores das casas.
Com isto, foi implementado um algoritmo que utiliza a transformada de Hough para extrair as linhas do tabuleiro.
Para a extração de linhas ser possível, ela deve ser feita na imagem resultado de um algoritmo de detecção de arestas. Foram testados os algoritmos de Prewitt, Canny, Sobel e Laplaciano. Foi escolhido o operador de Sobel por ele gerar arestas mais grossas que os outros detectores de arestas. Como queremos as linhas mais fortes do tabuleiro, isto é vantajoso para a extração das nossas linhas.
Primeiro aplica-se o filtro gaussiano na luminância da imagem capturada. Esta imagem serve de entrada para alguns operadores de detecção de arestas.
A partir desta imagem, aplica-se o operador de Sobel, que vai basicamente manter na imagem os pixels onde houveram derivadas maiores que um certo valor mínimo pré-determinado, ou seja, as arestas.
A partir da imagem que contém as arestas, aplica-se a transformada de Hough, a qual irá construir uma matriz com as discretizações no espaço rho x theta (rho é a distância da reta ao canto inferior esquerdo da imagem e theta é o ângulo que a normal a esta reta faz com a horizontal) contendo em cada (rho,theta) o número de pixels atingidos pela reta descrita por estes valores. Os valores de rho e theta que possuirem um número mínimo de pixels atingidos comporão as retas do tabuleiro.
Para delimitarmos corretamente as casas do tabuleiro, precisamos identificar quais retas da imagem são as 9 retas horizontais e 9 retas verticais do modelo.
O primeiro passo é possibilitar que a extração de linhas saiba inferir se a reta sendo extraída é horizontal ou vertical. Como não sabemos a priori qual é a orientação do tabuleiro na imagem, assumimos que precisamos primeiramente agrupar as retas em dois grupos diferentes (que logo serão identificados como horizontais e verticais). Para isto, foi utilizado um clássico algoritmo de classificação/agrupamento chamado K-Means. O objetivo do agrupamento é separar todos os thetas possíveis nos dois grupos.
Primeiramente, é feita uma divisão inicial arbitrária dos possíveis thetas em dois grupos. A cada iteração:
A partir daí, temos dois grupos de retas, e precisamos escolher 9 retas em cada um para interpretar o tabuleiro. Para reduzir o espaço de busca na etapa de interpretação destas retas, realizamos uma eleição entre as várias linhas similares que a transformada de Hough encontra sobre uma mesma linha no tabuleiro. Para tal, bastou identificar as linhas similares e escolher a que continha a maior contagem na transformada de Hough. A detecção de linhas similares se dá pelo cálculo da área do quadrilátero formado entre cada par de retas. Se a área do quadrilátero (que é pequena para retas similares) for menor que um determinado valor mínimo, as retas são consideradas similares e competem para permanecer na lista de retas. Somente a reta com a maior contagem dentre retas similares permanece. Além disso, as retas com mais de 40 graus de distância ao centróide do grupo a que pertencem foram consideradas retas espúrias e foram descartadas para esta busca.
Estes algoritmos se mostrou suficiente para a extração das retas do tabuleiro e sua divisão das retas em dois grupos.
Extração das linhas do tabuleiro.
Após este passo de filtragem do conjunto de retas encontradas, um algoritmo de interpretação força bruta foi implementado. Ele é executado separadamente em cada um dos dois grupos de retas encontradas. Ele basicamente anda na árvore de interpretação completa, descartando interpretações em que retas se cruzam ou que não geram uma sequência de retas na imagem (uma sequência de retas tem a reta 'i' do modelo sempre abaixo ou acima da reta 'i+1' do modelo na imagem, para todo 'i' entre 0 e 7). Quando uma interpretação plausível é encontrada, o algoritmo pára.
Agora temos dois grupos de 9 de retas, onde se garante que retas do mesmo grupo estão ordenadas na imagem (horizontais e verticais) e não que se intersectam. Para determinar qual grupo é de retas horizontais ou de retas verticais, assumiu-se que o jogo seria reconhecido sempre com uma orientação padrão: tabuleiro praticamente alinhado com a horizontal da imagem, com a linha 1 do tabuleiro na parte inferior da imagem (a orientação comum de jogos de xadrez de computador).
Assim, as retas verticais são as retas cujos thetas possuem valor absoluto menor que aproximadamente 20 graus, e as retas horizontais são as retas restantes. Ainda é checado se as retas não estão revertidas, observando se o rho da reta 0 do modelo é menor que o rho da reta 1 do modelo (reta 0 mais próxima do canto esquerdo da imagem).
3.1.2 - Reconhecimento de jogadas
A partir das retas do tabuleiro na imagem, cada pixel recebe um rótulo, identificando a qual casa ele pertence. Isso é feito pela rasterização do quadrilátero formado entre as linhas à esquerda, à direita, abaixo e acima da casa.
Ao mover uma peça de uma casa 'A' para uma casa 'B', o usuário sinaliza que fez uma jogada. O reconhecedor de jogadas então checa toda a imagem por variações nas cores em cada casa. A medida utilizada para esta variação é a distância quadrática no espaço RGB, sendo ela amplificada nas casas brancas quando o usuário utiliza peças brancas e nas casas pretas quando o usuário utiliza peças pretas. A medida utilizada é 10 pontos para cada pixel em uma casa com a mesma cor da peça e 1 ponto para cada pixel em uma casa com cor diferente da cor da peça.
Como cada pixel da imagem tem o identificador da casa a qual ele pertence, é possível contar o número de variações bruscas de cor em cada casa.
Para a detecção da jogada, são testadas as N casas com a maior variação de cor, onde N é o número de peças envolvidas em uma jogada.
No caso do jogo de xadrez, uma jogada comum muda o estado de duas casas, a casa de origem e a casa de destino. Como sabemos o estado atual do jogo, a casa destino é a casa que não possuía peça do jogador. A única jogada que não atende a esta regra é o roque, o qual irá mudar o estado de 4 casas, mas isto é facilmente detectável. A partir disto, é possível inferir qual jogada foi feita.
Os testes feitos foram bem sucedidos, tendo sido jogados alguns jogos completos sem erros na detecção das jogadas (sem uso da promoção de peão nem roque, jogadas não implementadas neste protótipo).
Estado do jogo antes da jogada.
Mapa de diferenças RGB normalizadas (jogada realizada = D2D4).
3.2 - Inserção de peças virtuais na imagem capturada
A inserção de peças virtuais se dá na imagem de uma outra câmera, esta com liberdade de movimento.
Para posicionar as peças corretamente, é necessário calibrar a câmera virtual. Foi utilizado o algoritmo de Tsai bi-dimensional, o qual tem como entrada um conjunto de pontos, sendo informadas as coordenadas de imagem e modelo de cada ponto. Assim ele é capaz de calcular as transformações de câmera (projeção e posicionamento) necessárias para o desenho das peças virtuais.
Uma vez reconhecido o tabuleiro na imagem capturada, teremos a liberdade de passar as coordenadas tanto no modelo quanto na imagem dos até 81 pontos formados pelas interseções das 9 linhas horizontais e 9 linhas verticais do tabuleiro.
Para o reconhecimento do tabuleiro, também nos baseamos na detecção de suas retas. É utilizado o mesmo algoritmo de detecção de linhas, agrupamento em dois grupos e remoção de retas espúrias e repetidas. No entanto, como a câmera tem liberdade de movimento, não podemos assumir nada quanto à orientação do tabuleiro na imagem. Além disso, não é possível contar que conseguiremos extrair todas as retas do tabuleiro, já que possivelmente algumas peças estarão na frente das retas.
A partir das retas extraídas, selecionamos as 4 retas do grupo 1 e 4 retas do grupo 2 com as maiores contagens na fase de extração. Para cada par de retas em cada grupo, consideramos todas as possíveis interpretações destas retas como retas do modelo. Para cada par de retas na imagem e sua interpretação no modelo, é possível calcular uma transformação perspectiva a partir da construção de um sistema linear que tem como dados os 4 pontos de interseção entre as retas e tem como incógnitas os 8 termos variáveis da matriz de transformação (basicamente o mesmo que o algoritmo de Tsai 2d faz, porém não há restrições quanto à transformação representar uma câmera). Esta matriz transforma um ponto (i,j) em coordenadas do modelo (i variando de 0 a WIDTH e j variando de 0 a HEIGHT). em um ponto (i',j') em coordenadas de imagem.
Uma interpretação correta do tabuleiro irá transformar a imagem original numa imagem bem plausível de ser o tabuleiro, assim como uma interpretação ruim transformará a imagem original numa imagem não plausível. Observe as imagens a seguir: a primeira é a imagem capturada, a segunda é a imagem transformada utilizando uma interpretação correta e a terceira é a imagem transformada utilizando uma interpretação incorreta:
Para quantificar a similaridade de uma interpretação com o tabuleiro real, a seguinte métrica foi utilizada: dada a imagem transformada, foi calculada uma pontuação baseada na similaridade da imagem transformada com uma imagem ideal, que seria uma imagem dividida em 8x8 blocos com as cores do tabuleiro de xadrez (com a casa A1 no canto inferior esquerdo). Em um determinado pixel da imagem transformada acontece um acerto se o seu valor em tom de cinza é acima de 127 em casas brancas e abaixo de 127 em casas pretas (assumindo uma escala de tons de cinza que vai de 0 - preto a 255 - branco).
Um acerto na borda do tabuleiro (linhas A e H, colunas 1 e 8) faz com que a interpretação ganhe 2 pontos, já um erro nessas casas faz com que a interpretação perca 2 pontos. Um acerto nas demais casas vale 1 ponto e um erro vale -1 ponto. Eventualmente a transformação levará um ponto no modelo para fora da imagem (na imagem acima representado pela grande porção preta). Estes pontos não recebem nem perdem pontos.
Baseado nisto, a interpretação com maior pontuação tende a ser a melhor maneira de se interpretar o tabuleiro. Este algoritmo se comporta bem quando correm mudanças bruscas na observação do tabuleiro, assim como não obriga que o tabuleiro inteiro esteja visível. O ruído na interpretação causado pela presença de peças é o mesmo para todas as interpretações (a imagem de entrada é a mesma), daí a idéia de se utilizar um algoritmo de busca.
O seu grande problema é a sua complexidade. Dependendo do número de retas escolhidas por grupo, serão necessárias as análises de diversas interpretações possíveis, cada uma delas fazendo acessos à imagem original. Algumas técnicas foram implementadas para acelerar este algoritmo, reduzindo o tempo de cálculo de 2 horas em um Pentium 4 para cerca de 7 segundos.
Isto no entanto não é suficiente para a interpretação do tabuleiro em tempo real. A otimização mais importante que não foi feita neste primeiro protótipo é a diminuição dos cálculos de similaridade repetidos entre interpretações iguais do tabuleiro. Observe a imagem a seguir:
A interpretação que considera que as retas 4 e 1 da imagem correspondem às retas horizontais 5 e 7 do modelo e que as retas 10 e 9 da imagem correspondem às retas verticais 5 e 6 do modelo é uma possível interpretação correta do tabuleiro. A interpretação que considera que as retas 7 e 5 da imagem correspondem às retas horizontais 1 e 2 do modelo e que as retas 11 e 9 da imagem correspondem às retas verticais 4 e 6 do modelo também é uma possível interpretação correta do tabuleiro. As matrizes de transformação calculadas para estas duas interpretações neste exemplo são praticamente as mesmas (diferença relativa de aproximadamente 5%). Uma possível identificação de interpretações iguais do tabuleiro provavelmente reduzirá enormemente o esforço computacional desta busca.
Tabuleiro de jogo virtual.
Peças virtuais sobre o tabuleiro real.
3.3 - Colaboração entre jogadores
Para a parte de colaboração entre os jogadores, foi desenvolvido um protótipo de gerenciador de jogo e foi inserido o suporte à colaboração no programa de reconhecimento de jogadas e desenho das peças virtuais.
Foi utilizada a tecnologia CORBA para a definição das interfaces de comunicação entre os dois módulos. Foi utilizada a ferramenta LuaCorba para a simplificação do uso de CORBA no projeto. Ela permite o uso de chamadas remotas via Lua (uma linguagem de extensão). Assim, o uso de chamadas remotas ficou bem simplificado, praticamente reduzido a um módulo cliente que chama as funções remotas e um módulo servidor que faz a comunicação entre os jogadores.
O gerenciador de jogos define a seguinte interface:
module DChess {
interface ChessManager
{
void Start ();
void End ();
short WhoseTurn ();
string LastMove ();
boolean Move (in string command);
boolean IsOver ();
};
};
Os métodos Start()/End() iniciam e terminam um jogo.
O método WhoseTurn() identifica de quem é a vez. O método LastMove() retorna a última jogada feita. A combinação WhoseTurn+LastMove possibilita a um jogador receber a jogada do adversário (fazendo com que o servidor seja sempre passivo).O método Move(command) envia uma jogada ao servidor, e o método IsOver() checa se o jogo terminou.
O servidor de jogo implementa esta interface em C++. Os clientes a utilizam via Lua.
Assim, é possível realizar um jogo distribuído, seja em uma rede local ou na internet.
Os resultados encontrados para este primeiro protótipo foram satisfatórios, sendo possível uma partida inteira de xadrez jogada com o sistema.
O sistema de reconhecimento de jogadas infelizmente necessita de uma câmera com pouca distorção radial. Distorção radial dificulta bastante a detecção de todas as linhas do tabuleiro (atualmente necessária para a interpretação correta do tabuleiro).
O algoritmo utilizado para a detecção de jogadas pode ser melhorado, pois ainda há problema de oclusão de peças mesmo se o tabuleiro for filmado de cima (devido à projeção perspectiva que ocorre na lente).
O algoritmo de reconhecimento se mostrou robusto, sendo capaz de reconhecer o tabuleiro em situações não triviais (imagem a seguir). Certamente a sua grande limitação é a sua complexidade computacional. Alguns algoritmos podem ajudar a otimizar a busca, viabilizando o seu uso em tempo real.
Além disso, técnicas de acompanhamento das linhas podem ser implementadas, não obrigando este algoritmo a ser executado a todo quadro.
Para uma composição de imagem real e virtual mais correta, o reconhecimento deveria ser feito apenas para selecionar as melhores retas e suas interpretações corretas. A transformação inversa ajudaria apenas a encontrar as linhas que pertencem ao tabuleiro na imagem. Atualmente elas estão sendo sintetizadas a partir da matriz de transformação ótima encontrada, e isto gera ruídos devido a imprecisões numéricas e modelos imperfeitos de câmeras. Isto é possível notar na imagem com o tabuleiro virtual desenhado, onde é bem visível que o tabuleiro desenhado não é perfeitamente alinhado com a imagem do tabuleiro real. As interseções das retas da imagem são mais confiáveis para a calibração da câmera.
Este algoritmo de reconhecimento também pode ser utilizado para o reconhecimento do tabuleiro no reconhecedor de jogadas. Ele seria mais robusto pois a falta de linhas não o atrapalharia na hora de reconhecer o tabuleiro. No entanto, é necessária a tática descrita acima, pois o uso de retas sintetizadas certamente prejudicaria o algoritmo de reconhecimento de jogadas, já que ele se baseia no contraste da imagem de entrada.
A estrutura de distribuição do jogo ficou bem simples, possibilitando sua extensão a esquemas mais elaborados.
A arquitetura modular do sistema ajudou no desenvolvimento do seu protótipo e certamente ajudará no seu amadurecimento.
Eis algumas fotos de tela do sistema:
Jogo em ação.
Algoritmo de interpretação do tabuleiro tolerante à morte do jogador.
5 - Downloads e instruções de uso
Clique aqui para fazer o download dos arquivos do projeto.
A estrutura de diretórios é a seguinte:
O código fonte desenvolvido está dividido nos seguintes módulos:
O código fonte dos executáveis são os arquivos dmanager.cpp (gerenciador de jogos) e rec.cpp (reconhecedor de jogadas e visualizador das peças virtuais).
O código fonte utilitário está dividido nos seguintes módulos:
Foi utilizado o ORB MICO como implementação do padrão CORBA utilizada no projeto.
5.1 - Instruções de uso do gerenciador de jogos
Primeiramente um repositório de interfaces IDL CORBA deve estar ativo. No caso do MICO (e dos binários disponibilizados), execute na máquina onde ficará o gerenciador de jogos:
$ runird localhost
Este é um script que executará o repositório de interfaces na porta 5555. Em seguida, execute o gerenciador de jogos com o comando:
$ runmanager localhost localhost
Este é um script que executará o gerenciador de jogos na porta 4444. Um arquivo chamado chess.ref será gerado. Ele contém as informações necessárias para um cliente se conectar ao servidor de jogos.
Neste primeiro protótipo, este arquivo deve ser acessível pelos clientes do jogo.
5.2 - Instruções de uso do reconhecedor de jogadas e visualizador das peças virtuais
$ rec /dev/video0 /dev/video1 chess.ref -ORBIfaceRepoAddr inet:localhost:5555
Neste comando, estamos utilizando "/dev/video0" como a câmera de reconhecimento de jogadas e "/dev/video1" como a câmera de desenho das peças virtuais. O servidor de jogos é referenciável pelo arquivo "chess.ref" e o repositório de interfaces utilizado está em "localhost" na porta 5555.
Os comandos possíveis são digitáveis quando se clica na janela de visualização.
Os seguintes comandos servem para o reconhecimento do tabuleiro:
Os seguintes comandos servem para o restante do jogo:
Para o teste do adversário do jogador que controla o sistema de reconhecimento, utiliza-se um script de conexão ao servidor de jogos, o qual pode executar os mesmos comandos que o jogador comum executa. Pelo comando pode-se utilizar este ambiente de testes:
$ luaorb -i -ORBIfaceRepoAddr inet:localhost:5555 -f testclient.lua
As funções disponíveis são as seguintes: