图像填充算法

封闭连通域的图像填充是个常见的算法，最近有机会接触到大图像的例子，做一下总结。

这类问题最基本的算法是种子填充。即先给出封闭区域内的一点，从这点出发搜索邻域，只要不到边界，就把相邻点纳入连通域，赋予填充色。边界的判断比较灵活，可以使用固定颜色，也可以用一定阈值的色彩容差，类似photoshop中的魔棒。其他更复杂的计算自然也可以。

邻域的搜索是填充的重点。最简单的算法就是递归，写出来也就几行代码，像下面的样子：

FillShape(int   x,   int   y)
{
    if( !IsBrim(x,y) )
    {
        SetPixel(x,y);
        FillShape(x+1,   y);
        FillShape(x-1,   y);
        FillShape(x,   y+1);
        FillShape(x,   y-1);
     }
}

只要当前点不是边缘，就填充，然后递归相邻的点。这个算法是4连域，改成8连域也是很简单的事。

上述算法简单直观，但存在一些问题。首先它需要逐点搜索，效率不高。其次，在实际的编程中，递归运算是很消耗资源的事情。函数的递归需要压栈，即把当前函数的地址和状态量放到系统的堆栈中，进入下一个状态。实际操作系统的资源总是有限的，如果递归的层数太多，系统的堆栈会溢出，这个是用户控制不了的。这样当我们处理稍大一些的图像时，往往会出现堆栈溢出的错误，使程序无法运行。

针对这些问题，我们先做修改，把填充目标由点改为线。也即使用线扫描的方式搜索连通域。进入一个种子点后，在X方向从左向右逐点搜索连通点，填充，直到遇到中断点停止，然后从这些连通点开始，取上下点递归，伪代码见下：

FillShape(int   x,   int   y)
{
    if( !IsBrim(x,y) )
    {
// 向左填充，FillToLeft(x,y);
        nleft = x;
        while(!IsBrim(nleft,y))
       {
            SetPixel(nleft,y);
            nleft--;
        }
// 向右填充，FillToRight(x,y);
        nright = x;
        while(!IsBrim(nright,y))
       {
            SetPixel(nright,y);
            nright++;
        }
// 上下层的点递归
        for(i=nleft+1;i<right;i++)
        {
            FillShape(x,y+1);
            FillShape(x,y-1);
        }
     }
}

这样做减少了递归次数，提高了效率。但是还没有解决递归的根本缺陷，如果遇到大区域填充，仍然可能出现堆栈溢出。根本的解决之道是放弃递归。研究表明，任何递归算法都是可以修改为使用循环的非递归算法。修改的关键是两步：一、设计并实现一个自己的栈，保存原来递归出现的中间状态量，这样资源的利用率大大提高。二、在循环处理代码中，至少实现起始层和下一层递归的功能，这样才能把中间状态压入自己的栈中以备处理。
经过修改的非递归算法如下：（为了简洁起见，我把具体的代码用函数名代替）：

// 构建堆栈代码
PushStack();// 压栈
PopStack();// 出栈
SetStackEmpty();// 清空栈
int IsStackEmpty();// 判断栈是否为空
 
FillShape(int   x,   int   y)
{
    FillToLeft(x,y);
    FillToRight(x,y);
    SetStackEmpty();
    PushStack();
    while(!IsStackEmpty())
    {
        PopStack();
        xLeft = getstack_left();
        xRight = getstack_right();
        // 处理上边
        y=y-1;
        FillToLeft(xLeft,y);
        i=xLeft;
        while( i <= xRight)
        {
            FillToRight(i,y);
            PushStack();
        }
        // 处理下边
        y=y+2;
        FillToLeft(xLeft,y);
        i=xLeft;
        while( i <= xRight)
        {
            FillToRight(i,y);
            PushStack();
        }
    }
}