Cuantización vectorial piramidal

La cuantización vectorial piramidal ( PVQ ) es un método utilizado en códecs de audio y vídeo para cuantizar y transmitir vectores unitarios , es decir, vectores cuyas magnitudes son conocidas por el decodificador, pero cuyas direcciones son desconocidas. La PVQ también puede utilizarse como parte de un esquema de cuantización de ganancia/forma , en el que la magnitud y la dirección de un vector se cuantizan por separado. La PVQ fue descrita inicialmente en 1986 en el artículo "A Pyramid Vector Quantizer" de Thomas R. Fischer. ^{[ 1 ]}

Una advertencia de PVQ es que opera bajo la distancia de taxi (norma L1). La conversión a/desde la distancia euclidiana más familiar (norma L2) es posible mediante proyección vectorial , aunque resulta en una distribución menos uniforme de los puntos de cuantización (los polos de la n- esfera euclidiana se vuelven más densos que los no polos). ^{[ 3 ]} No se conoce ningún algoritmo eficiente para la cuantización vectorial ideal (es decir, uniforme) de la n- esfera euclidiana hasta 2010. ^{[ 4 ]} Esta falta de uniformidad puede reducirse aplicando una deformación como potencia por coordenadas antes de la proyección, reduciendo el error cuadrático medio de cuantización en ~10%. ^{[ 2 ]}

PVQ se utiliza en el códec de audio CELT (heredado en Opus ) y en el códec de vídeo Daala .

Como una forma de cuantización vectorial , PVQ define un libro de códigos de M puntos de cuantización, a cada uno de los cuales se le asigna una palabra clave entera del 0 al M − 1. El objetivo del codificador es encontrar la palabra clave del vector más cercano, que el decodificador debe decodificar de nuevo en un vector.

El libro de códigos PVQ consta de todos los puntos N -dimensionales.${\displaystyle {\vec {p}}}$con coordenadas enteras cuyos valores absolutos suman una constante K (es decir, cuya norma L1 es igual a K ). En notación de construcción de conjuntos :

${\displaystyle S(N,K)=\left\{{\vec {p}}\in \mathbb {Z} ^{N}:\left\|{\vec {p}}\right\|_{1}=K\right\}}$

dónde${\displaystyle \left\|{\vec {p}}\right\|_{1}}$denota la norma L1 de${\displaystyle {\vec {p}}}$.

Tal como está, el conjunto S tesela la superficie de una pirámide N- dimensional. Si se desea, podemos transformarlo en una esfera "proyectando" los puntos sobre ella, es decir, normalizándolos :

${\displaystyle S_{\text{sphere}}(N,K)=\left\{{\frac {\vec {p}}{\left\|{\vec {p}}\right\|_{2}}}:{\vec {p}}\in S(N,K)\right\}}$

dónde${\displaystyle \left\|{\vec {p}}\right\|_{2}}$denota la norma L2 de${\displaystyle {\vec {p}}}$.

Al aumentar el parámetro K se obtienen más puntos de cuantización y, por lo tanto, generalmente se consigue una aproximación más "precisa" del vector unitario original.${\displaystyle {\vec {v}}}$a costa de utilizar palabras clave enteras más largas que requieren más bits para su transmisión.

import itertools import math from typing import NamedTupleclase PVQEntry ( NamedTuple ): codeword : int point : tuple [ int , ... ] normalizedPoint : tuple [ float , ... ]def create_pvq_codebook ( n : int , k : int ) -> list [ PVQEntry ]: """  Algoritmo ingenuo para generar un libro de códigos PVQ n-dimensional  con k pulsos.  Complejidad de tiempo de ejecución: O(k**n)  """ ret = [] for p in itertools . product ( range ( - k , k + 1 ), repeat = n ): if sum ( abs ( x ) for x in p ) == k : norm = math . sqrt ( sum ( x ** 2 for x in p )) q = tuple ( x / norm for x in p ) ret . append ( PVQEntry ( len ( ret ), p , q ))regresar​def search_pvq_codebook ( codebook : list [ PVQEntry ], p : tuple [ float , ... ] ) -> tuple [ PVQEntry , float ]: """  Algoritmo ingenuo para buscar en el libro de códigos PVQ. Devuelve el punto en el  libro de códigos que está "más cerca" de p, según la distancia euclidiana.)  """ ret = None min_dist = None for entry in codebook : q = entry . normalizedPoint dist = math . sqrt ( sum (( q [ j ] - p [ j ]) ** 2 for j in range ( len ( p )))) if min_dist is None or dist < min_dist : ret = entry min_dist = distdevolver ret , min_distdef example ( p : tuple [ float , ... ], k : int ) -> None : n = len ( p ) codebook = create_pvq_codebook ( n , k ) print ( "Número de entradas del libro de códigos: " + str ( len ( codebook ))) entry , dist = search_pvq_codebook ( codebook , p ) print ( "Mejor entrada: " + str ( entry )) print ( "Distancia: " + str ( dist ))phi = 1.2 theta = 5.4 x = math.sin ( phi ) * math.cos ( theta ) y = math.sin ( phi ) * math.sin ( theta ) z = math.cos ( phi ) p = ( x , y , z ) example ( p , 2 ) example ( p , 5 ) example ( p , 20 )​​​​​​​​​​

El libro de códigos PVQ se puede buscar en${\displaystyle O(KN)}$. ^{[ 4 ]} La codificación y decodificación también se pueden realizar en${\displaystyle O(KN)}$usando${\displaystyle O(K+N)}$memoria. ^{[ 5 ]}

El tamaño del libro de códigos obedece la recurrencia ^{[ 4 ]}

${\displaystyle V(N,K)=V(N-1,K)+V(N,K-1)+V(N-1,K-1)}$

con${\displaystyle V(N,0)=1}$a pesar de${\displaystyle N\geq 0}$y${\displaystyle V(0,K)=0}$a pesar de${\displaystyle K\neq 0}$.

Una solución en forma cerrada viene dada por ^{[ 6 ].}

${\displaystyle V(N,K)=2N\cdot {}_{2}F_{1}(1-K,1-N;2;2).}$

dónde${\displaystyle {}_{2}F_{1}}$es la función hipergeométrica .

• Cuantización vectorial
• ACELP
• Opus (formato de audio)