加载中…[数据结构与算法: 经典算法]种子填充的优化[zz]
(2012-11-23 10:35:09)
标签：
种子填充杂谈 |
分类： 图像处理与分析 |
原文地址：http://www.richardma.org/blog/?p=167418
[数据结构与算法: 经典算法]种子填充的优化
上篇说到种子填充（Flood Fill）算法，我们在研究这个算法之后发现它存在一些缺陷，今天我们来寻找更好的算法，也就是工程中能够应用的算法。
1. 当填充区域变大时，递归层次增多，可能造成溢出
2. 算法效率较低，多数节点需要被访问四次，递归调用函数时空开销大
上面两条是我们找到的关于种子填充算法的缺陷，第一条是由于递归定义自身的缺陷造成。现代计算机实现递归调用的时空代价还是比较大的，但由于计算机内存的增加和计算速度的加快，这个代价在递归层次较少时是可以容忍的。
使用队列的种子填充算法
如果修改算法为非递归则会避免很多问题。现在我们增加一个队列的存储空间来将种子填充改为非递归程序。如果用MAX_ROW表示二维数组的最大行数，MAX_COL表示二维数组的最大列数，则我们使用数组实现的队列最多需要MAX_ROW * MAX_COL + 1个元素。
算法描述
Flood-fill （点坐标， 目标颜色， 替换颜色）
- 将队列Q清空
- 如果点坐标的颜色不是目标颜色，则退出
- 将点坐标加入队尾
- 取队头元素，存入n
- 如果n坐标的颜色是目标颜色，则替换为替换颜色
- 删去队列头元素
- 如果n坐标左侧坐标颜色为目标颜色，替换为替换颜色，n坐标左侧坐标入队
- 如果n坐标右侧坐标颜色为目标颜色，替换为替换颜色，n坐标右侧坐标入队
- 如果n坐标上方坐标颜色为目标颜色，替换为替换颜色，n坐标上方坐标入队
- 如果n坐标下方坐标颜色为目标颜色，替换为替换颜色，n坐标下方坐标入队
- 如果队列Q不为空，则返回04继续执行，否则退出
C语言代码
void
seed_fill (int array[MAX_ROW][MAX_COL],
int row_size, int col_size,
int x, int y, int t_color, int r_color)
{
if (x < 0 || x >= col_size ||
y < 0 || y >= row_size ||
array[y][x] != t_color) {
return;
}
int queue[MAX_ROW * MAX_COL + 1][2];
int head = 0, end = 0;
int tx, ty;
queue[end][0] = x;
queue[end][1] = y;
end++;
printf("** Queue situatoins **\n");
while (head < end) {
int i;
for (i=head; i<end; i++)
printf("%d %d | ", queue[i][1], queue[i][0]);
printf("\n");
tx = queue[head][0];
ty = queue[head][1];
if (array[ty][tx] == t_color) {
array[ty][tx] = r_color;
}
head++;
if (tx-1 >= 0 && array[ty][tx-1] == t_color) {
array[ty][tx-1] = r_color;
queue[end][0] = tx-1;
queue[end][1] = ty;
end++;
}
if (tx+1 < col_size && array[ty][tx+1] == t_color) {
array[ty][tx+1] = r_color;
queue[end][0] = tx+1;
queue[end][1] = ty;
end++;
}
if (ty-1 >= 0 && array[ty-1][tx] == t_color) {
array[ty-1][tx] = r_color;
queue[end][0] = tx;
queue[end][1] = ty-1;
end++;
}
if (ty+1 < row_size && array[ty+1][tx] == t_color) {
array[ty+1][tx] = r_color;
queue[end][0] = tx;
queue[end][1] = ty+1;
end++;
}
}
return;
}
由于队列要存储二维坐标，所以使用了一个二维数组，其实是为了每个位置可以存储两个数据，即X， Y坐标，这个实现也可以使用一个结构体完成。
以行为单位的算法
这个算法使用队列替换了原先的递归实现，但都是以点为单位进行操作。我们下一个算法将以行为单位进行操作。
算法描述
Flood-fill （点坐标， 目标颜色， 替换颜色）
- 将队列Q清空
- 如果点坐标的颜色不是目标颜色，则退出
- 将点坐标加入队尾
- 取队头元素，存入n
- 如果n坐标的颜色是目标颜色，则继续，否则跳转到11
- 设置w和e两个横坐标变量为n的横坐标
- 当w左侧坐标颜色为目标颜色时，将w左侧横坐标赋给w
- 当e右侧坐标颜色为目标颜色时，将e右侧横坐标赋给e
- 将w和e之间的左右坐标点都替换为替换颜色，同时如果坐标点上方和下方为目标颜色时，将该点入队
- 删除队头元素
- 如果队列Q不为空，则返回04继续执行，否则退出
C语言代码
void
seed_fill (int array[MAX_ROW][MAX_COL],
int row_size, int col_size,
int x, int y, int t_color, int r_color)
{
if (x < 0 || x >= col_size ||
y < 0 || y >= row_size ||
array[y][x] != t_color) {
return;
}
int queue[MAX_ROW * MAX_COL + 1][2];
int head = 0, end = 0;
int tx, ty;
queue[end][0] = x;
queue[end][1] = y;
end++;
printf("** Queue situatoins **\n");
while (head < end) {
int i;
for (i=head; i<end; i++)
printf("%d %d | ", queue[i][1], queue[i][0]);
printf("\n");
tx = queue[head][0];
ty = queue[head][1];
if (array[ty][tx] == t_color) {
int w, e, i;
w = tx; e = tx;
while (w-1 >= 0 && array[ty][w-1] == t_color) w--;
while (e+1 < col_size && array[ty][e+1] == t_color) e++;
for (i=w; i<=e; i++) {
array[ty][i] = r_color;
if (ty-1 >=0 && array[ty-1][i] == t_color) {
queue[end][0] = i;
queue[end][1] = ty-1;
end++;
}
if (ty+1 < row_size && array[ty+1][i] == t_color) {
queue[end][0] = i;
queue[end][1] = ty+1;
end++;
}
}
}
head++;
}
return;
}
上述两个算法都使用了队列来替代原先的递归操作，避免了工程上的很多问题。第二个算法以行为单位进行操作，降低了每个元素的访问次数，提高了算法效率
喜欢
0
赠金笔