ロイドのアルゴリズム

電気工学とコンピュータサイエンスにおいて、ロイドのアルゴリズムは、ボロノイ反復法または緩和法とも呼ばれ、スチュアート・P・ロイドにちなんで名付けられた、ユークリッド空間のサブセット内で等間隔の点の集合を見つけ、これらのサブセットを形が整った均一なサイズの凸セルに分割するアルゴリズムです。^[1] 密接に関連するk平均法クラスタリングアルゴリズムと同様に、パーティション内の各セットの重心を繰り返し見つけ、どの重心が最も近いかに従って入力を再パーティションします。この設定では、平均操作は空間領域上の積分であり、最も近い重心操作はボロノイ図になります。

このアルゴリズムはユークリッド平面に最も直接的に適用できますが、同様のアルゴリズムを高次元空間や他の非ユークリッド距離を持つ空間に適用することもできます。ロイドのアルゴリズムは、入力の重心ボロノイ分割の近似値を構築するために使用でき、^[2]これは量子化、ディザリング、点描に使用できます。ロイドのアルゴリズムの他の用途には、有限要素法における三角形メッシュの平滑化があります。

このアルゴリズムは、1957年にベル研究所のスチュアート・P・ロイドがパルス符号変調の技術として初めて提案しました。ロイドの研究は広く流布しましたが、1982年まで公開されませんでした。^[1]同様のアルゴリズムがジョエル・マックスによって独立して開発され、1960年に公開されました。^[3]そのため、このアルゴリズムはロイド・マックスアルゴリズムと呼ばれることもあります。

ロイドのアルゴリズムは、入力ドメインにいくつかのk個のポイント サイトを最初に配置することから始まります。メッシュ スムージング アプリケーションでは、これらはスムージングするメッシュの頂点になります。他のアプリケーションでは、ランダムに配置されるか、適切なサイズの均一な三角形メッシュを入力ドメインと交差させることによって配置される場合があります。

次に、次の緩和ステップを繰り返し実行します。

• k 個のサイトのボロノイ図が計算されます。
• ボロノイ図の各セルを積分し、重心を計算します。
• 次に、各サイトをそのボロノイ セルの重心に移動させます。

ボロノイ図の構築アルゴリズムは、特に 2 次元を超える入力の場合、非常に複雑になる可能性があるため、この図を計算してセルの正確な重心を見つける手順は、近似値に置き換えられる場合があります。

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

他の空間への埋め込みも可能ですが、この説明ではL ²ノルムを使用するユークリッド空間を想定し、最も関連性の高い 2 つのシナリオ、つまり 2 次元と 3 次元について説明します。

ボロノイセルは凸形状で常にそのサイトを囲むため、簡単に積分可能な単体への単純な分解が存在します。

• 2 次元では、多角形セルのエッジがそのサイトに接続され、傘の形をした三角形のセットが作成されます。
• 3 次元では、セルはいくつかの平面多角形に囲まれており、最初に三角形に分割する必要があります。
  • ポリゴン面の中心、つまりすべての頂点の平均を計算します。
  • 多角形の面の頂点をその中心に接続すると、平面の傘型の三角形になります。
  • 当然のことながら、セルの外殻の三角形をセルのサイトに接続することによって、四面体のセットが得られます。

セルの積分とその重心（質量の中心）の計算は、その単体の重心の重み付き組み合わせとして与えられる（以下では と呼ぶ）。 ${\textstyle \mathbf {c} _{i}}$

• 2次元:
  • 三角形の場合、重心は、例えば直交座標を使用して簡単に計算できます。
  • 重み付けは単体とセルの面積比として計算されます。
• 3次元:
  • 四面体の重心は、 3つの二等分面の交点として求められ、行列とベクトルの積として表すことができます。
  • 重み付けは単体とセルの体積比として計算されます。

n 個の三角形単体と累積面積(三角形単体の面積)を持つ 2D セルの場合、新しいセルの重心は次のように計算されます。 ${\textstyle A_{C}=\sum _{i=0}^{n}a_{i}}$${\textstyle a_{i}}$

