BRPI0614759A2 - codificação e decodificação eficiente de blocos de transformação - Google Patents

Abstract

CODIFICAçAO E DECODIFICAçAO EFICIENTE DE BLOCOS DE TRANS FORMAçAO. Trata-se de um codec de mídia digital baseado emblocos de transformação que codifica de modo mais eficiente coeficientes de transformação através da codificação conjunta de coeficientes diferentes de zero junto com sucessões subseqúentes de coeficientes de valor igual a zero. Quando o coeficiente diferente de zero é o último de seu bloco, um último indicador é substituído pelo valor da sucessão no símbolo para aquele coeficiente. Coeficientes iniciais diferentes de zero são indicados em um símbolo especial que codifica em conjunto o coeficiente diferente de zero junto com as sucessões iniciais e subseqúentes de valores iguais a zero. O codec enseja a codificação múltipla de contextos reconhecendo interrupções nas sucessões de coeficientes diferentes de zero em cada um dos lados da dita interrupção separadamente. O codec também reduz o tamanho da tabela de código indicando em cada símbolo se um coeficiente diferente de zero apresenta valor superior a 1 e se sucessões de zero apresentam valor positivo, codificando separadamente o nível dos coeficientes e o comprimento das sucessões fora dos simbolos.

Description

"CODIFICAÇÃO E DECODIFICAÇÃO EFICIENTE DE BLOCOSDE TRANSFORMAÇÃO"

ANTECEDENTES DA INVENÇÃO

CODIFICAÇÃO BASEADA EM BLOCOS DE TRANSFORMAÇÃO

A codificação por transformação é uma técnica decompressão empregada em diversos sistemas de compressão deáudio, video e imagem. Imagens e vídeos digitais nãocomprimidos são caracteristicamente representados oucapturados como amostras de cores ou elementos de fotos emlocais dentro de um quadro de imagem ou de vídeo em redebidimensional (2D) . A isso nos referimos como umarepresentação de domínio espacial da imagem ou vídeo. Porexemplo, um formato característico para imagens consiste deum fluxo de amostras de elementos de 24 bits de imagemcolorida dispostas em uma grade. Cada amostra é um númeroque representa os componentes coloridos em uma localizaçãode pixel na grade dentro de um padrão de cor, como o RGB ouYIQ, dentre outros. Diversos sistemas de imagem e vídeopodem utilizar várias e diferentes resoluções de tempo, core espaço de amostragem. Da mesma forma, o áudio digital étipicamente representado como um fluxo do sinal de áudioamostrado em intervalos de tempo. Por exemplo, um formatode áudio típico consiste de um fluxo de amostras comamplitude de 16 bits de um sinal de áudio capturado emintervalos de tempo regulares.

Sinais não comprimidos de vídeo, imagem e áudiodigitais podem consumir considerável capacidade dearmazenamento e de transmissão. A codificação portransformação reduz o tamanho do vídeo, das imagens e doáudio digitais, ao transformar a representação de domínioespacial do sinal em representação de domínio de freqüência(ou outro domínio de transformação similar) , e em seguidareduzindo a resolução de determinados componentes dafreqüência geralmente menos perceptíveis da representaçãodo domínio de transformação. Essa situação produz,geralmente, uma degradação menos perceptível do sinaldigital comparado à redução da cor ou da resolução espacialde imagens ou vídeos no domínio espacial ou de áudio nodomínio de tempo.

Mais especificamente, um codec típico baseado natransformação de bloco 100 apresentado na Figura 1 divideos pixels da imagem digital não comprimida em blocosbidimensionais de tamanho fixo (Xi, . . . Xn) , sendo que cadabloco possivelmente se sobrepõe a outros blocos. Umatransformação linear 120-121 que executa a análise defreqüência espacial é aplicada a cada bloco, o qualconverte as amostras espaçadas dentro do bloco em umconjunto de coeficientes freqüência (ou de transformação)que geralmente representam a força do sinal digital nasbandas de freqüência correspondentes sobre o intervalo dobloco. Para a compressão, os coeficientes de transformaçãopodem ser seletivamente quantificados 130 (i.e., reduzidosna resolução, eliminando bits menos significativos dosvalores de coeficiente ou mapeando valores de outra formaem um número de resolução mais elevado ajustado para umaresolução mais baixa), e também a entropia ou um codificadode comprimento variável 130 em um fluxo de dadoscomprimidos. Na decodificação, os coeficientes detransformação irão transformar inversamente 170-171 parareconstruir aproximadamente o sinal original deimagem/video com amostragem de cor/espacial (blocosreconstruídos Xi, . . . Xn) .

O bloco de transformação 120-121 pode serdefinido como uma operação matemática em um vetor χ detamanho N. Mais comumente, a operação é uma multiplicaçãolinear, produzindo a saída de domínio de transformação y =Mxr sendo M a matriz de transformação. Quando os dados deentrada são arbitrariamente longos, são segmentados emvetores de tamanho Nr aplicando-se uma transformação porbloco a cada segmento. Para fins de compressão de dados,são escolhidos transformações de bloco reversíveis. Emoutras palavras, a matriz M é invertível. Nas dimensõesmúltiplas (por exemplo, para imagem e vídeo) , astransformações por bloco são tipicamente implantadas comooperações isoladas. Aplica-se a multiplicação da matrizseparadamente ao longo de cada dimensão de dados (i.e.,ambas as fileiras e colunas).

Para compressão, os coeficientes de transformação(componentes do vetor y) podem ser seletivamentequantificados (i.e., reduzidos na resolução, eliminandobits menos significativos dos valores de coeficiente oumapeando valores de outra forma em um número de resoluçãomais elevado ajustado para uma resolução mais baixa), etambém a entropia ou comprimentos variáveis codificados emum fluxo de dados comprimidos.

Decodificando no decodificador 150, o inversodessas operações (dequantização/decodificando a entropia160 e transformação por bloco inversa 170-171) é aplicadono decodificador do lado 150, conforme demonstrado na Fig.1. Enquanto reconstruindo os dados, a matriz inversa K1(transformação inversa 170-171) é aplicada como ummultiplicador aos dados do domínio de transformação. Quandoaplicado aos dados do domínio de transformação, atransformação inversa reconstrói aproximadamente a mídiadigital original do domínio do tempo ou do domínioespacial.

Em diversas aplicações de codificação baseada natransformação por bloco, a transformação é reversível edesejável, a fim de suportar a compressão com perda dedados e a compressão sem perda de dados, dependendo dofator de quantização. Sem quantização (geralmenterepresentada como um fator de quantização de 1), porexemplo, um codec utilizando uma transformação reversívelpode reproduzir exatamente os dados de entrada nadecodificação. Entretanto, a reversibilidade requeridanessas aplicações restringe a escolha de transformaçõessobre as quais o codec pode ser projetado.

Numerosos sistemas de compressão de imagem e devídeo, como o MPEG e o Windows Media, entre outros,empregam transformações baseadas na Transformação Discretado Cosseno (DCT) . A DCT é conhecida por suas propriedadesfavoráveis de compactação de energia que proporcionam umacompressão de dados próxima ao ideal. Nesses sistemas decompressão, a DCT inversa (IDCT) é empregada nas malhas dereconstrução no codificador e no decodificador do sistemade compressão para reconstruir blocos de imagem individual.Codificação de Entropia de Coeficientes deTransformação com Ampla Variação

Dados de entrada com ampla variação dinâmicaconduzem a coeficientes de transformação com variaçãodinâmica ainda maior, gerados durante o processo decodificação de uma imagem. Por exemplo, os coeficientes detransformação gerados por um N através de uma operação NDCT apresenta uma variação N vezes maior do que a variaçãodinâmica dos dados originais. Com fatores de quantizaçãopequenos ou unitários (empregados para efetuar compressãocom pequena perda ou sem perda), a variação doscoeficientes de transformação quantificados também égrande. Estatisticamente, esses coeficientes apresentam umadistribuição laplaciana conforme observado nas Figuras 2 e3. A Figura 2 apresenta uma distribuição Laplaciana paracoeficientes de ampla variação dinâmica. A Figura 3apresenta uma distribuição laplaciana para coeficientescaracterísticos de menor variação dinâmica.

A codificação por transformação convencional éajustada para uma pequena variação dinâmica de dados deentrada (tipicamente 8 bits), e quantificadoresrelativamente grandes (como valores numéricos de 4 eacima). A Figura 3, portanto, é representativa dadistribuição dos coeficientes de transformação na ditacodificação de transformação convencional. Ainda mais, acodificação de entropia empregada com a dita codificação detransformação convencional pode ser uma variante dacodificação do nível de execução, onde uma sucessão dezeros é codificada junto com um símbolo diferente de zero.Esse pode ser um meio efetivo de representar execuções dezeros (que ocorre com alta probabilidade) , assim como decapturar correlações inter-simbolos.

Por outro lado, a codificação por transformaçãoconvencional é menos adequada para se comprimirdistribuições de ampla variação dinâmica tais como asapresentadas na Figura 2. Embora os símbolos sejam zero,com maior probabilidade do que qualquer outro valor (i.e.,os picos de distribuição em zero), a probabilidade de umcoeficiente ser exatamente zero é diminuta para adistribuição de ampla variação dinâmica. Como conseqüência,os zeros não ocorrem com muita regularidade, e as técnicasde codificação de entropia de comprimento de execuçãobaseadas nò número de zeros entre coeficientes sucessivosdiferentes de. zero são bastante ineficientes para dados deentrada de ampla variação dinâmica.

A distribuição de ampla variação dinâmica tambémapresenta um alfabeto crescente de símbolos, quandocomparada com a distribuição de estreita variação. Emfunção desse crescente alfabeto de símbolos, a tabela deentropia utilizada para codificar os símbolos precisará sermaior. Caso contrário, muitos símbolos não serãocodificados, o que é ineficiente. As tabelas maioresrequerem mais memória e também podem resultar em maiorcomplexidade.

Portanto, a codificação por transformaçãoconvencional carece de versatilidade - trabalhandosatisfatoriamente para os dados de entrada com distribuiçãode variação dinâmica estreita, mas não para a distribuiçãocom ampla variação dinâmica.

No entanto, nos dados de variação estreita,encontrar codificação de entropia eficiente de coeficientesde transformação quantificados é um processo critico.

Qualquer ganho de desempenho que possa ser adquirido nessaetapa (ganhos em termos de eficiência de compressão e develocidade de codificação/decodificação) se traduz porganhos de qualidade geral.

Modelos diferentes de codificação de entropia sãomarcados por sua habilidade de se beneficiar positivamentedos ditos critérios de eficiência dispares como: o uso deinformação contextual, compressão maior (como a codificaçãoaritmética), requerimentos computacionais inferiores (comoencontrado nas técnicas de codificação de Huffman), eempregando um conjunto conciso de tabelas de código com oobjetivo de minimizar a sobrecarga (overhead) da memória docodificador/decodificador. Métodos de codificação deentropia convencionais, que não se ajustam a todas essascaracterísticas, não demonstram eficiência completa decodificação de coeficientes de transformação.

SUMÁRIO

Uma técnica para decodificação e codificação deuma mídia digital e a realização da técnica em um codec demídia digital descrito no presente atinge maior eficiênciade compressão dos coeficientes de transformação. Porexemplo, um codec exemplificativo de mídia digital baseadona transformação de bloco ilustrado no presente codificacom maior eficiência coeficientes de transformaçãocodificando em conjunto coeficientes diferentes de zerojunto das execuções seguintes de coeficientes de valorigual a zero. Quando um coeficiente diferente de zero ocupaa última posição no bloco, um último indicador ésubstituído pelo valor de execução no símbolo relativoàquele coeficiente. Coeficientes iniciais diferentes dezero são indicados por um símbolo especial que codifica emconjunto o coeficiente diferente de zero junto com asexecuções iniciais e subseqüentes dos zeros.

