ロイドのアルゴリズム

Lloyd’s_algorithm
電気工学およびコンピュータ サイエンスでは、ボロノイ反復または緩和としても知られるロイドのアルゴリズムは、スチュアート P. ロイドにちなんで名付けられたアルゴリズムであり、ユークリッド空間のサブセットで等間隔の点のセットを見つけ、これらのサブセットを整形式で均一に分割します。サイズの凸セル。密接に関連するk -means クラスタリングアルゴリズムのように、重心を繰り返し見つけます。分割内の各セットの分割を行い、これらの重心のどれが最も近いかに従って入力を再分割します。この設定では、平均演算は空間領域の積分であり、最も近い重心演算はボロノイ図になります。
アルゴリズムはユークリッド平面に最も直接的に適用できますが、同様のアルゴリズムを高次元空間または他の非ユークリッドメトリックを持つ空間にも適用できます。ロイドのアルゴリズムを使用して、入力の重心ボロノイ分割に近い近似を作成できます。これは、量子化、ディザリング、点描に使用できます。ロイドのアルゴリズムの他のアプリケーションには、有限要素法での三角形メッシュの平滑化が含まれます。
ロイドのアルゴリズムの例。各反復における現在のサイト位置 (赤) のボロノイ図が表示されます。灰色の円は、ボロノイ セルの重心を表します。
反復 1
反復 2
反復 3
反復 15
最後の画像では、サイトはボロノイ セルの重心に非常に近くなっています。重心ボロノイ テッセレーションが見つかりました。
コンテンツ
1 歴史
2 アルゴリズムの説明
3 積分と重心計算
3.1 近似 3.2 正確な計算
4 収束
5 アプリケーション
6 異なる距離
7 こちらもご覧ください
8 参考文献
9 外部リンク

歴史
このアルゴリズムは、1957 年にBell Labsの Stuart P. Lloyd によって、パルス符号変調の手法として最初に提案されました。同様のアルゴリズムが Joel Max によって独自に開発され、1960 年に公開されたため、このアルゴリズムはLloyd-Max アルゴリズムと呼ばれることも

アルゴリズムの説明
ロイドのアルゴリズムは、入力ドメイン内にある数kのポイント サイトを最初に配置することから始まります。メッシュ スムージング アプリケーションでは、これらはスムージングされるメッシュの頂点になります。他のアプリケーションでは、ランダムに配置するか、適切なサイズの均一な三角形メッシュを入力ドメインと交差させることによって配置できます。
次に、次の緩和ステップを繰り返し実行します。
kサイトのボロノイ図が計算されます。
ボロノイ図の各セルを統合し、重心を計算します。
次に、各サイトをそのボロノイ セルの重心に移動します。

積分と重心計算
ボロノイ ダイアグラムの作成アルゴリズムは、特に 2 次元を超える入力の場合、非常に自明ではない可能性があるため、このダイアグラムを計算してそのセルの正確な重心を見つける手順は、近似値に置き換えることができます。

近似
一般的な単純化は、グラフィック ハードウェアのテクスチャバッファなど、細かいピクセル グリッドのような空間の適切な離散化を使用することです。セルはピクセルとして具現化され、対応するサイト ID でラベル付けされます。セルの新しい中心は、同じラベルが割り当てられたすべてのピクセルの位置を平均することによって近似されます。あるいは、モンテカルロ法を使用することもできます。モンテカルロ法では、ランダムなサンプル ポイントが固定された基本確率分布に従って生成され、最も近いサイトに割り当てられ、平均化されて各サイトの重心が近似されます。

正確な計算
他の空間への埋め込みも可能ですが、この詳細では、 L 2ノルムを使用するユークリッド空間を想定し、最も関連性の高い 2 つのシナリオ (2 次元と 3 次元) について説明します。
ボロノイ セルは凸形状であり、常にそのサイトを囲んでいるため、容易に積分可能なシンプリスへの自明な分解が存在します。
2 次元では、ポリゴン セルのエッジがそのサイトに接続され、傘型の三角形のセットが作成されます。
3 次元では、セルはいくつかの平面ポリゴンで囲まれており、最初に三角形分割する必要が
すべての頂点の平均など、ポリゴン フェースの中心を計算します。
多角形の面の頂点とその中心を結ぶと、平面の傘の形をした三角形分割ができます。
自明なことに、四面体のセットは、セルの外殻の三角形をセルのサイトに接続することによって得られます。
セルの統合とその重心(重心) の計算は、シンプリスの重心の重み付けされた組み合わせとして与えられるようになりました (以下では、c I
{textstyle mathbf {c} _{i}}

 ）。
二次元:
三角形の重心は、デカルト座標などを使用して簡単に計算できます。
重み付けは、シンプレックスとセルの面積比として計算されます。
三次元:
四面体の重心は、 3 つの二等分面の交点として求められ、行列ベクトルの積として表すことができます。
重み付けは、シンプレックスとセルの体積比として計算されます。
n 個の三角シンプリスと累積面積を持つ 2D セルの場合あ ハ=∑ I = 0 n a I
{textstyle A_{C}=sum _{i=0}^{n}a_{i}}

 （どこa I
{textstyle a_{i}}

 は単体三角形の面積)、新しいセル重心は次のように計算されます。 ハ =1 ハ ∑
