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

    这类问题最基本的算法是种子填充。即先给出封闭区域内的一点，从这点出发搜索邻域，只要不到边界，就把相邻点纳入连通域，赋予填充色。边界的判断比较灵活，可以使用固定颜色，也可以用一定阈值的色彩容差，类似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

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

    经过修改的非递归算法如下：（为了简洁起见，我把具体的代码用函数名代替）：

// 构建堆栈代码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();        }    }}

这段代码的思路是，仍然使用扫描线进行邻域填充，使用自己的堆栈来记录中间状态。完成一条扫描线的填充后，把前一个扫描线状态压入栈，弹出时，向上下搜索相邻的扫描线段，填充，压栈。直到栈中状态都被弹出处理为止。

    至此，填充算法提高了效率，也避免了系统堆栈溢出。而递归算法，更适合用于原理说明和较少层次的运算，对图像的处理应当慎用并修改之。