0 codec exemplificativo permite contextos decodificação múltipla reconhecendo interrupções nasexecuções dos coeficientes diferentes de zero e codificandocoeficientes diferentes de zero em cada lado da ditainterrupção separadamente. Contextos adicionais sãofornecidos através da comutação de contexto baseada nastransformações internas, intermediárias e externas assimcomo nas comutações de contexto baseadas em quetransformações correspondem a canais de luminância ou decrominância. Esse fato permite que as tabelas de códigoapresentem menor entropia, evitando criar tantos contextos,de forma a diluir seu proveito.

O codec exemplificativo também reduz a tabela decódigo indicando em cada símbolo se um coeficientediferente de zero apresenta um valor absoluto superior a 1e se as execuções de zero apresentam um valor positivo, ecodifica separadamente o nível de coeficientes e ocomprimento das execuções fora dos símbolos. O codec podese beneficiar da comutação do contexto no que diz respeitoa esses níveis e execuções com codificados separadamente.

Os vários sistemas e técnicas podem serutilizados em associação ou de forma independente.

Esse Sumário é fornecido a fim de introduzir umaescolha de conceitos de forma simplificada que serão aindadescritos abaixo na Descrição Detalhada. Esse Sumário nãopretende identificar elementos essenciais ou elementoschave da matéria objeto reivindicada, nem pretende serutilizada para auxiliar na determinação do escopo damatéria objeto reivindicada.

Características e vantagens adicionais tornar-se-ão aparentes a partir da seguinte descrição detalhada dasmodalidades que procedem com referência aos desenhosanexos.

BREVE DESCRIÇÃO DOS DESENHOS

A Figura 1 é um diagrama em bloco de um codecconvencional baseado na transformação de bloco na técnicaanterior.

A Figura 2 é um histograma mostrando umadistribuição de coeficientes de transformação dotados deampla variação dinâmica.

A Figura 3 é um histograma apresentando umadistribuição de coeficientes com estreita variação.

A Figura 4 é um diagrama de fluxo de umcodificador representativo que incorpora uma codificaçãoadaptativa de coeficientes de ampla variação.

A Figura 5 é um diagrama de fluxo de umdecodificador representativo que incorpora a decodificaçãode coeficientes com ampla variação codificadosadaptativamente.

A Figura 6 é um diagrama de fluxo ilustrando oagrupamento e a disposição em camadas de coeficiente detransformação na codificação adaptativa de coeficientes deampla variação, assim como no codificador da Figura 4.

A Figura 7 é um fluxograma mostrando um processorealizado pelo codificador da Figura 4 com o intuito decodificar um coeficiente de transformação para um dadoagrupamento de coeficientes de transformação em bins.

A Figura 8 é um fluxograma apresentando umprocesso realizado pelo codificador da Figura 5 com ointuito de reconstruir o coeficiente de transformaçãocodificado através do processo da Figura 7.

A Figura 9 é um fluxograma apresentando umprocesso de adaptação com o intuito de variar o agrupamentoda Figura 6 visando produzir uma distribuição melhor para acodificação de entropia dos coeficientes.

As Figuras 10 e 11 são uma lista de pseudocódigosdo processo de adaptação da Figura 9.

A Figura 12 ilustra exemplos de coeficientes detransformação codificados na técnica anterior.

A Figura 13 ilustra um exemplo de coeficientes detransformação codificados de acordo com as técnicas decodificação descritas no presente.

A Figura 14 é um fluxograma apresentando umprocesso realizado pelo decodificador da Figura 4 paracodificar coeficientes de transformação.

A Figura 15 ilustra exemplos de diferentescontextos de tabelas de código empregados para codificarcoeficientes de transformação de acordo com as técnicasdescritas no presente.A Figura 16 é um fluxograma apresentando umprocesso realizado pelo codificador da Figura 4 a fim dedeterminar contextos de codificação a serem empregados aocodificar coeficientes de transformação.

A Figura 17 ilustra um exemplo de coeficientes detransformação reduzidos que foram codificados de acordo comas técnicas descritas no presente.

A Figura 18 é um fluxograma apresentando umprocesso realizado pelo codificador da Figura 4 a fim decodificar e enviar coeficientes iniciais de transformaçãona forma reduzida.

A Figura 19 é um fluxograma apresentando umprocesso realizado pelo codificador da Figura 4 a fim decodificar e enviar coeficientes subseqüentes na formareduzida.

A Figura 20 é um fluxograma apresentando umprocesso realizado pelo codificador da Figura 5 a fim decodificar coeficientes de transformação codificados.

A Figura 21 é um fluxograma apresentando um ·processo realizado pelo codificador da Figura 5 a fim deocupar os coeficientes de transformação a partir dossímbolos decodificados.

A Figura 22 é um diagrama de bloco de um ambientede computação adequado para a implantação da codificaçãoadaptativa dos coeficientes de ampla variação da Figura 6.

DESCRIÇÃO DETALHADA

A seguinte descrição refere-se às técnicas decodificação e de decodif icação que se ajustam de modoadaptativo à codificação de entropia mais eficiente doscoeficientes de transformação de ampla variação, assim comoà codificação de entropia mais eficiente dos coeficientesde transformação em geral. A descrição a seguir descreveuma implantação exemplificativa no contexto de um sistemade compressão de midia digital ou codec. 0 sistema de midiadigital codifica dados de midia digital na forma comprimidapara transmissão ou armazenamento, e decodifica os dadospara reprodução ou outra forma de processamento. Para finsilustrativos, esse sistema exemplificativo de compressãoque incorpora essa codificação adaptativa dos coeficientesde ampla variação é um sistema de compressão de imagem oude video. Como alternativa, a técnica também pode serincorporada a sistemas de compressão ou codecs para outrosdados de 2D. A técnica de codificação adaptativa decoeficientes de ampla variação não requer que o sistema decompressão de midia digital codifique os dados de midiadigital comprimidos em um formato particular decodificação.

1. CODIFICADOR/DECODIFICADOR As Figuras 4 e 5 são um diagrama generalizado dosprocessos empregados em um decodificador 500 e umcodificador 400 representativos de dados bidimensionais(2D) . Os diagramas apresentam uma ilustração generalizadaou simplificada de um sistema de compressão que incorporaum decodificador e um codificador de dados 2D que implantama codificação adaptativa de coeficientes de ampla variação.Em sistemas de compressão alternativos que utilizam acodificação adaptativa de coeficientes de ampla variação,processos adicionais ou apenas alguns daqueles ilustradosnesse codificador e decodificador representativos podem serempregados para a compressão de dados 2D. Por exemplo,alguns codificadores/decodificadores também incluem aconversão de cor, formatos de cor, codificação graduável,codificação sem perda de dados, modos de macroblocos, etc.0 sistema de compressão (codificador e decodificador) podeproporcionar compressão com perda de dados 2D e/ou semperda de dados 2D, dependendo da quantização, podendo essaser baseada em um parâmetro de quantização que varia dedados perdidos a não perdidos.

O codificador de dados 2D 400 produz um fluxo debits comprimido 420 que é uma representação mais compacta(para a entrada típica) de dados 2D 410 apresentados como aentrada para o codificador. Por exemplo, a entrada de dados2D pode ser uma imagem, um quadro de uma seqüência de vídeoou outros dados de duas dimensões. O codificador de dados2D 430 recorta os dados de entrada em macroblocos de 16 χ16 pixels de tamanho nesse codificador representativo. Ocodificador de dados 2D ainda recorta cada macrobloco emblocos de 4 χ 4. Uma operadora de "sobreposição antecipada"440 é aplicada a cada bordo entre blocos, e em seguida cadabloco 4 χ 4 é transformado utilizando uma transformação debloco 450. Essa transformação de bloco 450 pode ser atransformação 2D reversível e livre de graduação descritapor Srinivasan, Pedido de Patente N0 U.S. 11/015.707intitulada "Reversible Transform for Lossy and Lossless 2-DData Compression", depositado em 17 de dezembro de 2004. Aoperadora de sobreposição 440 pode ser a operadora desobreposição reversível descrita por Tu et al, Pedido dePatente N0 U.S. 11/015.148 intitulada "Reversible OverlapOperator for Efficient Lossless Data Compression"depositado em 17 de dezembro de 2004; e por Tu et al,Pedido de Patente N0 U.S. 11/035.991 intitulado "Reversible2-Dimensional Pré-/Post-Filtering for Lapped BiorthogonalTransform" depositado em 4 dé janeiro de 2005. Comoalternativa, pode-se utilizar a transformação discreta docosseno. Em seguida à transformação, o coeficiente DC 460de cada bloco de transformação 4x4 é submetido à cadeia deprocessamento similar (recorte, sobreposição antecipada,seguida da transformação do bloco 4x4). Os coeficientes detransformação DC resultantes e os coeficientes detransformação AC são quantificados 470, codificados porentropia 480 e empacotados 490.

0 decodificador executa o processo reverso. Nolado do decodif icador, os bits do coeficiente detransformação são extraídos 510 de seus respectivospacotes, a partir dos quais os coeficientes em si sãodecodificados 520 e dequantifiçados 530. Os coeficientes DC540 são regenerados aplicando-se a transformação inversa, eo plano dos coeficientes DC é "sobreposto de forma inversa"aplicando uma operadora de uniformização apropriadaperpendicularmente às bordas dos blocos DC. Em seguida,todos os dados são regenerados aplicando-se a transformaçãoinversa 4x4 550 aos coeficientes DC e os coeficientes AC542 são decodificados a partir do fluxo de bits.Finalmente, as bordas dos blocos nos planos das imagensresultantes são filtradas com sobreposição inversa 560, oque produz uma saida de dados de 2D reconstruídos.Em uma implantação exemplificativa, o codificador400 (Figura 4) comprime uma imagem de entrada em um fluxode bits comprimidos 420 (por exemplo, um arquivo) e odecodificador 500 (Figura 5) reconstrói a entrada originalou uma aproximação da mesma, utilizando como base se acodificação empregada apresenta ou não perda de dados. 0processo de codificação envolve a aplicação de . umatransformação sobreposta anterior (LT) discutida abaixo,que é implantada junto com uma pré-/pós-f iltragemreversível bidimensional, também descrita abaixo em suatotalidade. O processo de decodificação envolve a aplicaçãoda transformação sobreposta inversa (ILT) que utiliza apré-/pós-filtragem reversível bidimensional.

A LT e a ILT ilustradas são a inversão uma daoutra, no sentido exato e, portanto, podem sercoletivamente denominadas como uma transformação sobrepostareversível. Como uma transformação reversível, o par LT/ILTpode ser utilizado para uma compressão de imagem sem perdade dados.

Os dados de entrada 410 comprimidos pelocodificador 400/decodificador 500 ilustrados podem serimagens com formatos de cores variadas (por exemplo,formatos de imagens coloridas RGB/YUV4: 4:4, YUV4: 2:2 ouYUV4: 2:0). Tipicamente, a imagem de entrada sempreapresenta um componente de luminância (Y) . Caso seja umaimagem RGB/YUV4: 4:4, YUV4: 2:2 ou YUV4: 2:0, a imagemtambém apresenta componentes de crominância, como umcomponente U e um componente V. Os planos coloridosseparados da imagem podem possuir diferentes resoluçõesespaciais. No caso de uma imagem de entrada no formatocolorido YUV 4:2: 0, por exemplo, os componentes UeVapresentam metade da largura e da altura do componente Y.

Conforme discutido acima,, o codificador 400agrupa a imagem de entrada ou a figura em macroblocos. Emuma implantação exemplificativa, o codificador 400 agrupa aimagem de entrada em macroblocos de 16 χ 16 no canal Y (quepodem apresentar áreas de 16 χ 16, 16 χ 8 ou 8 χ 8 noscanais U e V, dependendo do formato colorido) . Cada planocolorido do macrobloco é agrupado em blocos ou regiões 4 χ4. Portanto, um macrobloco é composto por diversos formatoscoloridos da seguinte maneira para a presente implantaçãode codificador exemplificativo:

