一个基于线性四元树的连通标记算法

AN ALGORITHM FOR CONNECTED COMPONENT LABELING BASED ON LINEAR QUADTREES

摘要: 图象的四元树表示提供了有效地节省图象存储空间及快速地实施图象处理的方法，而利用四元树实现图象的连通标记则是图象处理、图象分析及计算机图形学中最基本的操作之一．文献〔1〕和〔2〕分别给出了基于指针四元树和线性四元树的图象连通标记算法．本文提出了一个新的基于线性四元树（Linear Quadtree，简称 LQT）的连通标记算法 CCL（T，N）（Connected Component Labeling），其算法平均时间复杂度与前两个算法相同，均为O（N·logN），但其实用效率及通用性均优于前两者．

Abstract: Quadtree representation of an image provides a method of saving stcrages effectively and performing image processing quickly,while connected component labelingis one of the most basic operations in image processing,image analysis and computergraphics.Reference〔1〕and〔2〕had proposed an algorithm for connected component labeling of an image based on pointer quadtree and linear quadtrce (LQT,for short)respectively.In this paper,we propose a new algorithm for connected component labeling(CCL,for short) based on linear quadtree.This algorithm has thesame average time complexity (O(N·log N)) as that of〔1〕and〔2〕,but its efficiency and generality are better than that of〔1〕and〔2〕.