Reconhecimento de Padrões

A habilidade do ser humano em reconhecer e classificar objectos sempre impressionou e continua a impressionar os cientistas...

Desde os primórdios da computação, a tarefa de implementar algoritmos emulando essa capacidade humana, tem-se apresentado como

a mais intrigante e desafiadora !

Reconhecimento de Padrões: O que é ?

O Reconhecimento de Padrões (RP) é a ciência que trata da classificação e descrição de objectos.

Um projecto de RP envolve normalmente:

Extracção de características dos objectos a classificar (ou a descrever);

Selecção das características mais discriminativas;

Construção de um classificador (ou descritor).

Reconhecimento de Padrões: Relações

São múltiplas e importantes as relações de RP com outras disciplinas, em particular da área da Informática:

	Processamento de sinal e imagem
	Teoria da optimização e da estimação
	Inteligência artificial
	Aprendizagem automática (machine learning)

	Mineração de dados (data mining and knowledge discovery)
	Sistemas adaptativos
	Modelização neuronal (artificial neural networks)
	Teoria dos autómatos
	Conjuntos difusos *(fuzzy sets)*
	Modelização estrutural
	Linguagens formais

Reconhecimento de Padrões: Métodos

Conforme o tipo de objectos a classificar (ou descrever) o projecto de RP usa algum (ou alguns) dos seguintes principais métodos ou abordagens:

Abordagem estatística

A abordagem clássica, historicamente mais antiga, denominada por "Teoria da Decisão". Assume que as características das classes se regem por determinados modelos probabilísticos.

Abordagem sintáctica

Procura descrever a estrutura dos padrões usando inter-relações de características descritoras básicas denominadas primitivas.

Abordagem neuronal

Abordagem tipo "caixa negra" que procura determinar um mapeamento óptimo entre entradas e saídas inspirando-se em modelos de neurónios do cérebro.

Abordagem difusa

Abordagem que tem em conta o grau de incerteza por vezes inerente a características e a classificações, usando a Teoria dos conjuntos difusos para modelizar esse grau de incerteza.

Existem ainda outras abordagens, com parentesco com alguma das anteriores.

Reconhecimento de Padrões: Aplicações

Classificação de dados,

reconhecimento e descrição de objectos,

análise de cenas

são tarefas importantes

em muitas aplicações de software (e também de hardware).

As técnicas de Reconhecimento de Padrões têm, assim, um vasto leque de aplicações num grande número de áreas científicas e tecnológicas, nomeadamente no projecto e desenvolvimento de sistemas inteligentes, que constituem o cerne do investimento tecnológico actual.

Segue-se uma enumeração de áreas de aplicação de RP.

Aplicações científicas

Astronomia Geologia

Câmara de bolhas Análise de dados de satélite

Entomologia Biologia e botânica

Ciências da vida e do comportamento Psicologia

Arqueologia Antropologia

Cibernética Educação

Sistemas de gestão de informação Comunicação

Existência de vida em planetas remotos

Aplicações industriais

Reconhecimento de caracteres Máquinas controladas por imagens

Detecção de defeitos (p.ex. têxteis) Análise e reconhecimento da fala

Análise de assinaturas Identificação de retina

Reconhecimento de caras Visão por computador

Análise e descrição de cenas Sistemas automáticos de navegação

Reconhecimento de fotografias Exploração de minérios

Detecção de fluxos (X-ray, sonic) Multimedia e animação

Projecto de brinquedos electrónicos Citologia automatizada

Sistemas de análise psicológica

Aplicações médicas

Análise de electrocardiogramas Análise de electroencefalogramas

Análise de radiografias e tomografias Interacção de fármacos

Exames de radioisótopos Exames microscópicos (p. ex. contagem de células)

Propriedades de cromossomas Estudos genéticos

Sistemas de diagnóstico clínico

Aplicações na agricultura

Análise de colheitas Avaliação de solos

Controlo de processos Análise de fotografias de recursos terrestres

Aplicações governamentais

Previsão meteorológica Análise e controlo de tráfico

Determinação de crescimento urbano Análise de poluição

Análise sísmica Previsões económicas

Identificação de impressões digitais Sistemas de vigilância e alarme

Análise de geo-recursos usando imagens obtidas via satélite

Aplicações militares

Análise de fotografia aérea Detecção remota

Detecção e classificação de sonar Classificação e análise de radar

ATR – Reconhecimento automático de alvos

No DEEC e Institutos de investigação associados à FEUP existem numerosos exemplos de projectos envolvendo a aplicação de técnicas de RP resultando em importantes aplicações práticas. Seguem-se três exemplos:

Análise e Classificação de Sinais

- Reconhecimento de formas de onda e diagnóstico de sinais electrocardiográficos.

