# A Novel Connected-Components Algorithm for 2D Binarized Images
## 2 Materials and Methods
### Extraction of Connected Components
\begin{table}
\begin{tabular}{c c c c c c c c} \hline \hline
**MethodDataset** & **Fingerprints** & **Hamlet** & **Medical** & **3 dpes** & **Tobacco** & **xDocs** & **Mirfilckr** & **Synthetic** \\ \hline
**SAUF** & 5 & 55 & 30 & 13 & 166 & 385 & 13 & 319 \\ \hline
**BBDT** & 6 & 58 & 31 & 16 & 164 & 400 & 15 & 325 \\ \hline
**PRED** & 6 & 62 & 31 & 16 & 167 & 416 & 15 & 325 \\ \hline
**DRAG** & 6 & 56 & 29 & 16 & 168 & 414 & 15 & 324 \\ \hline
**Spaghetti** & 6 & 59 & 32 & 16 & 168 & 411 & 13 & 324 \\ \hline
**SBLA** & 8 & 54 & 38 & 14 & 156 & 308 & 12 & 296 \\ \hline
**BRTS** & 10 & 65 & 46 & 18 & 227 & 489 & 18 & 393 \\ \hline
**BMRS** & 9 & 67 & 49 & 18 & 231 & 495 & 18 & 395 \\ \hline
**Proposed** & 3 & 14 & 41 & 13 & 81 & 100 & 12 & 252 \\ \hline \hline \end{tabular}
\end{table} 
Table 5: Peak memory allocation (in Megabytes) per dataset for each CCL algorithm. One thing to note is that, while all other algorithms are evaluated using a UFPC as a backend for resolving label equivalences, our method uses a different merging mechanism, namely, a linked-list-based union-by-size approach. When two components are merged, the smaller list of nodes is traversed, and each node's head pointer is updated directly. This allows skipping recursive find operations and the extra logic used in maintaining balanced trees, which are inherent in UFPC. While this merge can vary in performance, when the list of segments that need to be compared is small, such as in the case of sparse or dense images, the reduced number of memory accesses, minimal branching, and better cache behavior push it to the top. On the other end, on datasets that contain very small images, such as Fingerprints or mirflickr, or those that contain extremely sparse ones, such as 3 dpes, our algorithm still outperforms the vast majority of the rest and ties or is very close in performance to Spaghetti. This is likely due to the fact that pre-caching and other sorts of optimizations are not that beneficial, due to the small size of the images, allowing for algorithms that go directly to traversing the image to come ahead. One major downside of our algorithm is its performance on the Synthetic dataset, which contains some images of mixed density. For these images, when the density is around 50%, the number of runs that contain a very small number of pixels will increase exponentially. In such cases, our algorithm is ill-equipped to deal with such a scenario, creating very large lists of pixels, and making UFPC approaches more efficient. However, while this is a limitation, it is not applicable to most real-world scenarios. ### Memory Efficiency and Access Patterns

The proposed method demonstrates not only strong computational performance but also consistent memory efficiency. Using pre-allocated run structures stored in cache memory reduces both peak memory usage and memory fragmentation. On high-resolution datasets such as xDocs or Tobacco, the algorithm uses significantly less memory than the others, achieving savings of over 50% in some cases. It is important to mention that the other algorithms all tend to have similar peak memory usage. This is likely due to the UFPC structure needing to allocate the memory for its solution, rather than the algorithms consuming most of their memory during segment retrieval. Something to note is that while other RLE algorithms might be faster than ours, such as BRTS and BMRS, they tend to have a very large memory footprint, especially on datasets with large images, such as xDocs, consuming close to 500 MB at peak memory usage. Meanwhile, our algorithm sits at a fifth of the memory usage, reaching only 100 MB at its peak. However, our algorithm tends to be less suited to noisy images, as demonstrated on the Synthetic dataset, where very short and numerous runs introduce overhead that increases both execution time and the number of memory access patterns by orders of magnitude when compared to the other algorithms.