静觅 崔庆才的个人站点 - Python爬虫教程

0%

OpenGL绘图实例三之种子填充算法

作者 发表于 分类于 阅读次数： 本文字数： 7.4k 阅读时长 ≈ 7 分钟

综述

博主研究了一下午加一晚上，终于把种子填充算法实现出来并把机器人填充完毕，路途很艰辛，不过也学到了很多，在此和大家一起分享。

吐槽

与我不是同学的小伙伴，请自动忽略，我是来吐槽教材的。 在此不得不吐槽一下，不得不说教材实在太坑爹了。对于种子填充算法的后半部分，下一个种子点的寻找过程中，从 while(x<=xright)开始，我实在无法搞懂它里面的神逻辑，最初我认为它是对的，后来按照它的思路实现之后，填充基本上是错误的，比如圆角矩形下方的部分，它就无法正常填充。根本原因还是它的下一步种子点找错了，而博主依然在固执地 DeBug，看看是不是我哪里编码有问题。后来，干脆放弃了书上的逻辑了，自己改写了搜寻下一个种子点的算法，最后终于成功。 另外，教材上的这些伪代码写得也是太伪，算了，这不是重点，言归正传。

基本梳理

在博主的研究过程中，遇到了许许多多的小问题，在这里统一做一下总结，也希望大家少走弯路，吸取我的经验教训。

1.点的定义

在这里我们避免不了要使用点，一个点包括了 2 个元素，一个是横坐标一个是纵坐标，所以我们可以直接把它定义为一个结构体。

1
2
3
4
5
 
struct Point
{
	int x;
	int y;
};

这样的话，我们就可以直接声明一个 Point 类型的变量使用了，既方便又直观。

2.栈的使用

对于种子填充算法，肯定避免不了使用栈的，在这里博主分享一下一些使用心得。 栈的引入 C++代码中，可以直接用下面的代码来导入

1
2
 
#include <stack>
using namespace std;

注意，这里一定记得加上 using namespace std 这句话，否则会出现 stack 未定义的错误，哈哈哈，深有体会。 栈的定义 引入了栈之后，我们就可以直接来声明一个栈了

1
 
stack<Point> pixelStack;

其中，需要加一个尖括号，尖括号中声明了 Point 类型，这样我们就可以使用它了 取栈顶元素 C++中取栈顶元素是很坑的，有一个 top 方法，还有一个 pop 方法。 其中 top 方法是只取得栈顶的元素而不移除它，pop 方法是直接移除栈顶元素，没有返回值。 所以我们要想取出栈顶元素并移除的话，就要分别调用这两个方法

1
2
3
4
 
//获取最顶端的元素
Point tempPoint=pixelStack.top();
//删除最顶端的元素
pixelStack.pop();

是不是不友好？不友好的话，那就自己去定义一个新方法吧，我就先不这么干啦。 判断栈非空 判断当前的栈是否已经为空，只需要调用 empty 方法就可以了

1
2
3
 
while(!pixelStack.empty()){
//code
}

这里是一个 while 循环，如果栈为非空的话不断循环。 关于栈置空 教材中的种子填充算法中用到了栈置空，不过我感觉没有必要这么做，因为在方法最前面是新声明的栈变量，它一定是空的。不过如果非要置空的话，可以利用下面的代码

1
2
3
 
while(!pixelStack.empty()){
    pixelStack.pop();
}

如果栈不为空，就一直取元素，就可以把它置空啦。

3.关于 glColor3b 和 glColor3ub

这的确也是坑得博主不浅，之前一直在用 glColor3b 这个方法来定义颜色，奇怪的是 glColor3b(255,0,0) 竟然不是红色，而是黑色！就是因为这个颜色问题，导致我在比对颜色的过程中走了很多弯路。在这里做一下说明 glColor3b()需要传入的是 byte 类型，它的数值范围是-128-127，也就是有符号数，我传入 255，由于越界了，255 这个数就相当于-128，难怪不变红啊。 glColor3ub()需要传入的是 unsigned byte 类型，范围是 0-255，无符号数，那么在这里我们传入 255,0,0 这三个数，就变成红色了。

