# A Novel Connected-Components Algorithm for 2D Binarized Images
## 2 Materials and Methods
### Extraction of Connected Components
All experiments were conducted on a PC with an AMD Ryzen 9 7900X3D processor, 64 GB RAM, running Windows 11 Pro 24H2 with OpenCV 4.11. The methods were compiled with Microsoft Visual Studio 2022 update 17.13.6 using optimization flags (-O2) for performance consistency, as well as extended AVX instructions. All tests were performed on 8-connectivity only, due to the fact that the variety in performance obtained when compared to 4-connectivity is minimal. ### Performance Metrics

The evaluation focused on the following primary metrics: \begin{table}
\begin{tabular}{c c c c} \hline \hline
**Dataset** & **Total Images** & **Description** & **Approximate Resolution** \\ \hline Fingerprints [30] & 960 & Collection of fingerprints & 300 \(\times\) 300 \\ \hline Hamlet [31] & 105 & \begin{tabular}{c} Scanned images pertaining to \\ [PERSON]’s Hamlet \\ \end{tabular} & 1200 \(\times\) 2175 \\ \hline Medical [32] & 343 & \
\begin{tabular}{c} Various images of \\ anatomical structures \\ \end{tabular} &
\begin{tabular}{c} Very different sizes: \\ [800–1900] \(\times\) [750–900] \\ \end{tabular} \\ \hline
3 dpes [33] & 23,189 & \begin{tabular}{c} Camera images that \\ captured pedestrians \\ \end{tabular} & 704 \(\times\) 576 \\ \hline Tobacco800 [34; 35] & 1290 & \begin{tabular}{c} Scanned legal \\ business documents \\ \end{tabular} & \
\begin{tabular}{c} Small: 1200 \(\times\) 1600 \\ Large: 2400 \(\times\) 3200 \\ \end{tabular} \\ \hline xDocs [36; 37] & 1677 & Scanned documents & 4700 \(\times\) 3200 \\ \hline Mirflickr [38] & 25,000 & Artistic real-world images & 500 \(\times\) 333 \\ \hline \multirow{3}{*}{Synthetic [22]} & \multirow{3}{*}{90} &
\begin{tabular}{c} Collection of artificially \\ generated images of different \\ densities, varying from \\ 0.1 to 0.9 \\ \end{tabular} & 4096 \(\times\) 4096 \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Datasets used for testing. * Mean execution time: measured in milliseconds, including the standard deviation across the dataset, in order to indicate consistency. * Memory Usage: measured in megabytes (MB), this metric reflects the peak memory allocated by each algorithm. * Memory accesses: the number of times each algorithm required a memory access, measured via a hardware counter. ### Comparative Analysis of Algorithms

Table 3 shows the average execution time per image for the proposed method and compares it against the three aforementioned CCL algorithms, being measured for 10 runs, taking the minimum average across those runs, for each dataset. We use NULL to represent the ideal algorithm, one that just copies the pixels from the input image into the output image. One thing to note is that the label image memory assignment will introduce unnecessary memory allocation overhead, this being true for all algorithms being compared. Thus, for fairness, Table 4 showcases the average execution times for each algorithm with these memory allocation overheads taken out. In addition to execution times, we measured the peak memory usage of each algorithm across a multitude of runs. We chose to avoid measuring the mean, as memory is very dependent on the operating system and device used, and we are more interested in the upper bound. Similarly, since most algorithms allocate the bulk