ピラミッドベクトル量子化

ピラミッドベクトル量子化（PVQ）は、オーディオおよびビデオコーデックで単位ベクトル（デコーダーには大きさはわかっているが方向は不明なベクトル）を量子化して送信するために使用される方法です。PVQは、ベクトルの大きさと方向が互いに別々に量子化されるゲイン/シェイプ量子化スキームの一部としても使用できます。PVQは、1986年にThomas R. Fischerの論文「ピラミッドベクトル量子化器」で最初に説明されました。^[1]

PVQ の注意点の 1 つは、タクシー距離(L1 ノルム)で動作することです。より一般的なユークリッド距離(L2 ノルム) との変換はベクトル投影によって可能ですが、量子化ポイントの分布が均一ではなくなります (ユークリッドn球面の極は非極よりも密になります)。^{[3]ユークリッド}n球面の理想的な (つまり均一な) ベクトル量子化のための効率的なアルゴリズムは、2010 年時点では知られていません。^[4] この不均一性は、投影前に座標ごとの累乗などの変形を適用することで軽減でき、平均二乗量子化誤差を約 10% 削減できます。^[2]

PVQ は、 CELTオーディオ コーデック ( Opusに継承) およびDaalaビデオ コーデックで使用されます。

ベクトル量子化の形式として、PVQ はM 個の量子化ポイントのコードブックを定義します。各量子化ポイントには0 からM −1 までの整数コードワードが割り当てられます。エンコーダの目的は最も近いベクトルのコードワードを見つけることであり、デコーダはそれをベクトルにデコードする必要があります。

PVQコードブックは、絶対値の合計が定数K（つまり、L1ノルムがKに等しい）になる整数のみの座標を持つN次元のすべての点から構成されます。セットビルダー表記では、次のようになります。 ${\displaystyle {\vec {p}}}$

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

ここで はの L1 ノルムを表します。 ${\displaystyle \left\|{\vec {p}}\right\|_{1}}$${\displaystyle {\vec {p}}}$

現状では、集合S はN次元ピラミッドの表面をモザイク状に並べます。必要に応じて、点を球面に「投影」する、つまり正規化することで、球面に再形成できます。

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

ここで はのL2 ノルムを表します。 ${\displaystyle \left\|{\vec {p}}\right\|_{2}}$${\displaystyle {\vec {p}}}$

パラメータK を増やすと量子化ポイントが増え、通常は、送信に必要なビット数が増える整数コードワードが大きくなるという犠牲を払って、元の単位ベクトル のより「正確な」近似値が得られます。 ${\displaystyle {\vec {v}}}$

パラメータK =2 を使用して 3 次元単位ベクトルを量子化したいとします。コードブックは次のようになります。

（0.707 =小数点以下3桁に丸められます。） ${\displaystyle {\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 単位になります。

 itertools
をインポートします。math をtypeからインポートします。List  、NamedTuple 、Tuple をインポートします。
     


クラス PVQEntry ( NamedTuple ): 
    codeword :  int 
    point :  Tuple [ int ,  ... ] 
    normalizedPoint :  Tuple [ float ,  ... ]


def  create_pvq_codebook ( n :  int ,  k :  int )  ->  List [ PVQEntry ]: 
"""     k パルスを持つ    n 次元 PVQ コードブックを生成する単純なアルゴリズム。    実行時の複雑さ: 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 ))    




      
           
               
                    
                    
              

    リターン ret


def  search_pvq_codebook ( 
    codebook :  List [ PVQEntry ],  p :  Tuple [ float ,  ... ] 
)  ->  Tuple [ PVQEntry ,  float ]: 
"""     PVQ コードブックを検索するための単純なアルゴリズムです。    ユークリッド距離に従って、コードブック内で p に「最も近い」点を返します。)     """ 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    



      
      
       
          
                  
               
              
              

     ret 、 min_distを返す


def  example ( p :  Tuple [ float ,  ... ],  k :  int )  ->  None : 
    n  =  len ( p ) 
    codebook  =  create_pvq_codebook ( n ,  k ) 
    print ( "コードブックエントリの数: "  +  str ( len ( codebook ))) 
    entry ,  dist  =  search_pvq_codebook ( codebook ,  p ) 
    print ( "最適なエントリ: "  +  str ( entry )) 
    print ( "距離: "  +  str ( dist ))


φ  =  1.2 
θ  =  5.4 
x  =  math.sin ( φ ) * math.cos ( θ ) y = math.sin ( φ ) * math.sin ( θ ) z = math.cos ( φ ) p = ( x , y , z )例( p , 2 )例( p , 5 )例( p , 20 )​​​​​​​​​​  
    
  
    
 
 
 

PVQコードブックはで検索できます。^[4]エンコードとデコードはメモリを使用して同様に実行できます。^[5]${\displaystyle O(KN)}$${\displaystyle O(KN)}$${\displaystyle O(K+N)}$

コードブックのサイズは再帰性に従う^[4]

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

みんなのために、みんなのために。 ${\displaystyle V(N,0)=1}$${\displaystyle N\geq 0}$${\displaystyle V(0,K)=0}$${\displaystyle K\neq 0}$

閉形式の解は^{[6]で与えられる。}

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

ここで は超幾何関数です。 ${\displaystyle {}_{2}F_{1}}$

• ベクトル量子化
• ACELP
• Opus（オーディオ形式）