Algoritmus náhodného chodce - Random walker algorithm - Wikipedia

The algoritmus náhodného chodce je algoritmus pro segmentace obrazu. V prvním popisu algoritmu^[1] uživatel interaktivně označí malý počet pixelů známými štítky (nazývanými seed), např. „objekt“ a „pozadí“. Neoznačené pixely si každý představuje uvolnění náhodného chodítka 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^[2]).

Ačkoli byl počáteční algoritmus formulován jako interaktivní metoda pro segmentaci obrazu, byl rozšířen o plně automatický algoritmus, vzhledem k termínu věrnosti dat (např. Před intenzitou).^[3] Bylo také rozšířeno na další aplikace.

Algoritmus původně publikoval Leo Grady jako konferenční příspěvek^[4] a později jako deník.^[1]

Matematika

Ačkoli byl algoritmus popsán v podmínkách náhodné procházky, pravděpodobnost, že každý uzel pošle náhodný chodec do semen, lze vypočítat analyticky řešením řídkého systému pozitivních konečných lineárních rovnic s grafem Laplaciánská matice, které můžeme proměnnou představovat ${ displaystyle L}$. 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).

Předpokládejme, že obrázek je reprezentován a graf, s každým uzlem ${ displaystyle v_ {i}}$ spojené s pixelem a každou hranou ${ displaystyle e_ {ij}}$ připojení sousedních pixelů ${ displaystyle v_ {i}}$ a ${ displaystyle v_ {j}}$. 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 ${ displaystyle g_ {i}}$ v uzlu ${ displaystyle v_ {i}}$, je běžné používat funkci vážení hran

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

Uzly, hrany a váhy pak mohou být použity ke konstrukci grafu Laplaciánská matice.

Algoritmus náhodného chodce optimalizuje energii

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

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

${ 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 ${ displaystyle L}$ indexovány příslušnými sadami.

Aby bylo možné do algoritmu začlenit (unární) pojmy pravděpodobnosti, bylo ukázáno v ^[3] že jeden může 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 ${ displaystyle F}$ a ${ displaystyle B}$. Optimalizace této energie vede k systému lineárních rovnic

${ 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ů, ${ displaystyle S}$, mohou být v tomto případě prázdné (tj. ${ displaystyle { overline {S}} = V}$), ale přítomnost kladných diagonálních matic umožňuje jedinečné řešení tohoto lineárního systému.

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

Interpretace algoritmů

Algoritmus náhodného chodce byl zpočátku 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 zárodku objektu (popředí) nebo zárodku pozadí. Existuje však několik dalších interpretací stejného algoritmu, které se objevily v.^[1]

Výklady teorie obvodů

Mezi nimi jsou dobře známá spojení elektrický obvod teorie a náhodné procházky po grafech.^[5] 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í lineární odpor. Odpor, ${ displaystyle r_ {ij}}$, spojené s hranou ${ displaystyle e_ {ij}}$ je nastaven na ${ displaystyle r_ {ij} = { frac {1} {w_ {ij}}}}$ (tj. hmotnost hrany se rovná elektrická vodivost ).

V první interpretaci každý uzel přidružený k semenu pozadí, ${ displaystyle v_ {i} v B}$, je vázán přímo na přízemní zatímco každý uzel přidružený k semenu objektu / popředí, ${ displaystyle v_ {i} ve F}$ je připojen k jednotce stejnosměrný proud ideál zdroj napětí svázán se zemí (tj. stanovit v každé jednotkový potenciál ${ displaystyle v_ {i} ve F}$). 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ě elektrický potenciál, ${ displaystyle x_ {i}}$ v uzlu ${ displaystyle v_ {i}}$ se bude rovnat pravděpodobnosti, že náhodný chodec spadl v uzlu ${ displaystyle v_ {i}}$ dosáhne uzlu objektu / popředí před dosažením uzlu pozadí.

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^[6]
• Alfa rohož^[7]
• Výběr prahu^[8]
• Měkké vstupy^[9]
• Spustit na předsegmentovaném obrázku^[10]
• Měřítko prostoru náhodná procházka^[11]
• Rychlé náhodné chodítko pomocí offline předpočítání ^[12][13]
• Zobecněné náhodné procházky umožňující flexibilní funkce kompatibility ^[14]
• Mocní povodí sjednocující řezy grafů, náhodný chodec a nejkratší cesta ^[15]
• Náhodné povodí chodítka ^[16]
• Vícerozměrné Gaussovo podmíněné náhodné pole ^[17]

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^[18]
• Interaktivní rotoscoping^[19]
• Segmentace lékařského obrazu^[20][21][22]
• Sloučení více segmentací^[23]
• Segmentace sítě^[24][25]
• Odšumění sítě^[26]
• Úpravy segmentace^[27]
• Odstranění stínu^[28]
• Stereo párování (tj. Jednorozměrné registrace obrázku )^[29]
• Fúze obrazu ^[14][17]

Reference

externí odkazy

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