【Algorithm】种子填充算法

【Algorithm】种⼦填充算法

【平⾯区域填充算法】是计算机图形学领域的⼀个很重要的算法，区域填充即给出⼀个区域的边界（也可以是没有边界，只是给出指定颜⾊），要求将边界范围内的所有象素单元都修改成指定的颜⾊（也可能是图案填充）。区域填充中最常⽤的是多边形填⾊，本⽂讨论种⼦填充算法（Seed Filling）如果要填充的区域是以图像元数据⽅式给出的，通常使⽤种⼦填充算法（Seed Filling）进⾏区域填充。种⼦填充算法需要给出图像数据的区域，以及区域内的⼀个点，这种算法⽐较适合⼈机交互⽅式进⾏的图像填充操作，不适合计算机⾃动处理和判断填⾊。根据对图像区域边界定义⽅式以及对点的颜⾊修改⽅式，种⼦填充⼜可细分为⼏类：

⽐如：①注⼊填充算法（Flood Fill Algorithm）、

②边界填充算法（Boundary Fill Algorithm）以及

经济研究参考　③为减少递归和压栈次数⽽改进的扫描线种⼦填充算法等等。

所有种⼦填充算法的核⼼其实就是⼀个递归算法，都是从指定的种⼦点开始，向各个⽅向上搜索，逐个像素进⾏处理，直到遇到边界，各种种⼦填充算法只是在处理颜⾊和边界的⽅式上有所不同。

在开始介绍种⼦填充算法之前，⾸先也介绍两个概念，就是“4-联通算法”和“8-联通算法”。

既然是搜索就涉及到搜索的⽅向问题，从区域内任意⼀点出发，如果只是通过上、下、左、右四个⽅向搜索到达区域内的任意像素，则⽤这种⽅法填充的区域就称为四连通域，这种填充⽅法就称为 “4-联通算法”。如果从区域内任意⼀点出发，通过上、下、左、右、左上、左下、右上和右下全部⼋个⽅向到达区域内的任意像素，则这种⽅法填充的区域就称为⼋连通域，这种填充⽅法就称为“8-联通算法”。

如图1（a）所⽰，假设中⼼的蓝⾊点是当前处理的点，如果是“4-联通算法”，则只搜索处理周围蓝⾊标识的四个点，如果是“8-联通算法”则除了处理上、下、左、右四个蓝⾊标识的点，还搜索处理四个红⾊标识的点。两种搜索算法的填充效果分别如如图1（b）和图1（c）所⽰，假如都是从黄⾊点开始填充，则“4-联通算法”如图1（b）所⽰只搜索填充左下⾓的区域，⽽“8-联通算法”则如图1（c）所⽰，将左下⾓和右上⾓的区域都填充了。

1. 注⼊填充算法（Flood Fill Algorithm）

边界填充算法与注⼊填充算法的本质其实是⼀样的，都是递归和搜索，区别只在于对边界的确认，也就是递归的结束条件不⼀样。注⼊填充算法没有边界的概念，只是对联通区域内指定的颜⾊进⾏替换，⽽边界填充算法恰恰强调边界的存在，只要是边界内的点⽆论是什么颜⾊，都替换成指定的颜⾊。边界填充算法在应⽤上也⾮常的⼴泛，画图软件中的“油漆桶”功能就是边界填充算法的例⼦。以下就是边界填充算法的⼀个实现：

void FloodSeedFill(int x, int y, int old_color, int new_color)

