343o [Modo de Compatibilidade]) - UFPR · Conceitos básicos de classificação • Apesar de complexo, esse modelo é pior do que o modelo linear. • A principal característica

1

Reconhecimento de Padrões

Introdução

Luiz Eduardo S. Oliveira, Ph.D.

http://lesoliveira.net

Universidade Federal do ParanáDepartamento de Informática

Objetivos

• Introduzir os conceito básicos de reconhecimento de padrões através de um exemplo de um sistema de classificação clássico.

2

Introdução

• Pense em ações simples que realizamos no nosso dia-a-dia, e na complexidade envolvida, como por exemplo:

Interpretar placas de trânsito

Introdução

Ler um jornal: Diferentes Fontes, Figuras, Gráficos, Ilustrações, etc...

3

Introdução

• Agora imagine como implementar essas simples ações em um sistema de computador!

• Complicado? • O que seria necessário?

– Adquirir a imagem, ler, entender (classificar), tomar uma ação.

Introdução

• Diferentes abordagem para Reconhecimento de Padrões.– Estatística– Estrutural– Sintática

4

Um Exemplo

• Para ilustrar a complexidade desse tipo de sistema, considere o seguinte exemplo:– Uma indústria recebe dois tipos de peixe:

Salmão e Robalo. Os peixes são recebido em uma esteira, e o processo de classificação é manual.

– A industria gostaria de automatizar esse processo, usando para isso uma câmera CCD.

Um Exemplo (cont)

5

Um Exemplo (cont)

• Primeiramente devemos encontrar as características que distinguem um salmão de um robalo.– Altura, largura, coloração, posição da boca,

etc...

• Características (Features): Qualquer medida que se possa extrair de um determinado objeto.

Um Exemplo (cont)

• Características podem ser:– Simbólicas.– Numéricas (Continuas ou binárias).

• Ruídos (Erros):– Conceito originário da teoria das comunicações;– Podem estar presente no objeto.

• Uma mancha no peixe, por exemplo.

– Devidos ao sistema de aquisição. • Iluminação por exemplo.

6

Um Exemplo (cont)

• Dado as diferenças entre as populações de Salmão e Robalo, podemos dizer que cada uma possui um modelo específico.

• Modelo: Um descritor, geralmente representado através de uma função matemática.– Bom modelo é capaz de absorver ruídos.

Sistema Clássico

Aquisição

Pré-Processamento

Classificação

Salmão Robalo

Segmentação

Extração de Características

7

Área Multidisciplinar

Algoritmos/Estrutura de Dados

Reconhecimentode Padrões

ProcessamentoDe Imagens

Aprendizagem deMáquina

Estatística

Álgebra Linear &GeometriaComputação

Evolutiva

Domínio daAplicação

Sistema Clássico –Pré-processamento

• Simplificação do sinal capturado pela câmera. – Ex: Eliminação de alguns ruídos.– Processamento digital de imagens.

• Tornar os processos subseqüentes mais simples e rápidos.

8

Sistema Clássico –Segmentação

• Isolar os objetos de interesse na imagem.– No nosso exemplo,

encontrar o que é peixe e o que não é peixe.

– Processamento Digital de Imagens

• Filtros, morfologia matemática, etc...

Sistema Clássico –Segmentação

• Segundo nível de segmentação.– Encontrar e segmentar

os objetos de interesse detectados na primeira fase da segmentação.

9

Sistema Clássico –Extração de Características

• A imagem do objeto de interesse é enviada para o módulo de extração de características.– Reduzir a complexidade através da extração

de certas “características” ou “propriedades”.

Sistema Clássico –Classificação

• As características (valores) são passadas para o classificador, o qual toma uma decisão– No nosso exemplo: Salmão ou Robalo.

• Mas que tipo de características devemos usar?

10

Conceitos básicos de classificação

• Suponha que alguém nos diga que:– Robalos geralmente são maiores que

salmões.– Isso nos dá uma direção para modelar nosso

problema, ou seja,– Se o peixe ultrapassa um tamanho t, então

ele é um robalo, caso contrário, é um salmão.– Mas como determinar t ??


