Sistema y procedimiento para comprimir un flujo de datos de valores enteros.

Procedimiento para la codificación entrópica de datos de pares de tirada/valor de datos que corresponden a un flujo de datos de valores enteros,

en el que cada tirada se codifica en una de tres maneras, comprendiendo dicho procedimiento:

clasificar cada una de dichas tiradas en función de su longitud siendo o 1, corta o larga;

si la tirada es 1, seleccionar un primer código con una longitud de 1;

si la tirada se clasifica como corta, seleccionar un primer código con una primera longitud predeterminada, cada primer código de primera longitud predeterminada teniendo un preámbulo para distinguir las otras clasificaciones de tirada, y teniendo un valor en función de la longitud de la tirada;

si la tirada se clasifica como larga, seleccionar un primer código con una segunda longitud predeterminada, cada primer código de segunda longitud predeterminada teni

endo un preámbulo para distinguir las otras clasificaciones de tirada, y teniendo un valor en función de la longitud de la tirada; y emitir el primer código seleccionado a un canal, en el que la primera longitud predeterminada es n + 1 bits, el primer código con la primera longitud predeterminada se selecciona a partir de una primera tabla de código, el primer código con la primera longitud predeterminada tiene el preámbulo para el primer bit y cuyo valor para los n bits restantes se basa en la duración de la tirada, la segunda longitud predeterminada es n + 1 + M bits, el primer código con la segunda longitud predeterminada se selecciona a partir de una segunda tabla de códigos, el primer código con la segunda longitud predeterminada teniendo el preámbulo para los primeros n + 1 bits y cuyo valor para los M bits restantes se basa en la longitud de la tirada.

Tipo: Patente Internacional (Tratado de Cooperación de Patentes). Resumen de patente/invención. Número de Solicitud: PCT/US2009/063526.

Solicitante: APPLE INC..

Nacionalidad solicitante: Estados Unidos de América.

Dirección: 1 INFINITE LOOP CUPERTINO CA 95014-2084 ESTADOS UNIDOS DE AMERICA.

Inventor/es: OSLICK,MITCHELL.

Fecha de Publicación: .

Clasificación Internacional de Patentes:

  • H03M7/40 SECCION H — ELECTRICIDAD.H03 CIRCUITOS ELECTRONICOS BASICOS.H03M CODIFICACION, DECODIFICACION O CONVERSION DE CODIGO, EN GENERAL (por medio de fluidos F15C 4/00; convertidores ópticos analógico/digitales G02F 7/00; codificación, decodificación o conversión de código especialmente adaptada a aplicaciones particulares, ver las subclases apropiadas, p. ej. G01D, G01R, G06F, G06T, G09G, G10L, G11B, G11C, H04B, H04L, H04M, H04N; cifrado o descifrado para la criptografía o para otros fines que implican la necesidad de secreto G09C). › H03M 7/00 Conversión de un código, en el cual la información está representada por una secuencia dada o por un número de dígitos, en un código en el cual la misma información está representada por una secuencia o por un número de dígitos diferentes. › Conversión en, o a partir de códigos la longitud variable, p. ej. código Shanno-Fano, código Huffman, código Morse.
  • H03M7/46 H03M 7/00 […] › Conversión en o a partir de códigos de coordenada diferencial, es decir, por representación del número de dígitos consecutivos o grupos de dígitos del mismo tipo con ayuda de una palabra código y de un dígito representativo de este tipo.

PDF original: ES-2546542_T3.pdf

 


Fragmento de la descripción:

Sistema y procedimiento para comprimir un flujo de datos de valores enteros.

ANTECEDENTES 5

Se conocen varios esquemas de codificación para codificar flujos de bits de valores enteros, en los cuales los flujos de bits pueden representar, por ejemplo, vídeos, imágenes, y demás. Los esquemas de codificación conocidos implican generalmente la codificación de longitud de tirada, codificación de longitud variable, codificación diferencial, y diversas combinaciones de los mismos. 10

Se sabe que la codificación de longitud de tirada, si bien es útil para la compresión de datos que presenta una uniformidad significativa, es generalmente ineficaz donde los valores de datos son propensos a diferir de un al siguiente. En esta segunda situación, es común entre los esquemas de compresión conocidos el conmutar de forma adaptativa entre la codificación de longitud de tirada y algún otro tipo de codificación, en el que la conmutación 15 generalmente se maneja en el decodificador por información anexa asociada con el flujo de bits, o por cálculo; esto o bien reduce la eficiencia de compresión o aumenta la carga computacional, respectivamente.

