Detekce hranice dynamickým programováním

Dynamické programování je optimalizační metoda založená na postupném řešení menších podúloh a složení konečného výsledku z těchto dílčích řešení, každé dílčí řešení je typicky mnohokrát využito.

Hranici v obraze si v této úloze definujeme jako cestu z pixelů o minimální celkové intenzitě vedoucí z jedné strany obrazu k protější straně (pro nalezení maximální cesty použijeme negativ obrazu). Cesta do pixelu Y může vést rovně nebo šikmo, ale nikdy ne ze strany ani se nesmí vracet:

X1 X2 X3 \ | / Y

Jestliže známe optimální cestu path(X_i) do pixelů X_1...3 a její cenu cost(X_i), pak optimální cesta do Y vede přes arg min(cost(X_i)) a její cena je cost(Y) = intensity(Y)+min(cost(X_i)). Pokud tedy hledáme cestu z horního okraje ke spodnímu, postupujeme po řádcích:

1. inicializujeme cenu cesty do pixelů prvního řádku jejich intenzitou
2. po řádcích počítáme cenu optimální cesty do každého pixelu s pomocí výsledků z předchozího řádku
3. nalezneme cíl jako pixel na posledním řádku, do nějž vede nejlevnější cesta
4. z cíle postupujeme zpět po zapamatovaných předchůdcích a zaznamenáváme optimální cestu

Algoritmus lze upravit pro více "kličkující" cesty rozšířením množiny povolených kroků v cestě (s případným zvýšením ceny delších kroků), ale všechny musí vést z předchozího řádku. Povolení kroků zpět by vedlo na Dijkstrův algoritmus pro nalezení nejkratší cesty v grafu (který také patří do kategorie dynamického programování).