Introdução

O QM-Coder [Pennebaker and Mitchell] é um método de codificação aritmética binária para imagens JPEG (Joint Photographic Experts Group), mas também é utilizado para imagens JBIG (Joint Photographic Experts Group) e JPEG-2000.

Este codec é propriedade de 3 organizações (IBM, Mitsubishi e Lucent), tem uma variante, o MQ-coder, que por sua vez é propriedade de 2 organizações (IBM e Mitsubishi), este utilizado para compressão de imagens JBIG2 e JPEG-2000.

O QM-Coder usa a codificação aritmética, que é um método de codificação de entropia, logo, um método sem perdas, aliado a métodos de codificação estatística. Sendo um codificador aritmético binário, não se centra apenas na codificação aritmética, mas usa este método somente para código binário. Isto faz com que seja um codec rápido e simples, mas o facto de ser um método patenteado, limita um pouco o seu uso.

Áreas de aplicação

O QM-coder está inserido na norma “ISO/IEC committee draft 11544” e é conhecido como dos melhores exemplos de codificadores aritméticos binários baseados em hardware, ou utilizados em hardware.

Pode ser encontrado em semicondutores das proprietárias IBM e Mitsubishi utilizados em impressoras e outros equipamentos para converter imagens num modo sem perdas.

No entanto, o JPEG é usado na norma “ISO/IEC IS 10918-1 | ITU-T Recommendation T.81”.

Alguns exemplos de aplicações da codificação aritmética em standards:

1.JBIG:  1024 to 4096 ‘ACS’. QM Coder. Também em: JBIG-2

O algoritmo do “QM-Coder”

Seguindo o método da codificação aritmética, o QM-coder precisa definir qual será o símbolo a codificar (cada bit) uma vez que este apenas vai codificar 2 símbolos, o 0 (zero) e o 1, em binário. Assim, para clarificar este aspecto, vai dividir em MPS (Símbolo mais provável) e em LPS (Símbolo menos provável). Antes do próximo bit ser inserido, o QM-coder usa o modelo estatístico para determinar se 0 ou 1 é mais provável de aparecer, logo que seja inserido o bit, classifica-o de acordo com o seu valor real. Se o modelo previr um 0 e o bit acabar por ser 1, o codificador classifica-o como LPS. Isto ajuda-nos a perceber que a única informação que o QM-coder codifica é se o próximo bit será MPS ou LPS, o que o torna rápido. Por sua vez, a descodificação também será rápida pois apenas precisa de saber se o bit é MPS ou LPS, usando para isso o mesmo modelo estatístico da codificação para determinar a relação entre MPS ou LPS e entre o bit 0 ou 1.

