Quantification vectorielle pyramidale - Pyramid vector quantization

La quantification vectorielle pyramidale ( PVQ ) est une méthode utilisée dans les codecs audio et vidéo pour quantifier et transmettre des vecteurs unitaires , c'est-à-dire des vecteurs dont les magnitudes sont connues du décodeur mais dont les directions sont inconnues. PVQ peut également être utilisé dans le cadre d'un schéma de quantification gain/forme , grâce à quoi l'amplitude et la direction d'un vecteur sont quantifiées séparément l'une de l'autre. Le PVQ a été initialement décrit en 1986 dans l'article "A Pyramid Vector Quantizer" de Thomas R. Fischer.

Amélioration de l'uniformité de la distribution des points PVQ par ou par la puissance des coordonnées du vecteur avant la projection. Le diagramme présente les constellations pour les dimensions et écrit L1-norm .${\style d'affichage w}$${\style d'affichage 1/w}$${\displaystyle p_{i}\to \operatorname {sgn}(p_{i})(|p_{i}|)^{w}}$${\style d'affichage N=3}$${\style d'affichage K=11,16,23,32}$

Une mise en garde de PVQ est qu'il fonctionne sous la distance de taxi (norme L1). La conversion vers/depuis la distance euclidienne plus familière (norme L2) est possible via la projection vectorielle , mais entraîne une distribution moins uniforme des points de quantification (les pôles de la n- sphère euclidienne deviennent plus denses que les non-pôles). Aucun algorithme efficace pour l'idéal ( à savoir, uniforme) quantification vectorielle euclidienne du n -sphere est connu sous le nom de 2010. Cette non-uniformité peut être réduite en appliquant la déformation comme la puissance de coordonnées sage avant la projection, ce qui réduit l' erreur de quantification quadratique moyenne par ~10 %.

PVQ est utilisé dans le codec audio CELT (maintenant Opus ) et le codec vidéo Daala .

Aperçu

En tant que forme de quantification vectorielle , PVQ définit un livre de codes de M points de quantification, à chacun desquels est affecté un mot de code entier de 0 à M- 1. Le but du codeur est de trouver le mot de code du vecteur le plus proche, que le décodeur doit recoder en vecteur.

Le livre de codes PVQ se compose de tous les points à N dimensions avec des coordonnées entières uniquement dont les valeurs absolues totalisent une constante K (c'est -à- dire dont la norme L1 est égale à K ). En notation set-builder : ${\displaystyle {\vec {p}}}$

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

où désigne la norme L1 de . ${\displaystyle \left\|{\vec {p}}\right\|_{1}}$${\displaystyle {\vec {p}}}$

En l'état, l'ensemble S tessele la surface d'une pyramide à N dimensions. Si vous le souhaitez, nous pouvons le remodeler en une sphère en "projetant" les points sur la sphère, c'est-à-dire en les normalisant :

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

où désigne la norme L2 de . ${\displaystyle \left\|{\vec {p}}\right\|_{2}}$${\displaystyle {\vec {p}}}$

L'augmentation du paramètre K entraîne plus de points de quantification et, par conséquent, donne généralement une approximation plus « précise » du vecteur unitaire d' origine au prix de mots de code entiers plus grands qui nécessitent plus de bits à transmettre. ${\displaystyle {\vec {v}}}$

Exemple

Supposons que nous souhaitions quantifier des vecteurs unitaires tridimensionnels en utilisant le paramètre K =2. Notre codebook devient :

(0,707 = arrondi à 3 décimales.) ${\displaystyle {\sqrt {2}}/2}$

Supposons maintenant que nous souhaitions transmettre le vecteur unitaire <0,592, -0,720, 0,362> (arrondi ici à 3 décimales, pour plus de clarté). Selon notre livre de codes, le point le plus proche que nous pouvons choisir est le mot de code 13 (<0,707, -0,707, 0,000>), situé à environ 0,381 unité de notre point d'origine.

L'augmentation du paramètre K donne un livre de codes plus grand, ce qui augmente généralement la précision de la reconstruction. Par exemple, sur la base du code Python ci-dessous, K = 5 (taille du livre de codes : 102) donne une erreur de seulement 0,097 unité et K = 20 (taille du livre de codes : 1602) donne une erreur de seulement 0,042 unité.

Code 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)

Complexité

Le livre de codes PVQ peut être recherché au format . L'encodage et le décodage peuvent également être effectués en utilisant la mémoire. ${\style d'affichage O(KN)}$${\style d'affichage O(KN)}$${\style d'affichage O(K+N)}$

La taille du livre de code obéit à la récurrence

${\style d'affichage V(N,K)=V(N-1,K)+V(N,K-1)+V(N-1,K-1)}$

avec pour tous et pour tous . ${\style d'affichage V(N,0)=1}$${\style d'affichage N\geq 0}$${\style d'affichage V(0,K)=0}$${\displaystyle K\neq 0}$

Une solution fermée est donnée par

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

où est la fonction hypergéométrique . ${\style d'affichage {}_{2}F_{1}}$

Voir également

• Quantification vectorielle
• ACELP
• Opus (format audio)

Les références