Fast Labeled Spanning Tree in Binary Irregular Graph Pyramids

Irregular Pyramids are powerful hierarchical structures in pattern recognition and image processing. They have high potential of parallel processing that makes them useful in processing of a huge amount of digital data generated every day. This paper presents a fast method for constructing an irregular pyramid over a binary image where the size of the images is more than 2000 in each of 2/3 dimensions. Selecting the contraction kernels (CKs) as the main task in constructing the pyramid is investigated. It is shown that the proposed fast labeled spanning tree (FLST) computes the equivalent contraction kernels (ECKs) in only two steps. To this purpose, first, edges of the corresponding neighborhood graph of the binary input image are classified. Second, by using a total order an efficient function is defined to select the CKs. By defining the redundant edges, further edge classification is performed to partition all the edges in each level of the pyramid. Finally, two important applications are presented : connected component labeling (CCL) and distance transform (DT) with lower parallel complexity 𝒪(𝑙𝑜𝑔(𝛿)) where the 𝛿 is the diameter of the largest connected component in the image.