最近ハードウェアを書いていないハードウェアプログラマです、こんにちは。加算がexor、乗算が指数領域での算術加算というガロア体演算回路を作ってRS符号を書いていた日々も過ぎ、JVTのドキュメントを読みながら高速動き探索と最適ブロック分割Rate-Distortionモデルを実装しつつ、H.264の動きベクトルはx、yそれぞれで単純に指数ゴルム符号かー、AC係数非ゼロ判定は1bit固定長で持ってるのね…とか言っていた日々も過ぎ去り、気が付けばベクトル量子化に立ち戻っていました。

そもそもベクトル量子化は、任意のベクトル集合を少数のベクトル集合で近似するものです。ようするに減色とかクラスタリングで、例えば256個あるベクトルを8個で近似する、とかいう話です。残念ながら完全な解はNP完全問題でして、カンペキな解法はありません。

一番簡単なやり方は、代表ベクトルが8個であれば、適当な初期ベクトルを8個決めておいて、256個のデータがどの代表ベクトルに近いか決めて、グルーピングします。次に、グループ内の重心を代表ベクトルにして、同じことを繰り返します。これがLBGアルゴリズムで、反復を重ねるごとに必ず誤差が小さくなることが保障されています。ただ、初期ベクトルに依存しまくりで、局所解に落ちまくります。

これを改善する方法がk-meanとあわせたLBGで、最初の代表ベクトルは1個にして、倍倍に増やしていきます。まず最初の代表ベクトルは、全データの重心、で、その重心に微小ベクトルεを足して、二本にします。で、二本のベクトルでLBGアルゴリズムをかけ、ある程度収束したら、また微小ベクトルεを足して二倍に増やします。で、LBG。これで、局所解には落ちにくくなります。

だがしかし、これでもまだ精度が足りないのが僕の現状です。はい、文献あたります。一応日本のお家芸だしねー。