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.
Nel passato sono stati proposti molti paradigmi di CCL e, dal momento che l'immagine di output è univoca, questi differiscono principalmente per la velocità di esecuzione. Data la maturità del problema e le finezze coinvolte nelle implementazioni, è importante permettere alla comunità di replicare i risultati senza l'onere di reimplementare ogni nuovo algoritmo proposto.
Il presente lavoro di tesi si pone l'obiettivo di risolvere questo problema sviluppando YACCLAB - Yet Another Connected Components Labeling Benchmark - una piattaforma open-source che permette di testare nuovi algoritmi di CCL e confrontarli con quelli attualmente disponibili. YACCLAB genera automaticamente file testuali e grafici contenenti i risultati di quattro differenti tipi di test, che permettono di analizzare i vari metodi secondo prospettive differenti. La correttezza dei risultati è garantita eseguendo tutti i test nello stesso sistema (hardware e software) e sugli stessi dataset.
Per migliorare le performance della funzione “connectedComponents” delle OpenCV - una libreria open-source di visione artificiale utilizzata in tutto il mondo - abbiamo, inoltre, implementato e sottomesso una versione ottimizzata, e compatibile con la libreria, dell'algoritmo “Optimized Block Based with Decision Trees” originariamente proposto da Grana et al. nel 2010. I test eseguiti tramite YACCLAB dimostrano che la versione proposta e' più veloce, in media, del 31% su immagini di documenti e del 128% su immagini naturali binarizzate, rispetto a quella attualmente presente nelle OpenCV.
Per ultimo, ma non per importanza, questo lavoro di tesi ha portato allo sviluppo di un nuovo paradigma di CCL che punta a minimizzare il numero di accessi in memoria sfruttando le informazioni sui pixel già analizzati. La fase di scansione dell'algoritmo proposto è guidata da una foresta di alberi decisionali connessi a formare un singolo grafo. Ogni albero decisionale è stato ottenuto mediante una riduzione dell'albero decisionale ottimo.
|
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.
Several algorithms for CCL have been presented in the past. Since an exact solution to the problem exists and should be mandatory provided as output, algorithms mainly differ on their execution speed. Given the maturity of the problem and the subtlety involved in the implementation, it should be obligatory to allow the community to reproduce the results without forcing everyone to reimplement every proposal.
This work of thesis aim to accommodate these problems providing YACCLAB - Yet Another Connected Components Labeling Benchmark - which contains an open source platform to test new proposals and to compare them with publicly available competitors. YACCLAB automatically generates textual and graphical outputs for four kinds of test, and analyze the methods from different perspectives. The fairness of the comparisons is granted by running on the same system and over the same datasets.
Moreover, in order to improve the performance of “connectedComponents” function in OpenCV - an open source computer vision library adopted all around the world - we implemented and submitted an optimized and compliant version of “Optimized Block Based with Decision Trees” proposed by Grana et al. on 2010. According to YACCLAB tests, the proposed code is, on average, 31% faster on document images and 128% faster on natural images, than the one currently included in OpenCV.
Last but not least, we proposed a new paradigm for CCL, which employs a general approach to minimize the number of memory accesses, by exploiting the information provided by already seen pixels, removing the need to check them again. The scan phase of our proposed algorithm is ruled by a forest of decision trees connected into a single graph. Every tree derives from a reduction of the complete optimal decision tree.
|
