Riassunto analitico
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.
|
Abstract
The Connected Components Labeling (CCL) is a well-known problem with many applications in image processing, physics, engineering and numerous other fields. The labeling process transform an image into a new symbolic one where all pixels which belong to the same connected component (object) are associated to the same identification label, hence labeling is required whenever a computer or a system needs to recognize objects (connected components) in binary images. In the past, many algorithms have been proposed because the improvement of the efficiency of CCL is critical in many applications. These algorithms differ mostly on their execution time and their performance can be easily benchmarked and compared. Unfortunately, in literature there are very few both articles and implementations which show the benefit of parallel connected components labeling algorithms. This work of thesis aim to find a viable way to parallel CCL, discovering the gain of these techniques compared to the traditional ones. The parallelization has been faced mainly with two distinguished approaches: using SIMD instructions and employing multithreading. The first strategy has been applied to the Haralick’s multiscan algorithm using the enhancement provided by AVX2 instructions. The second one, instead has been treated using Intel TBB framework applied to two scans algorithms. Furthermore, the multithread approach has been optimized to work with many other frameworks, allowing parallelization on different architectures and operating systems. The parallel improvement has been applied on distinct algorithms such as the one proposed by Wu et al. in “Two Strategies to Speed up Connected Component Labeling Algorithms” and “Optimized Block Based with Decision Trees” one published by Grana et al. . Finally, the optimized algorithms have been submitted to OpenCV —an open source computer vision and machine learning software library — in order to provide faster implementations to the worldwide computer vision community.
|