Ottimizzazione di Algoritmi di Etichettatura di Componenti Connesse

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

 not available