A run equivalence algorithm for parallel connected component labeling on CPU
Yury S. Bekhtin, Victor S. Gurov, Sergey S. Zavalishin · 2015
It is proposed a new algorithm for parallel connected component labeling which applies labels to image runs. The algorithm is designed to efficiently label a text document with a large number of characters inside. In contrast to the existing parallel labeling algorithms, our method benefits from modern CPU architectures; it is designed to operate on image runs, not pixels, which make it possible to minimize a number of memory read-write operations. Each CPU core processes a bunch of runs, aligned by rows, that has a positive impact to CPU and memory cache utilization. The results of modeling have shown that our algorithm demonstrates better performance than existing CPU-based connected component labeling algorithms. Moreover, the developed algorithm also demonstrates a good scalability across different numbers of CPU cores.