피라미드 벡터 정량화

피라미드 벡터 정량화(PVQ)는 오디오 및 비디오 코덱에서 단위 벡터(즉, 디코더에 크기가 알려져 있지만 방향을 알 수 없는 벡터)를 정량화 및 전송하는 데 사용되는 방법이다.또한 PVQ는 벡터의 크기와 방향을 서로 분리하여 정량화하는 게인/모양 정량화의 일부로 사용될 수 있다.PVQ는 1986년 토마스 R의 "A Pyramid Vector Quantizer"라는 논문에서 처음 설명되었다.피셔.^[1]

투영

전 벡터

이름

p_{

i})(p_

{i})({p_{i})에 대한 w

{\

}

또는

w

1/w

/

1/w

{\

displaystyle

1/w

1/w

}

p_{i}\to \operatorname {sgn}(p_{i})(|p_{i}|)^{w}

p i →

p_{i}\to \operatorname {sgn}(p_{i})(|p_{i}|)^{w}

p_{i}\to \operatorname {sgn}(p_{i})(|p_{i}|)^{w}

(

p_{i}\to \operatorname {sgn}(p_{i})(|p_{i}|)^{w}

p_{i}\to \operatorname {sgn}(p_{i})(|p_{i}|)^{w}

)

p_{i}\to \operatorname {sgn}(p_{i})(|p_{i}|)^{w}

p_

{i})^{w}

에 의한 PQ 포인트 분포의 균일성 개선.^[2]다이어그램은

N=3

=

N=3

{\

displaystyle N=3

} 치수에

N=3

대한 별자리

K=11,16,23,32

K =

K=11,16,23,32

K=11,16,23,32

23

K=11,16,23,32

K=11,16,23,32

{\

displaystyle

K=

11,16,23,

32

}

L1-orm을

K=11,16,23,32

나타낸다.

PVQ의 한 가지 주의사항은 택사브 거리(L1-norm)에서 작동한다는 것이다.보다 친숙한 유클리드 거리(L2-norm)로의 변환은 벡터 투영을 통해 가능하지만 정량화 지점의 분포는 덜 균일해진다(유클리드 n-sphere의 극은 비폴더보다 밀도가 높아짐).^[3]2010년 현재 유클리드 n-sphere의 이상적인(즉, 균일한) 벡터 정량화를 위한 효율적인 알고리즘은 알려져 있지 않다.^[4]이러한 불균일성은 투영 전 좌표현 전력과 같은 변형을 적용하여 평균 제곱 정량화 오차를 10%까지 ^[2]감소시킴으로써 감소시킬 수 있다.

PVQ는 CELT 오디오 코덱(현재의 Opus)과 다알라 비디오 코덱에 사용된다.

개요

벡터 정량화의 한 형태로서 PVQ는 의 코드북을 정의한다.M정량화 점, 각 점에는 0부터 0까지의 정수 코드 단어가 할당됨M-1. 인코더의 목표는 가장 가까운 벡터의 암호어를 찾는 것인데, 디코더는 이를 다시 벡터로 해독해야 한다.

PVQ 코드북은 모두로 구성된다.N-dimension ${\vec {p}}$ → ${\$ 절대값이 상수에 합한 정수 전용 좌표 ${\vec {p}}$ K(즉, L1-norm이 동일한 사람)K. set-builder 표기법:

S(N,K)=\{{\vec{p}\in \mathb {Z} ^{N}}\{N}}\{\vec {p}\right\ _{1}=K\right\}}}}

여기서 $\left\|{\vec {p}}\right\|_{1}$ $\left\|{\vec {p}}\right\|_{1}$ → $\left\|{\vec {p}}\right\|_{1}$ $\left\|{\vec {p}}\right\|_{1}$ ${\$ }는 ${\vec {p}}$ → ${\$ 의 L1-norm을 나타낸다 $\left\|{\vec {p}}\right\|_{1}$ ${\vec {p}}$

현재 상태로는 세트장이S테셀화하다.N-차원 피라미드.원하는 경우, 점을 구체에 "투사"하여 구체로 재구성할 수 있다. 즉, 점을 정상화함으로써:

S_{\text}{{{n,K)=\좌측\{\frac {\vec}{p}{p}}{\vec}{p}}}}{{2}}:{\vec{p}\in S(N,K)\right\}}