Os diversos componentes de um sinal electrocardiográfico são reconhecidos e medidos (a figura ilustra o reconhecimento automático das ondas P, Q, R, S e T). As medições são usadas para classificar (diagnosticar) os sinais. Abordagens sintácticas e estatísticas são apropriadas a este tipo de problema.

Análise e Classificação de Imagens

- Classificação automática de rolhas.

As imagens das rolhas são obtidas e processadas por forma a realçar claramente os defeitos. A partir de imagens a preto e branco, mostrando os defeitos, são obtidas medições que permitem categorizar as rolhas, usando um classificador estatístico. O classificador é treinado com vista a emular o perito humano.

Análise e Classificação de Dados

- Previsão de peso fetal

A previsão do peso fetal com base em medidas ecográficas (dimensão do cérebro, fémur, etc.) é importante para avaliar o risco de um parto. A figura ilustra as previsões obtidas com uma rede neuronal (vermelho) face aos valores reais (azul). As previsões obtidas com a rede neuronal são superiores às obtidas com fórmulas de regressão popularizadas. Existe trabalho em curso com vista a aumentar a eficiência desta abordagem.

Reconhecimento de Padrões: Contactos

África do Sul, Pretória

Pattern Recognition and Computers Group, Dept. of Electrical and Electronic Engineering,

University of Pretoria: http://www.ee.up.ac.za/ee/cgi-bin/ee/pattern_recognition_page/pr_index_html

Alemanha, Berlim

Research Group Adaptive Modelling and Pattern Recognition, Center for Applied Computer Science:

http://www.amspr.gfai.de/

Alemanha, Bochum

Pattern Recognition and Scene Analysis Group, Institut für Neuroinformatik, Ruhr-Universität:

http://www.neuroinformatik.ruhr-uni-bochum.de/

Alemanha, Bona

Computer Vision and Pattern Recognition Group, University of Bonn:

http://www-dbv.informatik.uni-bonn.de/

Alemanha, Erlangen-Nuremberg

Chair for Pattern Recognition, Dept. of Computer Science, Friedrich-Alexander University:

http://www5.informatik.uni-erlangen.de/

Austrália, Perth

Introduction to Pattern Recognition Course, Centre for Intelligent Information Processing Systems,

Dept. of Electrical and Electronic Engineering: http://ciips.ee.uwa.edu.au/~mike/PatRec/PatRec.html

Áustria, Viena

Introduction to Pattern Recognition Course, Dept. of Automation, Vienna University of Technology:

http://www.lzk.ac.at/lecture/tuwien/183315

Canadá, Montreal

Pattern Recognition Course, Computational Geometry Lab, School of Computer Science,

McGill University: http://www-cgrl.cs.mcgill.ca/~godfried/teaching/pr-web.html

EUA, Connecticut

Statistical Pattern Recognition Course, Electrical Engineering and Computer Dept,

University of Connecticut: http://www.eng2.uconn.edu/~ian/300_f93/tutorial.html

EUA, Massachusetts Institute of Technology

Pattern Recognition Course, Vision and Modelling Group:

http://vismod.www.media.mit.edu/vismod/classes/mas622/

EUA, San Jose

Course on Human Computer Interface Design, Dept. of Electrical Engineering,

San Jose State University: http://www-engr.sjsu.edu/~knapp/hci.html

EUA, Tempe

Statistical Pattern Recognition, Computer Science & Engineering Dept., Arizona State University:

http://www.eas.asu.edu/~morrell/598/598.html

EUA, Vermont

Pattern Recognition Laboratory, College of Engineering & Mathematics, University of Vermont:

http://candide.emba.uvm.edu/

Grã-Bretanha, Brighton

Neural Networks Research Group, Mathematical Sciences Dept., University of Brighton:

http://www.it.bton.ac.uk/research/nn.html

Grã-Bretanha, Glasgow

Image Processing and Pattern Recognition Course, Dept. of Electronics and Electrical Engineering,

University of Galsgow: http://www.elec.gla.ac.uk/coursedb/3lgx.html

Grã-Bretanha, Londres

Neural Computing Course, Pattern Recognition and Image Processing Course,

Computer Science Dept., University College London: http://www.cs.ucl.ac.uk/teaching/ug/index.htm

Grã-Bretanha, Londres

Intelligent Systems Group, Computer Science Dept., University College London:

http://www.cs.ucl.ac.uk/research/intelligent_systems/

Grécia, Patras

Pattern Recognition Group, Dept. of Electrical Engineering and Computer Technology:

http://www.wcl2.ee.upatras.gr/index.html

Holanda, Delft

Pattern Recognition Group, Faculty of Applied Sciences, Delft University of Technology:

http://www.ph.tn.tudelft.nl/delftpr.html

