区域填充

短命女 2022-10-01 00:52 230阅读 0赞

# 一、种子填充算法    #

区域是指光栅网络上的一组像素，区域填充是把某确定的像素值送入到区域内部的所有像素中。

区域填充方法分为两大类：区域由多边形围成，区域由多边形的顶点序列来定义；另一类方法是通过像素的值来定义区域的内部，相应的技术称为是以像素为基础的。

内定义区域，定义方法是指出区域内部所有的像素值，此时区域内部所有像素有某个原值oldvalue。

边界定义区域，定义方法是指出区域边界所具有的像素值。此时区域边界上的所有像素具有某个边界boundaryvalue。区域的边界应该是封闭的，并且应该指明区域的内部。

1. 以像素为基础的区域填充主要是依据区域的连通性进行。

四连通：从区域中的一个像素出发，经连续地上下左右四个相邻的像素的移动，就可以到达区域内的任意一个像素。

八连通：如果出了要经上下左右的移动，还要经左上、右上、左下、右下的移动，才能由一个像素走到区域中的另外一个任意像素。

利用区域的连通性进行区域填充，除了需要区域应该明确定义外，还需要事先给定一个区域内部像素，这个像素称为种子。

做区域填充时，要进行对光栅网络的遍历，找出由种子出发能达到而又不穿过边界的所有像素。这种利用连通性的填充，其主要优点是不受区域不规则性的影响，主要缺点是需要事先知道一个内部像素。

2.扫描线种子填充算法

将区域由内边界点限定的同一行内相连接的不具有新值newvalue的一组像素称为一个像素段，像素段用它最右边的像素来标识。

算法的步骤如下：

2.1 对种子所在像素段进行区域填充。

2.2 从右至左检查种子所在的行的上一横行，将查得的像素段一次编号存入堆栈。接着对种子所在的行的下一横行同样处理。

2.3若堆栈为空，则算法结束，否则从堆栈顶部取一个像素段，就以这个像素为新的种子，返回步骤2.1。

#     #

# 二、多边形的扫描转换算法。 #

多边形扫描转换产生面填充的图形。多边形扫描转换可以依据区域的一种“奇偶”性质，即一条直线与任意封闭区域的曲线相交时，总是从第一个交点进入内部，再从第二个交点推出，一下交替的进入退出，即基数次进入，偶数次退出。当然，可能有些“相切”的点应做特殊处理。

可以分如下三个步骤来做：

1.找出扫描线与多边形边界线的所有交点。

2.按x坐标增加顺序对交点排序。

3.交点对之间进行区域填充。

正确解决“相切”的办法是，当顶点表现为局部极大或者局部极小时，就看做是两个，否则看做是一个。在这里，称一个顶点局部极大，如果这个顶点的前面和后面各有一些相邻的顶点的y坐标，都小于该顶点的y坐标。局部极小的定义类似地可确定。

实际处理这个问题可以有一个简便的办法，那就是对应看做是一个的顶点，将其上面的边缩短两条相邻的扫描线对应的一个单位。

计算扫描线与多边形边界线的交点：注意到若扫描线yi与多边形边界线交点x的坐标是xi，则对下一条扫描线yi+1,它与那条边界线得交点的x坐标xi+1可如下求出：

xi+1=xi+1/m; (其中m为斜率)

活跃边表AET(Active-Edge-Table),用这个表存贮与当前扫描线相交的各边。每次离开一条扫描线进入下一条扫描线之前，将表中有但与下一条扫描线不相交的边清除出表，将与下一条扫描线相交而表中没有的边加入表中。

边表ET(Edge Table)，TE中各登记项按y坐标递增排序，每一登记项下的“吊桶”按所计x坐标递增排序，“吊桶”中各项内容依次是：

1.遍的另一端点的较大的y坐标ymax。

2.与较小的y坐标对应的边的端点的x坐标xmin。

3.斜率的倒数，即1/m。

