Algoritmus náhodného chodce - Random walker algorithm

Náhodný chodec algoritmus je algoritmus pro segmentaci obrazu . V prvním popisu algoritmu uživatel interaktivně označí malý počet pixelů známými štítky (tzv. Semeny), např. „Objekt“ a „pozadí“. Neoznačené pixely si každý představuje uvolnění náhodného chodce a vypočítá se pravděpodobnost, že náhodný chod každého pixelu nejprve dorazí k semenu nesoucímu každý štítek, tj. Pokud uživatel umístí K semena, každý s jiným štítkem, pak je nutné vypočítat pro každý pixel pravděpodobnost, že náhodný chodec opouštějící pixel nejprve dorazí ke každému semenu. Tyto pravděpodobnosti lze určit analyticky řešením soustavy lineárních rovnic. Po výpočtu těchto pravděpodobností pro každý pixel je pixel přiřazen štítku, pro který je nejpravděpodobnější odeslat náhodného chodce. Obrázek je modelován jako graf , ve kterém každý pixel odpovídá uzlu, který je spojen se sousedními pixely hranami, a hrany jsou váženy tak, aby odrážely podobnost mezi pixely. Náhodná procházka se proto vyskytuje na váženém grafu (úvod do náhodných procházek po grafech viz Doyle a Snell).

Přestože byl počáteční algoritmus formulován jako interaktivní metoda segmentace obrazu, byl rozšířen na plně automatický algoritmus, vzhledem k termínu věrnosti dat (např. Před intenzitou). Bylo také rozšířeno na další aplikace.

Algoritmus původně publikoval Leo Grady jako konferenční příspěvek a později jako časopis.

Matematika

Ačkoli byl algoritmus popsán v podmínkách náhodných procházek , pravděpodobnost, že každý uzel pošle náhodnému chodci do semen, lze vypočítat analyticky řešením řídkého pozitivně definitního systému lineárních rovnic pomocí grafu Laplacianská matice , kterou můžeme reprezentovat pomocí proměnná . Ukázalo se, že algoritmus platí pro libovolný počet štítků (objektů), ale expozice je zde z hlediska dvou štítků (pro jednoduchost expozice). ${\ displaystyle L}$

Předpokládejme, že obraz je reprezentován grafem , přičemž každý uzel je spojen s pixelem a každý okraj spojuje sousední pixely a . Okrajové váhy se používají ke kódování podobnosti uzlů, které lze odvodit z rozdílů v intenzitě obrazu, barvě, struktuře nebo jakýchkoli jiných smysluplných vlastnostech. Například pomocí intenzity obrazu v uzlu je běžné používat funkci vážení hran ${\ displaystyle v_ {i}}$${\ displaystyle e_ {ij}}$${\ displaystyle v_ {i}}$${\ displaystyle v_ {j}}$${\ displaystyle g_ {i}}$${\ displaystyle v_ {i}}$

${\ displaystyle w_ {ij} = \ exp {\ left (- \ beta (g_ {i} -g_ {j}) ^ {2} \ right)}.}$

Uzly, hrany a váhy pak lze použít ke konstrukci grafu Laplacianská matice .

Algoritmus náhodného chodce optimalizuje energii

${\ displaystyle Q (x) = x ^ {T} Lx = \ součet _ {e_ {ij}} w_ {ij} \ doleva (x_ {i} -x_ {j} \ doprava) ^ {2}}$

kde představuje proměnnou se skutečnou hodnotou spojenou s každým uzlem v grafu a optimalizace je omezena pomocí pro a pro , kde a představují sady semen popředí a pozadí. Necháme-li reprezentovat množinu uzlů, které jsou nasazeny (tj. ) A představují množinu nenasazených uzlů (tj. Kde je množina všech uzlů), pak je optimum problému minimalizace energie dáno řešením ${\ displaystyle x_ {i}}$${\ displaystyle x_ {i} = 1}$${\ displaystyle v_ {i} \ ve F}$${\ displaystyle x_ {i} = 0}$${\ displaystyle v_ {i} \ v B}$${\ displaystyle F}$${\ displaystyle B}$${\ displaystyle S}$${\ displaystyle S = F \ pohár B}$${\ displaystyle {\ overline {S}}}$${\ displaystyle S \ cup {\ overline {S}} = V}$${\ displaystyle V}$

${\ displaystyle L _ {{\ overline {S}}, {\ overline {S}}} x _ {\ overline {S}} = - L _ {{\ overline {S}}, S} x_ {S},}$

kde se indexy používají k označení části grafu Laplacianská matice indexovaná příslušnými množinami. ${\ displaystyle L}$

Abychom do algoritmu začlenili pravděpodobnostní (unární) výrazy, ukázalo se, že lze optimalizovat energii

${\ displaystyle Q (x) = x ^ {T} Lx + \ gamma \ vlevo ((1-x) ^ {T} F (1-x) + x ^ {T} Bx \ doprava) = \ součet _ {e_ {ij}} w_ {ij} \ left (x_ {i} -x_ {j} \ right) ^ {2} + \ gamma \ left (\ sum _ {v_ {i}} f_ {i} (1-x_ {i}) ^ {2} + \ sum _ {v_ {i}} b_ {i} x_ {i} ^ {2} \ right),}$

pro pozitivní, diagonální matice a . Optimalizace této energie vede k systému lineárních rovnic ${\ displaystyle F}$${\ displaystyle B}$

