# A Novel Connected-Components Algorithm for 2D Binarized Images
## 2 Materials and Methods
### Extraction of Connected Components
This could be considered an expected trade-off, and some future developments could consider switching to a different merging or labeling structure when encountering highly fragmented images. ### Comparison with RLE-Based Methods

The proposed method shares a common RLE foundation with a couple of other state-of-the-art algorithms, such as SBLA [27], RBTS [28], BRTS, and BMRS [29]. However, there are key implementation differences that distinguish our approach. In the case of RBTS and SBLA, they use structured tables or buffers in order to manage runs and provide provisional labels across rows. RBTS, for example, uses a circular buffer of run descriptors and a compact equivalence table. Similarly, SBLA relies on scan-based merging and traversing rows across stripes. In contrast, our method employs a pointer-linked segment structure where each run is represented as a lightweight object with references to its head component and the next segment after it for faster traversal. Merging is done via a union-by-size heuristic using direct pointer reassignment, without requiring circular buffers or label tables. This, in turn, offers simpler memory management and allows for a possible faster traversal of the overall structure, especially in sparse images. Additionally, algorithms like BRTS and BMRS operate in a similar manner to our algorithm when computing the initial run segments by traversing the image in a bitwise fashion. More specifically, they use 64-bit operators and rely on methods such as Fast Forward Scan or masked bit OR in order to merge and detect runs in binary images. While we also process runs in a bitwise fashion, our method relies on a precomputed segment cache that allows us to decode all 16-bit binary patterns in constant time. While both BRTS and BMRS perform faster in every scenario, they also tend to consume the most memory. In contrast, while our algorithm is slower, the lower memory footprint, due to pointer-linked structures, makes it better suited to scenarios that contain very large input images or constrained hardware environments. ## 5 Conclusions

The paper presents a novel RLE CCL algorithm optimized for speed, memory efficiency, and scalability. By processing horizontal runs, rather than individual pixels, and employing a direct pointer-based merging strategy, the method achieves significant improvements over traditional algorithms, such as SAUF, BBDT, and Spaghetti, particularly on sparse or moderately dense datasets and those with high-resolution images. The proposed approach is not only much faster than some of the aforementioned algorithms by up to 50% in certain scenarios but also offers a lower memory footprint and better cache locality, offering a variety of advantages to real-world image processing tasks and making it suitable for memory-constrained environments. The relationships between runs are adjusted without modifying the memory layout, leading to fast updates without memory fragmentation. Additionally, our proposed method can be considered suitable for large-scale image processing applications, particularly in high-resolution document analysis, industrial inspection, and medical imaging. Despite its strengths, the method does show its limitations, particularly when processing high-density, fragmented images, such as those in the Synthetic dataset. The creation of many short runs in such images leads to an increase in merging operations, impacting the overall performance. While both 4- and 8-way connectivity are supported in the current implementation, diagonal merging is not yet as optimized as block-based methods. Thus, future work could investigate quad-tree-based merging heuristics to improve performance under 8-way connectivity, particularly in images with irregular component shapes. Another area for enhancement lies in parallel execution. The current implementation is CPU-bound and sequential, but the algorithm is inherently parallelizable.