文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > 人文社科 > 教育学/心理学 > 一种新的快速复杂连通区域扫描线填充算法
侵权投诉

一种新的快速复杂连通区域扫描线填充算法

一种新的快速复杂连通区域扫描线填充算法

一种新的快速复杂连通区域扫描线填充算法

张志龙

李吉成

沈振康

!国防科技大学电子科学与工程学院/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",’"男"副教授"主要研究为图像处理"模式识别"神经

!!""#$%&

万方数据

网络和弱信号检测!沈振康"男"教授"博士生导师

一种新的快速复杂连通区域扫描线填充算法

!

计算机工程与应用

第1页

你可能喜欢

  • 扫描算法
  • 教学教案
  • 红外传感器
  • 老王ppt
  • 光纤温度传感器设计
  • 温度传感器设计报告

热门文档

相关文档

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email