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 globaisPartem de uma partição

e tentam melhorá-laÉ permitido realocar os

objetos

• Principais subclasses:Minimização do erro

quadráticoBaseados em grafosEvolucioná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çãoNo 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 coresConsiste 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)

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)

Condições de otimalidade

K-means: mínimo local

1 Escolha uma paleta inicial de cor2 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ção4 Repita os passos 2 e 3 um número fixo de

vezes ou até convergir