洪泛算法c语⾔代码，图像分割经典算法--《泛洪算法》 （FloodFill）
1.算法介绍
泛洪算法——Flood Fill，(也称为种⼦填充——Seed Fill)是⼀种算法，⽤于确定连接到多维数组中给定节点的区域。 它被⽤在油漆程序 的“桶”填充⼯具中，⽤于填充具有不同颜⾊的连接的，颜⾊相似的区域，并且在诸如围棋(Go)和扫雷(Minesweeper)之类的游戏中⽤于确定哪些块被清除。泛洪算法的基本原理就是从⼀个像素点出发，以此向周边的像素点扩充着⾊，直到图形的边界。
2.算法分类
泛洪填充算法采⽤三个参数：起始节点(start node)，⽬标颜⾊(target color)和替换颜⾊(replacement color)。 该算法查阵列中通过⽬标颜⾊的路径连接到起始节点的所有节点，并将它们更改为替换颜⾊。 可以通过多种⽅式构建泛洪填充算法，但它们都明确地或隐式地使⽤队列或堆栈数据结构。
根据我们是否考虑在连接⾓落处接触的节点，我们有两种变体：分别为⼋邻域泛洪(⼋种⽅向)和四邻域泛洪(四种⽅向)。 (1)四邻域泛洪
传统递归⽅式
传统的四邻域泛洪算法的思想是对于像素点(x,y)，将其着⾊之后将其周围的上下左右四个点分别进⾏着⾊。递归实现⽅式如下：
伪代码表⽰
Flood-fill (node, target-color, replacement-color):
1. If target-color is equal to replacement-color, return.
2. If the color of node is not equal to target-color, return.
3. Set the color of node to replacement-color.
4. Perform Flood-fill (one step to the south of node, target-color, replacement-color).
Perform Flood-fill (one step to the north of node, target-color, replacement-color).
Perform Flood-fill (one step to the west of node, target-color, replacement-color).
Perform Flood-fill (one step to the east of node, target-color, replacement-color).
5. Return.
巴士之家
函数实现
void floodFill4(int x, int y, int newColor, int oldColor)中国海洋石油报社
{
if(x >= 0 && x < w && y >= 0 && y < h && screenBuffer[y][x][y] == oldColor && screenBuffer[x] != newColor)
{
screenBuffer[y][x] = newColor;
floodFill4(x + 1, y , newColor, oldColor);
floodFill4(x - 1, y , newColor, oldColor);
floodFill4(x , y + 1, newColor, oldColor);
floodFill4(x , y - 1, newColor, oldColor);
}
}
四邻域泛洪算法改进
递归⽅式⾮常消耗内存，若所需着⾊的⾯积⾮常⼤，会导致溢出现象。因此，下⾯我们将介绍四邻域泛洪算法的⾮递归⽅式。
这⾥我们使⽤⼀个栈(或队列)来存储未被着⾊的点，然后依次将存在于着⾊空间内的点的上下左右的点加⼊栈(或队列)，依次着⾊直到栈(或队列)为空。基于栈(或队列)的显式实现(有时称为“Forest Fire算法”)在下⾯的伪代码中显⽰。 它类似于简单的递归解决⽅案，除了它不是进⾏递归调⽤，⽽是将节点推送到栈(或队列)中以供使⽤：
伪代码表⽰(Queue Way)
Flood-fill (node, target-color, replacement-color):
1. If target-color is equal to replacement-color, return.
2. If color of node is not equal to target-color, return.
3. Set Q to the empty Queue.
4. Set the color of node to replacement-color.
5. Add node to the end of Q.
6. While Q is not empty:
7. Set n equal to the first element of Q.
8. Remove first element from Q.
9. If the color of the node to the west of n is target-color,
set the color of that node to replacement-color and add that node to the end of Q.
10. If the color of the node to the east of n is target-color,
set the color of that node to replacement-color and add that node to the end of Q.
11. If the color of the node to the north of n is target-color,
set the color of that node to replacement-color and add that node to the end of Q.
12. If the color of the node to the south of n is target-color,
set the color of that node to replacement-color and add that node to the end of Q.
13. Continue looping until Q is exhausted.
14. Return.
代码实现(Stack Way)
void floodFill4Stack(int x, int y, int newColor, int oldColor)
{
if(newColor == oldColor) return; //avoid infinite loop
emptyStack();
static const int dx[4] = {0, 1, 0, -1};
static const int dy[4] = {-1, 0, 1, 0};
if(!push(x, y)) return;
while(pop(x, y))
{病案追踪
screenBuffer[y][x] = newColor;
for(int i = 0; i < 4; i++) {
int nx = x + dx[i];
上海电视大学浦东分校
int ny = y + dy[i];
if(nx > 0 && nx < w && ny > 0 && ny < h && screenBuffer[ny][nx] == oldColor) {
if(!push(nx, ny)) return;
}
}
}
}
(2)⼋邻域泛洪
⼋邻域算法是将⼀个像素点的上下左右，左上，左下，右上，右下都进⾏着⾊。
递归⽅式
void floodFill8(int x, int y, int newColor, int oldColor)
{
if(x >= 0 && x < w && y >= 0 && y < h && screenBuffer[y][x][y] == oldColor && screenBuffer[x] != newColor) {
screenBuffer[y][x] = newColor;
香港成人电视台
floodFill8(x + 1, y , newColor, oldColor);
floodFill8(x - 1, y , newColor, oldColor);
floodFill8(x , y + 1, newColor, oldColor);
floodFill8(x , y - 1, newColor, oldColor);
floodFill8(x + 1, y + 1, newColor, oldColor);
floodFill8(x - 1, y - 1, newColor, oldColor);
floodFill8(x - 1, y + 1, newColor, oldColor);
floodFill8(x + 1, y - 1, newColor, oldColor);
}
}
⾮递归⽅式(借⽤栈的⽅式)
void floodFill8Stack(int x, int y, int newColor, int oldColor)
{
if(newColor == oldColor) return; //avoid infinite loop
emptyStack();
static const int dx[8] = {0, 1, 1, 1, 0, -1, -1, -1};
static const int dy[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
if(!push(x, y)) return;
while(pop(x, y))
四川商业高等专科学校
{
screenBuffer[y][x] = newColor;
for(int i = 0; i < 8; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if(nx > 0 && nx < w && ny > 0 && ny < h && screenBuffer[ny][nx] == oldColor) {
if(!push(nx, ny)) return;
}
}
}
}
(3)描绘线算法(Scanline Fill)
利⽤填充线来加速算法， 它不是在堆栈上推动每个潜在的未来像素坐标，⽽是检查相邻线(前⼀个和下⼀个)以到可能在未来通过中填充的相邻段， 线段的坐标(开始或结束)被推到堆栈上。 在⼤多数情况下，该扫描线算法⾄少⽐每像素算法快⼀个数量级。
该算法的过程是：先将⼀条线上的像素点进⾏着⾊，然后依次向上下扩张，直到着⾊完成。算法实现如下：递归⽅式
void floodFillScanline(int x, int y, int newColor, int oldColor){
if(newColor==oldColor) return;
if(screen[x][y]!=oldColor) return;
int x1=x;
while(x1=0&&screen[x1][y]==oldColor){
screen[x1][y]=newColor;
x1--;
}
x1=x;
while(x10&&screen[x1][y]==newColor){
if(y>0&&screen[x1][y+1]==oldColor) floodFillScanline(x1,y+1,newColor,oldColor);
x1--;
}
x1=x;
while(x10&&screen[x1][y]==newColor){
if(y>0&&screen[x1][y-1]==oldColor) floodFillScanline(x1,y+1,newColor,oldColor);
x1--;
}
}
⾮递归⽅式
void floodFillScanline(int x, int y, int newColor, int oldColor){
if(newColor==oldColor) return;
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议