计算机工程 ›› 2010, Vol. 36 ›› Issue (9): 17-19,2.doi: 10.3969/j.issn.1000-3428.2010.09.006

• 博士论文 • 上一篇    下一篇

一种串行/并行两用的区域标记算法

胡 涛1,郭宝平2,郭 轩1,杨 欧1   

  1. (1. 华中科技大学光电子科学与工程学院,武汉 430074;2. 深圳大学光电子学研究所,深圳 518060)
  • 收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2010-05-05 发布日期:2010-05-05

Serial/Parallel Algorithm for Region Labeling

HU Tao1, GUO Bao-ping2, GUO Xuan1, YANG Ou1   

  1. (1. College of Optoelectronics Science and Engineering, Huazhong University of Science and Technology, Wuhan 430074; 2. Optoelectronics Institute, Shenzhen University, Shenzhen 518060)
  • Received:1900-01-01 Revised:1900-01-01 Online:2010-05-05 Published:2010-05-05

摘要: 通过设计一种游程与目标体间接关联的数据结构实现游程标记冲突的实时解决,提出一种基于游程的顺序扫描式区域标记算法,只需一次扫描分析即可获取游程区域表达,复杂度低,编码实现方便,易于扩展应用于并行计算系统中进行并行标记。实验结果表明,该算法与已有算法相比,拥有更高效的串行标记性能,在进行并行标记时具有近似线性的加速比。

关键词: 区域标记, 游程, 目标体索引, 目标体双重索引, 并行标记, 加速比

Abstract: By designing a structure of run-length associated indirectly with object to solve the problem of run-length labeling conflict in real time, an efficient run-length based and raster-scanned region labeling algorithm is proposed, which can acquire the run-length region representation by only one scan. The algorithm owns low complexity for easy implementation, and can be easily extended to implement parallel labeling in parallel computing system. Experimental results show that the algorithm is more efficient than other algorithms in serial labeling, and gains approximate linear speedup ratio in parallel labeling.

Key words: region labeling, run-length, object index, object dual index, parallel labeling, speedup ratio

中图分类号: