Upload
gayora
View
30
Download
3
Embed Size (px)
DESCRIPTION
Quantização de Cores por GNG. Aurélio Moraes Figueiredo. Quantização. Processo de representar imagens do tipo “true color” utilizando um número reduzido de cores se comparado ao número de cores original. - PowerPoint PPT Presentation
Citation preview
Quantização de Cores por GNG
Aurélio Moraes Figueiredo
Quantização
• Processo de representar imagens do tipo “true color” utilizando um número reduzido de cores se comparado ao número de cores original.
• Imagens do tipo “true color” são representadas a taxa de 24bit/pixel, componentes vermelho, verde e azul (modo RGB).
• O número máximo de cores distintas de uma determinada imagem seria 224 ~ 16.8 milhões de cores.
Quantização - Vantagens
• O processo reduz a quantidade requerida de memória e o tempo de transferência de uma determinada imagem.
• Extremamente importante em aplicações multimídia de maneira geral (uso na Internet, etc.).
• Pode ser perfeitamente utilizado como uma etapa de pré-processamento para um determinado algoritmo de compactação a ser utilizado.
Objetivo
• Estudo de técnicas conhecidas de Machine Learning aplicadas ao problema de quantização (GNG).
• As técnicas são aplicadas a um benchmark de imagens já utilizado em artigos, e seus resultados são comparados a resultados já obtidos por outras técnicas.
• Cada uma das imagens foi quantizada a 256, 128, 64, 32, e 16 cores.
• O critério de comparação adotado foi o erro médio quadrático.
Luz e Cor
Onda eletro-magnética
(m)
VISÍVEL
f (Hertz)
102 104 106 108 1010 1012 1014 1016 1018 1020
rádioAM FM,TVMicro-Ondas
Infra-VermelhoUltra-Violeta
RaiosX
106 104 102 10 10-2 10-4 10-6 10-8 10-10 10-12
vermelho (4.3 1014
Hz), laranja, amarelo,..., verde, azul, violeta (7.51014
Hz)
Luz branca
luzbranca
prisma
vermelhoalaranjadoamareloverdeazulvioleta
luz branca (acromática) tem todos os comprimentos de onda
luz branca (acromática) tem todos os comprimentos de onda
Newton
Cor Violeta 380-440 nmAzul 440-490 nmVerde 490-565 nmAmarelo 565-590 nmLaranja 590-630 nmVermelho 630-780 nm
Cor Violeta 380-440 nmAzul 440-490 nmVerde 490-565 nmAmarelo 565-590 nmLaranja 590-630 nmVermelho 630-780 nm
1 nm = 10-9 m
Representação perceptual da cor CIE RGB
r() R
g() G
b() B
Cor MonocromáticaC()
R = 700 nmG = 546 nmB = 435.8 nm
C) = r R + gG + bB
- 0.2
0
0.2
0.4
400 500 600 700
438
nm
546
nm
(nm)V
alo
res
do
s tr
i-es
imu
los
Combinação de três cores (RGB) para reproduzir as cores espectrais
r)
r)
g)
b)
C) = r) R + gG + bB
Componentes das cores monocromáticas
- RGB -
Processo aditivo para formação de cor
normalmentetemos 1 byte para cada componentemapeando[0, 255] em [0,1]
normalmentetemos 1 byte para cada componentemapeando[0, 255] em [0,1]
processo aditivo
R
G
B
1.0
1.0
1.0
Y
M
CW
K vermelho
azul
preto
verde
amarelo
ciano
magenta
branco
Formação de imagens
pixel
Imagem RGB
Imagem RGB
Canal R
Canal G
Canal B
Canais RGB
Quantizaçao
16 Cores 4.000 Cores
Quantizaçao
64 Cores 4.000 Cores
Quantizaçao
256 Cores 4.000 Cores
GNG (Growing Neural Gas):
• Em métodos de aprendizado não supervisionado somente os dados de entrada estão disponíveis, e não existe nenhuma informação a respeito das saídas desejadas.
• Um objetivo possível é o de obter redução de dimensionalidade dos dados de entrada, encontrar um sub-espaço de menor dimensão que represente a maior parte ou todo o conjunto de dados.
• Diminuir o número de amostras de um determinado conjunto de dados.
• Dependendo da relação existente entre a dimensionalidade dos dados de entrada e dos dados da saída, alguma informação pode ser perdida durante o processo.
GNG (Growing Neural Gas Algorithm):http://www.ki.inf.tu-dresden.de/~fritzke/
O algoritmo é descrito abaixo:
• Passo 0:– Iniciar com duas unidades a e b com vetores posição aleatórios
Wa e Wb em Rn;
• Passo 1:– Escolher uma amostra da ser treinada segundo a distribuição de
probabilidades do conjunto de amostras;• Passo 2:
– Encontrar, dentre as unidades disponíveis, as duas unidades mais próximas da amostra de entrada, S1 e S2;
GNG (Growing Neural Gas Algorithm):
• Passo 3:– Incrementar o peso de todas as arestas que tenham S1 como
um de seus vértices;
• Passo 4:– Adicionar a distância quadrada existente entre a amostra
sendo treinada e a unidade mais próxima dessa amostra ao acumulador de erros do neurônio:
GNG (Growing Neural Gas Algorithm):
• Passo 5:
– Mover a unidade S1 e seus vizinhos topológicos na direção da amostra sendo treinada, por frações iguais a eb e en respectivamente:
• Passo 6:
– Caso as unidades S1 e S2 estejam conectadas por arestas, essa aresta deve receber 0 (zero) como peso;
• Passo 7:
– Remover todas as arestas que possuam peso maior que Amax. Caso após a remoção das arestas alguma das unidades fique sem arestas, remover essa unidade da rede;
GNG (Growing Neural Gas Algorithm):
• Passo 8:
– Caso o número de amostras já treinadas seja igual a λ, inserir uma nova unidade na rede da seguinte maneira:
– Determinar a unidade q que possui o maior erro acumulado;– Inserir uma unidade r entre a unidade q e o seu vizinho
topológico de maior erro acumulado f;– Os pesos iniciais de r terão, portanto, a seguinte configuração:– Inserir arestas conectando a nova unidade criada r às duas
unidades através das quais r foi gerada;– Decrementar o erro das unidades q e f multiplicando esses error
pela constante a. Inicializar o erro acumulado da nova unidade r como sendo o novo valor de erro da unidade q;
GNG (Growing Neural Gas Algorithm):
• Passo 9:– Decrementar os erros de todas as unidades existentes
multiplicando seus erros acumulados por uma constante d;• Passo 10:
– Caso o critério de parada seja atingido (ex: caso o número de unidades existentes na rede seja alcançado), o treinamento está completo. Caso contrário, voltar ao passo 1.
Um exemplo de execução do algoritmo pode ser visto aqui. Os
parâmetros de entrada para esse caso foram: λ=100, eb=0.2,
en=0.006, a=0.5, Amax=50, d=0.995:
λ=100, eb=0.2, en=0.006, a=0.5, Amax=50, d=0.995:
Resultados obtidos com o GNG
Peppers
111334 Cores 256 Cores Erro * 500
Mandrill
230651 Cores 256 Cores Erro * 500
Airplane
77274 Cores 256 Cores Erro * 500
148279 Cores 256 Cores Erro * 500
Lena
168627 Cores 256 Cores Erro * 500
Sailboat
Resultados do GNG:
– Método iterativo, os parâmetros são ajustados caso a caso para o melhor resultado.
– Para o caso geral verificou-se que uma boa configuração seria: λ=200, eb=0.2, en=0.006, a=0.5, Amax=50, d=0.995
– A variação de λ foi a que produziu as diferenças mais significativas.
Resultados Comparativos
Trabalhos Anteriores