Compressão Sem Perdas de Imagens Digitais
Coord. de Pós-Grad. em Informática - Universidade Tiradentes - Campus II - Aracaju-Se,1999. jfonseca@unitnet.com.br
Resumo - Este trabalho descreve os aspectos da compressão sem perdas de imagens digitais e introduz o leitor ao padrão de compressão de imagens digitais paradas JPEG - Joint Photografic Experts Group - enfatizando a compressão JPEG sem perdas.
Abstract - This paper describes the aspects of lossless data compression, and introduces the reader to Still Image Compression Standard JPEG - Joint Photografic Experts Group - with emphasis on lossless JPEG.
(Palavras-chave: compressão de imagens digitais, compressão sem perdas, JPEG, lossless JPEG)
Comprimir dados é o processo que permite reduzir a quantidade total de dados necessária para representar uma certa quantidade de informação, e apresenta dois fatores de extrema importância: a taxa de compressão e a velocidade de processamento .
A compressão de dados é composta de duas etapas: modelagem e codificação. A etapa de modelagem dos dados de entrada é responsável pela decisão de qual código representará a informação; ou seja, é simplesmente um conjunto regras usadas para processar os dados de entrada e determinar qual código os representará. A codificação é um conjunto de símbolos que representa a informação ou os dados de entrada.
Os métodos de compressão de imagens dividem-se em dois grandes grupos: os sem perdas ou reversíveis e os com perdas ou irreversíveis. Algoritmos sem perdas eliminam somente as informações redundantes, possibilitando, assim, a reconstrução total da imagem original após o processo de descompressão. Já os algoritmos de compressão com perdas eliminam, além das informações redundantes, as informações irrelevantes, possibilitando somente a reconstrução aproximada da imagem original após a descompressão.
Um esquema típico de compressão sem perdas para imagens em tons de cinza obtém taxa de compressão da ordem de 50%, possibilitando reaver a imagem original a partir da versão comprimida.
Numa imagem digital há, basicamente, três tipos de redundâncias: de código, interpixel e psicovisual. Na redundância de código o processo de codificação atribui à informação códigos com número de bits variáveis de acordo com a probabilidade de ocorrência de determinado tom de cinza ou cor do pixel na cena; ou seja, o nível de cinza ou cor com maior ocorrência, será representado por uma palavra-código de comprimento menor; ao contrário, se um nível de cinza ou cor tem pouca presença na cena, este valor é representado por uma palavra-código maior.
A redundância interpixel nos permite prever o valor de um pixel pelos valores de seus pixels vizinhos, esta correlação espacial está ligada ao relacionamento geométrico entre os objetos na imagem.
A redundância psicovisual está relacionada à informação visual real ou quantificada em uma cena. Portanto, a redução ou a eliminação da redundância psicovisual, leva necessariamente a um processamento com perdas.
As principais técnicas de compressão de imagem podem ser classificadas, como apresentadas na Figura 1, a, b.
Compressão de dados sem perdas é o método de compressão que permite a recuperação exata dos dados originais após o processo de descompressão.
Algumas aplicações exigem que o processo de compressão e descompressão seja livre de perdas de informação: imagens médicas digitais , transmissão de textos e imagens binárias de fac-símile, textos, programas executáveis, banco de dados etc. Em imagens médicas, se há perdas de informação após a descompressão, há comprometimento na precisão do diagnóstico. No caso de documentos de fac-símile, a exigência é de caráter legal etc.
Os algoritmos de compressão de dados sem perdas são divididos, basicamente, em duas categorias: os métodos baseados em dicionário ou universal e os métodos estatísticos. Os métodos baseados em dicionário ou universal geram um arquivo comprimido contendo códigos de comprimento fixo, normalmente, com 12 a 16 bits, onde cada código representa uma seqüência particular de valores dos dados originais, não necessitam do conhecimento da freqüência com que os símbolos fonte ocorrem na informação original (conhecimento estatístico).
Os métodos estatísticos utilizam códigos de comprimentos variáveis. Os dados na informação original que aparecem com maior freqüência são representados por palavras-código menores, enquanto os dados de menor incidência são representados por palavras-código maiores.
Podemos afirmar que numa imagem há redundância de informação entre os pixels vizinhos e, consequentemente, o valor de cada pixel pode ser predito por sua vizinhança.
A codificação preditiva visa eliminar a redundância interpixels presente na informação original, codificando somente a diferença ou resíduo entre o valor do pixel original e o valor predito para este pixel.
A Modulação por Código de Pulso Diferencial (Differential Pulse Code Modulation - DPCM) é o método que utiliza a soma do valor do pixel predito com o valor do resíduo para obter o valor do pixel original.
Quando o valor predito se aproxima do valor do pixel original, obtém-se um resíduo pequeno permitindo uma codificação, através de um código de comprimento variável, com menos bits para o resíduo do que se a codificação fosse feita diretamente sobre o valor do pixel original (normalmente 8 bits), possibilitando, assim, o processo de compressão .
A codificação preditiva tem fundamental importância nos padrões de compressão para imagens: JPEG (Joint Photographics Experts Group), JBIG(Joint Binary Image Experts Group) e MPEG ( Motion Picture Experts Group).
A adoção de padrões está relacionada com a necessidade de operacionalidade entre os equipamentos dos diversos fabricantes.
O desenvolvimento e a adoção dos principais padrões de compressão de imagens, em uso atualmente, são baseados em algumas técnicas de compressão de imagens apresentadas na Figura 1 a , b .
Os padrões de compressão para imagens binárias, em tons de cinza ou coloridas, estáticas ou dinâmicas, em muitos casos, foram desenvolvidos e sancionados pela International Standards Organization (ISO) e o Commité Consulatif International des Téléphonique et Télégraphique (CCITT) atualmente denominado International Telecommunication Union (ITU-T).
JPEG é um acrônimo de Joint Photographic Experts Group que é o nome original do comitê que escreveu o padrão. Esse padrão é a junção de esforços de três das maiores organizações de padronização do mundo: ISO, CCITT e o IEC (International Electrotechnical Commission).
O padrão JPEG foi desenvolvido para comprimir imagens paradas, em tons contínuos de cinza ou de cor, de cenas do mundo real e imagens naturais, não tendo um bom desempenho em imagens que apresentem descontinuidades nas cores ou nos tons de cinza.
O padrão JPEG apresenta quatro modos de operação: JPEG com perdas ou JPEG - DCT (Joint Photographic Experts Group - Discrete Cosine Transform), JPEG sem perdas ou JPEG - DPCM (Joint Photographic Experts Group - Differential Pulse Coding Modulation), modo Progressivo e o modo Hierárquico.
Normalmente, quando há referência ao padrão JPEG trata-se do JPEG - DCT cujo grau de qualidade e velocidade de descompressão podem ser variados de acordo com os parâmetros da compressão. Isso significa que o tamanho do arquivo da imagem em processamento pode ser regulado de acordo com a qualidade final da imagem desejada.
Tipicamente para imagens coloridas, o padrão JPEG obtem taxa de compressão entre 10:1 a 20:1 sem perdas visíveis, taxas de 30:1 a 50:1 com pequenos defeitos na imagem, enquanto para uma qualidade muito pobre da imagem pode ser obtida taxa de compressão de até 100:1.
Para imagens em tons de cinza, não se obtém taxas tão altas de compressão devido aos olhos humanos serem mais sensíveis à variação do brilho do que à variação de tonalidade; com isso o limite da taxa de compressão sem perdas visíveis fica em torno de 5:1. Num processo repetido de compressão e descompressão as perdas na imagem são cumulativas.
Como visto, o padrão JPEG só é especificado para imagens paradas. Contudo, freqüentemente ouve-se referências ao motion JPEG ou MJPEG para vídeo. Vários fabricantes e vendedores de equipamentos médicos têm aplicado JPEG aos quadros de uma seqüência de vídeo chamando o resultado de MJPEG.
Para imagens em movimento, o padrão de compressão/descompressão reconhecido é o MPEG (Motion Picture Experts Group), o qual utiliza muito das técnicas do JPEG além de explorar a redundância inter-quadros, geralmente, presente em uma seqüência que forma o movimento, elevando a taxa de compressão em torno de três vezes, se comparado ao método MJPEG para semelhante qualidade da imagem, mas com o inconveniente de requerer muitos buffers de quadro.
Enquanto isto, o JPEG não necessita de nenhum buffer de quadro, pois processa cada quadro independentemente apresentando grande simetria, em termos de complexidade, entre os codificadores e decodificadores. Por esta razão, algumas aplicações requerendo seqüências em movimentos usam JPEG, mesmo perdendo em taxa de compressão.
O método de compressão JPEG sem perdas ou JPEG - DPCM é completamente independente do método JPEG - DCT. O método sem perdas utiliza a codificação preditiva para formar os resíduos que são codificados com um código de comprimento variável: Huffman ou Aritmético.
A alta correlação interpixels para as imagens típicas é modelada por uma função de co-variância bidimensional, [4], que decai rapidamente para distâncias superiores a 8 pixels. Isso implica em não haver vantagem em utilizarmos mais do que 8 pixels da vizinhança para efetuar uma predição, porém na prática o padrão JPEG sem perdas utiliza um, dois ou até três pixels vizinhos para efetuar sua predição dependendo da posição da linha ou da coluna, a que o pixel pertence dentro da imagem.
O esquema apresentado na Figura 2 , representa um determinado pixel "Px, y" e sua vizinhança, a qual determinará o seu valor predito," f( ) ", que subtraído do próprio valor original, "Px, y", fornecerá o resíduo, "r", que será codificado com um código de comprimento variável; tal que: r = Px, y - f( ).
Para cada pixel "Px, y", o padrão JPEG - DPCM utiliza uma combinação linear do pixel da esquerda (Px , y-1), do pixel superior (Px-1 , y) e do pixel superior esquerdo (Px-1 , y-1), para calcular a sua predição.
O padrão JPEG sem perdas define oito funções de predição,Tabela 1 [17] .
A função de predição f(0) é somente reservada para a codificação diferencial no modo de hierárquico de operação .
Normalmente, a escolha da função de predição, f( ), é feita tal que a predição da imagem apresente os menores resíduos, consequentemente aumentando a taxa de compressão. Contudo, a primeira linha, a primeira coluna e o pixel P1,1 são tratados atipicamente quando da predição, pois a sua vizinhança é somente de um pixel, enquanto o primeiro pixel (P1,1) não apresenta vizinhança alguma. Os outros pixels têm dois ou mais pixels como vizinhos.
Para a primeira linha da imagem, utilizamos a função de predição f(1). Para a primeira coluna, a função de predição f(2). Para o pixel (P1,1) a função de predição [5] é 2k - kt - 1, onde "k" é o número de bits de precisão da amostragem, que na técnica JPEG pode ser um número inteiro entre 2 e 16 e "t" é um parâmetro de transformação pontual, cujo valor é, normalmente, zero, pois um valor diferente, somente desloca os bits do pixel de entrada para a direita de "kt" bits, reduzindo sua precisão.
A seguir é apresentado para imagens típicas, Figura 3a , a distribuição de probabilidade de ocorrência dos valores dos pixels e, Figura 3b , a distribuição de probabilidade de ocorrência para os resíduos.
Quando o valor da predição se aproxima do valor original, o resíduo será pequeno, Fig. 3b , e é dito de baixa entropia, podendo ser muito mais eficientemente codificado do que o pixel original, pois valores pequenos leva a comprimento dos códigos menores. Esta codificação pode ocorrer de duas formas através de um Código de Comprimento Variável: a) default JPEG Código de Huffman (categoria e magnitude do resíduo) ou, b) pela utilização do código aritmético.
A escolha entre o código de Huffman e o código aritmético não tem impacto sobre a qualidade final da imagem, mas geralmente o código aritmético produz arquivos 5 a 10% menores do que o código de Huffman, contudo o JPEG Aritmetic Coding especificado pelo padrão JPEG sem perdas é um código proprietário da IBM, AT&T e Mitsubishi não podendo ser legalmente usado sem licença destas companhias. Portanto, em virtude disto e do baixo custo computacional, o código de Huffman (categoria e magnitude do resíduo) é geralmente adotado.
A técnica de compressão sem perdas JPEG-DPCM não codifica diretamente o resíduo da diferença entre o valor do pixel original e o valor do pixel predito. Em vez disto, o resíduo é representado por um par de valores (categoria, magnitude), o primeiro determina a categoria, a qual será codificada pelo código de base (Huffman) conforme a Tabela 2 [17] . O segundo termo, a magnitude, será o valor do resíduo em binário.
Portanto, o código final para o processo de compressão será o código de base em binário, (Tabela 2 [17] ) mais os bits menos significativos do valor do resíduo, em binário, até que seja alcançado o comprimento do código apresentado na Tabela 2 [17] , para o caso do resíduo positivo, e no caso do resíduo negativo, teremos o código de base (Tabela 2 [17] ) acrescido dos bits menos significativos do "complemento de um" do módulo do valor do resíduo, sempre respeitando o número máximo de bits do código que será composta pelo código de base mais o resíduo em binário.
A seguir, Figura 4 , é apresentado em diagrama de blocos os passos do processo de codificação JPEG - DPCM.
Cada pixel da imagem entra no codificador; o preditor gera um valor baseado nas informações dos pixels anteriores de acordo com a função de predição apresentada na Tabela 1 [17] . A saída do preditor é arredondada para o valor inteiro mais próximo e assim, é usado para obter o resíduo, o qual será codificado pelo código default JPEG Huffman (categoria e magnitude do resíduo), Tabela 2 [17] .
Convém observar que o arredondamento do valor predito não causa perda no processo de descompressão uma vez que a codificação ocorre no resíduo e no processo de descompressão é utilizada, de maneira inversa, a mesma lógica de arredondamento do valor predito.
A Figura 5 apresenta em diagrama de blocos do sistema de descompressão sem perdas.
O decodificador de entropia recebe os resíduos codificados pelo código default JPEG Huffman (categoria e magnitude do resíduo), executa a operação inversa separando os valores dos resíduos das respectivas categorias. A seguir soma os valores dos resíduos decodificados aos valores da predição inteira, obtendo assim os valores dos pixels da imagem original.
A compressão de uma imagem é o processo pelo qual se consegue reduzir a quantidade de dados necessária para representar uma certa quantidade de informação pela eliminação de informações redundantes e/ou irrelevantes de acordo ao processo sem ou com perdas.
Como o valor de cada pixel da imagem original é, normalmente, representado por um byte, o processo de compressão, efetivamente, ocorre quando representamos cada pixel por uma quantidade menor de bits.
A compressão sem perdas permite a recuperação total da imagem original, contudo apresenta baixa taxa de compressão se comparada aos métodos com perdas.
A compressão sem perdas, pela aplicação da técnica JPEG-DPCM, é obtida utilizando código de comprimento variável, com o objetivo de eliminar as informações redundantes na cena, e a descompressão é, praticamente, a inversão do processo de compressão devido a simetria entre estas etapas.
O crescente uso de imagens digitais, envolvendo armazenamento e transmissão, tornou imperativo a adoção de padrões de compressão/descompressão para permitir a operacionalidade entre os equipamentos diferentes dos diversos fabricantes.
[1]Fonseca, J., N., Compressão de Imagens Médicas Digitais, Aracaju: Revista Sergipana de Medicina - RSM, janeiro de 1999. /no prelo/
[2] Moura, L. et al, Lossy Compression Techniques, Medical Images, and the Clinician, M. D. Computing, Vol.13, No. 2, 1996.
[3] Alcocer, P.,R.,C., Furuie, S.,S., Arie, S., Melo, C.,P., A DICOM Graphic User Interface For PC's: Towards a Hierarchical System for Dynamic Digital Angiographic Image Storage and Visualization, RBE - Caderno de Engenharia Biomédica, Vol.12, p.191-201, out.1996.
[4] Gonzales, R.,C., Woods R.,E.,Digital Image Processing, Addison-Wesley Publishing Company, USA, 1993.
[5] Bhaskaran, V., Konstantinides, K., Image and Video Compression Standards Algorithmos and Architectures, Kluwer Academic Pub., 1995.
[6] Huang, K., Experiments with a lossless JPEG Codec, Cornell University, 1994.
[7] JPEG image compression FAQ, part 1/2, Independent JPEG Group, April, 1998.
[8] Cyganski, D., Orr, J., A., Vaz, R., F., Information Engineering Across the Professions, Part IV, National Science Foundation and Worcester Polytechnic Institute, Febuary, 1998.
[9] Das, M., Burgett, S., Lossless Compression of Medical Images Using Two- Dimensional Multiplicative Autoregressive Models, IEEE Trans. on Medical Imaging, Vol.12, No. 4, Dec.1993.
[10] Roos, P., Viergever, M.,C.,A., Dijke, V., Peters, J., H., Reversible Intraframe Compression of Medical Images, IEEE Trans. on Medical Imaging, Vol.7, No.4, Dec.1988.
[11] Kau W., Digital Image Compression: Algorithms and Standards, Kluwer Academic Pub., 1995.
[12] Gonzales, R., C., Wintz, P., Digital Image Processing, 2nd ed, Addison-Wesley Pub., 1987.
[13] Castleman, R., K., Digital Image Processing, Prentece-Hall, Inc., 1996.
[14] Nelson, M., Gailly, J.,L., The Data Compression Book, 2nd ed., M & T Books, 1996.
[15] Smith, B., C., Rowe, L., A., Algorithms for Manipulating Compressed Images, IEEE Computer Graphics & Applications, Set, 1993.
[16] Pennebaker, W., B., Mitchell, JPEG Still Image Data Compression Standard, Van Nostrand Reinhold, 1993.
[17] Fonseca, J., N., Alcocer, P., R., C., Compressão de Imagens Médicas Utilizando a Técnica JPEG-DPCM , IV Fórum Nacional de Ciência e Tecnologia em Saúde - IV FNCTS, Curitiba, BR, 1998.
[18] Grob, B., Televisão Básica: princípios e reparação. 4a ed. Rio de Janeiro, Guanabara Dois S.A, 1983.
[19] Lindlay C., A.,Practical Image Processing In C, John Wiley & Sons, Inc., 1991.
