Пирамидальное векторное квантование

Пирамидально-векторное квантование ( PVQ ) — это метод, используемый в аудио- и видеокодеках для квантования и передачи единичных векторов , то есть векторов, величины которых известны декодеру, но направления которых неизвестны. PVQ также может использоваться как часть схемы квантования усиления/формы , при которой величина и направление вектора квантоваются отдельно друг от друга. Первоначально PVQ был описан в 1986 году в статье Томаса Р. Фишера «Пирамидальный векторный квантователь».

Улучшение равномерности распределения точек PVQ за счет $w$ или $1/w$ координатная мощность $p_{i}\to \operatorname {sgn}(p_{i})(|p_{i}|)^{w}$ вектора перед проекцией. На диаграмме представлены созвездия для $N=3$ размеры и написанное $K=11,16,23,32$ Л1-норма .

Единственное предостережение PVQ заключается в том, что он работает на расстоянии, соответствующем такси (норма L1). Преобразование в/из более знакомого евклидова расстояния (L2-норма) возможно посредством векторной проекции , хотя это приводит к менее равномерному распределению точек квантования (полюса евклидовой n -сферы становятся более плотными, чем неполюсы). эффективный алгоритм идеального (то есть равномерного) векторного квантования евклидовой n -сферы неизвестен. По состоянию на 2010 год Эту неравномерность можно уменьшить, применяя перед проецированием деформацию, такую ​​​​как мощность по координатам, что снижает среднеквадратическую ошибку квантования на ~ 10%.

PVQ используется в аудиокодеке CELT (унаследованном от Opus ) и Daala видеокодеке .

Обзор

В качестве формы векторного квантования PVQ определяет кодовую книгу из M точек квантования, каждой из которых присваивается целочисленное кодовое слово от 0 до M -1. Цель кодера — найти кодовое слово ближайшего вектора, которое декодер должен декодировать обратно в вектор.

Кодовая книга PVQ состоит из всех N -мерных точек. ${\vec {p}}$ с целочисленными координатами, сумма абсолютных значений которых равна константе K (т. е. чья L1-норма равна K ). В обозначениях построителя множеств :

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

где $\left\|{\vec {p}}\right\|_{1}$ обозначает L1-норму ${\vec {p}}$.

В нынешнем виде множество S замощает поверхность N -мерной пирамиды. При желании мы можем преобразовать его в сферу, «проецируя» точки на сферу, то есть нормализовав их :

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

где $\left\|{\vec {p}}\right\|_{2}$ обозначает L2- норму ${\vec {p}}$.

Увеличение параметра K приводит к увеличению количества точек квантования и, следовательно, обычно дает более «точное» приближение исходного единичного вектора. ${\vec {v}}$ за счет более крупных целочисленных кодовых слов, для передачи которых требуется больше битов.

Пример

Предположим, мы хотим квантовать трехмерные единичные векторы, используя параметр K =2. Наша кодовая книга становится:

Кодовое слово Точка Нормализованная точка 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>

Кодовое слово Точка Нормализованная точка 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$ округляется до трех десятичных знаков.)

Теперь предположим, что мы хотим передать единичный вектор <0,592, -0,720, 0,362> (округленный здесь до 3 десятичных знаков, для ясности). Согласно нашей кодовой книге, ближайшей точкой, которую мы можем выбрать, является кодовое слово 13 (<0,707, -0,707, 0,000>), расположенное примерно на 0,381 единицы дальше от нашей исходной точки.

Увеличение параметра K приводит к увеличению кодовой книги, что обычно увеличивает точность реконструкции. Например, на основе приведенного ниже кода Python K =5 (размер кодовой книги: 102) дает ошибку всего 0,097 единиц, а K =20 (размер кодовой книги: 1602) дает ошибку всего 0,042 единицы.

Код 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(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)

Сложность

Кодовую книгу PVQ можно найти в $O(KN)$. Кодирование и декодирование также могут выполняться в $O(KN)$ с использованием $O(K+N)$ память.

Размер кодовой книги подчиняется повторяемости

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

с $V(N,0)=1$ для всех $N\geq 0$ и $V(0,K)=0$ для всех $K\neq 0$.

Решение в замкнутой форме имеет вид

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

где ${}_{2}F_{1}$ — гипергеометрическая функция .

См. также

• Векторное квантование
• ACELP
• Работа (аудиоформат)