Lattice points enumeration using the l1 norm

Abstract

El uso de retículos como cuantizadores vectoriales en sistemas de compresión de imágenes fijas y de vídeo ha crecido notablmente en los últimos años, Para conseguir un compromiso entre una distorsión mínima y una baja taxa de transmisión, deben truncarse los retículos de manera que los puntos de retículo escogidos, que condicionan el tamaño del código, estén dentro de una frontera finita. La determinación de esta frontera depende de la fuente. Las propiedades geométricas de una fuente Laplaciana sin memoria son adecuadas para modelar las estadísticas de las imágenes transformadas. En tal caso, la norma 1 es preferible a la norma 1-2, hecho que implica que la clásica serie Theta de los retículos no deba ser utilizada. Las técnicas presentadas por otros autores para realizar el proceso de etiquetage de los puntos de retículo tienen el inconveniente de, o bien no conseguir una eficiencia plena en términos de la cantidad de bits necesarios, o bien, se se consigue dicha eficiencia, es a cargo de un escesivo tiempo de computación o de una capacidad de memoria demasiado elevada. En esta tesis definimos los puntos del contorno, que cuentan los puntos de retículo que se encuentran a distancia m de un punto de retículo fijado, es decir, ayudan a establecer la frontera del retículo (el tamaño). Se dan también expresiones combinatóricas explícitas para calcular los puntos del contorno para el retículo de los enteros, para el retículo raiz A, para el retículo raiz D, para su dual Dº, para el empaquetado D+, y para retículos resultantes de una construcción A o B. Estas expresiones son fácilmente implementables en cualquier lenguaje de programación, y son útiles para los algoritmos de etiquetage eficientes. Por último, se prueban diversas equivalencias combinatóricas entre propuestas presentadas pro diversos autores.