${\displaystyle C={\frac {1}{A_{C}}}\sum _{i=0}^{n}\mathbf {c} _{i}a_{i}}$

同様に、体積が（四面体単体の体積）の 3D セルの場合、重心は次のように計算されます。 ${\textstyle V_{C}=\sum _{i=0}^{n}v_{i}}$${\textstyle v_{i}}$

${\displaystyle C={\frac {1}{V_{C}}}\sum _{i=0}^{n}\mathbf {c} _{i}v_{i}}$

緩和ステップが実行されるたびに、点の分布はわずかに均等になります。つまり、間隔が近い点は離れ、間隔が広い点は互いに近づきます。1次元では、このアルゴリズムは重心ボロノイ図（重心ボロノイ分割とも呼ばれます）に収束することが示されています。^[4]高次元では、収束結果がわずかに弱くなることが知られています。^{[5] [6]}

このアルゴリズムはゆっくりと収束するか、数値精度の制限により収束しないこともあります。そのため、ロイドのアルゴリズムの実際のアプリケーションでは、分布が「十分に良好」になると停止するのが一般的です。一般的な終了基準の 1 つは、反復中に任意のサイトが移動した最大距離が事前に設定されたしきい値を下回ったときに停止することです。収束は、ポイントを過剰に緩和することで加速できます。これは、各ポイントを質量中心までの距離のω倍移動することで行われ、通常はωに 2 よりわずかに小さい値を使用します。^[7]

ロイドの方法はもともとスカラー量子化に使用されていましたが、この方法がベクトル量子化にも拡張できることは明らかです。そのため、情報理論のデータ圧縮技術で広く使用されています。ロイドの方法は、結果として得られる分布がブルーノイズ特性（ノイズの色も参照）を持つため、コンピュータグラフィックスで使用されます。つまり、アーティファクトとして解釈される可能性のある低周波成分がほとんどありません。特に、ディザリングのサンプル位置を選択するのに適しています。ロイドのアルゴリズムは、点描スタイルのドット描画を生成するためにも使用されます。^[8]このアプリケーションでは、参照画像に基づいて重心に重みを付け、入力画像に一致する点描イラストを作成できます。^[9]

有限要素法では、複雑な形状の入力領域がより単純な形状の要素に分割されます。たとえば、2 次元領域 (ユークリッド平面のサブセットまたは 3 次元の表面) は、多くの場合、三角形に分割されます。有限要素法の収束には、これらの要素が適切に形作られていることが重要です。三角形の場合、ほぼ正三角形の要素が好まれることがよくあります。ロイドのアルゴリズムを使用すると、他のアルゴリズムで生成されたメッシュを滑らかにすることができ、頂点を移動し、要素間の接続パターンを変更して、より正三角形に近い三角形を作成できます。^[10]これらのアプリケーションでは通常、メッシュのさまざまな部分での要素サイズの違いなど、メッシュの他の機能を保持するために、ロイドのアルゴリズムの反復回数を減らして収束を停止します。別のスムージング方法であるラプラシアン スムージング(メッシュの頂点を隣接する頂点の位置の平均に移動)とは対照的に、ロイドのアルゴリズムはメッシュのトポロジを変更して、より正三角形に近い要素を実現し、ラプラシアン スムージングで発生する可能性のある絡み合いの問題を回避できます。ただし、ラプラシアン スムージングは​​、三角形以外の要素を持つメッシュに一般的に適用できます。

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

• Linde -Buzo-Grayアルゴリズムは、このアルゴリズムをベクトル量子化に一般化したアルゴリズムである。
• 最も遠いものから順に探索する、幾何学的空間に等間隔の点を生成する別の方法
• 平均シフト、密度関数の最大値を見つけるための関連方法
• K平均法++

• DemoGNG.js LBG アルゴリズムおよびその他のモデル用のグラフィカル Javascript シミュレーター。ボロノイ領域の表示も含まれています。