Para procurar o LPS ou MPS, o modelo estatístico usa a probabilidade (Q_e) de tal acontecer, no caso, Q_e para LPS e (1- Q_e) para MPS. Uma vez que Q_e é o valor menos provável de acontecer, o sub-intervalo de probabilidades será entre [0; 0,5[ e por sua vez, o MPS será no sub-intervalo superior, de [0,5; 1[, num intervalo de probabilidades A, num momento inicial. O intervalo de probabilidades A é dividido em dois sub-intervalos, inferiormente como MPS, em que o tamanho é A(1- Q_e); superiormente como LPS, cujo tamanho é A x Q_e.

Este modo de processamento é a característica de codificação aritmética “nativa” do QM-coder, com algumas mudanças por forma a optimizar o desempenho e velocidade e, acima de tudo, simplicidade perante a codificação aritmética.

Apresentamos então o modelo de diferenças entre codificação aritmética e o QM-coder.

Quadro 1 – Diferenças entre codificação aritmética optimizada e QM-coder

De cada vez que o intervalo A vai encolhendo, e o output é um qualquer valor dentro desse sub-intervalo, isto no caso da codificação aritmética, no caso do QM-coder é adicionada, em cada passo, o limite inferior de sub-intervalo analisado até cada momento, que será a guardado numa string C.

Valores tomados por C:

– no caso de ser MPS, C toma o valor de 0, pois inicialmente o limite inferior do sub-intervalo de MPS é 0.

– no caso de ser LPS, C toma o valor do limite inferior do sub-intervalo, neste caso

A(1- Q_e).

De cada vez que C é actualizado, o limite do intervalo A vai encolhendo para novos limites, para os limites de cada sub-intervalo, entre [0; A[, sendo este o principio do codificador QM.

Fig.1 Exemplo do limite do intervalo A (Salomon,2007)

Este processo, apesar de assentar sobre o mesmo principio da codificação aritmética standard, apresenta-se com dois problemas:

– O primeiro tem a ver com os limites do intervalo A que começa em 1 e cada vez que este toma os valores dos sub-intervalos, ou seja, cada vez que encolhe, vamos ter o problema de distinguir entra valores menores que 1 e próximos de 0, sendo preciso valores de alta-precisão para computação.

A solução parece estar em duplicar ou dobrar o valor de A cada vez que ficar mais pequeno, chamada de renormalização e que pode ficar rápida de processar usando operações como shift, neste caso, logical left shift, em vez de usar a operação de multiplicação, que usa mais processamento. Estudo experimentais dizem-nos que as operações de multiplicação de integers demora cerca de 10-15 vezes mais do que operações de adição, e que as operações de divisão demoram cerca de 50 vezes mais,

logo não é de estranhar que o QM-coder use operações do tipo shift/add, por forma de simplificar e acelerar este processo.

Temos de ter em atenção que de cada vez que dobrarmos A, também teremos que dobrar C, pois os dois estão inter-ligados nas operações de codificação e descodificação.

– O segundo problema tem a ver com a operação de multiplicação mencionado anteriormente, pois uma vez que esta operação precisa de mais processamento por parte do computador e o pretendido é uma compressão rápida, temos que minimizar este aspecto recorrendo então à substituição por operações shift.

Mais uma vez este processo fica resolvido recorrendo então à renormalização, de forma a manter os limites do intervalo próximos de 1, pois temos que ter em atenção que Q_e não poderá ser muito diferente de o valor de (A x Q_e).

É necessário então explicar a forma como a renormalização é processada e como A é mantido próximo de 1.

– Caso A seja inferior a 0.5, o dobro deste valor será menos de 1, mas caso seja próximo de 1,como 0.9 por exemplo, quando duplicado vai ficar mais próximo de 2 do que de 1, quando o pretendido é aproximar os valores de 1. O valor mínimo para esta operação acabará por ser 0.75, pois duplicado é 1.5, e caso seja inferior como 0.6, acaba ainda mais próximo de 1.

Vamos explicar melhor a renormalização com um exemplo a seguir.

Começando o intervalo em 1 e codificando LPS com a probabilidade de 0.5. A cada renormalização, indicado por à, é incrementado um bit ao integer no fluxo de dados.

Assim, salientamos que o limite mínimo óptimo para a renormalização é 0.75, pois se  A ficar abaixo de 0.5, terá que ser dobrado e renormalizado várias vezes, o que acabaria por acontecer o mesmo com C.

Codificação

• Uma vez que explicamos a codificação de forma extensiva na secção anterior, apenas apresentamos o algoritmo de codificação em pseudo-código nesta secção.

• Algoritmo de codificação, pseudo-código:

Codificar MPS

Begin

C = C;

A ß A – Q;

If (A<0.75) then

If (A<Q) then

C ß C+A;

A = Q;

Endif

Renormalize A and C;

Endif;

End

Codificar LPS

Begin

If (A – Q >= Q) then

C ß C + A – Q;

A = Q;

Else

A = A – Q;

Endif

Renormalize A and C;

End

Descodificação

• A descodificação funciona no modo inverso da codificação, sendo assim um método simétrico.

Para obter o C descodificado, temos que inverter as regras usadas na codificação para C e para A: (Salomon, 2007)

MPS: C mantém; A ß A(1 – Q_e)

LPS: C ß C – A(1 – Q_e); A ß A x Q_e

• Assim, este descodificador vai descodificar o código binário determinando que sub-intervalo é referenciado no fluxo de dados. Como a variável A é do tipo fixed-precision integer, este não pode conter mais informação que a do sub-intervalo actual a descodificar, sendo para isso necessário subtrair o sub-intervalo em questão com o adicionado na codificação.

Algoritmo de descodificação, pseudo-código:

Input C, A=1, Q;

Begin

X ß A*(1-Q);

MPS_interval = [0, X[;

LPS_interval = [X,A[;

If C is in MPS_interval then

{

Output MPS symbol;

A ß A*(1- Q)

}else {

Output LPS symbol;

C ß C – A*(1- Q);

A ßA* Q)}

Endif;

End

Exemplo de aplicação

• Descrever o exemplo que vai ser desenvolvido nesta secção para ilustrar o modo de funcionamento das partes de codificação (compressão) e descodificação (descompressão) do algoritmo correspondente ao método de compressão abordado neste artigo.
• Indica a forma inicial do texto ou conjunto de símbolos que irão ser trabalhados pelo método de compressão.

Codificação

Apresentar passo-a-passo e detalhadamente o resultado da aplicação de cada um dos passos do algoritmo de codificação (compressão) recorrendo ao exemplo introduzido acima, pegando na forma inicial do texto ou conjunto de símbolos a comprimir e mostrando os resultados intermédios até á forma final comprimida.

Descodificação

Apresentar passo-a-passo e detalhadamente o resultado da aplicação de cada um dos passos do algoritmo de descodificação (descompressão) recorrendo ao exemplo introduzido acima, pegando agora na forma comprimida do exemplo obtida na secção anterior e mostrando como decorre a descompressão, até á forma final descomprimida.

Implementação do algoritmo “QM-coder”

• Com base na posse de conhecimentos relacionados com a linguagem, foi decidido usar uma linguagem de programação orientada aos objectos, a linguagem Java para implementar o algoritmo do QM-coder.
• Para proceder à implementação foi usado o programa NetBeans, que contém todos os elementos necessários. Em termos de API’s, não foi necessário usar nenhuma biblioteca, função ou rotina para além das fornecidas pelo programa.
• Enviaremos em ficheiro anexo o código da implementação deste algoritmo, com uma breve explicação de como usar o nosso programa.

Comparação com outros métodos semelhantes

• Resolvemos comparar o QM-coder com o Quic-coder (Quantization integrated compression Coder), desenvolvido pela OKI (Ito e Matsushiro), um sistema a dois níveis da compressão de dados da imagem.
• Este sistema foi desenvolvido para melhorar a performance de codificação, mas realiza uma codificação irreversivel da imagem, mas que resultou num desempenho que ultrapassa o QM-coder, considerando que esta caracteristica irreversivel da imagem ocorra de forma indetectavel entre a relaçao de impressoras de alta-resolução (o objectivo da OKI) e as caracteristicas visuais perceptiveis ao olho humano.
• Tal como o QM-coder, o Quic-coder também dá a máxima prioridade ao racio de compressão, contudo implementaram alguns melhoramentos com vista a focar o tempo de processamento e a performance de codificação.
• O Quic-coder usa as regras de codificação aritmética tal como o QM-coder, no entanto codifica de forma reversível imagens de nível 2-D que sejam reestruturadas dentro do quadro de adaptação da codificação aritmética, ou seja, as imagens reconstruídas são geradas durante o processo de codificação baseado nessas regras, de forma a que o rácio de compressão fosse diminuindo enquanto se minimiza a deterioração da qualidade da imagem visualmente detectada.
• O Quic-coder usa os mesmo métodos de codificação no que diz respeito ao modelo estatístico do calculo das probabilidades do símbolo alvo a ser codificado.
• O processamento de pixéis na fase de reconstrução da imagem é também controlado pelas regras usadas na codificação, para preservar a qualidade da imagem, tal como no QM-coder, podendo ser usado em imagens monocromáticas como com imagens coloridas.
• Uma vantagem do Quic-coder é a de o seu código também poder ser descodificado pelo descodificador QM, uma vez que os princípios de descodificação são os mesmos.

Tabela 1- Comparação de performance de codificação (OKI technical review)

• Embora o Quick-coder possa ter melhores resultados a nível de desempenho de codificação do que o QM-coder, não podemos deixar de salientar que o Quic-coder apresenta algumas perdas, ainda que muito diminutas e imperceptíveis, o que não acontece com o QM-coder e este tem um tempo de processamento de 1/70, muito melhor que o Quick-coder (OKI technical review, 1998).

Conclusão

• O QM-coder é um codec de alta eficácia pois é dependente da informação a codificar/descodificar sendo capaz de restaurar a imagem original, sendo então um método sem perdas, pois as suas funções vão optimizando os parâmetros de  calculo do modelo estatístico da imagem.
• Cada vez mais as técnicas de compressão de imagens são indispensáveis para diminuir o tamanho de armazenamento e o tempo de transmissão das imagens.

Bibliografia

Salomon, D., “Data Compression”, Springer, 4^th. Edition, 2007

Mitchell, J., “Jpeg: Still Image Data Compression Standard”, Kluwer,8^th Edition, 2004

Nishitani,T.,“Digital signal processing for multimedia systems”, Dekker, 1^st Edition, 1999

http://www.jpeg.org/jpeg/, [Em Linha], Consultado a 25/05/2014

http://www.oki.com/en/otr/, [Em linha], Consultado a 26/05/2014

Trabalho desenvolvido no âmbito da disciplina de Multimédia II da Licenciatura em Engenharia Informática, lecionada pelo Prof. Doutor Nuno Magalhães Ribeiro da Faculdade de Ciência e Tecnologia da UFP.

Texto da autoria de Hugo Fernandes (9545) e Rúben Simões (13333) e revisto por Nuno Magalhães Ribeiro.

Site planeado, desenhado, desenvolvido e programado por Daniel Dias Lima Mendes, Diogo Emanuel Lamas e Silva, Nelson José Santos Almeida no âmbito do Projeto de final de Licenciatura realizado na Unidade Curricular de Laboratório de Projeto Integrado sob a orientação técnica do Prof. Doutor Nuno Magalhães Ribeiro.