I= 0 n c I a I
{ C={frac {1}{A_{C}}}sum _{i=0}^{n}mathbf {c} _{i}a_{i}}
  同様に、体積がⅤ ハ=∑ I = 0 n v I
{textstyle V_{C}=sum _{i=0}^{n}v_{i}}

 （どこv I
{textstyle v_{i}}

 は四面体シンプレックスの体積です)、重心は次のように計算されます。 ハ =1 ハ ∑
I= 0 n c I v I
{ C={frac {1}{V_{C}}}sum _{i=0}^{n}mathbf {c} _{i}v_{i}}

 

収束
緩和ステップが実行されるたびに、ポイントはわずかに均一な分布のままになります。間隔が狭いポイントは離れて移動し、間隔が広いポイントは互いに近くなります。1 次元では、このアルゴリズムは、重心ボロノイ テッセレーションとも呼ばれる重心ボロノイ図に収束することが示されています。高次元では、わずかに弱い収束結果が知られています。
アルゴリズムの収束が遅いか、数値精度の制限により収束しない場合がしたがって、ロイドのアルゴリズムの実世界への適用は、通常、分布が「十分に良好」になると停止します。一般的な終了基準の 1 つは、イテレーションでいずれかのサイトが移動した最大距離が事前設定されたしきい値を下回ったときに停止することです。収束は、ポイントを過度に緩和することによって加速できます。これは、各ポイントを重心までの距離のω倍移動することによって行われます。通常、 ωには 2 よりわずかに小さい値を使用します。

アプリケーション
ロイドの方法はもともとスカラー量子化に使用されていましたが、この方法がベクトル量子化にも拡張されていることは明らかです。そのため、情報理論のデータ圧縮技術で広く使用されています。ロイドの方法はコンピュータ グラフィックスで使用されます。これは、結果の分布がブルー ノイズ特性を持ち (「ノイズの色」も参照)、アーティファクトと解釈される可能性のある低周波成分がほとんどないことを意味します。これは、ディザリング用のサンプル位置を選択するのに特に適しています。ロイドのアルゴリズムは、点描のスタイルでドット描画を生成するためにも使用されます。このアプリケーションでは、参照画像に基づいて重心を重み付けして、入力画像に一致する点描イラストを生成できます。
有限要素法では、複雑なジオメトリを持つ入力ドメインがより単純な形状の要素に分割されます。たとえば、2 次元のドメイン (ユークリッド平面のサブセットまたは 3 次元のサーフェス) は、多くの場合、三角形に分割されます。有限要素法の収束には、これらの要素が適切に形成されていることが重要です。三角形の場合、多くの場合、正三角形に近い要素が好まれます。ロイドのアルゴリズムを使用して、他のアルゴリズムによって生成されたメッシュを滑らかにし、頂点を移動し、要素間の接続パターンを変更して、より厳密な正三角形を生成することができます。これらのアプリケーションは通常、メッシュのさまざまな部分での要素サイズの違いなど、メッシュの他の機能を保持するために、ロイドのアルゴリズムの反復回数を減らして収束を停止します。別の平滑化方法であるラプラシアン平滑化(メッシュの頂点が隣接する頂点の位置の平均に移動される)とは対照的に、ロイドのアルゴリズムはメッシュのトポロジを変更して、より等辺の要素に近づけ、問題を回避することができます。ラプラシアン平滑化で発生するもつれ。ただし、ラプラシアン スムージングは​​、より一般的に非三角形要素を持つメッシュに適用できます。

