Tulvan täyttö - Flood fill

Rekursiivinen tulvitäyttö 4 suuntaan

Tulvan täyttö , jota kutsutaan myös siementäytteeksi , on algoritmi, joka määrittää ja muuttaa tiettyyn solmuun yhdistettyä aluetta moniulotteisessa taulukossa, jolla on jokin vastaava attribuutti. Sitä käytetään "ämpäri" Täyttötyökalu of maali ohjelmia täyttää kytketty, samoin värinen alueilla eri väriä, ja peleissä kuten Go ja Miinaharava määrittämiseksi, mitkä osat poistetaan. Muunnos nimeltään rajan fill käyttää samoja algoritmeja vaan määritellään alue liitetään tiettyyn solmuun, jolla ei ole erityistä määrite.

Huomaa, että tulvitäyttö ei sovellu täytettyjen monikulmioiden piirtämiseen, koska se jättää väliin pikselit terävämmissä kulmissa. Katso sen sijaan parilliset ja parittomat säännöt .

Algoritmin parametrit

Rekursiivinen tulva täyttää 8 suuntaa

Perinteinen tulvan täyttöalgoritmi sisältää kolme parametria: aloitussolmu, kohdeväri ja korvaava väri. Algoritmi etsii kaikki taulukon solmut, jotka on yhdistetty aloitussolmuun kohdevärin polulla, ja muuttaa ne korvaavaksi väreksi. Rajatäyttöä varten kohdevärin tilalle toimitetaan reunuksen väri.

Jotta algoritmia voidaan yleistää yleisellä tavalla, seuraavissa kuvauksissa on sen sijaan käytettävissä kaksi rutiinia. Yksi nimeltään Insidejoka palauttaa totta täyttämättömille pisteille, jotka värinsä mukaan olisivat täytetyn alueen sisällä, ja toinen kutsutaan Setjoka täyttää pikselin/solmun. Mikään sitä Setkutsunut solmu ei saa enää olla Inside.

Riippuen siitä, katsommeko solmujen koskettavan toisiinsa liitettyjä kulmia vai ei, meillä on kaksi muunnosta: kahdeksan- ja nelisuuntainen.

Pinoon perustuva rekursiivinen toteutus (nelisuuntainen)

Varhaisin tunnettu, epäsuorasti pinopohjainen, rekursiivinen , nelisuuntainen tulvantäyttö toteutetaan seuraavasti: 

Flood-fill (node):
 1. If node is not Inside return.
 2. Set the node
 3. Perform Flood-fill one step to the south of node.
 4. Perform Flood-fill one step to the north of node
 5. Perform Flood-fill one step to the west of node
 6. Perform Flood-fill one step to the east of node
 7. Return.

Vaikka ylläoleva algoritmi on helppo ymmärtää, sen käyttäminen on epäkäytännöllistä kielillä ja ympäristöissä, joissa pinotilaa on vakavasti rajoitettu (esim. Mikro -ohjaimet ).

Rekursion siirtäminen tietorakenteeseen

Nelisuuntainen tulvan täyttö käyttäen jonoa tallennukseen
Nelisuuntainen tulvan täyttö käyttäen pinoa säilytykseen

Rekursion siirtäminen tietorakenteeseen (joko pinoon tai jonoon ) estää pinon ylivuodon. Se on samanlainen kuin yksinkertainen rekursiivinen ratkaisu, paitsi että rekursiivisten puheluiden soittamisen sijaan se työntää solmut pinoon tai jonoon kulutusta varten, ja tietorakenteen valinta vaikuttaa leviämismalliin: 

Flood-fill (node):
  1. Set Q to the empty queue or stack.
  2. Add node to the end of Q.
  3. While Q is not empty:
  4.   Set n equal to the first element of Q.
  5.   Remove first element from Q.
  6.   If n is Inside:
         Set the n
         Add the node to the west of n to the end of Q.
         Add the node to the east of n to the end of Q.
         Add the node to the north of n to the end of Q.
         Add the node to the south of n to the end of Q.
  7. Continue looping until Q is exhausted.
  8. Return.

Lisää mahdollisia optimointeja

  • Tarkista ja aseta kunkin solmun pikseliväri ennen sen lisäämistä pinoon/jonoon, mikä pienentää pinon/jonon kokoa.
  • Käytä silmukkaa itä/länsi -suuntiin ja jonota pikselit ylä-/alapuolelle. (Tehdään se samanlaiseksi span -täyttöalgoritmien kanssa, alla.)
  • Lomaile kaksi tai useampia kopioita koodista ylimääräisillä pinoilla/jonoilla, jotta OoO -prosessorit saavat enemmän mahdollisuuksia rinnastaa
  • Käytä useita säikeitä (mieluiten hieman eri vierailutilauksilla, jotta ne eivät pysy samalla alueella)

Edut

  • Erittäin yksinkertainen algoritmi - helppo tehdä virheetön.

Haitat

  • Kuluttaa paljon muistia, etenkin pinon käytön aikana.
  • Testaa useimmat täytetyt pikselit yhteensä neljä kertaa.
  • Ei sovellu kuvion täyttämiseen, koska se vaatii pikselitestitulosten muuttamista.
  • Pääsykuvio ei ole välimuistiystävällinen jonotusvaihtoehdolle.
  • Ei voi helposti optimoida usean pikselin sanoja tai bittitasoja varten.

Span täyttö

Skannauslinjan täyttö

On mahdollista optimoida asioita edelleen työskentelemällä ensisijaisesti jännevälien kanssa. Ensimmäinen julkaistu täydellinen esimerkki toimii seuraavan perusperiaatteen mukaisesti. Aloita siemenpisteestä täyttämällä vasemmalle ja oikealle ja seuraamalla reunoja. Sitten skannaat saman osan ylä- ja alapuolella olevasta viivasta etsimällä uusia siemenpisteitä jatkaaksesi. Tämä algoritmi on suosituin sekä lainauksissa että toteutuksissa, vaikka useimmat täytetyt pikselit testataan yhteensä kolme kertaa. Pseudokoodimuodossa: 

fn fill(x, y):
  if not Inside(x, y) then return
  let s = new empty stack or queue
  add (x, y) to s
  while s is not empty:
    Remove an (x, y) from s
    let lx = x
    while Inside(lx - 1, y):
      Set(lx - 1, y)
      lx = lx - 1
    while Inside(x, y):
      Set(x, y)
      x = x + 1
    scan(lx, x - 1, y + 1, s)
    scan(lx, x - 1, y - 1, s)

fn scan(lx, rx, y, s):
  let added = false
  for x in lx .. rx:
    if not Inside(x, y):
      added = false
    else if not added:
      Add (x, y) to s
      added = true

Ajan myötä seuraavat optimoinnit toteutettiin:

  • Kun uusi skannaus olisi kokonaan isovanhemman alueella, se löytäisi varmasti vain täytetyt pikselit, joten se ei tarvitse jonottaa.
  • Lisäksi kun uusi skannaus on isovanhemman alueen päällekkäin, vain ylitykset (U-käännökset ja W-käännökset) on skannattava.
  • On mahdollista täyttää siemeniä etsiessään

Lopullinen, yhdistetty skannaus ja täyttöalue-täyteaine julkaistiin sitten vuonna 1990 ja etenee seuraavasti (vaikka tässä oleva versio korjaa joitain alkuperäisen virheitä): 

fn fill(x, y):
  if not Inside(x, y) then return
  let s = new empty queue or stack
  Add (x, x, y, 1) to s
  Add (x, x, y - 1, -1) to s
  while s is not empty:
    Remove an (x1, x2, y, dy) from s
    let x = x1
    if Inside(x, y):
      while Inside(x - 1, y):
        Set(x - 1, y)
        x = x - 1
    if x < x1:
      Add (x, x1-1, y-dy, -dy) to s
    while x1 < x2:
      while Inside(x1, y):
        Set(x1, y)
        x1 = x1 + 1
      Add (x, x1 - 1, y+dy, dy) to s
      if x1 - 1 > x2:
        Add (x2 + 1, x1 - 1, y-dy, -dy)
      while x1 < x2 and not Inside(x1, y):
        x1 = x1 + 1
      x = x1

Edut

  • 2x-8x nopeampi kuin pikselirekursiivinen algoritmi.
  • Pääsykuvio on välimuisti- ja bittitasoystävällinen.
  • Voi piirtää vaakasuoran viivan yksittäisten pikseleiden asettamisen sijaan.

Haitat

  • Vierailee edelleen pikseleissä, jotka se on jo täyttänyt. (Suositulla algoritmilla kolme skannausta useimmista pikseleistä. Viimeisessä tapauksessa vain lisätarkistuksia pikseleistä, joissa on reikiä täytetyllä alueella.)
  • Ei sovellu kuvion täyttämiseen, koska se vaatii pikselitestitulosten muuttamista.

Kuvion täyttötuen lisääminen

Kaksi yleistä tapaa saada mittausalue- ja pikselipohjaiset algoritmit tukemaan kuvion täyttämistä ovat joko käyttää ainutlaatuista väriä tavallisena täyttönä ja korvata se sitten kuviolla tai seurata (2d: n boolean-taulukossa tai alueina), mistä pikselistä on käytetty osoittamaan, että pikselit eivät ole enää täytettävissä. Inside on palautettava epätosi tällaisille vierailluille kuvapisteille.

Kaavioteoreettinen täyttö

Jotkut teoreetikot käyttivät ongelmaan nimenomaista kuvaajateoriaa, pitäen pikselien alueita tai niiden aggregaatteja solmuina ja tutkimalla niiden yhteyksiä. Ensimmäinen julkaistu kuvaajateorialgoritmi toimi samalla tavalla kuin yllä oleva täyttöalue, mutta sillä oli tapa havaita, milloin se kaksinkertaistaa jännevälien täytön. Valitettavasti siinä oli virheitä, joiden vuoksi se ei täyttänyt joitain täyttöjä. Korjattu algoritmi julkaistiin myöhemmin samalla periaatteella graafiteoriassa; se kuitenkin muuttaa kuvaa sen edetessä estämään väliaikaisesti mahdolliset silmukat, mikä vaikeuttaa ohjelmallista käyttöliittymää. Myöhemmin julkaistu algoritmi riippui siitä, että raja on erilainen kuin kaikki muu kuvassa, joten se ei sovellu useimpiin käyttötarkoituksiin; se vaatii myös ylimääräisen bitin pikseliä kohti kirjanpidossa.

Edut

  • Sopii kuvion täyttöön suoraan, koska se ei koskaan testaa uudelleen täytettyjä pikseleitä.
  • Kaksinkertainen alkuperäisen mittausalgoritmin nopeus yksinkertaisten täyttöjen saamiseksi.
  • Pääsykuvio on välimuisti- ja bittitasoystävällinen.

Haitat

  • Väliä on säännöllisesti verrattava jokaiseen jonon "etuosaan", mikä hidastaa merkittävästi monimutkaisia ​​täyttöjä.
  • Siirtyminen edestakaisin kuvaajan teoreettisen ja pikselialueen välillä vaikeuttaa ymmärtämistä.
  • Koodi on melko monimutkainen, mikä lisää virheiden mahdollisuutta.

Kävelypohjainen täyttö (kiinteän muistin menetelmä)

On olemassa menetelmä, joka käytännössä ei käytä muistia neljään kytkettyyn alueeseen teeskennellen olevansa maalari, joka yrittää maalata alueen maalaamatta itseään nurkkaan. Tämä on myös menetelmä sokkelojen ratkaisemiseksi. Neljä pikseliä, jotka muodostavat ensisijaisen rajan, tutkitaan, jotta voidaan selvittää, mitä on tehtävä. Taidemaalari voi joutua johonkin useista olosuhteista:

  1. Kaikki neljä rajapikseliä täytetään.
  2. Kolme rajapikseliä on täytetty.
  3. Kaksi rajapikseliä on täytetty.
  4. Yksi rajapikseli on täynnä.
  5. Nollarajapikselit täytetään.

Jos polkua tai rajaa on noudatettava, käytetään oikean käden sääntöä. Taidemaalari seuraa aluetta asettamalla oikean kätensä seinälle (alueen raja) ja etenemällä alueen reunan ympäri poistamatta kättään.

Tapauksessa #1 maalari maalaa (täyttää) pikselin, jonka päällä maalari seisoo, ja pysäyttää algoritmin.

Tapauksessa #2 on olemassa alueelta johtava polku. Maalaa pikseli, jolla maalari seisoo, ja siirry avoimen polun suuntaan.

Tapauksessa #3 kaksi rajapikseliä määrittävät polun, joka, jos maalaamme nykyisen pikselin, voi estää meitä pääsemästä takaisin polun toiselle puolelle. Tarvitsemme "merkin" määritelläksemme, missä olemme ja mihin suuntaan olemme menossa nähdäksemme, palaammeko koskaan täsmälleen samaan pikseliin. Jos olemme jo luoneet tällaisen "merkin", säilytämme edellisen merkin ja siirrymme seuraavaan pikseliin oikean käden säännön mukaisesti.

Merkkiä käytetään ensimmäiseen 2 pikselin rajaan, joka havaitaan muistamaan, mistä kulku alkoi ja mihin suuntaan maalari liikkui. Jos merkki kohdataan uudelleen ja maalari kulkee samaan suuntaan, maalari tietää, että on turvallista maalata neliö merkillä ja jatkaa samaan suuntaan. Tämä johtuu siitä, että (jonkin tuntemattoman polun kautta) merkin toisella puolella olevat pikselit voidaan saavuttaa ja maalata tulevaisuudessa. Merkki poistetaan tulevaa käyttöä varten.

