Universidade Federal de Pernambuco
Centro de Informática
 
Reconhecimento de Padrões

  

Aluno: Valnor Calheiros Dória

Introdução

Este trabalho é parte da avaliação da disciplina Linguagens e Máquinas do centro de informática da Universidade Federal de Pernambuco. Seu objetivo é dar uma visão geral do problema de reconhecimento de padrões, com  enfoque  na abordagem lingüística. A página está estruturada nos seguintes tópicos:

O Que é Reconhecimento de Padrões ?

Os problemas de classificação de objetos podem ser divididos em quatro categorias: cognição, reconhecimento, identificação e verificação. Cognição e reconhecimento têm a ver com a extração do significado semântico de um padrão. Entende-se por padrão o objeto observado cujas propriedades medidas constituem suas características. Uma assinatura, uma impressão digital ou uma figura são exemplos de padrões. A diferença entre reconhecimento e cognição reside no fato de que no primeiro caso tem-se um conhecimento a priori das classes de padrão existentes, o que não acontece com a cognição. Como exemplo de um sistema de reconhecimento, pode ser citado o reconhecimento óptico de caracteres (OCR – Optical Character Recognition). Já um exemplo de aplicação que utiliza cognição, seria um sistema  para  decifrar  uma  linguagem  ainda desconhecida, onde haveria inicialmente uma fase de aprendizagem, para a partir de então se decifrar a linguagem.

Por outro lado, identificação e verificação não estão preocupados com o significado semântico de um padrão, apenas tratam da classificação de padrões. Na identificação a tarefa é determinar a que classe um dado padrão pertence e na verificação, que é mais simples, a tarefa é, dada uma determinada classe, afirmar se um padrão pertence ou não àquela classe. Como exemplo de uma  importante aplicação comercial de verificação e identificação pode-se considerar a processamento automático de assinaturas.

Muitas técnicas matemáticas podem ser usadas para resolver problemas de reconhecimento de padrões, mas historicamente tem-se utilizado dois tipos de técnicas:

Esse trabalho vai se limitar a tratar do reconhecimento Lingüístico/Estrutural.

Reconhecimento Lingüístico ou Estrutural

Este tipo de reconhecimento de padrões surgiu com o intuito de representar padrões complexos através de uma estrutura hierárquica, onde a filosofia é que um padrão seja descrito em função de padrões mais simples e esses por sua vez descritos em função de padrões ainda mais simples. Um típico exemplo desta classe de problemas de reconhecimento de padrões é o reconhecimento de figuras ou, de forma mais geral, a análise de cenários. Em problemas deste tipo a figura a ser analisada é em geral bastante complexa e o número de características requeridas é muito grande, o que torna a idéia de descrever um padrão em termos de uma composição hierárquica de sub-padrões bastante atrativa. Como exemplo disso que acabou de ser dito considere o padrão abaixo representado pela figura 1.
 

                                  

                                                                               Figura 1- Cenário.

Ele pode ser perfeitamente descrito em termos de uma estrutura hierárquica como uma árvore, como mostra a figura 2.

                           

                                               Figura 2 – Representação da Figura 1 através de uma árvore.

Analisando a estrutura da figura 2 fica clara a analogia feita por esta abordagem entre a estrutura de padrões e a sintaxe das linguagens, senão vejamos. Aqui um padrão é construído a partir de padrões mais simples através de várias formas de composição, exatamente como as frases são compostas através da concatenação de padrões mais simples, as palavras, e estas por sua vez compostas novamente pela concatenação de padrões ainda mais simples, os caracteres. Evidentemente, para que este tipo de reconhecimento seja vantajoso, o mais simples sub-padrão selecionado, chamado padrão primitivo, tem que ser muito mais facilmente identificado do que o padrão como um todo e tem que reunir características que permitam identificar um único padrão.

Assim, a seleção do padrão primitivo, ou extração de característica, é uma tarefa muito importante e vai variar de problema para problema a depender do padrão que se quer reconhecer. À linguagem que faz a descrição estrutural do padrão em termos de um conjunto de padrões primitivos e suas operações de composição dá-se o nome de Linguagem de Descrição de Padrão ou PDL (Pattern Description Language). As regras que governam a composição de padrões são dadas pela gramática da PDL. As operações de composição definidas entre sub-padrões podem usualmente ser expressas em temos de operações lógicas e/ou matemáticas. Para ilustrar um caso simples de escolha de padrão primitivo e operação de composição, considere o exemplo onde os padrões a serem reconhecidos são retângulos. Na figura 3 a relação de concatenação foi a escolhida.
 

                    
                            Figura 3 – Escolha de sub-padrões característicos usando a relação de concatenação.

Da figura 3 fica claro que o padrão em questão será representado pela cadeia aaabbcccdd, quando a relação ou operação de composição utilizada for a concatenação. Outra operação de composição poderia ter sido empregada. Para ilustrar o problema anterior, mas agora utilizando uma outra operação de composição através do operador +, considere a figura 4.

                                        

                                            Figura 4 – Ilustração do uso da concatenação “head-to-tail”.

