一种新的快速复杂连通区域扫描线填充算法
一种新的快速复杂连通区域扫描线填充算法
张志龙
李吉成
沈振康
!国防科技大学电子科学与工程学院/01国家重点实验室"长沙#&""2%#
3,4567$895:;8967<:;&%=&.%$><4
摘
要
提出一种快速求取扫描线与轮廓线交点的算法"只需遍历!次轮廓线即可求得所有交点"显著降低了算法复杂
度$基于该求交算法得到的扫描线填充算法"可以填充任意的复杂连通区域$与同类算法+!"#"*)相比"该文算法流程简单"填充速度快$关键词
计算机图像学
轮廓
区域
区域填充
扫描线填充
中图分类号0?%@&%A!%*
文章编号&""!,-%%&,!!""#%%&,""".,"%文献标识码/
!"#$%&’()*&+,-+#%-..-+/!./01-(23401
5036.-*&(#750++#*(-+/8#/-0+
92&+/92-.0+/,-:-*2#+/)2#+92#+;&+/
&/01B5C$"37D>EF<:6>G>6D:>D5:H3:;6:DDF6:;I<77D;D"J5E6<:57K:6LDFM6EN<O
PDOD:>D0D>9:<7<;N"I95:;M95#&""2%’
<=’(1&*($
Q:E96MR5RDF"5O5ME57;<F6E946MRFDMD:EDHE<5>ST6FDE9D>F<MMR<6:EMCDEUDD:E9DM>5:76:D5:HE9D
><:E<TFM$QE:DDHMF5:M5>V6:;E9D><:E<TFR<6:EM<:7NEU<E64DME<5>ST6FD577E9D>F<MMR<6:EM"U96>9M576D:E7NFDHT>DE9D><4R7DW6EN$X5MDH<:E9DO5ME>F<MMR<6:E5>ST6F6:;57;<F6E94"5:DUM>5:76:DO6776:;57;<F6E946MD5M67N<CE56:DHE95E>5:CDTMDHE<O6775:N><4R7DW><::D>E6:;FD;6<:M$I<4R5FDHU6E957;<F6E94MRFDMD:EDH6:’!"#"*)"E9DM>5:76:DO6776:;57;<F6E9495MMT>95HL5:E5;DM5MM64R76>6EN5:HMRDDH6:DMM$
>#?$017’$><4RTEDF;F5R96>M"><:E<TF"FD;6<:"FD;6<:O6776:;"M>5:76:DO6776:;
&引言
将区域的边界表示转换为区域内部象素表示的过程称为
论文基于多边形扫描线填充算法的基本原理"通过分析水平扫描线与复杂连通区域轮廓线相交的各种可能情况"给出了一种求取扫描线与轮廓线交点的新方法"可以快速求取交点!在此基础上"论文提出了一种任意形状复杂连通区域的快速扫描线填充算法!该算法与文献’!"#"*)中介绍的算法相比具有遍历轮廓线次数少#逻辑规则简单#求交速度快#配对填充准确等优点"对#,连通区域和-,连通区域的填充均能适用!
区域填充!区域填充是计算机图形学中的一个基本问题"在计算机辅助设计#真实感图形显示#图像分析等领域有着广泛的应用!完成区域填充的算法总体上可以分为两类"一类是种子填充算法"一类是扫描线填充算法!种子填充算法的形式虽然相对简单"但是存在递归调用"没有考虑象素之间的相关性"每个象素都可能多次入栈"因此效率较低"对于面积较大的区域几乎无法使用’&(!相比之下"扫描线填充算法由于利用了扫描线上象素之间的连贯性"因此具有较高的效率’!)!
以往的扫描线填充算法主要用于处理一些简单图形"如多边形#圆#椭圆等’%)!这些算法对于任意形状复杂连通区域的扫描线转换问题并不适用!文献’!"#"*)研究了复杂连通区域的扫描线填充问题"给出了一些算法描述!通过分析发现"文献+!)的算法需要把区域的内#外轮廓线关于!的极值点分裂成若干段"对每段进行折线近似"还需对求取的交点排序"之后才能进行配对和填充"算法比较复杂"实现难度较大"而且本质上是一种多边形的近似算法!文献’#)的算法需要判断轮廓线的方向"求扫描线与轮廓线的交点时对于一些特殊情况考虑不周"导致求取的交点无法正确配对!另外"文献’#"*)的算法存在多次遍历轮廓线的缺点"因而效率较低!
基金项目!国家部委项目
!算法描述
复杂连通区域是一个含有若干孔洞的连通区域!图&中的
灰色区域就是一个包含两个孔洞的复杂连通区域"其中""是区域的外轮廓线""&和"!是区域的内轮廓线"!#$是一条穿过区域的扫描线"%&#%!#$$$$$$#%.是扫描线与区域内外轮廓线的交点!
图&扫描线与复杂连通区域轮廓线的交点
作者简介!张志龙&&@2.,’"男"博士生"主要研究方向为图像处理与模式识别!李吉成&&@2",’"男"副教授"主要研究为图像处理"模式识别"神经
!!""#$%&
万方数据
网络和弱信号检测!沈振康"男"教授"博士生导师

!
计算机工程与应用
2 复杂连通区域扫描线填充算法扫描线填充算 法一般包括 4个步 骤: 求交、 ...一 种新的 快速复 杂连通 区域 扫描线填充算法 [ J] . 计算机工 程与应 ...
复杂连通区域扫描线填充算法的问题及改进_专业资料...的改进办法.从而实现了复杂连通区域的快速正确填充。... 一种改进的扫描线种子填... 107人阅读 2页 ...
一种新的快速复杂连通区域... 3页 免费 一种新的快速复杂连通区域... 3页 5财富值 复杂连通区域扫描线填充算... 3页 2财富值 区域填充的扫描线算法 ...
关键词:八连通;区域填充;扫描线算法;种子点;高速 中图法分类号:-.&/’) )... 一种新的快速复杂连通区... 3页 免费 一种新的连通区域标记算... 暂无...
关键词 : 八连通 ; 区域填充 ; 扫描线算法 ; 种子点 ; 高速 中图法分类... 一种新的快速复杂连通区... 3页 免费 一种二值图像连通区域标... 3页 ...
现有算法存在着只适用于四连通区域或者算法速度不高等缺点。提出了一种可以运用在八连通区域上的扫描线种子填充算法,同时在算法的实现上摒弃函数调用方式,以线性空间...
基于边界扫描的快速区域填充算法_专业资料。提出一种基于边界扫描的区域填充新算法.该算法能对任意复杂的单连通区域进行快速填充,弥补了扫描线算法应用受限制的缺陷...
扫描线种子填充算法中存在的缺陷, 提出了一种改进算法 . 该算法根据填充区域... 郑永果 . 复杂连通区域 扫描线填充算法的问题及 改进 〔J〕. 图像处理与...
关键词 区域填充 , 扫描线算法 , 4-连通区域 , ...它是光栅计算机图形学中的一个基本操作 , 在交互式...判读重复操作的改进算法, 但此算法较复杂, 条理不...
热门文档