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.


  1. 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ů.

  2. 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?

  3. 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).