基于Max-tree的连通区域标记新算法(电子科技大学计算机科学与工程学院计算智能实验室，四川成都610054）摘要：采用灰度图像创建Maxtree的基本思想，提出一种新的二值图像连通区域标记算法。该算法主要采用8邻域搜索及排序队列方式实现，通过一次扫描二值图像即可完成连通区域标记。提出一种新的8邻域搜索策略，可以将邻域搜索次数由八次减少到平均四次以下，从而提高了系统效率。此外，还给出一种排序队列的快速实现方法，并将其应用到标记算法中。而且，该算法的运行时间仅与待标记图像的大小有关，与连通区数目和图像内容无关。该算法已应用于海藻图像识别，实验结果表明该算法是快速、高效的。??关键词：Maxtree；连通区域标记；8邻域搜索；排序队列??中图法分类号：TP391文献标识码：A：10013695(2006)08016803??ConnectedComponentLabelingAlgorithmBasedonMaxtree??ZHANGDewei，PUXiaorong，ZHANGYi(ComputationalIntelligenceLaboratory,CollegeofComputerScienceEngineering,UESTofChina,ChengduSichuan610054,China)Abstract:BasedonthetheoryofMaxtree,anewconnectedcomponentlabelingalgorithmisproposedinthispaper.Theproposedalgorithmcanlabeltheconnectedcomponentsbyscanningthebinaryimageontime.Byimprovingthetraditionalalgorithmof8NeighborSearching,theaverageNeighborSearchingcanbereducedfromeighttofour.Anefficientimplementationoforderedqueueisalsointroducedinthispaper.Theexperimentsondiatomimagesidentificationhavebeendonetotesttheperformanceoftheproposedalgorithm,whichshowthatthenewalgorithmhasbetterperformancethanthetraditionalones.??Keywords:Maxtree;ConnectedComponentLabeling;8NeighborSearching;OrderedQueue?お?二值图像指仅包含背景像素和目标像素的数字图像；二值图像连通区域标记指将图像中符合某种连通规则的目标像素点用相同的标号表示出来。通常使用的连通规则包括4邻域连通或8邻域连通两种。其中，后者的应用更广泛。在模式识别等许多图像处理应用中，灰度图像经过预处理转变为二值图像以后，常常需要对不同的连通区域（即目标）进行标记，以便单独分析每一个目标的特征[11～13]。此外，二值图像标记算法本身也可以作为图像预处理步骤，为后续处理提供依据[1]。??到目前为止，先后研究出了许多二值图像连通区域标记方法。这些方法大致可以分为以下几类：??(1)两次扫描法[2]。第一次扫描时，将临时标号存储在一个与图像大小一样的二维数组中并形成等价对。扫描结束时，通过某种搜索方法合并等价标号；第二次扫描时，用等价标---本文来源于网络，仅供参考，勿照抄，如有侵权请联系删除---号中最小的标号值赋予所有等价标号对应的像素点。??(2)双向反复扫描法[3]。第一次扫描时，将每个目标像素点标记为一个唯一的标号。然后，通过正向和反向反复扫描标号图像，并在每个像素的邻域内传播最小标号，直到没有标号变化时为止。??(3)区域增长法[4]。依次扫描二值图像的每一个像素点。当找到某个未标记的目标像素点时，将其压入堆栈并从该点开始反复标记其邻域，直到堆栈为空。??(4)此外，还有基于二值图像特殊表示方法的标记算法，如基于跑长码表示[14]、基于游程表示[15]、基于四叉树表示[5]等标记方法，以及专用于特殊体系结构的计算机的并行标记算法[6]等。??本文基于Maxtree的思想，提出一种快速连通区域标记方法。该方法通过一次扫描二值图像即可完成连通区域标记，且处理过程中不需要真正创建Maxtree，使得算法简单有效。为了减少邻域比较次数，本文还提出一种新的8邻域搜索策略，可以将邻域搜索次数由八次减少到平均四次以下，大大提高了搜索效率。此外，本文还给出了标记方法及搜索策略的一种快速实现。??1连通区域标记??1.1Maxtree??由Salembier等人提出的Maxtree数据结构被认为是一种万能的图像表示方法，并且已被成功地应用到计算机视觉等方面的许多经典问题中，如图像滤波和分割、信息获取等[7，8]。??灰度图像的Maxtree是一棵有根的树，数的深度为图像的灰度等级。对于二值图像，...