4.取得某像素颜色

我想说的是，这也是个深坑啊，一下午的 Debug 全归它身上了。 获取某个像素的这个函数是

1
 
void glReadPixels(GLint x,GLint y,GLsizesi width,GLsizei height,GLenum format,GLenum type,GLvoid *pixel);

函数说明如下：

该函数总共有七个参数。前四个参数可以得到一个矩形，该矩形所包括的像素都会被读取出来。（第一、二个参数表示了矩形的左下角横、纵坐标，坐标以窗口最左下角为零，最右上角为最大值；第三、四个参数表示了矩形的宽度和高度） 第五个参数表示读取的内容，例如：GL_RGB 就会依次读取像素的红、绿、蓝三种数据，GL_RGBA 则会依次读取像素的红、绿、蓝、alpha 四种数据，GL_RED 则只读取像素的红色数据（类似的还有 GL_GREEN，GL_BLUE，以及 GL_ALPHA）。如果采用的不是 RGBA 颜色模式，而是采用颜色索引模式，则也可以使用 GL_COLOR_INDEX 来读取像素的颜色索引。目前仅需要知道这些，但实际上还可以读取其它内容，例如深度缓冲区的深度数据等。 第六个参数表示读取的内容保存到内存时所使用的格式，例如：GL_UNSIGNED_BYTE 会把各种数据保存为 GLubyte，GL_FLOAT 会把各种数据保存为 GLfloat 等。 第七个参数表示一个指针，像素数据被读取后，将被保存到这个指针所表示的地址。注意，需要保证该地址有足够的可以使用的空间，以容纳读取的像素数据。例如一幅大小为 256*256 的图象，如果读取其 RGB 数据，且每一数据被保存为 GLubyte。

好了，那么重点来了，这个方法的坐标基准点是在画布的左下角！！而我们绘图的基准点是在画布的正中心！！所以我在获取某个点的颜色的时候一直都是错误的结果，这样的话在使用的时候我们的 xy 坐标值就要加上画布宽高的一半才能正常获取到像素的颜色，希望大家一定注意！！ 那么我们如何来使用呢？实例如下，首先定义 GLByte 的数组

1
 
GLubyte iPixel[3];

另外还有画布的宽度高度的一半变量

1
 
int halfWidth,halfHeight;

我们可以调用如下的方法来获取(x,y)这个点像素的值

1
 
glReadPixels(x+halfWidth,y+halfHeight,1,1,GL_RGB,GL_UNSIGNED_BYTE,&iPixel);

在这里第五个参数我们定义了 GL_RGB，第六个参数我们定义了 GL_UNSIGNED_BYTE，最后是传入了数组的引用。 所以在调用这个方法之后，iPixel 数组里面的三个值就已经赋值为了该点的 RGB 值，可以拿来做下一步的判断。 比如我们边界可以定义为

1
 
GLubyte oldColor[3]={255,255,255};

在比较的时候就可以用下面的判别式

1
 
iPixel[0]!=borderColor[0]&&iPixel[1]!=borderColor[1]&&iPixel[2]!=borderColor[2]

这里我们是依次比较了三个 RGB 值是否与边界的 RGB 值相等，不过，有意思的是，识别颜色的这个方法，黑色的 RGB 值会识别成 1,1,1，而有时候在我调试的时候会识别为 0,1,1。我在想是不是系统计算误差问题，如果真是的话，因为这个小小的误差就影响了我们的判别条件岂不是亏大了？那么在这里我就定义了一个方法，允许一定的误差，这个误差姑且就称为 PS 里面的容差吧。

1
2
3
4
5
6
7
8
9
10
 