異なる距離
ロイドのアルゴリズムは通常、ユークリッド空間で使用されます。ユークリッド距離は、アルゴリズムで 2 つの役割を果たします。ボロノイ セルを定義するために使用されますが、重心は平均二乗ユークリッド距離を最小化する点であるため、各セルの代表点としての重心の選択にも対応します。そのセル内のポイントに。代替距離、および重心以外の代替中心点を代わりに使用することができます。たとえば、Hausner （2001)は、マンハッタン メトリクスの変形(局所的に異なる方向) を使用して、方向が画像の特徴と一致するほぼ正方形のタイルによる画像のタイリングを見つけ、タイル張りのモザイクの構築をシミュレートするために使用しました。 . このアプリケーションでは、メトリックを変更したにもかかわらず、ハウスナーはボロノイ セルの代表点として重心を使用し続けました。ただし、ユークリッドとは大きく異なるメトリックについては、重心の代わりに、平均二乗距離の最小値を代表点として選択することが適切な場合が

こちらもご覧ください
Linde–Buzo–Gray アルゴリズム、ベクトル量子化のためのこのアルゴリズムの一般化
Farthest-first traversal、幾何学的空間で等間隔の点を生成する別の方法
平均シフト、密度関数の最大値を見つけるための関連する方法
K平均++

参考文献
^ Lloyd， Stuart P. (1982)， “”Least squares quantization in PCM””， IEEE Transactions on Information Theory ， 28 (2): 129–137， doi : 10.1109/TIT.1982.1056489. ^ デュ、チャン; フェイバー、ヴァンス。Gunzburger， Max (1999)， “”Centroidal Voronoi tessellations: applications and algorithm””， SIAM Review ， 41 (4): 637–676， Bibcode : 1999SIAMR..41..637D ， doi : 10.1137/S0036144599352836 . ^ マックス、ジョエル (1960)、「最小歪みの量子化」、情報理論に関する IRE トランザクション、6 (1): 7–12、doi : 10.1109/TIT.1960.1057548 . ^ デュ、チャン; Emelianenko， マリア; Ju， Lili （2006)、「重心ボロノイ テッセレーションを計算するためのロイド アルゴリズムの収束」、数値解析に関する SIAM ジャーナル、44 : 102–119、CiteSeerX 10.1.1.591.9903、doi : 10.1137/040617364  . ^ セイビン、MJ; グレイ、RM (1986)、「一般化ロイド アルゴリズムのグローバル収束と経験的一貫性」、情報理論に関する IEEE トランザクション、32 (2): 148–155、doi : 10.1109/TIT.1986.1057168 . ^ エメリアネンコ、マリア; ジュ、リリ; ランド、アレクサンダー （2009)、「R dにおけるロイド アルゴリズムの非縮退と弱いグローバル収束」、数値解析に関する SIAM ジャーナル、46 : 1423–1441、doi : 10.1137/070691334 . ^ シャオ、シャオ。「重心ボロノイ テッセレーションを計算するための過緩和ロイド法。」（2010）。
^ デュッセン、オリバー。ヒラー、ステファン。van Overveld、コーネリアス。Strothotte， Thomas （2000)， “”Floating points: a method for compute stipple drawing””， Computer Graphics Forum ， 19 (3​​): 41–50， doi : 10.1111/1467-8659.00396 ， S2CID 142991 ， Proceedings of Eurographics  . ^ Secord， Adrian （2002)， “”Weighted Voronoi stippling””， Proceedings of the Symposium on Non-Photorealistic Animation and Rendering (NPAR) ， ACM SIGGRAPH ， pp. 37–43， doi : 10.1145/508530.508537 ， S2CID 12153589  . ^ デュ、チャン; Gunzburger， Max （2002)， “”Grid Generation and Optimization based on centroidal Voronoi tessellation”， Applied Mathematics and Computation ， 133 (2–3): 591–607， CiteSeerX 10.1.1.324.5020 ， doi : 10.1016/S0096-3003( 01)00260-0  . ^ Hausner、Alejo （2001)、「装飾モザイクのシミュレート」、コンピューター グラフィックスとインタラクティブ技術に関する第 28 回年次会議の議事録、ACM SIGGRAPH、pp. 573–580、doi : 10.1145/383259.383327、S2CID 7188986  . ^ ディッカーソン、マシュー T .; エプスタイン、デビッド; Wortman、Kevin A. （2010)、「凸関数の和の平面ボロノイ図、平滑化された距離と膨張」、Proc. 7th International Symposium on Voronoi Diagrams in Science and Engineering (ISVD 2010) ， pp. 13–22， arXiv : 0812.0607 ， doi : 10.1109/ISVD.2010.12 ， S2CID 15971504  .

外部リンク
DemoGNG.js LBG アルゴリズムおよびその他のモデル用のグラフィカル Javascript シミュレーター (ボロノイ領域の表示を含む)”