勞埃德演算法

在電機工程與電腦科學領域，勞氏演算法（Lloyd's algorithm），亦稱沃羅諾伊迭代法（Voronoi iteration）或鬆弛法（relaxation），是一種以其發明者斯圖爾特·勞埃德（Stuart P. Lloyd）命名的演算法，用於在歐幾里得空間的子集中尋找均勻分佈的點集，並將這些子集分割成形狀良好且大小一致的凸胞。與其密切相關的 k-平均演算法（k-means clustering）相似，它會重複尋找分割中每個集合的質心，然後根據輸入點與哪個質心最近來重新進行分割。在此設定下，求平均值的操作是對一個空間區域進行積分，而尋找最近質心的操作則會產生沃羅諾伊圖（Voronoi diagram）。

雖然此演算法最直接的應用是在歐幾里得平面上，但類似的演算法也可應用於更高維度的空間，或具有其他非歐幾里得度量的空間。勞氏演算法可用於建構輸入資料的質心沃羅諾伊鑲嵌（centroidal Voronoi tessellations）的近似圖，可用於量化、抖色及點畫法。勞氏演算法的其他應用還包括在有限元素法中平滑化三角網格。

歷史

此演算法最早由貝爾實驗室的斯圖爾特·勞埃德於 1957 年提出，作為一種脈衝編碼調變技術。勞埃德的研究成果廣為流傳，但直到 1982 年才正式發表。喬爾·麥克斯（Joel Max）於 1960 年獨立開發並發表了類似的演算法，因此該演算法有時也被稱為勞氏-麥克斯演算法（Lloyd-Max algorithm）。

演算法說明

勞氏演算法首先在輸入域中初始放置 k 個點位。在網格平滑化應用中，這些點位是待平滑網格的頂點；在其他應用中，它們可以隨機放置，或是透過將一個大小適當的均勻三角網格與輸入域相交來決定。

接著，演算法會重複執行以下鬆弛步驟：

• 計算 k 個點位的沃羅諾伊圖。
• 對沃羅諾伊圖的每個胞進行積分，並計算其質心。
• 將每個點位移動到其對應沃羅諾伊胞的質心位置。

積分與質心計算

由於沃羅諾伊圖的建構演算法可能相當複雜，尤其是在高於二維的輸入中，因此計算沃羅諾伊圖及尋找其胞的精確質心的步驟，可以被近似方法取代。

近似法

一種常見的簡化方法是採用合適的空間離散化，例如細緻的像素網格，像是圖形硬體中的紋理緩衝區。胞被具現化為像素，並標上其對應點位的 ID。透過對所有標有相同標籤的像素位置取平均，來近似計算胞的新中心。 另外，也可使用蒙地卡羅方法，即根據某個固定的基礎機率分佈生成隨機樣本點，將其分配給最近的點位，然後對各點位的樣本點進行平均，以近似計算其質心。

精確計算

儘管也可以嵌入其他空間，但此處的闡述假設在歐幾里得空間中使用 L 2 範數，並討論兩種最相關的情境，即二維和三維空間。

由於沃羅諾伊胞是凸形且總是包含其點位，因此存在能將其簡單分解為易於積分的單純形（simplices）的方法：

• 在二維空間中，將多邊形胞的邊與其點位連接，可形成一組傘狀的三角形。
• 在三維空間中，胞由數個平面多邊形包圍，這些多邊形必須先進行三角化：
  • 計算多邊形面的中心，例如其所有頂點的平均值。
  • 將多邊形面的頂點與其中心連接，可得到一個平面的傘狀三角剖分。
  • 接著，將胞外殼上的三角形與胞的點位連接，即可輕易得到一組四面體。

現在，胞的積分及其質心（質量中心）的計算，可表示為其各單純形之質心（以下稱為 \mathbf{c}_i ）的加權組合。

• 二維空間：
  • 三角形的質心可以輕易計算得出，例如使用笛卡兒座標。
  • 權重為單純形面積與胞總面積的比值。
• 三維空間：
  • 四面體的質心可透過三個平分面的交點求得，並可表示為矩陣-向量乘積。
  • 權重為單純形體積與胞總體積的比值。

對於一個由 n 個三角形單純形組成的二維胞，其總面積為 A_C = \sum_{i=0}^n a_i （其中 a_i 為三角形單純形的面積），新的胞質心計算如下：

