Quantização Vetorial com k-means
Quantização Vetorial com k-means
Quantização vetorial é uma técnica utilizada para mapear dados de um conjunto grande em um conjunto menor de elementos, geralmente para fins de compressão de dados. No contexto de imagens, isso significa reduzir o número de cores diferentes em uma imagem, o que pode ser útil para compactação e segmentação.
Um dos algoritmos mais populares para quantização vetorial é o k-means, que particiona o espaço N-dimensional em células de Voronoi, onde cada célula é determinada por um centro. Cada ponto da célula está mais próximo do seu centro do que de qualquer outro centro.
Como funciona o algoritmo de k-means
O algoritmo k-means pode ser descrito em cinco passos principais:
- Escolha do número de clusters (𝑘): Define quantos grupos ou classes serão criados.
- Inicialização dos centros: Seleção inicial dos centros dos clusters.
- Classificação: Cada ponto é associado ao centro mais próximo.
- Recalcular os centros: Novos centros são calculados como a média dos pontos associados a cada centro.
- Convergência: Verifica-se se os centros mudaram significativamente. Se não, o algoritmo termina. Caso contrário, repete-se a partir do passo 3.
Experimento: Variabilidade no k-means
Para este experimento, modificamos o código para executar o k-means com nRodadas=1 e inicialização aleatória dos centros usando KMEANS_RANDOM_CENTERS. Executamos o algoritmo 10 vezes e comparamos os resultados.
Resultados
| Sushi (original) | Sushi K-means (NUM_ITERATIONS=1 e usando cv::KMEANS_PP_CENTERS) |
|---|---|
 |  |
10 Rodadas do Algoritmo k-means com Inicialização Aleatória
| 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|
 |  |  |  |  |
| 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|
 |  |  |  |  |
Análise dos Resultados
Embora as imagens possam parecer similares à primeira vista, ao sobrepor uma à outra, as diferenças se tornam evidentes. Isso ocorre devido à inicialização aleatória dos centros dos clusters. No algoritmo k-means, a posição inicial dos centros influencia o resultado final. Com NUM_ITERATIONS=1, o algoritmo não tem tempo suficiente para convergir para uma solução ótima, resultando em soluções que dependem fortemente das posições iniciais dos centros, causando alta variabilidade nos resultados entre diferentes execuções do algoritmo.
Esta variabilidade demonstra a importância da inicialização dos centros no k-means e como diferentes execuções podem levar a diferentes agrupamentos dos dados.