# 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 c} \hline \hline \multirow{2}{*}{**MethodDataset**} & \multirow{2}{*}{**Fingerprints**} & \multirow{2}{*}{**Hamlet**} & \multirow{2}{*}{**Medical**} & \multirow{2}{*}{**3 dpes**} & \multirow{2}{*}{**Tobacco**} & \multirow{2}{*}{**xDocs**} & \multirow{2}{*}{**Mifflickr**} & \multirow{2}{*}{**Synthetic**} \\ \hline
**NULL** & 0.01 \(\pm\) 0.003 & 0.29 \(\pm\) 0.07 & 0.11 \(\pm\) 0.03 & 0.02 \(\pm\) 0.01 & 0.58 \(\pm\) 0.32 & 2.52 \(\pm\) 0.38 & 0.01 \(\pm\) 0.002 & 2.58 \(\pm\) 0.33 \\ \hline
**SAUF** & 0.19 \(\pm\) 0.06 & 2.65 \(\pm\) 0.28 & 1.21 \(\pm\) 0.52 & 0.31 \(\pm\) 0.05 & 3.75 \(\pm\) 2.51 & 14.99 \(\pm\) 1.88 & 0.21 \(\pm\) 0.08 & 56.45 \(\pm\) 20.84 \\ \hline
**BBDT** & 0.17 \(\pm\) 0.05 & 2.56 \(\pm\) 0.28 & 1.04 \(\pm\) 0.45 & 0.25 \(\pm\) 0.06 & 3.6 \(\pm\) 2.36 & 13.87 \(\pm\) 2.02 & 0.18 \(\pm\) 0.06 & 43.95 \(\pm\) 14.22 \\ \hline
**PRED** & 0.18 \(\pm\) 0.05 & 2.47 \(\pm\) 0.23 & 1.09 \(\pm\) 0.47 & 0.28 \(\pm\) 0.05 & 3.63 \(\pm\) 2.39 & 14.21 \(\pm\) 1.68 & 0.19 \(\pm\) 0.07 & 51.93 \(\pm\) 19.76 \\ \hline
**DRAG** & 0.18 \(\pm\) 0.05 & 2.63 \(\pm\) 0.37 & 1.07 \(\pm\) 0.46 & 0.26 \(\pm\) 0.06 & 3.79 \(\pm\) 2.44 & 14.29 \(\pm\) 1.88 & 0.18 \(\pm\) 0.06 & 44.68 \(\pm\) 14.04 \\ \hline
**Sspaheti** & 0.15 \(\pm\) 0.04 & 1.87 \(\pm\) 0.19 & 0.78 \(\pm\) 0.34 & 0.18 \(\pm\) 0.05 & 2.59 \(\pm\) 1.71 & 10.45 \(\pm\) 1.44 & 10.46 \(\pm\) 0.06 & 39.59 \(\pm\) 12.28 \\ \hline
**SBLA** & 0.39 \(\pm\) 0.1 & 5.41 \(\pm\) 0.47 & 2.69 \(\pm\) 0.73 & 0.64 \(\pm\) 0.17 & 8.76 \(\pm\) 3.65 & 38.42 \(\pm\) 4.77 & 0.47 \(\pm\) 0.13 & 112.2 \(\pm\) 28.26 \\ \hline
**RSTS** & 0.24 \(\pm\) 0.08 & 2.97 \(\pm\) 0.38 & 1.3 \(\pm\) 0.51 & 0.33 \(\pm\) 0.08 & 4.01 \(\pm\) 2.75 & 16.65 \(\pm\) 2.48 & 0.24 \(\pm\) 0.09 & 80.34 \(\pm\) 23.69 \\ \hline
**BRTS** & 0.07 \(\pm\) 0.04 & 0.72 \(\pm\) 0.13 & 0.37 \(\pm\) 0.34 & 0.04 \(\pm\) 0.02 & 0.74 \(\pm\) 0.45 & 3.97 \(\pm\) 0.77 & 0.07 \(\pm\) 0.01 & 32.83 \(\pm\) 10.59 \\ \hline
**BMRS** & 0.09 \(\pm\) 0.05 & 0.71 \(\pm\) 0.13 & 0.43 \(\pm\) 0.34 & 0.05 \(\pm\) 0.02 & 0.76 \(\pm\) 0.46 & 4.01 \(\pm\) 0.79 & 0.09 \(\pm\) 0.02 & 35.97 \(\pm\) 11.45 \\ \hline
**Proposed** & 0.15 \(\pm\) 0.05 & 1.29 \(\pm\) 0.21 & 0.55 \(\pm\) 0.26 & 0.13 \(\pm\) 0.07 & 1.55 \(\pm\) 1.23 & 8.36 \(\pm\) 1.67 & 0.14 \(\pm\) 0.05 & 69.13 \(\pm\) 23.38 \\ \hline \hline \end{tabular}
\end{table} 
Table 4: Average execution time per image (milliseconds) against the tested CCL algorithms without memory allocation overhead. \begin{table}
\begin{tabular}{c c c c c c c c c} \hline \hline \multirow{2}{*}{**MethodDataset**} & \multirow{2}{*}{**Fingerprints**} & \multirow{2}{*}{**Hamlet**} & \multirow{2}{*}{**Medical**} & \multirow{2}{*}{**3 dpes**} & \multirow{2}{*}{**Tobacco**} & \multirow{2}{*}{**xDocs**} & \multirow{2}{*}{**Mifflickr**} & \multirow{2}{*}{**Synthetic**} \\ \hline
**NULL** & 0.03 \(\pm\) 0.01 & 1.19 \(\pm\) 0.13 & 0.55 \(\pm\) 0.11 & 0.3 \(\pm\) 0.04 & 1.93 \(\pm\) 1.18 & 6.4 \(\pm\) 1.31 & 0.02 \(\pm\) 0.01 & 6.54 \(\pm\) 0.50 \\ \hline
**SAUF** & 0.22 \(\pm\) 0.08 & 3.92 \(\pm\) 0.33 & 1.78 \(\pm\) 0.77 & 0.49 \(\pm\) 0.06 & 5.61 \(\pm\) 3.57 & 20.55 \(\pm\) 2.65 & 0.23 \(\pm\) 0.08 & 62.04 \(\pm\) 20.94 \\ \hline
**BBDT** & 0.2 \(\pm\) 0.08 & 3.82 \(\pm\) 0.34 & 1.62 \(\pm\) 0.71 & 0.44 \(\pm\) 0.07 & 5.45 \(\pm\) 3.32 & 19.42 \(\pm\) 2.80 & 0.20 \(\pm\) 0.07 & 49.54 \(\pm\) 14.43 \\ \hline
**PRED** & 0.21 \(\pm\) 0.08 & 3.7 \(\pm\) 0.30 & 1.68 \(\pm\for each image, the memory does not vary that much after the first steps. The results are given in Table 5.

Similarly, for each algorithm, we were also interested in how many times they access the memory in total, since the fewer memory accesses required, the faster an algorithm will tend to perform, in theory. The results of these tests are given in Table 6. One thing to note is that the RBTS algorithm is missing from both of these tables because it does not have a memory test implementation in YACCLAB.