Projeto de uma Arquitetura de DCT 1D para a Compressão de

Projeto de uma Arquitetura de DCT 1D para a
Compressão de Imagens JPEG
Luciano Agostini, Sergio Bampi
Grupo de Microeletrônica
Instituto de Informática – Universidade Federal do Rio Grande do Sul
Cx. Postal 15064 – CEP 91501-971 – Porto Alegre – Brasil
{agostini, bampi}@inf.ufrgs.br
RESUMO
Este artigo apresenta o projeto de uma arquitetura para o cálculo da Transformada Discreta do Cosseno
(DCT) em uma dimensão (1D). A aplicação alvo é a compressão de imagens digitais, mais especificamente, a
compressão JPEG. A DCT é a essência da compressão JPEG, por isso o seu estudo e desenvolvimento é um dos
fatores mais críticos em projetos de arquiteturas para compressores JPEG. O artigo apresenta o algoritmo
escolhido para o cálculo da DCT 1D, a arquitetura desenvolvida e os resultados do mapeamento desta arquitetura
para FPGAs da Altera. Como resultado final, a arquitetura desenvolvida gera uma matriz 8 x 8 de coeficientes da
DCT 1D, a cada 7,27ms.
ABSTRACT
This paper presents the design of an architecture for the calculation of Discrete Cosine Transform
(DCT) in one dimension (1D). The target application is digital images compression, more specifically, the JPEG
compression. DCT is the essence of JPEG compression, then its design is one of the most critical factors in
designs of architectures for JPEG compressors. This paper presents the chosen algorithm to DCT 1D calculation,
the designed architecture and the results of mapping of this architecture for Altera FPGAs. As final result, the
developed architecture generates a 8 x 8 matrix of DCT 1D coefficients in each 7,27ms.
1
Introdução
A Transformada Discreta do Cosseno (DCT) é uma ferramenta matemática que possui muitas
aplicações para a eletrônica, de filtros de áudio à compressão de vídeo. Basicamente a DCT transforma a
informação do domínio espacial para o domínio das freqüências, sobre o qual outras ferramentas podem ser
utilizadas. Este artigo abordará o uso da DCT para a compressão de imagens, em especial, para a compressão
JPEG. O padrão de compressão de imagens JPEG foi desenvolvido pelo Join Photographic Expert Group
[HOM00] e o seu princípio básico é a utilização de compressão com perdas controláveis para obter maiores taxas
de compressão. Neste contexto, as informações são transformadas, através da DCT, para o domínio das
freqüências. Neste domínio, as freqüências mais altas, para as quais o olho humano é menos sensível, podem ser
eliminadas gerando uma elevada taxa de compressão e uma pequena perda perceptível na qualidade da imagem.
Este tipo de compressão é recomendada apenas para imagens fotográficas, uma vez que as imagens de desenhos
são ricas em regiões de alta freqüência (bordas), que ficam distorcidas com a aplicação da compressão JPEG
[MIA99].
A Figura 1 apresenta os passos básicos da compressão JPEG, na qual pode-se perceber que o cálculo da
DCT está disposto no centro do processo. A transformação do espaço de cor é utilizada para transformar a
informação da entrada, que está no espaço RGB, para o espaço YCbCr, porque os espaços de cores do tipo
luminância e crominância (como o YCbCr) apresentam uma menor correlação entre os seus componentes,
potencializando o uso da DCT [BHA97]. A operação de downsampling elimina parte da informação de
crominância (componentes Cb e Cr) pois o olho humano é menos sensível a estas informações do que às
informações de luminância (componente Y). A DCT é então aplicada sobre os dados obtidos do downsampling.
Não é a DCT que efetua a compressão da informação, ela apenas possibilita as operações chamadas quantização
e codificação de entropia, que fazem juntas (e com a ajuda do downsampling) a compressão acontecer. A
quantização é uma divisão inteira dos coeficientes gerados pela DCT e, como a divisão é inteira, existem perdas
de informação. A codificação de entropia utiliza ferramentas das compressões sem perdas, como a codificação
RLE e de Huffman, para diminuir a quantidade de bits necessários para representar o resultado da quantização.
Informações mais detalhadas sobre o padrão JPEG podem ser encontradas em [THE92] e [PEN92].
Figura 1 – Passos da compressão JPEG
Como a compressão JPEG manipula imagens, que possuem duas dimensões, a DCT utilizada deve ser
em duas dimensões (DCT 2D). A DCT 2D não é efetuada sobre a totalidade da imagem de uma única vez devido
a alta complexidade deste cálculo. A imagem é então dividida em blocos, que possuem o tamanho típico de 8
linhas por 8 colunas e possuem apenas a informação de um dos componentes do espaço de cores (Y ou Cb ou
Cr). Neste artigo consideraremos o uso de 8 bits para representar cada uma das informações de cores. Desta
forma, a DCT 2D da compressão JPEG recebe como entrada uma matriz 8 x 8 com 8 bits para cada elemento.
Os algoritmos para o cálculo da DCT 2D possuem uma elevada complexidade computacional
dificultando o seu uso para aplicações dedicadas em hardware. A solução encontrada, na maior parte dos casos,
tem base em uma das propriedades da DCT 2D chamada de separabilidade, em que a DCT 2D pode ser
calculada a partir de dois cálculos da DCT 1D. O primeiro cálculo é efetuado sobre as linhas da matriz de
entrada e o segundo é efetuado sobre as colunas da matriz resultante do primeiro cálculo. Este artigo preocupa-se
em desenvolver uma arquitetura para o cálculo da DCT 1D.
O artigo está dividido em mais quatro itens. O item dois descreve o algoritmo de cálculo da DCT 1D
que foi utilizado. O item três apresenta a arquitetura que foi desenvolvida para o algoritmo descrito no item dois.
No item quatro estão apresentados os resultados obtidos com o mapeamento em FPGA da arquitetura definida no
item três. Por fim, no item cinco, são apresentadas as conclusões do artigo.
2
O Algoritmo para o Cálculo da DCT 1D
Genericamente, a DCT 1D para um vetor de 8 elementos pode ser definida como
Ti =
c (i )
 (2n + 1)iπ 