Uma forma alternativa de representar padrões estruturalmente é através de grafos. Considere a figura abaixo.

                                                        
 
                                     

A vantagem de se utilizar grafos para representar padrões estruturalmente é que quando opta-se por esta estrutura, ganha-se em generalidade. Em contra partida, o uso de árvores nos dá um canal direto para adaptar as técnicas da teoria da linguagem formal ao problema de representar e analisar padrões contendo um significante conteúdo estrutural de forma compacta. Como exemplos de aplicações práticas de reconhecimento lingüístico de padrões tem-se o reconhecimento de caracteres ingleses e chineses, classificação de imagens de cromossomo e de imagens de impressões digitais dentre outros.

Arquitetura de um Sistema Lingüístico de Reconhecimento de Padrões

Um sistema lingüístico de reconhecimento de padrões é constituído de três partes principais: pré-processamento, representação do padrão e análise sintática. Embora essa seja uma descrição do método lingüístico, outros métodos utilizam uma arquitetura similar a esta. A figura 6 faz uma representação do que foi dito.
 

                    

                                Figura 6 – Arquitetura de um sistema de reconhecimento linguístico de padrões.

A primeira etapa é a fase de pré-processamento. Inicialmente ocorre a captura do padrão através de algum dispositivo de entrada e saída para que este seja armazenado no computador de maneira apropriada, conforme o seu tipo. Por exemplo, uma figura preta e branca pode ser codificada em termos de uma matriz de zeros e uns. Após a aquisição dos dados, inicia-se o pré-processamento propriamente dito, com o intuito de eliminar problemas existentes nos dados recém adquiridos. Para tanto, técnicas de filtragem, restauração, e/ou realce serão usadas para limpar ruídos, restaurar a degradação, e/ou melhorar a qualidade do padrão. Para facilitar o processamento em fases mais avançadas do sistema, algum tipo de compressão de dados é freqüentemente aplicado ainda na fase de pré-processamento. Assim, no final desta fase deve-se obter padrões com boa qualidade.

 A fase seguinte é a representação do padrão. Nela duas tarefas são realizadas: segmentação e extração de características. Com o objetivo de representar um padrão em termos de seus sub-padrões devem ser aplicadas técnicas de segmentação, que serão escolhidas de acordo com o resultado que se deseja obter. A importância da segmentação para o reconhecimento de padrões varia de acordo com a aplicação, geralmente em função da complexidade do padrão com o qual se deseja trabalhar. Em problemas de verificação de assinaturas, por exemplo, a segmentação não é uma fase tão importante quanto é em aplicações que lidam com a análise de imagens de satélite, onde desempenha um papel decisivo. Já a extração de características, ou seleção de atributos como também é conhecida, é uma tarefa de extrema importância para qualquer problema de reconhecimento de padrões e será estudada com mais detalhes ainda nesse trabalho.

Por fim resta a fase que vai decidir se um padrão é reconhecido ou não pelo sistema. No caso de reconhecimento lingüístico de padrões essa decisão é tomada pelo parser ou analisador sintático. Se o padrão pertencer a classe em estudo, o parser vai fazer sua descrição completa, através de uma parsing tree. Caso contrário o padrão é inválido ou pertence a outra classe.

Extração de Características

Extração de características, como o próprio nome sugere, é utilizada para extrair as características que são suficientes para o reconhecimento de um padrão. De forma mais detalhada, o objetivo da extração de características é obter um conjunto de características de menor dimensão que o dado bruto (uma imagem, por exemplo) sem perder a capacidade de discriminação, ou seja, conseguindo classificar os padrões em questão com melhor desempenho. Não há uma regra geral para se saber quais características são relevantes para um problema. Essa escolha é fortemente influenciada pela natureza do dado, a aplicação em questão e a tecnologia disponível para implementar o sistema. A escolha cuidadosa de quais características são importantes é fundamental para se evitar o processamento de informações redundantes. Os requerimentos abaixo servem como um guia para seleção de características que devem ser extraídas:

Como exemplos de características clássicas que devem ser extraídas em algumas aplicações pode-se citar fonemas em identificação de voz e pontos de ataque em aplicações de reconhecimento de manuscritos e verificação de assinaturas. Para ilustrar que a escolha de características varia de acordo com o problema, segue a figura 7. Nela as aplicações em questão referem-se ao reconhecimento de retângulos. Na figura 7.a o objetivo é distinguir objetos retangulares de objetos não retangulares. Já na figura 7.b o objetivo é reconhecer retângulos de tamanhos diferentes. Observe que os padrões  característicos escolhidas para a resolução do problema da figura 7.a não são adequados para a resolução do problema da figura 7.b.

                                

                                                           Figura 7.a – Reconhecimento de retângulos.

                    
 
                                            Figura 7.b – Reconhecimento de retângulos de diferentes tamanhos.

