EVO: cvičení 4 - Detekce hran v obraze pomocí algoritmu mravenčí kolonie
Stáhněte si archív se zdrojovými kódy k dnešní úloze: cv4.zip
Poskytnutý ACO SW vychází z původní (rozšířené) verze popsané v článku:
S. Gullipalli: Search Improvemnt Based on Ants Performance in Image Edge Detection using ACO. University of Paderborn, DE, 2015
Originál dostupný z: https://github.com/syamgullipalli/edge-detection-aco
Pro potřeby výuky EVO upravil: Michal Bidlo, FIT VUT v Brně, 2018
Program cvičení:
V rámci cvičení se nejprve seznamte s principy použití technik ACO pro detehci
hran v obrazu. Výklad k tomu poskytne cvičící. Následně proveďte experimenty
s přiloženým programem, v rámci nichž se pokuste splnit níže uvedené úkoly
a nejlepší vybraná řešení předvést cvičícímu.
Přiložený SW je plně funkční implementací algoritmu Ant Colony System, který
na základě vhodné heuristické funkce vypočítané z původních hodnot intenzit
pixelu obrázku (odstíny šedé na 8 bitech) v několika iteracích identifikuje
co nejlépe důležité hrany v obrazu a tyto vrátí jako výsledek v podobě bitmapy.
Algoritmus pracuje se základní inicializací počátečních pozic mravenců náhodně.
Spuštěním skriptu run.sh proběhne výpočet s vizualizací důležitých obrazových
dat.
- Základní ověření funkce SW: Spusťte skript run_aco.sh, sledujte postup
výpočtu a vyčkejte na dokončení (indikováno hláškou FINISHED running ACS).
Změnou argumentu --image ve skriptu run_aco.sh ověřte funkci systému na různých
obrázcích. Použijte předpřipravené obrázky v adresáři images, případně dodejte
vlastní! POZOR, doporučená rozumná velikost obrázku je max. cca 300x300 pixelů.
Za této situace (konkrétně, nenachází-li se v adresáři se spouštěcím skriptem
soubor ants.ini) je před zahájením algoritmu ACO provedena náhodná inicializace
pozic mravenců v obrázku. Po proběhnutí výpočtu naleznete v adresáři results
uložené výsledky. Především posuďte kvalitu detekce hran v souborech png
v jednotlivých ACO. Pro další experimenty bude zajímavý obrázek Heuristics.png,
jenž využijeme v úkolu 3 pro vhodnější inicializaci pozic mravenců.
- Na zvoleném obrázku experimentujte s různými nastaveními systému volbou
hodnot parametrů v souboru run_aco.sh. Jelikož ACO představuje stochastický
algoritmus, pro jedno konkrétní nastavení a různé nezávislé běhy se výsledky
budou lišit. Je tedy třeba spustit algoritmus vícekrát a pro úspěšný výsledek
zjistit nastavení inicializční hodnoty generátoru pseudonáhodných čísel (seed).
Její výpis je součástí informací poskytovaných během výpočtu na konzoli. Pro
vybrané nastavení a hodnotu seedu demonstrujte funkci detektoru vyučujícímu.
Podařilo se uspokojivě detekovat alespoň základní hrany v obrázku? Jaké jsou
nevýhody výslednýh řešení získaných tímto postupem?
- Proveďte modifikaci náhodné inicializace pozic mravenců tak, aby byly cíleně
umísťovány pokud možno do prostorů s nejvyššími hodnotami heuristické informace.
K tomuto úkolu použijte skript ant_init.sh, který spustí nástroj pro ruční
výběr pozic mravenců z vizualizace heuristické informace k obrázku naposledy
zpracováveného systémem ACO. V něm myší zvolte několik souřadnic v místech
s nejvyšší intenzitou (--> bílá). Po ukončení nástroje (Esc/Return/space) je
vygenerován soubor ants.ini se zvolenými souřadnicemi. Spuštěním ACO pomocí
run_aco.sh dojde k inicializaci pozice mravenců z tohoto souboru. Poznamenejme,
že pokud soubor ants.ini neexistuje, případně pokud je daná souřadnice mimo
rozsah či je nastaven vyšší počet mravenců než je počet souřadnic v ants.ini,
pozice těchto mravenců jsou inicializovány náhodně. Experimentujte s různými
nastaveními parametrů (zejména počtem mravenců, kroků konstrukčním grafem,
počtem iterací a hodnotou q0). Zjistěte seed generátoru pro vybraný kvalitní
výsledek a jeho nalezení opět demonstrujte vyučujícímu.
Ve všech případech se snažte dosáhnout stavu, kdy bude rozumný výsledek nalezen
pomocí co nejnižší celkovou výpočetní náročností (ovlivněno nastavením výše
zmíněných argumentů aplikace).