首页 | 本学科首页   官方微博 | 高级检索  
     


Parallel Light Speed Labeling: an efficient connected component algorithm for labeling and analysis on multi-core processors
Authors:Laurent Cabaret  Lionel Lacassagne  Daniel Etiemble
Affiliation:1.Laboratoire de Recherche en Informatique (LRI),Univ. Paris-Sud, CNRS UMR 8623,Orsay,France;2.Sorbonne Universites,UPMC Univ Paris 06, CNRS UMR 7606,Paris,France
Abstract:In the last decade, many papers have been published to present sequential connected component labeling (CCL) algorithms. As modern processors are multi-core and tend to many cores, designing a CCL algorithm should address parallelism and multithreading. After a review of sequential CCL algorithms and a study of their variations, this paper presents the parallel version of the Light Speed Labeling for connected component analysis (CCA) and compares it to our parallelized implementations of State-of-the-Art sequential algorithms. We provide some benchmarks that help to figure out the intrinsic differences between these parallel algorithms. We show that thanks to its run-based processing, the LSL is intrinsically more efficient and faster than all pixel-based algorithms. We show also, that all the pixel-based are memory-bound on multi-socket machines and so are inefficient and do not scale, whereas LSL, thanks to its RLE compression can scale on such high-end machines. On a 4 × 15-core machine, and for 8192 × 8192 images, LSL outperforms its best competitor by a factor ×10.8 and achieves a throughput of 42.4 gigapixel labeled per second.
Keywords:
本文献已被 SpringerLink 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号