Japão, Tóquio

Pattern Recognition Laboratory Yamamoto: http://www.parl.tutkie.tut.ac.jp/indexE.html

Polónia, Cracóvia

Dept. of Image Processing and Pattern Recognition, Institute of Computer Science,

Jagiellonian University: http://www.ii.uj.edu.pl/zpro/index.en.html

Portugal, Porto

Instituto de Engenharia Biomédica: http://ineb.fe.up.pt/

Suiça, Neuchâtel

Pattern Recognition Group, Institute of Microtechnology, University of Neuchâtel:

http://www-imt.unine.ch/www/grp_hu/welcome.html

Turquia, Istambul

Pattern Recognition Course, Dept. of Computer Engineering, Bogaziçi University:

http://www.cmpe.boun.edu.tr/~ethem/CmpE621.html

Reconhecimento de Padrões: Exemplo

O reconhecimento de caracteres é um tema clássico de RP. Um exemplo introdutório desta vasta área de investigação é apresentado nesta secção, onde se aproveita para introduzir também a noção de perceptrão.

Consideremos a situação ilustrada na figura inicial relativa à discriminação de U de V.

Suponhamos que desejávamos projectar uma máquina-perceptrão capaz de discriminar automaticamente Us de Vs, usando uma regra simples, linear, de classificação. Os Us e Vs consideram-se desenhados numa grelha de 8x7, conforme se ilustra a seguir (supõe-se que as imagens foram binarizadas):

Efectuando a soma dos bits segundo as linhas e as colunas da grelha obtêm-se as "projecções" (resp. H1 a H8 e V1 a V7) indicadas a azul na figura. Estas projecções sugerem as seguintes características como potencialmente úteis na discriminação de U's de Vs (outras escolhas são possíveis):

x1 = (V1+V2+V6+V7) / (V3+V4+V5)

x2 = (H7+H8) / (H1+H2+H3+H4+H5+H6)

A um conjunto (dito de treino) de Us e Vs podemos agora aplicar um perceptrão adaptativo linear (adaline), com vista a encontrar a recta óptima de separação de Us e Vs no espaço bidimensional das características x e y. O perceptrão tem a seguinte estrutura:

A classificação em duas classes de um qualquer objecto, representado pelo vector de características x = [x₁ x₂ ... x_d]^', exprime-se da seguinte forma:

Resposta = w₁x₁+w₂x₂+...+w_dx_d+w_d+1

Resposta >=0 : atribui à Classe 1 (Saída=1, p. ex.)

Resposta < 0 : atribui à Classe 2 (Saída=-1, p. ex.)

Trata-se, portanto, de um classificador linear em que a superfície de decisão é um hiperplano (para um dos lados está a classe 1; para o outro a classe 2). Podemos discriminar mais de duas classes usando vários perceptrões.

No exemplo da separação de Us de Vs usamos duas características (d=2): a superfície de decisão é uma recta.

O perceptrão começa por usar uma superfície de decisão arbitrária (pesos aleatórios, p. ex.) e "aprende" uma regra de classificação usando iterativamente as entradas (características dos objectos do conjunto de treino), ajustando os pesos com vista a obter à saída a classificação correcta. Na iteração k os pesos (w^k) são adaptados segundo o princípio de "punição-recompensa" (um dos princípios de aprendizagem artificial mais popularizados):

Punição:

(Resposta errada)

Se objecto Î Classe 1 e Resposta<0 : w^k = w^k-1+ cx^k-1

Se objecto Î Classe 2 e Resposta>=0 : w^k = w^k-1- cx^k-1

^{(c: factor correctivo)}

Recompensa:

(Resposta correcta)

w^k = w^k-1

Se as classes são linearmente separáveis o processo de aprendizagem pára quando se alcança um hiperplano separador. Caso contrário o hiperplano irá oscilar próximo da fronteira entre as classes.

Estamos agora em condições de avançar para a

Demonstração do Perceptrão

Clique no botão a seguir para executar a demonstração.

À pergunta inicial, responda "Yes".

Reconhecimento de Padrões: História

Alguns marcos importantes na história do RP:

Teoria da Decisão

1928 - J. Neyman, E.S. Pearson iniciam um trabalho pioneiro na Teoria da Decisão.

1936 - R.A. Fisher desenvolve o conceito de funções discriminantes em problemas de classificação.

1939 - A. Wald introduz na Teoria da Decisão a noção de risco.

1957 - C.K. Chow aplica a Teoria de Decisão Bayesiana ao RP.

1958 - T.W. Anderson desenvolve em detalhe a classificação Bayesiana com distribuições normais multivariadas.

1967 - T.M. Cover e P.E. Hart analisam o método não paramétrico dos K vizinhos mais próximos e determinam limites para o erro de classificação com este método.

