Compressão de Imagem Digital: Compressão de Imagem Digital Joaquim Macedo
Departamento de Informática da Universidade do Minho
Sumário: Sumário Princípios de Compressão de Imagem
Compressão de Imagem de Baixa Complexidade
Codificação de Transformada
Outras Técnicas de Codificação
Normas de Compressão de Imagem
Norma JPEG
Norma JPEG 2000
Formatos de Imagem
Princípios para Compressão de Imagem : Princípios para Compressão de Imagem Remover vários tipos de Redundâncias
Estatística
Espacial
Estrutural
Conhecimento
Psico-Visual
Tipos de Compressão: Tipos de Compressão Sem perdas
Reversível
Imagem Reconstruída = Imagem Original
Baixa taxa de compressão ( < 3:1)
Aplicações: Imagens médicas e de satélite
Com perdas
Irreversível
Imagem Reconstruída = Imagem Original+ Ruído
Taxas de compressão levadas
Diversas aplicações: WWW,....
Compressão de Baixa Complexidade: Compressão de Baixa Complexidade Codificação de Entropia
Cofidicação Run-Length
Codificação Preditiva
Codificação baseada na entropia: Codificação baseada na entropia Função densidade de probabilidade da imagem da Lena Entropia = 7.45 bits/pixel Não muito ganho Contudo quando a codificação baseada na entropia é combinada com
Outros métodos torna-se muito eficaz (veremos mais tarde)
Codificação Run-Length: Codificação Run-Length Técnica de compressão eficaz em imagem com símbolos idênticos consecutivos
Run= sequência de pixels com valores idênticos
Em vez de codificar pixel a pixel é codificado um run de cada vez
Exemplo de aplicação
Imagens FAX
Exemplo 8.1: Exemplo 8.1 Considere a codificação Run-Length duma imagem FAX cujas primeiras linhas de varrimento são mostras a seguir
ImagemFAX={11111111111000000000000000000011111111111111111
00000000000000111111111111111111110000000000000000}
Código RLC=[....11,22,17,EOL,0,14,20,16,EOL,...]
Codificação Run-Length: Codificação Run-Length
Codificação Preditiva: Codificação Preditiva Explorar a previsibilidade e regularidade dos dados
DPCM
extendido a 2D para codificar imagens
Preditores típicos
Codificação DPCM: Codificação DPCM X = 0.97* A3
X = 0.49*A3 + 0.49*A2
X = 0.9*A3 – 0.81*A1 + 0.9*A2 Similar à codificação áudio preditiva, mas extendida a 2D Predição Linear
Exemplo 8.2: Exemplo 8.2 Usando o preditor de 3ª ordem do exemplo anterior, calcule o erro da saída previsível para a seguinte imagem 4x4. Assuma a inexistência de erro de quantificação do sinal
Solução do Exemplo 8.2: Solução do Exemplo 8.2 Usar para a primeira fila e primeira coluna o preditor de 1ª ordem
Para as outras filas e colunas o de 3ª ordem 2D.
Saída DPCM calculada subtraindo a saída predita com os valores originais
Saída prevista Saída DPCM
Saída DPCM: Saída DPCM Valores predictos– assumindo que
Os valores de errro são aramzenados
exactamente Valores originais Valores de erro
Transmissor DPCM: Transmissor DPCM
Receptor DPCM: Receptor DPCM
Codificação DPCM da imagem da Lena : Codificação DPCM da imagem da Lena Error Image
Codificação de Transformada: Codificação de Transformada Unitária
De Bloco
Wavelet
Comparação DCT e DWT
Transformada Discreta de Fourier 2-D : Transformada Discreta de Fourier 2-D
Imagem da Lena e o seu espectro: Imagem da Lena e o seu espectro
Esquema de Codificação de Transformada: Esquema de Codificação de Transformada Transformada Inversa 2-D Desquantificador Descodificador de Entropia Receptor Canal Imagem de
Entrada Imagem Reconstruída
Quantização e Codificação: Quantização e Codificação A quantificação, alocação de bits e codificação deve ser feita com cuidado para se conseguir um bom desempenho de compressão.
O principal objectivo é minimizar o erro quadrático médio da imagem reconstruída.
Dependendo das características estatísticas dos coeficientes da transformada, pode ser usado um quantificador não uniforme.
Contudo, conceber tal quantificador pode ser difícil pelo facto de ser dependente dos dados.
Na maioria dos casos, para quantizar os coeficientes de transformada é usado um quantificador não uniforme fixo.
Os coeficientes quantizados são então codificados usando codificação baseada na entropia.
Transformada unitária: Transformada unitária As transformadas não unitárias
têm uma capacidade muito boa de compactação da energia
As transformadas unitárias
Para além da compactação da energia, tem propriedades muito úteis nas aplicações de codificação de imagens
A energia total no domínio da frequência é igual à energia total no domínio espacial
O MSE de quantificação é igual ao MSE da reconstrução
TU: Propriedades mais importantes: TU: Propriedades mais importantes Energia total no domínio da frequência é igual à energia total
no domínio espacial (Teorema de Parseval) ii) O MSE na reconstrução é igual ao MSE da quantização
Transformada Óptima: Transformada Óptima Há muitas transformadas de imagem
É necessário encontrar a que tem máximo desempenho de compressão
A que elimina completamente a correlação dos dados de imagem de entrada
Matriz de auto-correlação é diagonal
Empacota os dados de entrada num pequeno número de coeficientes
Se calcularmos a energia dos primeiros L coeficientes para várias transformadas
A óptima tem máxima energia
Transformada Óptima: Transformada Óptima A transformada unitária que satisfaz os 2 critérios é a Karhunen-Loeve (KLT)
A KLT é
Dependente da imagem
Tem complexidade computacional alta
Na prática, usam-se transformadas sub-óptimas
DFT, DCT
Baixa complexidade computacional
Que Transformada? : Que Transformada?
Transformada Discreta do Coseno: Transformada Discreta do Coseno
Transformadas sub-óptimas DCT : Transformadas sub-óptimas DCT DCT
Desempenho da taxa de distorção
Próximo da KLT
Para imagens naturais que têm uma taxa alta de correlação
DCT é virtualmente não distinguível da KLT
Tem uma concretização eficiente
Como a DFT
Complexidade O(N logN) para transformadas de N pontos
Ao contrário da DFT
Evita a geração de dos componentes espectrais falsos nas arestas
Transformadas sub-óptimas DCT: Transformadas sub-óptimas DCT Foi adoptado como núcleo para as normas de codificação de imagem e vídeo
JPEG, MPEG, H.261
DCT da sequência Nx1
está relacionada com a DFT da sequência 2N-1 impar simétrica
Devido a esta relação o sinal reconstruído a partir dos coeficientes DCT preserva melhor as arestas
Exemplo 8.4: Exemplo 8.4 Considere um sinal com oito pontos [ 0 2 4 6 8 10 12 14].
Calcule a DFT e a DCT do sinal
Para compressão do sinal ignore os três coeficientes mais pequenos das 2 transformadas e reconstrua o sinal.
Compare os resultados.
Solução do Exemplo 8.4: Solução do Exemplo 8.4 0 2 4 6 8 10 12 14 20 –13 0 -1 0 0 0 0 20 7 4 3 3 3 4 7 20 7 4 0 0 0 4 7 20 –13 0 -1 0 0 0 0 3 0 4 7 7 10 14 11 0 2 4 6 8 10 12 14 DFT DCT Sinais Reconstruídos Sinal Original
Solução do Exemplo 8.4: Solução do Exemplo 8.4 Preservação dos contornos
A DCT preserva mehlor os contornos que a DFT.
Transformada de Bloco: Transformada de Bloco DCT e DFT
Eficientes para explorar a natureza de baixa frequência da imagem
Maior desvantagem
As funções de base são muito longas
Quantificação dos coeficientes são visíveis em toda a imagem
Pouco importante para os coeficientes de LF codificados com precisão
Afecta a qualidade das arestas na imagem recosntruída, porque os coeficentes HF são codificados grosseiramente
Desvantagens da Transformada de Fourier: Desvantagens da Transformada de Fourier As transformadas de Fourier e derivadas disponibilizam uma boa compactação da energia.
Contudo, a maior desvantagem destas transformadas e que as funções de base são muito longas.
Então, se o coeficiente da transformada é quantizada, o efeito é visível através da imagem.
Isto é especialmente verdadeiro para os coeficientes de alta frequência que são quantizados de forma grosseira.
Um contorno escarpado de uma imagem é representado por muitos coeficientes da transformada da alta frequência.
Quando os coeficientes de alta frequência são quantizados de forma grosseira, os contornos não são reconstruídos de forma apropriada reconstrução pobre da imagem.
Transformada de Bloco: Transformada de Bloco Uma aresta viva na imagem
Representada por muitos coeficientes da transformada
Uma imagem é um sinal não estacionário
Diferentes partes da imagem têm diferentes propriedades estatísticas
Se a transformada for calculada sobre toda a imagem a não estacionaridade é perdida
Para minimizar o impacto das tuas desvantagens, são usadas geralmente técnicas de codificação de bloco.
Transformada de Bloco: Transformada de Bloco
Normalmente
Implementações de DFT e DCT trabalham por blocos de 8x8 ou 16x16
Cada bloco é transformado, quantificado e codificado separadamente
Efeito de quantificação limitado ao bloco
Menor complexidade computacional
Exemplo: Cálculo da Complexidade: Exemplo: Cálculo da Complexidade Considere uma imagem a 512x512.
Calcule a complexidade dum cálculo duma DFT 2-D usando o método radix-2 da FFT.
Divida a imagem e blocos 8x8.
Calcule a complexidade do cálculo 2-D DFT calculation para todos os blocos.
Compare as duas complexidades.
Cálculo da Complexidade: Cálculo da Complexidade Complexidade N x N DFT = Complexidade 2N, N-point 1-D DFT
= operações butterfly
= operações butterfly
2-D Block Transform = 2.4 x 106 butterfly quando N=512
Se a imagem é dividida em blocos de 8x8, há 4096 blocos.
Complexdade da DFT 2-D para cada bloco 8x8 = 192 operações.
Complexidade global = 4096*192 =0.79 x 106 operações butterfly .
Comentários
A transformada de bloco reduz a complexidade para 1/3.
DFT 2-D da imagem inteira (512x512)
Transformada de Bloco: Transformada de Bloco
Transformada de Bloco Desvantagens: Transformada de Bloco Desvantagens Estrutura em blocos visível na imagem
Fenómeno de Gibbs
Perda de contraste quando os coeficientes de alta frequência têm erros de quantificação
Limite superior na taxa de compressão
Necessidade dum termo DC de alta resolução e coeficientes de baixa frequência por bloco
Transformadas Wavelet: Transformadas Wavelet Tornaram-se bastante populares no processamento de imagens
São eficientes na representação de sinais não estacionários
Janela adaptável tempo-frequência
Alta descorrelação e compactação de energia
Redução dos artefactos do bloco e ruído do mosquito (efeito de Gibbs)
As funções de base para wavelet adaptam-se ao sistema visual humano
Transformadas Wavelet: Transformadas Wavelet Unitárias ou não Unitárias
Unitárias permitem taxa de compressão superior
Decomposição Wavelet
Dyadic: só a baixa escala é decomposta recursivamente
Regular: decomposição completa
Irregular
Tamanho da árvore de decomposição depende de
Tamanho da imagem
Número de derivações de filtros wavelet
Decomposição eficiente
Nº de filas e colunas da banda >= ao nº de derivações de filtros
Decomposição Wavelet: Decomposição Wavelet
DWT:Decomposição de imagens: DWT:Decomposição de imagens Escala 1
4 sub-bandas
Cada coeficiente
Corresponde a uma área 2*2 na imagem original
Baixas Frequências
Altas Frequências:
DWT:Decomposição de imagens: DWT:Decomposição de imagens Escala 2
4 sub-bandas
Cada coeficiente
Área 2x2 da imagem na escala 1
Baixas frequências
Altas Frequências
Num nível de escala mais
grosseira, os coeficientes
representam uma maior
área espacial mas uma menor
gama de frequência
DWT:Decomposição de imagens: DWT:Decomposição de imagens Pais
Filhos
Descendentes
Coeficientes correspondentes a escalas mais finas
Ascendentes
Coeficientes correspondentes a escalas mais grossas Dependências pai-filho de sub-bandas: setas entre
sub-bandas dos pais para sub-bandas dos filhos
DWT:Decomposição de imagens: DWT:Decomposição de imagens Característica 1
Distribuição da energia similar a outras CT
Concentrada nas BF
Característica 2
Auto-similaridade espacial entre sub-bandas A ordem de varrimento das sub-bandas
para codificação do mapa
características significativas.
Quantização: Quantização Baixa compressão
Taxa de bits alta Alta Compressão
Taxa de bits baixa
Fdp dos coeficientes wavelet: Fdp dos coeficientes wavelet Fdp da banda HH para os coeficientes da imagem da Lena imag
Desempenho da Compressão: Desempenho da Compressão A entropia da banda HH da imagem da Lena = 3.67 bits/pixel.
Se esta banda for codificada sem quantização, pode ser conseguida uma relação de compressão de 2.2:1 (relativamente à taxa PCM de 8 bits/pixel)
Se os coeficientes forem quantificados com um tamanho de passo de 8 a entropia decresce ainda mais 0.86 bits/pixel C.R.= 9.3:1.
O desempenho base de compressão num esquema de codificação de transformada é conseguido reduzindo a entropia global dos ecoeficientes quantizando os coeficientes passa alto.
DWT versus DCT: DWT versus DCT DCT
Anomalias nas arestas
Muitos coeficientes a zero e energia insignificante
Muitos bits para a tendência, o normal, poucos bits para “anomalias”
Problemas na codificação a débitos muito baixos: artefatos de bloco
DWT
Disponível tanto a informação do normal como das anomalias
Dificuldade principal: coeficientes de detalhe fino nas anomalias conduz a um maior nº de coeficientes
Problema: como representar eficientemente a informação de posição?
DCT versus DWT: DCT versus DWT Sãos as 2 transformadas mais importantes na codificação de imagens
Embora possam parecer diferentes, há algumas similaridades.
Exemplo 8.6: Exemplo 8.6 Considere a imagem da Lena 512x512. Divida a imagem em blocos não sobrepostos 8x8.
Calcule o DCT de cada bloco e a energia média do componente DC e 63 coeficientes AC.
Decomponha a imagem em 3 estágios usando a wavelet Daub-4. Calcule a energia média das banda passa-baixo e da nona passa-lato
Compare os dois conjuntos de energias
Comparação do DCT e DWT : Comparação do DCT e DWT Coeficientes DCT rearranjados em bandas de igual frequência Coeficientes DWT
Primeiras 4 bandas: Primeiras 4 bandas
Compactação da energia no DCT: Compactação da energia no DCT Lena 512x512, blocos DCT 8x8
Compatação da Energia no DWT: Compatação da Energia no DWT Daub-4, 3 stages, Lena 512x512
DCT versus DWT Compactação da Energia: DCT versus DWT Compactação da Energia 1057 70.9 42.2 11.3 15.7 26.4 11.1 8.4 5.4 3.4 DCT DWT Média da raiz quadrada da média da energia (RMSE)
Outras Técnicas de Codificação: Outras Técnicas de Codificação Vector de Quantificação
Compressão de Imagem com Fractais
Vector de Quantização: Vector de Quantização A imagem é segmentada em blocos de pixels (2x2, 4x4, 8x8)
O codificador atribui uma etiqueta para bloco.
A etiqueta é armazenada na imagem compactada em vez do bloco.
Uma vez que a etiqueta necessita menos bits para ser representada, pode-se
conseguir uma compressão superior.
Tanto o codificador como o descodificador usam um dicionário
para gerar etiquetas.
Vectores de quantização Esquema simplificado: Vectores de quantização Esquema simplificado wxyz wxyz wxyz wxyz ... Livro de código N K wxyz wxyz wxyz wxyz ... Livro de código N K Vector de
Entrada Regra do
Vizinho mais
próximo Tabela de
Lookup Canal Etiqueta i Vector
Reconstruído
Livro de Códigos Universal : Livro de Códigos Universal Se gerar o livro de código para cada imagem, tem que se enviar o
Livro de código juntamente com a imagem A taxa de bits aumenta Solução? Usar um livro de códigos Universal Seleccionar um número grande de imagens, e divide-as em blocos. Gere um livro de código de tal forma que minimize o MSE geral sobre a imagem.
Compressão de Imagens por Fractais: Compressão de Imagens por Fractais Fractal
é uma imagem duma textura ou forma expressa como uma ou mais fórmulas matemáticas
Forma geométrica cujos detalhes irregulares ocorrem em diferentes escalas e ângulos que podem ser descritos por transformações fractais.
A compressão baseada em fractais
determina um conjunto de fractais que descrevam ou representem uma imagem digital
Dependente da imagem e complexa computacionalmente
Concretizações muito rápidas em hradwrae
Complexidade assimétrica
Mais complexa a codificação
Limitações: Limitações A codificação fractal é dependente da imagem
Para cada imagem, é especificado um conjunto distinto de regras
A codificação fractal é também uma técnica computacionalmente intensivo.
Contudo, as computações necessárias são iterativas e tornam possível concretizações hardware de altamente eficiente.
Codificação fractal é altamente assimétrico
-- Complexidade do descodificador << Complexidade do descodificador
Normas para Compressão de Imagens: Normas para Compressão de Imagens
Normas de Compressão de Imagens: Normas de Compressão de Imagens Imagens 2-níveis (Preto e Branco): MH Fax Coder
MREAD Fax Coder
JBIG-1 Standard (1980+)
JBIG-2 Standard (1990+) Níveis de cinzento/Imagens a cores : JPEG
JPEG-2000
Normas Fax MH e MREAD : Normas Fax MH e MREAD Codificador Fax MH : Usa o Run Length Coding 1-D
Fornece uma compressão 20:1 em documentos de texto simples Codificador Fax MREAD : Usa o Run Length Coding 2-D(25% melhoria relativo ao MH) Os codificadores Fax MH e MREAD Fax Coder não têm bom
desempenho para texto escrito à mão e imagens contínuas
Introdução ao JPEG O contexto: Introdução ao JPEG O contexto JPEG são as iniciais de Joint Photographic Expert Group, formado em 1986
O Grupo desenvolveu a norma de compressão JPEG para disponibilizar qualidade alta de compressão para imagens em tons de cinzento e a cores.
É necessário um método de compressão de imagens normalizado para permitir a inter-operação entre máquinas de diferentes fabricantes.
É a primeira norma de compressão internacional para imagens de tom contínuo (preto e branco ou a cores).
Introdução ao JPEG Qual é o objectivo?: Introdução ao JPEG Qual é o objectivo? “muito boa” ou “excelente”
Taxa de compressão, qualidade da imagem reconstruída e débito de transmissão
Ser aplicável a praticamente qualquer éspecie de imagem digital de tom contínuo
Nível bom de complexidade
Ter os seguintes modos de operação
Codificação sequencial
Codificação progressiva
Codificação sem perdas
Codificação hierárquica
Esquema do Codificador JPEG : Esquema do Codificador JPEG DCT (Transformada Discreta do Coseno)
Quantização
Varrimento Zigzag
DPCM no componente DC
RLE nos componentes AC
Codificação de Entropia DCT Quantizer Entropy Coder compactada Quantization Table VLC Table DCT Quantizador Codificador de entropia Cadeia de bits Quantização Tabela VLC Tabela Imagem Original Blocos 8x8
Dados de Entrada 8x8: Dados de Entrada 8x8 Gama dinâmica = [0, 255], Média=~ 128
Dados de entrada -128: Dados de entrada -128
Coeficientes 8x8 DCT: Coeficientes 8x8 DCT
Matriz de Quantização: Matriz de Quantização F'[u, v] = round ( F[u, v] / q[u, v] ).
Exemplo: 101101 = 45 (6 bits).
q[u, v] = 4 --> Truncate to 4 bits: 1011 = 11.
Matriz de Quantização: Matriz de Quantização Tabela de luminância Q. Tabela de Crominância Q.
Coeficientes Quantizados: Coeficientes Quantizados Coeficientes DC Coeficientes AC
Varrimento Zigzag: Varrimento Zigzag [-496 22 132 56 24 -10 0 0 0 14 EOB] [ -31 2 11 4 2 -1 0 0 0 1 EOB ]
Codificação dos coeficientes quantizados: Codificação dos coeficientes quantizados Differential Pulse Code Modulation (DPCM) para componente DC O componente DC é grande e variado, mas amiúde próximo do valor
precedente
Codifique a diferença dos blocos 8x8 prévios -- DPCM Run Length Encode (RLE) para componente AC O vector 1 x 63 vector tem grande número de zeros
Guarde o salto e o valor, onde salto é o número de zeros e o valor o próximo componente diferente de zero
Envie (0,0) como valor que indica fim de bloco.
Coeficientes dequantizados: Coeficientes dequantizados
Coeficientes DCT Inversos: Coeficientes DCT Inversos
Coeficientes + 128: Coeficientes + 128
Erros nos pixéis reconstruídos: Erros nos pixéis reconstruídos Erro = Original – Reconstruído
Imagens JPEG – Lena a níveis cinzento: Imagens JPEG – Lena a níveis cinzento 0.9 bpp 0.56 bpp 0.25 bpp 0.13 bpp 0.37 bpp
Imagens JPEG – Lena a cores: Imagens JPEG – Lena a cores 0.95 bpp 0.53 bpp 0.18 bpp 0.36 bpp
Desempenho Típico do JPEG: Desempenho Típico do JPEG
Deficiências do JPEG: Deficiências do JPEG Fraco desempenho a baixa taxa de bits (<0.25 bpp)
Não eficiente na compressão imagens contínuas ou de dois níveis
Falta de protecção dos direitos de autor das imagens
Falta de robustez a erros de bits
Norma JPEG-2000 : Norma JPEG-2000
Funcionalidades do JPEG-2000: Compressão com perdas a sem perdas numa única cadeia de código
Codificação dinâmica/estática de regiões de interesse com alta
qualidade
Codificação resistente a erros
Escabilidade espacial e da qualidade
Descrição baseada no conteúdo Funcionalidades do JPEG-2000
Esquema do Algoritmo JPEG2000: Esquema do Algoritmo JPEG2000
Coeficientes de Filtros de Análise e Síntese: Coeficientes de Filtros de Análise e Síntese Le Gall 5/3
Coeficientes de Filtro Daubechies 9/7: Coeficientes de Filtro Daubechies 9/7
Sub-bandas e Códigos de Bloco: Sub-bandas e Códigos de Bloco
Plano de bits no JPEG-2000 : Plano de bits no JPEG-2000
Contribuições código de blocos JPEG2000: Contribuições código de blocos JPEG2000
Qualidade subjectiva das imagens em JPEG2000 – Nível de cinzento: Qualidade subjectiva das imagens em JPEG2000 – Nível de cinzento 0.90 bpp 0.56 bpp 0.37 bpp 0.25 bpp 0.13 bpp JPEG 0.13 bpp
Qualidade objectiva das imagens JPEG2000: Qualidade objectiva das imagens JPEG2000 Imagem a nível de cinzento Imagem da Lena a Cores