1. Para uma imagem em tons de cinza, cadamacrobloco contém 16 blocos 4 χ 4 de luminância (Y) .

2. Para uma imagem colorida com formato YUV4:2:0, cada macrobloco contém 16 blocos 4 χ 4 Y e 4 blocos 4χ 4 com crominância (U e V) cada.

3. Para uma imagem colorida com formato YUV4:2:2, cada macrobloco contém 16 blocos 4 χ 4 Y e 4 blocos 4

χ 4 com crominância (U e V) cada.

4. Para uma imagem colorida RGB ou YUV4: 4:4,cada macrobloco contém 16 blocos cada um com canais Y, U eV.

2. CODIFICAÇÃO ADAPTATIVA DE COEFICIENTES DEAMPLA VARIAÇÃO

No caso de dados de ampla variação dinâmica, emespecial dados de transformação não correlacionados (taiscomo os . coeficientes 460, 462 no codificador da Figura 4),um número significativo de bits de razão menor sãoimprevisíveis e "ruidosos". Em outras palavras, não hácorrelação estreita dos bits de razão menor que podem serutilizados para a codificação de entropia eficiente. Osbits apresentam entropia elevada, aproximando-se de 1 bitpara cada bit codificado.

2.1 AGRUPAMENTO

Mais além, a função de distribuição deprobabilidade Laplaciana dos coeficientes de transformaçãode ampla variação demonstrados na Figura 3 é dada por:

<formula>formula see original document page 18</formula>

(por conveniência, a variável aleatóriacorrespondente aos coeficientes de transformação é tratadacomo um valor contínuo). Para dados de ampla variaçãodinâmica, γ é pequeno, e a média absoluta l/γ é grande. 0gradiente dessa distribuição está limitado a ± h (γ2) , oque é bem pequeno. Significa que a probabilidade de umcoeficiente de transformação ser igual a χ está muitopróxima à probabilidade de χ + ξ para um ξ de pequeno. Nodomínio discreto, isso traduz a reivindicação, "aprobabilidade de um coeficiente de transformação adotarvalores adjacentes j e (j+1) é quase idêntica".

Fazendo referência à Figura 6, a codificaçãoadaptativa de coeficientes de ampla variação desempenha umagrupamento 610 de símbolos sucessivos do alfabeto em"bins" de símbolos Ν. 0 número de símbolos por bin pode serqualquer número N. Para comodidade, no entanto, o número Né, de preferência, uma potência de 2 (i.e., N = 2k) , deforma que o indicador ou endereço de um coeficiente dentrode um bin pode ser codificado com eficiência como um códigode comprimento fixo. Por exemplo, os símbolos podem seragrupados em pares, de modo que um símbolo possa seridentificado como o indicador do par, junto com o indicadordo símbolo dentro do par.

Esse agrupamento se beneficia do fato de que, comuma escolha apropriada de N, a distribuição deprobabilidade do indicador do bin para coeficientes deampla variação se parece mais com uma distribuição deprobabilidade de dados de estreita variação, por exemplo,aqueles demonstrados na Figura 3. O agrupamento ématematicamente semelhante à operação de quantização, o quesignifica que o indicador de bin pode ser codificado comeficiência utilizando técnicas de codificação de entropiacom comprimento variável que atuam melhor para dados comdistribuição de probabilidade de variação estreita.

Baseando-se no agrupamento de coeficientes embins, o codificador pode então codificar um coeficiente detransformação 615 empregando um indicador de seu bin(também citado no presente como o coeficiente normalizado620) e seu endereço dentro do bin (citado no presente comoo endereço de bin 625). O coeficiente normalizado écodificado utilizando uma codificação de entropia comcomprimento variável, enquanto o endereço do bin écodificado por meio de um código de comprimento fixo.

A escolha de N (ou de forma equivalente, o númerode bits k para a codificação de comprimento fixo doendereço bin) determina a granularidade do agrupamento. Emgeral, quanto maior a variação dos coeficientes detransformação, maiores os valores k que devem serescolhidos. Quando k é escolhido com critério, ocoeficiente normalizado Y é zero, com elevada probabilidadede se ajustar ao modelo de codificação de entropia para Y.

Conforme descrito acima, pode-se atribuiradaptativamente diferentes valores a k (de forma adaptativacom a anterior) em um codificador e decodificador. Maisespecificamente, o valor de K tanto no codificador quantono decodif icador varia com base apenas nos dadospreviamente codificados/decodificados.

Em um exemplo particular desta codificaçãoapresentada na Figura 7, o codificador codifica umcoeficiente de transformação X da forma adiante. Para umaação inicial 710, o codificador calcula um coeficientenormalizado Y para o coeficiente de transformação. Nessaimplantação exemplificativa, o coeficiente normalizado Y édefinido como

Y=Sinal(X)*piso(abs(X)/Ν), para uma determinadaescolha do tamanho do bin N=2k. O codificador codifica osímbolo Y usando um código de entropia (ação 720), sejaisoladamente ou em conjunto com outros símbolos. A seguir,na ação 730, o codificador determina um endereço bin (Z) docoeficiente de transformação X. Nessa implantaçãoexemplificativa, o endereço bin é o resíduo da divisãointeira de abs(X) pelo tamanho de bin N ou Z=abs(X)%N. 0codificador codifica esse valor como um código decomprimento fixo de k bits na ação 740. Mais além, no casode um coeficiente de transformação diferente de zero, ocodificador também codifica o sinal. Mais especificamente,conforme indicado nas ações 750-760, o codificador codificao sinal do coeficiente normalizado (Y) quando o coeficientenormalizado é diferente de zero. Ainda mais, no caso docoeficiente normalizado ser zero e o coeficiente detransformação ser diferente de zero, o codificador codificao sinal do coeficiente de transformação (X). Uma vez que ocoeficiente seja codificado através de um código deentropia com comprimento variável, também será citado nopresente como a parte de comprimento variável, e o endereçobin (Z) também será citado no presente como a parte decomprimento fixo. Em outras implantações alternativas, asdefinições matemáticas do coeficiente normalizado, doendereço bin e do sinal para um coeficiente detransformação podem variar.

Continuando com esse exemplo, a Figura 8apresenta um processo exemplificativo 800 realizado pelocodificador 500 (Figura 5) a fim de reconstruir ocoeficiente de transformação que foi codificado peloprocesso 700 (Figura 7). Na ação 810, o codificadorcodifica o coeficiente normalizado (Y) a partir do fluxo debits comprimido 420 (Figura 5) , tanto isoladamente quantoem conjunto com outros símbolos segundo definido noprocesso de codificação do bloco. 0 decodificador ainda lêa palavra código com k bits para o endereço bin e o sinal(quando codificado) a partir do fluxo de bits comprimido naação 820. Nas ações 830 a 872, o codificador entãoreconstrói o coeficiente de transformação, da seguintemaneira:1. Quando Y>0 (ação 830), então o coeficiente detransformação é reconstruído como X=Y*N+Z (ação 831)).

2. Quando Y<0 (ação 840), então o coeficiente detransformação é reconstruído como X=Y*N-Z (ação 841).

3. Quando Y=O e Z=O (ação 850), então ocoeficiente de transformação é reconstruído como X=O (ação851) .

4. Quando Y=O e Z#0, o codificador, ainda lê osinal codificado (S) a partir do fluxo de bits comprimido(ação 860) . Se o sinal for positivo (S=O) (ação 870), entãoo coeficiente de transformação é reconstruído como X=Z(ação 871). Ainda, se o sinal for negativo (S=I), ocoeficiente de transformação é reconstruído como X=Z (ação872) .

2.2 DISPOSIÇÃO EM CAMADASFazendo referência novamente à Figura 6, ocodificador e o decodificador, de preferência, extraem osendereços bin de comprimento fixo codificados 625 e o sinalpara uma camada codificada separada (no presente denominadacamada "Flexbits" 645) no fluxo de bits comprimido 420(Figura 4). Os coeficientes normalizados 620 sãocodificados em uma camada do fluxo de bits do núcleo 640, oque permite ao codificador e/ou decodificador optar porminimizar ou abandonar inteiramente essa porção Flexbits dacodificação, conforme desejado, para se ajustar à taxa debit ou a outras restrições. Mesmo que o codificadorabandone inteiramente a camada Flexbit, o fluxo de bitscomprimido ainda poderia efetuar a decodificação, emboracom degradação da qualidade. O decodificador poderia aindareconstruir o sinal a partir apenas da porção doscoeficientes normalizados. Essa situação é efetivamentesemelhante à aplicação de um grau mais elevado dequantização 470 (Figura 4) no decodificador. Adecodificação do sinal e dos endereços bin como uma camadade flexbits separada também apresenta o beneficio potencialque em algumas implantações de codificador/decodificador,uma outra codificação de entropia com comprimento variável(por exemplo, codificação aritmética, Lempel-Ziv, Burrows-Wheeler, etc.) poderia ser aplicada aos dados nessa camadapara futuro aperfeiçoamento de compressão.

Para a disposição de camadas, as seções do fluxode bits contendo as porções flexbits são sinalizadasatravés de um cabeçote de camada separada ou outraindicação no fluxo de bits, de modo que o decodif icadorpossa identificar e separar (i.e., analisar) a camada deFlexbits 645 (quando não omitida) a partir do fluxo de bitsprincipal 640.

A disposição de camadas apresenta um desafioadicional no projeto do agrupaménto adaptativo anterior(descrito na próxima seção). Uma vez que a camada Flexbitspode estar presente ou ausente em um dado fluxo de bits, omodelo de agrupamento adaptativo anterior não pode, comconfiança, se referir a nenhuma informação na camadaFlexbits. Toda a informação necessária para se·determinar onúmero de bits de código de comprimento fixo k(correspondente ao tamanho bin N=2k) deveria residir nofluxo de bits causai, principal.

2.3 ADAPTAÇÃOO codificador e decodificador proporcionam aindaum processo adaptativo anterior para ajustaradaptativamente a escolha do número k de bits de código decomprimento fixo e, de modo correspondente, o tamanho debin N do agrupamento descrito acima, durante a codificaçãoe a decodificação. Em uma implantação, o processo deadaptação pode se basear na modelagem dos coeficientes detransformação como uma distribuição Laplaciana, de formaque o valor de k deriva do parâmetro Laplaciano λ. Noentanto, o dito modelo sofisticado poderia requerer que odecodificador executasse o inverso do agrupamento 610(reconstruir os coeficientes de transformação a partir doscoeficientes normalizados no fluxo de bits principal 640 eo endereço/sinal bin na camada Flexbits 645) na Figura 6antes de modelar a distribuição para blocos futuros. Esserequerimento poderia violar a restrição da disposição decamadas que o decodificar deveria permitir abandonando acamada Flexbits a partir do fluxo de bits comprimido 420.

Na implantação exemplificativa apresentada naFigura 9, o processo de adaptação 900 se baseia, aocontrário, na observação de que uma melhor codificação decomprimento de execução dos coeficientes de transformação éatingida quando em torno de um quarto dos coeficientes sãodiferentes de zero. Assim, um parâmetro de adaptação quepode ser empregado para ajustar o agrupamento em direção auma situação "ideal" irá promover um bom desempenho dacodificação de entropia. Da mesma forma, o número decoeficientes normalizados diferentes de zero em um bloco éutilizado como um parâmetro de adaptação na implantaçãoexemplificativa. Esse parâmetro de adaptação incorpora avantagem de depender apenas na informação contida no fluxode bits principal, que se ajusta à restrição da disposiçãode camada que os coeficientes de transformação podem aindaser decodificados com a omissão da camada Flexbits. 0processo é uma adaptação anterior no sentido de que omodelo de adaptação aplicado quandocodificando/decodificando o atual bloco se baseia nainformação do(s) bloco(s) anterior(es).

