The initialization consists of entirely local operations on each
processor. Pixels on each tile are examined in row-major order
fashion. If a pixel is an unmarked, colored pixel, a breadth-first
search procedure starting at that pixel labels all connected
like-colored pixels within that tile with a globally unique label.
When a pixel is visited in the labeling procedure, it becomes marked.
During the initial row-major order search, for 8-connectivity, only
the four pixels to the right, below-left, below, and below-right, need
to be examined for connectivity. For 4-connectivity, only the pixels
to the right and below need to be examined. This sequential connected
components algorithm runs in
O
where |V| is the number of vertices, and |E| is the
number of edges searched. Since 
, this algorithm runs
in 
time. The result is an array of positive integers
corresponding to the unique label values of the connected components
in the subimage.
The initial labeling of each pixel with local offset 
in the
processor with logical grid position 
will be 
. This labeling ensures that each processor will obtain
unique labelings across the subimages after running the sequential
connected components step, without having to do any communication
among the processors. Thus, the initialization step runs in
