Veien videre

A determinação do dicionário de palavras visuais é de extrema importância no mé- todo BoF, pois ela será responsável por determinar quais características representam a estrutura de uma imagem.

A estratégia de geração do dicionário de palavras visuais está esquematizada na Figura 10 e é definida pelos seguintes passos: primeiramente um conjunto de imagens é escolhido da base de dados; para cada imagem é utilizado um detector de regiões de interesse (Hessian-Affine, Harris-Affine) e as regiões são descritas com algum descritor (SIFT, CS- LBP, etc), tal como discutido na Seção anterior; por fim, é realizado um agrupamento de dados desse espaço de características utilizando algum algoritmo de agrupamento. Cada agrupamento terá um centróide, o qual será considerado uma palavra visual do dicionário. Os algoritmos de agrupamento podem ser divididos em três categorias: hierárquicos, por particionamento e incrementais. Tais algoritmos serão descritos na Sub-seção 2.3.2.1.

(a) Detector Hessian-Affine

(b) Construção do descritor e quantização pelo k-means

Figura 10: Estratégia de geração do dicionário no algoritmo BoF

Um fator importante que afeta o desempenho do método BoF é o tamanho do dicio- nário de palavras visuais. Um vocabulário pequeno tem pouco poder discriminativo, pois dois agrupamentos podem ser atribuídos a uma mesma palavra visual. Por outro lado, um vocabulário grande é pouco generalista e afeta o desempenho da abordagem (SIVIC;

50 Capítulo 2. Fundamentação Teórica

2.3.2.1 Algoritmos de agrupamento

Algoritmos de agrupamento são técnicas de classificação não supervisionada de dados em grupos. Tal agrupamento é baseado na similaridade entre os dados, sendo que dados de um mesmo grupo são mais similares entre si do que dados pertencendo a outros grupos. Eles são divididos em duas categorias: hierárquicos e por particionamento (JAIN; MURTY;

FLYNN, 1999).

Nos algoritmos hierárquicos, os grupos vão sendo formados por aglomerações ou di- visões de elementos, normalmente sendo representados por uma árvore. Uma vantagem destes algoritmos seria a facilidade em lidar com qualquer medida de similaridade utili- zada e sua consequente aplicabilidade a qualquer atributo. As desvantagens seriam em relação ao critério de parada impreciso e ao não refinamento das soluções obtidas durante a execução do algoritmo (BERKHIN, 2002).

Os algoritmos mais comuns são o single-link e o complete-link (JAIN; MURTY; FLYNN,

1999) que são diferentes na maneira de como calculam a similaridade entre um par de dados. Os formatos dos grupos também serão diferentes. Pelo complete-link os grupos são mais compactos e pelo single-link são mais alongados (Figura 11).

(a) Algoritmo single-link para 2 classes (b) Algoritmo complete-link para 2 classes

Figura 11: Algoritmos de agrupamento (JAIN; MURTY; FLYNN, 1999)

O algoritmo single-link é um algoritmo do tipo aglomerativo, ou seja, todos os dados são grupos individuais e, recursivamente os dados vão se agrupando.

O algoritmo single-link (LACHI; ROCHA, 2005) pode ser descrito da seguinte maneira:

1. Defina cada padrão como sendo um grupo;

2. Construa uma lista das distâncias entre padrões, para todos os pares de padrões; 3. Ordene esta lista em ordem crescente;

próximos de dk são conectados por uma aresta;

5. Se todos os padrões são membros de um grafo conexo, então, pare. Caso contrário repita todos esses passos.

Veja que no single-link a similaridade é definida como máxima entre os membros dos grupos. No algoritmo complete-link, é utilizado o mesmo esquema do algoritmo single-link, porém a similaridade é definida como mínima entre os membros dos grupos.

Nos algoritmos por particionamento o conjunto de elementos é dividido em k subcon- juntos, alocando inicialmente os elementos aos grupos. Tais algoritmos são vantajosos em aplicações que envolvem um grande número de conjuntos, devido a capacidade computa- cional de se criar a hierarquia (LACHI; ROCHA, 2005;PIRES, 2008).

Um dos grandes problemas desses algoritmos é a escolha do número ideal de grupos. Para minimizar tais problemas, são utilizados índices de validação, ou seja, os algoritmos são executados repetidas vezes, utilizando diferentes valores para k, e o melhor resultado obtido com o índice é utilizado como resultado do agrupamento. Alguns índices utilizados são: PBM-index (PAKHIRAA; BANDYOPADHYAY; MAULIK, 2004), Xie-Beni (XIE; BENI,

1991) e Calinski-Harabasz (CALINSKI; HARABASZ., 1974).

Um dos métodos bem conhecidos é o k-means (MACQUEEN, 1967) que utiliza os cen-

tróides para representar os grupos, o qual é calculado pela média de todos os objetos do grupo.

O algoritmo k-means pode ser descrito pelos seguintes passos (Figura 12) (FONTANA;

NALDI, 2009):

❏ Atribuem-se valores iniciais para os protótipos, como por exemplo, sorteio aleatório desses valores dentro dos limites de domínio de cada atributo;

❏ Atribui-se cada objeto ao grupo cujo protótipo possua maior similaridade com o objeto;

❏ Recalcula-se o valor do centróide de cada grupo, determinando a média dos objetos atuais do grupo;

❏ Repetem-se os passos 2 e 3 até a estabilização dos grupos;

Um dos maiores problemas do k-means é que ele é sensível a seleção da partição inicial e pode convergir para um mínimo local caso a partição inicial não seja bem escolhida

(JAIN; MURTY; FLYNN, 1999). Outra desvantagem é a sua sensibilidade em relação a

erros ou elementos muito diferentes dos demais. Caso haja um dado errôneo, ele pode influenciar drasticamente o centro do seu grupo, interferindo na análise do resultado.

52 Capítulo 2. Fundamentação Teórica

(a) Sorteio dos valores iniciais dos cen- tróides

(b) Atribuição dos objetos aos grupos cujo centróides possuem maior simila- ridade

(c) Recalcula os valores dos protótipos como sendo a média dos objetos atuais pertencentes ao grupo

(d) Preparação para repetição dos pas- sos 2 e 3. Disvincula-se os objetos dos grupos.

(e) Repetição do passo 2 - Atribuição dos objetos aos grupos cujo protótipo possua maior similaridade

(f) Repetição do passo 3 - Recalcula os valores dos protótipos como sendo a média dos objetos atuais pertencentes ao grupo

culos de distâncias. Llyod k-means (LLOYD, 1982) usa um diagrama de Voronoi ao invés

de determinar o centro mais próximo do conjunto de pontos.