No seu processo de adaptação, o codificador e odecodificador exemplificativos realizam a adaptação combase na adaptação anterior. Quer dizer, uma iteração atualda adaptação se baseia na informação previamente observadano processo de codificação ou de decodificação, tal como nobloco ou macrobloco anterior. No decodificador e nocodificador exemplificativo, a atualização da adaptaçãoocorre uma vez por bloco para uma dada banda detransformação, a qual deve atuar reduzindo a latência e adependência cruzada. Implantações alternativas de codecpodem realizar a adaptação em intervalos diferentes, comoapós cada bloco de transformação.

No decodificador e no codificadorexemplificativos, o processo de adaptação 900 atualiza ovalor k. Se o número do coeficiente normalizado diferentede zero for muito alto, então k assumirá valores maiores,de forma que esse número tenderá a ser abandonado nosblocos futuros. Se o número de coeficientes normalizadosdiferentes de zero for muito pequeno, então o valor k éreduzido com a expectativa de que blocos futuros, então,irão produzir mais coeficientes normalizados diferentes dezero, porque o tamanho de bin N é menor. 0 processo deadaptação exemplificativo restringe o valor k ao conjuntode números {0, 16}, mas implantações alternativaspoderiam utilizar outras variações de valores para k. Acada atualização de adaptação, o codificador e odecodificador elevam, reduzem ou mantém o valor kinalterado. O codificador e o decodificador elevam oureduzem k em um, mas implantações alternativas poderiamempregar outros tamanhos de etapas.

O processo de adaptação 900 no codificador edecodificador exemplificativo utiliza ainda um parâmetro demodelo interno ou uma variável de estado (M) para controlara atualização do parâmetro de agrupamento k com efeito dehisterese. Esse parâmetro de modelo produz um intervaloantes de atualizar o parâmetro de agrupamento k, evitandocausar flutuação rápida no parâmetro de agrupamento. 0parâmetro do modelo no processo de adaptaçãoexemplificativo é composto por 17 etapas inteiras, de -8 a8.

Fazendo referência agora à Figura 9, o processode adaptação exemplificativa 900 ocorre da seguinte forma.Esse processo de adaptação exemplificativa é mais detalhadona relação de pseudocódigos das Figuras 10 e 11. Nasindicações das ações 910, 990, o processo de adaptação nocodificador e decodificador exemplificativo é realizadoseparadamente em cada banda de transformação que estárepresentada no fluxo de bits comprimido, inclusive a bandade luminância e as bandas de crominância, os coeficientesAC e DC, etc. Os codecs alternativos podem apresentarvariação no número de bandas de transformação, e depoispodem aplicar a adaptação às bandas de transformaçãoisoladamente ou em conjunto.

Na ação 920, o processo de adaptação, então,contabiliza o número de coeficientes normalizadosdiferentes de zero da banda de transformação dentro dopróximo macrobloco previamente codificado/decodificado. Naação 930, essa contabilização bruta é normalizada com oobjetivo de refletir o número inteiro de coeficientesdiferentes de zero em uma área de tamanho regular. Oprocesso de adaptação, então, calcula (ação 940) o desvioda contagem a partir do modelo desejado (i.e., o "pontoideal" de um quarto dos coeficientes que é diferente dezero) . Por exemplo, um macrobloco de coeficientes AC nocodificador exemplificativo apresentado na Figura 4apresenta 240 coeficientes. Então, o modelo desejado deveapresentar 70 coeficientes diferentes de zero dos 240coeficientes. Em seguida, o desvio é dimensionado, niveladoe empregado para atualizar o parâmetro do modelo interno.

Nas ações seguintes 960, 965, 970, 975, então, oprocesso de adaptação adapta o valor k de acordo comqualquer alteração no parâmetro do modelo interno. Se oparâmetro do modelo interno é inferior a um patamarnegativo, o valor k é reduzido (dentro de seus limitesadmissíveis). Essa adaptação deveria produzir maiscoeficientes diferentes de zero. Por outro lado, se oparâmetro do modelo exceder um patamar positivo, o valor ké elevado (dentro dos limites admissíveis). A ditaadaptação deve produzir poucos coeficientes diferentes dezero. Caso contrário, o valor k permanece inalterado.

Mais uma vez, conforme indicado nas ações 910,980, o processo de adaptação é repetido separadamente paracada canal e sub-banda dos dados, tais como separadamentepara os canais de luminância e crominância.

0 processo de adaptação exemplificativo 900 éobservado com mais detalhes na relação de pseudocódigo 1000apresentada nas Figuras 10 e 11.

3. CODIFICAÇÃO DE ENTROPIA EFICIENTE

3.1 MÉTODOS DA TÉCNICA ANTERIOR

Em diversos padrões de codificação, o processo decodificação dos blocos de transformação se reduz àcodificação de uma seqüência de coeficientes. Um exemplo dadita seqüência é dada na Figura 12 como exemplo decoeficientes de transformação 1200. No exemplo 1200, oscoeficientes CO, Cl, C2, C3 e C4 representam quatro valoresde coeficientes diferentes de zero (tanto de sinal positivoquanto de sinal negativo) enquanto os outros coeficientesna série apresentam valor igual a zero.

Determinadas propriedades são tradicionalmentecaracterísticas da dita seqüência de coeficientes detransformação:

• O número total de coeficientes é tipicamentedeterminista e é dado pelo tamanho da transformação.

• Segundo a probabilidade, um grande número decoeficientes é zero.

• Pelo menos um coeficiente é diferente dezero. No caso de todos os coeficientes serem iguais a zero,o caso é tipicamente sinalizado através de padrão de blococodificado, assim como descrito em Srinivasan, Pedido N0U.S. T DB, "Non-Zero Coefficient Block Pattern Coding",depositado em 12 de agosto de 2005.

· Segundo a probabilidade, coeficientesdiferentes de zero e com valores maiores ocorrem no inicioda seqüência, .e coeficientes de valor igual a zero emenores ocorrem no sentido do final da seqüência.

• Coeficientes diferentes de zero assumemvalores inteiros mínimo/ máximo conhecidos.

Inúmeras técnicas de codificação se beneficiam dofato de que os coeficientes de valor igual a zero, quetipicamente ocorrem com menor freqüência, podem sercodificados com códigos de comprimento de execução.Entretanto, quando a imagem de entrada que está sendocodificada apresenta dados de elevada variação dinâmica(por exemplo, maior do que 8 bits) ou quando o parâmetro dequantização é igual a uma unidade ou é pequeno, poucoscoeficientes de transformação são zero, conforme discutidoabaixo. Na dita situação, a codificação adaptativa e astécnicas de decodificação descritas acima podem serutilizadas para condicionar os dados de modo que os dadoscondicionados apresentem essas características. Outrastécnicas também podem produzir conjuntos de coeficientes detransformação semelhantes àqueles da exemplificação decoeficientes de transformação 1200 através de outros meios,como, por exemplo, ao ajustar um nível elevado dequantização.

A Figura 12 também ilustra dois métodos decodificar coeficientes de transformação como os daexemplificação dos coeficientes de transformação 1200.Esses métodos se beneficiam da codificação conjunta de umaseqüência de zeros junto com o coeficiente diferente dezero seguinte visando proporcionar um beneficio àcodificação. A exemplificação de codificação 2D 1220demonstra uma técnica para o dito modelo de codificação denível de seqüência. Conforme ilustrado pela exemplificação1220, na . codificação 2D uma seqüência de coeficientesdiferentes de zero (sendo a seqüência de comprimento zeroou positivo) é codificada junto como um símbolo 1225 com ocoeficiente diferente de zero seguinte na série decoeficientes de transformação; no caso ilustrado o símbolo<0, C0> indica que não há zeros antecedendo o coeficientediferente de zero CO. Um símbolo especial 1235 denominada"final do bloco", ou BOB, é empregado para sinalizar aúltima série de zeros. Essa codificação é tipicamentedenominada codificação 2D porque cada símbolo codifica emconjunto a seqüência (a seqüência de coeficientes com valorigual a zero) e o nível (o valor do coeficiente diferentede zero) e, portanto, apresenta dois valores, e pode serinterpretado como uma codificação de duas dimensões dosdados de coeficiente de transformação. Esses símbolos,então, podem ser codificados por entropia, utilizando oscódigos Huffman ou a codificação aritmética e são enviadosao fluxo de bits comprimidos 420 da Figura 4.

Outro modelo de codificação alternativo é acodificação 3D, cuja exemplificação é ilustrada naexemplificação 1240. Na codificação 3D, a seqüência dezeros é tipicamente codificada em conjunto com ocoeficiente seguinte diferente de zero, da mesma forma quena codificação 2D. Ainda, um elemento de dados booleano,"último", que indica se esse coeficiente diferente de zeroé o último coeficiente diferente de zero no bloco, écodificado. O simbolo 1245, portanto, codificaconjuntamente a seqüência, o nivel e o último; no casoilustrado o simbolo <2, Cl, não último> indica que doiszeros antecedem o coeficiente diferente de zero Cl, e quenão é o último coeficiente diferente de zero na série. Umavez que todos esses elementos podem adotar livremente todosos valores, o simbolo codifica três dimensõesindependentes, originando o nome "codificação 3D".

Cada uma dessas técnicas apresenta vantagensisoladas. Cada simbolo na técnica de codificação 2Dapresenta entropia menor do que o simbolo usado nacodificação 3D, porque a primeira transmite menosinformações do que a última. Assim, o número de possiveissímbolos em um dado modelo de codificação 3D será duasvezes maior do que para um modelo comparável de codificação2D, o que eleva o tamanho da tabela de código, e podedesacelerar a codificação e a decodificação do modelo decodificação 3D. Entretanto, na codificação 2D. um símboloadicional é enviado para sinalizar o fim do bloco, e édispendioso requerer o envio de um símbolo adicionalinteiro, da perspectiva do tamanho do fluxo de bits. Defato, na prática, a codificação 3D é mais eficiente do quea codificação 2D, apesar dos tamanhos maiores das tabelasde código.3.2 CODIFICAÇÃO 3 1/2D - 2 1/2D

Enquanto as técnicas anteriores ilustradas naFigura 12 utilizam a codificação conjunta de níveis decoeficiente diferentes de zero junto com as seqüênciasanteriores de zeros, pode ser demonstrado que a seqüênciade zeros posteriores aos coeficientes diferentes de zeroapresenta forte correlação com a magnitude do coeficientediferente de zero. Essa propriedade sugere a utilidade donível de codificação conjunta e da seqüência seguinte.

A Figura 13 demonstra uma dita técnicaalternativa de codificação que aprimora as técnicas de 2D ede 3D esquematizadas na Figura 12. A Figura 13 ilustra umaexemplificação 1340 de um modelo de codificação que utilizaa idéia de codificar seqüências sucessivas de zero com ointuito de criar símbolos destinados a uma sérieexemplificativa de coeficientes de transformação 1300. AFigura 13 ilustra que os coeficientes são codificados emconjunto em símbolos 1355, que contém o valor de umcoeficiente diferente de zero junto com o comprimento daseqüência de zeros que sucedem o coeficiente diferente dezero (se houver algum) como um par; <nível, seqüência>.Assim, o símbolo ilustrado 1355, <C1, 4> codifica emconjunto o coeficiente diferente de zero Cl e os quatrocoeficientes de valor igual a zero que o sucedem.

