[tarefa] Codificação de entropia no JPEG

Olá

louds:

Tou tentando implementar essa etapa de um compressor jpeg e tou apanhando pra entender como faz pra codificar o DC com DPCM e o AC com run-length e onde huffman entra nessa historia.

Alguém tem link, documento, referência, fontes ou qualquer material que explique como isso funciona?

O que chama de DC? Discrete Cosine Transform? (classe de operações matemáticas que inclui FFT, fast Fourier transform)

Desconfio que AC (arithmetic coding) não entra na codificação de entropia no passo final da compressão JPEG [color=red](editado: pode entrar sim. Ou usa Huffman ou AC, depende do implementador)[/color]

E DPCM é Differential Pulse Code Modulation? Isto não é para audio?

Alguns links:
http://www.data-compression.info/Algorithms/AC/

http://www.faqs.org/faqs/compression-faq/part2/section-6.html

http://www.dogma.net/markn/articles/articles.htm

http://www.ddj.com/maillists/compression/0011cm/0011cm001.htm

Se quiser, pegue comigo o livro The Data Compression Handbook de 1991 (código em C) do Mark Nelson que no tempo em que estudei compressão (1989/91) era a maior autoridade no assunto.

[]s
Luca

Luca,Acho q oDC é o coeficiente da posição [0,0] da matriz de coeficientes!!!
Louds, eu tô meio véio, e jah tive aula de codificação em jpeg no mcdonalds há muuuito tempo, mas como vc deve estar procurando qquer ajuda.Não custa tentar …
DPCM é para audio não???Eu tenho um resuminho que eu fiz das antigas aqui:
A compressão em JPEG é baseada na transformação DCT(pelo q eu lembro), e nessa transformação a imagem é subdividida em blocos de dados para obtenção de uma matriz 8x8 pixels, sendo que em qualquer dimensão da imagem que não for múltipla de 8 o codificador irá replicar a última coluna e/ou linha até que o tamanho final se torne um múltiplo de 8.
A DCT possui esse nome pq as linhas e colunas da matriz de transformação C são obtidas como funções de cosenos.
Como a DCT deve capturar a influência das 2 direções da imagem, deve-se fazer a multiplicação de matrizes: CxBxtransposta de C onde B é a matriz do bloco da imagem original, e transposta de C é a própria DCT transposta.
Daí teremos o famoso DC(que é o coeficiente [0,0] da matriz de coeficieintes resultantes e os outros serão o AC.(Note que nessa matriz, os coeficientes de mais baixa frequência se localizam na parte superior esquerda da matriz, enquanto os termos de mais alta frequência se localizam na parte inferior direita.Logo depois, teremos o processo de
quantização.

Quantização:
Cada coeficiente DCT deve ser mapeado em um número finito de níveis determinados pelo
fator de compressão desejado.Isto é feito dividindo-se cada elemento da matriz de coefi-
cientes DCT pelo correspondente na matriz de quantização e no final arredondar os valores.
O que, matematicamente temos:
DCTq[i,j]=trunca(DCT[i,j]/q[i,j]+0.5)

A matriz de quantização deve ser definida para cada componente da imagem.(NOTA:Procurar uma tabela para luminância(Y) e outra para crominância(CrCb))

Mapeamento:
A quantização é a etapa que mais contribui para a compressão dos dados.Entretanto, a natureza dos coeficientes DCT quantizados e a preponderância de zeros na matriz permitem que a codificação dos coeficientes para os símbolos seja feita sem perda.Logo, JPEG trata
os coeficientes DC de forma diferente que os coeficentes AC,ou seja, os coeficientes DC são definidos por blocos(blocos adjacentes de que possuem alta correlação), enquanto os coeficientes AC são armazenados na forma de zig-zag, deixando no início desse zig-zag, as informações mais relevantes.

Após o mapeamento, temos a Codificação por Entropia, onde os símbolos definidos(Dc e Ac) devem ser então codificados, usando a codificação por Huffman, que é o método de códigos de tamanho variável(variable-length coding-VLC), onde os menores códigos são atribuídos aos símbolos mais frequêntes.
Uma explicação sucinta do algoritmo de Huffman pode ser feita a partir da resolução do seguinte problema:
“Definir os códigos de um alfabeto que possua os seguintes símbolos e probabilidades de ocorrência: a1(P=0.2),a2(P=0.4),a3(P=0.2),a4(P=0.1) e a5(P=0.1)”.

Note que ordenando os símbolos temos:
Símbolo Probabilidade Código
a2 0.4 c(a2)
a1 0.2 c(a1)
a3 0.2 c(a3)
a4 0.1 c(a4)
a5 0.1 c(a5)

Onde a probabilidade é maior,teremos um menor núm de bits e na menor, um maior num de bits.
Note que os 2 símbolos com menor ocorrência são a4 e a5, onde iremos atribuir os seguinte códigos:
c(a4)=x1+0 e c(a5)=x1+1

onde: x1 é uma string binária e o sinal de (+) significa concatenação.Tem-se então um alfabeto com novas probabilidades:
Símbolo Probabilidade Código
a2 0.4 c(a2)
a1 0.2 c(a1)
a3 0.2 c(a3)
a4 0.2 x1

Seguindo-se o raciocínio para a3 e a4 teremos:
c(a3)=x2+0 e c(a4)=x2+1 ,Mas como c(a4)=x1,

nós teremos c(a4)=x2+10 e c(a5)=x2+11
onde repetindo essa metodologia até o final teremos

Símbolo Probabilidade Código
a2 0.4 1
a1 0.2 01
a3 0.2 000
a4 0.1 0010
a5 0.1 0011

Esta metodologia irá conduzir a criação de árvores que deverão ser usadas para as codificações por entropia como:

0/ \ O O / \1 / \ a2 O a1 a3 / \1 a4 a5

depois voltamos ao problema da codificação dos coeficientes AC da matriz para depois somarmos o conteúdo da coluna total de bits.Por exemplo, se o total de bits for 128, como o bloco possui 64 coeficientes nos tivemos um gotp por esse bloco de 128/64bits o que dará 2bits por pixel, o que é uma redução considerável(comparando com os originais
8bits/pixel).

Louds, eu tinha uma tabela de recomendação de como fazer tudo(com tabela de quantização,codificação etc), mas infelizmente não achei…

Ah, eu jah ia esquecendo de postar, a fórmula para se obter a matriz DCT:
[c]i,j={
sqrt(1/8 ) (cos(2j+1)ip)/16 onde i=0, j=0,1,…,7
e
sqrt(1/4) (cos(2j+1)ip)/16 onde i=1,2,…,7, j=0,1,…,7

Obs:A chave é aquela tradicional chavona que indica que é um sistema.
Na árvore, a4 e a5 estão de baixo do nodo O, é que o fórum zoou tudo e eu não tenho habilidades umlaufianas para design! :lol:

Pois é, meu problema não é na etapa de transformação, quando ocorre a DCT, mas sim durante o entropy coding, quando o coeficiente DC (o [0][0] como o ironlynx falou) é codificado com DPCM (esse algoritmo é genérico e funciona com qualquer stream) e os AC com run-length, e depois tudo com huffman.

Meu problema é encontrar documentação sobre como a etapa de entropy coding funciona, DCT e quantização são bobinhas e existem 1 zilhão de referencias sobre como funciona.

Por enquanto tou programando fazendo engenharia reversa no jpeg codificado pelo painbrush, mais tenho minhas dúvidas se vou muito longe com isso.

Olá

Realmente não me lembrava dos detalhes do coeficiente DC da matriz de quantização (processo de redução do número de bits necessários para guardar um inteiro reduzindo sua precisão). Só procurei rapidamente em http://www.datacompression.info/ e no índice do livro do Mark Nelson.

Continua de pé o meu oferecimento de emprestar a 1a edição do antigo livro do Mark Nelson The Data Compression Book (a 2a Edição (*) saiu em 1995) que na página 372 descreve a codificação de entropia usando RLE (não percebi se também usa AC) e ainda inclui código fonte em C.

(*) The second edition of this book was printed in November, 1995. The text and source code of the book was cleaned up somewhat to match up with current events. In addition, Jean-loup Gailly added a chapter on Fractal Image Compression, and performed some work on the rest of the text.

Há outros livros mais modernos como o The Transform and Data Compression Handbook de 2001 e o Data Compression: The Complete Reference 3a Ed. de 2004.

E mais alguns links:
The Scientist and Engineer’s Guide to Digital Signal Processing - Chapter 27 - Data Compression

Hcompress Image Compression Software (pouco a ver mas interessante)

[]s
Luca

Valeu luca, os links do datacompression.info deram uma boa ajuda.

Tudo bem que meu compressor tá daltonico, mas valeu.