4

ベクトル量子化の実装を、さまざまなタイプとベクトルの次元 (たとえば、バイトの 16 次元ベクトル、または double の 4d ベクトルなど) を処理できる C++ テンプレート クラスとして設計しようとしています。

私はアルゴリズムを読んでいて、ほとんどを理解しています：

こことここ

Linde-Buzo-Gray (LBG) アルゴリズムを実装したいのですが、クラスターを分割するための一般的なアルゴリズムを理解するのに苦労しています。平面の両側に等しい数があるように、クラスター内のベクトルを分割する平面 (超平面?) を定義する必要があると思います。

[編集して詳細情報を追加] これは反復プロセスですが、すべてのベクトルの重心を見つけることから始めて、その重心を使用して分割平面を定義し、平面の各側面の重心を取得し、続行すると思いますVQ アルゴリズムに必要な数のクラスターが得られるまで (途中で歪みが少なくなるように最適化を繰り返します)。上記の最初のリンクのアニメーションは、それをうまく示しています。

私の質問は次のとおりです。

重心を取得したら、平面を見つけるアルゴリズムは何ですか?

ベクトルをテストして、その平面の両側にあるかどうかを確認するにはどうすればよいですか?

4

2 に答える 2

2

1 つの重心から開始する場合は、基本的にそれを 2 倍にし、ポイントを任意の方向にわずかに離して分割する必要があります。平面は、その方向に直交する平面です。

しかし、その平面を計算する必要はありません。

より一般的には、領域 (i) は、他のどの重心よりも重心 c_i に近い点のセットとして定義されます。重心が 2 つある場合、各領域は半空間であり、(超) 平面で区切られます。

ベクトル x をテストして、平面のどちら側にあるかを確認する方法は? （それは2つの重心です）

距離 ||x-c1|| を計算するだけです。||x-c2||、最小値 (1 または 2) のインデックスは、点 x が属する領域を示します。

より一般的には、重心が n 個ある場合、すべての距離 ||x-c_i|| を計算すると、重心 x が最も近い (つまり、距離が最小になる) ことで、x が属する領域が得られます。

于 2010-04-10T07:14:01.867 に答える
0

アルゴリズムはよくわかりませんが、2 番目の質問は簡単です。

平面上の任意の点から問題の点まで伸びるベクトルをVと呼びましょう。次に、問題の点は、(超) 平面の​​法線N iff V·N > 0と同じ側にあります。

于 2010-04-10T04:59:44.093 に答える