Além de se beneficiar da forte correlação entreos coeficientes diferentes de zero e as seqüências de zerossucessivos, esse método proporciona uma vantagem adicionalquando um coeficiente diferente de zero é o últimocoeficiente diferente de zero no bloco, utilizando um valorespecial de seqüência para sinalizar que o coeficientediferente de zero é o último na série. Assim, nacodificação conjunta de um símbolo, a informação que éenviada é um valor de nível e um outro valor que indicatanto o comprimento de uma seqüência de zeros quanto o"último" valor. A Figura 13 ilustra essa situação atravésdo símbolo 1365, <C4, último>, que compreende um valor denível e um "último" valor mais do que o comprimento de umaseqüência. Pelo fato dessas diferentes situações seremcodificadas no mesmo lugar de um símbolo, a seqüência e o"último" não são independentes; apenas um é enviado porsímbolo. Assim, a dimensionalidade do símbolo não é 2 nem3, mas algo entre esses dois valores. Essa codificação édenominada "codificação 2 W. Esse elemento da codificação 2 H D não énecessariamente requerido no modelo de codificação conjuntaque associa níveis e seqüências sucessivas; em umaimplantação alternativa, o símbolo final transmitidopoderia simplesmente codificar o comprimento da seqüênciafinal de zeros, embora isso pudesse ser indesejável porquepoderia aumentar sobremaneira o tamanho do fluxo de bitscodificado. Em outra alternativa, um símbolo EOB,semelhante ao utilizado na codificação 2D, poderia serutilizado. No entanto, assim como na codificação 3D, autilização de um "último" valor na codificação 2H D admiteuma vantagem sobre a codificação 2D, não há necessidade dese codificar um símbolo extra para denotar o fim do bloco.Adicionalmente, a codificação 2^ D, admite vantagens sobrea codificação 3D (1) a entropia de cada símbolo da primeiraé inferior à da última e (2) o modelo da tabela de códigoda primeira é mais simples do que a última. As duasvantagens decorrem do fato da codificação 2H D apresentarmenores possibilidades do que a codificação 3D.

No entanto, apenas a codificação D não podedescrever uma seqüência completa de coeficientes detransformação porque não fornece uma maneira de enviar umcomprimento de seqüência antes do primeiro coeficientediferente de zero. Conforma ilustra a Figura 13, para essafinalidade, um símbolo especial 1375 é utilizado, quecodifica adicionalmente o comprimento da primeira seqüênciade zeros. Isso torna o primeiro símbolo uma codificaçãoconjunta da first_run, nível e (seqüência OU último). NaFigura 13, o primeiro símbolo 1375, <0, CO, 2> envia aprimeira seqüência (que é zero), o nível do primeirocoeficiente diferente de zero e a segunda seqüência (que é2, e o primeiro coeficiente diferente de zero não é oúltimo coeficiente diferente de zero no bloco). Pelo fatodesse símbolo compreender uma dimensão adicional, acodificação é mencionada como "codificação 3^ D".

Embora a informação extra na codificação 3H Dpossa parecer, ao primeiro olhar, negar algumas dasvantagens da codificação 2H D, o manuseio distinto doprimeiro símbolo é realmente vantajoso segundo aperspectiva da eficiência da codificação. Um símbolo 3H Dnecessariamente apresenta um alfabeto diferente do outro,símbolos 2H D, o que significa que ele é codificadoseparadamente de outros símbolos e não eleva a entropia de2H D.A Figura 14 mostra um processo exemplificativo1400 realizado pelo codificador 400 (Figura 4) paracodificar coeficientes de transformação de acordo com acodificação 2½ D - 3½ D. Em um meio, o processo 1400 podeser incluído como parte do processo 720 da Figura 7 paracodificar coeficientes normalizados. Em outro, o processo1400 pode ser utilizado para codificar coeficientes detransformação que foram quantificados por meio de técnicastradicionais. Em numerosas implantações do processo 1400,as ações podem ser removidas, combinadas ou fragmentadas emsub-ações.

O processo principia pela ação 1420, onde oprimeiro coeficiente de transformação diferente de zero éidentificado. Em seguida, na ação 1430, um símbolo 3h D écriado a partir do comprimento inicial da seqüência dezeros (que tanto poderia apresentar comprimento 0 quantocomprimento positivo) e o primeiro coeficiente diferente dezero. Nesse ponto, o símbolo 3h D não está completo. Aseguir, o processo atinge a ação decisiva 1435, ondedetermina se o coeficiente diferente de zero que éatualmente identificado é o último coeficiente diferente dezero na série de coeficientes de transformação. Se esse foro último coeficiente diferente de zero, o processo continuaaté a ação 1480, onde o "último" indicador é inserido nosímbolo, em vez de ser inserido na seqüência de zerossucessivos. Esse processo, então, codifica o símbolo usandoa codificação de entropia na ação 1490, e o processo éfinalizado. Um exemplo do dito processo de codificação desímbolos é dado abaixo, com referência à Figura 16.Se, entretanto, o processo determinar na açãodecisiva 1435 que esse não é o último coeficiente diferentede zero, então, na ação 1440 o comprimento da seqüênciasucessiva de zeros (que pode ser 0 ou um número positivo) éinserido no símbolo e o símbolo é codificado na ação 1450.Um exemplo do dito processo de codificação de símbolos édado abaixo com referência à Figura 16. Em seguida, oprocesso identifica o próximo coeficiente diferente de zerona ação 1460, cuja existência é conhecida porque ocoeficiente diferente de zero anterior foi determinado comonão sendo o último. Na ação 1470, um símbolo D é entãocriado utilizando esse coeficiente diferente de zero. Nessemomento, como o símbolo 3H D acima, o símbolo ainda nãoestá completo. Então, na ação decisiva 1435, o processodetermina se o atual coeficiente diferente de zero é oúltimo da série. Se assim for, o processo continua até aação 1480, onde o "último" indicador é incluído e o símboloé codificado. Caso contrário, o processo retorna à ação1440, onde a próxima seqüência de zeros é incluída, osímbolo é codificado e o processo continua com o próximocoeficiente diferente de zero.

3.3 INFORMAÇÕES DO CONTEXTO

Além de codificar símbolos de acordo com ascodificações D e 3H D, inúmeras partes da informaçãocausai podem ser utilizadas para criar um contexto para osímbolo que é codificado. Esse contexto pode ser utilizadopelo codificador 400 (Figura 4) ou pelo decodificador 500(Figura 5) para indexar em uma de uma coleção de tabelas decodificação de entropia para codificar e decodificar osímbolo. Aumentar o número de contextos proporciona maiorflexibilidade ao codec para adaptar, ou para usar tabelastalhadas para cada contexto específico. No entanto, asdesvantagens de se definir um grande número de contextossão que (1) há diluição do contexto (em que cada contextose aplica apenas a um pequeno número de símbolos, reduzindoassim a eficiência da adaptação) e (2) maior número detabelas de código significa maior complexidade erequerimentos de memória. Com esses pontos em mente, o modelo do contextodescrito no presente é escolhido para consultar trêsfatores com o intuito de determinar que contexto éescolhido para cada símbolo. Em uma implantação, esses trêsfatores são (1) o nível de transformação - se atransformação é interna, intermediária ou externa, (2) seos coeficientes são dos canais de luminância e crominânciae (3) se houve alguma interrupção na seqüência de zerosdentro da série de coeficientes. Nas implantaçõesalternativas, um ou mais desses fatores podem ser usadospara determinar o contexto da codificação, e/ou outrosfatores podem ser considerados.

Assim, por meio de (1), uma transformação internaemprega um conjunto diferente de tabelas de código do queuma transformação intermediária, que emprega um conjuntodiferente de tabelas de código do que uma transformaçãoexterna. Em outras implantações, os modelos do contextopodem apenas diferenciar entre dois níveis detransformação. De forma análoga, por meio de (2) oscoeficientes de luminância empregam um conjunto diferentede tabelas de código do que os coeficientes de crominância.Ambos os fatores desse contexto não se modificam dentro deum dado conjunto de coeficientes de transformação.

No entanto, o fator (3) varia dentro de umconjunto de coeficientes de transformação. A Figura 15ilustra três séries exemplificativas de coeficientes detransformação que melhor ilustram essa mudança de contexto.Em todas as três séries 1500, 1520 e 1540, coeficientesdiferentes de zero são representados por letras.

Como os três exemplos ilustram, o primeirosímbolo em um bloco, sendo um símbolo 3H D énecessariamente codificado com uma tabela diferente do queos outros símbolos, porque seu alfabeto é diferente dosoutros. Esse forma um contexto "natural" para o primeirosímbolo. Assim, o coeficiente A, sendo o primeirocoeficiente diferente de zero de todos os três exemplos, écodificado com um código 3h D. Adicionalmente, pelo fato dosímbolo 3Ή D codificar as seqüências de zero anteriores eseguintes em torno do· primeiro coeficiente diferente dezero, os dois primeiros coeficientes do exemplo 1520 (A, 0)e os dois primeiros coeficientes do exemplo 1540 (0, A) sãocodificados em conjunto em um símbolo 3h D. Em funçãodisso, em uma implantação, o fator (3) não pode seraplicado na determinação do contexto dos símbolos 3Ή D.

Em contrapartida, os símbolos 21/2D sãocodificados diferentemente dependendo do fator (3). Assim,no exemplo 1500, pode ser observado que pelo fato de nãohaver interrupção na seqüência de coeficientes diferentesde zero até depois do coeficiente D, os coeficientes B, C eD (assim como os zeros seguintes ao D) são codificados como primeiro modelo do contexto. No entanto, os zeros após oD constituem uma interrupção na seqüência de coeficientesdiferentes de zero. Portanto, os coeficientes restantes E,F, G, H (e todos os que se seguirem) . . . são codificadosusando o segundo modelo do contexto, o que significa que,enquanto cada coeficiente diferente de zero e de A écodificado com um símbolo 2H D, diferentes tabelas decódigo serão usadas para os coeficientes B, C e D (equaisquer seqüências associadas com valor zero) do queserão usadas para os coeficientes E, F, G e H.

Por outro lado, no exemplo 1520, há umainterrupção entre A e Β, o que constitui uma interrupção naseqüência de coeficientes diferentes de zero e, portanto, ocoeficiente B e todos os coeficientes subseqüentes sãocodificados com o segundo modelo do contexto. De formaanáloga, no exemplo 1540, há uma interrupção antes de A.Assim, como no exemplo 1520, os coeficientes B, C, D... sãocodificados com o segundo modelo do contexto. A Figura 16 mostra um processo exemplificativo1600 realizado pelo codificador 400 (Figura 4) paracodificar um símbolo. Em uma implantação, o processo 1600realiza o processo das ações 1450 e 1490 do processo 1400(Figura 14). Em diversas implantações do processo 1600, asações podem ser removidas, combinadas ou fragmentadas emsub-ações. O processo se inicia na ação decisiva 1605, ondeo codificador determina se o símbolo é um símbolo 3H D. Seassim for, o processo prossegue até a ação 1610, onde osímbolo é codificado utilizando a tabela D e o processoé finalizado. Em várias implantações o símbolo pode sercodificado através da codificação de entropia, tal como acodificação de Huffman ou a codificação aritmética. Comoalternativa outros modelos de codificação podem serutilizados.

Se o símbolo não for um símbolo de D, oprocesso prossegue até a ação decisiva 1615, onde ocodificador determina se pelo menos um zero antecedeu ocoeficiente diferente de zero que é. codificadoconjuntamente no símbolo. Caso contrário, o processopersiste até a ação 1620, onde o símbolo é codificado pormeio das tabelas de código D a partir do primeiro modelodo contexto e o processo é finalizado. Se tiver havido umainterrupção, então na ação 1630 o símbolo é codificadousando as tabelas de código D a partir do segundo modelodo contexto e o processo é finalizado.

3.4 REDUÇÃO DO TAMANHO DA TABELA DE CÓDIGO

