# A Novel Connected-Components Algorithm for 2D Binarized Images
## 2 Materials and Methods
### Run-Length Generation Process  
As previously introduced, RLE is a technique used to represent sequences of consecutive identical values. In the context of binary images, RLE identifies continuous horizontal sequences of black pixels (foreground pixels, value 1) and encodes them as run segments. Each run is characterized by a starting coordinate, an ending coordinate, and the row index: \(\mathrm{R}(\mathrm{x}_{\mathrm{s}},\mathrm{x}_{\mathrm{e}},\mathrm{y})\) represents a continuous sequence of black pixels starting at position \(\mathrm{x}_{\mathrm{s}}\), ending at \(\mathrm{x}_{\mathrm{e}}\), and located in row \(\mathrm{y}\). In the following algorithms, \(\mathrm{x}_{\mathrm{s}}\) is dentoted as \(run.start\), \(x_{\mathrm{e}}\) as \(run.end\), and \(y\) as \(run.row\). Mathematically, a run \(\mathrm{R}_{\mathrm{i}}\) is defined as \(\mathrm{R}_{\mathrm{i}}\)\(=(\mathrm{x}_{\mathrm{si}},\mathrm{x}_{\mathrm{ei}},\mathrm{y}_{\mathrm{i}})\), where \(\mathrm{I}(\mathrm{x},\mathrm{y})=1\) for \(\mathrm{x}\in[\mathrm{x}_{\mathrm{si}},\mathrm{x}_{\mathrm{ei}}]\) and \(\mathrm{I}(\mathrm{x}_{\mathrm{s}}-1,\mathrm{y})=\mathrm{I}(\mathrm{x}_{ \mathrm{e}}+1,\mathrm{y})=0\). In our case, unlike traditional RLE-based CCL algorithms, which process image pixels one at a time, our algorithm pre-caches a precomputed lookup table used to extract runs from words that represent binary pixels. Each row gets interpreted in sequences of 16-bit integers, where each bit encodes a pixel. This step allows for rapid segmentation of rows by simply looking up segment patterns and offsetting them accordingly. In order to achieve this, we construct a CacheSegment table, obtained after executing a one-time preprocessing phase. All 65,536 possible 16-bit values get scanned and, for each one, the positions of 0-bit runs are identified and stored as initial one-pixel segments. This result is then further refined by a second pass, which merges adjacent or overlapping segments into possible RLEs. It is important to mention that since this table caches all possible 16-bit runs that could be identified in an image, it only needs to be computed once on program startup. This merging is implemented as a linear scan through the generated segments, performed in reverse. If any pair of consecutive segments is found where the end of the first would touch the start of the second, they are merged in place by adjusting segment boundaries. The segment list is then memory-shifted in place in order to remove the redundant entry. These steps ensure a compact lookup table that stores only valid horizontal runs for each 16-bit word. The steps for this method can be seen in Algorithm 1. ```
Input: None Output: CacheSegments--map of 16 bits to horizontal runs
1. For wordValue \(\leftarrow\) 0:65,535
2. Segments \(\leftarrow\) empty list
3. For i \(\leftarrow\) 0 to 15 do
4. If wordValue[i] = 1
5. start \(\leftarrow\) i
6. end \(\leftarrow\) i
7. Segments.append((start, end))
8. i \(\leftarrow\) size(Segments) \(-\) 2
9. While i \(\geq\) 0
10. If Segments[i].end + 1 \(\geq\) Segments[i + 1].start
11. Segments[i].end \(\leftarrow\) Segments[i + 1].end
12. Remove Segments[i + 1] by shifting the remaining entries left
13. Decrease size(Segments)
14. Else
15. i \(\leftarrow\) i - 1
16. CacheSegments[wordValue] \(\leftarrow\) Segments
```  
**Algorithm 1** Precompute Segment Caching AlgorithmFollowing the CacheSegments creation, we proceed to extract RLE from the image rows by looking at the pixels in a row in 16-bit increments. This can be seen in Algorithm 2. ```
Input: Binary Image Output: List or row-wise RLE segments
1. For row \(\leftarrow\) 0:height-1
2. imageRow \(\leftarrow\) image[row]
3. RowSegments \(\leftarrow\) empty list
4. imageWidthWords \(\leftarrow\) width/16
5. For i \(\leftarrow\) 0:imageWidthWords-1
6. word \(\leftarrow\) imageRow[i]
7. Segments \(\leftarrow\) CacheSegments[i]
8. For each segment in Segments
9. start\(\leftarrow\) 16\(\times\)i + segment.start
10. end\(\leftarrow\) 16\(\times\)i + segment.end
11.