Ottimizzazione di Algoritmi di Etichettatura di Componenti Connesse

Software optimization is the process by which an algorithm is made more efficient in terms of execution time, memory requirement or energy consumption. In the image processing field, time is in many cases the most restrictive constraint; optimization is therefore particularly important to allow tasks operating on considerable amounts of data to end in a reasonable time, and to consent real-time execution when required. An emblematic case in this sense is represented by binary images processing: connected components labeling, morphological operators, contour tracing. All these algorithms are commonly used in the pre- or post-processing phases of image analysis pipelines, even those based on modern deep learning techniques. This thesis introduces different methods for optimizing connected components labeling, for which innovative and efficient solutions are proposed in different contexts. By modeling the problem through a decision table, which defines the actions to be carried out for a pixel based on its neighborhood, and by applying different optimization techniques such as decision trees, block-based approach, state prediction and code compression, it is possible to describe an extremely efficient algorithm that represents the current state of the art. The same techniques are then applied to the labeling of 3D volumes, which represent a further challenge due to the growth of decision tables and the associated computational cost. Finally, specific solutions are explored for so-called bitonal images, stored with one bit per pixel, which allow to further increase efficiency through specific hardware instructions. Later, parallel solutions are explored for connected components labeling with GPUs. Algorithms based on the same decision trees used for the sequential counterpart are initially proposed, and then others are obtained by combining the block-based approach with pre-existing solutions, in order to establish the new state of the art for massively parallel connected components labeling.

L’ottimizzazione del software è il processo con il quale un algoritmo viene reso più efficiente in termini di tempo di esecuzione, memoria richiesta o energia consumata. Nell’ambito dell’elaborazione di immagini, il vincolo temporale è in molti casi quello più stringente; l’ottimizzazione è quindi particolarmente importante per permettere a processi che operano su considerevoli moli di dati di terminare in tempo utile, e consentire, quando richiesto, l’esecuzione in tempo reale. Uno caso emblematico in questo senso è rappresentato dall’elaborazione di immagini binarie: etichettatura delle componenti connesse, operatori morfologici, tracciamento dei contorni. Tutti questi algoritmi vengono comunemente impiegati nelle fasi di pre- o post-processing delle pipeline di analisi di immagini, anche quelle basate sulle moderne tecniche di deep learning. Questa tesi introduce diversi metodi per l’ottimizzazione di etichettatura delle componenti connesse, per la quale vengono proposte soluzioni innovative ed efficienti in diversi contesti. Modellando il problema tramite una tabella decisionale, che definisce le azioni da effettuare per un pixel sulla base dei pixel vicini, e applicando diverse tecniche di ottimizzazione come l’uso di alberi decisionali, approccio a blocchi, predizione dello stato e compressione di codice, viene descritto un algoritmo estremamente efficiente che rappresenta l’attuale stato dell’arte. Le stesse tecniche sono poi applicate all’etichettatura dei volumi 3D, che rappresentano un’ulteriore sfida a causa della crescita delle tabelle decisionali e del costo computazionale associato. Infine, vengono esplorate soluzioni specifiche per le immagini cosiddette bitonali ovvero memorizzate con un bit per pixel, che permettono di aumentare ulteriormente l’efficienza tramite specifiche istruzioni hardware. In seguito, per l’etichettatura di componenti connesse vengono esplorate soluzioni parallele tramite l’utilizzo di GPU. Vengono proposti inizialmente algoritmi basati sugli stessi alberi decisionali utilizzati per la controparte sequenziale, e poi altri ottenuti combinando l’approccio a blocchi con soluzioni preesistenti, in modo da stabilire il nuovo stato dell’arte per l’etichettatura di componenti connesse su architetture ad elevato parallelismo.