{

if(GetPixelColor(x, y) == old_color)

{

SetPixelColor(x, y, new_color);

for(int i = 0; i < COUNT_OF(direction_8); i++)

{

FloodSeedFill(x + direction_8[i].x_offset,

y + direction_8[i].y_offset, old_color, new_color);

}

for循环实现了向8个联通⽅向的递归搜索，秘密就在direction_8的定义：

typedef struct tagDIRECTION

{

int x_offset;

int y_offset;

}DIRECTION;

DIRECTION direction_8[] = { {-1, 0}, {-1, 1}, {0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1}, {-1, -1} }; 下图就是应⽤本算法实现的“4-联通”和“8-联通”填充效果：

2. 边界填充算法（Boundary Fill Algorithm）

void BoundarySeedFill(int x, int y, int new_color, int boundary_color)

{

int curColor = GetPixelColor(x, y);

if( (curColor != boundary_color)&& (curColor != new_color) )

{

SetPixelColor(x, y, new_color);关于文学的资料

for(int i = 0; i < COUNT_OF(direction_8); i++)

{

BoundarySeedFill(x + direction_8[i].x_offset,

y + direction_8[i].y_offset, new_color, boundary_color);

}

关于direction_8的说明请参考上⼀节，图3就是应⽤本算法实现的“4-联通”和“8-联通”填充效果（其中颜⾊值是1的点就是指定的边界）：

3. 扫描线种⼦填充算法（ScanLineSeed Fill Algorithm）

前⾯介绍的1与2，介绍的两种种⼦填充算法的优点是⾮常简单，缺点是使⽤了递归算法，这不但需要⼤量栈空间来存储相邻的点，⽽且效率不⾼。为了减少算法中的递归调⽤，节省栈空间的使⽤，⼈们提出了很多改进算法，其中⼀种就是扫描线种⼦填充算法。

扫描线种⼦填充算法不再采⽤递归的⽅式处理“4-联通”和“8-联通”的相邻点，⽽是通过沿⽔平扫描线填充像素段，⼀段⼀段地来处理“4-联通”和“8- 联通”的相邻点。这样算法处理过程中就只需要将每个⽔平像素段的起始点位置压⼊⼀个特殊的栈，⽽不需要象递归算法那样将当前位置周围尚未处理的所有

相邻点都压⼊堆栈，从⽽可以节省堆栈空间。应该说，扫描线填充算法只是⼀种避免递归，提⾼效率的思想，前⾯提到的注⼊填充算法和边界填充算法都可以改进成扫描线填充算法，下⾯介绍的就是结合了边界填充算法的扫描线种⼦填充算法。

扫描线种⼦填充算法的基本过程如下：当给定种⼦点(x, y)时，⾸先分别向左和向右两个⽅向填充种⼦点所在扫描线上的位于给定区域的⼀个区段，同时记下这个区段的范围[xLeft, xRight]，然后确定与这⼀区段相连通的上、下两条扫描线上位于给定区域内的区段，并依次保存下来。反复这个过程，直到填充结束。

扫描线种⼦填充算法可由下列四个步骤实现：

（1）初始化⼀个空的栈⽤于存放种⼦点，将种⼦点(x, y)⼊栈；

（2）判断栈是否为空，如果栈为空则结束算法，否则取出栈顶元素作为当前扫描线的种⼦点(x, y)，y是当前的扫描线；

（3）从种⼦点(x, y)出发，沿当前扫描线向左、右两个⽅向填充，直到边界。分别标记区段的左、右端点坐标为xLeft和xRight；

（4）分别检查与当前扫描线相邻的y - 1和y + 1两条扫描线在区间[xLeft, xRight]中的像素，从xLeft开

始向xRight⽅向搜索，若存在⾮边界且未填充的像素点，则出这些相邻的像素点中最右边的⼀个，并将其作为种⼦点压⼊栈中，然后返回第（2）步；

如果新扫描线上实际点的区间⽐当前扫描线的[xLeft, xRight]区间⼤，⽽且是连续的情况下，算法的第（3）步就处理了这种情况。如下图所⽰：

假设当前处理的扫描线是黄⾊点所在的第7⾏，则经过第3步处理后可以得到⼀个区间 [6,10]。然后第4步操作，从相邻的第6⾏和第8⾏两条扫描线的第6列开始向右搜索，确定红⾊的两个点分别是第6⾏和第8⾏的种⼦点，于是按照顺序将（6, 10）和（8, 10）两个种⼦点⼊栈。接下来的循环会处理（8, 10）这个种⼦点，根据算法第3步说明，会从（8, 10）开始向左和向右填充，由于中间没有边界点，因此填充会直到遇到边界为⽌，所以尽管第8⾏实际区域⽐第7⾏的区间[6,10]⼤，但是仍然得到了正确的填充。

如果新扫描线上实际点的区间⽐当前扫描线的[xLeft, xRight]区间⼤，⽽且中间有边界点的情况，算法⼜是怎么处理呢？算法描述中虽然没有明确对这种情况的处理⽅法，但是第4步确定上、下相邻扫描线的种⼦点的⽅法，以及靠右取点的原则，实际上暗含了从相邻扫描线绕过障碍点的⽅法。下⾯以下图为例说明：

算法第3步处理完第5⾏后，确定了区间[7, 9]，相邻的第4⾏虽然实际范围⽐区间[7, 9]⼤，但是因为

被（4, 6）这个边界点阻碍，使得在确定种⼦点（4, 9）后向左填充只能填充右边的第7列到第10列之间的区域，⽽左边的第3列到第5列之间的区域没有填充。虽然作为第5⾏的相邻⾏，第⼀次对第4⾏的扫描根据靠右原则只确定了（4, 9）⼀个种⼦点。但是对第3⾏处理完后，第4⾏的左边部分作为第3⾏下边的相邻⾏，再次得到扫描的机会。第3⾏的区间是[3, 9]，向左跨过了第6列这个障碍点，第2次扫描第4⾏的时候就从第3列开始，向右，可以确定种⼦点（4, 5）。这样第4⾏就有了两个种⼦点，就可以被完整地填充了。

由此可见，对于有障碍点的⾏，通过相邻边的关系，可以跨越障碍点，通过多次扫描得到完整的填充，算法已经隐含了对这种情况的处理。

4. 根据本节总结的四个步骤实现并运⾏通过程序⽚段如下：

//扫描线绘制算法，提⾼填充效率，种⼦是基于⿏标点击的像素位置

inline void CScanLineSeedFill::scanLineSeedFill(CPoint clickPos, GLfloat (&frameWork)[4][3] )

{

//⾸先判定当前点是否有效，⽆效直接返回

assert(isInialDone);

//⿏标的点击点必须在外围框之内

GLdouble winFramePos[4][3];

getViewPortCoordPos(frameWork, winFramePos);

int frameLeft = (int)winFramePos[0][0];

int frameDown = (int)winFramePos[0][1];

int frameRight = (int)winFramePos[2][0];

int frameUp = (int)winFramePos[2][1];

//对绘制的范围进⾏限定：点击框架之外，或者原点⽆效

//计算click位置在视⼝中的坐标

PointInt clickViewPos(clickPos.x, (this->winHigh) - (clickPos.y));

if ((clickPos.x==0 && clickPos.y==0) ||!(clickViewPos.x>frameLeft && clickViewPos.x<frameRight && clickViewPos.y>frameDown && clickViewPos.y<frameUp)) return ;

GLubyte readColor[3];

glReadPixels(clickViewPos.x, clickViewPos.y, 1, 1, GL_RGB, GL_UNSIGNED_BYTE, readColor);

if (sameColor(readColor, boundryColor) || sameColor(readColor, fillColor))//如果种⼦是边界点或填充颜⾊则直接退出

return;

glColor3ubv(fillColor);

//⼀开始⾮边界的种⼦，必然可以绘制扫描描线

//PointInt startPoint;

经济犯罪侦查//startPoint.x = clickViewPos.x;

//startPoint.y = clickViewPos.y;

seedsStack.push(clickViewPos);

//pixelStack.push(point);

float viewPosition[3];

double worldPosition[3];//世界坐标系

int saveX;

int xRight,xLeft;

int x,y;

//如果栈不为空

while(!pty())

{

//获取最顶端的元素

PointInt p();

//删除最顶端的元素

seedsStack.pop();

saveX = tempPoint.x;//绘制点的X坐标，从当前点向左向右扫描

x = tempPoint.x;

y = tempPoint.y;

dasglReadPixels(x, y, 1, 1, GL_RGB, GL_UNSIGNED_BYTE, &readColor);

//向右：如果没有到达右边界，就填充

while(!sameColor(readColor, boundryColor))

{

x=x+1;

glReadPixels(x, y, 1, 1,GL_RGB,GL_UNSIGNED_BYTE, &readColor);

}

xRight=x-1;

x=saveX-1;

glReadPixels(x, y, 1, 1, GL_RGB, GL_UNSIGNED_BYTE, &readColor);

//向左：如果没有到达左边界，就填充

while(!sameColor(readColor, boundryColor))

{

x=x-1;

神经皮肤黑变病

glReadPixels(x, y, 1, 1, GL_RGB,GL_UNSIGNED_BYTE, &readColor);

}

/保存左端点

xLeft=x+1;

//把当前像素点还原为世界坐标系中的点然后再绘制

glBegin(GL_LINES);

viewPosition[0] = xLeft;

viewPosition[1] = y;

viewPosition[2] = 0;

getWorldCoordPos(viewPosition, worldPosition);

glVertex3f(worldPosition[0], worldPosition[1], worldPosition[2]);

viewPosition[0] = xRight;

getWorldCoordPos(viewPosition, worldPosition);

glVertex3f(worldPosition[0], worldPosition[1], worldPosition[2]);

glEnd();

//从右边的点开始

x=xRight;

//检查上端的扫描线

searchNewLineSeed(seedsStack, xLeft, xRight, y+1);

searchNewLineSeed(seedsStack, xLeft, xRight, y-1);

}

//查新扫描线的种⼦

inline void CScanLineSeedFill::searchNewLineSeed(stack<PointInt>& stk, int xLeft, int xRight, int y)

神经网络法

{

unsigned char readColor[3];

int xt = xLeft;

bool findNewSeed = false;

while(xt <= xRight)

{

findNewSeed = false;

glReadPixels(xt, y, 1, 1, GL_RGB, GL_UNSIGNED_BYTE, readColor);

while(!sameColor(readColor, boundryColor) && !sameColor(readColor, fillColor) && (xt < xRight))

{

findNewSeed = true;

xt++;

glReadPixels(xt, y, 1, 1, GL_RGB, GL_UNSIGNED_BYTE, &readColor);

}

if(findNewSeed)

{

if(!sameColor(readColor, boundryColor) && !sameColor(readColor, fillColor) && (xt == xRight))//到达边界 {

stk.push(PointInt(xt, y));

}

else

stk.push(PointInt(xt - 1, y));//不到边界

}

/*向右跳过内部的⽆效点（边界点）, 即与边界相同颜⾊的点

（处理区间右端有障碍点的情况）*/

//xt或者在障碍点上，或者为右边端点

int tag = xt;

while((sameColor(readColor, boundryColor) || sameColor(readColor, fillColor)) && (xt < xRight))

{

xt++;

glReadPixels(xt, y, 1, 1, GL_RGB, GL_UNSIGNED_BYTE, &readColor);

}

if (tag == xt)//如果xt>= xRight or 都不为边界或已经填充则右移动

xt += 1;

}

程序运⾏结果如下：

本文发布于:2024-09-22 05:27:48，感谢您对本站的认可！

本文链接：https://www.17tex.com/xueshu/307752.html

上一篇：【Matlab学习手记】图像分割：区域生长

下一篇：点云分割和点云分类（点云语义分割）

标签：填充算法边界扫描线区域处理

留言与评论（共有 0 条评论）