A New Efficient Split & Merge Algorithm for Embedded Systems

This article presents a new image segmentation algorithm based on a Split & Merge approach. By nature, the execution time of Split & Merge algorithms is data-dependent, as their halting conditions are tied to the homogeneity of each region. While previous algorithms made the Split step less sensitive to input data, the execution time of the more complex Merge step remains highly sensitive to image content. This paper tackles the sensitivity and performance problems from a system and architecture perspective. Memory reallocations due to array fusions are eliminated with the introduction of a TTA (Three Table Array) structure in the Merge step. As iterating over entries in this structure causes a loss of memory locality, we propose two new mechanisms that implement a software cache to mitigate this. An experimental study on an embedded system (Nvidia Jetson Xavier NX) has shown our Merge algorithm to be 10.6 times faster than the state-of-the-art Split & Merge algorithm for $960 \times 720$ images. Moreover, the execution time of our algorithm is also more resistant to image characteristics.