浏览量:16,811

区域填充算法和多边形填充的扫描线算法

本文主要介绍几种区域填充算法,重点解释多边形的扫描线填充算法,最后实现了多边形填充算法,包括在附录文件中。在参考【5】中,作者详细介绍了一系列区域填充算法,可以查看相应网页。代码的下载地址为:https://github.com/twinklingstar20/twinklingstar_cn_region_polygon_fill_scanline/

1. 1.      区域的定义和填充

1.1   像素定义的区域(Pixel-Defined Region

1.1.1        边界定义区域(boundary-defined)

定义某些像素是边界,边界包围着一块区域。填充所有在边界内的相连通的像素,主要分下面几个步骤:

  1. 从区域内部一个像素点开始
  2. 判断这个像素是否是一个边界像素点或者已经被填充了
  3. 如果都不是,就把它填充,然后开始设置邻居像素点。

用图片演示这个过程,如下面的幻灯片所示,代码片段如下所示:

void boundaryFill4 (int x, int y, int fill, int boundary)
{
   int current;
   current = getPixel (x,y);
   if (current != boundary && current !=fill) 
   {
      setColor(fill);
      setPixel(x,y);
      boundaryFill4 (x+1, y, fill, boundary);
      boundaryFill4 (x−1, y, fill, boundary);
      boundaryFill4(x, y+1, fill, boundary);
      bonddaryFill4(x, y−1, fill, boundary);
   }
}

  • 2013-11-10 15-41-57
  • 2013-11-10 15-30-21
  • 2013-11-10 15-30-35
  • 2013-11-10 15-35-48
  • 2013-11-10 15-31-05
2013-11-10 15-41-571 2013-11-10 15-30-212 2013-11-10 15-30-353 2013-11-10 15-35-484 2013-11-10 15-31-055
Bootstrap Carousel by WOWSlider.com v4.8

1.1.2          内定义区域(interior-defined)

内定义区域的定义是:给定一个像素S,颜色是C,区域R指与S连通的且颜色都是C的像素集合(Region R is the set of all pixels having color C that are “connected” to a given pixel S)。

如果两个像素连通,则它们之间有一条“相邻(adjacent)”像素组成的连续路径,所以连通的概念就依赖“相邻”的定义。在图形学中,相邻通常有两种定义:

(1)       四相邻(4-Adjacent):两个像素是四相邻的,则它们在彼此水平或者垂直相邻的位置上,如图1所示:

2013-11-13 22-12-03

图1. 四相邻

(2)       八相邻(8-Adjacent):两个像素是八相邻的,则它们在彼此水平、垂直或者是斜方向上相邻的位置,如图2所示:

2013-11-13 22-12-28

图2. 八相邻

如果两个像素是四连通(4-connected),指它们之间有一条四相邻像素组成的连续路径;如果两个像素是八连通(8-connected),指它们之间有一条四相邻像素组成的连续路径。举个例子,如下图3所示,是由黑色、灰色和白色组成的像素图,给定一个像素点S,则由它定义的四连通区域共有20像素,由它定义的八连通区域共有28个像素。

2013-11-13 22-12-41

图3 像素区域

这里介绍两种简单的填充算法:

(1)       一种称为洪水填充法。规定采用4连通的区域,下面用幻灯片演示了这个过程,下面的代码片段实现了该算法。由于没有使用到区域间的相关性,很多像素点可能会重复被填充。

  1. 从内部一个像素点开始,并用新的颜色替换它
  2. 填充四连通或者八连通区域,直到所有的内部点被替换了
void floodFill4 (int x, int y, int fill, int oldColor)
{
     if (getPixel(x,y) == oldColor) 
     {
        setColor(fill);
        setPixel(x,y);
        floodFill4 (x+1, y, fill, oldColor);
        floodFill4 (x−1, y, fill, oldColor);
        floodFill4(x, y+1, fill, oldColor);
        floodFill4(x, y−1, fill, oldColor);
     }
}

  • 2013-11-10 17-11-13
  • 2013-11-10 17-11-23
  • 2013-11-10 17-11-32
  • 2013-11-10 17-11-41
  • 2013-11-10 17-12-01
2013-11-10 17-11-131 2013-11-10 17-11-232 2013-11-10 17-11-323 2013-11-10 17-11-414 2013-11-10 17-12-015
Bootstrap Carousel by WOWSlider.com v4.8

缺点是:1)大量的嵌套调用;2)很多像素点可能会被测试多次;3)难以清楚的掌控由于嵌套调用所占的内存大小;4)如果算法多次测试一个像素,会导致占用的内存扩大。

(2)利用像素间的相关性,可以提高算法的性能,并避免堆栈的溢出。每次填充在同一条扫描线上相邻的一排像素,同时把与它相邻的未填充的种子像素放在堆栈中,下面的幻灯片演示了这个过程。伪码如下所示:

Push address of seed pixel on the stack;
while( stack not empty)
{
	Pop the stack to provide the next seed;
	Fill the run defined by the seed; 
	In the row above find interior runs reachable from this run;
	Push the addresses of the rightmost pixels of each such run;
	Do the same for the row below the current run;
}
  • 2013-11-10 17-49-00
  • 2013-11-10 17-50-20
  • 2013-11-10 17-51-20
  • 2013-11-10 17-52-40
  • 2013-11-10 17-55-31
  • 2013-11-10 17-56-44
  • 2013-11-10 17-57-44
  • 2013-11-10 17-58-40
  • 2013-11-10 17-59-24
  • 2013-11-10 18-00-11
  • 2013-11-10 18-01-00
  • 2013-11-10 18-02-01
2013-11-10 17-49-001 2013-11-10 17-50-202 2013-11-10 17-51-203 2013-11-10 17-52-404 2013-11-10 17-55-315 2013-11-10 17-56-446 2013-11-10 17-57-447 2013-11-10 17-58-408 2013-11-10 17-59-249 2013-11-10 18-00-1110 2013-11-10 18-01-0011 2013-11-10 18-02-0112
Bootstrap Carousel by WOWSlider.com v4.8
1.2   符号定义的区域(Symbolically Defined Region

这里简单介绍下符号定义的区域的分类,详细参见参考【4】,主要包括两类:

(1)用一系列的矩形方块表示的区域;

(2)通过一条表示一个区域边界的路径来界定一个区域:

1)用一个数学公式来定义边界,例如采用(x-122)^2+(y-36)^2=25来定义一个圆的区域

2)通过一系列的多边形顶点,像(x1,y1),(x2,y2),(x3,y3)…(xn,yn)来定义一个多边形区域

3)通过一系列相邻的像素来定义。

4)链码(chain code),这是一个很经典的方法,在参考【3】和【4】中都有简单的介绍,这里不详细介绍这块知识

5)其它

2.     多边形填充算法

2.1   算法思想

参考【5】,扫描线填充算法的基本思想是:每条水平扫描线与多边形的边产生一系列交点,交点之间形成一条一条的线段,该线段上的像素就是需要被填充的像素。将这些交点按照x坐标排序,将排序后的交点两两成对,作为线段的两个端点。水平扫描线从上到下(或从下到上)扫描由多条首尾相连的线段,使用要求的颜色填充该水平线段上的像素。多边形扫描完成后,颜色填充也就完成了。扫描线填充算法可以归纳为以下4个步骤:

(1)       求交,计算扫描线与多边形的交点;

(2)       交点排序,对第(1)步得到的交点按照x值从小到大进行排序;

(3)       颜色填充,对排序后的交点两两组成一个水平线段,以画线段的方式进行颜色填充;

(4)       是否完成多边形扫描?如果是就结束算法,如果不是就改变扫描线,然后转第1步继续处理;

整个算法的关键是第1步,需要用尽量少的计算量求出交点,还要考虑交点是线段端点的特殊情况,最后,交点的计算最好是整数,便于光栅设备输出显示。对于每一条扫描线,如果每次都按照正常的线段与直线相交算法进行计算,则计算量大,而且效率低下,如图(4)所示:

2013-11-13 22-12-56

图4. 扫描线算法

2.2   存在的问题

利用上述算法还存在几个问题,接下来分别讨论:

(1)       如果多个多边形相邻的话,它们可能会共享一条边,那么共享边可能会被绘制两次,图5和图6演示了该错误:

2013-11-13 22-13-08

图5. 相邻的两个三角形共享边

2013-11-13 22-13-18

图6. 左图是背景颜色与前景颜色混合的情况,右图是不绘制共享边的情况

对这个问题有一种很好的解决方案是:

原则1:每个多边形只拥有它左边的像素,即采用左闭右开的原则,如果边是水平的话,则只拥有底边。        

2013-11-13 22-13-28

图7. 共享边的解决方案

(2)       如图7所示,若采用Bresenham直线绘制算法,(参见文章,《布雷森汉姆直线算法》可能会出现一些像素超出边所在的范围:

原则2:在计算完扫描线与边的交点后,会形成一条条的首尾相连的线段,用xLeft表示左端点,xRight表示右端点,xLeftxRight是实数,取大于等于xLeft的最小整数xNewLeft,取小于等于xRight的最大整数xNewRight,则绘制像素范围是[xNewLeftxNewRight),如果 xNewRight<xRight,则右端也封闭。

(3)       水平扫描线与端点发生相交的情况。如图8所示,穿过顶点H的扫描线,发生了两次相交(一次是与边GH,一次是与边HI),所以2.1描述的算法思想的第1步结束后,H点会存储两次,排完序后H两边的奇偶性会相同,因此会错误的将H右边的像素进行填充。(本图是从参考【4】中获取的,个人觉得该图解释这个问题,有点牵强。如果整个图左右翻转的话,解释这个问题就特别清楚了,算法思想的第1步结束后,该扫描线上共有三个交点:(H,H,右交点),这样问题就明显了)。这里采用两条原则,可以很简单的解决这个问题:

2013-11-13 22-13-37

图8. 填充多边形

原则3:忽略任何一条与水平边的相交计算;

原则4:如果交点是边的上端点,则把该端点忽略。

举个遵守该该原则的例子,如图9所示,得到每条边端点相交的数量:

2013-11-13 22-13-47

图9. 一个多边形的端点相交的数量

2.3   数据结构设计

2.3.1活动边链表(Active-Edge List,AEL)

在计算相邻两条扫描线与一条边的相交时,可以利用它们之间的相关性。假设,一条边与的斜率是k,与扫描线y相交于x,则该边与扫描线y+1相交于x+1/k点的位置,利用这个特性可以减少运算量。为了方便进行该运算,有人提出了一种数据结构,称为活动边链表,链表的每个节点存储三个数据:(1)与当前水平扫描线的交点xint;(2)斜率m的倒数,1/m;(3)边的上端点的yhigh。举个例子来说该结构的存储方式,如图10所示,虚线代表了水平扫描线,在该水平扫描线上与多边形共有4个交点,则在AEL中会存储4个节点,4个结点按照xint从小到大排序。

2013-11-13 22-14-07

图10. 活动边链表

2.3.2边表(Edge Table,ET)

边表存储的是边的信息,边表中每个节点的数据结构与AEL中每个节点的相同,同样存储了三个信息:(1)边下端点X坐标xbottom;(2)边斜率的倒数;(3)边上端点Y坐标yhigh。当AEL表进行更新时,边表这种数据结构提供了快速索引的功能。如图10中多边形的边信息,用边表表示,如图11所示,这里就记录了其中四条边的信息。首先用一个边节点的数组,一条边下端点的Y坐标值,表示该数组的索引。图10中,Y=20扫描线上,共有两条边(原则3,忽略水平边),所以把两条边的信息记录节点,该节点存储在数组索引号20的表项后面,注意:在我的实现中,要求这个链表中的节点也是按照xbottom从小到大的顺序排列的;例如扫描线39所示,不存在边的下端点在该扫描线上,则索引号39的表项后面为空。

2013-11-13 22-14-16

图11. 边表

2.4   算法实现

如下面的代码片段所示,主要有如下几个步骤:

(1)       分配AEL的表头g_ptrAELHead和边表g_ptrEdgeTable[EDGE_TABLE_SIZE]的表头内存空间,由于现在显示器在垂直方向的分辨率一般不超过1024,所以这里不进行优化。

(2)       初始化边表

(3)       在当前扫描线上,在ET中是否存在表项,如果存在,则插入到AEL表中。

(4)       填充该扫描线

(5)       更新AEL。AEL中是否有边的y坐标值大于或者等于下一条扫描线(原则1:上边不进行绘制),由于AEL结点中保存有yhigh,这一步很容易判断,将相应的节点删除。

(6)       判断算法是否结束,否则的话重复(3)-(5)几个步骤。

typedef struct _Edge
{
	double	dbX;
	double	dbDelta;
	int		inMaxY;
	_Edge*	ptrNext;
}Edge;

Edge*	g_ptrEdgeTable[EDGE_TABLE_SIZE];
Edge*	g_ptrAELHead;
void scanLineFill(Vector* ptrPolygon, int inNumPoly,DWORD inColor)
{
	allocEdges();
	initEdgeTable(ptrPolygon,inNumPoly);
	for(int y=g_inMinY ; y<g_inMaxY ; y++ )
	{
		insertAEL(g_ptrAELHead,g_ptrEdgeTable[y]);
		fillAELScanLine(g_ptrAELHead,y,inColor);
		updateAEL(g_ptrAELHead,y+1);
	}
	deallocEdges();
}
2.5   算法结果演示

如图12所示,实现该算法,并用glut库实现了个简单的Demo,按’U’,’L’可以放大或者缩小图像,即放大缩小每个“像素”占据的像素大小。

2013-11-13 22-14-30

图12. 算法演示

3.      参考

【1】http://www.cs.ucdavis.edu/~ma/ECS175_S00/Notes/0411_a.pdf

【2】http://www.cs.tufts.edu/~sarasu/courses/comp175-2009fa/pdf/comp175-04-region-filling.pdf

【3】冈萨雷斯《数字图像处理》

【4】F.S Hill, JR. 《Computer Graphics Using OpenGL, Second Edition》

【5】http://blog.csdn.net/orbit/article/details/7368996

 

spacer

One comment on “区域填充算法和多边形填充的扫描线算法

  1. Anonymous

    楼主,我看了你github上的代码, 比我之前读到的好太多了。问一句, 你的这个边界这一块, 我看是直接取ceil和floor的, 这会不会导致一些边界不够准确?

Leave a reply to Anonymous Cancel reply