极大树及其区域填充算法  

Maximum Tree and its Area-filling Algorithm

作　　者：邹昌伟[1] 吴献[1] 王建文[1] 

机构地区：[1]福建师范大学软件学院,福州350108

出　　处：《小型微型计算机系统》2012年第3期637-640,共4页Journal of Chinese Computer Systems

基　　金：福建省教育厅B类科技项目(JB09053)资助

摘　　要：分析了经典扫描线种子算法及其各种改进算法的发展规律,指出这些算法因只在相邻两条区段间进行比较而存在不必要重复判读.通过建立极大树的概念,将相邻多条区段作为一个有机整体来处理以减少判读次数,把相邻3条区段的长度关系分成九类,并引入确定的有限自动机来减少比较次数,给出了极大树区域填充算法和实验对比,结果表明此算法可较大提高填充效率.This paper analyzes the evolution rule from the traditional scan-line filling algorithm to its enhanced ones,points out that there are redundant reading operations in these algorithms which are due to the two-scan-line only comparision.To save more context information,this paper creates a new concept called maximum tree which considers maximum adjacent scan lines together as an integral whole in order to reduce reading operations,classifies their length relations into nine different cases,introduces a deterministic finite automata to reduce comparisions,proposes the maximum-tree filling algorithm.At last,this paper compares the efficiency of different algorithms and shows that the new one is enhanced considerably.

关 键 词：区域填充 扫描线算法 种子填充 极大树 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]