Lloydin algoritmi

Ensimmäinen iterointi Toisen iteroinnin Kolmas iteraatio Viidestoista iteraatio Viime kuvan, kohdat ovat hyvin lähellä centroids Voronoi solujen. Painopisteen Voronoi mosaiikki on todettu.

Tietotekniikassa ja sähkötekniikka, Lloyd algoritmi, joka tunnetaan myös nimellä Voronoi iteraation tai rentoutumista, on algoritmi nimetty Stuart P. Lloyd löytää tasaisesti rivivälillä sarjaa pistettä osajoukkoja Euclidean tilat, ja väliseinät näistä subsets osaksi hyvin muotoillut ja tasakokoisia kupera soluihin. Kuten läheistä sukua K-means klusterointi algoritmi, se toistuvasti toteaa centroid kunkin asetettu osio, ja sitten uudelleen väliseinät tulo mukaan mikä näistä centroids on lähimpänä. Kuitenkin Lloyd algoritmi eroaa K-means klusterointi, että sen panos on jatkuva geometrinen alue pikemminkin kuin erillinen joukko pisteitä. Niinpä, kun uudelleen jakaminen tulo, Lloyd algoritmi käyttää Voronoi kaaviot melko yksinkertaisesti määrittämiseksi lähintä toimipistettä kullekin rajallinen joukko pisteitä K-means algoritmi ei.

Vaikka algoritmia voidaan soveltaa parhaiten suoraan euklidisessa tasossa, vastaavia algoritmeja voidaan soveltaa myös korkeamman ulottuvuuden tilat tai tilat muiden Epäeuklidinen mittareita. Lloyd algoritmia voidaan rakentaa lähellä likiarvojen painopisteen Voronoi tessellations panos, joka voidaan käyttää kvantisointia, kiertelevät, ja stippling. Muita sovelluksia Lloyd algoritmi ovat tasoittaa kolmio silmää elementtimenetelmällä.

Algoritmi kuvaus

Lloyd algoritmi alkaa avaustarjoukset joidenkin k kohdan sivustoja panos verkkotunnuksen. Mesh tasoitus sovelluksissa, nämä olisivat kärkipisteet silmän tasoittaa; muissa sovelluksissa ne voidaan sijoittaa satunnaisesti tai leikkaavat yhtenäinen kolmion silmäkoko on aiheellisen suuruinen tulo verkkotunnuksen.

Se sitten toistuvasti suorittaa seuraavat rentoutumista vaihe:

  • Voronoi kaavio k sivustoja lasketaan.
  • Jokainen solu Voronoi kaavio on integroitu ja centroid lasketaan.
  • Jokainen kohde siirretään sitten painopisteen sen Voronoi solun.

Koska Voronoi kaavio rakentaminen algoritmeja voidaan olla hyvin ei-triviaali, erityisesti tuotantopanosten ulottuvuuden suurempi kuin kaksi, vaiheet lasketaan tämän kaavion ja löytää centroids sen soluja voidaan arvioida sopivalla diskretisointitasolla, jossa kunkin solun sakon ruudukko, lähin sivusto määritetään, minkä jälkeen centroid varten sivuston solu arvioida keskimäärin keskusten ruudukon sille. Vaihtoehtoisesti, Monte Carlo menetelmiä voidaan käyttää, jossa satunnaisotos pisteitä syntyy mukaan tiettyjä kiinteitä taustalla todennäköisyysjakauma, osoitetaan lähinnä sivuston, ja keskimäärin lähentää painopisteen jokaiselle sivustolle.

Lähentyminen

Aina rentoutuminen vaihe suoritetaan, kohdat jäävät hieman tasaisempi jakautuminen: tiiviisti sijaitsevassa pisteessä siirtää kauemmas toisistaan, ja laajalti sijaitsevassa pisteessä lähemmäksi toisiamme. Yhdessä ulottuvuudessa, tämä algoritmi on osoitettu lähentyä painopisteen Voronoi kaavio, myös nimeltään painopisteen Voronoi tessellation. Vuonna korkeampiin ulottuvuuksiin, jotkut hieman heikompi lähentymistä tulokset ovat tiedossa.