//传入两个颜色的RGB值，比较是否相同，容差为dis
bool sameColor(int r1,int g1,int b1,int r2,int g2,int b2){
	//容差度
	int dis = 10;
	if(abs(r1-r2)<=dis&&abs(g1-g2)<=dis&&abs(b1-b2)<=dis){
		return true;
	}else{
		return false;
	}
}

那么我们的判定条件就改为了

1
 
!sameColor(iPixel[0],iPixel[1],iPixel[2],borderColor[0],borderColor[1],borderColor[2])

这样系统误差便不会影响了。

5.下一个种子点的选取

教材上的种子点选取算法有点搞不懂，我按照上面的思路实现出来，在填充的时候出现了一系列问题。后来干脆放弃了教材中的方法，自己改写了一下。 思路大体上是这样的。

在填充完一行后，这一行最左边的像素点我们定义为(xLeft,y)，最右边的像素我们定义为(xRight,y)，扫描上一行找寻下一个种子点，这里 y 就要增加 1，如果(xRight,y+1)这个点不是边界不是已经填充的点，那么这个点就可以作为种子点压入堆栈。如果这个点是边界或者是已经填充的点，那么就继续往左搜索，如果找到既不是边界又未填充的点，那么这个点就是种子点，压入堆栈。如果一直往左找到 xLeft 还是没有找到的话，就不存在下一个种子点了。下一行扫描线也是同样的原理，y 要在这个基础上减去 2 即可。

恩，不知道大家有没有看懂，这是我自己想出来的方法，不敢保证完全正确，在此仅供参考。 如果大家真的可以按照教材中的方法实现成功的话，希望告诉我一下，感激不尽。

方法实现

恩，重要的地方都已经点明了，下面就直接附上我的种子填充算法吧！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
 
//种子填充算法
void zzFill(int startX,int startY,int r,int g,int b){
	stack<Point> pixelStack;
	//x,y是给定的种子像素点，rgb就是要填充的颜色的RGB值
	Point point  = {startX,startY};
	pixelStack.push(point);
	int saveX;
	int xRight,xLeft;
	int x,y;
	//如果栈不为空
	while(!pixelStack.empty()){
		//获取最顶端的元素
		Point tempPoint=pixelStack.top();
		//删除最顶端的元素
		pixelStack.pop();
		saveX=tempPoint.x;
		x=tempPoint.x;
		y=tempPoint.y;
		glReadPixels(x+halfWidth,y+halfHeight,1,1,GL_RGB,GL_UNSIGNED_BYTE,&iPixel);
		//如果没有到达右边界，就填充
		while(!sameColor(iPixel[0],iPixel[1],iPixel[2],borderColor[0],borderColor[1],borderColor[2])){
			glPoint(x,y,r,g,b);
			x=x+1;
			glReadPixels(x+halfWidth,y+halfHeight,1,1,GL_RGB,GL_UNSIGNED_BYTE,&iPixel);
		}
		xRight=x-1;
		x=saveX-1;
		glReadPixels(x+halfWidth,y+halfWidth,1,1,GL_RGB,GL_UNSIGNED_BYTE,&iPixel);
		//如果没有到达左边界，就填充
		while(!sameColor(iPixel[0],iPixel[1],iPixel[2],borderColor[0],borderColor[1],borderColor[2])){
			glPoint(x,y,r,g,b);
			x=x-1;
			glReadPixels(x+halfWidth,y+halfWidth,1,1,GL_RGB,GL_UNSIGNED_BYTE,&iPixel);
		}
		//保存左端点
		xLeft=x+1;
		//从右边的点开始
		x=xRight;
		//检查上端的扫描线
		y=y+1;
		while(x>=xLeft){
			glReadPixels(x+halfWidth,y+halfWidth,1,1,GL_RGB,GL_UNSIGNED_BYTE,&iPixel);
			if(!sameColor(iPixel[0],iPixel[1],iPixel[2],borderColor[0],borderColor[1],borderColor[2])&&!sameColor(iPixel[0],iPixel[1],iPixel[2],r,g,b)){
				//如果上方的点不是边界点，直接压入
				Point p={x,y};
				pixelStack.push(p);
				//压入之后停止循环
				break;
			}else{
				x--;
				glReadPixels(x+halfWidth,y+halfWidth,1,1,GL_RGB,GL_UNSIGNED_BYTE,&iPixel);
			}
		}
		//检查下端的扫描线
		y=y-2;
		//从右边的点开始
		x=xRight;
		while(x>=xLeft){
			glReadPixels(x+halfWidth,y+halfWidth,1,1,GL_RGB,GL_UNSIGNED_BYTE,&iPixel);
			if(!sameColor(iPixel[0],iPixel[1],iPixel[2],borderColor[0],borderColor[1],borderColor[2])&&!sameColor(iPixel[0],iPixel[1],iPixel[2],r,g,b)){
				//如果上方的点不是边界点，直接压入
				Point p={x,y};
				//压入之后停止循环
				pixelStack.push(p);
				break;
			}else{
				x--;
				glReadPixels(x+halfWidth,y+halfWidth,1,1,GL_RGB,GL_UNSIGNED_BYTE,&iPixel);
			}
		}
	}
}

