DocumentCode
3063800
Title
Finding connected components in digital images
Author
Khanna, Vikrant ; Gupta, P. ; Hwang, C.J.
Author_Institution
Dept. of Comput. Sci. & Eng., Indian Inst. of Technol., Kanpur, India
fYear
2001
fDate
36982
Firstpage
652
Lastpage
656
Abstract
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×N image. It is also shown that the maintenance of the table has an overall linear amortized cost
Keywords
computational complexity; image processing; spatial data structures; 2D digital images; aggressive label reuse; connected component labelling algorithm; data structure; equivalence table maintenance; equivalence table size; linear amortized cost; lower bound; union-find algorithms; Application software; Computer science; Computer vision; Costs; Data structures; Digital images; Image processing; Maintenance engineering; Pixel;
fLanguage
English
Publisher
ieee
Conference_Titel
Information Technology: Coding and Computing, 2001. Proceedings. International Conference on
Conference_Location
Las Vegas, NV
Print_ISBN
0-7695-1062-0
Type
conf
DOI
10.1109/ITCC.2001.918871
Filename
918871
Link To Document