TEMA 5
5.Tiposde Media II
Formatos. Normas. Compressão. Armazenamento. Distribuição
- Comente a seguinte afirmação: “Existem várias técnicas de compressão de informação, que são escolhidas e combinadas por questões de eficiência, de acordo com as características da informação a ser comprimida e, eventualmente, das características perceptuais humanas”. Dê três exemplos: um de uma escolha de uma técnica a depender do tipo de informação, outro a depender também de aspectos perceptuais, e outro da combinação de técnicas no mesmo formato. Justifique e indique em cada exemplo as técnicas onde há ou não perdas. (2010)
Comentário: A frase está correcta porque existem várias técnicas de compressão e o algoritmo que é escolhido depende das características da informação.
1: A codificação de Huffman funciona bem quando sei a aprobabilidade e quando a distribuição estatística não é uniforme.
2: RLE - funciona bem com sequências, por exemplo, da mesma tonalidade cor. (permite que qualquer sequência de caracteres reptidos possa ser substituída por uma forma abreviada permitindo comprimir qualquer cacracter que surja de forma repretitiva para além de 0(zeros) e espaços).
3: A codificação artitmética aproxima mais da entropia e normalmente é misturada com outras técnicas.
LZW - Baseada em dicionários - é boa para sequências que aparecem mais do que uma vez.
Aspectos perceptuais -
- A sequência de compressão JPEG pode ser resumidamente descrita como: segmentação da imagem em blocos / forward Discrete Cosine Transform / quantização / codificação de entropia. Onde se encontram as “perdas” no esquema de compressão com perdas JPEG?
a compressão JPEG é uma compressão com perdas, o que lhe permite, apesar de uma perda de qualidade, um das melhores taxas de compressão (20: 1 a 25:1, sem perda notável de qualidade).
Este método de compressão é muito mais eficaz em imagens fotográficas (que comportam numerosos pixéis de cores diferentes) e não em imagens geométricas (ao contrário da compressão LZW), porque nestas últimas as diferenças de matizes devidas à compressão são muito visíveis.
As etapas da compressão JPEG são as seguintes :
- Amostragem da crominância, porque o olho não pode distinguir diferenças de crominância num quadrado de 2x2 pontos
- Corte da imagem em blocos de 8x8 pontos, e seguidamente a aplicação da função DCT (Discrete Cosinus Transform, transformação discreta em cossenos) que decompõe a imagem em soma de frequências
- Quantificação de cada bloco, ou seja, aplica um coeficiente de perda (que permite determinar o rácio dimensão/qualidade) que “anulará” ou diminuirá valores de elevadas frequências, para atenuar os detalhes percorrendo o bloco inteligentemente com uma codificação LAN (em zig-zag, para retirar um máximo de valores nulos).
- Codificação da imagem (codificação de entropia) seguidamente compressão com o método de Huffman. Extraído de:( https://pt.kioskea.net/contents/video/jpeg-jpg.php3 )
- Por que as perdas são usualmente negligenciáveis?
Porque perde a informação que é irrelevante à percepção humana (não são aparentes ao sistema visual/auditivo humano).
- JPEG: Porque razão é um formato aconselhado para imagens fotográficas?
O JPEG utiliza uma tecnica de compressão com perdas baseada em transformadas. As imagens naturais digitalizadas pela maquina fotografica apresentam variações contínuas de tonalidade e por isso ao serem comprimidas com esta técnica fá-lo de forma mais eficiente porque a informação que é descartada é irrelevante para a percepção humana.
- JPEG: O que caracteriza a fase de quantização nesta compressão? O que deve ser feito a este nível para optimizar a taxa de compressão com o mínimo de perda de qualidade? Justifique.
A fase de quantização aplica um coeficiente de perda (que permite determinar o rácio dimensão/qualidade) que “anulará” ou diminuirá valores de elevadas frequências, para atenuar os detalhes percorrendo o bloco inteligentemente com uma codificação LAN (em zig-zag, para retirar um máximo de valores nulos).
A familía de formatos MPEG baseiam os seus codecs aplicando a tecnica de codificação interframe (compresão temporal) e a tecnica de codificação por transformadas (DCT- discrete cosin transform). (A DCT faz uma transformação na imagem, mudando o domínio de representação da mesma. Este processo não introduz perdas de qualidade na imagem, sua utilização se dá porque ela permite uma representação mais compacta da imagem, facilitando a compressão.-wikipedia) O maior problema da codificação interframe é a dificuldade de implementação de edição e do acesso aleatório, pois cada trama depende de outra.
Também contemplam a codificação de áudio e a combinação de fluxos de áudio e vídeo.
O MPEG permite que certas tramas sejam codificadas independentemente e que sejam utilizadas como ponto de acesso à sequência (entry points). A reprodução em tempo real é mais simples do que a codificação. (formatos mais utilizados MPEG-1 e MPEG-2)
- Indique princípios e técnicas que o MPEG-1 introduz para lidar com compressão de imagens em movimento (quando comparado com compressões “simples” de imagens baseadas em JPEG, por exemplo M-JPEG)? (2010)
O MPEG-1 permite codificar um vídeo graças a várias técnicas :
- Intra coded frames (Frames I, correspondente a uma codificação interna): as imagens são codificadas separadamente sem fazer referência às imagens precedentes
- Predictive coded frames (frames P ou codificação preventiva): as imagens são descritas por diferença em relação às imagens precedentes
- Bidirectionally predictive coded frames (Frames B): as imagens são descritas por diferença em relação à imagem precedente e à imagem seguinte
- DC Coded frames: as imagens são descodificadas fazendo médias por bloco
M-JPEG- é um codec baseado no JPEG , uma norma para a compressão de imagem (estática) que pode ser utilizada para comprimir vídeo digital atraves do tratamento independente de cada trama como uma imagem separada (comprime e guarda cada frame em vez de registar apenas as diferenças entre uma frame e a seguinte)- compressão do tipo intraframe. Permite a compressão e descompressão de imagens de resolução média 640X480 pixéis
Desvantagem: Necessita de mais espaço de armazenamento do que um ficheiro MPEG (tem um data rate mais elevado do que o MPEG)
Vantagem: Mais eficiente do que o MPEG quando existem mudanças rápidas de imagens, ficando facilitado o processo de edição pois é mais simples reordenar as tramas e reproduzir a sequencia de vídeo em movimento invertido ou a taxas variáveis.
- Que tipos de frame são definidos pela norma MPEG-1 e em que consistem? Qual a razão da sua existência?
- Que tipos de frame são definidos na norma de compressão MPEG-1 (e o que significam)?
MPEG-1 engloba um conjunto de normas para compressão de vídeo digital foi desenvolvido para ser utilizado com o formato VideoCD
Surgimento de "blocos" que podem degradar a qualidade da imagem em particular se existirem mudanças abruptas de imagem entre frames sucessivas ou se existirem alterações súbitas de cor.
Uma fonte de informação produz símbolos estatisticamente independentes de um alfabeto de oito letras, s1 ... s8 com probabilidades 1/16, 1/8, 1/4, 1/8, 1/8, 1/8, 1/8 e 1/16 respectivamente. (2010)
a) Use a codificação de Huffman para determinar um código binário para a saída.
s1: _______ s2: _______ s3: _______ s4: _______ s5: _______ s6: _______ s7: _______ s8: _______
b)Determine o número médio de dígitos binários n por cada letra de origem. Este valor deverá ser maior, menor, ou igual ao valor da entropia para este alfabeto? Justifique (sem calcular a entropia).
c)Uma representação uniforme para o código seria: {000, 001, 010, 011, 100, 101, 110, 111}. Por qual optaria (alínea a ou c) para situações em que a fonte tivesse as caracxterísticas descritas no início da pergunta? Justifique.
d)Quais as consrquências de usar o código determinado na alínea a) numa situação em que as probabilidades de ocorrência dos símbolos fosse diferente? (por exemplo numa língua diferente). Justifique.
Se o código tiver probabilidades diferentes mas na mesma ordem é excelente porque optimiza. Se forem diferentes (ou se inverter as probabilidade) posso gerar códigos maiores.
Uma fonte de informação produz símbolos estatisticamente independentes de um alfabeto de oito letras, Si :1, 2,…,8 com probabilidades 1/16, 1/16, 1/8, 1/8, 1/4, 1/4, 1/16 e 1/16.
a) Use a codificação de Huffman para determinar um código binário para a saída.
s1: _______ s2: _______ s3: _______ s4: _______ s5: _______ s6: _______ s7: _______ s8: _______
b)Determine o número médio de dígitos binários n por cada letra de origem.
c)Quais as vantagens do código de Huffman?
Técnica de compressão sem perdas – codificação de comprimento variável. A compressão seguida de descompressão preserva integralmente os dados.
Considere uma fonte com alfabeto {a1; a2; a3; a4; a5} onde a probabilidade
dos símbolos é: p1 = 0,125; p2 = 0,25; p3 = 0,5; p4 = 0,0625; p5 = 0,0625
a) Proponha um código de Huffman para esta fonte.
a1: __________ a2: __________ a3: __________ a4: __________ a5: __________
b) Determine o comprimento médio de cada símbolo de origem.
c) Calcule a entropia da fonte.
h =
___________________________________________________________________
Nota: log2 (1/16) = -log2 (16) = -4, log2 (1/2) = -1, log2 (1/8) = -3, log2 (1/4) = -2
d) Qual deve ser maior, a entropia ou o comprimento médio dos símbolos calculado em b)? Justifique.
A entropia é o valor mínico teórico para a dimensão média de cada símbolo.
Considere uma fonte com alfabeto {a1; a2; a3; a4; a5; a6} onde a probalilidade dos símbolos é: p1 = 0,125; p2 = 0,25; p3 = 0,25; p4 = 0,25; p5 = 0,0625; p6 = 0,0625
a) Calcule um código de Huffman para esta fonte.
a1: _______ a2: _______ a3: _______ a4: _______ a5: _______ a6: _______
b) Calcule a dimensão esperada (média) dos códigos (codeword) para o código de
Huffman anterior.
c) Calcule a entropia da fonte.
h = _______________________________
Nota: log2 (1/16) = -log2 (16) = -4
d) A entropia h deverá ser maior ou menor que o comprimento dos códigos (codeword length) calculados ?
Se fosse adoptada uma codificação aritmética, esperaria que o comprimento médio dos símbolos fosse superior ou inferior ao obtido na pergunta anterior? E em relação à entropia? Justifique, com base nos fundamentos deste tipo de codificação.
Codificação aritmética
É uma extensão directa da codificação de ShannonFanoElias, em que, em vez de atribuir palavras de código a símbolos individuais, atribui a blocos de n símbolos.
Ideia:
Substituir cada sequência de n símbolos por um único número no intervalo [0,1[. O número tem tanto mais casas decimais quanto menos provável é o bloco a codificar.
Vantagens:
Não é necessário construir/manipular árvores
Desempenho muito bom (melhor que o Huffman) uma vez que não necessita de um número inteiro de bits para codificar cada símbolo individualmente.
Identifique afirmações verdadeiras (V) e falsas (F) sobre técnicas de compressão, na seguinte lista: (2010)
(F) a codificação aritmética tende a aumentar o comprimento médio dos códigos em relação à entropia, quando comparada com codificações como a de Huffman.
(V) A codificação aritmética baseia-se na conversão de 1 sequência de bits de entrada num número real.
(V) No JPEG, o varrimento ZIGZAG dos coeficientes DCT junta os zeros em sequências e permite optimizar a compressão por recurso ao RLE (DPCM ou Huffman).
(V) Os algorítmos LZ* efectuam uma adaptação contínua do esquema de codificação à distribuição estatística desconhecida da fonte, através da construção de dicionários.
(F) a codificação de Huffman é adequada quando não conhecemos a distribuição estatística da fonte.
https://www2.dbd.puc-rio.br/pergamum/tesesabertas/0410838_06_cap_04.pdf
- Quais os princípios por trás do varrimento ZIGZAG dos coeficientes DCT usados no esquema de compressão JPEG?
(Ainda no padrão JPEG, os coeficientes quantizados são separados (o coeficiente mais significativo de cada bloco 8x8 é separado dos demais para efeito de maior compressão) e comprimidos usando-se uma combinação de RLE e codificação de Huffman.)
A compressão de dados é o ato de reduzir o espaço ocupado por dados num determinado dispositivo. Essa operação é realizada através de diversos algoritmos de compressão, reduzindo a quantidade de Bytes para representar um dado, sendo esse dado uma imagem, um texto, ou um arquivo (ficheiro) qualquer.
Comprimir dados destina-se também a retirar a redundância, baseando-se que muitos dados contêm informações redundantes que podem ou precisam ser eliminadas de alguma forma. Essa forma é através de uma regra, chamada de código ou protocolo, que, quando seguida, elimina os bits redundantes de informações, de modo a diminuir seu tamanho nos ficheiros
- Algoritmos de compressão de informação: Comente a seguinte afirmação “A informação comprimida ocupa sempre um espaço inferior ou igual ao que ocupava antes de ser comprimida”. Justifique, corrigindo-a e dando um contra exemplo, se for caso disso.
Falsa. Por vezes os códigos gerados são superiores (ocupam mais espaço)
- Algoritmos de compressão de informação: Qual a relação disso com o facto de o algoritmo adoptado ser com ou sem perdas?
O exemplo mais tradicional que falamos e até que experimentamos na prática é usar o RLE para casos em que não há (muita) informação repetida de seguida. Por exemplo uma imagem com pixeis de cores diferentes em sequência (por exemplo alternando entre pixeis vermelhos e amarelos, ou brancos e pretos (como era o exemplo da aula),
estou a usar só 2 cores para evidenciar que o problema não é serem muitas cores diferentes, mas a ordem ou proximidade das repetições.
O resultado seria análogo com muitas cores diferentes em que não haja muita repetição consecutiva) vai ficar com cerca do dobro do tamanho porque para além do código da cor de cada píxel ainda vai ter a info a dizer quantos pixeis de seguida da mesma cor
(e neste caso é só 1). branco 1 preto 1 branco 1 preto 1 branco 1 ... etc. (em que o número pode ocupar o mesmo espaço para representar que o código da cor - daí ficar cerca do dobro) em vez de branco preto branco preto branco ... Se os mesmos pixeis estivessem organizados de outra forma, o resultado da compressão seria outro. Por exemplo, metade de cima da imagem em branco e metade de baixo em preto,
ficaria com o RLE: branco num_de_pixeis preto num_de_pixeis - e já está, sem '...'. (muito menos info - muito menos espaço requerido)
em vez de: branco branco branco... preto preto preto preto ... assim descomprimido tem o mesmo tamanho da imagem anterior descomprimida: branco preto branco preto branco ...
Algoritmo com perdas vai ser sempre inferior enquanto que sem perdas pode não acontecer depende do algoritmo aplicado (ás vezes é superior).
PS. Outros exemplos:
- usar um código de hufman com info que não tem afinal a distribuição de probbilidades prevista (e troca a ordem relativa de grandeza das probabilidades em relação ao previsto).
- usar LZW em casos em que não se consegue ter grandes sequências que ocorram várias vezes, e que foram incluidas no dicionário.