El documento EP 1 004 975 A2 divulga un conjunto de palabras de código de compresión de ocho bits que se utilizan en el comienzo de una tirada de datos que comprende un recuento de píxeles y uno o más valores de color, 20 los primeros cuatro bits de la primera palabra siendo utilizados para especificar el formato de los bytes en la siguiente secuencia de datos y si los siguientes píxeles se van a imprimir como la superposición o como el fondo, y los últimos cuatro bits siendo utilizados para especificar sugerencias de impresión.

Es común entre los esquemas de compresión que utilizan codificación tanto de longitud de tirada como diferencial, 25 llevar a cabo la codificación diferencial antes de la codificación de longitud de tirada, cuyo orden requiere que el codificador calcule una diferencia, y el decodificador calcule una suma (es decir, reconstruir el valor de datos) para cada valor de datos en el flujo de bits.

Por lo tanto, es deseable usar un esquema de codificación que pueda eliminar o por lo menos mitigar estas 30 limitaciones conocidas.

BREVE DESCRIPCIÓN DE LOS DIBUJOS

La FIG. 1 ilustra un procedimiento para codificar un flujo de datos de valores enteros de acuerdo con una realización de la presente invención.

La FIG. 2 ilustra un procedimiento de codificación de una lista de pares de tirada/valor de datos de acuerdo con una realización de la presente invención. 40

La FIG. 3 ilustra un flujo de datos de valores enteros a modo de ejemplo, y sus tiradas asociadas.

La FIG. 4 ilustra un sistema de codificador-decodificador de acuerdo con una realización de la presente invención. 45

DESCRIPCIÓN DETALLADA

Las realizaciones de la presente invención reducen el tamaño y la complejidad de los flujos de bits asociados a datos codificados mediante el uso de un nuevo esquema de compresión. Un codificador entrópico recibe una lista de 50 pares de tirada/valor de datos y codifica entrópicamente por separado las tiradas y los valores de datos, seleccionando sus palabras de código según longitud y magnitud, respectivamente, y concatena los pares de palabras de código resultantes - la palabra de código de valor de datos primero - en un flujo de bits codificados. El esquema de codificación reduce el tamaño y la complejidad de un flujo de bits codificados, cuyo flujo de bits puede representar imágenes, vídeos, y demás. Por lo tanto, el flujo de bits puede ser transmitido utilizando menos ancho 55 de banda y se puede disminuir la carga computacional tanto en el codificador como en el decodificador.

La FIG. 1 ilustra un procedimiento de codificar un flujo de bits de acuerdo con una realización de la presente invención. Según la realización, el procedimiento puede escanear un conjunto de valores de datos en un sentido de escaneo predeterminado (cuadro 100) . El procedimiento puede convertir valores de datos del conjunto en una 60 secuencia de pares de tirada/valor de datos (cuadro 110) . En el bloque 120, el procedimiento puede seleccionar una palabra de código en función de un valor de una tirada. Del mismo modo, en el cuadro 130, el procedimiento puede seleccionar una palabra de código en función de un valor de un valor de datos. El procedimiento puede realizar ya sea la etapa 120 o la etapa 130 o ambos. El procedimiento puede concatenar los datos codificados de tirada/valor de datos en parejas de datos codificados (cuadro 140) . A partir de entonces, los datos podrán ser procesados adicionalmente para transmisión.

Más específicamente, en el bloque 100, el procedimiento puede escanear un conjunto de datos de origen de acuerdo con un sentido de escaneo, cuyos datos de origen representan, por ejemplo, una imagen, un vídeo, y 5 demás. El procedimiento puede acomodar conjuntos de datos de una variedad de tamaños y configuraciones. Se apreciará que los conjuntos multi-dimensionales de números enteros pueden ser considerados como un conjunto lineal cuando se consideran según una dirección de escaneo y, por lo tanto, la presente discusión se dirige a un caso de conjunto lineal.

10 En el bloque 110, el conjunto unidimensional de valores de datos se puede convertir, utilizando la codificación por longitud de tirada, en una lista de pares de tirada de tirada/valor de datos, donde un número entero (comúnmente, el primer número entero) en el par es la longitud de la tirada, y otro número entero (comúnmente, el segundo número entero) es el valor de los datos que comprenden la tirada correspondiente. Por ejemplo, y como se muestra en la FIG. 3, si el conjunto unidimensional consta de 10 elementos - {0, 0, 0, 3, 3, 2, 2, 2, 2, 2} - esos 10 elementos se 15 convertirían en los siguientes pares: { (3, 0) , (2, 3) , (5, 2) }. Los pares resultantes indican que el conjunto original constaba de tres valores iguales a 0, dos valores iguales a 3, y cinco valores iguales a 2, y en ese orden.