• Podemos selecionar alguns exemplares (base de treinamento) de peixe e verificar seus tamanhos.

• Suponha que após analisarmos nossa base de treinamento, tenhamos os seguintes histogramas

11


t

salmão

robalo Usando somente a medidade tamanho, não podemosseparar de maneira confiável nossas duas classes de peixes. Portanto, devemos tentar outras características.


salmão robalo

x

Outra característica: Medida de Claridade (coloração)

Como podemos notar,essa característica émuito mais confiável, mas não é perfeita.

Robalos que serão classificados comosalmão.

Noção deCUSTO

12


• Suponha que os clientes da nossa industria aceitem um pedaço de salmão embalado junto com robalo, mas o contrário é inaceitável.

• Devemos então alterar nossa fronteira para que isso não aconteça.


salmão robalo

Custo maior, uma vez que mais salmões serão classificados comorobalos

x

Erro Bayesiano

13


• Isso sugere que existe um custoassociado com a nossa decisão.

• Nossa tarefa consiste em encontrar uma regra de decisão que minimize o custo.– Isso é o papel central da Teoria da Decisão.

– Também pode ser visto como um problema de otimização.


• Como minimizar o custo?– Buscar outras características.

• Suponha que a claridade seja a melhor.

– Podemos utilizar duas características ao mesmo tempo.

=

2

1

x

x

x

Vetor de características bi-dimensional.

14


Nossa base de treinamento em um gráfico de dispersão

salmão robalo

altu

ra

claridade


• Nosso problema consiste em encontrar a fronteira de decisão que minimize o custo.

• Modelo mais simples:– Separação linear, y = ax+b– Algoritmos tradicionais:

• Perceptron, Funções Discriminantes Lineares.

15


salmão robalo

altu

ra

claridade


• Essa regra fornece uma boa fronteira de decisão, entretanto pode ser melhorada.– Adicionar mais características, como por

exemplo, dimensões do peixe, posição relativa dos olhos, etc..., poderiam ajudar.

• Quanto mais características, mais base de treinamento será necessária.– Maldição da dimensionalidade.

16


• Suponha que não dispomos de mais características.

• Solução: – Construir um modelo mais complexo do que

um modelo linear.


salmão robalo

altu

ra

claridade

Fronteira muito maiscomplexa.Separação perfeita!

Um exemplo (salmão) de teste

17


• Apesar de complexo, esse modelo é pior do que o modelo linear.

• A principal característica de um modelo deve ser a sua capacidade de generalizar.

• Modelos muito complexos geralmente não generalizam bem, pois decoram a base de treinamento (over-fitting).


• Por outro lado, modelos muito simples tendem a generalizar demais (under-fitting).

• Na aprendizagem de máquina, veremos técnicas para evitar over- e under-fitting, ou seja, construir fronteiras de decisão nem tão simples e nem tão complexas.

18


salmão robalo

altu

ra

claridade

Taxas

• Um sistema pode ser avaliado usando diferente taxas.

• A mais comuns são– Taxa de rec = (N_rec/Total_Img) * 100– Taxa de Erro = (N_err/Total_Img) * 100– Taxa de Rej = N_rej/Total_img) * 100– Confiabilidade = (Taxa de Rec / (Taxa Rec + Taxa de Erro)) * 100

19

Taxas

• Outra forma bastante utilizada para se avaliar classificadores são as curvas ROC (Receiver Operating Characteristics)– TP, TN (Diagonal principal da matriz)– FP, FN

20

Exercício

• Planeje um sistema que inspecione automaticamente uma linha de produção de biscoitos. Os seguintes aspectos devem ser observados:

1. Forma (redondo) e tamanho (2cm de raio).2. Integridade (Quebrado, mordido, etc) 3. Quantidade de recheio (pelo menos 3

marcas de chocolate).

� Considere todos os aspectos, desde a aquisição da imagem até a classificação.

Documents

343o [Modo de Compatibilidade]) - UFPR · Conceitos básicos de classificação • Apesar de complexo, esse modelo é pior do que o modelo linear. • A principal característica