C = \frac{1}{A_C}\sum_{i=0}^{n}\mathbf{c}_i a_i

同理，對於一個體積為 V_C = \sum_{i=0}^n v_i 的三維胞（其中 v_i 為四面體單純形的體積），其質心計算如下：

C = \frac{1}{V_C}\sum_{i=0}^{n}\mathbf{c}_i v_i

收斂性

每執行一次鬆弛步驟，點的分佈都會變得稍微更均勻：間距近的點會相互遠離，而間距遠的點會相互靠近。在一維空間中，此演算法已被證明會收斂至質心沃羅諾伊圖，也稱為質心沃羅諾伊鑲嵌。在更高維度中，已知存在一些稍弱的收斂性結果。

該演算法收斂緩慢，或因數值精度的限制而可能無法收斂。因此，勞氏演算法在實際應用中，通常在分佈達到「足夠好」的狀態時便會停止。一個常見的終止條件是，當單次迭代中任何點位的最大移動距離低於預設閾值時停止。可以透過對點進行「過鬆弛」（over-relaxing）來加速收斂，即將每個點朝質心方向移動 ω 倍的距離，ω 的值通常取略小於 2。

應用

勞氏方法最初用於純量量化，但顯然該方法也可擴展至向量量化。因此，它在資訊理論的資料壓縮技術中被廣泛使用。勞氏方法被用於電腦圖形學，因為其產生的分佈具有藍噪音特性（另見噪音顏色），意味著幾乎沒有可被解讀為瑕疵的低頻成分。它特別適合為抖色技術選取取樣位置。勞氏演算法也用於生成點畫風格的點陣圖。在此應用中，可根據參考影像對質心進行加權，以產生與輸入影像相匹配的點畫插圖。

在有限元素法中，一個具有複雜幾何形狀的輸入域會被分割成形狀較簡單的元素；例如，二維域（歐幾里得平面的子集或三維空間中的曲面）常被分割成三角形。為了讓有限元素法收斂，這些元素的形狀必須良好；以三角形為例，通常偏好接近正三角形的元素。勞氏演算法可用於平滑由其他演算法產生的網格，透過移動頂點並改變元素間的連接模式，以產生更接近正三角形的三角形。這些應用通常只執行較少次數的勞氏演算法迭代，在收斂前就停止，以保留網格的其他特徵，例如網格不同部分元素大小的差異。與另一種平滑化方法——拉普拉斯平滑（將網格頂點移至其鄰近頂點的平均位置）相比，勞氏演算法可以改變網格的拓撲結構，從而產生更接近正三角形的元素，並避免拉普拉斯平滑可能引起的網格糾纏問題。然而，拉普拉斯平滑可以更廣泛地應用於包含非三角形元素的網格。

不同距離度量

勞氏演算法通常用於歐幾里得空間。歐幾里得距離在演算法中扮演兩個角色：它被用來定義沃羅諾伊胞，同時也對應了選擇質心作為每個胞代表點的作法，因為質心是能使其胞內各點到該點的平均歐幾里得距離平方和最小化的點。也可以使用替代的距離度量和質心以外的中心點。例如，有研究曾使用曼哈頓度量的一種變體（具局部變化的方向性）來尋找一種能以近似方形的圖塊鋪滿影像的方案，其中圖塊的方向與影像特徵對齊，並以此模擬馬賽克磁磚的建構過程。在此應用中，儘管改變了度量方式，豪斯納（Hausner）仍繼續使用質心作為其沃羅諾伊胞的代表點。然而，對於與歐幾里得度量差異較大的度量，選擇平均距離平方和的最小值點作為代表點，可能會比選擇質心更為合適。

參見

• 林德-布索-格雷演算法（Linde–Buzo–Gray algorithm），此演算法在向量量化領域的推廣
• 最遠點優先遍歷（Farthest-first traversal），一種在幾何空間中生成均勻分佈點的不同方法
• 平均移位（Mean shift），一種尋找密度函數最大值的相關方法
• K-means++

外部連結

• DemoGNG.js：LBG 演算法及其他模型的圖形化 Javascript 模擬器，包含沃羅諾伊區域的顯示

Category:幾何演算法 Category:最佳化演算法與方法