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 !
© Copyright J.P. Marques de Sá - 2000 |
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).
© Copyright J.P. Marques de Sá - 2000 |
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 |
© Copyright J.P. Marques de Sá - 2000 |
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.
© Copyright J.P. Marques de Sá - 2000 |
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
Câmara
de bolhas
Entomologia
Ciências
da vida e do comportamento
Psicologia
Arqueologia Antropologia
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
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
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
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ális
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
Análise e Classificação de Sinais
-
Reconhecimento de formas de onda
Os
diversos componentes de
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.
© Copyright J.P. Marques de Sá - 2000 |
Á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:
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:
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
© Copyright J.P. Marques de Sá - 2000 |
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 = [x1 x2 ... xd]', exprime-se da seguinte forma:
Resposta = w1x1+w2x2+...+wdxd+wd+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 (wk) 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 : wk = wk-1 + cxk-1 Se objecto Î Classe 2 e Resposta>=0 : wk = wk-1 - cxk-1 (c: factor correctivo)
|
Recompensa: (Resposta correcta) |
wk = wk-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". |
© Copyright J.P. Marques de Sá - 2000 |
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.
© Copyright J.P. Marques de Sá - 2000 |