Riassunto analitico
L'etichettatura delle componenti connesse (Connected Components Labeling - CCL) di una immagine binaria ricopre un ruolo fondamentale nel processamento di immagini ed è un problema ben definito, ovvero ammette una ed una sola soluzione. Con l'operazione di etichettatura si trasforma un'immagine binaria in un'immagine simbolica in cui a tutti i pixel appartenenti allo stesso oggetto (componente connessa) viene assegnata la stessa etichetta. Questa trasformazione è indispensabile tutte le volte che un programma deve conoscere gli oggetti presenti in un'immagine ed è alla base di molti algoritmi di pattern analysis, computer vision e robot vision. A partire dalla prima proposta di algoritmo di etichettatura, che risale agli anni '60, molti approcci hanno ottimizzato il carico computazionale necessario per etichettare un'immagine. Nella scorsa decade, dato il crescente utilizzo di GPU per l'elaborazione di immagini, sono state presentate anche diverse proposte di algoritmi paralleli. L'obiettivo principale di questa tesi è lo sviluppo di nuove strategie per migliorare le prestazioni di algoritmi sia in CPU che in GPU.
Per quanto riguarda gli algoritmi sequenziali, le foreste decisionali e la predizione di pixel si sono recentemente dimostrate essere efficienti strategie per migliorare le prestazioni. In questa tesi, le tecniche di predizione di pixel e compressione di codice sono state unite all'utilizzo di una maschera a blocchi: l'algoritmo risutante è modellato come un grafo diretto aciclico.
Nell'ambito degli algoritmi paralleli, gran parte delle proposte recenti si sono focalizzate sulla connettività a 4, trascurando l'importanza della connettività a 8. In questa tesi, gli algoritmi per GPU che rappresentano lo stato dell'arte per la connettività a 4 sono stati estesi alla connettività a 8, e sono stati migliorati con ottimizzazioni addizionali, tra le quali la più significativa è l'utilizzo di un approccio a blocchi. Inoltre, sono mostrate varianti degli stessi algoritmi per l'etichettatura di componenti connesse in volumi tridimensionali.
Lo strumento di benchmarking più utilizzato per la valutazione di algoritmi di etichettatura di componenti connesse è YACCLAB - Yet Another Connected Components LAbeling Benchmark, una piattaforma open-source che permette di effettuare test di nuove proposte e confrontarle con alternative pubblicamente disponibili. Tuttavia, YACCLAB è stato progettato specificamente per algoritmi di etichettatura di immagini bidimensionali in CPU; parte del lavoro ha consistito nell'estensione del framework, tramite l'aggiunta della funzionalità di effettuare test di algoritmi in GPU e di algoritmi che lavorano su volumi tridimensionali.
Gli algoritmi proposti in questa tesi sono poi stati valutati tramite YACCLAB, e test eseguiti su dataset sintetici e reali ne mostrano il vantaggio prestazionale rispetto allo stato dell'arte.
|
Abstract
Connected Components Labeling (CCL) in binary images is an important and well-defined problem in image processing. With the labeling operation, a binary image is transformed into a symbolic image in which all pixels belonging to the same connected component (object) are given the same label: this transformation is required whenever a computer program needs to identify independent objects in an image. Therefore, it is a fundamental pre-processing task of many pattern analysis, computer vision and robot vision algorithms. Since the first proposal of a labeling algorithm, which dates back to the sixties, many approaches have optimized the computational load needed to label an image. In the last decade, given the growing use of GPUs in image processing applications, many data parallel CCL techniques have been proposed as well.
This work of thesis mainly aims to develop new strategies to improve the performance of CCL algorithms both on CPUs and GPUs.
As regards sequential algorithms, the use of decision forests and pixel prediction strategies have recently appeared as valuable strategies to improve performance. In this thesis, a block-based mask is combined with pixel prediction and code compression: the resulting algorithm is modeled as a Directed Rooted Acyclic Graph with multiple entry points.
For what concerns parallel solutions, most of the recent proposals have focused on 4-way connectivity neglecting the importance of 8-way connectivity. In this thesis, state-of-the-art GPU-based algorithms are extended from 4 to 8-way connectivity and improved with additional optimizations, among which the most significant one is the use of a block-based approach. Moreover, variations of the proposed algorithms for the labeling of connected components in 3D volumes are discussed.
The most used benchmarking framework for the evaluation of CCL algorithms is YACCLAB - Yet Another Connected Components Labeling Benchmark, an open-source platform to test new proposals and to compare them with publicly available competitors.
Anyway, YACCLAB was specifically designed for CPU algorithms and 2D CCL. Thus, part of the work consisted of its extension, in order to make it also suitable for GPU algorithms and 3D CCL.
When tested with YACCLAB on synthetic and real datasets, in comparisons with state-of-the-art alternatives, the proposed algorithms show superior performance, beating the results obtained by all compared approaches in all settings.
|