Ghent University Academic Bibliography

Advanced

Fast and memory efficient 2-D connected components using linked lists of line segments

Johan De Bock and Wilfried Philips UGent (2010) IEEE TRANSACTIONS ON IMAGE PROCESSING. 19(12). p.3222-3231
abstract
In this paper we present a more efficient approach to the problem of finding the connected components in binary images. In conventional connected components algorithms, the main data structure to compute and store the connected components is the region label image. We replace the region label image with a singly-linked list of line segments (or runs) for each region. This enables us to design a very fast and memory efficient connected components algorithm. Most conventional algorithms require (at least) two raster scans. Those that only need one raster scan, require irregular and unbounded image access. The proposed algorithm is a single pass regular access algorithm and only requires access to the three most recently processed image lines at any given time. Experimental results demonstrate that our algorithm is considerably faster than the fastest conventional algorithm. Additionally, our novel region coding data structure uses much less memory in typical cases than the traditional region label image. Even in worst case situations the processing time of our algorithm is linear with the number of pixels in an image.
Please use this url to cite or link to this publication:
author
organization
year
type
journalArticle (original)
publication status
published
subject
keyword
linked lists, linear worst case time, memory efficient, Connected components, OPERATIONS, LABELING ALGORITHM
journal title
IEEE TRANSACTIONS ON IMAGE PROCESSING
IEEE Trans. Image Process.
volume
19
issue
12
pages
3222 - 3231
Web of Science type
Article
Web of Science id
000284362400012
JCR category
ENGINEERING, ELECTRICAL & ELECTRONIC
JCR impact factor
2.606 (2010)
JCR rank
20/247 (2010)
JCR quartile
1 (2010)
ISSN
1057-7149
DOI
10.1109/TIP.2010.2052826
language
English
UGent publication?
yes
classification
A1
copyright statement
I have transferred the copyright for this publication to the publisher
id
1074605
handle
http://hdl.handle.net/1854/LU-1074605
date created
2010-11-16 13:47:32
date last changed
2016-12-19 15:45:11
@article{1074605,
  abstract     = {In this paper we present a more efficient approach to the problem of finding the connected components in binary images. In conventional connected components algorithms, the main data structure to compute and store the connected components is the region label image. We replace the region label image with a singly-linked list of line segments (or runs) for each region. This enables us to design a very fast and memory efficient connected components algorithm. Most conventional algorithms require (at least) two raster scans. Those that only need one raster scan, require irregular and unbounded image access. The proposed algorithm is a single pass regular access algorithm and only requires access to the three most recently processed image lines at any given time. Experimental results demonstrate that our algorithm is considerably faster than the fastest conventional algorithm. Additionally, our novel region coding data structure uses much less memory in typical cases than the traditional region label image. Even in worst case situations the processing time of our algorithm is linear with the number of pixels in an image.},
  author       = {De Bock, Johan and Philips, Wilfried},
  issn         = {1057-7149},
  journal      = {IEEE TRANSACTIONS ON IMAGE PROCESSING},
  keyword      = {linked lists,linear worst case time,memory efficient,Connected components,OPERATIONS,LABELING ALGORITHM},
  language     = {eng},
  number       = {12},
  pages        = {3222--3231},
  title        = {Fast and memory efficient 2-D connected components using linked lists of line segments},
  url          = {http://dx.doi.org/10.1109/TIP.2010.2052826},
  volume       = {19},
  year         = {2010},
}

Chicago
De Bock, Johan, and Wilfried Philips. 2010. “Fast and Memory Efficient 2-D Connected Components Using Linked Lists of Line Segments.” Ieee Transactions on Image Processing 19 (12): 3222–3231.
APA
De Bock, Johan, & Philips, W. (2010). Fast and memory efficient 2-D connected components using linked lists of line segments. IEEE TRANSACTIONS ON IMAGE PROCESSING, 19(12), 3222–3231.
Vancouver
1.
De Bock J, Philips W. Fast and memory efficient 2-D connected components using linked lists of line segments. IEEE TRANSACTIONS ON IMAGE PROCESSING. 2010;19(12):3222–31.
MLA
De Bock, Johan, and Wilfried Philips. “Fast and Memory Efficient 2-D Connected Components Using Linked Lists of Line Segments.” IEEE TRANSACTIONS ON IMAGE PROCESSING 19.12 (2010): 3222–3231. Print.