Quantizzazione vettoriale piramidale - Pyramid vector quantization

La quantizzazione vettoriale piramidale ( PVQ ) è un metodo utilizzato nei codec audio e video per quantizzare e trasmettere vettori unitari , ovvero vettori le cui grandezze sono note al decodificatore ma le cui direzioni sono sconosciute. PVQ può anche essere usato come parte di uno schema di quantizzazione guadagno/forma , per cui l'ampiezza e la direzione di un vettore sono quantizzate separatamente l'una dall'altra. Il PVQ è stato inizialmente descritto nel 1986 nell'articolo "A Pyramid Vector Quantizer" di Thomas R. Fischer.

Miglioramento dell'uniformità della distribuzione dei punti PVQ o della potenza coordinata del vettore prima della proiezione. Il diagramma presenta le costellazioni per le dimensioni e la norma L1 scritta .${\displaystyle w}$${\displaystyle 1/w}$${\displaystyle p_{i}\to \operatorname {sgn}(p_{i})(|p_{i}|)^{w}}$${\displaystyle N=3}$${\displaystyle K=11,16,23,32}$

Un avvertimento di PVQ è che opera sotto la distanza del taxi (norma L1). La conversione alla/dalla distanza euclidea più familiare (norma L2) è possibile tramite la proiezione vettoriale , anche se risulta in una distribuzione meno uniforme dei punti di quantizzazione (i poli della n- sfera euclidea diventano più densi dei non poli). A partire dal 2010 non è noto alcun algoritmo efficiente per la quantizzazione vettoriale ideale (cioè uniforme) della n- sfera euclidea . Questa non uniformità può essere ridotta applicando una deformazione come la potenza delle coordinate prima della proiezione, riducendo l'errore di quantizzazione quadratico medio di ~10%.

PVQ è utilizzato nel codec audio CELT (ora Opus ) e nel codec video Daala .

Panoramica

Come forma di quantizzazione vettoriale , PVQ definisce un vocabolario di M punti di quantizzazione, a ciascuno dei quali è assegnato un codice intero da 0 a M -1. L'obiettivo del codificatore è trovare la parola in codice del vettore più vicino, che il decodificatore deve decodificare nuovamente in un vettore.

Il codice PVQ è costituito da tutti i punti N- dimensionali con coordinate solo intere i cui valori assoluti si sommano a una costante K (cioè la cui norma L1 è uguale a K ). Nella notazione del set-builder : ${\displaystyle {\vec {p}}}$

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

dove denota la norma L1 di . ${\displaystyle \left\|{\vec {p}}\right\|_{1}}$${\displaystyle {\vec {p}}}$

Così com'è, l'insieme S tassella la superficie di una piramide N- dimensionale. Se lo si desidera, possiamo rimodellarlo in una sfera "proiettando" i punti sulla sfera, cioè normalizzandoli :

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

dove denota la norma L2 di . ${\displaystyle \left\|{\vec {p}}\right\|_{2}}$${\displaystyle {\vec {p}}}$

Aumentando il parametro K si ottengono più punti di quantizzazione e quindi si ottiene tipicamente un'approssimazione più "accurata" del vettore di unità originale al costo di parole di codice intere più grandi che richiedono più bit per la trasmissione. ${\displaystyle {\vec {v}}}$

Esempio

Supponiamo di voler quantizzare i vettori unitari tridimensionali usando il parametro K =2. Il nostro codice diventa:

(0,707 = arrotondato alla terza cifra decimale.) ${\displaystyle {\sqrt {2}}/2}$

Supponiamo ora di voler trasmettere il vettore unitario <0.592, -0.720, 0.362> (arrotondato qui a 3 decimali, per chiarezza). Secondo il nostro codice, il punto più vicino che possiamo scegliere è la parola codice 13 (<0.707, -0.707, 0.000>), situata a circa 0,381 unità di distanza dal nostro punto originale.

Aumentando il parametro K si ottiene un codebook più grande, che in genere aumenta l'accuratezza della ricostruzione. Ad esempio, in base al codice Python riportato di seguito, K =5 (dimensione libro di codici: 102) produce un errore di sole 0,097 unità e K =20 (dimensione libro di codici: 1602) produce un errore di sole 0,042 unità.

Codice Python

import itertools
import math
from typing import List, NamedTuple, Tuple


class PVQEntry(NamedTuple):
    codeword: int
    point: Tuple[int, ...]
    normalizedPoint: Tuple[float, ...]


def create_pvq_codebook(n: int, k: int) -> List[PVQEntry]:
    """
    Naive algorithm to generate an n-dimensional PVQ codebook
    with k pulses.
    Runtime complexity: 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(abs(x) ** 2 for x in p))
            q = tuple(x / norm for x in p)
            ret.append(PVQEntry(len(ret), p, q))

    return ret


def search_pvq_codebook(
    codebook: List[PVQEntry], p: Tuple[float, ...]
) -> Tuple[PVQEntry, float]:
    """
    Naive algorithm to search the PVQ codebook. Returns the point in the
    codebook that's "closest" to p, according to the Euclidean distance.)
    """
    ret = None
    min_dist = None
    for i in range(len(codebook)):
        q = codebook[i].normalizedPoint
        dist = math.sqrt(sum(abs(q[j] - p[j]) ** 2 for j in range(len(p))))
        if min_dist is None or dist < min_dist:
            ret = codebook[i]
            min_dist = dist

    return ret, min_dist


def example(p: Tuple[float, ...], k: int) -> None:
    n = len(p)
    codebook = create_pvq_codebook(n, k)
    print("Number of codebook entries: " + str(len(codebook)))
    entry, dist = search_pvq_codebook(codebook, p)
    print("Best entry: " + str(entry))
    print("Distance: " + 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)

Complessità

Il codebook PVQ può essere ricercato in . Anche la codifica e la decodifica possono essere eseguite utilizzando la memoria. ${\displaystyle O(KN)}$${\displaystyle O(KN)}$${\displaystyle O(K+N)}$

La dimensione del codebook obbedisce alla ricorrenza

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

con per tutti e per tutti . ${\displaystyle V(N,0)=1}$${\displaystyle\geq 0}$${\displaystyle V(0,K)=0}$${\displaystyle K\neq 0}$

Una soluzione in forma chiusa è data da

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

dove è la funzione ipergeometrica . ${\displaystyle {}_{2}F_{1}}$

Guarda anche

• Quantizzazione vettoriale
• ACELP
• Opus (formato audio)

Riferimenti