En una realización, la lista resultante de pares de tirada/valor de datos se puede codificar en diferencia, en el bloque 110, en una lista de pares de diferencia de tirada/valor de datos. Volviendo al ejemplo del conjunto de 10 elementos 20 utilizado anteriormente, la lista resultante de pares de diferencia de tirada/valor de datos consta de { (3, +1) , (2, +3) , (5, -1) }, en el que [0 - (-1) = 1], [3 - 0, = +3], y [2 - 3 = -1]. En circunstancias normales la diferencia de valor de datos no será cero, ya que ello implicaría una continuación de la tirada anterior; mediante el tratamiento del valor de tirada anterior de la tirada inicial como -1 (como se muestra en el ejemplo anterior) , se puede garantizar una diferencia de valor de datos distinta de cero (a menos que una tirada se divide en sub-tiradas, como se detalla en este 25 documento) .

Al hacer la codificación por longitud de tirada antes de la codificación de por diferencia, se tiene que calcular una diferencia (codificador) o suma (decodificador) solamente una vez por tirada, en lugar de una vez por cada valor de datos. Esta distinción de orden puede ser especialmente valiosa en el decodificador, donde no sólo reduce la 30 cantidad de cálculo requerido, sino que también elimina cualquier secuencia asociada, permitiendo que varios de los valores de los datos idénticos de una tirada sean emitidos simultáneamente.

Tal como descrito anteriormente, los principios de la presente invención encuentran aplicación tanto con valores de datos diferenciales como con valores de datos no diferenciales. Por lo tanto, a menos que se especifique a 35 continuación, la discusión que sigue se refiere a los "valores de datos" en un sentido genérico, para referirse por igual a valores de datos diferenciales como no diferenciales.

En los bloques 120, 130 la lista resultante de pares de tirada/ valor de datos puede se puede codificar entrópicamente; las tiradas pueden ser codificadas por separado de los valores de datos y tal codificación se pueden 40 realizar en serie (por ejemplo, tiradas antes que valores de datos, y demás) o en paralelo. Las realizaciones de la presente invención permiten la codificación por entropía basada en tabla de códigos propuesto en este documento a ser utilizado en conjunción con otros esquemas de codificación, si se desea. Por ejemplo, aunque la presente discusión propone codificar ambas tiradas y valor de datos de acuerdo con el proceso descrito a continuación con respecto a la FIG. 2, es admisible codificar sólo un tipo de datos (por ejemplo, las tiradas) de acuerdo con el 45 esquema propuesto y codificar el otro tipo de datos (por ejemplo, los valores de datos) de acuerdo con otro... [Seguir leyendo]

 


Reivindicaciones:

1. Procedimiento para la codificación entrópica de datos de pares de tirada/valor de datos que corresponden a un flujo de datos de valores enteros, en el que cada tirada se codifica en una de tres maneras, comprendiendo dicho 5 procedimiento:

clasificar cada una de dichas tiradas en función de su longitud siendo o 1, corta o larga;

si la tirada es 1, seleccionar un primer código con una longitud de 1; 10

si la tirada se clasifica como corta, seleccionar un primer código con una primera longitud predeterminada, cada primer código de primera longitud predeterminada teniendo un preámbulo para distinguir las otras clasificaciones de tirada, y teniendo un valor en función de la longitud de la tirada;

si la tirada se clasifica como larga, seleccionar un primer código con una segunda longitud predeterminada, cada primer código de segunda longitud predeterminada teniendo un preámbulo para distinguir las otras clasificaciones de tirada, y teniendo un valor en función de la longitud de la tirada; y

emitir el primer código seleccionado a un canal, en el que la primera longitud predeterminada es n + 1 bits, el 20 primer código con la primera longitud predeterminada se selecciona a partir de una primera tabla de código, el primer código con la primera longitud predeterminada tiene el preámbulo para el primer bit y cuyo valor para los n bits restantes se basa en la duración de la tirada,

la segunda longitud predeterminada es n + 1 + M bits, el primer código con la segunda longitud 25 predeterminada se selecciona a partir de una segunda tabla de códigos, el primer código con la segunda longitud predeterminada teniendo el preámbulo para los primeros n + 1 bits y cuyo valor para los M bits restantes se basa en la longitud de la tirada.

2. El procedimiento de la reivindicación 1, en el que la longitud de la tirada corta es mayor que 1 y menor o igual a 30 2n, y la longitud de la tirada larga es mayor que 2n.

3. El procedimiento de la reivindicación 1 en el que:

para tiradas clasificadas como cortas, el preámbulo del primer código es un bit '0' y el valor de los n bits 35 restantes es el código binario para uno menos la longitud de la tirada; y

para tiradas clasificadas como largas, el preámbulo del primer código es n + 1 bits '0' y el valor de los M bits restantes es el código binario para uno menos la longitud de la tirada.

4. El procedimiento de la reivindicación 1 que comprende además dividir una tirada en dos o más sub-tiradas cuando la longitud de una tirada es mayor que 2M, en el que:

la longitud de cada una de las sub-tiradas es inferior o igual a 2M;

el valor de datos asociado con la primera sub-tirada es igual al valor de datos asociado con la tirada; y 45

el valor de datos asociado a cada sub-tirada después de la primera sub-tirada es cero.

5. El procedimiento de la reivindicación 1 que comprende además:

clasificar cada valor de datos en función de su magnitud; 50

si el valor de datos se clasifica como pequeño, seleccionar un segundo código que comprende k + 2 bits a partir de una tercera tabla de códigos, el segundo código seleccionado teniendo un preámbulo predeterminado para el primer bit y cuyo valor para los k + 1 bits restantes se basa en el valor de datos;

si el valor de datos se clasifica como grande, seleccionar un segundo código que comprende N + 1 bits a 55 partir de una cuarta tabla de códigos, el segundo código seleccionado teniendo un preámbulo predeterminado para el primer bit y cuyo valor para los N bits restantes se basa en el valor de datos y en N; y

emitir el segundo código seleccionado al canal.

6. Un sistema para la codificación entrópica de una lista de datos de pares de tirada/valor de datos correspondientes a un flujo de datos de valores enteros, en el que cada tirada se codifica de una de tres maneras, en el que el sistema está configurado para llevar a cabo el procedimiento de acuerdo con cualquiera de las reivindicaciones 1 a 5.

7. Un medio legible por ordenador codificado con un conjunto de instrucciones que, cuando se realiza por un ordenador, lleva a cabo el procedimiento de cualquiera de las reivindicaciones 1 a 5.


 

Patentes similares o relacionadas:

Sistema y procedimiento para transformar y codificar progresivamente datos digitales, del 10 de Abril de 2019, de Zhigu Holdings Limited-Harneys Services (Cayman) Limited: Un sistema de compresión de imágenes, que comprende: un mapeador de espacio de color que mapea una imagen de entrada con una representación de espacio de color YCoCg […]

Sistema y procedimiento para transformar y codificar progresivamente datos digitales, del 10 de Abril de 2019, de Zhigu Holdings Limited: Un procedimiento para mapear un espacio de color, que comprende: recibir una entrada RGB, comprendiendo la entrada RGB un componente […]

Codificador, descodificador, método de codificación, método de descodificación, programa de codificación, programa de descodificación y medio de grabación, del 10 de Abril de 2019, de NIPPON TELEGRAPH AND TELEPHONE CORPORATION: Un codificador que comprende: una parte de generación de envolvente combinada periódica que está adaptada para generar una secuencia […]

Procedimiento de descodificación de longitud variable y aparato, del 3 de Abril de 2019, de Godo Kaisha IP Bridge 1: Un procedimiento de decodificación para realizar una decodificación de longitud variable en datos codificados obtenidos realizando codificación de longitud variable en los […]

Procedimiento de descodificación de imágenes y dispositivo de descodificación, del 3 de Abril de 2019, de Panasonic Intellectual Property Corporation of America: Un dispositivo de descodificación que descodifica un flujo de bits de una señal de imagen codificada (Str) que comprende un flujo de cabecera (Str_H) y un flujo de trama […]

Cifrado de manera independiente de la posición del último coeficiente significativo de un bloque de vídeo en cifrado de vídeo, del 27 de Marzo de 2019, de Velos Media International Limited: Método de codificación de coeficientes asociados con un bloque de datos de vídeo durante un procedimiento de cifrado de vídeo, comprendiendo el método: […]

Inicialización de estados y probabilidades de contexto para codificación de entropía adaptativa al contexto, del 26 de Marzo de 2019, de QUALCOMM INCORPORATED: Un procedimiento para inicializar un contexto usado para codificar datos de vídeo en un proceso de codificación aritmética binaria adaptativa al contexto […]

Método y aparato para decodificación aritmética, del 20 de Marzo de 2019, de NTT DOCOMO, INC.: Un método de decodificación aritmética que usa codificación aritmética binaria adaptativa al contexto que comprende: introducir una secuencia de información […]

Utilizamos cookies para mejorar nuestros servicios y mostrarle publicidad relevante. Si continua navegando, consideramos que acepta su uso. Puede obtener más información aquí. .