Lloydsův algoritmus - Lloyds algorithm - Wikipedia

Příklad Lloydova algoritmu. Je zobrazen Voronoiův diagram aktuálních bodů při každé iteraci. Znaménka plus označují centroidy buněk Voronoi.

Iterace 1

Iterace 2

Iterace 3

Iterace 15

Na posledním obrázku jsou body velmi blízko centroidů Voronoiových buněk. Byla nalezena mozaiková Voronoiova mozaikování.

v počítačová věda a elektrotechnika, Lloydův algoritmus, také známý jako Voronoiova iterace nebo relaxace, je algoritmus pojmenovaný podle Stuarta P. Lloyda pro hledání rovnoměrně rozmístěných sad bodů v podmnožinách Euklidovské prostory a oddíly těchto podmnožin do dobře tvarovaných a rovnoměrně velkých konvexních buněk.^[1] Stejně jako blízcí příbuzní k- znamená shlukování algoritmus opakovaně najde těžiště každé sady v oddílu a poté znovu rozdělí oddíl podle toho, který z těchto centroidů je nejblíže. V tomto nastavení je střední operace integrálem v oblasti vesmíru a nejbližší těžiště operace má za následek Voronoiovy diagramy.

Ačkoli lze algoritmus použít nejpříměji na Euklidovské letadlo, podobné algoritmy lze použít i na prostory vyšších dimenzí nebo na prostory s jinými neeuklidovský metriky. Lloydův algoritmus lze použít ke konstrukci blízkých aproximací těžiště Voronoi mozaikování vstupu,^[2] pro které lze použít kvantování, dithering, a tečkování. Mezi další aplikace Lloydova algoritmu patří vyhlazování trojúhelníkové sítě v Metoda konečných prvků.

Popis algoritmu

Lloydův algoritmus začíná počátečním umístěním nějakého čísla k bodových webů ve vstupní doméně. V aplikacích pro vyhlazení sítě by to byly vrcholy sítě, která má být vyhlazena; v jiných aplikacích mohou být umístěny náhodně nebo protínáním jednotné trojúhelníkové sítě vhodné velikosti se vstupní doménou.

Poté opakovaně provede následující relaxační krok:

• The Voronoiho diagram z k stránky se počítají.
• Každá buňka Voronoiho diagramu je integrována a je vypočítán těžiště.
• Každé místo je poté přesunuto do těžiště své Voronoiho buňky.

Integrace a výpočet těžiště

Protože algoritmy pro konstrukci Voronoiho diagramu mohou být vysoce netriviální, zejména pro vstupy dimenze vyšší než dvě, kroky výpočtu tohoto diagramu a nalezení přesných centroidů jeho buněk mohou být nahrazeny aproximací.

Přiblížení

Běžným zjednodušením je použít vhodnou diskretizaci prostoru jako jemnou mřížku pixelů, např. textury nárazník v grafickém hardwaru. Buňky se zhmotňují jako pixely označené příslušným ID webu. Nový střed buňky je aproximován průměrováním pozic všech pixelů přiřazených se stejným štítkem. Metody Monte Carlo může být použito, ve kterém jsou generovány náhodné vzorkovací body podle nějakého pevného podkladového rozdělení pravděpodobnosti, přiřazené k nejbližšímu místu a zprůměrovány k přiblížení těžiště pro každé místo.

Přesný výpočet

Ačkoli je také možné zabudování do jiných prostor, toto zpracování předpokládá Euklidovský prostor za použití L² norma a pojednává o dvou nejrelevantnějších scénářích, kterými jsou dva, respektive tři rozměry.

Vzhledem k tomu, že Voronoiova buňka má konvexní tvar a vždy obklopuje své místo, existují triviální rozklady na snadno integrovatelné jednoduchosti:

• Ve dvou rozměrech jsou okraje polygonální buňky spojeny s jejím místem a vytvářejí deštníkovou sadu trojúhelníků.
• Ve třech rozměrech je buňka uzavřena několika rovinnými polygony, které je třeba nejprve triangulovat:
  • Vypočítejte střed polygonové plochy, např. průměr všech jeho vrcholů.
  • Propojení vrcholů polygonální plochy s jejím středem poskytuje rovinnou trojúhelníkovou triangulaci.
  • Triviálně, soubor čtyřstěn se získá spojením trojúhelníků trupu buňky s místem buňky.

Integrace buňky a její výpočet těžiště (těžiště) je nyní dána jako vážená kombinace těžišť jeho simplexů (v následujícím textu nazvaná ${ textstyle mathbf {c} _ {i}}$).

• Dva rozměry:
  • Pro trojúhelník lze těžiště snadno vypočítat, např. použitím Kartézské souřadnice.
  • Vážení počítá jako simplex-to-cell plocha poměry.
• Tři rozměry:
  • The těžiště čtyřstěnu se nachází jako průsečík tří půlících rovin a lze jej vyjádřit jako produkt matice-vektor.
  • Vážení počítá jako simplex-to-cell objem poměry.

Pro 2D buňku s n trojúhelníkové jednoduchosti a akumulovaná plocha ${ textstyle A_ {C} = součet _ {i = 0} ^ {n} a_ {i}}$ (kde ${ textstyle a_ {i}}$ je oblast trojúhelníku simplex), nový centroid buňky počítá jako:

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

