シードフィルアルゴリズム

はるか昔に同じトピックを取り上げた気がするけど、ちょいと事情があってC#に移植したので改めて取り上げてみる。
シードフィルアルゴリズムというのは画像処理の一つで、画像上の１点を指定すると同じ領域を塗りつぶすアルゴリズムである。大抵のdrawingソフトにあるはずである。例えばMSペイントならペンキバケツのアイコンの処理がそれにあたる。
シードフィルアルゴリズムを実現する方法は速度とかメモリとか考えなければ簡単である。最初の点が塗りつぶせたらその周囲４点をまたスタート地点として再帰的に処理すればよい。というわけで何も考えずに作ると以下のようになる

public class Paint2D
{
    private short[,] image;
    private short BaseColor, PaintColor;

    //画像の設定
    public void SetImage(short[,] image)
    {
        this.image = image;
    }

    //塗りつぶす領域と塗りつぶす色
    void SetColor(short BaseColor, short PaintColor)
    {
        this.BaseColor = BaseColor;
        this.PaintColor = PaintColor;
    }
    //実行開始
    public void Execute(int startX, int startY)
    {
        if (IsEnablePaint(startX, startY))
        {
            Execute(startX - 1, startY);
            Execute(startX + 1, startY);
            Execute(startX, startY - 1);
            Execute(startX, startY - 1);
        }
    }

    //塗りつぶし条件
    protected bool IsEnablePaint(int x, int y)
    {
        if (image[y, x] == BaseColor)
        {
            image[y, x] = PaintColor;
            return true;
        }
        return false;
    }
}

なぜにshort型に？と思われるかもしれないが単なる私の癖である（ぇ　まあ気になるならジェネリックにしてくれれば画素を問わなくなる。
ここで重要なのは実行メソッドであるExecuteだ。最初の点を塗ったらその周囲４点を塗る。これだけで十分。ただし画像のサイズによってはスタックがものすごい食うので要注意。
ことろでこれ、画像の範囲チェックを行なっていない。もし行いたかったらIsEnablePaintを以下のように書き換えればよい

public class Paint2D
{

    //　・・・・中略

    //塗りつぶし条件
    protected bool IsEnablePaint(int x, int y)
    {
        if (x < 0 || y < 0 || image.GetLength(0) <= y || image.GetLength(1) <= x)
        {
            return false;
        }
        if (image[y, x] == BaseColor)
        {
            image[y, x] = PaintColor;
            return true;
        }
        return false;
    }
}

ところで塗りつぶし条件だが、「同じ領域を塗る」以外にも「特定のboundaryの内部を塗る」という塗り方も考えられる。そうすると以下の用になる。

public class Paint2D
{

    //　・・・・中略
    
    private short BoundaryColor;
    private short PaintColor;
    void SetColor(short BoundaryColor, short PaintColor)
    {
        this.BoundaryColor = BoundaryColor;
        this.PaintColor = PaintColor;
    }

    //塗りつぶし条件
    protected bool IsEnablePaint(int x, int y)
    {
        if (image[y, x] != BoundaryColor && image[y, x] != PaintColor)
        {
            image[y, x] = PaintColor;
            return true;
        }
        return false;
    }
}

これ以外にもさらに画像の領域チェックを入れたバージョンや、はたまたマスク画像に対して特定のビットを塗りたいとか、さらには別に塗らなくていいからその領域の座標列だけ欲しい・・・とまあきりがないわけです。こういうときはどうするか？オブジェクト指向の基本であるポリモーフィズムの出番ですね。シードフィルアルゴリズムを抽象化すると「ある特定の条件にあった連続領域を網羅的に処理する」アルゴリズムになります。というわけで抽象化すると以下のようにスッキリします。

public abstract class Paint2D
{
    //実行開始
    public void Execute(int startX, int startY)
    {
        if (IsEnablePaint(startX, startY))
        {
            Execute(startX - 1, startY);
            Execute(startX + 1, startY);
            Execute(startX, startY - 1);
            Execute(startX, startY - 1);
        }
    }
    //領域判定
    protected abstract bool IsEnablePaint(int x, int y);
}

見事にシードフィルのアルゴリズム部分だけが抽出されました。あとはIsEnablePaintをオーバーライドすれば好きなように塗るクラスが作れます。

//同じ部分を塗る
public class Paint2DOnBase<T> : Paint2D
{
    private T[,] image;
    private T BaseColor, PaintColor;

    //画像の設定
    public void SetImage(T[,] image)
    {
        this.image = image;
    }

    //塗りつぶす領域と塗りつぶす色
    void SetColor(T BaseColor, T PaintColor)
    {
        this.BaseColor = BaseColor;
        this.PaintColor = PaintColor;
    }

    //領域判定
    protected override bool IsEnablePaint(int x, int y)
    {
        if (base.image[y,x].Equals(BaseColor))
        {
            base.image[y,x] = PaintColor;
            return true;
        }
        return false;
    }
}
//特定のboundary内部を塗る
public class Paint2DInBoundary<T> : Paint2D
{
    private T[,] image;
    private T BoundaryColor, PaintColor;

    //画像の設定
    public void SetImage(T[,] image)
    {
        this.image = image;
    }

    //Boundaryの値と塗りつぶす色
    void SetColor(T BoundaryColor, T PaintColor)
    {
        this.BoundaryColor = BoundaryColor;
        this.PaintColor = PaintColor;
    }

    //領域判定
    protected override bool IsEnablePaint(int x, int y)
    {
        if (!base.image[y,x].Equals(BoundaryColor) && !base.image[y,x].Equals(PaintColor))
        {
            base.image[y,x] = PaintColor;
            return true;
        }
        return false;
    }
}

ちょっと無駄にジェネリックにして汎用性を増やしてみました。

というわけで、シードフィルのトピックでなくシードフィルアルゴリズムを用いてオブジェクト指向の基本であるポリモーフィズムの説明になってしましました（＾＾；