Parallel algorithm of region labeling based on run-length coding

Computer Engineering and Applications ›› 2008, Vol. 44 ›› Issue (16): 49-50.

• 理论研究 • Previous Articles Next Articles

Parallel algorithm of region labeling based on run-length coding

LU Ke-zhong¹,DING Feng-xia²,SUN Hong-yuan³,LIN Xiao-hui²

1.SuperComputing Center，Shenzhen University，Shenzhen，Guangdong 518060，China
2.College of Information Engineering，Shenzhen University，Shenzhen，Guangdong 518060，China
3.ATR Lab，Shenzhen University，Shenzhen，Guangdong 518060，China

Received:2007-09-10 Revised:2008-12-17 Online:2008-06-01 Published:2008-06-01
Contact: LU Ke-zhong

一种基于游程码的并行区域标记算法

陆克中¹,丁凤霞²,孙宏元³,林晓辉²

1.深圳大学超级计算中心，广东深圳 518060
2.深圳大学信息工程学院，广东深圳 518060
3.深圳大学 ATR实验室，广东深圳 518060

通讯作者: 陆克中

Abstract

Abstract: Region labeling is a usual way in image processing.In order to satisfy the real-time request of image processing，a parallel algorithm of region labeling based on run-length coding was proposed.The algorithm adopted strip mode to partition image.First each computing node executed local labeling on sub-image based on run-length coding.Then managing process completed global labeling by computing connectivity of run-length coding of sub-image boundary.Experiments show that the algorithm has right result，good performance，high efficiency and approximately linear speed-up ratio.

Key words: binary image, region labeling, parallel algorithm, run-length coding, real-time image processing

摘要： 区域标记是图像处理中常用的方法，为了满足实时图像处理要求，提出了一种基于游程码的并行区域标记算法.该算法采用带状方式划分子图，各计算节点先通过基于游程码的方法对子图进行本地标记，然后管理进程再通过计算子图边界游程码的连通关系完成全局标记.实验表明，该算法结果正确，性能较好，效率较高，具有近似于线性的加速比。

关键词: 二值图像, 区域标记, 并行算法, 游程码, 实时图像处理

LU Ke-zhong¹,DING Feng-xia²,SUN Hong-yuan³,LIN Xiao-hui². Parallel algorithm of region labeling based on run-length coding[J]. Computer Engineering and Applications, 2008, 44(16): 49-50.

陆克中¹,丁凤霞²,孙宏元³,林晓辉². 一种基于游程码的并行区域标记算法[J]. 计算机工程与应用, 2008, 44(16): 49-50.

[1]	YANG Jie, WU Suping. Parallel Algorithm for Point Cloud Reconstruction [J]. Computer Engineering and Applications, 2020, 56(6): 213-219.
[2]	ZHU Chao, WU Suping. Feature Point Detection DoG Parallel Algorithm [J]. Computer Engineering and Applications, 2020, 56(10): 36-43.
[3]	CEHN Yazhong1, LI Zhenjun1, LI Ronghua1, MAO Rui1, QIAO Shaojie2. Improved Graph Structure Clustering Algorithm by Using Parallel Strategy [J]. Computer Engineering and Applications, 2019, 55(1): 76-83.
[4]	WANG Dezheng1, ZHANG Yinong1, YANG Fan2. Implementation of parallel PLS algorithm of process monitoring using MapReduce [J]. Computer Engineering and Applications, 2018, 54(24): 61-65.
[5]	SHEN Xiajiong1，2, DUAN Xiaoyu2, YUAN Wanli2, HAN Daojun1，2. Research on circle detection algorithm based on connected region labeling algorithm [J]. Computer Engineering and Applications, 2018, 54(21): 95-98.
[6]	DUAN Suolin, ZHU Fang, YAN Xiang. Study of multi-window binarization algorithm for image processing [J]. Computer Engineering and Applications, 2017, 53(17): 212-217.
[7]	ZHAO Dandan, WANG Huabin, TAO Liang, ZHOU Jian. Improved EPTA parallel thinning algorithm [J]. Computer Engineering and Applications, 2016, 52(9): 196-201.
[8]	SUN Jinguang1, WU Suhong2. Collision detection algorithm based on ellipsoid bounding box and spatial decomposition [J]. Computer Engineering and Applications, 2016, 52(4): 217-222.
[9]	YU Jin1, ZHOU Haojie2, HAI Zhilei1. Dense optical flow parallel computing method based on mesh many-core architecture [J]. Computer Engineering and Applications, 2016, 52(16): 186-191.
[10]	LI Zhengfu1，2, WANG Xicheng3, LI Keqiu1, YAO Xiang3, DONG Yueli2. Information entropy multi-population genetic algorithm based on CUDA [J]. Computer Engineering and Applications, 2016, 52(1): 12-16.
[11]	ZHOU Leqian, GUO Siyu, WEN He, ZHANG Yi. Improved algorithm of large structural elements basic binary morphological operations [J]. Computer Engineering and Applications, 2016, 52(1): 190-194.
[12]	FENG Haiwen1，2, NIU Lianqiang1, LIU Xiaoming2. Efficient one-scan algorithm for labeling connected component [J]. Computer Engineering and Applications, 2014, 50(23): 31-35.
[13]	ZHUANG Caiyun, XIONG Ping. 2D image skeleton generation based on approximate minimum distance field [J]. Computer Engineering and Applications, 2013, 49(21): 164-167.
[14]	CHENG Qi, WEN Jianguo, YANG Dong. New area segmentation method for remote sensing binary image [J]. Computer Engineering and Applications, 2013, 49(20): 202-205.
[15]	GUO Shichao, Kamil·MOYDI. Uyghur handwriting edge extraction algorithm and feature extraction research [J]. Computer Engineering and Applications, 2013, 49(15): 162-166.

Parallel algorithm of region labeling based on run-length coding

一种基于游程码的并行区域标记算法

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics