Ottimizzazione di Algoritmi per l’Elaborazione di Immagini Binarie

Abstract: 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.

 not available