Finding connected components in digital images
Vivek Khanna, P. Gupta, C. Jinshong Hwang · 2002
An efficient algorithm is presented to label the connected components in an array representation of 2D images. A new data structure is suggested to maintain the equivalence table that makes use of a modified version of union-find algorithms. The operations supported by the equivalence table enable aggressive reuse of labels and (lower) bound the size of the table to [N/2]+1 for an N/spl times/N image. It is also shown that the maintenance of the table has an overall linear amortized cost.