1968 - L.N. Kanal e B. Chandrasekaran tratam de forma detalhada os aspectos relacionadas com a dimensionalidade dos problemas de RP.

1971 - D.G. Lainiotis e S.K. Park apresentam limites para a probabilidade de erro de um classificador estatístico.

1971 - K. Fukunaga e D.L. Kessell apresentam fórmulas de erro de classificação estatístics.

1972 - D.H. Foley apresenta fórmulas das estimativas de erro de treino e teste para um classificador estatístico linear de duas classes.

1973 - D.A. Bell apresenta um trabalho detalhado sobre classificadores usando árvores de decisão.

1974 - G:T. Toussaint compara diversos métodos de estimação de probabilidade de erro e apresenta o método de rotação.

1975 - J.A. Hartigan apresenta um trabalho detalhado sobre as diversas técnicas de aglomeração de dados e estimação da sua performance.

1980 - S. Raudys e V. Pikelis generalizam o trabalho de Foley (1972) para diversos tipos de classificadores.

1989 - K. Fukunaga e R.R. Hayes analisam em pormenor o efeito da dimensão amostral no projecto de classificação estatística e na sua performance

1991 - S.B. Gelfand, C.S. Ravishankar e E.J. Delp analisam em detalhe o projecto de classificadores hierárquicos.

1995 - E. Backer apresenta um trabalho de aplicação de técnicas de inteligência artificial em análise de aglomerados.

Análise Sintáctica de Padrões

1969 - J. Hopcroft e J. Ullman mostram a relação entre certas classes de gramáticas e autómatos de análise sintáctica.

1969 - A.C. Shaw mostra a relação entre descrição e análise sintáctica de dados pictóricos.

1975 - S. Horowitz apresenta um trabalho sobre descrição sintáctica de formas de onda.

1977 - T. Pavlidis apresenta um trabalho analisando em detalhe as diversas técnicas de reconhecimento sintáctico.

1978 - R. Gonzalez e M. Thomason descrevem aplicações de análise sintáctica ao reconhecimento de padrões.

1979 - Rosenfeld apresenta um estudo compreensivo de abordagens sintácticas usando linguagens de descrição de figuras.

1985 - H. Don e K. Fu mostram a utilidade da abordagem sintáctica em interpretação de imagens.

Redes Neuronais

1943 - W.C. McCulloch e W. Pitts estabelecem um modelo de neurónio baseado nos conceitos biológicos da época.

1958 - F. Rosenblatt introduz o modelo do perceptrão que se tornou um marco importante do RP, bem como os conceitos de aprendizagem supervisada e não-supervisada.

1960 - B. Widrow e M. Hoff introduzem o dispositivo adaline (adaptive linear) que permite discriminar classes de padrões usando um algoritmo iterativo de erro mínimo quadrático. O adaline e respectivo algoritmo sobrevivem ainda hoje no modelo do perceptrão multi-camada e algoritmo de retropropagação.

1969 - M. Minsky e S. Pappert e põem fim ao optimismo gerado pelo adaline e perceptrão mostrando algumas das suas limitações. O trabalho destes autores mergulha a abordagem das redes neuronais numa época de pessimismo que só termina nos anos oitenta.

1972 - T. Kohonen introduz o modelo de memória associativa e demonstra a sua capacidade de convergência em situações de aprendizagem não-supervisada.

1972 - S. Grossberger e G. Carpenter introduz o modelo dito de "adaptive resonance theory".

1982 - J. Hopfield introduz o modelo de rede neuronal que tem o seu nome e a função de activação sigmoidal.

1986 - D. Rumelhart, J. Hinton, R. Williams desenvolvem o algoritmo de retropropagação abrindo assim o caminho para a grande popularidade do modelo de perceptrão multicamada. As redes neuronais entram definitivamente no domínio das aplicações.

1988 - D. Broomhead e D. Lowe introduzem as redes neuronais baseadas em funções de base radial.

1992 - V.N. Vapnik introduz o conceito de máquinas de suporte vectorial.

Conjuntos Difusos

1965 - L. Zadeh introduz o conceito de conjunto difuso.

1969 - E.H. Ruspini introduz a aglomeração de dados usando conjuntos difusos.

1973 - J.C. Dunn apresenta a versão difusa do algoritmo ISODATA/C-médias.

1975 - S.C. Lee e E.T. Lee introduzem as redes neuronais difusas.

1977 - R.L.P. Chang e T. Pavlidis apresentam árvores de decisão difusa.

1982 - E.T. Lee apresenta métodos reconhecimento sintáctico usando árvores de decisão difusa.

1991 - H. Takagi e I. Hayashi apresentam redes neuronais com "raciocínio" difuso.