Ottimizzazione di Algoritmi per l’Elaborazione di Immagini Binarie

The procedure of making an algorithm more efficient in terms of memory requirements or execution time is called optimization and represents a crucial step in image and video processing. Usually, it is achieved with a trade-off between time and memory. Anyway, in many scenarios the total execution time required to complete a task is the most restrictive constraint. Binary image processing algorithms, for example, represent a fundamental pre- and post-processing operation in most of the state-of-the-art image and video analysis pipelines, even when they are based on deep learning techniques. For this reason, having a fast implementation is crucial, especially when these pipelines must be employed in real time scenarios in which compromising the output quality result or resort to more powerful hardware is not a choice. This thesis introduces and explores different approaches for the optimization of all the binary image processing algorithms that can be modeled with decision tables. There is a large amount of algorithms that can be defined in such a way: Connected Component Labeling, Thinning, Chain Code, and Morphological operators are some of them. Generally, all those algorithms in which the output value for each image pixel is obtained from the value of the pixel itself and of some of its neighbors can be defined using decision tables. Focusing on Connected Component Labeling, this thesis analyzes the state-of-the-art approaches for both sequential CPU-based and parallel CPU- and GPU-based environments, focusing on how to fairly measure performance. We then introduce novel approaches to further optimize such a kind of algorithms, showing how these optimization techniques can be generalized to boost the performance of any algorithm modeled with decision tables. A framework that allows to automatically apply the optimization strategies to a given problem is then presented. The framework, called GRAPHGEN, takes a definition of the problem in terms of conditions to check and actions to be performed as input and it is able to produce the C++ code including all the required optimizations as output. When compared to existing approaches, the algorithms generated with GRAPHGEN perform significantly better than previous state-of-the-art algorithms, on real-world and synthetic datasets.

La procedura che rende un algoritmo più efficiente in termini di requisiti di memoria o tempo di esecuzione si chiama ottimizzazione e rappresenta un passaggio cruciale nell'elaborazione di immagini e video. È raro che il processo di ottimizzazione produca un algoritmo ottimo in senso assoluto, ma spesso occorre raggiungere un compromesso tra i requisiti di tempo e quelli di memoria. Ad ogni modo, esistono molti scenari in cui il tempo di esecuzione totale richiesto per completare un'attività è il vincolo più restrittivo. Gli algoritmi di elaborazione di immagini binarie, ad esempio, rappresentano un'operazione fondamentale nella maggior parte dei sistemi di analisi di immagini e video all'avanguardia, anche quando questi sono basati su tecniche di deep learning. Avere un'implementazione efficiente è quindi essenziale, specialmente quando questi sistemi devono essere impiegati in scenari con vincoli temporali, dove compromettere la qualità del risultato, o fare affidamento su hardware più performante, non è una strada percorribile. Questa tesi introduce ed esplora diversi approcci per l'ottimizzazione degli algoritmi di elaborazione di immagini binarie modellabili con tabelle decisionali. Esistono diversi problemi che possono essere definiti in questo modo: l’etichettatura delle componenti connesse, il thinning, il chain code e gli operatori morfologici sono alcuni di questi. In generale, tutti gli algoritmi in cui il valore di output per ciascun pixel dell'immagine è ottenuto dal valore del pixel stesso e di alcuni dei suoi vicini possono essere definiti utilizzando tabelle decisionali. Concentrandosi sull'etichettatura delle componenti connesse, vengono analizzati gli approcci all'avanguardia sia per ambienti sequenziali basati su CPU che per ambienti paralleli basati su CPU e GPU, focalizzandosi su come misurare in modo equo le prestazioni. Vengono quindi introdotti nuovi approcci per migliorare ulteriormente le prestazioni in termini di tempo totale di esecuzione, mostrando come queste tecniche possano essere generalizzate per migliorare qualsiasi algoritmo modellabile con tabelle decisionali. Infine, viene presentato un framework che consente di applicare automaticamente molte delle strategie di ottimizzazione precedentemente descritte ed analizzate ad un determinato algoritmo. Il framework, chiamato GRAPHGEN, prende come input una definizione del problema in termini di condizioni da verificare e azioni da eseguire ed è in grado di produrre come output il codice C/C++ che include tutte le ottimizzazioni necessarie. Rispetto agli approcci esistenti, gli algoritmi generati con GRAPHGEN hanno prestazioni significativamente migliori, sia su set di dati reali che su quelli sintetici.