区域填充算法c

⑴ 用队列实现种子填充算法的非递归

一、种子填充算法（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） “4-联通”和“8-联通”填充效果

并不能仅仅因为图1的填充效果就认为“8-联通算法”一定比“4-联通算法”好，应该根据应用环境和实际的需求选择联通搜索方式，在很多情况下，只有“4-联通算法”才能得到正确的结果。
1.1 注入填充算法（Flood Fill Algorithm）
注入填充算法不特别强调区域的边界，它只是从指定位置开始，将所有联通区域内某种指定颜色的点都替换成另一种颜色，从而实现填充效果。注入填充算法能够实现颜色替换之类的功能，这在图像处理软件中都得到了广泛的应用。注入填充算法的实现非常简单，核心就是递归和搜索，以下就是注入填充算法的一个实现：

164 void FloodSeedFill(int x, int y, int old_color, int new_color)
165 {
166 if(GetPixelColor(x, y) == old_color)
167 {
168 SetPixelColor(x, y, new_color);
169 for(int i = 0; i < COUNT_OF(direction_8); i++)
170 {
171 FloodSeedFill(x + direction_8[i].x_offset,
172 y + direction_8[i].y_offset, old_color, new_color);
173 }
174 }
175 }

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

15 typedef struct tagDIRECTION
16 {
17 int x_offset;
18 int y_offset;
19 }DIRECTION;

79 DIRECTION direction_8[] = { {-1, 0}, {-1, 1}, {0, 1}, {1, 1}, {1, 0}, {1, -1},{0, -1}, {-1, -1} };

这个是搜索类算法中常用的技巧，无需做太多说明，其实只要将其替换成如下direction_4的定义，就可以将算法改成4个联通方向填充算法：

80 DIRECTION direction_4[] = { {-1, 0}, {0, 1}, {1, 0}, {0, -1} };

图2就是应用本算法实现的“4-联通”和“8-联通”填充效果：

⑵ 填充算法的注入填充区域算法

注入填充算法(FloodFill Algorithm)用于内部定义区域，以改变整个区域的颜色属性，它把区域内的原像素点值改变成另一种像素点值。算法3.2用于填充八连通的内部定义区域。算法中，read &iexcl; pixel(x; y)表示读出像素点(x; y)像素点值。old-value为像素点的原值, new-value为将要填充的新值。
[算法3.2] 注入填充区域算法。
Procere flood-fill-8(x,y,old-value,new-value)
BEGIN
IF read-pixel(x,y)=old-value THEN
BEGIN
write-pixel(x,y,new-value)
flood-fill-8(x,y-1,old-value,new-value)
flood-fill-8(x,y+1,old-value,new-value)
flood-fill-8(x-1,y,old-value,new-value)
flood-fill-8(x+1,y,old-value,new-value)
flood-fill-8(x+1,y-1,old-value,new-value)
flood-fill-8(x+1,y+1,old-value,new-value)
flood-fill-8(x-1,y-1,old-value,new-value)
flood-fill-8(x-1,y+1,old-value,new-value)
END
ENDIF
END
此算法所采用的基本方法是首先确定(x; y)点的像素点是否在区域内尚未被访问过的那一部分之中，也就是说，如果这个像素点的值是原始值old-value，则需要把它改为填充的值new-value，然后按八连通区域性质先后访问其八个相邻的像素点，当访问其中每一个近邻像素点时，都要进行递归调用。此算法通过在四个方向而不是八个方向上扩展，就可以用来填充一个内部定义的四连通式区域。这时程序只要有前面四个flood-fill-8(...)语句就可以了.

⑶ 区域增长算法（C#实现)

这个不是跟区域填充差不多么?
如果每次都要逐个单元扫描 不是卡死?
你可以去参考下区域填充算发 虽然那个算法也不怎么样 不过至少每次寻找新点时候 不用逐个重新扫描;

你是想做识别么?

是逐个扫描一次..问题当标识好之后,,当你选择下一个种子点的时候,又要重新扫描.这样是很麻烦;
你可以采用区域填充..他首先确定一个种子点 然后他由这个种子点出发.当走到一路尽头的时候就会返回 延下一个方向走..这样就避免了逐点扫描
例如有这么一个方块
A B C D E F
G H I J K L
M O P Q R S
T U V W X Y
假如冲 Q开始先左走 PQ关系小 则 P跟Q一样 依次走到M 每一个都标记了 当然其中也有些不符合要求 然后M开始往上走....当走到一个点发现他四周所有的位置都被标记 而退回上一个点 继续下一个方向..依次走完 这就是一个递归的方法,,而递归本质也是栈的使用(跟4皇后求法 也有点类似)