算法别名:
漫水填充算法、种子填充算法(Seed Fill)
作用:
用于确定连接到多维数组中给定节点的区域,可以用来标记或者分离图像的一部分,实现如Ps中自动选区功能。
基本思想:
顾名思义就像洪水漫过一样,把一块连通的区域填满。
当然水要能漫过需要满足一定的条件,可以理解为满足条件的地方就是低洼的地方,水才能流过去。
在图像处理中就是给定一个种子点作为起始点,向附近相邻的像素点扩散,把颜色相同或者相近的所有点都找出来,并填充上新的颜色,这些点形成一个连通的区域。
算法参数:
起始节点(start node)
目标颜色(target color)
替换颜色(replacement color)
算法实现:
漫水填充算法实现最常见有四邻域像素填充法,八邻域像素填充法,基于扫描线的填充方法。根据代码实现方式又可以分为递归与非递归。
1、四邻域递归实现
将像素点(x,y)周围的上下左右四个点分别进行着色。
//Recursive 4-way floodfill, crashes if recursion stack is full
public void floodFill4(int x, int y, int newColor, int oldColor)
{
if(x >= 0 && x < width && y >= 0 && y < height
&& getPixel(x, y) == oldColor && getPixel(x, y) != newColor)
{
setPixel(x, y, newColor); //set color before starting recursion
floodFill4(x + 1, y, newColor, oldColor);
floodFill4(x - 1, y, newColor, oldColor);
floodFill4(x, y + 1, newColor, oldColor);
floodFill4(x, y - 1, newColor, oldColor);
}
}
2、八邻域递归实现
将一个像素点的上下左右