区域填充极点判别算法

第 15卷 第 8期 加03年 8月 计算机辅助设计与图形学学报 J0URNAL OF COMPUTER—AIDED DESIGN & COMPUTER GRAPHICS V01．15．No．8 Aug．，2003 区域填充极点判别算法 吴章文 杨代伦 勾成俊 罗正明 (四川大学原子核科学技术研究所辐射物理及技术教育部重点实验室 成都 610064) 摘 要 在深入分析现有的边标志算法的基础上，提出一种适用于图像处理的区域填充算法．在图像处理中，经轮 廓跟踪得到的轮廓点是 目标区域内的像素，这与边标志算法的边界像素的约定不一致．文中算法利用轮廓点与其前 后邻点的相对位置关系将轮廓点分为极点和非极点，再对扫描线上的非极点进行两两配对和填充．在具有较高运算 效率的同时，该算法适用于任意复杂形状的区域． 关键词 区域填充；计算机图形学 ；图像处理；边标志算法 中图法分类号 TP391．41 Singular Point Distinguishing Algorithm for Area Filling Wu Zhangwen Yang Dailun Gou Chengjun Luo Zhengming (KeyLaboratoryforRadiationPhysics andTechnology ofEducationMinistryof China， Institute of Nuclear Science＆ Technology。Sichuan University，Chengdu 610064) Abstract After deep investigation on the edge flag algorithm，we present an area filling algorithm applicable tO image processing．Different from the edge flag algorithm ，contour points got by contour extraction are pixels in the target region．This algorithm classifies these contour points as singular po ints and nonsingular points，then establishes pairs of nonsingular po ints and fills between these pairs．This algorithm is highly efficient and applicable to arbitrary shape region． Key words area filling；computer graphics；image processing；edge flag algorithm 1 引 言 区域填充算法是计算机图形学的基本算法，在 实际中得到了广泛应用．在图像处理中，通常用轮 廓提取算法获得某个物体的轮廓．为了得到该轮廓 所包围的区域以及该区域的一些统计信息(如直方 图)就需要用填充算法．研究区域填充算法的效率 及适用性有十分重要的意义． 传统的区域填充算法有扫描线填充算法、种子 填充算法、边填充算法和边标志算法 。¨J．扫描线填 充算法的基本思想是用一系列平行直线去切割轮廓 线，通常有成对的交点出现，每对交点就代表扫描线 与轮廓线的一个相交区间；该算法的缺点是每条扫 描线要和轮廓线进行求交运算，并且得到的交点还 需排序运算．种子填充算法是在被填充的区域中预 先设置一个种子像素，然后以该像素为起点，按四向 算法或八向算法搜索下一个像素，由此出发蔓延直 到找到区域内所有像素；该算法的缺点是种子点的 找寻比较困难，有的像素可能被访问多次，并且种子 点的人栈和出栈也降低了算法的效率．边填充算法 的基本思想是对于每一条扫描线和轮廓线的每个交 点，将该扫描线上交点右方的所有像素取补．它的 优点在于简单，与边的顺序无关；缺点是每个像素可 原稿收到日期：2002．08—01；修改稿收到日期：2003—03—03．本课题得到国家自然科学基金(10075033)和国家“九五”攻关项目(96．920．06． 02)资助．吴章文，男，1970年生，硕士，助研，主要研究方向为图像处理、计算机图形学、医学图像可视化．杨代伦，男，1946年生，副研究员，主 要研究方向为核技术及应用．勾成俊，男，1970年生，博士，工程师，主要研究方向为核技术及应用．罗正明，男，1940年生，研究员，博士生导 师。主要研究方向为核技术及应用． 维普资讯 http://www.cqvip.com http://www.lw23.com ??? ???? http://www.lw23.com ??? ???? 计算机辅助设计与图形学学报 2003芷 能被访问多次 ，也需要各扫描线与每条边进行求交 运算．边标志算法L4 首先勾画轮廓线，在每条中心 扫描线上建立各区段的边界像素对，然后填充这些 边界像素对之间的所有像素；该算法不需求交运算 和交点的排序运算，且对每个像素仅访问一次，因此 可以获得较高的计算效率． 在图像处理中，区域 R中的轮廓点(边界点)定 义为 R 中这样的像素，它的邻域像素中至少有一个 不在 R 中L5 J．而在边标志算法中的边界像素有可能 不在区域 R中，因此直接对轮廓点作边界像素配对 有可能导致填充失败．本文在分析现有的边标志算 法的基础上，详细讨论了如何利用图像处理中的轮 廓点进行配对，并提出了区域填充极点判别算法． 最后，将本文算法在几种不 同形状 区域上进行了分 析和测试，并与现有区域填充算法在运算效率上作 了比较． 2 边标志算法分析 边标志算法步骤如下： Step1．勾画轮廓线．按中心扫描线约定，对每条与扫描 线相交的多边形边 ，将中心位于交点之右的最左像素标记上 轮廓标志．如图 1 fl所示， 代表轮廓点像素，其余为非轮廓 点像素． Step2．填充．对每条与区域相交的扫描线，按从左到右 顺序逐个访问该扫描线上 的像素．用一个布尔量 inside表 示当前像 素的状态．如果当前像素在 区域 内，则 inside为 true；否则为 false．在每行开始时，令 inside为 false．每当访 问到轮廓像素，将 inside取反．图 1 fl中第 4行和第5行在填 充过程中 inside的状态如图 1 b所示， 代表 true，其余为 false． 5 4 0 1 2 3 4 5 6 7 8 9 b布尔量inside的状态 图 1 边标志算法示意图 根据边标志算法 的中心扫描线约定 ，在扫描线 上轮廓像素总是成对出现．然而图像处理中的轮廓 点在扫描线上有可能是单数．图 2 a所示为图像处 理中的一个待填充区域， 代表 目标区域轮廓．轮 廓是区域内像素．如果直接对它们进行轮廓像素配 对，按边标志算法分别得第 7行、第6行的 inside状 态如图 2 b所示 ．边标 志算 法在 填充 时错误 地把 P(2，7)，P(3，7)和 P(4，6)作 为区域 内点予 以填 充．正确的填充状态如 图 2 C所示．这时可以将极点 概念引入边标志算法 ，在极点情况 ，inside状态不应 取反(如 P(1，7))． 8 0 1 2 3 4 5 6 7 8 9 a各像素打上边标志 0 l 2 3 4 5 6 7 8 9 b边标志算法中inside的状态 0 1 2 3 4 5 6 7 8 9 cinside的正确状态 图 2 边标志算法在第 6，7行上失败 通常，极点和非极点定义如下【6 J：如果某轮廓 点 P的两个最邻近轮廓点不在同一行，且其右方的 最近轮廓点与它不在同一行，则定义 P点为极点； 否则为非极点．这种定义只考虑了轮廓点的两个最 近邻点，而没有考虑轮廓点的前后顺序，在复杂情况 下有可能导致填充算法失败． 将边标志算法分别应用于图3所示情形，其中 P(5，4)，P(6，4)和 P(7，4)构成与扫描线方向平行 的线段．在图3 a中，P(7，4)和P(8，4)的 inside将 为错 误 的 false状态 ．同样地 ，图 3 b中P(7，4)和 P(8，4)得到的 inside亦为 false状态，却是正确的 结果．产生如此不 同结果 的原 因在 于，两图 中该线 段的端点 P(7，4)的邻域轮廓点(分别为 P(8，5)和 P(8，3))与另一端点 P(5，4)的邻域轮廓点 P(4，5) 的相对位置关系不同(一个是同侧，另一个为异侧)． 维普资讯 http://www.cqvip.com http://www.lw23.com ??? ???? http://www.lw23.com ??? ???? 8期 吴章文等：区域填充极点判别算法 981 这表明，在与扫描线方向平行的线段上，两个端点的 邻近点位置将影响填充结果． O 1 2 3 4 5 6 7 8 9 a P(8，4)为区域内像素 b P【8，4)为区域外像素 图 3 不同的前后邻域位置将得到不同的填充结果 在图像处理中，通过轮廓提取算法得到的目标 区域的轮廓可能出现各种奇异的轮廓点，其中的轮 廓点重叠现象(如图 4中 P3与P13，P4与P12， P7与 P9等)需要仔细处理．简单地将重叠轮廓点 合并作为一个轮廓点，对该点对应像素进行标记，有 可能得到错误 的填充结果． 图4 轮廓点重叠现象 3 区域填充极点判别算法 区域填充极点判别算法步骤如下 ： Step1．应用 Bresenham画线算法[ 一 在区域轮廓线上每 相邻两轮廓点间顺序插入若干新轮廓点，使得每个轮廓点与 其前后邻点互为邻域点(如图 5所示)，形成连续闭合的有序 链．对于从轮廓提取算法输出的区域 ，各顶点与其前后邻点 已经互为邻域点，可以跳过这一步． 图 5 8邻域 点示意图 Step2．利用轮廓点与其邻点的相对位置关系，将轮廓点 分为极点和非极点(见第 3．2节)，并在各轮廓点对应的像素 上作标记．对于重叠的轮廓点，按负负得正原则处理．如果 判定某一轮廓点为非极点 ，且对应的像素已标记为非极点 ， 则将对应像素标记为极点． Step3．填充．对被填充区域 的每行，按从左到右顺序逐 点访问各像素．用一个布尔量 inside表示当前像素的状态 ， 如果该像素在区域内，则 inside为true；否则为 false．在每行 开始时，令 inside为 false，每 当访 问到非极点像 素，就把 inside取反． 3．1 算法约定 本文算法对所需的输入、输出量和约束条件的 约定如下 ： 输入量．任意区域轮廓点坐标的有序链表；代 表被填充区域的一个 Buffer，其中每个单元代表一 个像素． 输出量．代表被填充区域的Buffer中每个像素 单元被标记为区域内或区域外像素． 约束条件．轮廓点所在像素为区域内像素，予以 填充；轮廓线无 自相交情况；轮廓线可顺时针也可逆 时针表示；轮廓点可以重叠(如图4中P3与P13)． 3．2 算法相关的几个定义 起始端点．由两个以上的轮廓点构成的、在与 扫描线平行的一段线段上按轮廓点顺序最先的轮廓 点．起始端点可能靠左也可能靠右． 结束端点．由两个以上的轮廓点构成的、在与 扫描线平行的一段线段上按轮廓点顺序最末的轮廓 点．结束端点可能靠左也可能靠右． 线段内点．由三个以上的轮廓点构成的、在与 扫描线平行的一段线段上除起始端点和结束端点以 外的其他轮廓点(即起始轮廓点与结束轮廓点之间 的轮廓点)． 普通轮廓点．除起始端点、结束端点和线段内 点以外的其他轮廓点． 布尔量 inside．代表扫描填充过程中像素的填充 维普资讯 http://www.cqvip.com http://www.lw23.com ??? ???? http://www.lw23.com ??? ???? 计算机辅助设计与图形学学报 状态．inside=true表示当前像素为区域内像素，应予 以填充；否则当前像素为区域外像素，不填充． 变量 direction．代表在某一与扫描方向(水平 方向)平行的直线段上，起始端点与其前一轮廓点的 Y坐标的差值．在扫描到该直线段的结束端点时，用 于判定结束端点的类型． 极点与非极点．在扫描填充过程中，一条扫描线 上有若干轮廓点．一般情况下，按从左到右顺序进行 轮廓点配对，每对轮廓点代表扫描线与轮廓线的一个 相交区间．然而在某些情况下，有的轮廓点不能参加 轮廓点配对，需要进行取舍．被舍去的轮廓点称为极 点，其余为非极点(其判定准则见第 3．3节)． 在本文算法中，为了适应“轮廓点重叠”的情况 (如第2节所述)，提出了轮廓点像素的概念，即轮廓 点对应的像素．在扫描填充时，对轮廓点像素进行配 对，参加配对的轮廓点像素为非极点像素，其余为极 点像素．在有“轮廓点重叠”的情况下，某些轮廓点像 素有可能对应多个轮廓点，这时按“负负得正原则”， 对应于奇数个非极点的轮廓点像素才为非极点像素． 3．3 极点与非极点判定 顺序处理 输入 的有 序链 中的每个轮 廓点． current代表当前处理的轮廓点，previous和 next 分别代表current的前邻点和后邻点．current有如 下 4种情况 ： (1)线段内点 如 果 next．Y= previous．Y = current．Y，则 current为极点．如 图 2所示的 P(7，1)，P(2，6)和 图 6所示的 P3点． (2)普通轮廓点 如果 pre~ous，current和 next三点的纵坐标各 不相同，则 current为非极点．如图 2所示的 P(1，2) 和 P(4，5)点． (3)起始端点 若 ．Y=current． 且 cuFre?／t．Y!=previous．Y， 则 current为极点 ，同时记 direction=previous．Y current．Y．如图 6所示的 P2点． JD1 Jp2 JD3 P4 Jp2 JD3 尸4 P1 a前后异向 b前后同向’ 图 6 水平方向的轮廓点 (4)结束端点 当 ．Y!=CuFFe?12．Y且 cur'Fen2．Y=嬲 ．Y 时 ，如果 direction=next．Y—current．Y，则 current 为极点(如图 6 b所示的 P4点 )；否则 current为非极 点(如图 6 a所示的 P4点)；同时记 direction=0． 此外 ，根据“负负得正原则”，如果轮廓点 current 为非极点，且其对应轮廓点像素已标记为非极点像 素，则将其对应轮廓点像素标记为极点像素． 3．4 扫描填充 将每个轮廓点分为极点和非极点，在各自对应 的像素上标记后，就可以对区域进行扫描填充了． 本文算法约定，轮廓点像素均为目标区域内像素． 因此在填充过程 中不需考虑扩大化问题 ]，所有轮 廓点像素均予以填充． Step1．对轮廓线的外接矩形区域 自上而下、从左到右地 扫描每个像素 ，每行扫描开始之前 ，设置布尔标志 inside= false． Step2．在扫描过程中，只有扫描到标记为非极点的像素 时 ，inside取反 。即 inside=!inside． Step3．在扫描过程中，inside=true的所有像素均为区 域内的像素． Step4．在扫描过程中，所有轮廓点像素为区域内的像素． 4 效率分析和结论 本文算法由于不需进行扫描线与轮廓线的求交 运算，每个像素仅访问一次，因此具有很高的运算效 率．我们在 Acer Veriton 7100一M(PIII 866)上分别 实现 了有序 边表 算法L1 J、扫 描线种 子填 充算 法 ]、任继成的改进算法L7 和本文算法，并取 4种 典型的区域(矩形、圆形，实际应用中的人体头部、胸 部区域)对以上 4种算法进行了测试和比较，测试结 果如表 1所示．为了减小 Windows多任务操作系统 中各种系统任务对算法统计时间的随机影响，每个 测试项均重复 100次，并取其中最小值作为有效结 果．表中 ，丁1，丁2和 丁3分别代表各种算法对几 种典型形状区域进行填充所花时间，单位为 ms．结 果表明，本文算法的效率优于其他算法．本文算法利 用轮廓点与前后邻点的相对位置关系将轮廓点分为 极点和非极点，并引入了极点像素和非极点像素的 概念，从而成功地将该算法应用到包含有重叠轮廓 点的任意复杂形状的区域．在 CT图像的自动分割、 器官识别及区域直方图等统计信息的获得上，应用 本文算法取得了良好的效果． 维普资讯 http://www.cqvip.com http://www.lw23.com ??? ???? http://www.lw23.com ??? ???? 8期 吴章文等：区域填充极点判别算法 983 表 1 4种区域填充算法的效率比较 参 考 文 献 Sun Jiaguaog，Yang Changgui．Computer Graphics[M]． Beijing：Tsinghua University Press，1997(in Chinese) (孙家广，杨长贵．计算机图形学[M]．北京：清华大学出版 杜 ，1997) Rogers David F．Procedural Elements for Co mputer Graphics [M]．2nd ed．Beijing：China Machine Press，2002 Dunlavey M R． Efficient polygon-filling algorithms for raster displays[J]．ACM Transactions on Graphics，1983，2(4)：264 — — 273 AcklandBryan D，Weste Neff H．The edge flag Mgofithm-- A fill method for raster 8Can displays[J]．IEEE Transactions on Computers，1981，30(1)：41～48 [5] Wu Lide．Computer Vision[M】．Shanghai：Fudan University Press，1993(in Chinese) [6] [7] (吴立德．计算机视觉[M]．上海：复旦大学出版杜，1993) Luo Biogwei．Medical Image Processing and Recognition[M]． Chengdu： Press of University of Electronic Science and Technology of China，1989(in Chinese) (罗炳伟．医学图像处理与识别[M]．成都 ：电子科技大学出 版杜 ，1989) Ren Jicheng．Improvement of area filling scanline algorithm[J]． Journal of Co mputer-Aided Design ＆ Computer Graphics． 1998，10(6)：481～486(in Chinese) (任继成．区域填充扫描线算法的改进[J]．计算机辅助设计 与图形学学报，1998，10(6)：481～486) ⋯ ⋯ 维普资讯 http://www.cqvip.com http://www.lw23.com ??? ???? http://www.lw23.com ??? ????