${\ displaystyle \ left (L _ {{\ overline {S}}, {\ overline {S}}} + \ gamma F _ {{\ overline {S}}, {\ overline {S}}} + \ gamma B_ { {\ overline {S}}, {\ overline {S}}} \ right) x _ {\ overline {S}} = - L _ {{\ overline {S}}, S} x_ {S} - \ gamma F_ { {\ overline {S}}, {\ overline {S}}}.}$

Sada nasazených uzlů,, může být v tomto případě prázdná (tj. ), Ale přítomnost pozitivních diagonálních matic umožňuje jedinečné řešení tohoto lineárního systému. ${\ displaystyle S}$${\ displaystyle {\ overline {S}} = V}$

Pokud se například k začlenění barevného modelu objektu použijí pravděpodobnostní / unární výrazy, pak by to představovalo jistotu, že barva v uzlu by patřila k objektu (tj. Větší hodnota označuje větší jistotu, která patřila k označení objektu ) a představoval by jistotu, že barva v uzlu patří k pozadí. ${\ displaystyle f_ {i}}$${\ displaystyle v_ {i}}$${\ displaystyle f_ {i}}$${\ displaystyle v_ {i}}$${\ displaystyle b_ {i}}$${\ displaystyle v_ {i}}$

Interpretace algoritmů

Algoritmus náhodného chodce byl původně motivován označením pixelu jako objektu / pozadí na základě pravděpodobnosti, že náhodný chodec spadlý na pixel by nejprve dosáhl semene objektu (popředí) nebo semene pozadí. Existuje však několik dalších interpretací stejného algoritmu, které se objevily v.

Výklady teorie obvodů

Existují dobře známá spojení mezi teorií elektrických obvodů a náhodnými procházkami po grafech. V důsledku toho má algoritmus náhodného chodce dvě různé interpretace, pokud jde o elektrický obvod. V obou případech je graf zobrazen jako elektrický obvod, ve kterém je každá hrana nahrazena pasivním lineárním rezistorem . Odpor spojený s hranou je nastaven na (tj. Hmotnost hrany se rovná elektrické vodivosti ). ${\ displaystyle r_ {ij}}$${\ displaystyle e_ {ij}}$${\ displaystyle r_ {ij} = {\ frac {1} {w_ {ij}}}}$

V první interpretaci je každý uzel přidružený k semenu pozadí vázán přímo na zem, zatímco každý uzel přidružený k semenu objektu / popředí je připojen k jednotce stejnosměrného ideálního zdroje napětí vázaného k zemi (tj. K vytvoření jednotky potenciál každého ). Potenciály elektrického obvodu v ustáleném stavu stanovené v každém uzlu touto konfigurací obvodu se přesně budou rovnat pravděpodobnostem náhodných chodců. Konkrétně se elektrický potenciál v uzlu bude rovnat pravděpodobnosti, že náhodný chodec upuštěný v uzlu dosáhne uzlu objektu / popředí před dosažením uzlu na pozadí. ${\ displaystyle v_ {i} \ v B}$${\ displaystyle v_ {i} \ ve F}$${\ displaystyle v_ {i} \ ve F}$${\ displaystyle x_ {i}}$${\ displaystyle v_ {i}}$${\ displaystyle v_ {i}}$

Ve druhé interpretaci je označení uzlu jako objektu nebo pozadí prahováním pravděpodobnosti náhodného chodce na 0,5 ekvivalentní označení uzlu jako objektu nebo pozadí na základě relativní efektivní vodivosti mezi uzlem a semenem objektu nebo pozadí. Konkrétně, pokud má uzel vyšší efektivní vodivost (nižší efektivní odpor) k semenům objektu než k semenům pozadí, pak je uzel označen jako objekt. Pokud má uzel vyšší efektivní vodivost (nižší efektivní odpor) k semenům pozadí než k semenům objektů, pak je uzel označen jako pozadí.

Rozšíření

Tradiční algoritmus náhodného chodce popsaný výše byl rozšířen několika způsoby:

• Náhodné procházky s restartem
• Alfa rohož
• Výběr prahu
• Měkké vstupy
• Spustit na předsegmentovaném obrázku
• Měřítko prostoru náhodná procházka
• Rychlý náhodný chodec využívající offline předpočítání
• Zobecněné náhodné procházky umožňující flexibilní funkce kompatibility
• Mocní povodí sjednocující řezy grafů, náhodný chodec a nejkratší cesta
• Náhodné povodí chodítka
• Vícerozměrné Gaussovské podmíněné náhodné pole

Aplikace

Kromě segmentace obrazu byl algoritmus náhodného chodce nebo jeho rozšíření navíc aplikován na několik problémů v počítačovém vidění a grafice:

• Zbarvení obrazu
• Interaktivní rotoscoping
• Segmentace lékařského obrazu
• Sloučení více segmentací
• Segmentace sítě
• Odšumění sítě
• Úpravy segmentace
• Odstranění stínu
• Stereo shoda (tj. Jednorozměrná registrace obrazu )
• Fúze obrazu

Reference

externí odkazy

• Kód Matlab implementující původní algoritmus náhodného chodce
• Kód Matlab implementující algoritmus náhodného chodce s předpočítáním
• Implementace původního náhodného chodítka v Pythonu v sadě nástrojů pro zpracování obrazu scikit-image v jazyce Python