Quantização de cores em
Imagens: o caso do K-means
O Problema de Conglomerados (PC)
• PC se aplica quando temos um conjunto de dados e
queremos identificar subgrupos com características
comuns.
• Gostaríamos que estes subgrupos contivessem objetos
internamente similares entre si e distintos dos objetos
não contidos no subgrupo.
• Ao aplicar PC podemos estar categorizando objetos
que não possuem transições abruptas.
O problema de conglomerados em
processamento de imagem
Métodos
hierárquicos
• Árvore binária (divisivos ou
aglomerativos)
• Não permite realocação dos
objetos
• As tomadas de decisão são
locais não olhando para o
conjunto todo dos dados,
não abordando o problema
globalmente
Métodos Particionais
• Características:
Em geral tomam
decisões mais globais
Partem de uma partição
e tentam melhorá-la
É permitido realocar os
objetos
• Principais subclasses:
Minimização do erro
quadrático
Baseados em grafos
Evolucionários
Erro Quadrático
• Função objetivo: minimizar o erro quadrático
dado por
E(c,q(c))= w(c)d2(c,qj)
Onde c é o objeto e q(c) é o seu
representante, w(c) é 1 ou 0 quando c está
ou não associado a qj.
Definição do problema
• Uma cor no sistema RGB é representada pelo espaço
R3. Chamamos de resolução de cor da imagem ao
número de bits que utilizamos para a representação
de cor no computador.
• O processo de discretização do espaço de cor para
exibição de uma imagem é chamado de quantização
de cor
• Nosso objetivo é quantizar o gamute de cores original
de uma imagem
Quantização de cores em
imagens
Exemplo de imagem quantizada
(256 cores – octree)
Quantização: um caso do PC
• Queremos reduzir a quantidade de cores do gamute de
uma imagem, em geral para compactar o
armazenamento das informações
• Grande quantidade inicial de cores
• Sabemos quantos conglomerados queremos formar
• Validação perceptual dos conglomerados
Modelagem
• Objetos: cores da imagem
• Métrica euclidiana no espaço de cores
• Métodos capazes de lidar com uma grande quantidade
de objetos (caso contrário temos que recorrer a algum
pré-processamento da imagem)
• Representantes que minimizam o erro introduzido pelo
conglomerado: centróide
• Validação perceptual dos conglomerados obtidos
Pré-processamento dos dados
• Pré-quantização
No formato ‘truecolor’ cada
cor ocupa 24 bits de
memória, a pré-quantização
trunca as informações dos
bits de cada canal de cor, em
geral para 15 bits, o que
resulta em pouca perda
perceptual e uma redução
significativa da quantidade
de cores da imagem.
• Amostra de cores
Consiste em tomar uma
amostra aleatória das cores
da imagem para proceder a
quanização apenas neste
subconjunto, com isso
reduzimos muito a
quantidade de dados inicial
do problema, mas corremos
o risco de não amostrar
cores pouco freqüêntes
porém importantes da
imagem
Métodos mais usados para resolver
o problema
• Algoritmo de Populosidade
• Quantização Uniforme
• Hierárquicos divisivos (em geral fazem partições do
RGB adaptadas às cores da imagem): Corte Mediano
• Hierárquicos aglomerativos (recorrem a decisões locais
ou a uma redução inicial da quantidade de cores da
imagem): Octree
• Particionais: k-means (erro quadrático)
• Quantização uniforme: divide
uniformemente o espaço de cor em N níveis (não
se adaptando às particularidades de cada
imagem)
• Algoritmo de populosidade: A partir do
histograma de cores da imagem toma-se como
níveis de quantização as suas cores mais
freqüêntes (não se aplica ao problema geral de
conglomerados)
Condições de otimalidade
1- Dado um conjunto de níveis de
quantização obtemos a partição que fornece
a menor distorção segundo uma norma
(usamos distância euclidiana)
2- Dada uma partição, os níveis ótimos de
quantização podem ser determinados pelo
centróide da célula (média dos vetores)
K-means: mínimo local
1 Escolha uma paleta inicial de cor
2 Calcule a partição ótima para esta paleta (que
minimize a distorção)
3 A partir dessa partição redefina a paleta como
sendo os centróides da nova partição
4 Repita os passos 2 e 3 um número fixo de
vezes ou até convergir