Sobre o Indice de Desordem Como Figura de Merito em

Quantizacao Vetorial Robusta

A. R. S. Barreto, E. A. Lima, F. Madeiro

Programa de Pos-Graduacao em Engenharia de Sistemas, POLI, UPE,

50720-001, Recife, PE

E-mail: ar ppges@poli.br, eal@upe.poli.br, madeiro@poli.br

Palavras-chave: processamento de sinais, ındice de desordem, distancia de Hamming

Resumo: A quantizacao vetorial (QV) e suscetıvel aos erros do canal de transmissao. Umadas tecnicas usadas para torna-la menos sensıvel aos erros e a quantizacao vetorial robusta(QVR). O projeto de um quantizador robusto depende da definicao de uma figura de merito. Nopresente trabalho, apresentamos um estudo de vizinhanca (distancia) de Hamming do ındice dedesordem, que e uma figura de merito amplamente utilizada. Sao apresentados resultados desimulacoes envolvendo a transmissao de imagem por canal binario simetrico.

1 Introducao

A quantizacao vetorial (QV) e utilizada em diversos sistemas de compressao de sinais, porpermitir elevadas taxas de compressao. Entretanto, a QV apresenta uma grande sensibilidadeaos erros do canal de transmissao.

Uma alternativa para reduzir a sensibilidade e a Quantizacao Vetorial Robusta (QVR)[1, 3, 6]. Nessa tecnica, um dicionario (composto por vetores-codigo), previamente projetadoconsiderando um canal sem erro (ruıdo), e submetido a uma atribuicao de ındices (IA, indexassignment), na qual os vetores-codigos sao devidamente indexados, de modo a minimizar osimpactos dos erros de canal na qualidade da imagem reconstruıda. Duas tecnicas de IA bastanteutilizadas sao o Pseudo-Gray Coding [6] e o algoritmo Simulated Annealing (SA) [1].

A atribuicao de ındices aos vetores-codigo constitui um problema de otimizacao combinatorialque e classificado como sendo NP-Completo [5]. Uma alternativa de otimizacao e o simulatedannealing, utilizado neste trabalho.

Neste artigo e apresentado um estudo de vizinhanca de Hamming do ındice de desordem,que constitui-se em uma figura de merito utilizada em QVR.

2 Quantizacao Vetorial

Define-se a quantizacao vetorial [2] como um mapeamento Q de vetores de entrada x, K-dimensionais (no espaco euclidiano R

K), em N vetores de reconstrucao w pertencentes ao sub-conjunto finito W de R

K . Matematicamente, este mapeamento e definido por, Q : RK→W .O conjunto de N vetores-codigo (ou vetores de reconstrucao) e denominado dicionario e e

representado por W = {w1, w2, . . . , wN}. O tamanho do dicionario e N (quantidade de vetores-codigo) e K e a dimensao do quantizador vetorial.

Um quantizador vetorial pode ser entendido como a combinacao de duas funcoes: um co-dificador C e um decodificador D. O codificador representa cada vetor de entrada (da fonte)x ∈ R

K pelo seu vizinho mais proximo dentre os vetores-codigo. A regra de codificacao seresume a: C(x) = bI se d(x,wI) < d(x,wi), ∀i 6= I, em que bI e a representacao binaria de wI e

162

ISSN 2317-3297

d(.) e uma medida de distorcao. No decodificador, ha uma copia do dicionario W , e a regra dedecodificacao e dada por, D(bI) = wI .

3 Quantizacao Vetorial Robusta

Em um sistema de transmissao com canal ruidoso, a quantizacao vetorial apresenta grandesensibilidade aos ruıdos de canal. Devido aos erros de canal, a palavra-binaria bI e degradada e odecodificador recebe bj, que, por sua vez, indexara um vetor de reconstrucao wj e nao mais wI . Enesse cenario que a QVR desempenha um papel importante, dado que ela consiste em reordenar(organizar) os vetores-codigo de modo a minimizar o impacto dos erros de canal. Portanto,o reposicionamento (reordenamento) das palavras-binarias provoca uma nova organizacao dosvetores-codigo que compoe o dicionario.

