Parallelizzazione di Algoritmi di Connected Components Labeling

L'etichettatura delle componenti connesse (Connected Components Labeling †" CCL) ਠun problema ben definito, ovvero ammette una ed una sola soluzione, e occupa un ruolo primario nell'elaborazione delle immagini. Con l'operazione di etichettatura si trasforma un'immagine binaria in una simbolica in cui a tutti i pixel, appartenenti alla stessa componente connessa, ਠassociata la stessa etichetta. Questa trasformazione ਠindispensabile tutte le volte che un programma deve conoscere gli oggetti presenti in un'immagine binaria e trova applicazione nel campo dell'image processing, della robot vision, in fisica e tanti altri. In passato tanti algoritmi sono stati proposti con l'intento di migliorare l'efficienza di questo tema. Difatti il tempo di esecuzione ha un ruolo cruciale per l'etichettatura di componenti connesse e ogni paradigma esistente puಠessere prestazionalmente confrontato con tutti gli altri. Purtroppo perà², in letteratura esistono pochi articoli a supporto di implementazioni parallele di algoritmi di CCL e che ne mostrino i relativi vantaggi. Questo elaborato di tesi ha quindi l'obiettivo di trovare una via percorribile per il CCL in parallelo, dimostrandone inoltre i vantaggi rispetto ad approcci tradizionalmente sequenziali. La parallelizzazione ਠstata affrontata con due tecniche differenti: utilizzando istruzioni SIMD e mediante l'impiego di multithreading. Nel primo caso ਠstato sfruttato l'algoritmo multiscan di Haralick ma con l'utilizzo di istruzioni AVX2. Invece, la seconda strategia, ha portato all'utilizzo di multithreading, mediante il framework Intel TBB, su algoritmi di tipo two scans. Visti i risultati positivi, l'approccio multithread ਠstato ottimizzato per poter lavorare con molti altri framework e proposte, come l'algoritmo introdotto da Wu et al. in †œTwo Strategies to Speed up Connected Component Labeling Algorithms†� e †œOptimized Block Based with Decision Trees†� pubblicato da Grana et al. . Infine, gli algoritmi ottimizzati sono stati sottomessi a OpenCV, una libreria open source di visione artificiale utilizzata in tutto il mondo, per fornire performance migliori sfruttando a pieno le risorse che i moderni processori mettono a disposizione.