Source: https://patents.google.com/patent/ES2201207T3/en
Timestamp: 2018-12-10 22:33:39+00:00

Document:
ES2201207T3 - Digital storage and retrieval of large images. - Google Patents
Digital storage and retrieval of large images.
ES2201207T3
ES2201207T3 ES96937039T ES96937039T ES2201207T3 ES 2201207 T3 ES2201207 T3 ES 2201207T3 ES 96937039 T ES96937039 T ES 96937039T ES 96937039 T ES96937039 T ES 96937039T ES 2201207 T3 ES2201207 T3 ES 2201207T3
ES96937039T
LA INVENCION SE REFIERE A LA COMPRESION YA LA VISUALIZACION DE LAS IMAGENES. The invention relates to compression and viewing images. UN METODO DE COMPRESION BASADO EN DWT UTILIZA UN ORDENADOR CON UNA MEMORIA DE DOS NIVELES. A method DWT-based compression using a computer with a memory of two levels. EL METODO DE VISUALIZACION SELECCIONA LAS AREAS DE LA IMAGEN EN FORMA COMPRIMIDA Y CON MULTIPLES RESOLUCIONES. The display method selects areas IMAGE IN COMPRESSED FORM AND MULTIPLE RESOLUTIONS. PARA LA COMPRESION, SE DEFINE UNA PLURALIDAD DE SUBCONJUNTOS DE IMAGENES TIPO BALDOSA DISCRETAS (118), LAS CUALES FORMAN LA IMAGEN COMPLETA. FOR compression, a plurality of subassemblies DEFINE IMAGE TYPE DISCRETE TILE (118), which form the whole picture. LA COMPRESION DE UNA IMAGEN BASADA EN FORMAS DE ONDA SIN COSTURAS OCURRE AL INTRODUCIR LAS BALDOSAS, EN UNA SECUENCIA SELECCIONADA, EN UNA RUTINA DWT (120). AN IMAGE COMPRESSION BASED WAVEFORM HAPPENS TO INTRODUCE SEAMLESS TILES, in a selected sequence, a routine DWT (120). LOS COEFICIENTES DWT RESULTANTES SE ALMACENAN EN UNA PRIMERA MEMORIA PRIMARIA, Y PERIODICAMENTE SE COMPRIMEN (128) Y SE ALMACENAN EN UNA MEMORIA SECUNDARIA (124). DWT RATIOS ARE RESULTING IN A FIRST PRIMARY STORED MEMORY, AND PERIODICALLY compressed (128) and stored in a secondary memory (124). LA SECUENCIA DE OPERACIONES DWT EN LAS BALDOSAS CALCULA DE FORMA EFECTIVA UNA DWT SIN COSTURAS DE LA IMAGEN. SEQUENCE OPERATIONS IN TILES CALCULATED DWT EFFECTIVELY A seamless DWT IMAGE. LA RECUPERACION DE LOS DATOS OCURRE AL ESPECIFICAR UNA RESOLUCION Y UNA REGION DE LA IMAGEN PARA SU VISUALIZACION (146). THE RECOVERY OF DATA OCCURS specifying a resolution and a region of the image for display (146). SE DETERMINA EL SUBCONJUNTO DE COEFICIENTES DWT ALMACENADOS CORRESPONDIENTES A CADA A ESCENA SOLICITADA Y, ENTONCES, SE DESCOMPRIME PARA SU ENTRADA EN UNA DWT INVERSA (164) PARA FORMAR LA VISUALIZACION (166). DETERMINED subassembly STORED DWT Coefficients for each A REQUESTED SCENE and then decompressed FOR ENTRY INTO A REVERSE DWT (164) to form the screen (166). LA INTERACCION (168) PUEDE OCURRIR CON UN DISPOSITIVO PUNTERO EN LAS VISUALIZACIONES PREVIAS RECUPERADAS. INTERACTION (168) CAN OCCUR WITH A POINTER DEVICE IN RECOVERED previews.
Almacenamiento y recuperación de imágenes digitales de gran tamaño. Digital storage and retrieval of large images.
La invención se refiere a la representación de imágenes digitales y de manera más particular al almacenamiento ya la recuperación de los datos contenidos en imágenes digitales de gran tamaño. The invention relates to digital imaging and more particularly to storage and retrieval of data in large digital images way.
Existen muchas aplicaciones que requieren el almacenamiento y la recuperación de imágenes digitales de muy gran tamaño. There are many applications that require storage and retrieval of digital images of very large. Ejemplos de dichos conjuntos de datos incluyen una escena Landsat Thematic Mapper (TM), un mosaico de ortofotos digital (fotografías aéreas digitalizadas) o una exploración de alta resolución de un negativo fotográfico. Examples of such data sets include a scene Landsat Thematic Mapper (TM), a digital orthophotos mosaic (digitized aerial photographs), or a high resolution scan of a photographic negative. De la manera en que se usa en este documento, el término "imagen" significa cualquier matriz bidimensional de gran tamaño de datos numéricos incluso si no se hace referencia típicamente a esos datos como una "imagen", por ejemplo, datos digitales de elevación. The way used herein, the term "image" means any two-dimensional array of large numerical data even if no reference is typically made to these data as a digital "image", for example, elevation data.
Debido a las ingentes cantidades de datos que se encuentran presentes en dichas imágenes, la compresión de datos es de una importancia significativa para la mejora de la utilización del almacenamiento de un ordenador y de los recursos de transmisión. Due to the huge amounts of data present in such images, data compression is of significant importance for improving storage utilization of a computer and transmission resources. Las dimensiones de la imagen bajo consideración son lo significativamente grandes como para ser visualizadas sobre un monitor de un ordenador. The image dimensions under consideration are large enough to be significantly displayed on a computer monitor. Si un usuario puede solamente visualizar subsecciones de imagen a resolución completa, una visualización puede contener menos del uno por ciento de la imagen. If a user can only display sub-image at full resolution, a display may contain less than one percent of the image. Bajo dicha circunstancia, es difícil formar en el visionador un cuadro global de la imagen o localizar características particulares de interés. Under such circumstance, it is difficult to form in the viewer an overall picture of the image or to locate particular features of interest. La visualización de imágenes a resoluciones menores que la resolución completa permite visualizar regiones de tamaño mayor de la imagen o incluso una imagen completa. Viewing images at lower resolutions than the full resolution can display regions larger image or even a complete picture.
Ciertos esquemas de compresión de datos de imagen implementados por medio de ordenador usados en la técnica anterior son técnicas de codificación subbanda, tratadas con más detalle más adelante. Some compression schemes implemented image data used by the prior art computer techniques are subband coding of, treated with more detail below. Los datos de la imagen son separados en varias subimágenes a las que se hace referencia como "subbandas" ya que cada una de ellas contiene información de una banda diferente de frecuencias espaciales en la imagen. The image data are separated into several subimages referenced as "subband" it is because each contains information from a different band of spatial frequencies in the image. La compresión de subbandas de manera separada facilita la adaptación del algoritmo de compresión global a las estadísticas de imagen. Compression subbands separately facilitates adaptation algorithm statistics overall image compression. Un desarrollo matemático reciente, la transformada de tren de ondas discreta (DWT), tiene un solapamiento teórico significativo con los procedimientos desarrollados para generar las subbandas de imagen. A recent mathematical development, transform discrete wavelet (DWT), it has significant theoretical overlap with procedures developed to generate subbands image. Por esta razón, el término "descomposición de subbanda" se ha convertido en un sinónimo de DWT. For this reason, the term "subband decomposition" has become synonymous with DWT. Esta terminología se usa en este documento. This terminology is used herein.
Para las imágenes de muy gran tamaño, surgen las complicaciones en el cálculo de la DWT. For very large images, complications arise in calculating the DWT. La técnica anterior trata las técnicas para llevar a la práctica la DWT donde se dé a entender que la matriz de datos de imagen al completo va a ser almacenada en la memoria principal de un ordenador y que el algoritmo procesado por un ordenador puede acceder rápidamente a todos los píxeles de la imagen. The prior art addresses the techniques to implement the DWT where given to understand that the data matrix big picture is to be stored in the main memory of a computer and the algorithm processed by a computer can access quickly all pixels in the image. Para las imágenes de gran tamaño, la memoria implicada en la realización de una DWT puede llegar a ser prohibitiva. For large images, memory involved in performing a DWT can become prohibitive. Por ejemplo, considérese una imagen que sea de una dimensión de 50.000 x 50.000 píxeles, es decir, consistente en 2.500 millones de píxeles. For example, consider an image that is of dimension 50,000 x 50,000 pixels of, that is, consisting of 2500 million pixels. Si se realiza la transformada en aritmética de punto flotante con 32 bits de precisión, entonces se necesitan 10 Gb de memoria de ordenador (sin incluir el espacio de trabajo). If converted into floating point arithmetic with 32-bit precision is performed, then 10Gb computer memory (not including work space) are needed. Claramente, se requiere algún procedimiento para la búsqueda de los datos de la memoria de un ordenador y el cálculo de la DWT en secciones. Clearly, a procedure for finding data memory of a computer and calculating the DWT in sections is required. Aunque se podría dividir la matriz de imagen en subsecciones rectangulares y realizar una DWT sobre cada una de ellas de manera independiente, esto no sería deseable por dos razones. Although one could divide the image array into rectangular subsections and perform a DWT on each independently, this would be undesirable for two reasons. La primera de ellas, existirían condiciones de limitación de la transformada de tren de ondas en el interior de los datos de imagen que podrían potencialmente dar como resultado aberraciones de compresión. The first of these limiting conditions exist transform wavelet within the image data which could potentially result in compression aberrations. Además, la implementación de una rutina de recuperación multiescala se ve complicada por estos contornos interiores. In addition, the implementation of a multiscale routine recovery is complicated by these inner contours.
1. La patente de los Estados Unidos número 4.692.806 en favor de Anderson y colaboradores, instruye acerca de un procedimiento para la visualización selectiva de áreas de una imagen a varias resoluciones en un ordenador que tenga una memoria primaria para el procesado de datos y una memoria secundaria inherente para el almacenamiento de datos, incluyendo la selección de un conjunto de visualización de la matriz de datos de imagen que vaya a ser visualizada a una resolución deseada, pero no instruye acerca de la transformada de tren de ondas o del uso de mosaico en la compresión de imágenes. 1. Patent US 4,692,806 in number for Anderson et al, teaches to a method for selectively viewing areas of an image at various resolutions in a computer having a primary memory for data processing and a secondary memory inherent to data storage, including selecting a set of matrix display image data that is to be displayed at a desired resolution, but does not teach the transformed wavelet or the use of mosaic image compression.
2. La patente de los Estados Unidos número 5.204.916 en favor de Hamiltori, Jr. Y colaboradores, instruye acerca del almacenamiento de un conjunto completo de matriz de datos de imagen que represente la imagen en una primera memoria secundaria del ordenador y la definición de una pluralidad de subconjuntos de datos de imagen de cuadrícula de mosaico discretos, en la que el conjunto completo de datos de imagen está formado por medio de la superposición de los datos de imagen de cuadrícula de mosaico discretos, en la que el mosaico se realiza para reducir los requisitos de memoria en la operación de dimensionamiento. 2. Patent Number 5,204,916 US in favor of Hamiltori, Jr. et al, instructs about storing a complete set of image data matrix representing the image in a first computer memory and high definition a plurality of subsets of image data grid of discrete mosaic, where the complete set of image data is formed by superimposing the image data of discrete tile in which the mosaic is made to reduce memory requirements in the operation of sizing. Hamilton, Jr. y colaboradores no instruyen acerca del uso de mosaico para reducir la cantidad total de datos que se están procesando o de cómo procesar los cuadros de mosaico para formar una DWT sin junturas a través de todos los datos de mosaico. Hamilton, Jr. et al do not teach the use of mosaic to reduce the total amount of data being processed or how to process the tiles to form a seamless DWT across all data mosaic.
3. La patente de los Estados Unidos número 5.315.670 en favor de Shapiro instruye acerca de la realización de uno o más procedimientos de compresión basados en la transformación discreta de tren de ondas (DWT) sobre datos de imagen en una subsecuencia seleccionada para sacar los datos discretos de imagen como una sucesión de coeficientes DWT en una sucesión de conjuntos de subbanda, en la que una subbanda de cada conjunto es una representación de baja resolución de los datos de imagen discretos para formar una secuencia de representaciones de baja resolución de la matriz de datos de imagen para resoluciones seleccionadas. 3. Patent US 5,315,670 in number for Shapiro instructs on performing one or more compression methods based on the discrete wavelet transform (DWT) on image data in a selected subsequence to remove the discrete image data as a succession of DWT coefficients in a succession of sets of subband, where one subband of each set is a low-resolution representation of the image data discrete to form a sequence of representations of low resolution image data array to selected resolutions. Shapiro comprime toda la imagen en lugar de mosaico de la imagen; Shapiro compresses the entire image rather than mosaic image; la visualización de un conjunto de coeficientes de tren de ondas DWT almacenados que soporten el conjunto de visualización de los datos de imagen a la resolución deseada. displaying a set of coefficients stored DWT train waves that support the set of display image data to the desired resolution. En el procedimiento de descomposición, se generan los coeficientes de tren de ondas que representan los distintos niveles de descomposición y de resolución. In the process of decomposition, the wavelet coefficients representing different levels of decomposition and resolution are generated. Los datos son descomprimidos por medio de la transformación inversa de los coeficientes para llegar a la imagen original. The data is decompressed by inverse transforming the coefficients to arrive at the original image. No hay selección de subconjuntos de coeficientes de tren de ondas para producir imágenes de resolución seleccionada, como se cita en la reivindicación 6. No selection of subsets of wavelet coefficients to produce images of selected resolution as cited in claim 6.
4. La patente de los Estados Unidos número 5.325.449 en favor de Burt y colaboradores instruye acerca de la formación de un subconjunto de coeficientes de tren de ondas DWT almacenados como una visualización de ordenador del conjunto de visualización de los datos de imagen a la resolución deseada. 4. The patent US 5,325,449 in number for Burt et al teaches about the formation of a subset of coefficients train DWT waves stored as a computer display set display image data to desired resolution. Burt y colaboradores también instruyen acerca de la combinación de imágenes seleccionadas usando los coeficientes de tren de ondas en el que las imágenes fuente que se combinan podrían ser de una resolución seleccionada. Burt and collaborators also instructive about combining selected images using the wavelet coefficients where the source images that are combined could be of a selected resolution. Burt y colaboradores no instruyen acerca de ninguna utilización de mosaico en combinación con el procesado DWT. Burt and colleagues do not instruct about any use of mosaic in combination with DWT processing. La presente invención está dirigida a la compresión de los datos de mosaico y el posterior procesado de los datos de mosaico en una secuencia seleccionada de forma que los coeficientes DWT almacenados resultantes representen a toda la imagen, no imágenes de mosaico, y sin ninguna aberración en los contornos del mosaico. The present invention is directed to compression of data tile and the subsequent processing of the data mosaic in a selected sequence so that the DWT coefficients stored resulting representing the entire image, not tile images, and without any aberration in mosaic contours. Después de esto, se puede seleccionar un subconjunto de visualización sin considerar los contornos de cuadrícula de mosaico originales. After this, you can select a subset of display regardless contours original mosaic grid.
De acuerdo con la presente invención, se proporciona un procedimiento para la compresión basada en tren de ondas sin junturas de imágenes contiguas de muy gran tamaño y para el acceso a posiciones arbitrarias en la imagen a varias resoluciones. According to the present invention, a method for compression based on wavelet seamless contiguous images of very large and for accessing arbitrary locations in the image resolutions it is provided.
De acuerdo con esto, es un objeto de la presente invención proporcionar la recuperación, a partir de la representación comprimida, una subsección de imagen de cualquier posición dentro de la imagen con dimensiones que sean adecuadas para su visualización. Accordingly, it is an object of the present invention to provide recovery from the compressed representation an image subsection from any location within the image with dimensions that are suitable for viewing.
Otro objeto de la presente invención es permitir a un usuario especificar de manera interactiva regiones de imagen para visualización y la rápida recuperación de las regiones de imagen. Another object of the present invention is to allow a user to interactively specify image regions for display and rapid recovery of the image regions.
Otro objeto más de la presente invención es permitir al usuario navegar u "hojear" sobre la base datos que forma la imagen. Yet another object of the present invention is to allow the user to navigate or "browse" based on data forming the image.
Otro objeto de la presente invención es proporcionar la rellamada a la imagen en varias resoluciones. Another object of the present invention to provide redialing the image in various resolutions.
Objetos, ventajas y características novedosas adicionales de la invención se declaran en parte en la siguiente descripción, y en parte serán aparentes para aquéllos que sean expertos en la técnica al examinar lo siguiente, o se puede aprender con la práctica de la invención. Objects, advantages and novel features of the invention are stated in part in the following description, and in part will become apparent to those skilled in the art upon examination of the following or may be learned by practice of the invention. Los objetos y las desventajas de la invención se pueden realizar y conseguir por medio de la instrumentación y de las combinaciones apuntadas de manera particular en las reivindicaciones anejas. The objects and disadvantages of the invention will be realized and attained by means of the instrumentalities and combinations particularly pointed in the appended claims.
Para conseguir los anteriores y otros aspectos, y de acuerdo con los propósitos de la presente invención, como se encarna y se describe ampliamente en este documento, la invención puede comprender (1) un procedimiento para realizar la compresión basada en DWT sobre una imagen digital de gran tamaño con un sistema de ordenador que procese un sistema de dos niveles de memoria y (2) un procedimiento para visualizar de manera selectiva áreas de la imagen a partir de su representación comprimida a varias resoluciones y, si se desea, en un entorno cliente-servidor. To achieve the above and other aspects and in accordance with the purposes of the present invention, as embodied and broadly described herein, the invention may comprise (1) a method for performing DWT-based compression on a digital image large with a computer system that processes a two-level system of memory and (2) a method for displaying selectively areas of the image from its compressed resolutions representation and, if desired, in an environment client-server. El sistema de memoria de dos niveles se refiere a memorias primaria y secundaria. The memory system of two levels refers to primary and secondary memories. La memoria primaria es típicamente mucho más pequeña que la memoria secundaria pero es más accesible por parte del procesador. The primary memory is typically much smaller than the secondary memory but is more accessible by the processor.
La compresión de una imagen digital de gran tamaño l(x, y) es llevada a cabo primeramente definiendo una pluralidad de subconjuntos de datos de imagen de mosaico discretos T_{ij}(x, y) que, al superponerse, forman el conjunto completo de datos de imagen l(x, y). Compressing a digital large image l (x, y) is accomplished by first defining a plurality of subsets of image data of discrete tile T_ {ij} (x, y) by superimposing, form the complete set image data I (x, y). Se efectúa un procedimiento de compresión basado en tren de ondas sin junturas sobre l(x, y) que está comprendido de la entrada sucesiva de los cuadros de mosaico T_{ij}(x, y) en una secuencia seleccionada a una subrutina DWT, añadiendo las correcciones que sean pasadas desde las indicaciones previas de la rutina DWT sobre otra T_{ij}(x, y) y almacenando los coeficientes DWT resultantes en una memoria primaria. a compression process based on wavelet seamlessness on l (x, y) that is comprised of successive input the tiles T_ {ij} (x, y) is performed in a sequence selected DWT subroutine, adding corrections that are passed from previous indications of the DWT routine on other T_ {ij} (x, y) and storing the resulting DWT coefficients in a primary memory. Estos coeficientes son periódicamente comprimidos y transferidos a una memoria secundaria para mantener suficiente memoria en ka memoria primaria para el procesado de datos. These coefficients are periodically compressed and transferred to a secondary memory to maintain sufficient memory in ka primary memory for data processing. En ausencia del paso de compresión, la secuencia de operaciones DWT sobre los cuadros de mosaico T_{ij}(x, y) calcula de manera efectiva una DWT sin junturas de l(x, y) que se pueda visualizar como una realización "solapamiento-adición" de la DWT. In the absence of the compression step, the sequence of operations DWT on the tiles T_ {ij} (x, y) calculated effectively one seamless DWT of I (x, y) that can be viewed as an embodiment "overlap -Adding "DWT. El procedimiento DWT sin junturas transforma l(x, y) en un conjunto de coeficientes DWT para formar un conjunto de subbandas que expresen una representación jerárquica de las representaciones de baja resolución de la matriz de datos de imagen l(x,y). The seamless DWT process transforms I (x, y) in a set of DWT coefficients to form a set of subbands that express a hierarchical representation of low-resolution representations of the image data array I (x, y).
La recuperación de datos consta de la especificación de una resolución y de una región de l(x, y) para visualización. Data retrieval consists of specifying a resolution and a region of I (x, y) for display. Se determina el subconjunto de coeficientes DWT almacenados correspondiente a cada escena solicitada, y después es descomprimido para su entrada en una DWT inversa, la salida de la cual forma la visualización de la imagen. the subset of stored DWT coefficients corresponding to each requested scene is determined and then it is decompressed for input in a reverse DWT, the output of which forms the image display. El procedimiento repetido por el que se especifican las visualizaciones de la imagen, puede tomar la forma de una interacción con un dispositivo de apuntamiento de ordenador sobre una visualización de imagen a partir de una recuperación anterior. Repeated procedure that displays the image specified, may take the form of an interaction with a computer pointing device on an image display from a previous retrieval.
Los dibujos adjuntos, que se incorporan y que forman una parte de la especificación, ilustran las realizaciones de la presente invención y, junto con la descripción, sirven para explicar los principios de la invención. The accompanying drawings, which are incorporated in and form a part of the specification, illustrate embodiments of the present invention and, together with the description, serve to explain the principles of the invention.
La figura 1 es un diagrama esquemático de una transformación de tren de ondas discreta (DWT) de dos canales directa (análisis) e inversa (síntesis) de una matriz de datos de entrada. Figure 1 is a schematic diagram of a transformation of discrete wavelet (DWT) two direct channels (analysis) and inverse (synthesis) of a matrix of input data.
La figura 2 es un diagrama esquemático de un procedimiento DWT bidimensional realizado con múltiples aplicaciones de la parte de análisis del sistema mostrado en la figura 1. Figure 2 is a schematic diagram of a two dimensional DWT process realized with multiple applications of the analysis part of the system shown in Figure 1.
La figura 3 ilustra las cuatro subbandas formadas a partir de una matriz de imagen por medio de la aplicación de la DWT mostrada en la figura 2. Figure 3 illustrates the four subbands formed from an image array by application of the DWT shown in Figure 2.
La figura 4 ilustra el soporte de frecuencia de una descomposición de subbanda resultante de las aplicaciones repetidas del sistema mostrado en la figura 3. Figure 4 illustrates the frequency support of a subband decomposition resulting from repeated applications of the system shown in Figure 3.
La figura 5 es un diagrama de flujo para la compresión de datos DWT de acuerdo con una realización de la presente invención. Figure 5 is a flow diagram for DWT data compression according to one embodiment of the present invention.
La figura 6 es un diagrama de flujo para la descompresión de datos de acuerdo con una realización de la presente invención. 6 is a flow diagram for decompressing data according to one embodiment of the present invention.
La presente invención tiene que ver en parte con un esquema de compresión de subbanda implementado por medio de ordenador para imágenes de gran tamaño. The present invention concerns partly a subband compression scheme implemented by computer for large images. El uso ventajoso de un sistema de dos niveles de memoria de ordenador proporciona el cálculo local eficiente de la DWT junto con un esquema de codificación espacialmente adaptable, permitiendo la compresión de la imagen sin junturas con requisitos mínimos de memoria. The advantageous use of a two-level system of computer memory provides the efficient local computation of the DWT in conjunction with a spatially adaptive coding scheme, allowing the image compression seamlessness with minimal memory requirements. Además, la invención proporciona la recuperación rápida de vistas de imágenes de dimensiones y posiciones arbitrarias a varias resoluciones a partir de los datos comprimidos. Furthermore, the invention provides rapid recovery of image views of arbitrary dimensions and resolutions from the compressed data positions.
La invención usa de manera ventajosa la DWT para dos propósitos. The invention advantageously uses the DWT for two purposes. La DWT se usa como un paso de preprocesado en un ordenador para facilitar la compresión de datos. The DWT is used as a preprocessing step in a computer to facilitate data compression. La subdivisión de la matriz de datos de la imagen de entrada en un conjunto de subbandas de imagen que se codifican de manera separada facilita la adaptación del algoritmo de compresión a la estadística de la imagen. The subdivision of the array of image data input in a set of subbands image are coded separately facilitates adaptation of the compression algorithm to the image statistics. Además, la DWT se usa también para proporcionar la recuperación de datos multiescala. Moreover, the DWT is also used to provide data recovery multiscale. Debido a la naturaleza multirresolución de la DWT, es inherente una descripción de la imagen a varias resoluciones en la descomposición de la DWT, facilitando de esta manera la recuperación multiescala de los datos comprimidos de acuerdo con la presente invención. Due to the multiresolution nature of the DWT, a description of inherent image resolutions in the DWT decomposition, thus facilitating multiscale retrieval of the compressed data according to the present invention.
columnas : Muestras por línea en una imagen. columns: Samples per line in an image.
datos comprimidos : O los datos de imagen comprimidos o los datos de especificación de tabla o ambos. compressed data: Either compressed image data or table specification data or both.
compresión : Reducción en el número de bits usados para representar los datos de imagen fuente. compression: Reduction in the number used to represent source image data bits.
imagen (digital) : Una matriz bidimensional de datos. image (digital): A two - dimensional data matrix.
inframuestreo : Un procedimiento por el que la resolución espacial de una imagen se ve reducida. downsampling: A procedure by which the spatial resolution of an image is reduced.
DWT : (transformada discreta de tren de ondas) Una transformación lineal implementada por medio de un banco de filtros multitasa, que asigna una señal de entrada digital a una colección de subbandas de salida. DWT: (discrete wavelet transform) A linear transformation implemented by a multirate filter bank, which assigns a digital input signal to a collection of output subbands.
codificación Huffman : Un procedimiento de codificación de entropía que asigna un código de longitud variable a cada símbolo de entrada. Huffman encoding: An entropy encoding procedure which assigns a variable length code to each input symbol.
tabla Huffman : El conjunto de códigos de longitud variable requeridos en un codificador Huffman. Huffman table: The set of variable length codes required in a Huffman coder.
datos de imagen : O los datos de imagen fuente o los datos de imagen reconstruida. image data: Either source data or reconstructed image data image.
sin pérdidas : Un término descriptivo para los procedimientos de codificación y descodificación en los que la salida del procedimiento o de los procedimientos de descodificación son idénticos a la entrada al procedimiento oa los procedimientos de codificación. lossless: A descriptive term for encoding and decoding procedures in which the output process or decoding methods are identical to the procedure or the input encoding methods.
imágenes RGB : Una imagen "roja-verde-azul", es decir, una imagen digital que se almacena como tres imágenes monocromáticas, cada una de las cuales representa uno de las tres componentes de color primarias. RGB images: A "red-green-blue" image, ie a digital image that is stored as three monochromatic images, each of which represents one of the three components of primary color.
tabla de cuantificación : El conjunto de valores de cuantificación (es decir, anchuras de contenedor) usados para cuantificar los coeficientes DWT dentro de las subbandas. quantization table: The set of quantization values (i.e., bin widths) used to quantize DWT coefficients within the subbands.
cuantificar : El acto de realizar el procedimiento de cuantificación para un coeficiente DWT. quantify: the act of performing the quantization process for DWT coefficient.
muestra : Un elemento de la matriz bidimensional que comprende una imagen. sample: One element of the two - dimensional array comprising an image.
sobremuestreo : Un procedimiento por medio del que se aumenta la resolución espacial de una imagen. upsampling: A procedure by which the spatial resolution of an image is increased.
Codificación de subbanda de la técnica anterior Subband coding of the prior art
La primera etapa en una implementación de ordenador de un algoritmo de compresión de imagen con pérdidas basado en DWT acarrea una descomposición DWT de la imagen de entrada. The first stage in a computer implementation of an algorithm for lossy image compression based on DWT carries a DWT decomposition of the input image. En el caso de técnica de imagen multiespectral (que incluye las imágenes RGB), se puede aplicar una transformación interespectral en esta etapa inmediatamente antes o después de la DWT. For multispectral imaging technique (which includes RGB images), you can apply a transformation interspectral at this stage immediately before or after the DWT. Siguiente a la transformación de la imagen, se cuantifican los coeficientes de DWT. Following the transformation of the image, DWT coefficients are quantized. Esta es la parte con pérdidas del algoritmo y asigna los coeficientes DWT a un flujo de índices de cuantificador. This is the part lossy algorithm and assigns the DWT coefficients to a quantizer flow rates. Finalmente, el flujo de índices del cuantificador se comprime con una técnica sin pérdidas. Finally, the flow rates of quantifier is compressed with a lossless technique. La descompresión de la imagen se consigue invirtiendo la compresión sin pérdidas, descodificando los símbolos del cuantificador, y después, realizando una DWT inversa. Image decompression is achieved by reversing the lossless compression, decoding the quantizer symbols, and then performing an inverse DWT. En "The Wavelet-Scalar Quantization Compression Standard for Digital Fingerprints Images", de JN Bradley y colaboradores, Proc. In "The Wavelet Scalar Quantization-Compression Standard for Digital Fingerprints Images" by JN Bradley et al, Proc. de IEEE International Symposium sobre circuitos y sistemas, del 31 de mayo al 2 de junio de 1994 se puede encontrar una discusión acerca del uso de la DWT en la compresión de imágenes. IEEE International Symposium on Circuits and Systems, from May 31 to June 2, 1994 You can find a discussion about the use of DWT in image compression.
La figura 1 es un diagrama de flujo de una implementación de un procesador de ordenador para una DWT directa (análisis) y una DWT inversa (síntesis) unidimensionales y forma un bloque básico de construcción en la implementación DWT bidimensional usada en la invención. Figure 1 is a flow chart of an implementation of a computer processor for direct DWT (analysis) and inverse DWT (synthesis) one-dimensional and forms a basic building block in the two-dimensional DWT implementation used in the invention. La entrada a la sección de análisis es la señal discreta en el tiempo x 10 a la sección de análisis 12 ya la sección de síntesis 14 . The input to the analysis section is the discrete - time signal x 10 to analysis section 12 and synthesis section 14. las secuencias discretas en el tiempo A_{0} 26 y A_{1} 28 son las señales subbanda de salida de la sección de análisis y forman la entrada a la sección de síntesis 14 . discrete time sequences A_ {0} 26 {1} and A 28 are the output subband signals the analysis section and form the input to synthesis section 14. Los sistemas h_{0} 16 y h_{1} 18 forman un par de filtros de respuesta al impulso finita (FIR) paso bajo-paso alto que separan las componentes de alta y de baja frecuencia de x 10 . The h_ {1} 18 {0} systems 16 and h_ form a pair of filter finite impulse response (FIR) lowpass-highpass separating the components of high and low frequency of x 10. Los sistemas 22 y 24 denotados por \downarrow2 son "inframuestreadores" que descartan cada segunda muestra de las salidas de los filtros. Systems 22 and 24 denoted by \ downarrow2 are "downsamplers" that discard every second sample of the filter outputs. El sistema de análisis se dice que está "críticamente muestreado", es decir, los datos se sacan del sistema a la misma velocidad en que entran. The analysis system is said to be "critically sampled", ie, the data is removed from the system at the same rate as they enter. Debido a las operaciones de inframuestreo, 22 y 24 , A_{0} 26 y A_{1} 28 son señales de banda completa que representan, respectivamente, la información de baja y de alta frecuencia en x 10 . Because downsampling operations 22 and 24, A_ {0} 26 {1} and A 28 are full band signals that respectively represent information of low and high frequency x 10.
El procedimiento mostrado en la figura 1 introduce también las señales de subbanda A_{0} 26 y A_{1} 28 a una sección de síntesis 14 que sintetiza la señal \hat{x} 42 . The process shown in Figure 1 also introduces the subband signals A_ {0} 26 {1} A_ and 28 to a synthesis section 14 that synthesizes the \ {x} hat 42 signal. Los sistemas h_{0}' 36 y h_{1}' 38 forman otro par de filtros FIR paso bajo-paso alto y los sistemas 32 y 34 denotados por \uparrow2 son "sobremuestreadores" que incrementan la velocidad de muestreo de la señal insertando un cero entre muestras. {0} '36 and h_ {1}' 38 h_ systems form another pair of filters FIR lowpass-highpass and systems 32 and 34 denoted by \ uparrow2 are "oversamplers" that increase the sampling rate of the signal inserting a zero between samples. Si los cuatro filtros digitales, h_{0} 16 y h_{1} 18 , y h_{0}' 36 y h_{1}' 38 mostrados en la figura 1, se han elegido de manera apropiada, \hat{x} 42 es igual ax 10 , es decir, la sección de síntesis 14 mostrada en la figura 1 invierte la operación realizada por la sección de análisis 12 . If the four digital filters, h_ {0} 16 and h_ {1} 18, and h_ {0} '36 and h_ {1}' 38 shown in Figure 1, are chosen appropriately, \ hat {x} 42 is equal to x 10, i.e. synthesis section 14 shown in figure 1 inverts the operation performed by analysis section 12.
A menudo se usan realizaciones separadas para los dos procedimientos de síntesis y de análisis DWT bidimensionales, es decir, implementaciones en las que el correspondiente procedimiento unidimensional mostrado en la figura 1 se aplica de manera separada a cada fila y columna de la imagen. Often separate embodiments for the two methods of synthesis and analysis DWT dimensional, ie, implementations where the corresponding one-dimensional procedure shown in Figure 1 is applied separately to each row and column of the image so used. La figura 2 describe una DWT directa bidimensional independiente. Figure 2 describes an independent direct bidimensional DWT. El sistema de análisis de la figura 1 se aplica primero a cada fila de la imagen / 50 a través de un par de filtro FIR h_{0} 52 y h_{1} 54 , con inframuestreadores 56 y 58 para dividir cada fila en una subbanda paso bajo y subbanda paso alto. The analysis system of Figure 1 is first applied to each row of image / 50 through a pair of FIR filter h_ {0} 52 and h_ {1} 54, with downsamplers 56 and 58 to split each row into a subband lowpass and highpass subband. La subbanda paso bajo de cada fila de imagen se escribe como una fila en la matriz temporal A_{0}' 62 . The lowpass subband from each image row is written as a row into the temporary array A_ {0} '62. De manera similar, la subbanda paso alto de cada fila se escribe como una fila en la matriz temporal A_{1}' 64 . Similarly, the highpass subband of each row is written as a row in the temporary array A_ {1} '64.
Las columnas de cada matriz temporal son procesadas cada una de ellas con una DWT unidimensional de la figura 1. La matriz de subbanda paso bajo A_{0}' es procesada a través del par de filtros FIR h_{0} 66 y h_{1} 68 , con inframuestreadores 76 y 78 para dividir adicionalmente cada columna en subbandas paso bajo-paso bajo y paso bajo-paso alto. The columns in each temporary array are processed each with a one - dimensional DWT of Figure 1. The matrix subband lowpass A_ {0} 'is processed through the pair of FIR filters h_ {0} 66 and h_ {1 } 68, with downsamplers 76 and 78 to further split each column into lowpass-subband lowpass and lowpass-highpass. La matriz de subbanda paso alto A_{1}' es procesada a través del par de filtros FIR h_{0} 72 y h_{1} 74 , con inframuestreadores 82 y 84 para dividir además cada columna en subbandas paso alto-paso bajo y paso alto-paso alto. The matrix highpass subband A_ {1} 'is processed through the pair of FIR filters h_ {0} 72 and h_ {1} 74, with downsamplers 82 and 84 to further split each column into subbands high-pass lowpass and highpass-highpass.
El sistema básico mostrado en la figura 2 divide de esta manera la imagen de entrada l=A_{00,0} en cuatro subbandas, A_{00,1}, 86 , A_{01,1}, 88 , A_{10,1}, 92 , A_{11,1}, 94 , con soportes apropiados de frecuencia como se representa en la figura 3. En esta notación de subbanda A_{ij,k}, los subíndices iyj denotan el trayecto de filtro que fue usado en su creación. The basic system shown in Figure 2 thus splits the input image l = A {00.0} in four subbands, A_ {00.1}, 86 {01.1} A_, 88, A_ {10, 1}, 92 {11.1} A_, 94, with appropriate frequency supports as shown in figure 3. in this subband notation A_ {ij, k}, i and j subscripts denote the filter path that was used in its creation. El primer subíndice se refiere a la operación fila y el segundo subíndice se refiere a la operación columna, indicando con un "0" una operación paso bajo, y con un "1" una operación paso alto. The first subscript refers to the row operation and the second subscript refers to the column operation, indicating a "0" lowpass operation and a "1" one highpass operation. Por ejemplo, la subbanda A_{10} 92 se creó por medio de un filtrado paso alto sobre las filas de imagen seguido por un filtrado paso bajo sobre las columnas de A_{1}' 64 . For example, {10} 92 A_ subband is created by a highpass filtering on the image rows followed by lowpass filtering on the columns of A_ {1} '64. La imagen se resuelve en cuatro subbandas que contienen diferentes componentes de frecuencia de la imagen original, a partir de las cuales se puede sintetizar la imagen original, como se ha tratado para la figura 1. The image is resolved into four subbands that contain different frequency components of the original image, from which one can synthesize the original image, as discussed for Figure 1.
Se pueden conseguir particiones más finas de frecuencia poniendo en cascada el sistema de la figura 2. De manera típica, la subbanda paso bajo-paso bajo se saca repetidamente a este mismo procedimiento, dando como resultado una descomposición "dimensionada en octavas". Can get finer frequency partitions by cascading the system of Figure 2. Typically, the lowpass-subband is repeatedly lowpass shows this same procedure, resulting in decomposition "dimensioned in octaves". La figura 4, ilustra el soporte de frecuencia de una descomposición de subbanda resultante de tres cascadas. Figure 4 illustrates the frequency support of a subband decomposition resulting from three cascades. El tercer subíndice en la notación de subbanda denota el nivel de recursividad en la descomposición. The third subscript in the subband notation denotes the recursion in the decomposition. L denota el número de niveles en la cascada. L denotes the number of levels in the cascade. Nótese que A_{00,s} para 1 \leq s \leq L existe en etapas intermedias del proceso. Note that A_ {00} for 1 s \ leq s \? L exists in the middle stages.
En ocasiones es conveniente expresar la DWT dimensionada en octavas de l(x, y), es decir, la colección de subbandas A_{ij,k} (u, v) como Î (s, u,v), en la que s denota una ordenación unidimensional de las subbandas. It is sometimes convenient to express the DWT dimensioned octaves l (x, y), ie, the collection of subbands A_ {ij, k} (u, v) as Î (s, u, v), where s denotes a one dimensional ordering of the subbands. Por ejemplo, en la notación de subbanda mostrada en la figura 4, s=i+2j+3(Lk), y Î(0,u ,v), Î(1,u,v) = A_{0,1,L} (u,v), ..., Î(3L,u,v)= A_{11,1} (u, v). For example, in the subband notation shown in Figure 4, s = i + 2j + 3 (L k), and I (0, u, v), I (1, u, v) = A {0.1, L} (u, v), ..., Î (3L, u, v) = A {11,1} (u, v).
La entrada a la DWT unidimensional representada en la figura 1 se supone que es de duración infinita. The input to the one-dimensional DWT depicted in Figure 1 is assumed to be of infinite duration. Efectuar la DWT sobre una señal de longitud finita, por ejemplo, una fila o columna de la imagen, necesita la definición de las condiciones de límite de transformada. Perform DWT on a finite length signal, for example, a row or column of the image, need the definition of the boundary conditions transform. Las condiciones de contorno definen una extensión de la señal, es decir, una definición de la señal fuera de su dominio. The boundary conditions define a signal extension, i.e., a definition of the signal outside of its domain. Una condición de contorno que se usa comúnmente es la extensión periódica en la que la señal de longitud finita es visualizada como un periodo de una forma de onda periódica infinita. A boundary condition that is commonly used is the periodic extension in which the finite length signal is viewed as a period of a form of infinite periodic waveform. Otro ejemplo es las condiciones de contorno cero en las que la señal es visualizada como rellena con ceros. Another example is zero boundary conditions in which the signal is viewed as padded with zeros. Otro ejemplo más son las condiciones de contorno reflejadas en la que se extiende la señal realizando una imagen reflejada de los datos. Yet another example is reflected boundary conditions where the signal is extended by performing a mirror image of the data.
Descomposición de subbandas de imágenes de gran tamaño Subband decomposition large images
La invención consta de dos procedimiento principales: una rutina de compresión y una rutina de descompresión (navegación). The invention consists of two main procedures: a compression routine and a routine decompression (browsing). La rutina de compresión procede de manera similar que una compresión WSQ con la ventaja del uso de un sistema de memoria de dos niveles para acomodar las dimensiones de la imagen de gran tamaño. The compression routine proceeds in a similar manner as WSQ compression with the advantage of using a memory system of two levels to accommodate the dimensions of the large image. De acuerdo con un aspecto de la invención, la imagen es subdividida en varios cuadros de mosaico, cada uno de los cuales se procesa por medio de una rutina DWT. According to one aspect of the invention, the image is subdivided into several frames it mosaic, each of which is processed by a DWT routine. La rutina DWT usa condiciones de contorno dependientes de la cuadrícula de mosaico y se transfieren los datos con llamadas de la rutina DWT sobre otros cuadros de mosaico de imagen para producir de manera efectiva la misma salida que la rutina DWT sacaría si se aplicase a toda la imagen mientras que se proporciona un uso más ventajoso tanto de la memoria primaria como de la memoria secundaria. The DWT routine uses conditions dependent contour of the tile grid and the data is transferred to call the DWT routine on other pictures mosaic image to produce effectively the same output as the DWT routine would take if applied to all image while a more advantageous use of both the primary memory and the sub memory is provided. El proceso puede verse como una implementación solapamiento-adición de la DWT. The process can be viewed as an overlap-add implementation of the DWT. La implementación preferida de la invención se basa en la DWT separable de cuatro canales de la figura 2. Claramente, también son aplicables bancos de filtros no separables y de canal M. The preferred implementation of the invention is based on the separable DWT four channels of Figure 2. Clearly, banks are also applicable to non-separable filters and channel M.
La rutina de compresión The compression routine
Con referencia ahora a la figura 5, la rutina de compresión saca los datos comprimidos en un fichero de datos de imagen comprimido (CID) que está estructurado para la rápida recuperación multiescala local. Referring now to Figure 5, the compression routine outputs the compressed data in a data file compressed image (CID) that is structured for rapid local multiscale retrieval the. Se supone que los datos de la imagen existen en la memoria secundaria, por ejemplo, una memoria del disco duro de un ordenador, y pueden estar contenidos en un solo fichero o como un mosaico de subimágenes, cada subimagen contenida en un fichero separado. It is assumed that the image data exist in the secondary memory, for example, a hard disk memory of a computer, and may be contained in a single file or as a mosaic of subimages, each subimage contained in a separate file. Los datos de imagen se denotan por l(x, y) donde xyy son enteros tales que 0 \leq x < W_{i} y 0 \leq y < H_{i}. The image data are denoted by l (x, y) where x and y are integers such that 0 \? X <W_ {i} and 0 \ ≤ y <H {i}. Las imágenes de cuadrícula de mosaico son de las mismas dimensiones que l(x, y) pero tienen el soporte restringido a un subconjunto W_{t} \times H_{t} de las coordenadas (x, y). Images mosaic grid are of the same dimensions as I (x, y) but have support restricted to a subset {t} W_ \ {t} H times the coordinates (x, y). De manera más específica, More specifically,
sop\lfloor T_{ij} (x,y) \rfloor = \{(x,y)|t_{00,ij}\leq x<t_{01,ij},t_{10,ij}\leq y\leq t_{11,ij}\} sop \ lfloor T_ {ij} (x, y) \ rfloor = \ {(x, y) | t_ {00, ij} \ = x <t_ {01, ij}, t_ {10, ij} \ = y \ leq t_ {11} ij \}
y donde las cuatro esquinas de una cuadrícula de mosaico vienen dadas por and where the four corners of a mosaic grid are given by
t_{00,ij} = iW_{t} t_ {00, ij} = {t} iW_
t_{01,ij} = min((i+1) W_{t} - 1, W_{i-1}) t_ {01} ij = min ((i + 1)} W_ {t - 1, W_ {i-1})
t_{10,ij} = jH_{t} t_ {10} ij = {t} JH_
t_{11,ij} = min ((j+1) H_{t} - 1, H_{i-1}). t_ {11} ij = min ((j + 1) H {t} - 1 H {i-1}).
El número de imágenes de cuadrícula de mosaico viene dado por The number of images mosaic grid is given by
T=\left[\frac{W_{i}}{W_{t}}\right] \left[\frac{H_{i}}{H_{t}}\right] T = \ left [\ frac {W_ {{i}} {t}} W_ \ right] \ left [\ frac {H {i}} {H {t}} \ right]
No hay restricciones en las dimensiones de la imagen y no es necesario que W_{i} sea divisible por W_{t} o que H_{i} sea divisible por H_{t}. There are no restrictions on the image dimensions and need not W_ {i} is divisible by W_ {t} or {i} H is divisible by H {t}. Se permite que las imágenes de cuadrícula de mosaico para i = [W_{i}/W_{t}]-1 y para j = [H_{i}/H_{t}]-1 tengan regiones de soporte más pequeñas que W_{t} \times H_{t}. It allows images of tile grid for i = [W_ {i} / W_ {t}] - 1 and for j = [H {i} / H {T}] - 1 have support regions smaller than W_ {t} \ {t} H times. La presente invención reconoce que l(x, y) pueda ser representado como una superposición de los cuadros de mosaico, en la que The present invention recognizes that I (x, y) can be represented as a superposition of the tiles, in which
(1)l(x,y)=\sum\limits_{i}\sum\limits_{j}T_{ij}(x,y) (1) l (x, y) = \ sum \ {i} limits_ \ sum \ {j} limits_ T_ {ij} (x, y)
y como la DWT es una transformación lineal, la DWT de l(x, y) se puede obtener sumando las DWT de la T_{ij} (x, y), es decir, and as the DWT is a linear transformation, the DWT of I (x, y) can be obtained by summing the DWT of T_ {ij} (x, y), that is,
(1a)\hat{I} (s,u,v)=\sum\limits_{i}\sum\limits_{j}\hat{T}_{ij}(s,u,v) (1a) \ hat {I} (s, u, v) = \ sum \ {i} limits_ \ sum \ {j} limits_ \ hat {T} _ {ij} (s, u, v)
en la que s se ha definido anteriormente. where s is defined above. Como se describirá a continuación, realizar una DWT de manera separada sobre las imágenes de cuadrícula de mosaico permite que una compresión basada en DWT ocurra sobre la imagen con unos requisitos mínimos de memoria. As described below, performing a DWT separately on the tile images grid allows a DWT-based compression to occur on the image with minimal memory requirements.
Las T_{ij} son procesadas de manera secuencial en la rutina de compresión. The T_ {ij} are processed sequentially in the compression routine. Esto requiere una ordenación unidimensional de las T_{ij} que es denotada por \theta(\tau) = (i, j). This requires a one-dimensional ordering of T_ {ij} which is denoted by \ theta (\ tau) = (i, j). (Esto es, la cuadrícula de mosaico de imagen \tau^{ésima} que va a ser sometida a transformación de tren de ondas es T_{\theta (\tau)}. La suma en la ecuación (1a) no se evalúa siguiente al cálculo de todas las \hat{T}_{ij}(s, u, v). En lugar de esto, esta suma es actualizada tras cada iteración \tau como (That is, the grid image tile \ tau ^ {th} to be subjected to transformation wavelet is T _ {\ theta (\ tau)}. The sum in equation (1a) is not evaluated following the calculation of all \ hat {T} _ {ij} (s, u, v). rather, this sum is updated after each iteration \ tau
(2)\hat{I}_{\tau}(s,u,v)=\sum\limits_{t=1}^{\tau}\hat{T}_{\theta (t)}(s,u,v) (2) \ hat {I} _ {\ tau} (s, u, v) = \ sum \ limits_ {t = 1} ^ {\ tau} \ hat {T} _ {\ theta (t)} (s , u, v)
Después de haber calculado una T_{\theta (\tau)} (s, u, v), esta actualización implica solamente aquéllas Having calculated a T {\ theta (\ tau)} (s, u, v), this update involves only those
(s,u,v)\in sop[\hat{T}_{\theta (\tau)}(s,u,v)] (S, u, v) \ in supp [\ hat {T} _ {\ theta (\ tau)} (s, u, v)]
(Nótese que como h_{0} y h_{1} son FIR, \hat{T}_{ij} tienen un soporte finito). (Note that as h_ {0} and h_ {1} are FIR, \ hat {T} _ {ij} have finite support). En la rutina de compresión, el resultado de la ecuación (1a) nunca se almacena en su integridad. In the compression routine, the result of equation (1a) is never stored in its entirety. De manera periódica, algunos o todos los coeficientes DWT se comprimen y se escriben en una memoria secundaria. Periodically, some or all DWT coefficients are compressed and written to secondary memory. Esos coeficientes elegibles para compresión son Those coefficients eligible for compression are
(3)\{\hat{T}_{\theta (\tau)}(s,u,v)|\hat{T}_{\theta (\tau)}(s,u,v)=\hat{I} (s,u,v)\} (3) \ {\ hat {T} _ {\ theta (\ tau)} (s, u, v) | \ hat {T} _ {\ theta (\ tau)} (s, u, v) = \ hat {I} (s, u, v) \}
Efectuando secuencialmente una DWT sobre cada cuadrícula de mosaico de imagen y actualizando la suma en la ecuación (2), se puede efectuar una compresión DWT de toda la imagen con un uso eficiente de la memoria primaria. Sequentially effecting a DWT on each image tile grid and updating the sum in equation (2) can perform a DWT compression entire image with an efficient use of primary memory.
La rutina de compresión está parametrizada por W_{j}, W_{j}, W_{t}, y H_{t} así como el número de niveles L en la descomposición de subbanda; The compression routine is parameterized by {j} W_, W_ {j}, {t} W_, and H {T} and the number of levels L in the subband decomposition; un parámetro de tasa de bit R que especifica la relación de compresión; a parameter bit rate R that specifies the compression ratio; y los filtros de análisis h_{0} y h_{1}. and the analysis filters H {0} and h_ {1}. En la figura 5 se ilustra un diagrama de flujo del proceso de compresión. In figure 5 a flow chart of the compression process is illustrated. La rutina 110 comienza 112 con \tau = 1 y consiste en un bucle 136 indexado por \tau que itera sobre T_{ij}. The routine 110 begins 112 with \ tau = 1 and consists of a loop 136 indexed by \ tau iterating over T_ {ij}. La primera rutina encontrada en el bucle es Extraer Cuadrícula de Mosaico 118 , que lee los valores de píxel contenidos en sop[T_{ij}] de los datos de imagen y los almacena en la memoria primaria. The first routine encountered in the loop is Extract Tile grid 118, which reads the pixel values contained in supp [T_ {ij}] of the image data and stores them in primary memory. La cuadrícula de mosaico de imagen se almacena en una estructura de datos que contiene una descripción de su soporte así como un puntero a los valores de píxel. The grid image tile is stored in a data structure containing a description of its support as well as a pointer to the pixel values.
Se llama entonces a la subrutina DWT 120 (Transformada de Tren de Ondas discreta). It then calls the subroutine 120 DWT (Transform discrete wavelet). En la práctica, la DWT de cada T_{ij} no se efectúa operando sobre la matriz rellena de ceros de W_{i} \times W_{j}. In practice the DWT of each T_ {ij} is not effected by operating on the zero-padded matrix W_ {i} of \ {j} W_ times. Solamente es necesario proporcionar memoria para aquellos valores de T_{ij} (x, y) en los que (x, y) \in sop [T_{ij} (x, y)]. It is only necessary to provide memory for those values ​​of T_ {ij} (x, y) where (x, y) \ in supp [T_ {ij} (x, y)]. La rutina de la DWT unidimensional opera sobre las filas y las columnas de la matriz de datos de cuadrícula de mosaico con las condiciones de contorno apropiadas. The one-dimensional DWT routine operates on the rows and columns of the data matrix tile grid with appropriate boundary conditions. Las condiciones de contorno empleadas en las distintas llamadas a la rutina DWT unidimensional son dependientes de la posición de cuadrícula de mosaico T_{ij} en l. The boundary conditions employed in the various calls DWT routine are dependent dimensional grid position T_ {ij mosaic} in l. Las condiciones de contorno reflejadas se usan si el límite correspondiente de T_{ij} coincide con un límite de l, en caso contrario se usan las condiciones de contorno cero. Reflected contour conditions are used if the corresponding boundary of T_ {ij} coincides with a limit of l, otherwise zero boundary conditions are used. Nótese que la DWT 120 efectúa una transformada expansiva, esto es, el número de coeficientes distintos de cero que surgen de la rutina es generalmente mayor que el número de píxeles que se introducen a la misma. Note that DWT 120 effects an expansive transform, that is, the number of nonzero coefficients arising from the routine is generally greater than the number of pixels that are input to it.
Se llama a la subrutina Añadir Coeficientes 122 para recuperar las transferencias de datos para \hat{T}_{i-1, j} y \hat{T}_{i, j-1} que fueron almacenadas sobre la memoria primaria o secundaria por medio de la llamada de la subrutina Transferencia de Datos 126 (véase más adelante) para una iteración anterior de \tau, y después las suma a \hat{T}_{ij} realizando de manera efectiva la actualización en la ecuación (2). It calls the subroutine Add Coefficients 122 to retrieve the data transfers for \ hat {T} _ {i-1, j} and \ hat {T} _ {i, j-1} that were stored on primary memory or secondary through the subroutine call transfer data 126 (see below) for an earlier iteration of \ tau, and then adds them to \ hat {T} _ {ij} performing effectively update equation ( 2). Nótese que este proceso implica una restricción sobre \theta. Note that this process implies a restriction on \ theta. Claramente, no se puede proceder con el procesado sobre \hat{T}_{ij} (x, y) si no ha ocurrido ya sobre los cuadros de mosaico T_{i-1, j} (x, y) y T_{i, j-1} (x, y). Clearly, it can not proceed with the processing of \ hat {T} _ {ij} (x, y) if it has not already occurred on the tiles T_ {i-1, j} (x, y) and T_ { i, j-1} (x, y).
Se llama entonces a la subrutina Archivar Coeficientes 124 , que almacena en la memoria primaria aquellos coeficientes de tren de ondas de la ecuación (3) que no fueron almacenados anteriormente en un archivo de coeficientes. It then calls the subroutine File Coefficients 124, which stores in primary memory those wavelet coefficients of equation (3) that were not previously stored in a file of coefficients. La subrutina Transferencia de Datos 126 almacena los datos que son rellamados en posteriores llamadas a Añadir Coeficientes 122 . Data transfer subroutine 126 stores the data that is rellamados in subsequent calls to Add Coefficients 122. Se almacenan dos segmentos de datos: aquéllos que se usan cuando se llama a la subrutina Añadir Coeficientes 122 para T_{i j+1} Two data segments are stored: those that are used when calling the subroutine 122 Add Coefficients for T_ {i} j + 1
\{\hat{T}_{ij}(u,v)|(u,v) \in sop [\hat{T}_{ij}] Y \ sop[\hat{T}_{i+1.j}]\} \ {\ Hat {T} _ {ij} (u, v) | (u, v) \ in supp [\ hat {T} _ {ij}] Y \ sop [\ hat {T} _ {i + 1 .j}] \}
y aquéllos que se usen cuando Añadir Coeficientes 122 sea llamada para T_{i j+1} and those that are used when Add Coefficients 122 is called for T_ {i} j + 1
\{\hat{T}_{ij}(u,v)|(u,v) \in sop[\hat{T}_{ij}] I \ sop[\hat{T}_{i+1.j}]- sop\hat{T}_{i+1.j}\} \ {\ Hat {T} _ {ij} (u, v) | (u, v) \ in supp [\ hat {T} _ {ij}] I \ sop [\ hat {T} _ {i + 1 .j}] - sop \ hat {T} _ {i + 1j} \}
Las transferencias de datos se llevan a cabo a través de almacenamiento temporal sobre la memoria primaria o sobre la memoria secundaria. Data transfers are performed via temporary storage on the primary memory or secondary memory. Nótese que se supone que Note that it is assumed that
sop[\hat{T}_{ij}] I \ sop[\hat{T}_{i+2.j}] = \phi sop [\ hat {T} _ {ij}] I \ sop [\ hat {T} _ {i + 2.j}] = \ phi
sop[\hat{T}_{ij}] I \ sop[\hat{T}_{i.j+2}] = \phi sop [\ hat {T} _ {ij}] I \ sop [\ hat {T} _ {i.j + 2}] = \ phi
para todas las iy j. for all i and j.
De manera periódica, en la subrutina Comprimir Coeficiente 128 , algunos o todos los coeficientes DWT del archivo se comprimen y se escriben en la memoria secundaria, es decir, se vuelcan. Periodically, in subroutine Compress Coefficient 128, some or all of DWT coefficients of the file is compressed and written to secondary memory, ie they turn. De esta manera, la rutina de compresión procede con la memoria primaria de manera continua siendo asignada en Archivar Coeficiente 124 y siendo liberada en Comprimir Coeficiente 128 . Thus, the compression routine proceeds with primary memory continuously being allocated in Archive Coefficient 124 and being released Compress Coefficient 128. El índice \tau se indexa entonces 132 a \tau+1 y se repite el bucle 136 hasta \tau = T 138 , es decir, el número de cuadros de mosaico, y se termina la rutina 138 . The \ tau index is then indexed 132 to \ tau + 1 and the loop 136 is repeated until \ tau = T 138, i.e., the number of frames mosaic, and routine 138 ends.
En la implementación preferida de la invención, la compresión incluye la cuantificación escalar seguida por la codificación de longitud cero y Huffman de los índices del cuantificador. In the preferred implementation of the invention, the compression includes scalar quantization followed by Huffman encoding zero and the length quantizer indices. (También son claramente aplicables en este punto otras estrategias de cuantificación y procedimientos de codificación sin pérdidas). (They are also clearly applicable at this point other strategies quantization and lossless coding procedures). La cuantificación escalar requiere realizar la asignación de un bit que seleccione una anchura de bit para cada subbanda en base a las estadísticas de imagen local. Performing scalar quantization requires the assignment of a bit to select a bit width for each subband based on local image statistics. Para un volcado dado, se prefiere que todas las estadísticas de subbanda correspondan a aproximadamente la misma región de l. For a given dump it is preferred that all subband statistics correspond to roughly the same region l. Aunque un volcado particular puede no implicar la compresión de coeficientes de todas las subbandas, la estadística de todas las subbandas se utilizarán en la realización de una asignación global de bit. Although a particular dump may not involve compression of coefficients from all subbands, statistics from all subbands will be used in performing an overall bit allocation. El resultado es un esquema de compresión de imagen espacialmente adaptable con las anchuras de contenedor del cuantificador escalar y las longitudes de palabra de código Huffman una función de la posición espacial sobre la imagen. The result is an image compression scheme with spatially adaptive quantizer bin widths and lengths scalar Huffman code word a function of spatial position on the image. El número de llamadas de DWT 120 entre volcados depende de la subbanda. The number of calls of DWT 120 between dumps depends on the subband. En cada volcado de coeficiente, se genera una sola tabla Huffman para cada subbanda que se saca. On each coefficient dump a single Huffman table is generated for each subband is removed.
Se usa una jerarquía de bloqueo de coeficientes de dos niveles en el proceso de compresión. a hierarchy of coefficient blocking bilevel the compression process is used. El primer nivel es necesario por el hecho de que el archivo de coeficientes de tren de ondas debe ser periódicamente purgado (Comprimir Coeficientes 128 ), después de lo cual se codifica una subsección rectangular de una subbanda (es decir, un bloque). The first level is necessitated by the fact that the coefficient file wavelet must be periodically purged (Compress Coefficient 128), whereupon a rectangular subsection of a subband (i.e., a block) is coded. Además, antes de que se produzca un volcado, cada bloque de subbanda que se saca se bloquea además en subbloques más pequeños. In addition, before a dump occurs, each block is removed subband blocks further into smaller sub-blocks. El segundo nivel de bloqueo es para proporcionar el acceso rápido a una sección arbitraria del fichero CID durante la navegación de imagen. The second level lock is to provide quick access to an arbitrary section of the CID file during image browsing. Al salir en la memoria secundaria, se hace referencia al bloque mayor como un bloque Huffman y tiene información de cabecera que describe la tabla Huffman, la característica del cuantificador, el soporte de bloque y una tabla de desplazamiento que describe el desplazamiento relativo en el registro de datos comprimido de cada subbloque. On leaving the secondary memory, reference to the larger block as a Huffman block is and has header information that describes the Huffman table, the characteristic of the quantizer, the support block and an offset table describing the relative displacement in the register compressed data of each sub-block. Se hace referencia al bloque más pequeño como un subbloque Huffman. It references the smallest as a Huffman subblock block is made. Cada subbloque Huffman dentro de un bloque Huffman particular es típicamente comprimido con la misma característica de cuantificador y de la tabla Huffman. Each subblock within a particular Huffman block is typically compressed Huffman with the same quantizer characteristic and Huffman table. El fichero CID contiene una tabla de desplazamiento que describe el desplazamiento de cada bloque Huffman comprimido. The CID file has an offset table that describes the displacement of each block compressed Huffman.
La rutina de navegación Routine navigation
La rutina de navegación 140 mostrada en forma de diagrama de flujo en la figura 6 accede al fichero de memoria del ordenador CID generado por la rutina de compresión 110 mostrada en la figura 5 y genera valores de píxel para una secuencia de visualizaciones de ventana. The navigation routine 140 shown in flow diagram form in Figure 6 accesses the computer memory file generated CID compression routine 110 shown in Figure 5 and generates pixel values for a sequence of window displays. El procedimiento tiene la capacidad para funcionar en un entorno distribuido, es decir, en el que los datos se vayan a descomprimir en diferentes plataformas de computación a aquéllas en las que reside el fichero CID. The process has the ability to function in a distributed environment, ie, in which data is to be decompressed in different computing platforms to those where the CID file resides. El ordenador cliente envía peticiones al ordenador servidor que a su vez transmite los datos comprimidos necesarios para sintetizar una visualización de ventana supervisora. The client computer sends requests to the server computer which in turn transmits the compressed data necessary to synthesize a supervisor display window. El ordenador cliente realiza la operación de descomprimir los datos recibidos y de crear la visualización de monitor de ordenador. The client computer performs the operation of decompressing the received data and create display computer monitor. La rutina en el lado del ordenador cliente proporciona la gestión de una memoria caché que contiene datos de los accesos anteriores al fichero CID. Routine on the client side management computer provides a cache containing data from previous accesses to the CID file. Cualquier dato solicitado contenido en el caché puede ser recuperado de la memoria caché en lugar del ordenador servidor. Any data requested content in cache can be retrieved from the cache instead of the server computer memory. El esquema de caché tiene ventajas cuando una aplicación está limitada por el ancho de banda de transmisión y no se usa típicamente cuando el fichero ejecutable de descompresión y el fichero CID residen en la misma plataforma. The caching scheme is advantageous when an application is limited by transmission bandwidth and is not typically used when the decompression executable file and the CID file reside on the same platform.
Como las subbandas A_{00,s} para 0 \leq s \leq L se obtienen por medio de aplicaciones repetidas del filtrado paso bajo y de submuestreo duplicado, éstas forman representaciones de baja resolución de los datos de imagen originales. As subbands A_ {00} for 0 s \ leq s \? L are obtained by repeated applications of lowpass filtering and subsampling duplicate, they form low resolution representations of the original image data. La rutina de navegación 140 hace uso de esta propiedad multiescala de la descomposición de subbanda. Navigation routine 140 uses this property multiscale subband decomposition. Cuando se especifica una vista, el usuario está restringido a seleccionar una resolución que es una potencia de dos veces la resolución de la imagen original. When you specify a view, the user is restricted to select a resolution that is a power of two times the resolution of the original image. La generación de la visualización implica entonces la síntesis de la subsección apropiada de A_{00,s} desde el fichero CID. Display generation then involves the synthesis of the appropriate subsection of A_ {00} s from the CID file. De esta forma, la rutina de navegación 140 extrae un subconjunto relativamente pequeño de los coeficientes de tren de ondas que se introducen después en una DWT inversa de nivel (Ls). Thus, the navigation routine 140 extracts a relatively small coefficients of wavelet that are then introduced into an inverse DWT level (Ls) subset.
Una petición de datos de la subbanda A_{ij,s} (x, y) está descrita por el conjunto de coordenadas (x, y) que definen la subregión que se vaya a extraer. A data request subband A_ {ij} s (x, y) is described by the set of coordinates (x, y) defining the subregion to be extracted. Este conjunto se denota por a_{ij,s}, donde This set is denoted by a_ {ij, s}, where
a_{ij,s} = \{(x,y)|x_{ij,s,0} \leq x \leq x_{ij,s,1},y_{ij,s,0} \leq y \leq y_{ij,s,1}\} a_ {ij, s} = \ {(x, y) | x_ {ij, s, 0} \ = x \ leq x_ {ij, s, 1}, y_ {ij, s, 0} \ = y \ leq y_ {ij, s, 1} \}
Nótese que como se supone que la ventana es rectangular, los a_{ij,s} también son rectangulares. Note that since it is assumed that the window is rectangular, the a_ {ij} s are rectangular also. Se recalca que una vista a escala s requiere coeficientes de tren de ondas de A_{00,s}. It is emphasized that a view at scale s requires wavelet coefficients of A_ {00} s. Para s\neqL estos coeficientes no se almacenan de manera explícita pero se deben sintetizar a partir de un subconjunto de los coeficientes contenidos en el fichero CID. For s \ neqL these coefficients are not stored explicitly but must be synthesized from a subset of the coefficients contained in the CID file. La petición especifica subconjuntos a_{ij,s} para (s, i, j) en K, donde K = {(0,0,0)} \cup {(0,1,l), (1,0 l), (1,1,l)} | The request specifies subsets a_ {ij} s for (s, i, j) in K where K = {(0,0,0)} \ cup {(0,1, l), (1.0 l) (1,1, l)} | s < l \leq L}. s <l \? L}.
En la figura 6 se muestra una visión global de la rutina 140 . In Figure 6 an overview of the routine 140 is shown. El procedimiento 140 se inicia 142 y comienza por la lectura de la información de cabecera 144 del fichero CID que describe la estructura global de este fichero. The method 140 starts 142 and begins by reading header information 144 from the CID file that describes the overall structure of this file. La información de estructura incluye el número de niveles en la descomposición de subbanda, la anchura y la altura de imagen, los soportes y valores de coeficientes de los filtros de síntesis y la tabla de desplazamiento que describe las posiciones de los datos de tabla y de los registros de datos comprimidos. The structure information includes the number of levels in the subband decomposition, the width and height of image, the supports and coefficient values ​​of the synthesis filters and the offset table describing the locations of table data and compressed data records. El procedimiento llama entonces a la subrutina Seleccionar Parámetros de Vista 146 en la que se introducen los parámetros que especifican una petición de vista. The procedure then calls the subroutine Select View Parameters 146 in which the parameters specifying a view request are introduced. Estos parámetros incluyen la resolución sy el soporte de ventana a_{00,s}. These parameters include the resolution s and the window support a_ {00} s.
En este punto, se llama a la subrutina Determinar Soportes 148 , que evalúa los conjuntos a_{ij,s} que especifican los coeficientes de tren de ondas que se deben sintetizar a partir del fichero CID. At this point, it calls the subroutine Determine Supports 148, which evaluates the sets a_ {ij, s} that specify the wavelet coefficients that must be synthesized from the CID file. Los subconjuntos en el nivel s están relacionados con a_{00,s-1} por medio de las siguientes expresiones: The subsets at level s are related to a_ {00} s -1 by means of the following expressions:
x_{ij,s,0} = \left[\frac{x_{00,s-1.0} - l_{i1}}{2}\right] x_ {ij, s, 0} = \ left [\ frac {x_ {00} s-1.0 - l_ {i1}} {2} \ right]
x_{ij,s,1} = \left[\frac{x_{00,s-1.1} - l_{i0}}{2}\right] x_ {ij, s, 1} = \ left [\ frac {x_ {00} s-1.1 - l_ {i0}} {2} \ right]
y_{ij,s,0} = \left[\frac{y_{oo,s-1.0} - l_{i1}}{2}\right] y_ {ij, s, 0} = \ left [\ frac {y_ {oo, s-1.0} - {i1} l_} {2} \ right]
y_{ij,s,1} = \left[\frac{y_{00,s-1.1} - l_{i0}}{2}\right] y_ {ij, s, 1} = \ left [\ frac {y_ {00} s-1.1 - l_ {i0}} {2} \ right]
en las que el soporte de los filtros de síntesis viene dado por where the support of the synthesis filters is given by
sop{h_{0}} = [l_{00}, l_{01}] sop h_ {{0}} = [{00} l_, l_ {01}]
sop{h_{1}} = [l_{10}, l_{11}] sop h_ {1}} = {[l_ {10}, {11} l_]
La subrutina Determinar Soportes 148 acarrea la evaluación de estas ecuaciones para s < l \leq L. Subroutine Determine Supports 148 entails the evaluation of these equations for s <l \ leq L.
El caché existe en el cliente y se compone de una memoria caché y una tabla caché. The cache exists on the client and consists of a cache and a cache table. La memoria caché contiene datos de transmisiones anteriores de subpetición desde el servidor. The cache contains data from previous sub-request transmissions from the server. Para cada entrada en la memoria caché, hay una entrada de tabla caché que describe su soporte. For each entry in cache memory there is a cache entry table describing its support. El soporte de la entrada caché l-ésima para la subbanda A_{ij,s} está denotado por la entrada de tabla de caché e_{ij,s,l}. The support of the l-th cache entry for subband A_ {ij, s} is denoted by the table entry cache e_ {ij, s, l}. Tras haber hecho una petición de ventana, la subrutina Consulta a Caché 152 (véase la figura 7) accede a la tabla de caché y genera una descripción de los datos solicitados que están contenidos en la memoria caché. Having made a request window, the subroutine Cache Query 152 (see Figure 7) accesses the cache table and generates a description of the requested data that is contained in the cache. Claramente, durante la primera llamada a Consulta a Caché 152 , el caché estará vacío. Clearly, during the first call to Cache Query 152 the cache will be empty. Las entradas de datos de caché típicamente serán índices de coeficiente comprimidos de Huffman pero también pueden contener coeficientes de tren de ondas descomprimidos. The data inputs of cache indices will typically be Huffman compressed coefficient but may also contain decompressed coefficients train waves. Las entradas de datos de caché pueden existir en la memoria primaria o secundaria. The data inputs of cache can exist in primary or secondary memory.
Para la subbanda A_{ij,s} existen cero o más entradas de caché. For subband A_ {ij} s are zero or more cache entries. El soporte de las entradas de tabla de caché, denotadas por e_{ij,s,l}, para 1 \leq l \leq N_{ij,s}, describen el subconjunto de coeficientes de tren de ondas contenidos en la correspondiente entrada de memoria caché. The support table entries cache, denoted by e_ {ij, s, l}, for 1 \ leq l \ leq N_ {ij, s}, describe the subset of coefficients wavelet contained in the corresponding input cache. Los datos de A_{ij,s} que deben ser obtenidos desde el servidor vienen dados por Data A_ {ij} s that must be obtained from the server are given by
\{(A_{ij,s}(x,y)|(x,y) \in R_{ij,s})\} \ {(A_ {ij} s (x, y) | (x, y) \ in R_ {ij, s}) \}
para todo (s, i, j) \in K, for all (s, i, j) \ K,
Esto describe el subconjunto de A_{ij,s} requerido para la visualización que no está presente en memoria caché. This describes the subset of A_ {ij} s required for display that is not present in cache. Los datos que se transfieren entonces desde el fichero CID en el cliente al servidor son los registros que tienen soportes r_{ij,s,l} tales que The data is then transferred from the CID file on the client to the server are the records having r_ {ij supports, s, l} such that
r_{ij,s,l} \cap R_{ij,s} \neq \diameter r_ {ij, s, l} \ {R ij cap, s} \ neq \ diameter
Estos registros pueden ser subbloques Huffman o algún subconjunto del mismo. These records may be Huffman subblocks or some subset thereof.
Siguiendo a la subrutina Consulta a Caché 152 , el cliente transmite 154 la petición y espera los datos solicitados. Following the subroutine Cache Query 152, the client 154 transmits the request and expects the requested data. El servidor envía 154 la petición en forma de un paquete de subpeticiones, cada una de las cuales consta de datos comprimidos de una región rectangular de una subbanda particular. The server sends 154 the request in the form of a packet of subrequests, each of which consists of compressed data of a rectangular region from a particular subband. Las subpeticiones son recibidas 156 y la subrutina Actualizar Caché 158 almacena las subpeticiones de la transferencia de datos en la memoria caché, purga las entradas de caché menos usadas recientemente y registra cada evento de caché encontrado en la Consulta a Caché 152 . The subrequests are received 156 and subroutine Update Cache 158 the stores subrequests from the data transfer in cache memory, purges the cache entries least recently used records each event found in cache Cache Query 152. Se llama después a la subrutina Sintetizar Subbandas 162 para descomprimir los índices de cuantificador de los datos comprimidos en la transferencia de petición y reconstruye los coeficientes de tren de ondas. It then calls the subroutine Synthesize Subband 162 to decompress the quantizer indices from the compressed data in the request transfer and reconstructs the wavelet coefficients. El procedimiento llama entonces a la subrutina DWT inversa 164 , que sintetiza el subconjunto requerido de a_{00,s}. The procedure then invokes subroutine DWT Inverse to 164, which synthesizes the required subset of a_ {00} s.
Pero la DWT inversa 164 no calcula los valores reales de píxel que se usan en la visualización de ventana. But DWT Inverse 164 does not calculate the actual pixel values used in the display window. Esto se hace por medio de la subrutina Crear Imágenes de Ventana 166 con la salida de datos por medio de la DWT inversa 164 . This is done by the subroutine Create Window 166 with the data output by DWT Inverse 164. Como un ejemplo, la salida de la DWT inversa 164 puede ser en formato de punto flotante en cuyo caso, Crear Imágenes de Ventana 166 transforma estos valores en palabras de un octeto (después de un posible redimensionamiento). As an example, the output of DWT Inverse 164 may be in floating point format in which case Create Window 166 converts these values into words of a byte (after a possible resizing). En otro caso, los datos recuperados pueden ser palabras de dos octetos que contienen, por ejemplo, datos de elevación. Otherwise, the recovered data can be words of two octets containing, for example, elevation data. La subrutina Crear Imágenes de Ventana 166 en este caso, puede generar una vista compartida de relieve de los datos. The Create Window subroutine 166 in this case, can generate a shared view of the data highlighted. En esta etapa en el procedimiento de navegación, si se pide otra ventana 168 , el procedimiento vuelve 172 a la subrutina Seleccionar Vista 146 . At this stage in the process of navigation, if another window 168 is requested, the process returns to the subroutine 172 146 Select View. En cualquier otro caso, el programa termina 174 . Otherwise, the program terminates 174.
La rutina de descompresión tratada anteriormente limita la resolución de la imagen de navegación obtenible a una potencia de dos veces la resolución de la imagen original. The decompression routine discussed above limits the image resolution obtainable navigation to a power of two times the resolution of the original image. La generación de resolución arbitraria puede ser proporcionada por medio de la recuperación de la resolución de la potencia de dos más próxima mayor que la solicitada y realizando después un procedimiento de interpolación. The generation of arbitrary resolution can be provided by the recovery of the resolution of the nearest power of two larger than requested and then performing an interpolation procedure.
La invención inicialmente está pensada para su uso en una aplicación interactiva. The invention is initially intended for use in an interactive application. Inicialmente, el usuario ve una representación en baja resolución de la imagen sobre una pantalla de ordenador que proporciona un icono de una parte de gran tamaño de, o quizá toda, la escena de la imagen. Initially, the user sees a low resolution representation of the image on a computer screen icon that provides a large part of, or perhaps all, the scene of the image. Usando un dispositivo de apuntamiento de ordenador, tal como un ratón, el usuario puede interactuar con una imagen de baja resolución para especificar una región y escala de la longitud (una vista de imagen) para visualización. Using a computer pointing device, such as a mouse, the user can interact with a low resolution image to specify a region and length scale (a view image) for display. Estos parámetros se pasan entonces a la rutina de descompresión que recupera la vista deseada. These parameters are then passed to the decompression routine which retrieves the desired view. El procedimiento se puede repetir con el usuario interactuando con la escena original de baja resolución o con las imágenes posteriores devueltas por la rutina de descompresión. The procedure can be repeated with the user interacting with the original low-resolution scene or with subsequent images returned by the decompression routine. Durante dichas aplicaciones repetidas de la rutina de descompresión, la invención permite también la gestión de un caché de imagen para almacenar los resultados de los accesos previos a los datos. During these repeated applications of the decompression routine, the invention also allows managing an image cache to store the results of previous data accesses. Utilizando el caché de imagen, el proceso descrito en este documento necesita solamente recuperar esos datos solicitados por la consulta que no están en la memoria caché. Using the image cache, the process described in this document need only retrieve the data requested by the query that are not in the cache. El esquema de caché es particularmente ventajoso si los datos a los que se está accediendo sobre un enlace de datos que es lento comparado con el tiempo computacional asociado el proceso de descompresión. The caching scheme is particularly advantageous if the data being accessed over a data link that is slow compared to the computational time associated the decompression process.
Se entenderá que la anterior descripción y la nomenclatura de la reivindicación se presenta en una representación bidimensional para facilidad de descripción y nomenclatura. It is understood that the above description and nomenclature of claim presented in a two dimensional representation for ease of description and nomenclature. El proceso es igualmente aplicable a un proceso unidimensional ya un proceso tridimensional. The process is equally applicable to a one-dimensional process and a three-dimensional process. Solamente la designación de subíndices es diferente y el uso de nomenclatura bidimensional no debería ser interpretada como limitadora del ámbito de la invención reivindicada. Only the designation of subscripts is different and the use of two-dimensional nomenclature should not be construed as limiting the scope of the claimed invention.
La descripción anterior de la invención se ha presentado con propósitos ilustrativos y descriptivos y no está destinada a ser exhaustiva oa limitar la invención a la forma precisa descrita, y obviamente son posibles muchas modificaciones y variaciones a la luz de las enseñanzas anteriores. The foregoing description of the invention has been presented for illustrative purposes and descriptive and is not intended to be exhaustive or to limit the invention to the precise form disclosed, and obviously many modifications and variations in light of the above teachings are possible. Las realizaciones se eligieron y se describieron con el fin de explicar lo mejor posible los principios de la invención y su aplicación práctica para de esta manera hacer posible a otros que sean expertos en la técnica utilizar lo mejor posible la invención en varias realizaciones y con varias modificaciones según sean adecuadas para el uso particular contemplado. The embodiments were chosen and described in order to explain best the principles of the invention and its practical application to thereby enable others who are skilled in the art to best utilize the invention in various embodiments and with various modifications as are suited to the particular use contemplated. Está pensado que el ámbito de la invención sea definido por medio de las reivindicaciones adjuntas a la presente descripción. It is intended that the scope of the invention be defined by the appended claims to the present disclosure.
1. Un procedimiento para comprimir una imagen digital de gran tamaño para el almacenamiento en un ordenador, en el que las áreas seleccionadas de la imagen son visualizadas a varias resoluciones por medio de un ordenador que tiene una memoria primaria para el procesado de datos y una memoria secundaria para el almacenamiento de datos, comprendiendo el procedimiento los pasos de: 1. A method for compressing a digital image large for storage in a computer, wherein selected areas of the image are viewed at multiple resolutions by a computer having a primary memory for data processing and secondary memory for data storage, the method comprising the steps of:
almacenar un conjunto completo de datos de imagen l(x, y) que representan a dicha imagen en una primera posición de memoria secundaria de dicho ordenador; storing a complete set of image data I (x, y) representing said image in a first secondary memory location of said computer;
definir una pluralidad subconjuntos de datos de imagen de cuadrícula de mosaico discretos T_{ij}(x, y), en el que dicho conjunto completo datos de imagen l(x, y) está formado por medio de la superposición de dichos datos de imagen de cuadrícula de mosaico discretos T_{ij}(x, y); define a subset plurality of image data of discrete tile T_ {ij} (x, y), where said complete set of image data I (x, y) is formed by superimposing said image data of discrete tile T_ {ij} (x, y);
realizar uno o más procesos de compresión basados en transformaciones de tren de ondas discretas (DWT) sobre cada uno de mencionados datos de imagen de cuadrícula de mosaico T_{ij}(x, y) en una secuencia seleccionada para sacar cada uno de los datos de imagen de cuadrícula de mosaico discretos T_{ij}(x, y) como una sucesión de coeficientes de DWT en una sucesión de conjuntos de subbanda, en el que una subbanda de cada conjunto es una representación de baja resolución de dichos datos de imagen de cuadrícula de mosaico discretos T_{ij}(x, y) para formar una secuencia de representaciones de baja resolución de la mencionada matriz de datos de imagen l(x, y); performing one or more processes based compression transformations train of discrete waves (DWT) on each of said data image tile grid T_ {ij} (x, y) in a selected sequence to get each data image discrete tile T_ {ij} (x, y) as a succession of coefficients DWT on a sequence of sets of subband, where one subband of each set is a low-resolution representation of said image data of discrete tile T_ {ij} (x, y) to form a sequence of low resolution representations of said image data array I (x, y); y Y
mantener sumas actualizadas de dichos coeficientes DWT a partir de la mencionada imagen de cuadrícula de mosaico discreta T_{ij}(x, y) para formar una DWT sin junturas de la mencionada l(x, y) y almacenar dichas sumas en una segunda posición de memoria del mencionado ordenador. maintain sums date of said DWT coefficients from said image of tile grid discrete T_ {ij} (x, y) to form a seamless DWT of said I (x, y) and storing said sums in a second position said computer memory.
2. Un procedimiento de acuerdo con la reivindicación 1, incluyendo además el paso de: 2. A process according to claim 1, further comprising the step of:
comprimir de manera periódica dichas sumas y transferir dichas sumas comprimidas a una segunda memoria secundaria para mantener memoria suficiente en la mencionada memoria primaria para el procesado de datos. compressing said sums periodically and transferring said compressed sums to a second secondary memory to maintain sufficient memory in said primary memory for data processing.
3. Un procedimiento de acuerdo con la reivindicación 1, en el que el paso de realizar una o más DWT de cada uno de los mencionados datos de imagen de cuadrícula de mosaico T_{ij}(x, y) incluye el paso de fijar todos los valores de datos de imagen a cero fuera de dicha imagen de cuadrícula de mosaico para formar una matriz de cuadrícula de mosaico y realizar dicha DWT sobre la totalidad de la matriz de datos de cuadrícula de mosaico. 3. A process according to claim 1, wherein the step of performing one or more DWT of each said image data tile grid T_ {ij} (x, y) includes the step of setting all values ​​image data to zero outside said tile image grid to form a grid array and performing said DWT mosaic on the entire data matrix tile grid.
4. Un procedimiento de acuerdo con la reivindicación 1 ó 3, en el que dicha secuencia seleccionada para realizar dicha compresión DWT sobre los mencionados datos de imagen T_{ij}(x, y) es para comprimir los datos de imagen de cuadrícula de mosaico T_{i-1, \ j}(x, y) y T_{i, \ j-1}(x, y) antes de comprimir T_{ij}(x,y). 4. A process according to claim 1 or 3, wherein said selected compression for performing said DWT over said image data T_ {ij} (x, y) sequence is to compress the image data mosaic grid T_ {i-1, \ j} (x, y) and T_ {i \ j-1} (x, y) before compressing T_ {ij} (x, y).
5. Un procedimiento de acuerdo con cualquiera de las reivindicaciones de la 1 a la 3, en el que el paso de mantener sumas actualizadas de los mencionados coeficientes DWT incluye el paso de la recuperación de las sumas actualizadas de los coeficientes DWT para T_{i-1, \ j}(x,y) y T_{i, \ j-1}(x, y) y la suma a los coeficientes para T_{ij}(x, y). 5. A process according to any of claims 1 to 3, wherein the step of maintaining updated sums of DWT coefficients includes the step mentioned recovery updated sums of DWT coefficients for T_ {i -1, \ j} (x, y) and T_ {i \ j-1} (x, y) and the sum of the coefficients for T_ {ij} (x, y).
6. Un procedimiento de acuerdo con la reivindicación 1, incluyendo además los pasos de: 6. A process according to claim 1, further comprising the steps of:
seleccionar un conjunto de visualización de dichos datos de imagen l(x,y) para ser visualizados a una resolución deseada; selecting a set of display said image data I (x, y) to be viewed at a desired resolution;
determinar un subconjunto de visualización de los mencionados coeficientes de tren de ondas DWT que soportan dicho conjunto de visualización de los mencionados datos de imagen a dicha resolución deseada; determining a subset of display of the coefficients train DWT waves supporting said viewing set of said image data at said desired resolution; y Y
formar a partir de dicho subconjunto de los mencionados coeficientes DWT una visualización de ordenador del mencionado conjunto de visualización de dichos datos de imagen a la mencionada resolución deseada. forming from said subset of DWT coefficients one computer display said set display said image data to said desired resolution mentioned.
7. Un procedimiento de acuerdo con la reivindicación 6, en el que el paso de realizar una o más DWT de cada uno de los mencionados datos de imagen de cuadrícula de mosaico T_{ij}(x, y) incluye el paso de fijar todos los valores de datos de imagen a cero fuera de dichos datos de imagen de cuadrícula de mosaico para formar una matriz de datos de cuadrícula de mosaico que es soportada solamente sobre la mencionada imagen de cuadrícula de mosaico y realizar dicha DWT sobre la mencionada totalidad de la matriz de datos de cuadrícula de mosaico. 7. A process according to claim 6, wherein the step of performing one or more DWT of each said image data tile grid T_ {ij} (x, y) includes the step of setting all values ​​image data to zero outside said image data of tile grid to form a matrix grid data mosaic that is supported only on said image tile grid and performing said DWT over said entire data matrix grid mosaic.
8. Un procedimiento de acuerdo con la reivindicación 6 ó 7, en el que dicha secuencia seleccionada para realizar dicha compresión DWT sobre dichos datos de imagen de cuadrícula de mosaico T_{ij}(x, y) es para comprimir los datos de imagen de cuadrícula de mosaico T_{i-1, \ j}(x, y) y T_{i, \ j-1}(x, y) antes de comprimir T_{ij}(x, y). 8. A process according to claim 6 or 7, wherein said selected sequence for performing said DWT compression on said image data grid T_ {ij} mosaic (x, y) is to compress the image data tile grid T_ {i-1, \ j} (x, y) and T_ {i \ j-1} (x, y) before compressing T_ {ij} (x, y).
9. Un procedimiento de acuerdo con la reivindicación 6, en el que el paso de seleccionar un conjunto de visualización de dichos datos de imagen l(x, y) que vayan a ser visualizados a una resolución seleccionada comprende los pasos de especificar un conjunto de coordenadas (x, y) de los mencionados datos de imagen l(x, y) y leer la información almacenada relacionada que incluye el número de niveles de resolución para dichos conjuntos de subbanda, anchura y altura de imagen, soportes y valores de coeficiente para los filtros de síntesis, y una tabla de desplazamiento que describe las posiciones de los datos de la tabla y de los registros de datos comprimidos. 9. A process according to claim 6, wherein the step of selecting a set of display said image data I (x, y) that are to be displayed at a selected resolution comprises the steps of specifying a set of coordinates (x, y) of said image data I (x, y) and reading related stored information that includes the number of resolution levels for said sets of subband width and image height, supports and coefficient values ​​for synthesis filters, and an offset table describing the locations of table data and compressed data records.
10. Un procedimiento de acuerdo con la reivindicación 6, en el que el paso de seleccionar un subconjunto de visualización de dichos coeficientes de tren de ondas DWT incluye el paso de extraer los coeficientes de tren de ondas correspondientes a dicho conjunto de visualización ya los correspondientes filtros de síntesis para descomprimir los mencionados coeficientes de tren de ondas. 10. A process according to claim 6, wherein the step of selecting a subset of display of said wavelet coefficients includes the step of DWT coefficients extracted wavelet corresponding to said viewing set and corresponding synthesis filters for decompressing the coefficients mentioned wavelet.
11. Un procedimiento de acuerdo con la reivindicación 6, incluyendo además el paso de establecer una memoria caché para almacenar los coeficientes de tren de ondas descomprimidos para cada visualización de ordenador que se forma. 11. A process according to claim 6, further comprising the step of establishing a cache for storing decompressed coefficients train waves for each computer display memory is formed.
12. Un procedimiento de acuerdo con la reivindicación 11, en el que el paso de seleccionar un subconjunto de visualización de dichos coeficientes de tren de ondas DWT incluye un primer paso de determinar si dichos coeficientes son almacenados en dicha memoria caché. 12. A process according to claim 11, wherein the step of selecting a subset of display of said wavelet coefficients includes a first DWT step of determining whether said coefficients are stored in said cache.
ES96937039T 1995-11-14 1996-10-28 Digital storage and retrieval of large images. Expired - Lifetime ES2201207T3 (en)
US557475 1995-11-14
US08557475 US5710835A (en) 1995-11-14 1995-11-14 Storage and retrieval of large digital images
ES2201207T3 true ES2201207T3 (en) 2004-03-16
ES96937039T Expired - Lifetime ES2201207T3 (en) 1995-11-14 1996-10-28 Digital storage and retrieval of large images.
JP3512346B2 (en) * 1998-10-15 2004-03-29 ソニー株式会社 Wavelet decoding apparatus and method
US7245304B2 (en) * 2001-11-16 2007-07-17 Lockheed Martin Corporation System and method for managing compressed graphic image data
JP3948619B2 (en) * 2003-03-31 2007-07-25 株式会社リコー Image compression apparatus, an image compression method, program and recording medium
JP2000500936A (en) 2000-01-25 application
US5710835A (en) 1998-01-20 grant
EP0864135A1 (en) 1998-09-16 application
EP0864135A4 (en) 2001-06-13 application
DE69628760D1 (en) 2003-07-24 grant
EP0864135B1 (en) 2003-06-18 grant
WO1997018527A1 (en) 1997-05-22 application
DE69628760T2 (en) 2004-04-29 grant
Meyer et al. 2000 Fast adaptive wavelet packet image compression

References: resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución