Povodňová výplň - Flood fill

Image
Rekurzivní povodňová výplň se 4 směry

Flood fill , také nazývaný seed fill , je algoritmus, který určuje a mění oblast připojenou k danému uzlu ve vícerozměrném poli s nějakým odpovídajícím atributem. Používá se v nástroji pro vyplňování „kbelíku“ malířských programů k vyplnění spojených, podobně zbarvených oblastí jinou barvou a ve hrách, jako je Go a Minesweeper, k určování, které kusy jsou vymazány. Varianta nazývaná hraniční výplň používá stejné algoritmy, ale je definována jako oblast připojená k danému uzlu, která nemá konkrétní atribut.

Povodňová výplň není vhodná pro kreslení vyplněných polygonů, protože v ostřejších rozích postrádá některé pixely. Místo toho viz Pravidlo sudých lichých a Nenulové pravidlo .

Parametry algoritmu

Image
Rekurzivní povodňová výplň s 8 směry

Tradiční algoritmus zaplavení má tři parametry: počáteční uzel, cílovou barvu a náhradní barvu. Algoritmus vyhledá všechny uzly v poli, které jsou připojeny k počátečnímu uzlu cestou cílové barvy, a změní je na náhradní barvu. Pro okrajovou výplň bude místo cílové barvy dodána barva ohraničení.

Aby bylo možné generalizovat algoritmus běžným způsobem, následující popisy budou místo toho mít k dispozici dvě rutiny. Jeden volaný, Insidekterý vrací hodnotu true pro nevyplněné body, které by podle své barvy byly uvnitř vyplněné oblasti, a druhý volaný, Setkterý vyplňuje pixel/uzel. Jakýkoli uzel, který Setna něj zavolal, pak již nemusí být Inside.

V závislosti na tom, zda považujeme uzly dotýkající se rohů za spojené nebo ne, máme dvě varianty: osmisměrné a čtyřsměrné.

Rekurzivní implementace založená na zásobníku (čtyřcestná)

Nejdříve známá, implicitně založená na zásobníku, rekurzivní , čtyřsměrná implementace zaplnění záplavami probíhá následovně: 

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.

Ačkoli je snadno pochopitelná, implementace výše použitého algoritmu je nepraktická v jazycích a prostředích, kde je prostor zásobníku výrazně omezen (např. Mikrokontroléry ).

Přesun rekurze do datové struktury

Image
Čtyřcestné zaplnění pomocí fronty pro ukládání
Image
Čtyřcestná záplavová výplň využívající zásobník pro ukládání

Přesun rekurze do datové struktury (buď zásobníku nebo fronty ) zabraňuje přetečení zásobníku. Je to podobné jednoduchému rekurzivnímu řešení, kromě toho, že místo rekurzivního volání tlačí uzly do zásobníku nebo fronty ke spotřebě, přičemž výběr datové struktury ovlivňuje vzor šíření: 

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.

Další potenciální optimalizace

  • Před přidáním do zásobníku/fronty zkontrolujte a nastavte barvu pixelu každého uzlu, čímž zmenšíte velikost zásobníku/fronty.
  • Použijte smyčku pro směr východ/západ, přičemž fronty pixelů nahoře/dole za pochodu. (Je to podobné algoritmům vyplňování polí níže.)
  • Prokládejte dvě nebo více kopií kódu s dalšími zásobníky/frontami, aby procesory OoO měly více příležitostí k paralelizaci
  • Použijte více vláken (ideálně s mírně odlišnými návštěvními objednávkami, aby nezůstaly ve stejné oblasti)

Výhody

  • Velmi jednoduchý algoritmus - snadné vytvoření bez chyb.

Nevýhody

  • Využívá hodně paměti, zejména při použití zásobníku.
  • Testuje nejvíce vyplněné pixely celkem čtyřikrát.
  • Není vhodné pro vyplňování vzorů, protože ke změně vyžaduje výsledky testu pixelů.
  • Vzorec přístupu není pro variantu ve frontě vhodný pro mezipaměť.
  • Nelze snadno optimalizovat pro vícepixelová slova nebo bitplany.

Span Filling

Image
Scanline fill

Je možné věci dále optimalizovat tím, že pracujete především s rozpětími. První publikovaný kompletní příklad funguje na následujícím základním principu. Počínaje počátečním bodem vyplňujete doleva a doprava a sledujete hrany. Poté naskenujete stejnou část řádku výše a řádku níže a vyhledáte nové počáteční body, se kterými budete pokračovat. Tento algoritmus je nejpopulárnější, a to jak pro citace, tak pro implementace, a to navzdory testování většiny vyplněných pixelů celkem třikrát. Ve formě pseudokódu: 

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

Postupem času byly realizovány následující optimalizace:

  • Když by nové skenování bylo zcela v rámci prarodičů, určitě by našlo pouze vyplněné pixely, a proto by nemuselo být ve frontě.
  • Dále, když nové skenování překrývá rozpětí prarodičů, je třeba skenovat pouze převisy (otočky do U a do W).
  • Je možné naplnit při skenování semen

V roce 1990 byla poté publikována finální výplň span-kombinaci-skenování a vyplnění, která probíhá následujícím způsobem (ačkoli verze zde opravuje některé chyby v originále): 

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

Výhody

  • 2x-8x rychlejší než algoritmus rekurzivní v pixelech.
  • Vzor přístupu je vhodný pro mezipaměť a bitplane.
  • Může kreslit vodorovnou čáru, nikoli nastavovat jednotlivé pixely.

Nevýhody

  • Stále navštěvuje již zaplněné pixely. (U populárního algoritmu 3 skenování většiny pixelů. U posledního provedení pouze extra skenování pixelů, kde jsou v vyplněné oblasti díry.)
  • Není vhodné pro vyplňování vzorů, protože ke změně vyžaduje výsledky testu pixelů.

Přidání podpory pro vyplňování vzorů

Dva běžné způsoby, jak podporovat vyplňování vzorů pomocí algoritmů založených na pixelech a pixelech, jsou buď použít jedinečnou barvu jako prostou výplň a poté ji nahradit vzorem nebo sledovat (ve 2d booleovském poli nebo jako oblasti) kterých pixelů byly navštíveny a pomocí nich bylo naznačeno, že pixely již nelze plnit. Inside musí poté vrátit false pro takto navštívené pixely.

Graficko-teoretická výplň

Někteří teoretici na problém aplikovali explicitní teorii grafů, ošetřovali rozpětí pixelů nebo jejich agregáty jako uzly a studovali jejich konektivitu. První publikovaný algoritmus teorie grafů fungoval podobně jako výplň rozpětí výše, ale měl způsob, jak zjistit, kdy by duplikoval vyplňování polí. Bohužel to mělo chyby, díky kterým to nedokončilo některé výplně. Opravený algoritmus byl později publikován s podobným základem v teorii grafů; nicméně mění obraz tak, jak jde, dočasně blokovat potenciální smyčky, což komplikuje programové rozhraní. Později publikovaný algoritmus závisel na tom, že hranice je odlišná od všeho ostatního na obrázku, a proto není vhodný pro většinu použití; to také vyžaduje další bit na pixel pro vedení účetnictví.

Výhody

  • Vhodné přímo pro vyplňování vzorů, protože nikdy nezkouší vyplněné pixely.
  • Zdvojnásobte rychlost původního algoritmu span pro nekomplikované výplně.
  • Vzor přístupu je vhodný pro mezipaměť a bitplane.

Nevýhody

  • Rozpětí musí být pravidelně srovnáváno se všemi ostatními „frontami“ ve frontě, což výrazně zpomaluje komplikované výplně.
  • Přepínání mezi grafickými teoretickými a pixelovými doménami komplikuje porozumění.
  • Kód je poměrně komplikovaný, což zvyšuje pravděpodobnost chyb.

Chůze založené plnění (metoda s pevnou pamětí)

Existuje metoda, která v podstatě nepoužívá paměť pro čtyři propojené oblasti tím, že se vydává za malíře, který se pokouší malovat region, aniž by se namaloval do rohu. Toto je také metoda řešení bludišť. Zkoumají se čtyři pixely tvořící primární hranici, aby se zjistilo, jakou akci je třeba provést. Malíř se mohl ocitnout v jedné z několika podmínek:

  1. Všechny čtyři hraniční pixely jsou vyplněny.
  2. Tři hraniční pixely jsou vyplněny.
  3. Dva okrajové pixely jsou vyplněny.
  4. Je zaplněn jeden okrajový pixel.
  5. Pixely s nulovými hranicemi jsou vyplněny.

Pokud se má dodržovat cesta nebo hranice, použije se pravidlo pravé ruky. Malíř sleduje region tak, že pravou ruku položí na zeď (hranice regionu) a postupuje kolem okraje regionu, aniž by ruku sundal.

V případě č. 1 malíř namaluje (vyplní) pixel, na kterém malíř stojí, a zastaví algoritmus.

Pro případ č. 2 existuje cesta vedoucí z oblasti. Namalujte pixel, na kterém malíř stojí, a pohybujte se ve směru otevřené cesty.

V případě č. 3 dva hraniční pixely definují cestu, která, pokud bychom namalovali aktuální pixel, nám může zabránit v návratu na druhou stranu cesty. Potřebujeme „značku“, abychom definovali, kde se nacházíme a kterým směrem se ubíráme, abychom zjistili, zda se někdy dostaneme zpět na přesně stejný pixel. Pokud jsme již takovou „značku“ vytvořili, zachováme naši předchozí značku a přesuneme se na další pixel podle pravidla pravé ruky.

Značka je použita pro první hranici 2 pixelů, se kterou se setkává, aby si pamatovala, kde průchod začínal a jakým směrem se malíř pohyboval. Pokud se se značkou setkáme znovu a malíř jede stejným směrem, pak malíř ví, že je bezpečné namalovat čtverec značkou a pokračovat stejným směrem. Důvodem je, že (nějakou neznámou cestou) lze v budoucnu dosáhnout a namalovat pixely na druhé straně značky. Značka bude odstraněna pro budoucí použití.

Pokud malíř narazí na značku, ale jde jiným směrem, došlo k nějaké smyčce, která způsobila, že se malíř vrátil ke značce. Tuto smyčku je třeba odstranit. Značka je vyzvednuta a malíř pak pokračuje ve směru, který byl dříve označen značkou, pomocí pravidla levé ruky pro hranici (podobné pravidlu pravé ruky, ale pomocí malířovy levé ruky). Toto pokračuje, dokud není nalezena křižovatka (se třemi nebo více otevřenými hraničními pixely). Malíř stále používá pravidlo levé ruky a nyní hledá jednoduchý průchod (vytvořený dvěma hraničními pixely). Po nalezení této hraniční cesty dvou pixelů je tento pixel vymalován. To přeruší smyčku a umožní algoritmu pokračovat.

V případě č. 4 musíme zkontrolovat protilehlé 8 propojených rohů, abychom zjistili, zda jsou vyplněné či nikoli. Pokud je vyplněno jedno nebo obě, vytvoří se křižovatka s mnoha cestami a nelze ji vyplnit. Pokud jsou oba prázdné, lze aktuální pixel namalovat a malíř se může pohybovat podle pravidla pravé ruky.

Algoritmus obchoduje s časem za paměť. U jednoduchých tvarů je velmi účinný. Pokud je však tvar složitý s mnoha funkcemi, algoritmus stráví velké množství času sledováním okrajů regionu a snaží se zajistit, aby bylo možné vše namalovat.

Tento algoritmus byl poprvé komerčně dostupný v roce 1981 na systému Vicom Image Processing vyráběném společností Vicom Systems, Inc. Algoritmus chůze byl publikován v roce 1994. Klasický algoritmus rekurzivního zaplavení byl k dispozici také na systému Vicom.

Pseudo kód

Toto je implementace pseudokódu optimálního algoritmu zaplnění pevné paměti s pevnou pamětí napsaného strukturovanou angličtinou:

Proměnné
  • cur, marka mark2každý obsahuje buď souřadnice pixelu, nebo hodnotu null
    • POZNÁMKA: pokud markje nastavena na hodnotu null, nevymažte její předchozí hodnotu souřadnic. Mějte tyto souřadnice k dispozici, abyste je v případě potřeby mohli vyvolat.
  • cur-dir, mark-dira mark2-dirkaždý drží směr (vlevo, vpravo, nahoru nebo dolů)
  • backtracka findloopkaždý obsahuje booleovské hodnoty
  • count je celé číslo
Algoritmus
POZNÁMKA: Všechny směry (přední, zadní, levé, pravé) se vztahují k 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

Výhody

  • Konstantní využití paměti.

Nevýhody

  • Vzorec přístupu není vhodný pro mezipaměť ani pro bitplane.
  • Dokáže strávit spoustu času procházením kolem smyček, než je zavře.

Vektorové implementace

Verze 0.46 aplikace Inkscape obsahuje nástroj pro naplnění kbelíku, který poskytuje výstup podobný běžným bitmapovým operacím a dokonce jej používá: plátno se vykreslí, ve zvolené oblasti se provede operace zaplnění a výsledek se poté vysleduje zpět na cestu. Používá koncept okrajové podmínky .

Viz také

externí odkazy

Reference

  1. ^ a b c Smith, Alvy Ray (1979). Tónová výplň . SIGGRAPH '79: Sborník příspěvků ze 6. ročníku konference o počítačové grafice a interaktivních technikách. s. 276–283. doi : 10,1145/800249,807456 .
  2. ^ a b Ackland, Bryan D; Weste, Neil H (1981). Algoritmus hranového příznaku - Metoda výplně pro rastrové skenování . Transakce IEEE na počítačích (svazek: C-30, vydání: 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). Analýza a algoritmus pro plnění šíření . Počítačem generované obrázky: Stav techniky Proceedings of Graphics Interface '85. s. 56–76. doi : 10,1007/978-4-431-68033-8_6 .
  4. ^ Newman, William M; Sproull, Robert Fletcher (1979). Zásady interaktivní počítačové grafiky (2. vyd.). McGraw-Hill. p. 253. ISBN 978-0-07-046338-7.
  5. ^ Pavlidis, Theo (1982). Algoritmy pro grafiku a zpracování obrazu . Springer-Verlag. p. 181. ISBN 978-3-642-93210-6.
  6. ^ a b c d e f g h i Levoy, Marc (1982). Algoritmy pro zaplavení oblasti . SIGGRAPH 1981 Poznámky k kurzu dvourozměrné počítačové animace.
  7. ^ Foley, JD; van Dam, A; Feiner, SK; Hughes, SK (1990). Počítačová grafika: Principy a praxe (2. vyd.). Addison – Wesley. s. 979–982. ISBN 978-0-201-84840-3.
  8. ^ Heckbert, Paul S (1990). „IV.10: Algoritmus plnění osiva“. V Glassner, Andrew S (ed.). Grafické drahokamy . Akademický tisk. s. 275–277. ISBN 0122861663.
  9. ^ a b Lieberman, Henry (1978). Jak vybarvit v omalovánkách . SIGGRAPH '78: Sborník příspěvků z 5. ročníku konference o počítačové grafice a interaktivních technikách. s. 111–116. doi : 10,1145/800248,807380 .
  10. ^ a b c Shani, Uri (1980). Vyplňování oblastí v binárních rastrových obrázcích: graficko-teoretický přístup . SIGGRAPH '80: Sborník příspěvků ze 7. výroční konference o počítačové grafice a interaktivních technikách. s. 321–327. doi : 10,1145/800250,807511 .
  11. ^ a b Pavlidis, Theo (1981). Vyplňování obrysů v rastrové grafice . SIGGRAPH '81: Sborník příspěvků z 8. výroční konference o počítačové grafice a interaktivních technikách. s. 29–36. doi : 10,1145/800224,806786 .
  12. ^ Henrich, Dominik (1994). Prostorově efektivní oblast vyplňující rastrovou grafiku . Vizuální počítač. s. 205–215. doi : 10.1007/BF01901287 .