Técnicas de Inicialização Aplicadas ao Algoritmo FSS-LBGa

Resumo

A Quantização Vetorial (QV) é uma técnica utilizada na codificação de imagens. A QV é a extensão da quantização escalar para um espaço com k-dimensões (GRAY, 1984), podendo ser compreendida como o mapeamento dos vetores k-dimensionais em vetores de um subconjunto finito desse espaço chamado dicionário.  O algoritmo LBG (LINDE; BUZO; GRAY, 1980) é amplamente utilizado para o projeto de dicionários para a QV. Para a execução do algoritmo LBG, informam-se: dicionário inicial, dimensão k, o tamanho N do dicionário e um limiar de distorção ɛ. Um dos problemas apresentados pelo LBG é que ele pode gerar um dicionário com vetores-código subutilizados, de modo que existirão regiões de Voronoi vazias ou pequenas. Buscando melhorias no projeto de dicionário, diversos autores propuseram inicialização de dicionários. Versões bioinspiradas (inteligência de enxames) têm sido propostas para o projeto de dicionário, como é o caso dos algoritmos PSO-LBG modificado (PSO, do inglês Particle Swarm Optimization), FA-LBG modificado (FA, do inglês Firefly) (SEVERO et al, 2015) e FSS-LBG (FSS, do inglês Fish School Search) (FONSECA; FERREIRA; MADEIRO, 2018). Outra proposta foi uma versão modificada do LBG (LEE; BAEK; SUNG, 1997), na qual um fator de aceleração é introduzido na etapa de atualização do dicionário, de modo que novo vetor-código = vetor-código anterior + escala x (novo centroide – vetor-código anterior). Paliwal e Ramasubramanian (2000) também propuseram a aceleração do algoritmo LBG, porém utilizando um fator de escala variável baseado no número de iterações. Barros et al. (2019) propuseram a substituição do LBG pelo LBG acelerado de Paliwal e Ramasubramanian (2000) na etapa de atualização do dicionário do algoritmo FSS-LBG, chamando essa versão de FSS-LBGa, mostrando que a nova versão apresenta uma convergência mais rápida, porém sem ganho aparente na qualidade da reconstrução das imagens. O objetivo deste trabalho é avaliar se o uso de técnicas de inicialização combinadas em substituição à inicialização aleatória no algoritmo FSS-LBGa pode proporcionar uma melhor qualidade das imagens reconstruídas e maior velocidade de convergência. A metodologia consiste no uso de três técnicas de inicialização: Nova Técnica de Inicialização para LBG (KATSAVOUNIDIS, 1994), Inicialização Baseada em Clusterização Subtrativa (MIRZAEI; NEZAMABADI-POUR, 2014) e Inicialização Baseada em Estratégia de Grupos (MA, 2015) combinadas e aplicadas ao algoritmo FSS-LBGa. Foram utilizadas nove imagens em escala de cinza, Barbara, Boat, Clock, Elaine, Goldhill, Lena, Mandrill, Peppers e Tiffany, com dimensões de 256 x 256 pixels e 8 bits por pixel cada. Os dicionários utilizados nas simulações possuem dimensão k = 16, correspondendo a blocos de 4 x 4 pixels, e tamanhos N = 32, 64, 128, 256 e 512, resultando em taxas de codificação iguais a R = 0,3125 bpp, 0,375 bpp, 0,4375 bpp, 0,5 bpp e 0,5625 bpp, respectivamente. Quanto aos dicionários iniciais, foram utilizados dez dicionários inicializados de quatro formas diferentes: inicialização 1 (dez dicionários iniciais aleatórios), inicialização 2 (8 dicionários iniciais aleatórios + 1 da técnica de estratégia de grupos + 1 da técnica de clusterização subtrativa), inicialização 3 (8 dicionários iniciais aleatórios + 1 da técnica de estratégia de grupos + 1 da técnica nova) e inicialização 4 (8 dicionários iniciais aleatórios + 1 da técnica de clusterização subtrativa + 1 da técnica nova). Foram realizadas 30 simulações para cada cenário, sendo utilizado o valor de 1,6 como constante de aceleração para o algoritmo FSS-LBGa. O desempenho da aplicação das técnicas de inicialização foi avaliado por meio da qualidade das imagens reconstruídas a partir do valor médio da relação sinal-ruído de pico  (PSNR, do inglês Peak Signal-to-Noise Ratio)  em dB e a velocidade de convergência avaliada através do número médio de iterações e tempo em segundos. Resultados preliminares obtidos indicam que o uso combinado de técnicas de inicialização aumenta a velocidade de convergência do algoritmo em questão, bem como proporciona uma melhor qualidade das imagens reconstruídas na maior parte dos cenários estudados. Pode-se destacar em relação à qualidade, por exemplo, o ganho médio de 0,53 dB da imagem Elaine com a inicialização 3 para N = 512 em relação à inicialização 1. Neste mesmo cenário, a imagem Elaine apresentou redução de 45,07% no número médio de iterações e 48,9% em relação ao tempo médio com a inicialização 4 quando comparada com a inicialização 1.
 
Palavras-chave: Quantização Vetorial; Inteligência de Enxames; FSS-LBGa; Inicialização.
Referências
BARROS, N.; FERREIRA, F.; SEVERO, V.; MADEIRO, F. Aceleração do algoritmo FSS-LBG aplicado ao projeto de dicionários. In: Conferência Nacional em Comunicações, Redes e Segurança da Informação, 9. Anais. 2019.
 
FONSECA, C.; FERREIRA, F.; MADEIRO, F. Vector quantization codebook design based on fish school search algorithm. Applied Soft Computing, v. 73, p. 958-968, 2018.
 
GRAY, R. Vector Quantization. IEEE ASSP Magazine, nº. 1, pp. 4-29, Abril 1984.
 
KATSAVOUNIDIS, I.; KUO, J. C.-C.; ZHANG, Z. A new initialization technique for generalized Lloyd iteration. IEEE Signal Processing Letters, v. 1, n. 10, p. 144-146, out. 1994.
 
LINDE, Y.; BUZO, A.; GRAY, R. M. An algorithm for vector quantizer design. IEEE Transactions on Communications, v. 28, nº 1, p. 84-95,  jan. 1980.
 
MA, X.; PAN, Z.; LI, Y.; FANG, J. High quality initial codebook design method of vector quantization using grouping strategy. IET Image Processing, v. 9, p. 986-992, 2015.
 
MIRZAEI, B.; NEZAMABADI-POUR, H.; ABBASI-MOGHADAM, D. An effective codebook initialization technique for LBG algorithm using subtractive clustering. Iranian Conference on Intelligent Systems, p. 1-5, 2014.
 
SEVERO, V.; LEITÃO, H.; LIMA, J.; MADEIRO, F. Algoritmo PSO modificado aplicado ao projeto de quantizadores vetoriais. In: Congresso Brasileiro de Inteligência Computacional, 12. Anais 2015.
 
SEVERO, V.; LEITÃO, H.; LIMA, J.; LOPES, W.; MADEIRO, F. Algoritmo FA modificado aplicado ao projeto de quantizadores vetoriais. In: Congresso Brasileiro de Inteligência Computacional, 12. Anais. 2015.