A Parallel Implementation for Computing the Region-Adjacency-Tree of a Segmentation of a 2D Digital Image

Area of Science:

• Computer Vision
• Image Processing
• Parallel Algorithms

Background:

• Region-Adjacency Trees (RATs) are crucial for representing spatial relationships in image segmentation.
• Efficient computation of RATs is challenging, especially for large-scale 2D digital images.
• Existing methods may not scale effectively on modern parallel computing architectures.

Purpose of the Study:

• To design and implement a novel parallel algorithm for computing the Region-Adjacency Tree of 2D image segmentations.
• To leverage Homological Spanning Forest (HSF) structures for efficient region analysis.
• To evaluate the scalability of the proposed algorithm on multicore processors.

Main Methods:

• A parallel algorithm was developed for RAT computation.
• The approach utilizes a distributed computation of Homological Spanning Forest (HSF) for connected regions.
• A classical geometric algorithm determines spatial inclusion between segmented regions.

Main Results:

• The implemented parallel algorithm successfully computes Region-Adjacency Trees.
• The technique demonstrates excellent scalability when executed on multicore processors.
• The distributed HSF computation and geometric inclusion methods are effective.

Conclusions:

• The proposed parallel algorithm offers an efficient solution for generating Region-Adjacency Trees from 2D image segmentations.
• The method's strong scalability makes it suitable for high-performance computing environments.
• This work advances the field of image analysis by providing a scalable tool for understanding regional image structures.