Enquanto as técnicas descritas acima são maiseficientes em relação às técnicas tradicionais, elas aindanão são capazes, por si próprias, de reduzirsignificativamente o tamanho da tabela de código. Astabelas de código criadas para as técnicas deveriam sercapazes de transmitir todas as combinações (max_level χ(max_run + 2)) para os símbolos 2H D e (max_level χ(max_run +1) χ (max_run + 2)) para os símbolos D, onde omax_level é o valor máximo (absoluto) de um coeficientediferente de zero e max_run é o comprimento máximo possívelde uma seqüência de zeros. O valor (max_run +1) é derivadopara a seqüência inicial do símbolo de 3H D porque osvalores possíveis para uma seqüência de seqüência de zerosde 0 para série_máx, para um total de (max_run + 1) . Demodo idêntico, cada símbolo codifica uma seqüênciasucessiva de zeros de comprimento entre 0 e max_run, assimcomo um último símbolo, para um total de valores (max_run+2) . Mesmo com codificação de escape (onde símbolos queocorrem raramente são agrupados em um ou múltiplos meta-símbolos sinalizados através de códigos de escape), ostamanhos das mesas de código podem ser formidáveis. A fim de reduzir ainda mais o tamanho das tabelasde código, as técnicas descritas acima podem ser ainda maisrefinadas. Primeiro cada seqüência e cada nível éfragmentado em um par de símbolos:

seqüência = nonZero_run ( + sériel)nível = nonOne_level (+ nívell)

Nesse par de símbolos, os símbolos nonZero_run enonOne_level são booleanos, indicando respectivamente se aseqüência é maior que zero, e o valor absoluto é maior que1. Os valores sequêncial e nívell são usados apenas quando- os booleanos são verdadeiros, e indicam a série (entre 1 emax_run) e o nível (entre 2 e o max_level ). No entanto,pelo fato do caso do "último" também precisar sercodificado, o valor (seqüência OU último) de qualquerseqüência sucessiva de zeros em um símbolo codificado emconjunto é enviado como um símbolo ternáriononZero_run_last, que assume o valor 0 quando a seqüênciaapresenta comprimento igual a zero, 1 quando a seqüênciaapresenta comprimento diferente de zero e 2 quando ocoeficiente diferente de zero do símbolo for o último dasérie.

Portanto, para utilizar essa codificaçãoreduzida, o primeiro símbolo D assume a forma<nonZero_run, nonOne_level, nonZero_run_last>. Isso cria umalfabeto de tamanho 2 χ 2 χ 3 = 12. Os símbolossubseqüentes 2H D assumem as formas <nonOne_level,nonZero_run_last> criando um alfabeto de tamanho 2x3=6.Em uma implantação, a sériel também é denominada NonzeroRune o nível 1 é denominado SignificantLevel.

Pelo fato do índice conter apenas informaçõessobre se os níveis e seqüências são significantes, pode sernecessário enviar informações adicionais com os símbolos afim de permitir que um decodificador recrie com precisãouma série de coeficientes de transformação. Assim, apóscada símbolo do índice, se o nível for um nívelsignificante, o valor do nível é separadamente codificado eenviado após o símbolo. Da mesma forma, se um símboloindicar que uma seqüência de zeros apresenta um comprimentodiferente de zero (positivo), aquele comprimento écodificado separadamente e enviado após o símbolo.

A Figura 17 ilustra um exemplo de uma codificaçãoreduzida 2M. D- 2H D 1740 que representa uma sérieexemplificativa 1700 de valores absolutos de coeficientesde transformação. Os sinais dos coeficientes detransformação podem ser codificados em outro lugar.Conforme ilustra a figura 17, a série exemplificativa doscoeficientes 1700 começa com "5, 0, 0". Na 3^ D-2^ D nãoreduzida, assim como naqueles ilustrados acima, o primeirosímbolo seria então <0, 5, 2>. No entanto, na codificaçãoreduzida, a Figura 17 ilustra um primeiro símbolo 1745 doíndice <0, 1, 1>. Esse símbolo indica que não há zerosantes do primeiro coeficiente diferente de zero, que oprimeiro coeficiente diferente de zero apresenta valorabsoluto maior do que 1, e que há pelo menos um zero depoisdesse coeficiente diferente de zero. A esse símbolo segue-se o valor SignificantLevel "level_5" (1755), indicando queo valor absoluto do coeficiente diferente de zero é 5, e umvalor NonzeroRun "run_2" (1765), que indicam a existênciade dois zeros depois do coeficiente. Por outro lado, osímbolo 1775, <0, 0>, que indica a existência de umcoeficiente diferente de zero de valor absoluto 1 seguidopor valores diferentes de zero, não requer que outrosvalores o sucedam para fornecer informações.

Em função de alguns símbolos requererem o enviode informações adicionais após os mesmos, os símbolos doíndice deveriam ser analisados para determinar seinformações adicionais deveriam ser enviadas junto deles. AFigura 18 apresenta um processo exemplificativo 1800realizado pelo codificador 400 (Figura 4) com o intuito dedeterminar que informação está contida em um símbolo doíndice 3H D e de enviar informações adicionais, casoapropriado. Em diversas implantações do processo 1800,ações podem ser removidas, combinadas ou fragmentadas emsub-ações. Na descrição dos símbolos para a Figura 18, ovalor "x" é um marcador de posição, representando qualquervalor possível para aquela porção particular de um símbolo.0 processo começa na ação 1810, onde o primeiro símbolocodificado é enviado. A seguir, na ação decisiva 1820, ocodificador determina se o símbolo é da forma <x, 1, x>, oque significa perguntar se o coeficiente diferente de zerorepresentado pelo símbolo adota um valor absoluto superiora 1. Se o codificador estipular que esse é o caso, o valordo coeficiente diferente de zero é codificado e enviado naação 1830. É importante ressaltar que, enquanto a Figura 18não discute explicitamente a codificação do sinal de umcoeficiente diferente de zero, esse sinal poderia serincluído em diversos pontos no processo 1800. Em numerosasimplantações, isso poderia envolver enviar o sinalimediatamente a seguir do símbolo de codificação conjunta,dentro do símbolo de codificação conjunta, e/ou junto dovalor absoluto do nível.

Independente da determinação na ação 1820, naação decisiva 1840, o codificador determina se o símboloadota a forma <1, x, x>. Essa determinação eqüivale aperguntar se o coeficiente diferente de zero representadopelo símbolo apresenta qualquer zero que o preceda. Seassim for, na ação 1850, o codificador codifica ocomprimento da seqüência de zeros que precede o coeficientediferente de zero e envia esse valor.

A seguir, na ação decisiva 1860, o codificadorconsidera que o valor de t onde o símbolo for <x, x, t>.Essa determinação eqüivale a perguntar se o coeficientediferente de zero representado pelo símbolo apresentaquaisquer zeros que o sucedam. Se t=0, então o codificadorsabe que não há zeros que o sucedam, e continua a enviarmais símbolos na ação 1880 e o processo 1800 é finalizado.Em uma implantação, o processo 1900 da Figura 19 começa,então, pelo próximo símbolo. Se t=l, o codificador entãocodifica e envia o comprimento da seqüência de zeros quesucedem o coeficiente diferente de zero na ação 1870, eentão continua a enviar símbolos na ação 1880 e o processo1800 é finalizado. No entanto, se t=2, o codificador sabeque o coeficiente diferente de zero representado pelosímbolo é o último (e único) na série, e assim o blocorepresentado pelos coeficientes de transformação estácompleto. Assim, o processo 1800 é finalizado e o próximobloco pode ser transformado e codificado, se aplicável.

A Figura 19 apresenta um processo exemplificativo1900 realizado pelo codificador 400 (Figura 4) paradeterminar que informação está contida em um símbolo deíndice 2H D e para enviar informações adicionais, seapropriado. Em diversas implantações do processo 1900,ações podem ser removidas, combinadas ou fragmentadas emsub-ações. Assim como na Figura 18, na Figura 19, o valor"x" é um marcador, representando qualquer valor possívelpara aquela porção particular do símbolo. 0 processo iniciana ação 1910, onde o próximo símbolo codificado é enviado.A seguir, na ação decisiva 1920, o codificador determina seo símbolo é da forma <1, x>, o que eqüivale a perguntar seo coeficiente diferente de zero representado pelo símboloadota um valor absoluto superior a 1. Se o codificadordeterminar que esse é o caso, o valor do coeficientediferente de zero é codificado e enviado na ação 1930.Assim como no processo 1800, é importante ressaltar queenquanto a Figura 19 não discute explicitamente acodificação do sinal de um coeficiente diferente de zero,esse sinal poderia ser incluído em diversos pontos doprocesso 1900.

A seguir, na ação decisiva 1940, o codificadorconsidera o valor de t onde o símbolo for <x, t>, o queeqüivale a perguntar se o coeficiente diferente de zerorepresentado pelo símbolo apresenta zeros que o sucedam. Set=0, então o codificador reconhece que não há zeros osucedendo, e continua a enviar mais símbolos na ação 1960 eo processo 1900 é finalizado. Em uma implantação, oprocesso 1900 da Figura 19 então repete para o próximosímbolo. Se t=l, o codificador então codifica e envia ocomprimento da seqüência de zeros que sucedem o coeficientediferente de zero na ação 1950, e então continua a enviarsímbolos na ação 1960 e o processo 1900 é finalizado. Noentanto, se t=2, o codificador reconhece que o coeficientediferente de zero representado pelo símbolo é o último dasérie e, portanto, o bloco representado pelos coeficientesde transformação está completo. Assim, o processo 1900 éfinalizado e o próximo bloco pode ser transformado ecodificado, se aplicável.

3.5 EFICIÊNCIAS ADICIONAIS

Além do tamanho da redução da tabela de códigodiscutida acima, um benefício proporcionado pelainterrupção dos símbolos da seqüência e do nível é que, emseguida à transmissão do símbolo conjunto D, odecodificador pode determinar a existência ou não de zerosorientadores. Isso significa que a informação do contextodescrevendo se o primeiro ou o segundo modelo do contextose mantém é reconhecida no lado do decodif icador econstitui um contexto válido para codificar o valor donivell do primeiro coeficiente diferente de zero. Isso querdizer que os contextos que aplicam ao nivell valores dossímbolos de 2H D podem aplicar igualmente ao nivell valoresde símbolos 3Ή D, mesmo enquanto os símbolos do índicecodificados conjuntamente utilizam alfabetos diferentes.

Mais ainda, uma vez que o número total decoeficientes de transformação em um bloco é um númeroconstante, cada seqüência sucessiva é delimitada por umaseqüência monotônica decrescente. Em uma implantaçãopreferida, essa informação é explorada na codificação devalores da seqüência. Por exemplo, uma tabela de códigopode incluir um conjunto de códigos de valor da seqüênciapara seqüências que começam na primeira metade de umconjunto de coeficientes e um conjunto diferente paraseqüências que começam na segunda metade. Pelo fato docomprimento de qualquer seqüência possível que se inicia nasegunda metade ser necessariamente menor do que oscomprimentos possíveis de seqüências que iniciam naprimeira metade, o segundo conjunto de códigos não devemser grandes, reduzindo a entropia e aperfeiçoando odesempenho da codificação.

Outras informações podem ser coletadas por meioda observação cautelosa do posicionamento dos coeficientes.Por exemplo, se o coeficiente diferente de zerorepresentado por um símbolo ocorrer na última posição nasérie de coeficientes, então "último" sempre é verdadeiro.De forma semelhante, se o coeficiente diferente de zerorepresentado por um símbolo ocorrer na penúltima posição doarranjo, então, tanto o "último" é verdadeiro quanto aseqüência sucessiva é zero. Cada uma dessas observaçõespermite a codificação através de tabelas mais curtas.

3.6 EXEMPLIFICAÇÃO DA IMPLANTAÇÃO DO ÍNDICE0 primeiro índice possui um alfabeto de tamanho12. Em uma implantação, cinco tabelas de Huffman estãodisponíveis para esse símbolo, que é definido comoFirstIndex= a + 2b + 4c, onde o símbolo é <a, b, c>, sendoque a e b assumem valores 0 ou 1 e c assumem valores 0, 1ou 2. Uma implantação dos comprimentos da palavra códigopara os doze símbolos relativos a cada uma das tabelas édado abaixo. Os procedimentos para a construção do códigopadrão de Huffmann podem, em uma implantação, ser aplicadosde forma a originar esses conjuntos de palavras código pré-determinadas.

