今天写程序中有一个地方用到了漫水填充（FloodFill）。所谓漫水填充，简单来说，如下图中左图，白布上有一块红色的斑点，在这个红色的斑点上点一下，就自动选中了和该点相连的红色的区域，接着将该区域替换成指定的颜色，如下图中右图所示。
算法很简单：
（1）将最初的点作为种子点压入栈中；
（2）弹出一个种子点，把它涂成目标颜色；
（3）对于种子点来说，和它相邻的有4个像素，判断这4个像素中的颜色是否是背景色，如果是，则作为新的种子点入栈；
（4）循环至栈空。
实现起来也很简单，一共只需要22行代码：
void FloodFill(ImageRgb24 img, Point location, Rgb24 backColor, Rgb24 fillColor)
{
int width = img.Width;
int height = img.Height;
if (location.X < 0 || location.X >= width || location.Y < 0 || location.Y >= height) return;
if (backColor == fillColor) return;
if (img[location.Y, location.X] != backColor) return;
Stack<Point> points = new Stack<Point>();
points.Push(location);
int ww = width -1;
int hh = height -1;
while (points.Count > 0)
{
Point p = points.Pop();
img[p.Y, p.X] = fillColor;
if (p.X > 0 && img[p.Y, p.X - 1] == backColor)
{
img[p.Y, p.X - 1] = fillColor;
points.Push(new Point(p.X - 1, p.Y));
}
if (p.X < ww && img[p.Y, p.X + 1] == backColor)
{
img[p.Y, p.X + 1] = fillColor;
points.Push(new Point(p.X + 1, p.Y));
}
if (p.Y > 0 && img[p.Y - 1, p.X] == backColor)
{
img[p.Y - 1, p.X] = fillColor;
points.Push(new Point(p.X, p.Y - 1));
}
if (p.Y < hh && img[p.Y + 1, p.X] == backColor)
{
img[p.Y + 1, p.X] = fillColor;
points.Push(new Point(p.X, p.Y + 1));
}
}
}
有这个算法为基础，类似photoshop的魔术棒选择工具就很容易实现了。漫水填充（FloodFill）是查找和种子点联通的颜色相同的点，魔术棒选择工具则是查找和种子点联通的颜色相近的点，将和初始种子点颜色相近的点压进栈作为新种子。
在photoshop cs5中新引进了快速选择工具，这个工具看起来很神奇，它背后的算法也研究了有些年了，就是抠图技术，有兴趣的可以去研究，这里有一篇很好的综述文章：Image and Video Matting: A Survey。
来自：xiaotie——漫水填充及Photoshop中魔术棒选择工具的实现
欢迎转载，转载请注明出处：蔓草札记 » 漫水填充及Photoshop中魔术棒选择工具的实现