# A Novel Connected-Components Algorithm for 2D Binarized Images
## 2 Materials and Methods
### Merging Connected Components Across Rows  
Once all runs have been extracted and stored in the run vector, adjacent rows are scanned pairwise to merge connected runs based on 4-way or 8-way connectivity rules.  
To determine whether two runs \(\text{R}_{\text{i}}(\text{x}_{\text{si}},\text{x}_{\text{ei}},\text{y}_{\text{ j}})\) and \(\text{R}_{\text{j}}\left(\text{x}_{\text{si}},\text{x}_{\text{ej}},\text{y}_{ \text{j}}\right)\) belong to the same connected component, the following conditions are checked:  
* For 4-way connectivity: \(\text{R}_{\text{i}}\) and \(\text{R}_{\text{j}}\) are connected if they overlap horizontally and are located in consecutive rows, meaning \(\text{x}_{\text{si}}\leq\text{x}_{\text{ei}}\) and \(\text{x}_{\text{si}}\leq\text{x}_{\text{ej}}\) for \(\text{y}_{\text{j}}=\text{y}_{\text{i}}+1\).
* For 8-way connectivity: \(\text{R}_{\text{i}}\) and \(\text{R}_{\text{j}}\) are connected if they satisfy 4-way connectivity or are diagonally adjacent, meaning \(\left|\text{x}_{\text{si}}-\text{x}_{\text{ei}}\right|\leq\text{1}\) or \(\left|\text{x}_{\text{si}}-\text{x}_{\text{ej}}\right|\leq\text{1}\) for \(\text{y}_{\text{j}}=\text{y}_{\text{i}}+1\).  
If two runs \(\text{R}_{\text{i}}\) and \(\text{R}_{\text{j}}\) satisfy the connectivity condition, their corresponding nodes \(\text{N}_{\text{i}}\) and \(\text{N}_{\text{j}}\) are merged using the strategy presented in Algorithm 3. This merging strategy  
\begin{table}
\begin{tabular}{c c c c} \hline \hline
**Element** & **Description** & **Notation** & **Initial Value** \\ \hline Run & A reference to its own run & \(N_{i}\),_run_ & \(R_{i}\) \\ \hline Head & A pointer to the first run in the component & \(N_{i}\),_head_ & \(N_{i}\) \\ \hline Next & A pointer to the next run within the same component & \(N_{i}\),_next_ & NULL \\ \hline Size & A counter indicating the number of runs in the component & \(N_{i}\),_size_ & 1 \\ \hline Label & A number indicating the label of the component & \(N_{i}\),_label_ & NULL \\ \hline \hline \end{tabular}
\end{table}
Table 1: Run-node elements.  
ensures efficient union operations, leveraging the union by size heuristic to maintain a balanced component structure. Something to note is that we create two separate lists that are intended to keep track of the start and end segments for each row, allowing us to iterate faster over rows, by either skipping empty rows or determining quickly if there are no more segments on the current one.  
```
Input: List of RLE segments Output: List of connected components
```
1. rowStart, rowEnd \(\leftarrow\) List(totalRows,null)
2. connectivity \(\leftarrow\) 1 if 8-connected else 0
3. For each segment in RowSegments:
4. If rowStart[segment.row] = null
5. rowStart[segment.row] = segment
6. rowEnd[segment.row] = segment
7. For row = 1:totalRows
8. If current row or previous row has no segments
9. skip
10. curr\(\leftarrow\)rowStart[row]
11. currEnd\(\leftarrow\)rowEnd[row-1]
12. upper\(\leftarrow\)rowStart[row-1]
13. upperEnd\(\leftarrow\)rowEnd[row-1]
14. While curr = currEnd AND upper! = upperEnd
15. If curr.run.end + connectivity < upper.run.start
16. curr\(\leftarrow\)curr+1
17. Else If curr.run.start - connectivity > upper.run.end
18. upper\(\leftarrow\)upper+1
19. Else
20. If curr.head! = upper.head
21. If curr.head.size > upper.head.size
22. Swap(curr,upper)
23. upperhead.size \(\leftarrow\) upper.head.size + curr.head.size
24. For(walk\(\leftarrow\)curr.head;walk.next! = null;walk \(\leftarrow\) walk.next)
25. walk.head \(\leftarrow\) upper.head
26. walk.head \(\leftarrow\) upper.head
27. walk.next \(\leftarrow\) upper.head.next
28. upper.head.next\(\leftarrow\)current.head
29. If curr.run.end + connectivity < upper.run.end
30. curr\(\leftarrow\)curr + 1
31. Else
32. upper\(\leftarrow\)upper + 1 ```
**Algorithm 3**Merge Strategy Pseudocode