The high-level strategy of our connected components algorithm uses the well-known divide and conquer technique. Divide and conquer algorithms typically use a recursive strategy to split problems into smaller subproblems, and, given the solutions to these subproblems, merge the results into the final solution. It is common to have either an easy splitting algorithm and a more complicated merging, or vice versa, a hard splitting, following by easy merging. In our parallel connected components algorithm, the splitting phase is trivial and implicit, while the merging process requires more work.
Each processor holds a unique tile of the image, and hence can find
the initial connected components of its tile by using a standard
sequential algorithm based upon breadth-first search. Next, the
algorithm iterates 
times
, alternating between combining the tiles in
horizontal merges of vertical borders and vertical merges
of horizontal borders, with the number of horizontal merges equal to
and the number of vertical merges equal to 
, since
. Our algorithm uses novel
techniques to perform the merges and to update the labels. We start
by describing the initial sequential connected components algorithm.