以上便是我实现的种子填充算法，仅供参考 在这里我们用到了 glPoint 画点的方法，这是我们定义的，方法如下，为了便于调试，每画一个点刷新一下，这样我们就可以看到绘制的全部动态效果。

1
2
3
4
5
6
7
8
9
 
//画点
void glPoint(int x,int y,int r,int g,int b){
	glColor3ub (r,g,b);
	glPointSize(1);
	glBegin(GL_POINTS);
	glVertex2i(x,y);
	glEnd();
	glFlush();
}

以上便是画点的函数

方法使用

种子填充算法肯定要在我们绘制完机器人之后使用，任意选取某个四连通区域的点，传入 xy 坐标值还有要填充的颜色的 RGB 值，就可以成功实现填充。 在上一篇机器人的基础上，我们在画机器人的方法最后加入下面的代码，即可实现填充。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
 
//灰色:195,195,195
//黄色:255,243,0
//红色:237,28,36
//深灰色:126,126,126
//脖子
zzFill(0,70,195,195,195);
//头
zzFill(-50,110,195,195,195);
zzFill(0,93,195,195,195);
//肚子
zzFill(-50,0,195,195,195);
//耳朵
zzFill(-80,115,126,126,126);
zzFill(80,115,126,126,126);
//肚子三角
zzFill(-20,-10,255,243,0);
//肚子红色圆
zzFill(0,0,237,28,36);
//zzFill(-50,0,128,255,33);
//大臂
zzFill(-90,30,126,126,126);
zzFill(90,30,126,126,126);
//小臂
zzFill(-90,-20,126,126,126);
zzFill(90,-20,126,126,126);
//手
zzFill(-75,40,195,195,195);
zzFill(75,40,195,195,195);
//手
zzFill(-95,-47,195,195,195);
zzFill(95,-47,195,195,195);
//大腿连接处
zzFill(-40,-64,195,195,195);
zzFill(40,-64,195,195,195);
//大腿
zzFill(-40,-100,126,126,126);
zzFill(40,-100,126,126,126);
//脚踝
zzFill(-40,-121,195,195,195);
zzFill(40,-121,195,195,195);
//脚掌
zzFill(-40,-130,126,126,126);
zzFill(40,-130,126,126,126);
system("pause");

注意，有个很奇怪地方是绘制完了之后机器人就不见了，所以在这里加入了 system(“pause”)方法来暂停一下就好啦。 其他的代码基本都是上一篇中的了，大家自行整理。

运行结果

运行结果截图如下 20150419015002 恩，就是这样！

总结

以上便是博主利用种子填充算法来实现的机器人的颜色填充，在此分享给大家，希望对大家有帮助！ 如有问题和错误，欢迎大家给予我批评和指正，谢谢！