Inteligência Artificial
Reconhecimento de Padrões
Você está em: MarMSX >> Cursos >> AI
Os humanos são os melhores reconhecedores de padrões existentes na natureza, motivo que os tornam objetos de estudo de diversos pesquisadores. No espaço de 35 anos, os livros [1] e [2] definem que os humanos podem ser igualados ou superados pelas máquinas em tarefas específicas, como por exemplo, reconhecimento de imagens e sons, mas não conseguem ser superados em versatilidade.
A maioria das pesquisas foca em imitar a maneira humana de reconhecer padrões, onde duas principais abordagens são utilizadas: a primeira busca estudar e modelar a inteligência e o comportamento humano, enquanto que a segunda visa construir uma máquina que seja capaz de aprender, assim como os humanos fazem.
Um humano recém nascido reconhece poucas coisas, mas à medida que é exposto a novos padrões, passa a reconhecer também novas coisas. Mesmo na fase adulta, o ser humano continua a aprender novos padrões. Seria decepcionante se os humanos não fossem capazes de reconhecer um rosto, após tê-lo visto apenas uma ou duas vezes.
Vimos nos dois capítulos anteriores as vantagens de se criar uma máquina capaz de aprender, pois soluções baseadas na compreensão do funcionamento das coisas são difíceis de se modelar, dependem de especialistas, além de serem muito específicas. Por exemplo, um sistema especialista sobre animais só contém conhecimentos sobre animais, assim como a heurística do jogo da velha só serve para esse tipo de jogo.
O perceptron criado no capítulo de aprendizado supervisionado tem a capacidade de aprender sobre dados de qualquer tema! Podemos facilmente substituir os dados da flor íris por medidas de crânio de lontras e minks, ou até mesmo informações sobre o comportamento de clientes de uma empresa, sem ter que alterar uma linha sequer da máquina de aprendizado. Nesse caso, não há a necessidade de conhecimentos específicos sobre uma determinada área, mas apenas de dados sobre o tema a ser aprendido.
Nesse capítulo vamos construir uma máquina para reconhecer imagens simples, como padrões de caracteres. É uma máquina genérica, capaz de aprender e reconhecer qualquer tipo de padrão.
Texto adapatado de [1]
Reconhecimento de Imagens - Ajuste ao Gabarito
Uma imagem é uma matriz numérica que possui uma largura L e altura A. Cada ponto da matriz pode ser representado por uma cor - imagem colorida, por um nível de cinza - imagem em tons de cinza, ou até mesmo pelas cores branca ou preta - imagem monocromática.
A proposta dessa seção é construir uma máquina para reconhecer caracteres. Para isso, vamos utilizar imagens monocromáticas com a forma das letras, assim como é feito na tabela ASCII das screen 0 e 1 do MSX.
O programa deverá ter o "gabarito" das letras a serem reconhecidas, ou seja, ter armazenado o formato esperado para cada letra. Um bom exemplo desse "banco" de informações de caracteres é a própria tabela de caracteres da screen 0, armazenada no endereço de memória de vídeo &H800 (ou 2048). Assim, o usuário informa o desenho da letra e o programa verifica o grau de similaridade, ou seja, o quão parecido seu desenho da letra é com a letra armazenada no programa.
Como reconhecer caracteres?
Uma das formas é o usuário fornecer o formato gráfico de 8x8 pixels do caractere, e então o programa compara ponto a ponto a imagem do usuário U(i,j) com o a imagem do gabarito G(i,j). Se a imagem fornecida pelo usuário for igual à do gabarito, ambas as imagens terão os pixels acesos exatamente nos mesmos lugares. Dessa forma, contamos quantos pixels acesos estão nos mesmos lugares em ambas as imagens.
Uma maneira de contar os pixels coincidentes, quando representamos o pixel aceso do caractere pelo valor 1 e o pixel apagado como 0, é feita da seguinte forma [1]:
10 NC=0
20 FOR I=1 TO 8
30 FOR J=1 TO 8
40 NC = NC + U(I,J)*G(I,J);
50 NEXT J,I
A medida de similaridade deve levar em consideração a quantidade de pixels acesos em cada imagem. Caso contrário, teríamos sérios problemas na obtenção da medida de similaridade. Por exemplo, uma figura do gabarito que tivesse apenas um pixel aceso teria o mesmo grau de similaridade com qualquer figura que coincidisse com seu pixel aceso.
Na avaliação feita na figura anterior, a letra "A" é tão parecida com o ponto do gabarito quanto o próprio ponto.
Então, a medida de semelhança fica [1]:
(NUMERO DE UNS COINCIDENTES)2
SEMELHANCA = --------------------------------------------------
(NUMERO DE UNS USUARIO) * (NUMERO DE UNS GABARITO)
A avaliação completa em Basic fica:
10 NC=0 : NU=0 : NG=0
20 FOR I=1 TO 8
30 FOR J=1 TO 8
40 NC = NC + U(I,J)*G(I,J);
50 NU = NU + U(I,J)
60 NG = NG + G(I,J)
70 NEXT J,I
80 MS = NV^2 / (NU*NG)
O livro [1] apresenta um pequeno programa para verificar a semelhança de um formato gráfico fornecido pelo usuário e uma letra "A", no qual foi adaptado para o MSX por mim.
10 DIM M(2,8,8)
20 DATA 00001000
30 DATA 00010100
40 DATA 00100010
50 DATA 00100010
60 DATA 00111110
70 DATA 00100010
80 DATA 00100010
90 DATA 00000000
500 DIM A(8,8)
1000 K=1
1010 GOSUB 2000
1020 GOSUB 3000
1030 GOSUB 4000
1040 K=1
1050 GOSUB 5000
1060 GOTO 1030
2000 FOR I=1 TO 8
2010 READ D
2020 FOR J=1 TO 8
2030 M(K,I,9-J)=D-INT(D/10)*10
2040 D=INT(D/10)
2050 NEXT J
2060 NEXT I
2070 RETURN
3000 PRINT"GABARITO ";K;":":PRINT
3010 FOR I=1 TO 8
3020 FOR J=1 TO 8
3030 IF M(K,I,J)=1 THEN PRINT"1"; ELSE PRINT"0";
3040 NEXT J
3050 PRINT
3060 NEXT I
3070 PRINT
3080 RETURN
4000 FOR I=1 TO 8
4010 PRINT "LINHA ";I;
4020 INPUT LN
4030 FOR J=1 TO 8
4040 A(I,9-J)=LN-INT(LN/10)*10
4050 LN=INT(LN/10)
4060 NEXT J
4070 NEXT I
4080 PRINT
4090 FOR I=1 TO 8
4100 FOR J=1 TO 8
4110 IF A(I,J)=1 THEN PRINT"1"; ELSE PRINT"0";
4120 NEXT J : PRINT
4130 NEXT I
4140 PRINT
4150 RETURN
5000 R=0
5010 C=0
5020 B=0
5030 FOR I=1 TO 8
5040 FOR J=1 TO 8
5050 R=R+M(K,I,J)*A(I,J)
5060 C=C+M(K,I,J)
5070 B=B+A(I,J)
5080 NEXT J
5090 NEXT I
5100 PRINT "Similaridade: ";(R*R)/(C*B):PRINT
5110 RETURN
Ao rodar o programa, ele desenha o padrão do "A" contido no gabarito. Então, pede ao usuário que desenhe uma forma linha a linha. Vamos desenhar um "A" parecido:
LINHA 1 ? 00011100
LINHA 2 ? 00100010
LINHA 3 ? 00100010
LINHA 4 ? 00100010
LINHA 5 ? 00111110
LINHA 6 ? 00100010
LINHA 7 ? 00100010
LINHA 8 ? 00000000
Similaridade: .68055555555556
Tente agora desenhar a letra B:
LINHA 1 ? 00111100
LINHA 2 ? 00100010
LINHA 3 ? 00100010
LINHA 4 ? 00111100
LINHA 5 ? 00100010
LINHA 6 ? 00100010
LINHA 7 ? 00111100
LINHA 8 ? 00000000
Similaridade: .253125
Um problema evidente da abordagem de coincidência de pontos é que uma letra "A" desenhada deslocada de um pixel à esquerda ou direita irá retornar um grau de similaridade muito baixo. Experimente o desenho a seguir.
LINHA 1 ? 00010000
LINHA 2 ? 00101000
LINHA 3 ? 01000100
LINHA 4 ? 01000100
LINHA 5 ? 01111100
LINHA 6 ? 01000100
LINHA 7 ? 01000100
LINHA 8 ? 00000000
Similaridade: .0625
O programa anterior possui somente uma letra no gabarito. Entretanto, podemos ter quantas quisermos. Nesse caso, a letra do gabarito que será mais parecida com a fornecida pelo usuário será aquela que possui maior grau de similaridade com esta.
O programa a seguir foi escrito por mim e permite ao usuário desenhar um caractere de forma mais fácil, bem como utiliza a tabela ASCII (33-127) da screen 0 como gabarito.
É possível copiar padrões do gabarito para área de desenho. Para isso, pressione TAB, escolha um caractere da tabela e pressione ENTER.
Após terminar a edição, pressione ENTER para que o MSX encontre o caractere mais parecido com o seu.
Peque o programa "PADRAO.BAS" aqui.
No programa a seguir, o usuário está livre para criar seus símbolos, ensiná-lo ao MSX e depois ver se ele aprendeu.
Desenhe um símbolo qualquer, depois tecle de 1 a 5, para armazenar o símbolo no local de memória correspondente. Escreva um nome para representar o símbolo.
Por fim, desenhe um símbolo igual ou parecido com um dos 5 símbolos da memória do MSX e tecle ENTER para verificar.
Peque o programa "PADRAO2.BAS" aqui.
Uma solução para o problema da forma do caractere
Podemos adicionar gabaritos com variações de cada caractere, aumentando a chance de obtermos sucesso na identificação deles.
Veja o exemplo de gabaritos (ou templates) para a letra "A":
Entretanto, quanto mais gabaritos adicionarmos, mais lento ficará o processo de identificação de caracteres.
Referências
1. Inteligência Artificial para Leigos, J. P. Mueller e L. Massaron. Ed. Alta Books, 2019.
2. Inteligência Artificial em Basic, Mike James. Ed. Campus, 1985.