04 Cuantificacion

Cuantificación

Codificación de imágenes y video
















Un poco de historia
Definiciones
Performance de un cuantificador
El cuantificador escalar

Performance del cuantificador escalar

El cuantificador escalar uniforme
VQ: una extensión de la cuantificación escalar?
Codificador – Decodificador
Cuantificadores de Vecino Más Cercano
Condiciones de optimalidad
Diseño de unCuantificador Vectorial

Codebook Inicial

Algoritmo de Lloyd (ejemplo)
VQ: imágenes fijas
VQ: video
VQ: aplicaciones y variantes

lunes, 10 de mayo de 2004

Codificación de imágenes y video

Temario

2

Un poco de historia
 1898 - W.F.Sheppard, “On the calculation of the most probable
values of frequency constant for data arranged according to equidistant
division of scales”, primer análisisde la cuantificación escalar, error
de redondeo, etc.
 1948 - C.E.Shannon, “A mathematical theory of communnication”
 1956 - Steinhaus considera un problema equivalente a una
generalización 3D de la cuantificación escalar. En este trabajo se
derivan lo que hoy se conocen como las condiciones de optimalidad de
Lloyd.
 1957 - S.P.Lloyd “Least squared quantization in PCM”, condiciones
necesarias ysuficientes para la optimalidad local de cuantificadores de
rate fijo.
 1959 - C.E.Shannon “Coding theorems for a discrete source with
fidelity criterion”, esboza para fuentes i.i.d., MSE y codificación en
bloques
 1959 - Toth describe una especificación del problema planteada por
Steinhaus en 2D y lo resuelve con un cuantificador vectorial con
regiones hexagonales.
lunes, 10 de mayo de 2004Codificación de imágenes y video

3

Un poco de historia (VQ)
 Principios de `60 son ‘redescubiertas’ las condiciones de optimalidad
de Lloyd, Steinhaus y Zador, y los algoritmos de diseño de Lloyd y
Steinhaus en la literatura de statistical clustering.
 1965-1969 - desarrollo de algoritmos basados en aplicaciones de
statistical clustering (selección de templates que representen una grancolección de datos)
 1974-75 - Chaffee y Omura: aplicaciones de VQ a speech vocoding
 1977 - Hilbert: aplicaciones de VQ a compresión y clasificación de
imágenes
 1978-79 - Aplicaciones de VQ a LPC speech
 Julio 1979 - A.Gersho “Asimptotically optimal block quantization”,
popularizó y potencializó las mejoras en la performance de VQ, e
introdujo los lattice VQ para alcanzar asintoticamente laoptimalidad.
 1980 - Linde, Buzo y Gray “An algorithm for vector quantizer
design”, extiende el algoritmo de Lloyd al diseño de cuantificadores
vectoriales
 década de ‘80 - publican varios tutorial que popularizan y hacen
accesible el tema......
lunes, 10 de mayo de 2004

Codificación de imágenes y video

4

Definiciones


Cuantificador
Función (mapeo) de un vector de un espacio euclídeo de
dimensión ken un conjunto finito C (codebook)
conteniendo N vectores de salida yi (code-vector), esto es
Q : Rk  C

C ={y 1, ⋯, y N }

y i ∈R k

 Celdas o Regiones
Asociado a cada uno de los N code-vectors existe una
celda o región Ri definida como
Ri ={x∈R k /Q  x= y i }
lunes, 10 de mayo de 2004

Codificación de imágenes y video

5

Definiciones
 Celdas o Regiones
De la definición de celda sedesprende que
N
. ∪i=1
Ri =ℝ k

Ri ∩R j =∅ para i≠ j

 Cuantificador regular
Un cuantificador vectorial es regular si cada celda es un
conjunto convexo y si cada
y i ∈Ri

lunes, 10 de mayo de 2004

Codificación de imágenes y video

6

Medición de la performance
de un cuantificador






Proceso con pérdida.
Se modela la entrada como una variable aleatoria, x,
especificada por su función densidad deprobabilidad, fx(x).
Distorsión: media estadística de la distancia entre x y Q(x),
D=E [ d  x ,Q  x  ]=∫ d  x , Q  x  f X  x dx
ℝk

lunes, 10 de mayo de 2004

Codificación de imágenes y video

7

Medición de la performance
de un cuantificador
La performance de un cuantificador es especificada en
términos de la relación señal-ruido, definida como el cociente
entre la potencia de la...