Uma figura de merito denominada ındice de desordem (Ides(.)) pode ser utilizada para ava-liar o grau de organizacao do dicionario. Usualmente esta avaliacao e feita pelo ındice de desor-dem com distancia de Hamming igual a 1 bit (Ides 1), a qual acumula as distancias euclidianasquadraticas entre os vetores-codigo cujas palavras-binarias possuem distancia de Hamming igual1 bit. Para tornar os dicionarios mais robustos aos erros de canal, o alvo e reduzir o ındice dedesordem associado.

Neste trabalho, as simulacoes envolvendo a transmissao de imagens foram realizadas utili-zando o canal binario simetrico (BSC – Binary Symmetric Channel). Adotou-se um ındice dedesordem que reordena palavra-binarias cuja distancia de Hamming difere de 1 bit e tambemde 2 bits, denotado como ındice de desordem com distancia de Hamming igual a 2 bits (Ides 2),

Ides 2 =

N∑

i=1

∑

j∈H2(i)

||wi − wj ||2, (1)

em que {j : j ∈ H2(i)} e o conjunto de todas as palavras-binarias cuja distancia de Hammingentre j e i e igual a 1 bit ou igual a 2 bits (ou seja, {j : j ∈ H1(i) ∪H2(i)}).

No presente trabalho e realizada uma comparacao entre o Ides 1(.) e Ides 2(.) como figura demerito utilizada pelo algoritmo Simulated Annealing (SA) aplicado a QVR.

4 Resultados

Nesta secao sao apresentados resultados de simulacoes envolvendo a transmissao da imagemPeppers (256 × 256 pixels) pelo BSC. Para avaliar a qualidade das imagens reconstruıdas, foiutilizada a relacao sinal-ruıdo de pico (PSNR – Peak Signal to Noise Ratio), definida por

PSNR (dB) = 10 log10

[

(255)2

MSE

]

, (2)

em que MSE (mean square error) denota o erro medio quadratico entre as imagens original ereconstruıda.

Os dicionarios foram gerados a partir do algoritmo LBG [4]. Utilizou-se o conjunto de treinoformado por quatro imagens de 256×256 pixels: Barbara, Boat, Lena e Goldhill. Foram geradosdicionarios de dimensao K = 16 e tamanho N = 256 e N = 512. As seguintes notacoes foramadotadas: LBG – valores de PSNR obtidos usando dicionarios gerados pelo algoritmo LBG (semIA); SA1 – valores de PSNR obtidos usando dicionarios projetados pelo SA com Ides 1 e SA2 –valores de PSNR obtidos usando dicionarios projetados pelo SA com Ides 2.

A Tabela 1 mostra o numero de operacoes aritmeticas (adicao, subtracao e multiplicacaode valores de nıveis de cinza) envolvidas na determinacao de Ides 1 e de Ides 2. Nota-se, paraN = 256 e N = 512, que o numero de operacoes aritmeticas realizadas para determinacao deIdes 2 e, respectivamente, 4,5 e 5,0 vezes maior que o correspondente numero para Ides 1.

163

ISSN 2317-3297

NIdes 1 Ides 2

Adicao Subtracao Multiplicacao Adicao Subtracao Multiplicacao

256 30.720 32.768 32.768 138.240 147.456 147.456512 69.120 73.728 73.728 345.600 368.640 368.640

Tabela 1: Numero de operacoes aritmeticas para determinacao de Ides 1 e de Ides 2.

A Figura 1 apresenta os valores medios de PSNR referente a 50 transmissoes da imagemPeppers para cada valor da probabilidade de erro de bit (ǫ) considerado. Observa-se que, paraN = 256 e N = 512, houve uma superioridade de SA2 em relacao a SA1, no que diz respeito aosvalores medios de PSNR, para todas as probabilidade de erro de bit. Para ǫ = {10−3, 10−2, 10−1}e N = 512, SA2 apresenta um ganho de cerca de 0,02 dB, 0,12 dB e 0,40 dB, respectivamente,em relacao a SA1. A medida que a probabilidade de erro de bit aumenta, a superioridade de SA2em relacao a SA1 (em termos de ganho em dB) tende a aumentar, bem como a superioridadeem relacao ao algoritmo LBG.

12

14

16

18

20

22

24

26

10−4 10−3 10−2 10−1

PS

NR

(d

B)

Probabilidade de Erro de Bit

LBGSA1SA2

(a) N = 256.

12

14

16

18

20

22

24

26

10−4 10−3 10−2 10−1

PS

NR

(d

B)

Probabilidade de Erro de Bit

LBGSA1SA2

(b) N = 512.

Figura 1: Relacao Sinal-Ruıdo de pico (PSNR) para a imagem Peppers em funcao da probabilidade de

erro de bit do canal binario simetrico.

Na Figura 2 e mostrada a imagem Peppers reconstruıda, apos transmissao pelo BSC, comdicionarios deN = 512. Nota-se que, para cada valor de probabilidade de erro de bit considerado,a imagem obtida com dicionario projetado pelo SA2 apresenta uma qualidade ligeiramentesuperior a imagem reconstruıda pelo dicionario projetado pelo SA1 e, superior a imagem obtidacom dicionario gerado pelo LBG (sem IA).

5 Conclusao

Este artigo apresentou uma avaliacao do algoritmo SA utilizando o ındice de desordem comdistancia de Hamming igual a 1 bit e o ındice de desordem com distancia de Hamming igual a2 bits, no problema da QVR que envolve a obtencao de um dicionario mais resistente aos errosde canal. Os resultados das simulacoes mostram que a utilizacao do ındice de desordem comdistancia de Hamming igual a 2 bits no algoritmo SA aumenta a complexidade computacional aopasso que tem-se uma ligeira superioridade em termos de PSNR e qualidade visual das imagensreconstruıdas.

Agradecimentos

Os autores expressam seus agradecimentos a FACEPE e ao CNPq pelo apoio financeiro.

164

ISSN 2317-3297

(a) LBG, ǫ = 5× 10−3,PSNR = 22,06 dB.

(b) LBG, ǫ = 10−2,PSNR = 20,28 dB.

(c) LBG, ǫ = 5× 10−2,PSNR = 15,02 dB.

(d) SA1, ǫ = 5× 10−3,PSNR = 23,94 dB.

(e) SA1, ǫ = 10−2,PSNR = 22,79 dB.

(f) SA1, ǫ = 5 × 10−2,PSNR = 18,38 dB.

(g) SA2, ǫ = 5 × 10−3,PSNR = 24,04 dB.

(h) SA2, ǫ = 10−2,PSNR = 22,91 dB.

(i) SA2, ǫ = 5 × 10−2,PSNR = 18,65 dB.

Figura 2: Imagem Peppers reconstruıda por dicionarios com N = 512, apos transmissao por canal BSC,

considerando diversos valores de probabilidade de erro de bit (ǫ).

Referencias

[1] N. Farvardin, A study of vector quantization for noisy channels, IEEE Transactions onInformation Theory, 36, No. 4 (1990), 799–809.

[2] A. Gersho, R.M. Gray, “Vector Quantization and Signal Compression”, Kluwer AcademicPublishers, Boston, MA, 1992.

[3] E.A. Lima, G.G.M. Melo, W.T.A. Lopes, F. Madeiro, Um novo algoritmo para atribuicao deındices: avaliacao em quantizacao vetorial de imagens, TEMA - Tend. Mat. Apl. Comput.,2, No. 2 (2009), 167–177.

[4] Y. Linde, A. Buzo, R.M. Gray, An algorithm for vector quantizer design, IEEE Transactionson Communications, 28, No. 1 (1980), 84–95.

[5] X. Wang, X. Wu, Index assignment optimization for joint source-channel MAP decoding,IEEE Transactions on Communications, 58, No. 3 (2010), 901–910.

[6] K. Zeger, A. Gersho, Pseudo-gray coding, IEEE Transactions on Communications, 38, No.12 (1990), 2147–2157.

165

ISSN 2317-3297