View
128
Download
3
Category
Preview:
Citation preview
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
Recommended