Pyramid vector quantization

Pyramid vector quantization (PVQ) is a method used in audio and video codecs to quantize and transmit unit vectors, i.e. vectors whose magnitudes are known to the decoder but whose directions are unknown. PVQ may also be used as part of a gain/shape quantization scheme, whereby the magnitude and direction of a vector are quantized separately from each other. PVQ was initially described in 1986 in the paper "A Pyramid Vector Quantizer" by Thomas R. Fischer.

Improving uniformity of PVQ point distribution by $w$ or $1/w$ coordinate-wise power $p_i\to \mathrm{sgn}(p_i)(|p_i|{)}^w$ of the vector before projection. Diagram presents constellations for $N=3$ dimensions and written $K=11,16,23,32$ L1-norm.

One caveat of PVQ is that it operates under the taxicab distance (L1-norm). Conversion to/from the more familiar Euclidean distance (L2-norm) is possible via vector projection, though results in a less uniform distribution of quantization points (the poles of the Euclidean n-sphere become denser than non-poles). No efficient algorithm for the ideal (i.e., uniform) vector quantization of the Euclidean n-sphere is known as of 2010. This non-uniformity can be reduced by applying deformation like coordinate-wise power before projection, reducing mean-squared quantization error by ~10%.

PVQ is used in the CELT audio codec (inherited into Opus) and the Daala video codec.

Overview

As a form of vector quantization, PVQ defines a codebook of Template:Var quantization points, each of which is assigned an integer codeword from 0 to Template:Var−1. The goal of the encoder is to find the codeword of the closest vector, which the decoder must decode back into a vector.

The PVQ codebook consists of all Template:Var-dimensional points $\overrightarrow{p}$ with integer-only coordinates whose absolute values sum to a constant Template:Var (i.e. whose L1-norm equals Template:Var). In set-builder notation:

$S(N,K)=\{\overrightarrow{p}\in {\mathbb{Z}}^N:{\Vert \overrightarrow{p}\Vert }_1=K\}$

where ${\Vert \overrightarrow{p}\Vert }_1$ denotes the L1-norm of $\overrightarrow{p}$.

As it stands, the set Template:Var tesselates the surface of an Template:Var-dimensional pyramid. If desired, we may reshape it into a sphere by "projecting" the points onto the sphere, i.e. by normalizing them:

$S_{\text{sphere}}(N,K)=\{\frac{\overrightarrow{p}}{{\Vert \overrightarrow{p}\Vert }_2}:\overrightarrow{p}\in S(N,K)\}$

where ${\Vert \overrightarrow{p}\Vert }_2$ denotes the L2-norm of $\overrightarrow{p}$.

Increasing the parameter Template:Var results in more quantization points, and hence typically yields a more "accurate" approximation of the original unit vector $\overrightarrow{v}$ at the cost of larger integer codewords that require more bits to transmit.

Example

Suppose we wish to quantize three-dimensional unit vectors using the parameter Template:Var=2. Our codebook becomes:

Codeword Point Normalized point 0 <−2, 0, 0> <−1.000, 0.000, 0.000> 1 <−1, −1, 0> <−0.707, −0.707, 0.000> 2 <−1, 0, −1> <−0.707, 0.000, −0.707> 3 <−1, 0, 1> <−0.707, 0.000, 0.707> 4 <−1, 1, 0> <−0.707, 0.707, 0.000> 5 <0, −2, 0> <0.000, −1.000, 0.000> 6 <0, −1, −1> <0.000, −0.707, −0.707> 7 <0, −1, 1> <0.000, −0.707, 0.707> 8 <0, 0, −2> <0.000, 0.000, −1.000>

Codeword Point Normalized point 9 <0, 0, 2> <0.000, 0.000, 1.000> 10 <0, 1, −1> <0.000, 0.707, −0.707> 11 <0, 1, 1> <0.000, 0.707, 0.707> 12 <0, 2, 0> <0.000, 1.000, 0.000> 13 <1, −1, 0> <0.707, −0.707, 0.000> 14 <1, 0, −1> <0.707, 0.000, −0.707> 15 <1, 0, 1> <0.707, 0.000, 0.707> 16 <1, 1, 0> <0.707, 0.707, 0.000> 17 <2, 0, 0> <1.000, 0.000, 0.000>

(0.707 = $\sqrt{2}/2$ rounded to 3 decimal places.)

Now, suppose we wish to transmit the unit vector <0.592, −0.720, 0.362> (rounded here to 3 decimal places, for clarity). According to our codebook, the closest point we can pick is codeword 13 (<0.707, −0.707, 0.000>), located approximately 0.381 units away from our original point.

Increasing the parameter Template:Var results in a larger codebook, which typically increases the reconstruction accuracy. For example, based on the Python code below, Template:Var=5 (codebook size: 102) yields an error of only 0.097 units, and Template:Var=20 (codebook size: 1602) yields an error of only 0.042 units.

Python code

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(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 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 = 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)

Complexity

The PVQ codebook can be searched in $O(KN)$. Encoding and decoding can likewise be performed in $O(KN)$ using $O(K+N)$ memory.

The codebook size obeys the recurrence

$V(N,K)=V(N-1,K)+V(N,K-1)+V(N-1,K-1)$

with $V(N,0)=1$ for all $N\ge 0$ and $V(0,K)=0$ for all $K\ne 0$.

A closed-form solution is given by

$V(N,K)=2N\cdot {}_2{F}_1(1-K,1-N;2;2).$

where ${}_2{F}_1$ is the hypergeometric function.

See also

• Vector quantization
• ACELP
• Opus (audio format)