Jos maalari kohtaa merkin, mutta on menossa toiseen suuntaan, on tapahtunut jonkinlainen silmukka, joka sai maalarin palaamaan merkkiin. Tämä silmukka on poistettava. Merkki nostetaan, ja maalari etenee sitten merkin aiemmin osoittamaan suuntaan käyttämällä vasemmanpuoleista sääntöä rajalle (samanlainen kuin oikean käden sääntö, mutta käyttämällä maalarin vasenta kättä). Tämä jatkuu, kunnes risteys löytyy (vähintään kolme avointa rajapikseliä). Edelleen käyttämällä vasemmanpuoleista sääntöä maalari etsii nyt yksinkertaista kohtaa (kaksi rajapikseliä). Kun tämä kahden pikselin rajapolku on löydetty, pikseli maalataan. Tämä katkaisee silmukan ja sallii algoritmin jatkaa.

Tapauksessa #4 meidän on tarkistettava vastakkaiset 8-kulmaiset kulmat nähdäksemme, ovatko ne täytettyjä vai eivät. Jos jompikumpi tai molemmat täytetään, tämä luo monen polun risteyksen, eikä sitä voida täyttää. Jos molemmat ovat tyhjiä, nykyinen pikseli voidaan maalata ja maalari voi liikkua oikean käden säännön mukaisesti.

Algoritmi vaihtaa aikaa muistiin. Yksinkertaisille muodoille se on erittäin tehokas. Jos muoto on kuitenkin monimutkainen ja siinä on monia ominaisuuksia, algoritmi käyttää paljon aikaa alueen reunojen jäljittämiseen yrittäen varmistaa, että kaikki voidaan maalata.

Tämä algoritmi oli ensimmäisen kerran kaupallisesti saatavilla vuonna 1981 Vicom -kuvankäsittelyjärjestelmässä, jonka valmistaja oli Vicom Systems, Inc. Kävelyalgoritmi julkaistiin vuonna 1994. Klassinen rekursiivinen tulvan täyttöalgoritmi oli saatavilla myös Vicom -järjestelmässä.

Pseudokoodi

Tämä on optimaalisen kiinteän muistin tulvan täyttöalgoritmin pseudokooditoteutus, joka on kirjoitettu jäsennellyllä englannilla:

Muuttujat
  • cur, markJa mark2kumpikin joko pikselikoordinaateille tai nolla
    • HUOMAUTUS: kun markasetuksena on nolla, älä poista sen aiempaa koordinaattiarvoa. Pidä nämä koordinaatit saatavilla, jotta ne voidaan tarvittaessa palauttaa muistiin.
  • cur-dir, mark-dirJa mark2-dirkukin pitää suunnassa (vasemmalle, oikealle, ylös tai alas)
  • backtrackja findloopjokaisella on boolean arvot
  • count on kokonaisluku
Algoritmi
HUOMAUTUS: Kaikki suunnat (edessä, takana, vasemmalla, oikealla) ovat suhteessa cur-dir 
set cur to starting pixel
set cur-dir to default direction
clear mark and mark2 (set values to null)
set backtrack and findloop to false

while front-pixel is empty do
    move forward
end while

jump to START

MAIN LOOP:
    move forward
    if right-pixel is inside then
        if backtrack is true and findloop is false and either front-pixel or left-pixel is inside then
            set findloop to true
        end if
        turn right
PAINT:
        move forward
    end if
START:
    set count to number of non-diagonally adjacent pixels filled (front/back/left/right ONLY)
    if count is not 4 then
        do
            turn right
        while front-pixel is inside
        do
            turn left
        while front-pixel is not inside
    end if
    switch count
        case 1
            if backtrack is true then
                set findloop to true
            else if findloop is true then
                if mark is null then
                    restore mark
                end if
            else if front-left-pixel and back-left-pixel are both inside then
                clear mark
                set cur
                jump to PAINT
            end if
        end case
        case 2
            if back-pixel is not inside then
                if front-left-pixel is inside then
                    clear mark
                    set cur
                    jump to PAINT
                end if
            else if mark is not set then
                set mark to cur
                set mark-dir to cur-dir
                clear mark2
                set findloop and backtrack to false
            else
                if mark2 is not set then
                    if cur is at mark then
                        if cur-dir is the same as mark-dir then
                            clear mark
                            turn around
                            set cur
                            jump to PAINT
                        else
                            set backtrack to true
                            set findloop to false
                            set cur-dir to mark-dir
                        end if
                    else if findloop is true then
                        set mark2 to cur
                        set mark2-dir to cur-dir
                    end if
                else
                    if cur is at mark then
                        set cur to mark2
                        set cur-dir to mark2-dir
                        clear mark and mark2
                        set backtrack to false
                        turn around
                        set cur
                        jump to PAINT
                    else if cur at mark2 then
                        set mark to cur
                        set cur-dir and mark-dir to mark2-dir
                        clear mark2
                    end if
                end if
            end if
        end case
        case 3
            clear mark
            set cur
            jump to PAINT
        end case
        case 4
            set cur
            done
        end case
    end switch
end MAIN LOOP

Edut

  • Jatkuva muistin käyttö.

Haitat

  • Pääsykuvio ei ole välimuisti- tai bittitasoystävällinen.
  • Voi viettää paljon aikaa kävellen silmukoiden ympäri ennen niiden sulkemista.

Vektorin toteutukset

Inkscapen versio 0.46 sisältää kauhan täyttötyökalun, joka antaa samanlaisen tuloksen kuin tavalliset bittikarttaoperaatiot ja käyttää sitäkin: kangas renderöidään, tulvan täyttö suoritetaan valitulle alueelle ja tulos jäljitetään sitten polulle. Se käyttää rajaehdon käsitettä .

Katso myös

Ulkoiset linkit

Viitteet

  1. ^ a b c Smith, Alvy Ray (1979). Sävy Täytä . SIGGRAPH '79: Tietokonegrafiikkaa ja vuorovaikutteisia tekniikoita käsittelevän kuudennen vuosikonferenssin artikkelit. s. 276–283. doi : 10.1145/800249.807456 .
  2. ^ a b Ackland, Bryan D; Weste, Neil H (1981). Reunalipun algoritmi - Täyttömenetelmä rasteriskannausnäyttöihin . IEEE-tapahtumat tietokoneissa (Volume: C-30, Issue: 1). s. 41–48. doi : 10.1109/TC.1981.6312155 .
  3. ^ a b c d e f g h i j Fishkin, Kenneth P; Barsky, Brian A (1985). Analyysi ja algoritmi täyttämisen lisäämiseksi . Tietokoneella tuotetut kuvat: Graphics Interface'n uusin prosessi '85. s. 56–76. doi : 10.1007/978-4-431-68033-8_6 .
  4. ^ Newman, William M; Sproull, Robert Fletcher (1979). Interaktiivisen tietokonegrafiikan periaatteet (2. painos). McGraw-Hill. s. 253. ISBN 978-0-07-046338-7.
  5. ^ Pavlidis, Theo (1982). Grafiikan ja kuvankäsittelyn algoritmit . Springer-Verlag. s. 181. ISBN 978-3-642-93210-6.
  6. ^ a b c d e f g h i Levoy, Marc (1982). Alueen tulvan algoritmit . KUVA 1981 Kaksiulotteinen tietokoneanimaatio kurssin toteaa.
  7. ^ Foley, JD; van Dam, A; Feiner, SK; Hughes, SK (1990). Tietokonegrafiikka: periaatteet ja käytäntö (2. painos). Addison – Wesley. s. 979–982. ISBN 978-0-201-84840-3.
  8. ^ Heckbert, Paul S (1990). "IV.10: Siemenen täyttöalgoritmi". Julkaisussa Glassner, Andrew S (toim.). Grafiikka Jalokivet . Academic Press. s. 275–277. ISBN 0122861663.
  9. ^ a b Lieberman, Henry (1978). Kuinka värittää värityskirjaan . SIGGRAPH '78: Tietokonegrafiikkaa ja vuorovaikutteisia tekniikoita käsittelevän viidennen vuosikonferenssin artikkelit. s. 111–116. doi : 10.1145/800248.807380 .
  10. ^ a b c Shani, Uri (1980). Alueiden täyttäminen binäärirasterikuvissa: Kaavioteoreettinen lähestymistapa . SIGGRAPH '80: Tietokonegrafiikkaa ja vuorovaikutteisia tekniikoita käsittelevän seitsemännen vuosikonferenssin artikkelit. s. 321–327. doi : 10.1145/800250.807511 .
  11. ^ a b Pavlidis, Theo (1981). Muotojen täyttö rasterigrafiikassa . SIGGRAPH '81: Tietokonegrafiikkaa ja vuorovaikutteisia tekniikoita käsittelevän kahdeksannen vuosikonferenssin artikkelit. s. 29–36. doi : 10.1145/800224.806786 .
  12. ^ Henrich, Dominik (1994). Avaruustehokas alue, joka täyttää rasterigrafiikkaa . Visuaalinen tietokone. s. 205–215. doi : 10.1007/BF01901287 .