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:
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:
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:
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:
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.