算法：

y=置y为边表ET中各登记项对应的y坐标中最小值。

活跃边表AET初始化为空表；

while(ET表中仍有扫描线未被处理)

\{

将ET中登记项y对应的各“吊桶”合并到表AET中，将AET中各吊桶按x坐标递增排序；

在扫描线y上，按照AET表提供的x坐标对，用color填充。

将AET表中有y=yma各项清除出表；

对AET中留下的各项，分别将x换为x+1/m，这是求出AET中各边与下一条扫描线交点的x坐标。

由于前一步可能破坏了AET表中各项x坐标的递增次序，故按x坐标重新排序。

y=y+1，去处理下一条扫描线。

\}

发表评论取消回复

表情：

评论列表（有 0 条评论，230人围观）

还没有评论，来说两句吧...

相关阅读

相关区域填充

一、种子填充算法区域是指光栅网络上的一组像素，区域填充是把某确定的像素值送入到区域内部的所有像素中。区域填充方法分为两大类：区域由多边形围成，区域由多边形的顶

短命女/ 2022年10月01日 00:52/ 0 赞/ 231 阅读

相关 OPENCV二值化图像内孔洞填充/小区域去除

来源：http://lib.csdn.net/article/opencv/28353 原作者：robberjohn 博客已删除了，源码下载链接在 http://downl

妖狐艹你老母/ 2022年06月09日 14:14/ 0 赞/ 272 阅读

相关 Matlab图像剪切，超出图像区域指定颜色填充

Matlab图像剪切，超出图像区域指定颜色填充【尊重原创，转载请注明出处】http://blog.csdn.net/guyuealian/article/deta

末蓝、/ 2022年06月09日 00:55/ 0 赞/ 498 阅读

相关 OpenCV图像剪切，超出图像区域指定颜色填充

OpenCV图像剪切，超出图像区域指定颜色填充【尊重原创，转载请注明出处】http://blog.csdn.net/guyuealian/article/deta

深藏阁楼爱情的钟/ 2022年06月09日 00:15/ 0 赞/ 340 阅读

相关提取兴趣区域并进行缩放后填充

今天提取的方式为手动，后面或全自动找感兴趣区域用数据游标找到兴趣区域的坐标 ![这里写图片描述][SouthEast] 代码如下： clc,clear,

﹏ヽ暗。殇╰゛Y/ 2022年06月06日 05:13/ 0 赞/ 161 阅读

相关区域填充:扫描线种子填充算法应用(类似魔术棒功能)

/ < 扫描线种子填充算法 > 算法的基本过程如下：当给定种子点(x, y)时，首先分别向左和向右两

末蓝、/ 2022年06月01日 12:08/ 0 赞/ 236 阅读

相关多边形区域填充算法－－扫描线种子填充算法

[http://blog.csdn.net/orbit/article/details/7343236][http_blog.csdn.net_orbit_article_de

我就是我/ 2022年06月01日 05:13/ 0 赞/ 235 阅读

相关 autocomplete 自动填充与禁止填充

autocomplete 属性规定输入字段是否应该启用自动完成功能。自动完成允许浏览器预测对字段的输入。当用户在字段开始键入时，浏览器基于之前键入过的值，应该显示出在字段中

傷城~/ 2022年04月10日 12:31/ 0 赞/ 341 阅读

相关 photoshop对选中区域填充、画矩形、带箭头直线等常用操作

photoshop对选中区域填充、画矩形、带箭头直线等常用操作选中区域填充画矩形画带箭头直线其他选中区域填充选中区域后，快捷键

淡淡的烟草味﹌/ 2021年12月23日 04:59/ 0 赞/ 346 阅读

相关搜索（DFS）---填充封闭区域

填充封闭区域 [130. Surrounded Regions (Medium)][130. Surrounded Regions _Medium] For e

野性酷女/ 2021年11月29日 07:56/ 0 赞/ 244 阅读