Tabela 1: 5,6,7,7,5,3,5,1,5,4,5,3Tabela 2: 4,5,6,6,4,3,5,2,3,3,5,3Tabela 3: 2,3,7,7,5,3,7,3,3,3,7,4Tabela 4: 3,2,7,5,5,3,7,3,5,3,6,3Tabela 5: 3,1,7,4,7,3,8,4,7,4,8,5

Os símbolos subseqüentes de índice possuem umalfabeto de tamanho 6. Em uma implantação, o índice édefinido como índice = a + 2b, onde o símbolo é <a,b> e ébooleano, e b pode assumir valores de 0, 1 ou 2. Quatrotabelas de Huffmann são definidas para o índice, conformedemonstrado abaixo:

Tabela 1: 1,5,3,5,2,4Tabela 2: 2,4,2,4,2,3Tabela 3: 4,4,2.2,2,3Tabela 4: 5,5,2,1,4,3

Além disso, em uma implantação, com o objetivo dese beneficiar de algumas das informações descritas na Seção3.5 acima, quando o coeficiente está posicionado na últimadisposição do arranjo, um código de um bit (definido por a)é usado (b é unicamente 2 nesse caso). Em uma implantação,quando o coeficiente ocupa a penúltima posição, um códigode 2 bits é utilizado, visto ser conhecido que b#l.

Uma implantação dos códigos SignificantLevelcodifica o nivel utilizando um procedimento denominado"binning", que fragmenta uma gradação de níveis em setebins. Os níveis dentro de um bin são codificados a partirde códigos de comprimento fixo, e os bins em si sãocodificados utilizando os códigos de Huffman. Isso pode serefetuado, em uma implantação, através das técnicas deagrupamento descritas acima. Da mesma forma, em umaimplantação, NonzeroRun é codificado empregando umprocedimento de "binning" que indexa em cinco bins com basena localização do símbolo atual.

3.7 SÍMBOLOS DE DEC0DIFICAÇÃ0 D - D OU

DECODIFICANDO SÍMBOLOS 3 1/2D - 2 1/2D?

A Figura 20 apresenta um processo exemplificativo2000 efetuado pelo decodificador 500 (Figura 5) visandodecodificar uma série de símbolos em coeficientes detransformação. Em várias implantações do processo 2000, asações podem ser removidas, combinadas ou fragmentadas emsub-ações. Mais ainda, as ações podem ser definidas com oobjetivo de manipular as condições de erro semelhantesàquelas acionadas pelo fluxo de bits corrompido. 0 processose inicia na ação 2010, onde o decodificador recebe oprimeiro símbolo codificado em conjunto e o decodificautilizando a tabela de código D. A seguir, na ação 2020,os coeficientes de transformação são ocupados com base nosímbolo decodificado (inclusive qualquer informação deseqüência ou nível também presente no fluxo de bitscomprimido). Uma implantação dessa ação é descrita em maiordetalhe abaixo em relação à Figura 21. 0 processo continuaaté a ação decisiva 2030, onde o decodificador determina seo símbolo indica se esse se refere ao último coeficientediferente de zero. Se assim for, o processo continua até aação 2090, onde quaisquer coeficientes residuais nãoocupados são ocupados com valores iguais a zero e oprocesso 2000 é finalizado. Se o símbolo não se refere ao último coeficientediferente de zero, o processo continua até a ação decisiva2040, onde o decodificador determina se algum coeficientediferente de zero foi indicado por qualquer símbolo até omomento. Em caso negativo a ação prossegue até a ação 2050,onde o próximo símbolo é recebido e decodificado empregandoas tabelas de código 2H D em seguida ao primeiro modelo docontexto. Se, em vez disso, os coeficientes zero tiveremsido indicados na ação decisiva 2040, no processo 2060, odecodificador recebe e decodifica o próximo símboloempregando tabelas de código 2^ D em seguida ao segundomodelo do contexto. Independente de qual modelo do contextofoi utilizado, o processo então continua até a ação 2070,onde os coeficientes de transformação são preenchidos combase no símbolo decodificado (inclusive qualquer informaçãode seqüência ou nível também presente no fluxo de bitscomprimido). De forma idêntica à ação 2020, uma implantaçãodessa ação é descrita em maior detalhe abaixo em relação àFigura 21. O processo continua até a ação decisiva 2080,onde o decodificador determina se o símbolo indica que essese refere ao último coeficiente diferente de zero. Casocontrário, o processo retorna à ação decisiva 2040 e serepete. Se assim for, o processo continua até a ação 2090,onde quaisquer coeficientes não ocupados são ocupados comvalores iguais a zero, e o processo 2000 é finalizado.

A Figura 21 apresenta um processo exemplificativo2100 efetuado pelo decodificador 500 (Figura 5) para ocuparcoeficientes de transformação. Em numerosas implantações doprocesso 2100, as ações podem ser removidas, combinadas oufragmentadas em sub-ações. Na medida em que o processo 2100é configurado para decodificar símbolos codificados deacordo com as técnicas da Seção 3.4 acima, nas implantaçõesalternativas, os valores de nível e os comprimentos daseqüência podem ser incluídos em símbolos 2H D e 3H D, quepoderiam permitir que o processo 2100 fosse simplificado. Oprocesso se inicia na ação decisiva 2010, onde odecodificador determina se o símbolo é um símbolo D. Emcaso negativo, o processo salta para a ação decisiva 2140,descrita abaixo. No entanto, se o símbolo for um símbolo 3HD, o decodif icador determina na ação decisiva 2120 se osímbolo indica uma seqüência inicial de comprimentopositivo de coeficientes de valor igual a zero. Isso podeser feito determinando se o valor de nonZero_run no símboloD é 1, indicando uma seqüência de comprimento positivo,ou 0, indicando uma seqüência de comprimento igual a zero.Se o símbolo indicar uma seqüência de comprimento positivode coeficientes de valor igual a zero, o processo continuaaté a ação 2130, onde o comprimento da seqüência édecodificado, com base no nivell codificado em seguida aosímbolo D, e os coeficientes iniciais de transformaçãosão ocupados com zero de acordo com o comprimento daseqüência.

A seguir, o processo continua até a ação decisiva2140, onde o decodificador determina se o símbolo indicaque seu coeficiente diferente de zero apresenta valoresabsolutos maiores do que 1. Isso pode ser feitodeterminando se o valor de nonOne_level no símbolo é iguala 1, indicando que o nível apresenta valor absoluto maiordo que 1, ou 0, indicando que o coeficiente diferente dezero é -1 ou 1. Se o símbolo não indicar um coeficiente devalor absoluto maior do que 1, o processo continua até aação 2150, onde o próximo coeficiente é ocupado com -1 ou1, dependendo do sinal do coeficiente diferente de zero. Seo símbolo indicar um coeficiente com valor absoluto maiordo que 1, o processo, ao contrário, continua até a ação2160, onde o nível do coeficiente é decodificado e ocoeficiente é ocupado com o valor do nível, junto de seusinal. Conforme discutido acima, o sinal pode ser indicadode maneiras variadas, de forma que a decodificação do sinalnão é discutida explicitamente nas ações 2150 ou 2160.

Continuando, na ação decisiva 2170, odecodificador determina se o símbolo indica uma seqüênciasubseqüente de comprimento positivo de coeficientes iguaisa zero, o que pode ser feito determinando se o valornonZero_run_last no símbolo é igual a 1, indicando umaseqüência de comprimento positivo, ou 0, indicando umaseqüência de comprimento zero. (0 caso ondenonZero_run_last igual a 2 não é apresentado, já que essecaso é entendido no processo 2000) . Se o símbolo indicaruma seqüência de comprimento positivo de coeficientesiguais a zero, o processo continua até a ação 2180, onde ocomprimento da seqüência é decodificado, com base nasequêncial codificada em seguida ao símbolo, e oscoeficientes de transformação subseqüentes são preenchidoscom zeros de acordo com o comprimento da seqüência,finalizando assim o processo 2100.

4. AMBIENTE COMPUTACIONAL

O decodificador 400 (Figura 4) descrito acima, odecodificador 500 (Figura 5) e as técnicas para codificar edecodificar com eficiência os coeficientes de transformaçãopodem ser executados em uma gama de dispositivos em que oprocessamento do sinal da mídia digital é executado,incluindo, entre outros exemplos, computadores; gravação devídeo e imagem, equipamentos de transmissão e de recepção;aparelhos de reprodução de vídeo portáteis; video-conferências; e etc. As técnicas de codificação de mídiadigital podem ser implantadas em um conjunto de circuitosde hardware, assim como em software de processamento demídia digital, operando em computador ou em outro ambientecomputacional semelhantes aos apresentados na Figura 22.

A Figura 22 ilustra um exemplo generalizado de umambiente computacional adequado (2200) em que asmodalidades descritas podem ser implantadas (2200). Oambiente computacional (2200) não pretende sugerirlimitações ao escopo do uso ou da funcionalidade dainvenção, já que a presente invenção pode ser implantada emdiversos ambientes computacionais com finalidades gerais ouespecificas.

Com referência à Figura 22, o ambientecomputacional (2200) inclui pelo menos uma unidade deprocessamento (2210) e a memória (2220) . Na Figura 22, aconfiguração mais básica (2230) é incluída dentro de umalinha pontilhada. A unidade de processamento (2210) cumpreas instruções executáveis pelo computador, podendo ser umprocessador real ou virtual. Em um sistema demultiprocessamento, as unidades de multiprocessamentocumprem as instruções executáveis pelo computador visandoelevar a potência de processamento. A memória (2220) podeser uma memória volátil (por exemplo, registros, cache,RAM), uma memória não-volátil (por exemplo, ROM, EEPROM,memória flash, etc.) ou uma combinação das duas. A memória(2220) armazena o software (1280) que implanta ocodificador/decodificador descrito, assim como as técnicaseficientes de codificação/decodificação do coeficiente detransformação.

Um ambiente computacional pode apresentarelementos adicionais. Por exemplo, o ambiente computacional(2200) inclui o armazenamento (2240), um ou maisdispositivos de entrada (2250), um ou mais dispositivos desaída (2260) e uma ou mais conexões de comunicação (2270).Um mecanismo de interconexão' (não apresentado) , como umbarramento, uma controladora ou uma rede realiza ainterconexão dos componentes do ambiente computacional(2200). Tipicamente, um software de sistema em operação(não apresentado) proporciona um ambiente de operação paraoutros softwares que operam no ambiente computacional(2200), e coordena as atividades dos componentes doambiente computacional (2200) .

O armazenamento pode ser removível ou nãoremovível e inclui discos magnéticos, cassetes ou fitasmagnéticas, CD-ROMS, CD-RWs, DVDs ou outras mídias quepossam ser usadas para armazenar informações e que possamser acessadas no ambiente computacional (2200). Oarmazenamento (2240) armazena instruções para o softwareque implementa o codificador/decodificador descrito e astécnicas eficientes de codificação/decodificação docoeficiente de transformação.

0(s) dispositivo(s) de entrada (2250) podem serum dispositivo de entrada mediante o toque, como umteclado, um mouse, uma caneta ou trackball (mouse deesfera), um dispositivo de entrada de voz, um dispositivode varredura ou algum outro dispositivo que forneçaentradas ao ambiente computacional (2200). Para áudio, odispositivo de entrada (2250) pode ser uma placa de som ouum dispositivo semelhante que aceite entrada de áudio emformato analógico ou digital, ou uma leitora de CD-ROM queforneça amostras de áudio para o ambiente computacional.0(s) dispositivo(s) de saída (2260) pode ser um vídeo, umaimpressora, um alto-falante, um gravador de CD ou outrodispositivo que permita a saída a partir do ambientecomputacional (2200).