Algoritmi suppenee hitaasti tai rajoitusten takia numeerinen tarkkuus, ei voi lähentyä. Siksi, reaalimaailman sovelluksia Lloyd algoritmi tyypillisesti pysähtyä kerran jakelu on "riittävän hyvä". Yksi yhteinen irtisanominen kriteeri on lopettaa, kun suurin etäisyys liikuttaa mikään sivusto iteroinnissa laskee alle asetetun kynnysarvon. Lähentymistä voidaan kiihdyttää liikaa rentouttava pistettä, mikä tapahtuu siirtämällä kunkin pisteen ω kertaa etäisyys keskustasta massa, tyypillisesti käyttämällä arvo hieman vähemmän kuin 2 ω.

Sovellukset

Lloydin menetelmä käytettiin alun perin Skalaarikvantisoinnissa mutta on selvää, että menetelmä ulottuu vektorikvantisoinnin samoin. Sellaisenaan, se on laajalti käytetty tiedon pakkaus tekniikoita tietojen teoriassa. Lloydin menetelmää käytetään tietokonegrafiikan koska tuloksena jakelu on sininen meluominaisuuksien, eli on olemassa muutamia matalien taajuuksien komponentteja, jotka voidaan tulkita esineitä. Se on erityisen hyvin poiminta näyte kannat kiertelevät. Lloyd algoritmi käytetään myös tuottamaan piste piirustukset tyyliin stippling. Tässä sovelluksessa, centroids voidaan painottaa perustuen viittaus kuvan tuottamiseksi täplittää piirroksia Matching syötekuvan.

Vuonna elementtimenetelmällä, panos verkkotunnus monimutkainen geometria jaetaan elementtien yksinkertaisempi muotoja; Esimerkiksi kaksiulotteinen domeenit usein jaettu kolmioita. On tärkeää lähentymistä finiittielementtimenetelmät että nämä tekijät ovat hyvin muotoiltu; tapauksessa kolmioiden, usein elementtejä, jotka ovat lähes tasasivuinen kolmio, ovat edullisia. Lloyd algoritmia voidaan tasoittaa mesh syntyy muulla algoritmi, liikkuvat sen pisteet ja muuttamalla yhteysjärjestyksen keskuudessa elementtejä, jotta voidaan tuottaa kolmiot, jotka ovat tiiviimmin tasasivuisen. Nämä sovellukset käyttävät yleensä pienempi toistojen Lloyd algoritmi, pysäyttää sen lähentymistä, säilyttämiseksi muita ominaisuuksia silmän kuten eroja osa koko eri puolilla verkkoa. Toisin eri tasoituksen menetelmällä, Laplacen tasoitus, Lloyd algoritmi voi muuttaa topologian silmän, mikä lisäisi lähes-tasasivuinen elementtejä sekä välttää ongelmat sotkeutumista, jotka voivat syntyä Laplacen tasoitusta. Kuitenkin, Laplace tasoitusta voidaan soveltaa yleisemmin silmää ei-kolmiomainen elementtejä.

Eri etäisyyksillä

Lloyd'sin algoritmia käytetään yleensä euklidinen avaruus. Euklidisen etäisyyden soittaa kaksi roolia algoritmi: sitä käytetään määrittelemään Voronoi solut, mutta se myös vastaa valintaa sentroidin edustajana piste kunkin solun, koska sentroidi on kohta, joka minimoi keskimääräisen potenssiin euklidisen etäisyyden jotta kohdat solussa. Vaihtoehtoiset etäisyydet, ja vaihtoehtoiset Keski pisteitä kuin painopisteen, sijasta voidaan käyttää. Esimerkiksi Hausnerin käytetty muunnelma Manhattanin metristä löytää laatoitus kuvan noin neliön laatat, joiden suunta osuu piirteitä kuvan, jota hän käytti simuloida rakentamiseen kaakeloitu mosaiikit. Tässä hakemuksessa, huolimatta vaihtelemalla metrinen, Hausnerin edelleen käyttää centroids edustajana olevia niiden Voronoi soluja. Kuitenkin mittarit, jotka poikkeavat enemmän merkittävästi Euclidean, voi olla tarkoituksenmukaista valita minimizer keskimääräisen potenssiin etäisyyden edustavasta kohdasta, sijasta painopisteen.

  0   0
Edellinen artikkeli Nephelinite
Seuraava artikkeli KAZU

Kommentit - 0

Ei kommentteja

Lisääkommentti

smile smile smile smile smile smile smile smile
smile smile smile smile smile smile smile smile
smile smile smile smile smile smile smile smile
smile smile smile smile
Merkkiä jäljellä: 3000
captcha