PROJETO DE ARQUITETURA DE CODIFICADOR DE ENTROPIA
PARA COMPRESSÃO JPEG DE IMAGENS EM TONS DE CINZA
Luciano Volcan Agostini
Ivan Saraiva Silva*
Sergio Bampi
[email protected]
[email protected]
[email protected]
*Universidade Federal do Rio Grande do Norte – DIMAp - Natal - Brasil
Universidade Federal do Rio Grande do Sul – Grupo de Microeletrônica
Caixa Postal 15 064 - Porto Alegre – Brasil
ABSTRACT
This paper presents the design of an architecture to be
used in the last stage of the JPEG compression: the
entropy coding. This paper focuses in the compression of
gray scale images, but the proposed architecture can be
easily adapted to the compression of color images. The
entropy coder architecture was described in VHDL and
was synthesized for an Altera Flex10kE FPGA. This
architecture reaches a processing rate of 76 images per
second, for 640 x 480 pixels images. This performance is
larger than the performance demanded by real time
applications and it encourages the use of the entropy coder
architecture in a JPEG compressor designed in hardware.
RESUMO
Este artigo propõe e desenvolve uma arquitetura para a
última etapa da compressão JPEG: a codificação de
entropia. O foco do artigo é dado na compressão de
imagens em tons de cinza, mas a arquitetura proposta pode
facilmente ser adaptada à compressão de imagens
coloridas. A arquitetura do codificador de entropia foi
completamente descrita em VHDL e sintetizada para
FPGAs Altera da família Flex10kE, atingindo uma taxa
máxima de processamento de 76 imagens por segundo,
para imagens de 640 x 480 pixels. Este desempenho é
superior ao exigido para aplicações de tempo real e
encoraja o seu uso em um compressor JPEG
completamente desenvolvido em hardware.
1. INTRODUÇÃO
A compressão JPEG é a compressão mais utilizada para
imagens fotográficas, dada a sua elevada taxa de
compressão e as perdas não muito significativas inseridas
na qualidade da imagem pelo processo de compressão.
Os compressores JPEG em software estão amplamente
difundidos, mas a restrição de tempo de processamento
acaba por inviabilizar o seu uso em várias aplicações onde
o desempenho é o fator crítico. Para satisfazer os
requisitos destas aplicações foi necessário o
desenvolvimento de hardwares dedicados para partes e
mesmo para todo o compressor JPEG. Como o processo
para a compressão JPEG é bastante complexo, o
desenvolvimento de um compressor em hardware não é
uma atividade simples.
Este artigo apresenta uma arquitetura para a
codificação de entropia, que é o último passo da
compressão JPEG. Esta arquitetura está inserida em um
conjunto de arquiteturas já desenvolvidas que realizam
todas as etapas da compressão JPEG [1] [2] [3] [4]. A
arquitetura desenvolvida no artigo é direcionada para a
codificação de entropia de imagens em tons de cinza, mas
esta arquitetura pode ser facilmente adaptada para ser
usada na compressão de imagens coloridas.
As principais aplicações alvo para o compressor JPEG
em hardware em desenvolvimento são a monitoração e
controle de tráfego automotivo e a segurança predial.
O item 2 do artigo apresenta, resumidamente, a
compressão de imagens JPEG, enquanto que o item 3
apresenta em maiores detalhes a codificação de entropia.
O item 4 apresenta a arquitetura desenvolvida,
subdividindo-a em suas sete partes principais: codificação
diferencial, codificação RLE, cálculo de tamanho,
codificação VLC, codificação de Huffman, pre-montagem
e montagem.
O item 5 apresenta os resultados de síntese obtidos e,
por fim, o item 6 apresenta as conclusões do artigo.
2. A COMPRESSÃO JPEG
O padrão de compressão de imagens JPEG foi proposto
originalmente em 1987 pelo Join Photographic Expert
Group [5]. Rapidamente este padrão passou a ser o mais
utilizado para imagens fotográficas, mantendo este status
até os dias de hoje.
Existem quatro modos básicos de operação previstos no
padrão JPEG: sem perdas, hierárquico, progressivo e
seqüencial [6]. Os três últimos modos de operação
realizam uma compressão com perdas, isto é, parte da
informação contida na imagem original é perdida durante
o processo de compressão. Estas perdas podem ser
controladas para causarem efeitos minimamente
perceptíveis ao olho humano.
O modo seqüencial possui um subgrupo chamado de
baseline. O modo baseline é aquele que possui o número
mínimo de requisitos para considerar um processo de
compressão como sendo JPEG [7]. Por sua simplicidade e
eficiência, é o modo de operação mais utilizado em
compressores JPEG em hardware ou software [8]. O
modo baseline é o alvo da arquitetura proposta por este
artigo, por isso não serão dados maiores detalhes dos
demais modos de operação.
A compressão JPEG com perdas tem como núcleo o
uso da Transformada Discreta do Coseno em duas
dimensões (DCT 2-D). A DCT 2-D transforma a
informação da imagem do domínio tempo para o domínio
das freqüências. Então toda a manipulação dos dados, com
o objetivo de reduzir o número de bits necessários para
representar a imagem, é realizado neste domínio.
A imagem de entrada é dividida em blocos de 8x8
pixels para serem comprimidos e cada elemento destes
blocos possui 8 bits.
A compressão JPEG baseline para imagens em tons de
cinza pode ser dividia em três operações principais, de
acordo com a Fig. 1: DCT 2-D, quantização e codificação
de entropia.
Figura 1 – Operações da compressão JPEG baseline de
imagens em tons de cinza.
Para a compressão de imagens coloridas, mais duas
operações se fazem necessárias: conversão do espaço de
cores e dowsampling [7] [8]. Estas operações são
realizadas antes da aplicação da DCT 2-D e não serão
detalhadas neste artigo.
A primeira operação para a compressão JPEG de
imagens em tons de cinza é um deslocamento de nível nos
dados de entrada. Este deslocamento faz com que o valor
médio dos componentes da entrada seja igual a zero,
possibilitando uma maior uniformidade no processamento
da imagem [8]. Esta operação resume-se a uma simples
subtração de 128 em todos os valores de entrada
Após o deslocamento de nível as matrizes devem
passar pela DCT 2-D. A DCT 2-D não realiza nenhum
tipo de compressão, ela apenas prepara os dados para
serem comprimidos pelos passos seguintes da compressão
JPEG. Não se entrará, neste artigo, em detalhes e
definições sobre a DCT 2-D, por este ser um ferramental
matemático extremamente difundido. Uma abordagem da
DCT 2-D, direcionada para o processamento de imagens,
pode ser encontrada em [8] e [9].
Em [2] foi apresentado o projeto de uma arquitetura de
DCT 2-D para uso na compressão JPEG, que teve como
referência a arquitetura proposta em [10].
Os coeficientes da DCT 2-D passam, então, pela
operação de quantização [6] [7]. A quantização é uma
divisão inteira dos resultados da DCT 2-D por uma matriz
de valores predeterminados, chamada de matriz de
quantização. O objetivo da quantização é reduzir a zero a
maior parte dos elementos da matriz de coeficientes, sem,
no entanto, causar perdas muito perceptíveis na qualidade
da imagem. A operação de quantização, por ser uma
divisão inteira, é uma operação irreversível, isto significa
que as perdas geradas pela quantização não podem ser
recuperadas com uma simples operação inversa [8].
A última operação na compressão JPEG é a codificação
de entropia [6] [7] [8], que une várias técnicas de
compressão sem perdas para diminuir o número de bits
necessários para representar as matrizes quantizadas. Estas
técnicas são a codificação diferencial, a codificação de
comprimento variável (Variable Length Coding - VLC), a
codificação por seqüências de ocorrências (Run-Length
Encoding - RLE) e a codificação de Huffman. Como a
codificação de entropia é o foco deste trabalho, esta
operação será abordada em maiores detalhes no próximo
item deste artigo.
3. CODIFICAÇÃO DE ENTROPIA NA
COMPRESSÃO JPEG
Na compressão JPEG para imagens em tons de cinza, a
codificação de entropia é a operação onde é efetivamente
realizada a redução no número de bits utilizados para
representar cada uma das informações de cor da imagem.
A codificação de entropia é realizada sobre a matriz
8x8 de coeficientes quantizados da DCT 2-D. Nesta
matriz, o primeiro componente (linha 0, coluna 0) é
tratado de maneira diferenciada dos demais pela
codificação de entropia. Este componente é chamado de
componente DC da matriz, enquanto que os demais são
chamados de componentes AC [6].
A Fig. 2 apresenta genericamente as etapas da
codificação de entropia, onde destaca-se o fluxo
diferenciado entre os componentes DC e os componentes
AC da matriz de entrada. Este fluxo diferenciado será
detalhado a seguir.
Figura 2 – Etapas da codificação de entropia
Após o processo de quantização, a matriz resultante
terá muitas ocorrências de zeros. Como a DCT 2-D
concentra a maior parte da energia da imagem no canto
superior esquerdo da matriz [8], as freqüências localizadas
nesta região são as que possuem maior amplitude e, então,
são as que têm maior probabilidade de terem valores
diferentes de zero após a quantização. Então a matriz
resultante da quantização é lida em ziguezague pelo
codificador de entropia com o objetivo de agrupar as
ocorrências de zeros em grandes seqüências. Este
agrupamento das seqüências de zeros potencializa o uso
da compressão obtida através da codificação RLE [6].
3.1. Codificação de Entropia dos Componentes DC
A primeira etapa na codificação de entropia dos
componentes DC é a codificação diferencial. Como os
componentes DC de blocos consecutivos possuem um alto
grau de correlação [6], o valor da diferença entre estes
dois componentes possui uma amplitude menor do que a
amplitude original de um componente DC. A codificação
diferencial é efetuada com uma subtração do valor DC do
bloco anterior pelo valor DC do bloco atual (DCi – DCi-1),
gerando um campo que será chamado de Amplitude DC
neste artigo.
Após a codificação diferencial, a codificação de
entropia determina qual é o menor número de bits
necessários para representar o campo Amplitude DC,
através do cálculo de tamanho. Esta operação é realizada
tendo como referência a tabela de tamanhos, apresentada
no padrão JPEG [6]. De acordo com a faixa de valores do
campo Amplitude DC, este campo é classificado em
categorias que variam de 0 a 11. Cada categoria informa o
tamanho do resultado em bits através do seu identificador.
Este resultado será chamado de Tamanho neste artigo.
O campo Tamanho é então codificado por Huffman
[9]. A codificação de Huffman é uma codificação de
comprimento de palavra variável que utiliza a estatística
para determinar qual palavra deve ser associada a cada
símbolo. Os símbolos com maior número de ocorrências
recebem os menores códigos e os símbolos com menor
número de ocorrências recebem os maiores códigos. A
codificação de Huffman pode ser estática ou dinâmica. Na
codificação dinâmica as estatísticas são montadas para
cada diferente imagem, gerando um resultado ótimo em
termos de compressão. Por outro lado, na codificação
estática tabelas predefinidas são utilizadas, diminuindo
significativamente a complexidade do processo de
codificação, aumentando o seu desempenho, mas
reduzindo a taxa de compressão. O padrão JPEG [6]
sugere tabelas de Huffman estáticas para uso geral,
indicando que estas tabelas possuem desempenho razoável
para a maioria das aplicações. Para imagens em tons de
cinza a compressão JPEG baseline utiliza apenas duas
tabelas de Huffman: uma para os componentes DC e outra
para os componentes AC. O codificador de Huffman gera
o campo Código de Huffman.
A codificação VLC, da mesma forma que a codificação
de Huffman, utiliza palavras de comprimento variável
para representar os símbolos codificados. A diferença é
que a codificação VLC não utiliza dados estatísticos, ela
apenas descarta todos os bits que não são significativos no
símbolo de entrada. Mesmo o bit de sinal é descartado. Os
dados de entrada, para o codificador VLC, são: o campo
Amplitude DC, que será codificado; e o campo
Tamanho, que define o número de bits que serão
considerados pela codificação VLC. A codificação VLC
gera o campo chamado de Amplitude.
Por fim, o campo Código de Huffman é concatenado
com o campo Amplitude, gerando o par “Código de
Huffman / Amplitude”, que é a codificação do componente
DC gerada pelo codificador de entropia.
3.2. Codificação de Entropia dos Componentes AC
Para os componentes AC, a primeira etapa é a
codificação RLE. O princípio básico da codificação RLE é
a substituição de um conjunto de símbolos repetidos em
uma seqüência de dados pelo número de repetições e o
próprio símbolo [9]. Por isso a codificação RLE é indicada
para casos onde exista um grande número de repetições de
símbolos em seqüência. Na compressão JPEG existem
grandes seqüências de zeros após a leitura em zigue-zague
da matriz resultante da quantização, por isso a codificação
RLE foi simplificada para apenas contar a ocorrência
deste símbolo, além disso, como apenas os zeros é que são
contados, não é necessário que o símbolo apareça após o
número de ocorrências. Então a codificação RLE na
compressão JPEG conta quantos zeros existem antes de
um componente não zero e gera um par “Ocorrências /
Amplitude AC”, onde o campo Ocorrências informa o
número de zeros que antecedem o valor não zero e o
campo Amplitude AC é o próprio valor do componente
não zero. O padrão JPEG define em 15 o tamanho
máximo do campo Ocorrências, então uma seqüência de
16 ou mais zeros gera um par “Ocorrências / Amplitude
AC” especial, 15/0, que indica a existência de 15 zeros
seguidos por mais um zero e que reinicializa o contador de
zeros. Outro par especial é gerado quando a matriz de
entrada termina com zeros, este par é 0/0.
Após a codificação RLE a codificação de entropia do
componente AC, de forma similar ao que ocorre na
codificação dos componentes DC, determina qual é o
menor número de bits necessários para representar o
campo Amplitude AC, através da tabela de tamanhos,
também gerando o campo chamado de Tamanho.
O próximo passo para codificação de entropia dos
componentes AC é a concatenação do campo
Ocorrências, gerado pela codificação RLE, com o campo
Tamanho, gerado a partir da tabela de tamanhos. Esta
concatenação gera o par “Ocorrências / Tamanho”, que
deve passar pela codificação de Huffman, de modo similar
ao que ocorre com o campo Tamanho na codificação dos
componentes DC. A diferença está na tabela de Huffman
que será utilizada. O campo gerado também é chamado de
Código de Huffman neste artigo.
Simultaneamente à codificação de Huffman do par
“Ocorrências / Tamanho”, o campo Amplitude AC passa
pela codificação VLC, que é efetuada da mesma forma
que para os componentes DC, gerando o campo
Amplitude.
Por fim o campo Código de Huffman é concatenado
com o campo Amplitude, gerado pela codificação VLC
gerando o par “Código de Huffman / Amplitude”, que é a
codificação do componente AC gerada pelo codificador de
entropia.
4. A ARQUITETURA DESENVOLVIDA
A arquitetura proposta e desenvolvida neste artigo está
apresentada, genericamente, na Fig. 3. O codificador de
entropia recebe como entrada valores de 12 bits gerados
pela arquitetura da quantização. A saída do codificador de
entropia consiste de palavras JPEG de 32 bits, que são
entregues de forma assíncrona.
A arquitetura apresentada na Fig. 3 consome um valor
de entrada a cada ciclo de clock e opera em um pipeline de
quatro estágios.
Na Fig. 3 estão destacados os registradores usados
como barreira temporal para permitir o uso do pipeline.
A entrada da arquitetura do codificador de entropia é
síncrona, mas a sua saída é assíncrona. O assincronismo é
gerado por dois motivos. O primeiro diz respeito a
arquitetura do codificador RLE, que possui uma saída
assíncrona (como será visto em detalhes no item 4.2 deste
artigo) propagando este assincronismo para os demais
blocos da arquitetura. O segundo motivo é causado pelas
codificações VLC e de Huffman, que possuem
comprimento de palavra variável, fazendo com que os 32
bits da saída sejam entregues em uma taxa completamente
dependente do conjunto de entradas consideradas em cada
caso. Este assincronismo da saída não dificulta o cálculo
do desempenho do codificador de entropia, uma vez que a
taxa de consumo de entradas é fixa e que esta taxa pode
ser usada na definição do desempenho da arquitetura.
A arquitetura apresentada na Fig. 3 está dividida em
sete partes principais, abordadas nos próximos itens deste
artigo. Estas partes são: codificador diferencial,
codificador RLE, cálculo de tamanho, codificador de
Huffman, codificador VLC, pré-montador e montador.
4.1. Codificador Diferencial
O codificador diferencial é usado apenas para os
componentes DC e é a primeira operação na codificação
de entropia destes componentes. Como já foi dito, a
operação básica realizada pelo codificador diferencial é
uma subtração. O resultado gerado por esta operação é
chamado, neste artigo, de Amplitude DC.
A arquitetura desenvolvida para o codificador
diferencial é muito simples e está apresentada na Fig. 4. A
arquitetura consiste de um subtrator de 12 bits e de um
registrador, para armazenar o código DC do bloco
anterior. A escrita no registrador Anterior é habilitada
pelo sinal AC/DC, que indica se o valor de entrada é um
valor DC e, caso o valor seja AC, a escrita não é
permitida.
A saída do codificador diferencial terá 12 bits.
Figura 4 – Arquitetura do codificador diferencial
Figura 3 – Arquitetura genérica para o codificador de entropia
4.2. Codificador RLE
A codificação RLE é realizada somente nos
componentes AC da entrada, sendo simplificada para atuar
como um contador de zeros, como já foi exposto
anteriormente.
A arquitetura desenvolvida para o codificador RLE está
apresentada na Fig. 5, onde os registradores Amp. AC e
Ocorrências são os mesmos apresentados na arquitetura
global (Fig. 3). A linha tracejada na Fig. 5 delimita o
bloco chamado de Codificador RLE na Fig. 3.
Figura 5 – Arquitetura do codificador RLE
Esta arquitetura opera de forma assíncrona. Os valores
são consumidos na entrada a uma taxa constante de um
valor por ciclo de clock, mas a saída não respeita nenhuma
forma predeterminada de sincronismo. Se o valor de
entrada é zero a escrita nos registradores de saída fica
desabilitada. Esta escrita só é permitida quando o valor de
entrada for não zero. Como não é possível prever quando
um valor não zero irá aparecer na matriz de entrada, é
necessária a existência de um sinal de sincronismo que
indica que o valor na saída é um novo valor válido. Este
sinal está apresentado na Fig. 5 como OK e é utilizado
para habilitar a operação dos demais estágios da
arquitetura global.
Existem duas situações especiais no padrão JPEG,
previstas pela arquitetura proposta, em que o valor de
entrada é zero e é permitida a escrita na saída. Como o
campo Ocorrências tem o tamanho fixo de 4 bits,
seqüências de mais de 16 zeros não são permitidas, então
caso existam 15 zeros seguidos de mais um zero na
entrada, uma nova saída válida deve ser escrita, no caso o
registrador Ocorrências recebe o valor 15 e o registrador
Amp. AC o valor zero. Esta situação é controlada pela
arquitetura proposta através do carry out do contador de
zeros que, quando tem valor igual a um (16º zero), habilita
a escrita na saída. Desta forma o par “Ocorrências /
Amplitude AC” é gerado corretamente porque a entrada é
zero e é armazenada no registrador Amp. AC e o
conteúdo do registrador ACC é 15 e este valor é
armazenado no registrador Ocorrências.
A outra situação onde a entrada é zero e a escrita nos
registradores de saída deve ser habilitada é quando a
matriz de entrada termina com uma seqüência de zeros,
neste caso o valor escrito deve ser zero para os
registradores Ocorrências e Amp. AC. Esta situação é
controlada pelo sinal Last na Fig. 5, que indica que o
componente na entrada é o último componente da matriz.
Se este for o caso e a entrada for zero, então os
registradores de saída são resetados.
Quando o codificador RLE está operando em modo
normal (em nenhuma das situações acima), uma entrada
igual a zero inicia a operação no contador, desabilita a
escrita na saída e mantém o flag OK em zero, indicando
que a saída não está pronta.
Se a entrada for não zero, o conteúdo do registrador
ACC é copiado para o registrador Ocorrências, o
registrador ACC é resetado e o valor não zero da entrada
é escrito no registrador Amp. AC.
Sempre que uma nova saída válida é gerada, o flag OK
é posto em nível lógico um, habilitando a operação das
demais arquiteturas do codificador de entropia.
O codificador RLE está no mesmo estágio de pipeline
que o codificador diferencial Por isso as operações
realizadas pelos dois codificadores devem consumir
exatamente o mesmo número de ciclos de clock, para
possibilitar uma ligação transparente com o estágio
seguinte do pipeline.
As saídas dos codificadores diferencial e RLE passam
por um multiplexador, que seleciona qual das duas saídas
deve ser utilizada pelo próximo passo da arquitetura. Este
multiplexador está apresentado na Fig. 3 e é controlado
pelo sinal AC/DC, que indica se o valor em
processamento é AC ou DC. A saída deste multiplexador
é chamada de Amplitude do Coeficiente neste artigo.
4.3. Cálculo de Tamanho
O campo Amplitude do Coeficiente passa por um
cálculo de tamanho, que indica quantos bits são
significativos (sem contar como o bit de sinal) nos 12 bits
deste campo.
A arquitetura desenvolvida para este cálculo foi feita
através de uma simples lógica combinacional, similar com
a proposta em [10]. Esta arquitetura gera a saída chamada
Tamanho do Coeficiente, que possui 4 bits. A saída
Tamanho do Coeficiente será usada para controlar o
codificador VLC e o pré-montador e como entrada para o
codificador de Huffman.
4.4. Codificador VLC
O codificador de tamanho de palavra variável ou
Variable Length Coder (VLC) é usado para identificar os
bits significativos da entrada Amplitude do Coeficiente e
para descartar os bits não significativos, incluindo o bit de
sinal.
A arquitetura proposta identifica os bits significativos e
prepara o campo Amplitude do Coeficiente para ser
montado pelo pré-montador, gerando a saída Amplitude
VLC. Esta saída possui 12 bits portanto não possui um
tamanho de palavra variável. Os bits não significativos são
descartados a posteriori, quando da operação de prémontagem.
O codificador VLC é um barrel shifter controlado pelo
campo Tamanho do Coeficiente. O valor do campo
Amplitude do Coeficiente é deslocado para a esquerda
para que o seu primeiro bit significativo ocupe a posição
mais significativa da palavra.
A Tab. 1 apresenta o número de deslocamentos à
esquerda para cada valor do campo Tamanho do
Coeficiente.
bits. Então a saída das memórias e do próprio codificador
de Huffman será formada por dois campos: o Código de
Huffman e o Tamanho de Huffman. O campo
Tamanho de Huffman é necessário para a montagem das
palavras JPEG, uma vez que o campo Código de
Huffman deve ser montado em conjunto com o campo
Amplitude VLC e como ambos possuem comprimento de
palavra variável, o pré-montador necessita do tamanho do
Código de Huffman e do tamanho da Amplitude VLC
para poder realizar a sua função.
Tabela 1 – Deslocamentos para a esquerda gerados pelo VLC
para cada valor do campo Tamanho do Coeficiente
Tamanho
0
1
2
3
4
5
6
7
8
9
10
11
Nº de
deslocamentos
12
11
10
9
8
7
6
5
4
3
2
1
4.5. Codificador de Huffman
O valor Tamanho do Coeficiente (para os coeficientes
DC) e a concatenação entre o campo Tamanho do
Coeficiente e o campo Ocorrências (para os coeficientes
AC) são codificados por Huffman. Este artigo utiliza as
tabelas de Huffman estáticas propostas pelo padrão JPEG
[6]. A arquitetura do codificador de Huffman está
apresentada na Fig. 6.
Como o codificador de entropia foi desenvolvido para
ser utilizado para imagens em tons de cinza, existem
apenas duas tabelas de Huffman [6]: uma para os
elementos DC e outra para os elementos AC. As tabelas
de Huffman foram projetadas utilizando memórias ROM
internas ao FPGA. Os próprios valores a serem
codificados por Huffman são usados como endereços para
estas memórias.
Além do código de Huffman, também está armazenado
nestas memórias, o tamanho deste código em números de
Figura 6 – Codificador de Huffman
O uso das memórias foi otimizado ao máximo e uma
das operações realizadas neste sentido foi inverter o par
“Ocorrências / Tamanho”, proposto pelo padrão JPEG, o
que exigiu uma inversão equivalente no conteúdo da
tabela de Huffman utilizada. Esta inversão possibilitou o
uso direto do par “Tamanho / Ocorrências” como
endereço para a memória que contém a tabela de Huffman
de componentes AC usando o menor número possível de
posições de memória. Com o uso do par, tal qual proposto
pelo padrão, várias posições de memória reservadas não
seriam usadas. Este enfoque diferenciado em relação ao
padrão não implica em nenhuma incompatibilidade, uma
vez que a diferença reside no processo e não no produto,
no caso as palavras JPEG, que são idênticas às propostas
pelo padrão. Ainda assim foram inseridas 14 posições
vazias, referentes àqueles valores de entrada que possuem
probabilidade de ocorrência igual a zero.
São 162 possíveis códigos de Huffman referentes aos
elementos AC. Foram usadas 176 posições de memória
para esta tabela, com 8 bits de endereço.
São 12 os possíveis códigos de Huffman relativos aos
elementos DC, sendo que nesta memória não foram
inseridas palavras vazias. São usados 4 bits de endereço
para esta memória.
O comprimento de palavra de cada memória também
foi otimizado. A tabela de Huffman DC utiliza 9 bits para
os códigos de Huffman e 4 bits para o tamanho do código.
A tabela AC usa 16 bits para o código de Huffman e 5
para o tamanho do código.
Como o tamanho dos códigos de Huffman é variável,
optou-se por colocar o primeiro bit significativo de cada
código, no bit mais significativo de cada palavra de
memória, de forma similar ao que ocorre na codificação
VLC.
Como as saídas das duas memórias possuem tamanhos
de palavra diferentes, para padronizar o número de bits na
saída do codificador, na saída da memória com a tabela de
Huffman para os códigos DC são inseridos, entre o código
e o tamanho, 8 zeros.
A seleção de qual saída da memória deve ser entregue
na saída do codificador de Huffman é feita por um
multiplexador controlado pelo sinal AC/DC1, que indica
se o valor que está sendo processado é AC ou DC.
A saída do codificador entrega, para o pré-montador,
dois valores, o Código de Huffman e o Tamanho de
Huffman, que são obtidos com uma simples separação
entre os bits da saída do multiplexador. Os 16 bits mais
significativos formam o Código de Huffman, enquanto
que os 5 bits menos significativos formam o Tamanho de
Huffman.
A saída Amplitude utilizará 28 bits e a saída Tamanho
utilizará 5 bits.
4.7. Montador
A montagem final das palavras JPEG é realizada pela
arquitetura do montador. Esta arquitetura, apresentada na
Fig. 8, monta as palavras JPEG considerando apenas os
bits significativos do valor Amplitude, efetivando a
codificação de comprimento variável realizadas pelo
codificador VLC e indicadas pelo campo Tamanho,
gerado por estas arquiteturas e adicionados pelo prémontador. A arquitetura do montador foi inspirada na
arquitetura proposta por [11].
4.6. Pré-Montador
A arquitetura do pré-montador, apresentada na Fig. 7,
recebe quatro valores na entrada: Amplitude VLC,
Tamanho do Coeficiente, Código de Huffman e
Tamanho de Huffman. Na saída são entregues dois
valores para o montador: Amplitude e Tamanho.
Figura 8 – Arquitetura do montador
Figura 7 – Arquitetura do pré-montador
Os bits da Amplitude do VLC são deslocados para a
direita por um barrel shifter controlado pelo Tamanho de
Huffman. Nenhum bit é perdido nesta operação.
Este valor deslocado é montado com o Código de
Huffman por uma operação lógica ou, sendo que o
Código de Huffman é concatenado com zeros à direita,
que servem de máscara para os valores deslocados da
Amplitude do Coeficiente. Esta operação de montagem
preserva apenas os bits significativos do código Huffman,
realizando, de fato, a codificação de comprimento variável
referente ao codificação de Huffman. O resultado da
operação lógica ou é a saída Amplitude que será entregue
ao montador.
O número de bits significativos da Amplitude é dado
pela soma do Tamanho de Huffman com o Tamanho do
Coeficiente. Esta soma gera a saída Tamanho.
A operação realizada pelo montador é similar à
operação realizada pelo pré-montador, consistindo de um
barrel shifter controlado pelo campo Tamanho e uma
operação lógica ou para montar e agrupar os bits
significativos das diferentes entradas. A montagem das
palavras é controlada por um somador que acumula os
diferentes tamanhos das amplitudes de entrada.
O montador usa dois registradores para montar as
palavras JPEG. O registrador High armazena os primeiros
32 bits da saída e, quando estes 32 bits estão prontos, este
valor é enviado para a saída. O registrador Low é usado
para armazenar o overflow quando o valor gerado tiver
mais que 32 bits. Este overflow é armazenado no
registrador High quando uma nova palavra JPEG começa
a ser montada.
O flag OK indica que uma nova palavra JPEG válida
está pronta na saída do montador e, por conseqüência, na
saída da arquitetura do codificador de entropia.
5. RESULTADOS DA SÍNTESE
A Tab. 2 apresenta os resultados de síntese da
arquitetura proposta e desenvolvida para o codificador de
entropia. A família de dispositivos utilizados para a
síntese foi Flex10KE [12] da Altera e o dispositivo usado
foi um EPF10K30ETC144-1.
Tabela 2 – Resultados de síntese
Arquitetura
REFERÊNCIAS
Células Bits de Período
lógicas Memória (ns)
Codificador Diferencial
Codificador RLE
Cálculo de Tamanho
Codificador de Huffman
Codificador VLC
Pre-montador e montador
57
52
18
21
89
1238
0
0
0
3852
0
0
14,5
8,1
17,6
18,6
26
46,2
Codificador de Entropia
1532
3852
42,5
Como pode ser calculado a partir da Tab. 2, a
freqüência de operação do codificador de entropia atingiu
23,5MHz. Desta maneira, uma matriz de entrada de 8x8
elementos é completamente processada em 2,9µs e uma
imagem de 640 x 480 pixels é processada em 13,1ms.
Esse tempo de processamento para imagens de 640 x 480
pixels permite a codificação de entropia a uma taxa de 76
imagens em tons de cinza por segundo.
6. CONCLUSÕES
Este artigo apresentou a proposta e desenvolvimento de
uma arquitetura para a codificação de entropia, última
etapa da compressão JPEG. A compressão JPEG
considerada no artigo é a compressão para imagens em
tons de cinza no modo baseline.
O artigo preocupou-se com a contextualização do
codificador de entropia inserido na compressão JPEG para
então apresentar a arquitetura desenvolvida e seus
resultados.
Os resultados obtidos através da síntese em FPGAs da
Altera indicam que uma imagem de 640 x 480 pixels é
completamente codificada em 13,1ms pela arquitetura
desenvolvida, o que permitiria uma taxa de processamento
de 76 imagens por segundo.
É importante salientar que a taxa de processamento
obtida pelo codificador de entropia é cerca de duas vezes
superior à obtida pela arquitetura de cálculo da DCT 2-D
[2], que é o principal gargalo na compressão JPEG e no
compressor que está sendo desenvolvido em hardware.
Deste modo o uso da arquitetura do codificador de
entropia para o compressor JPEG em hardware é
encorajado pelos resultados obtidos.
[1] L. Agostini; S. Bampi. “Integrated Digital
Architecture for JPEG Image Compression”. In:
ECCTD’01 – European Conference on Circuit Theory and
Design 2001, 2001, Epoo - Finlândia. Vol. III, p. 181-184.
[2] L. Agostini; I. Silva; S. Bampi. “Pipelined Fast 2-D
DCT Architecture for JPEG Image Compression”. In:
SBCCI2001 - XIV Symposium on Integrated Circuits and
System Design, 2001, Pirenópolis - GO - Brasil. p. 226231.
[3] L. Agostini; S. Bampi. “Projeto de uma Arquitetura
de DCT 1D para a Compressão de Imagens JPEG”. In:
VII Workshop IBERCHIP, 2001, Montevidéo – Uruguai.
[4] L. Agostini; S. Bampi. “Arquitetura Integrada para
Conversor de Espaço de Cores e Downsampler para a
Compressão de Imagens JPEG”. In: VII Workshop
IBERCHIP, 2001, Montevidéo – Uruguai.
[5] “Home site of the JPEG and JBIG committees”
<http://www.jpeg.org>
[6] The International Telegraph and Telephone
Consultative
Committee
(CCITT).
“Information
Technology – Digital Compression and Coding of
Continuous-Tone Still Images – Requirements and
Guidelines”. Rec. T.81, 1992.
[7] W. Pennebaker and J. Mitchell. JPEG Still Image
Data Compression Standard, Van Nostrand Reinhold,
USA, 1992.
[8] V. Bhaskaran and K. Konstantinides. Image and
Video Compression Standards Algorithms and
Architectures – Second Edition, Kluwer Academic
Publishers, USA, 1999.
[9] J. Miano. Compressed Image File Formats – JPEG,
PNG, GIF, XBM, BMP. Addison Wesley Longman Inc,
USA, 1999.
[10] M. Kovac and N. Ranganathan. “JAGAR: A Fully
Pipeline VLSI Architecture for JPEG Image Compression
Standard”. Proceedings of the IEEE, vol. 83, n°. 2, 1995,
pp. 247-258.
[11] S. Lei; M. Sun. “An Entropy Coding System for
Digital HDTV Applications. IEEE Transactions on
Circuits and Systems for Video Technology. 1991, pp.
147-155.
[12] Altera Digital Library 2001 – version 1, Altera
Corporation, 2001.