A(s) conexões de comunicação (2270) permitem acomunicação sobre uma mídia de comunicação pra outraentidade computacional. A mídia de comunicação transfereinformações como as instruções executáveis pelo computador,informações de áudio ou vídeo comprimidas, ou outros dadosem um sinal de dados modulados. Um sinal de dados moduladoé um sinal que apresenta uma ou mais de suascaracterísticas ajustadas ou modificadas de modo acodificar informações no sinal. Para fins deexemplificação, e não visando restringir, mídias decomunicação incluem técnicas com fio ou sem fio implantadascom uma portadora elétrica, óptica, RF, infravermelha,acústica ou qualquer outra.

As técnicas de processamento de mídia digital dopresente podem ser descritas no contexto geral das mídiaslegíveis por computador. A mídia legível por computador équalquer mídia disponível que pode ser acessada dentro deum ambiente computacional. Para fins de exemplificação, enão de limitação, com o ambiente computacional (2200), amídia legível por computador inclui memória (2220),armazenamento (2240), mídia de comunicação e as combinaçõesde qualquer uma das acima.

As técnicas de processamento de mídia digital nopresente podem ser descritas no contexto geral dasinstruções executáveis por computador, semelhantes àquelasincluídas nos módulos do programa, que são executadas em umambiente computacional no processador alvo real ou virtual.Geralmente, os módulos do programa incluem rotinas,programas, bibliotecas, objetos, classes, componentes,estrutura dos dados, etc. que desempenhar tarefasespecificas ou implantam tipos específicos de dadosabstratos. A funcionalidade dos módulos do programa podeser combinada ou desmembrada em módulos do programaconforme desejado em diversas modalidades. As instruçõesexecutáveis por computador para os módulos do programapodem ser executadas em um ambiente computacional local oudistribuído.

Para fins de apresentação, a descrição detalheemprega termos como "determinar", "gerar", "ajustar" e"aplicar" para descrever operações de computador em umambiente computacional. Esses termos são abstrações denível elevado para as operações executadas por computador enão devem ser confundidas com atos desempenhados por um serhumano. As operações reais do computador correspondentes aesses termos variam dependendo da implantação.

Em vista das muitas variações possíveis em tornoda matéria objeto descrita no presente, reivindicamos comosendo nossas as ditas modalidades que possam surgir dentrodo escopo das seguintes reivindicações e equivalentes àsmesmas.

Claims (20)

1. Método de codificar uma série de coeficientesde transformação (1300) representando dados de mídiasdigitais, CARACTERIZADO pelo fato de que compreende:representar (1400) a série de coeficientes detransformação como uma série de símbolos (1340), em quecada símbolo (1355) compreende uma indicação de umcoeficiente diferente de zero obtido a partir de uma sériede coeficientes de transformação e uma indicação de umcomprimento de uma seqüência subseqüente de coeficientes devalor igual a zero;para cada símbolo na série de símbolos, enviar(1600) o símbolo a ser codificado em um fluxo de bitscomprimido (420); eem que um último coeficiente diferente de zero emuma seqüência de coeficientes de transformação érepresentado por um símbolo (1365), onde a indicação de umcomprimento de uma seqüência subseqüente de coeficientes devalor igual a zero compreende um indicador de que ocoeficiente é o último coeficiente diferente de zero.

2. Método, de acordo com a reivindicação 1,CARACTERIZADO pelo fato de que o primeiro símbolo na sériede símbolos compreende adicionalmente uma indicação de umcomprimento de uma seqüência de coeficientes de valor iguala zero que precede um primeiro coeficiente diferente dezero na série de coeficientes de transformação.

3. Método, de acordo com a reivindicação 2,CARACTERIZADO pelo fato de que uma série de coeficientes detransformação resulta da determinação de uma porçãonormalizada de uma série de coeficientes de transformaçãode ampla variação.

4. Método, de acordo com a reivindicação 2,CARACTERIZADO pelo fato de que um conjunto de tabelas decódigo é utilizada para codificar o primeiro símbolo nasérie de símbolos, e um conjunto diferente de tabelas decódigo é utilizada para codificar outros símbolos na sériede símbolos.

5. Método, de acordo com a reivindicação 2,CARACTERIZADO pelo fato de que cada símbolo na série desímbolos possui um contexto relacionado.

6. Método, de acordo com a reivindicação 5,CARACTERIZADO pelo fato de que o contexto para um símbolose baseia, pelo menos em parte, em se um coeficientediferente de zero representado pelo símbolo ocorre antes oudepois de um primeiro coeficiente de valor igual a zero nasérie de coeficientes.

7. Método, de acordo com a reivindicação 5,CARACTERIZADO pelo fato de que o contexto para um símbolose baseia, pelo menos em parte, em se a série decoeficientes de transformação se destinada aos canais deluminância ou de crominância.

8. Método, de acordo com a reivindicação 5,CARACTERIZADO pelo fato de que o contexto para um símbolose baseia, pelo menos em parte, se a série de coeficientesde transformação se destina a uma transformação interna,intermediária ou externa.

9. Método, de acordo com a reivindicação 2,CARACTERIZADO pelo fato de que para cada símbolo, aindicação naquele símbolo do comprimento da seqüência decoeficientes subseqüentes com valores iguais a zerocompreende um símbolo ternário que indica uma das seguintescondições no símbolo:a seqüência de coeficientes de valor igual a zeroapresenta comprimento igual a zero;a seqüência de coeficientes de valor igual a zeroapresenta um comprimento positivo;o coeficiente indicado pelo símbolo é o últimocoeficiente na série de coeficientes de transformação.

10. Método, de acordo com a reivindicação 9,CARACTERIZADO pelo fato de que a indicação do comprimentoda seqüência de coeficientes de valor igual a zero queprecede o primeiro coeficiente diferente de zero noprimeiro símbolo na série de símbolos compreende umbooleano que indica se a seqüência de coeficientes de valorigual a zero que precede o primeiro coeficiente diferentede zero apresenta ou não comprimento igual a zero ou seapresenta comprimento positivo.

11. Método, de acordo com a reivindicação 9,CARACTERIZADO ainda pelo fato de que, quando um símbolocompreende uma indicação de que uma seqüência decoeficientes de valor igual a zero apresenta um comprimentopositivo, o comprimento da seqüência de coeficientes devalor igual a zero a ser codificada é enviado através de umfluxo de bits comprimido.

12. Método, de acordo com a reivindicação 1,CARACTERIZADO pelo fato de que, para cada símbolo, aindicação naquele símbolo do coeficiente diferente de zeroa partir da série de coeficientes de transformaçãocompreende um booleano que indica se o valor absoluto docoeficiente diferente de zero é ou não maior do que um.

13. Método, de acordo com a reivindicação 12,CARACTERIZADO ainda pelo fato de que, quando um símbolocompreende uma indicação de que um coeficiente diferente dezero apresenta um valor absoluto maior do que 1, o valorabsoluto do coeficiente diferente de zero a ser codificadodeve ser enviado através de um fluxo de bits comprimido.

14. Decodificador de mídias digitais,CARACTERIZADO pelo fato de que compreende:uma memória de armazenamento de dados (2280) paraarmazenar dados de mídias digitais codificados; eum processador (2210) configurado para:receber um conjunto de símbolos comprimidos (420)descrevendo uma série de coeficientes de transformação;descomprimir os símbolos (510); ereconstruir (520) as séries de coeficientes detransformação analisando o conjunto de símbolosdescomprimidos; eonde:o conjunto de símbolos comprimidos compreendesímbolos codificados em conjunto (1340) codificados (1600)a partir de um conjunto de tabelas de código de acordo comum modelo do contexto;cada símbolo codificado em conjunto (1355)descreve um nível diferente de zero a partir da série decoeficientes de transformação e se há coeficientes de valorigual a zero depois do nível diferente de zero.

15. Decodificador de mídias digitais, de acordocom a reivindicação 14, CARACTERIZADO pelo fato de que:cada símbolo codificado em conjunto descreve umnível diferente de zero indicando se um valor absoluto deum nível diferente de zero é maior do que 1:o conjunto de símbolos comprimidos compreendeadicionalmente símbolos de nível que descrevem o valor decada nível diferente de zero e indicações dos sinais dosímbolo; eo processador é ainda configurado para, aoanalisar um símbolo codificado em conjunto que indica umnível diferente de zero cujo valor absoluto é maior do que1, reconstruir o nível diferente de zero em uso encontrandoo símbolo do nível que descreve o valor do nível diferentede zero.

16. Decodificador de mídias digitais, de acordocom a reivindicação 14, CARACTERIZADO pelo fato de que oprimeiro símbolo no conjunto de símbolos comprimidosdescreverem adicionalmente se há coeficientes de valorigual a zero que precedem o nível diferente de zero nasérie de coeficientes de transformação.

17. Decodificador de mídias digitais, de acordocom a reivindicação 14, CARACTERIZADO pelo fato de que:cada símbolo codificado em conjunto descreve umaseqüência de coeficientes de valor igual a zero indicandose um comprimento da seqüência de coeficientes de valorigual a zero é maior do que 0;o conjunto de símbolos comprimidos compreendeainda símbolos de seqüência que descrevem o comprimento decada seqüência de coeficientes de valor igual a zero cujocomprimento é maior do que 0.

18. Uma ou mais mídias legíveis por computador,portando instruções que descrevem uma mídia digitaldecodificando um programa para executar um método dedecodificar dados de mídia digital comprimida, sendo que ométodo é CARACTERIZADO pelo fato de que compreende:receber (2000) um fluxo de bits (420) quecompreende símbolos de códigos conjuntos comprimidos (1340)codificados a partir de um conjunto de tabelas de código deacordo com um modelo do contexto;decodificar (2000) os símbolos de códigosconjuntos para determinar, para cada símbolo, um nível decoeficiente de transformação e uma seqüência decoeficientes de transformação de valor igual a zerosubseqüentes; ereconstruir (2100) um conjunto de coeficientes detransformação a partir de níveis determinados e deseqüências de coeficiente de transformação de valor igual azero.

19. Mídia legível por computador, de acordo com areivindicação 18, CARACTERIZADA pelo fato de que o fluxo debits ainda compreende um símbolo inicial de códigosconjuntos e o método ainda compreender decodificar osímbolo inicial de códigos conjuntos para determinar umaseqüência de coeficientes de transformação igual a zero, umnível de coeficiente de transformação e uma seqüência decoeficientes de transformação subseqüentes de valor igual azero.

20. Mídia legível por computador, de acordo com areivindicação 18, CARACTERIZADA pelo fato de que:os símbolos de códigos conjuntos indicam, paracada nível de coeficiente de transformação, se aquele nívelapresenta um valor absoluto superior a 1;os símbolos de códigos conjuntos indicam, paracada seqüência de coeficientes de transformação de valorigual a zero, se aquela seqüência apresenta comprimentosuperior a 0; o fluxo de bits compreende ainda símboloscomprimidos que descrevem o comprimento da seqüência decoeficientes de transformação de valor igual a zero, e osinal e a magnitude dos níveis de coeficientes detransformação; e decodificar os símbolos de códigos conjuntoscompreende:ao decodificar um símbolo de código conjuntoindicando que um nível de coeficiente de transformaçãoapresenta um valor absoluto superior a 1, determinar onível do coeficiente de transformação através dadecodificação de um ou mais símbolos no fluxo de bits queindicam o sinal e o valor do nível do coeficiente detransformação; eao decodificar um símbolo de código conjuntoindicando que uma seqüência de coeficientes de transformaçãode valor igual a zero é maior que 0, determinar ocomprimento da seqüência de coeficientes de transformação devalor igual a zero através da decodificação de um símbolo emum fluxo de bits que indica o comprimento da sucessão.