Vn cos

2 n= 0
16


7
∑
(1)
onde Vn é amostra n do vetor, i = 0, 1, ..., 7 e
 1

c (i ) =  2

î 1
se i = 0
(2)
caso contrário
Como a complexidade computacional desta definição básica é muito elevada, vários algoritmos
otimizados foram propostos no intuito de maximizar o desempenho deste cálculo. Os algoritmos mais otimizados
para implementação em software nem sempre são viáveis para implementações em hardware, dado o excessivo
uso de operadores, registradores e barramentos que alguns destes algoritmos demandam. Os algoritmos
utilizados em implementações em hardware centram esforços em três frentes principais: a diminuição do número
de operações aritméticas, a diminuição do número de operadores aritméticos e a possibilidade do uso de pipeline.
Um dos algoritmos que possui a melhor relação entre área e desempenho foi proposto por [ARA88] e
modificado por [KOV95]. Este algoritmo é completamente escalonado, formando um pipeline implícito, além
disso, efetua o cálculo da DCT 1D para um vetor de 8 elementos com apenas 5 multiplicações e 29 adições. Por
estes motivos, o algoritmo proposto por [ARA88] e [KOV95] foi escolhido para a implementação desenvolvida
neste artigo.
O algoritmo escalona o cálculo da DCT 1D em seis passos distintos e independentes. Nos três primeiros
passos e nos dois últimos existem apenas adições enquanto que no quarto passo existem só multiplicações. As
operações que acontecem em cada passo estão apresentadas abaixo, onde as entradas são a0, a1, ... , a7 e os
coeficientes calculados da DCT 1D são S0, S1, ... , S7. Nas multiplicações, os multiplicandos m1, m2, m3 e m4
são cossenos constantes e possuem os seguintes valores: m1 = cos (4π 16) , m2 = cos (6π 16) ,
m3 = cos (2π 16) − cos (6π 16) e m4 = cos(2π 16) + cos (6π 16) .
Passo 1
b0 = a0 + a7
b1 = a1 + a6
b2 = a2 – a4
b3 = a1 – a6
b4 = a2 + a5
b5 = a3 + a4
b6 = a2 – a5
b7 = a0 – a7
Passo2
c0 = b0 + b5
c1 = b1 – b4
c2 = b2 + b6
c3 = b1 + b4
c4 = b0 – b5
c5 = b3 + b7
c6 = b3 + b6
c7 = b7
Passo 3
d0 = c0 + c3
d1 = c0 – c3
d2 = c2
d3 = c1 + c4
d4 = c2 – c5
d5 = c4
d6 = c5
d7 = c6
d8 = c7
Passo 4
e0 = d0
e1 = d1
e2 = m3 x d2
e3 = m1 x d7
e4 = m4 x d6
e5 = d5
e6 = m1 x d3
e7 = m2 x d4
e8 = d8
f0 = e0
f1 = e1
f2 = e5 + e6
f3 = e5 – e6
f4 = e3 + e8
f5 = e8 – e3
f6 = e2 + e7
f7 = e4 + e7
Passo 5
Passo 6
3
S0 = f0
S1 = f4 + f7
S2 = f2
S3 = f5 – f6
S4 = f1
S5 = f5 + f6
S6 = f3
S7 = f4 – f7
A Arquitetura Desenvolvida
Considerando o algoritmo escalonado, o uso de uma arquitetura em pipeline passa a ser natural. Neste
caso, o pipeline terá seis estágios, onde cinco deles são de soma e um de multiplicação. Cada estágio do pipeline
utiliza oito ciclos de clock. A arquitetura utilizada neste artigo, apresentada na Figura 2, tem como base a
arquitetura proposta por [KOV95] com algumas modificações.
No compressor JPEG em que o cálculo da DCT 1D será usada, os dados de cor, com oito bits cada,
chegam serialmente na arquitetura da DCT 1D. Estes valores são produzidos pelo circuito que transforma o
espaço de cores de RGB para YCbCr [BHA97] e pelo circuito que efetua a operação chamada de downsampling
[MIA99] [PEN92] [BHA97]. Mesmo que exista a possibilidade da geração de oito valores em paralelo para o
cálculo da DCT, o normal, no caso do algoritmo utilizado, é a geração de um valor por ciclo de clock, dada a
grande quantidade de hardware necessária para as oito conversões de espaço de cores e para as oito operações de
downsampling em paralelo.
Figura 2 – Arquitetura para o cálculo da DCT 1D
Como os dados chegam na arquitetura da DCT 1D na taxa de um dado (8 bits) por ciclo de clock de
forma contígua, do início até o final da imagem, há a necessidade de um sincronismo muito preciso entre os
armazenamentos e as operações em cada um dos passos do algoritmo escalonado. Este sincronismo pode ser
observado na Figura 3, que apresenta o diagrama temporal do pipeline da arquitetura desenvolvida. Na figura
estão representados os cálculos parciais de duas matrizes 8 x 8, identificadas pelas letras x e y. Em cada estágio
está representada a faixa de elementos da matriz de entrada que está sendo usada no cálculo no estágio.
Figura 3 – Diagrama temporal do pipeline da arquitetura da DCT 1D
Como pode ser observado na Figura 3, a latência do pipeline é de 48 ciclos de clock. O cálculo de uma
DCT 1D nas linhas de uma matriz 8 x 8 utiliza 104 ciclos de clock quando o pipeline está vazio e 64 ciclos se o
pipeline está cheio.
Figura 4 – Zoom no diagrama temporal entre os ciclos de clock 57 a 64
A Figura 4 apresenta um zoom no diagrama da Figura 3 entre os ciclos de clock 57 a 64, em que podese perceber quais cálculos estão sendo efetuados em cada estágio do pipeline. No fragmento do pipeline
apresentado na Figura 4 estão sendo calculadas as últimas seis linhas da matriz x, sendo que a terceira linha está
pronta ao final do ciclo 64. O estágio 4 apresenta o pipeline de dois estágios do multiplicador, que será
apresentado em maiores detalhes no próximo item do artigo.
Na arquitetura proposta, os somadores dos três primeiros estágios do pipeline podem gerar carry out,
então, os oito bits da entrada transformam-se em 11 bits no final do terceiro estágio. O multiplicador tem como
operandos os resultados das somas dos estágios anteriores e as constantes m1, m2, m3 e m4. Da multiplicação
aproveitam-se apenas os valores inteiros, uma vez que, a quantização (o passo seguinte à DCT na compressão
JPEG), é uma divisão inteira de todos os resultados da DCT, desta forma os valores fracionários do resultado da
multiplicação não são relevantes. Como as constantes tem valores próximos a unidade, os 11 bits inteiros da
entrada do multiplicador são os mesmos entregues na sua saída. Os dois últimos estágios de soma não geram
carry out, então a saída da DCT 1D pode ser representada com 11 bits.
Como um valor é entregue para o circuito da DCT a cada ciclo de clock e como os oito valores são
necessários já no primeiro cálculo (b0 = a0 + a7), é necessário o uso de registradores duplicados do tipo pingpong para armazenar os dados que estão chegando serialmente e, no oitavo ciclo, disponibilizar os oito primeiros
valores de forma paralela para o primeiro nível de soma. O mesmo tipo de registradores duplicados são
necessários em todos os estágios do pipeline. Uma arquitetura para um registrador ping-pong de oito valores está
apresentada na Figura 5, onde os valores entram serialmente nos registradores ping através do pino In. No oitavo
ciclo de clock o sinal de controle Enable é ativado, permitindo a cópia em paralelo dos valores armazenados nos
registradores ping para os registradores pong. Desta forma, no oitavo ciclo de clock os oito primeiros valores
estão disponíveis nas saídas Out0 a Out7 dos registradores pong.
Figura 5 – Exemplo de registrador ping-pong
Os oito ciclos de clock necessários para o início do primeiro cálculo acabam por determinar a restrição
básica de toda a arquitetura: cada passo do escalonamento precisa utilizar, no máximo, oito ciclos de clock.
Os somadores utilizados são ripple carries de estágio simples, entregando um resultado por ciclo de
clock. Como existem, no máximo, oito somas em cada passo do escalonamento, são usados oito ciclos para que
todas as somas do passo sejam efetuadas, respeitando assim a restrição posta anteriormente. Então, com um
único somador por estágio do pipeline é possível realizar todas as somas necessárias dentro do tempo
estabelecido.
O ponto crítico passa a ser o multiplicador, que deve efetuar as cinco multiplicações em oito ciclos de
clock. Para o multiplicador foi desenvolvida uma arquitetura especial, que será abordada em maiores detalhes no
próximo item do artigo.
3.1 O Multiplicador
O multiplicador utilizado na arquitetura da DCT 1D foi decomposto em deslocamentos e somas como
forma de minimizar o hardware utilizado. Como uma das entradas do multiplicador é sempre uma constante, é
possível prever de antemão quais serão os deslocamentos necessários para cada cálculo. Os deslocamentos foram
obtidos através de barrel shifters.
Com o uso de quatro somas de deslocamentos por multiplicação foi possível manter o erro das
constantes abaixo de 0,6%, como pode ser observado na Tabela 1.
Tabela 1 – Erros na multiplicação
Constante
Valor Binário
Erro (%)
m1
0,101101000
0,563108895641754
m2
0,011000101
0,544103156502412
m3
0,100010101
0,033347458739675
m4
1,010011100
0,143541867234388
Além disso, a arquitetura do multiplicador foi desenvolvida para operar em um pipeline de dois
estágios. A arquitetura desenvolvida está apresentada na Figura 6, onde pode-se perceber, entre os dois níveis de
soma, a existência da barreira temporal necessária ao pipeline.
Internamente ao multiplicador todos os bits significativos foram considerados, mesmo os da parte
fracionária, para minimizar o erro na parte inteira. Apenas na saída é que os bits da parte fracionária são
descartados.
Os barrel shifters foram simplificados ao máximo, o que possibilitou uma minimização de recursos,
tanto nos próprios barrel shifters como nos somadores que neles estão conectados. As saídas dos barrel shifters
são concatenadas com zeros ou com a extensão do sinal para manter os números a serem somados na mesma
escala. O mesmo ocorre com as saídas dos somadores do primeiro nível.
Figura 6 – Arquitetura do multiplicador
A Tabela 2 apresenta os quatro barrel shifters e os deslocamentos associados a cada uma das quatro
constantes. Na Tabela 2, i é o valor de entrada e [x] significa que i é deslocado x bits à direita.
Tabela 2 – Deslocamentos associados a cada constante
BS1
BS2
BS3
BS3
M1
i [1]
i [3]
i [4]
i [6]
M2
i [2]
i [3]
i [7]
i [9]
M3
i [1]
i [5]
i [7]
i [9]
M4
i [0]
i [2]
i [5]
i [6]
O multiplicador desenvolvido utiliza quatro barrel shifters (1 de 13 bits e 3 de 14 bits), dois somadores
de 16 bits, um somador de 20 bits e dois registradores de 16 bits e efetua as 5 multiplicações em seis ciclos de
clock, respeitando o limite de oito ciclos. Além disso, o atraso do multiplicador é similar ao atraso nos
somadores dos outros estágios do pipeline do cálculo da DCT 1D, uma vez que a operação básica do
multiplicador também é a soma.
4
Os Resultados do Mapeamento em FPGAs
A arquitetura da DCT 1D foi descrita em VHDL e esta descrição foi inserida na ferramenta Maxplus2
da Altera [ALT95] para o seu mapeamento em FPGAs. A descrição VHDL foi feita de forma hierárquica para
facilitar a compreensão do código escrito. Esta hierarquia pode ser observada na Figura 7.
Figura 7 – Hierarquia da descrição VHDL
Os resultados do mapeamento das descrições VHDL estão apresentados por nível hierárquico. O quarto
e mais profundo nível da hierarquia está apresentado na Tabela 3 e contém os resultados do mapeamento dos
blocos da parte operativa do multiplicador.
Tabela 3 – Resultados dos blocos da parte operativa do multiplicador (multoper)
Nome do
Bloco
Células
Lógicas
Freqüência
(MHz)
Período
(ns)
BS13
33
76,34
13,1
BS14(3x)
34
72,46
13,8
Add16(2x)
30
28,98
34,5
Add20
38
23,75
42,1
A Tabela 4 apresenta o terceiro nível de hierarquia, contendo os resultados do mapeamento dos blocos
do multiplicador.
Tabela 4 – Resultados dos blocos do multiplicador (mult)
Nome do
Bloco
Células
Lógicas
Freqüência
(MHz)
Período
(ns)
MultOper
205
26,04
38,4
MultCont
11
166,67
6
Os resultados do mapeamento dos blocos do segundo nível da hierarquia estão apresentados na Tabela
5. Neste nível estão os blocos da parte operativa da DCT1D.
Tabela 5 – Resultados dos blocos da parte operativa da DCT1D (dct1doper)
Nome do
Bloco
Células
Lógicas
Freqüência
(MHz)
Período
(ns)
Ping8
120
166,67
6
Ping9
135
166,67
6
Ping10
150
166,67
6
Ping11
176
166,67
6
Ping11a
165
166,67
6
Ping11b
165
166,67
6
AddSub8c
16
48,08
20,8
AddSub9c
18
43,1
23,2
AddSub10c
20
41,67
24
Mult
216
28,49
35,1
AddSub11(2x)
21
37,45
26,7
A Tabela 6 apresenta os resultados do mapeamento dos blocos da DCT1D, que formam o primeiro nível
na hierarquia.
Tabela 6 – Resultados dos blocos da DCT1D (dct1d)
Nome do
Bloco
Células
Lógicas
Freqüência
(MHz)
Período
(ns)
DCTt1Doper
1523
22,62
44,2
DCT1dCont
554
25,51
39,2
Os resultados do mapeamento global da arquitetura da DCT1D são apresentados na Tabela 7. Estes
resultados foram obtidos para um FPGA EPF10K50VRC240-1 da Altera e a arquitetura consumiu 71 % do
FPGA, com um total de 2067 células lógicas utilizadas. A freqüência de operação ficou em 8,8MHz.
Tabela 7 – Resultados finais para a arquitetura da DCT 1D
DCT1D
Células Lógicas
Freqüência (MHz)
2067
8,8
Período (ns)
113,6
Nº de Pinos
99
5
Conclusões
Este artigo apresentou o desenvolvimento de uma arquitetura para o cálculo da DCT em uma dimensão,
cujo algoritmo escolhido foi detalhado, a arquitetura desenvolvida foi apresentada e os resultados obtidos no
mapeamento desta arquitetura em FPGAs foram disponibilizados. Como resultado final, o cálculo da DCT 1D de
uma matriz 8 x 8 com elementos de 8 bits é efetuado em 64 ciclos de clock com o pipeline preenchido e o clock
pode ter um período mínimo de 113,6ns. Então uma matriz 8 x 8 de coeficientes da DCT 1D é gerada a cada
7,27ms para os próximos passos da compressão JPEG.
O próximo passo deste trabalho é o desenvolvimento de uma arquitetura para o cálculo da DCT 2D a
partir da arquitetura da DCT 1D apresentada neste artigo. Para tanto será desenvolvido um buffer de transposição
e este buffer será unido a duas arquiteturas de cálculo da DCT 1D, formando assim a arquitetura da DCT 2D.
Além disso, pretende-se substituir os somadores usados por somadores do tipo carry look ahead (CLA) e
verificar os impactos desta alteração em termos de desempenho e de recursos utilizados .
6
Bibliografia
[ARA88]
[ALT95]
[BHA99]
[HOM00]
[KOV95]
[MIA99]
[PEN92]
[THE92]
ARAI, Y., AGUI, T., NAKAJIMA, M. A Fast DCT-SQ Scheme for Images. Transactions of
IEICE. Vol. E71, No. 11, 1988. P.1095-1097.
Altera Data Book, Altera Corporation, 1995.
BHASKARAN, V., KONSTANTINIDES, K. Image and Video Compression Standards
Algorithms and Architectures – Second Edition. Kluwer Academic Publishers, USA, 1999.
“Home site of the JPEG and JBIG committees” <http://www.jpeg.org> (05/01/00)
KOVAC, M., RANGANATHAN, N. JAGUAR: A Fully Pipeline VLSI Architecture for JPEG
Image Compression Standard. Proceedings of the IEEE. Vol. 83, No. 2, Fevereiro 1995. p.247258.
MIANO, J. Compressed Image File Formats – JPEG, PNG, GIF, XBM, BMP. Addison Wesley
Longman Inc, USA, 1999.
PENNEBAKER, W., MITCHELL, J. JPEG Still Image Data Compression Standard. Van
Nostrand Reinhold, USA, 1992.
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.