SM Aula 8 v3

50 %
50 %
Information about SM Aula 8 v3
Entertainment

Published on December 28, 2007

Author: VolteMort

Source: authorstream.com

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

Add a comment

Related presentations

Related pages

go.padsdel.com

Hier sollte eine Beschreibung angezeigt werden, diese Seite lässt dies jedoch nicht zu.
Read more

Adicinando item shop v3 - YouTube

Adicinar itens shop v3 daldegam. Skip navigation ... Video Aula Instalando WebShop V3.1 Daldegam - Duration: ... Jonathan Oliveira 3,455 views 8.
Read more

Rom Galaxy S5 SM-G900M 4.4.2 [No Bloatware] - YouTube

Rom Galaxy S5 SM-G900M 4.4.2 [No Bloatware] ... ROM REVOLUTION S6 V3 PARA S5 G900M G900F G900T G900W8+ - Duration: ... Vídeo Aula - Instalando ...
Read more

ID.net Game Center

Game center at ID.net! Discover the best online games by playing various car games, dress up games, shooting games, strategy games
Read more

www.adnetworkperformance.com

www.adnetworkperformance.com
Read more

Google

Advertising Programmes Business Solutions +Google About Google Google.com © 2016 - Privacy - Terms ...
Read more

mapmyuser.com Realtime Visitor analytics | Mapmyuser

mapmyuser.com Stats (24 Users Online) Menu. Overview; Live visitors; Big Map; Top Pages; Source; History; Share This Stat. Stats Overview. Current Online ...
Read more