Analogicky, pro 3D buňku o objemu ${ textstyle V_ {C} = součet _ {i = 0} ^ {n} v_ {i}}$ (kde ${ textstyle v_ {i}}$ je objem čtyřstěnu simplex), těžiště počítá jako:

${ displaystyle C = { frac {1} {V_ {C}}} součet _ {i = 0} ^ {n} mathbf {c} _ {i} v_ {i}}$

Konvergence

Pokaždé, když je proveden relaxační krok, jsou body ponechány v mírně rovnoměrnějším rozložení: těsně rozmístěné body se pohybují dále od sebe a široce rozmístěné body se přibližují k sobě. V jedné dimenzi bylo prokázáno, že tento algoritmus konverguje k centroidnímu Voronoiovi diagramu, také pojmenovanému a těžiště Voronoi mozaikování.^[3] Ve vyšších dimenzích jsou známy některé mírně slabší výsledky konvergence.^[4][5]

Algoritmus konverguje pomalu nebo kvůli omezením v numerické přesnosti nemusí konvergovat. Skutečné aplikace Lloydova algoritmu v reálném světě se proto obvykle zastaví, jakmile je distribuce „dostatečně dobrá“. Jedním běžným kritériem ukončení je zastavení, když maximální vzdálenost přesunutá jakýmkoli webem v iteraci klesne pod přednastavenou prahovou hodnotu. Konvergenci lze urychlit přílišným uvolněním bodů, což se provádí pohybem každého bodu ω krát vzdálenost od středu hmoty, obvykle s použitím hodnoty o něco menší než 2 pro ω.^[6]

Aplikace

Lloydova metoda byla původně použita pro skalární kvantizaci, ale je zřejmé, že metoda se vztahuje i na vektorovou kvantizaci. Jako takový je široce používán v komprese dat techniky v teorie informace. Lloydova metoda se používá v počítačové grafice, protože výsledná distribuce ano modrý šum charakteristiky (viz také Barvy šumu ), což znamená, že existuje několik nízkofrekvenčních komponent, které lze interpretovat jako artefakty. Je zvláště vhodný pro výběr pozic vzorků pro dithering. Lloydův algoritmus se také používá ke generování bodových výkresů ve stylu tečkování.^[7] V této aplikaci lze centroidy vážit na základě referenčního obrázku, aby se vytvořily tečkované ilustrace odpovídající vstupnímu obrazu.^[8]

V Metoda konečných prvků, vstupní doména se složitou geometrií je rozdělena na prvky s jednoduššími tvary; například dvourozměrné domény (buď podmnožiny euklidovské roviny, nebo povrchy ve třech rozměrech) jsou často rozděleny do trojúhelníků. Pro konvergenci metod konečných prvků je důležité, aby tyto prvky byly dobře tvarované; v případě trojúhelníků jsou často preferovány prvky, které jsou téměř rovnostrannými trojúhelníky. Lloydův algoritmus lze použít k vyhlazení mřížky generované nějakým jiným algoritmem, pohybem jeho vrcholů a změnou vzoru připojení mezi jeho prvky, aby vznikly trojúhelníky, které jsou těsněji rovnostranné.^[9] Tyto aplikace obvykle používají menší počet iterací Lloydova algoritmu a zastavují jej ke konvergenci, aby se zachovaly další vlastnosti sítě, jako jsou rozdíly ve velikosti prvků v různých částech sítě. Na rozdíl od jiné metody vyhlazování Laplaciánské vyhlazování (ve kterém jsou vrcholy sítě přesunuty na průměr pozic svých sousedů) může Lloydův algoritmus změnit topologii sítě, což povede k téměř rovnostranným prvkům a vyhne se problémům se spletením, které mohou nastat při laplaciánském vyhlazování. Laplaciánské vyhlazování však lze obecněji aplikovat na sítě s netrojúhelníkovými prvky.

Různé vzdálenosti

Lloydův algoritmus se obvykle používá v a Euklidovský prostor. Euklidovská vzdálenost hraje v algoritmu dvě role: používá se k definování buněk Voronoi, ale také odpovídá výběru těžiště jako reprezentativního bodu každé buňky, protože těžiště je bod, který minimalizuje průměrnou čtvercovou euklidovskou vzdálenost k bodům v jeho buňce. Místo toho lze použít alternativní vzdálenosti a alternativní středové body než těžiště. Například, Hausner (2001) použil variantu Manhattanská metrika (s místně se měnícími orientacemi) najít obklad obrazu přibližně čtvercovými dlaždicemi, jejichž orientace je v souladu s vlastnostmi obrazu, které použil k simulaci konstrukce obkladů mozaiky.^[10] V této aplikaci navzdory měnící se metrice Hausner nadále používal centroidy jako reprezentativní body svých buněk Voronoi. U metrik, které se výrazněji liší od euklidovských, může být vhodné zvolit jako reprezentativní bod namísto těžiště minimalizátor průměrné čtvercové vzdálenosti.^[11]

Viz také

• The Algoritmus Linde – Buzo – Gray, zobecnění tohoto algoritmu pro vektorovou kvantizaci
• Nejdůležitější průchod, odlišná metoda generování rovnoměrně rozmístěných bodů v geometrických prostorech
• Střední posun, související metoda pro zjištění maxima funkce hustoty
• K-prostředky ++

Reference

externí odkazy

• DemoGNG.js Grafický simulátor Javascript pro algoritmus LBG a další modely zahrnuje zobrazení oblastí Voronoi