여기서 $\left\|{\vec {p}}\right\|_{2}$ $\left\|{\vec {p}}\right\|_{2}$ $\left\|{\vec {p}}\right\|_{2}$ → $\left\|{\vec {p}}\right\|_{2}$ $\left\|{\vec {p}}\right\|_{2}$ ${\$ p → ${\$ 의 L2-norm을 나타낸다 ${\vec {p}}$

매개 변수 증가K 결과적으로 정량화 지점이 더 많아지고, 따라서 전송에 더 많은 비트가 필요한 더 큰 정수 코드 워드의 비용으로 ${\vec {v}}$ 원래 단위 ${\vec {v}}$ v ${\vec {v}}$ → ${\$ vec ${v}}$ 의 근사치가 더 "상호"된다.

예

파라미터를 사용하여 3차원 단위 벡터를 정량화한다고 가정합시다.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$ / ${\sqrt {2}}/2$ ${\sqrt{2}}/2$ 소수점 3자리 반올림 ${\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에 불과하다.

파이톤 코드

수입하다 이터툴스 수입하다 수학 로부터 타자 치기 수입하다 리스트, 명명된 투플, 투플레   계급 PVQEntry(명명된 투플):     암호어: 인트로     점을 찍다: 투플레[인트로, ...]     정규화점: 투플레[둥둥 뜨다, ...]   반항하다 create_createq_codebook(n: 인트로, k: 인트로) -> 리스트[PVQEntry]:     """ n차원 PVQ 코드북을 생성하는 순진한 알고리즘 맥박으로 런타임 복잡성: O(k**n) """     되받아치다 = []     을 위해 p 에 이터툴스.상품(범위(-k, k + 1), 되풀이하여 말하다=n):         만일 합계를 내다(복근(x) 을 위해 x 에 p) == k:             규범을 정하다 = 수학.sqrt(합계를 내다(복근(x) ** 2 을 위해 x 에 p))             q = 터플(x / 규범을 정하다 을 위해 x 에 p)             되받아치다.덧셈을(PVQEntry(렌(되받아치다), p, q))      돌아오다 되받아치다   반항하다 검색_codeq_codebook(     코드북: 리스트[PVQEntry], p: 투플레[둥둥 뜨다, ...] ) -> 투플레[PVQEntry, 둥둥 뜨다]:     """ PVQ 코드북을 검색하는 순진한 알고리즘.에서 점을 반환함 유클리드 거리에 따라 p에서 "가장 가까운" 코드북). """     되받아치다 = 없음     min_min = 없음     을 위해 i 에 범위(렌(코드북)):         q = 코드북[i].정규화점         거리를 두다 = 수학.sqrt(합계를 내다(복근(q[j] - p[j]) ** 2 을 위해 j 에 범위(렌(p))))         만일 min_min 이다 없음 또는 거리를 두다 < min_min:             되받아치다 = 코드북[i]             min_min = 거리를 두다      돌아오다 되받아치다, min_min   반항하다 예시(p: 투플레[둥둥 뜨다, ...], k: 인트로) -> 없음:     n = 렌(p)     코드북 = create_createq_codebook(n, k)     인쇄하다("코드북 항목 수: " + 발을 동동 구르다(렌(코드북)))     입장권, 거리를 두다 = 검색_codeq_codebook(코드북, p)     인쇄하다("최상의 항목: " + 발을 동동 구르다(입장권))     인쇄하다("거리: " + 발을 동동 구르다(거리를 두다))   피 = 1.2 세타 = 5.4 x = 수학.죄를 짓다(피) * 수학.cas(세타) y = 수학.죄를 짓다(피) * 수학.죄를 짓다(세타) z = 수학.cas(피) p = (x, y, z) 예시(p, 2) 예시(p, 5) 예시(p, 20)

복잡성

PVQ 코드북은 $O(KN)$ N $O(KN)$ ) ${\displaystyle$ O $(KN)}$ 에서 검색할 수 있으며 $O(KN)$ ^[4] 인코딩 및 디코딩도 $O(K+N)$ + $O(K+N)$ ${\displaystyle O$ $(KN$ $)}$ 메모리를 사용하여 $O(K+N)$ O $O(KN)$ ( $O(KN)$ $O(KN)$ {\ $displaystystyle O$ $(K+N$ $)}$ 에서 수행할 수 있다.^[5]

코드북 크기는 재발을^[4] 준수한다.

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$ $N\geq 0$ $N\geq 0$ $V(N,0)=1$ $displaystyle N\geq 0}$ 에 $N\geq 0$ 대해 $V(N,0)=1$ $V(N,0)=1$ (N ) = $V(0,K)=0$ 1 ${\displaystyle$ V $(N,0$ )= $1},$ $V(0,K)=0$ $K\neq 0$ $K\neq 0$ 0 $K\neq 0$ 에 $V(0,K)=0$ 대해 ${\displaystystyle$ V $(0,$ K)= $0$ $K\neq 0$

폐쇄형 솔루션은 다음에 의해^[6] 제공된다.

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

여기서 ${}_{2}F_{1}$ ${}_{2}F_{1}$ ${\$ 1}은 ${}_{2}F_{1}$ (는) 초기하 함수다.

참고 항목

참조

^ Fischer, Thomas R. (July 1986). "A Pyramid Vector Quantizer". IEEE Transactions on Information Theory. 32 (4): 568–583. doi:10.1109/TIT.1986.1057198.
^ ^a ^b Duda, Jarek (2017). "Improving Pyramid Vector Quantizer with power projection". arXiv:1705.05285 [math.OC].
^ Valin, Jean-Marc (September 2013). "Pyramid Vector Quantization for Video Coding" (PDF). Xiph.Org Foundation. Retrieved April 4, 2021.
^ ^a ^b ^c Valin, Jean-Marc; Terriberry, Timothy B.; Montgomery, Christopher; Maxwell, Gregory (January 2010). "A High-Quality Speech and Audio Codec With Less Than 10 ms Delay". IEEE Transactions on Audio, Speech, and Language Processing. 18 (1): 58–67. arXiv:1602.05526. doi:10.1109/TASL.2009.2023186.
^ Terriberry, Timothy B. (2009). "cwrs.c". Opus. Xiph.Org Foundation. Retrieved April 6, 2021.
^ Terriberry, Timothy B. (December 2007). "Pulse Vector Coding". Xiph.Org Foundation. Archived from the original on September 30, 2019. Retrieved April 4, 2021.

[1] Fischer, Thomas R. (July 1986). "A Pyramid Vector Quantizer". IEEE Transactions on Information Theory. 32 (4): 568–583. doi:10.1109/TIT.1986.1057198.

[imp_pvq-2] Duda, Jarek (2017). "Improving Pyramid Vector Quantizer with power projection". arXiv:1705.05285 [math.OC].

[3] Valin, Jean-Marc (September 2013). "Pyramid Vector Quantization for Video Coding" (PDF). Xiph.Org Foundation. Retrieved April 4, 2021.

[celt_tasl-4] Valin, Jean-Marc; Terriberry, Timothy B.; Montgomery, Christopher; Maxwell, Gregory (January 2010). "A High-Quality Speech and Audio Codec With Less Than 10 ms Delay". IEEE Transactions on Audio, Speech, and Language Processing. 18 (1): 58–67. arXiv:1602.05526. doi:10.1109/TASL.2009.2023186.

[5] Terriberry, Timothy B. (2009). "cwrs.c". Opus. Xiph.Org Foundation. Retrieved April 6, 2021.

[cwrs-6] Terriberry, Timothy B. (December 2007). "Pulse Vector Coding". Xiph.Org Foundation. Archived from the original on September 30, 2019. Retrieved April 4, 2021.

[1]

[2]

[3]

[4]

[5]

[6]

Search

피라미드 벡터 정량화

네임스페이스

더

목차

개요

예

파이톤 코드

복잡성

참고 항목

참조