Redundant edges and parallel algorithms in binary irregular graph pyramids

Abstract

In the modern digital era, an astonishing volume of data is being produced across a diverse range of fields, encompassing biomedical imaging, document processing, geosciences, remote sensing, video surveillance, social media, machine learning, and artificial intelligence. The efficient processing of such expansive data necessitates the development of effective data structures and parallel algorithms with minimal complexity. Improvements in hardware and the increase in massively available processing elements have rendered parallel processing a compelling solution to accelerate algorithm execution. Irregular pyramids represent a powerful hierarchical structure that progressively reduces data size across levels, enabling rapid extraction of global information. Owing to their logarithmic height relative to the input size and parallel architecture, these structures offer considerable efficiency. In irregular pyramids, the fundamental data structure is a general graph embedded in image space, unconfined to array structures. However, graphs as versatile representative tools may harbor many redundant edges, thus accumulating memory. Conventional approaches to constructing irregular pyramids involve selecting a set of edges for contraction to produce a smaller graph at a higher level, which is then simplified by removing unnecessary edges. Contrarily, this thesis introduces a method dubbed Remove then Contract (RtC), that predicts and eliminates redundant edges prior to pyramid construction under certain conditions. This approach not only reduces memory requirements for data storage but also simplifies the pyramid construction process. It has been demonstrated that the upper bound of redundant edges is half of all edges in the input graph. Moreover, by defining a set of independent edges in irregular pyramids, operations can be performed in a fully parallel manner. Given a sufficient number of available processing elements, the algorithms proposed herein exhibit parallel complexity, where the only limiting factors are memory requirements or the number of available independent processing elements. However, as the number of available processing elements increases, the efficiency of these algorithms becomes increasingly pronounced. The thesis applies the constructed irregular pyramid to perform fundamental binary image operations with reduced computational complexity. Two pivotal methods, Connected Component Labeling (CCL) and Distance Transform (DT), which necessitate both local and global information, are examined. A new pyramidal parallel connected component labeling is proposed that reduces the computational complexity of CCL from sequential linear tovii parallel logarithmic complexity, O(log n), where n is the diameter of the largest connected component (CC) in the 2D binary image. This method not only performs the CCL task but also provides topological information between CCs containing inclusions and multi- boundaries. The DT is also computed with parallel logarithmic complexity, O(log n), where n is the maximum diameter of the largest foreground region in the 2D binary image. Furthermore, by defining DT over other data structures, such as combinatorial maps and n-dimensional generalized maps, novel DTs with higher resolution and n different distances are introduced. The efficiency of the proposed methods is demonstrated through simulation and comparison with state-of-the-art methods.