String Grammars

Depois que as características relevantes tiverem sido extraídas do padrão, a próxima fase é a construção de uma gramática que irá gerar uma linguagem para descrever o padrão que está sendo estudado. Para se construir a gramática o projetista baseia-se em conhecimentos disponíveis e em sua própria experiência. Quanto mais complexa a linguagem do padrão a ser reconhecido, maior poder deve ter o analisador sintático. Assim, enquanto autômatos finitos são capazes de reconhecer ou aceitar linguagens regulares, que não possuem um alto poder de descrição, gramáticas livres de contexto podem reconhecer linguagens com um poder de descrição muito maior, e analisadores construídos a partir de gramáticas livres de contexto podem ser necessários.

Para ilustrar o uso de gramáticas para o reconhecimento de padrões, pode-se considerar inicialmente o seguinte problema: deseja-se construir uma gramática que possa reconhecer triângulos equiláteros cujos lados têm dimensão 1, 2 ou 3. Utilizando  primitivas adequadas, como abaixo na figura 8, temos a seguinte linguagem para descrever os triângulos: L = {anbncn | 1 <= n <= 3}. Trata-se de uma linguagem regular e por razões de se facilitar a construção dos procedimentos de análise, a gramática que gera essa linguagem deve ser construída seguindo as regras abaixo:
 

                        
 
                                        Figura 8 – Padrões característicos para descrição de triângulos equiláteros.

Assim, algumas gramática para descrever o padrão desejado, atendendo às restrições acima, seguem abaixo:

Gramática Regular G1 = (N, W, P, S)

Onde:   N = {S, A1, A2, B10, B20, B30, B21, B31, B32, C1, C2, C3}
            W = {a, b, c}

            P:   S        =>  aA1 | aB10              B21   =>  bC2
                  A1      =>  aA2 | aB20              B30   =>  bB31
                  A2      =>  aB30                       B31   =>  bB32
                  B10     =>  bC1                        B32   =>  bC3
                  B20     =>  bB21                       C1    =>  c
                  C2      =>  cC1
                  C3      =>  cC2

Gramática Livre de Contexto: G2 = (N, W, P, S) na forma normal de Greibach

Onde:  N = {S, A1, A2, B1, B2, B3, C}
           W = {a, b, c}

          P:  S      =>   aA1C                           B3    =>  bB2
               A1    =>   b | aB2C | aA2C           B2   =>  bB1
               A2    =>   aB3C                           B1   =>  b
               C     =>   c

Mesmo neste simples exemplo, fica claro que gramáticas livres de contexto são mais compactas do que gramáticas regulares. Em casos mais complexos pode não ser possível se fazer uso das gramáticas regulares, nem mesmo de gramáticas livres de contexto, como por exemplo em problemas onde deseja-se reconhecer quadrados cujos comprimentos dos lados são maiores do que 1. Através do uso das primitivas da figura 3 a linguagem L = {anbncndn | n >= 1} descreveria este padrão. Claramente não trata-se de uma linguagem regular, visto que há infinitos quadrados que são descritos por essa linguagem. Assim é necessário utilizar uma gramática sensível ao contexto, pois nem gramáticas livres de contexto são capazes de denotar tal linguagem. Para resolver esse problema, um exemplo de gramática poderia ser o que segue:

Gramática Sensível ao Contexto: G3 = (N, W, P, S)

Onde:  N = {S, A, B, C, D, E, F, G}
           W = {a, b, c, d}

           P: S   =>  aAB              dG    =>  Gd
               A   =>  aAC | D        aG    =>  abcD
               Dc   =>  cD               bG   =>  bbcD
               Dd   =>  dD              dFB  =>  dFd
               DC  =>  EC              dFd  =>  Fdd
               EC  =>  Ed               cF    =>   Fc
               DB  =>  FB               bF   =>   bbc
               Ed   =>  Gd               aF   =>   ab
               cG  =>   Gc               bB   =>   bcd

Embora muitas classes de padrão intuitivamente pareçam ser sensíveis ao contexto, essas gramáticas têm sido raramente usadas para descrição de padrões simplesmente devido a sua complexidade. Ao invés disso gramáticas livres de contexto têm sido usadas para descrever padrões como caracteres do inglês, imagens de cromossomos e estruturas químicas.

Gramáticas Especiais

Até agora as gramáticas apresentadas possuíam  apenas uma relação entre os sub-padrões, a relação de concatenação. Trata-se de uma relação unidimensional e portanto insuficiente para descrever padrões em duas e três dimensões. O que tem que ser feito é incluir outras relações e assim aumentar o poder de descrição das gramáticas. A figura 9 ilustra uma utilização de gramáticas que possuem outras relações além da relação de concatenação.

                                    
 
                            Figura 9 - Exemplo do uso de uma gramática onde há mais de uma relação de construção.