第12回 課題1の演習
再帰プログラムを使った二値画像のぬりつぶし
画像処理や迷路を探索するロボットのプログラムでは，塗りつぶしルーチンによく用いられる．例えば9×9の白黒二値画像があったとする．このまんなかの(5,5)から塗りつぶしを行う．塗りつぶしとはその座標に連結している黒画素を抜き出す操作である．
□■■□□□□□□ ■■□■■■■■□ □□□□■□■□□ ■■□□■■■□□ ■□□□■■□□□ □□□□□■□□□ □■■■■■■□■ □■□□□□□■□ ■□□□□□□■□
この結果次の画像が出力されるはずである．
□□□□□□□□□ □□□■■■■■□ □□□□■□■□□ □□□□■■■□□ □□□□■■□□□ □□□□□■□□□ □■■■■■■□□ □■□□□□□□□ □□□□□□□□□
ここで，連結しているかどうかは上下左右の4方向だけで判定する．(これを4連結と呼ぶ．ちなみに斜めも含めて判定する場合には，8連結と呼ぶ．)
このような塗りつぶしを実現するには,再帰を用いる．
これを再帰呼出を利用して実現するには，次のような関数を用意するものとする．
int fill(int x, int y); //塗りつぶし関数
入力画像のデータは上記の画像の白を0，黒を1としてあらかじめ初期化しておく．出力画像のデータはすべて白(0)とする．
関数fillは，座標(x,y)から塗りつぶしを始めて，塗りつぶした画素の数を返すとする．ただし, 座標は左上を(0,0)とし右下を(8,8)とする．また,返値だけでなく塗りつぶした画素位置に相当するoutputの(x,y)をすべて1,ぬりつぶした領域外は0のままとする．
そうすると，プログラムはだいだい次のような感じになる．
#include <stdio.h>
int fill(int x, int y);
int input[9][9] = {
{0,1,1,0,0,0,0,0,0},
{1,1,0,1,1,1,1,1,0},
{0,0,0,0,1,0,1,0,0},
{1,1,0,0,1,1,1,0,0},
{1,0,0,0,1,1,0,0,0},
{0,0,0,0,0,1,0,0,0},
{0,1,1,1,1,1,1,0,1},
{0,1,0,0,0,0,0,1,0},
{1,0,0,0,0,0,0,1,0}
};
int output[9][9] = {
{0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0},
};
int main(void)
{
int x,n;
scanf("%d", &x); //xをキーボードから入力
n = fill(x, x); //座標x,xから塗りつぶすことにする
printf("%d\n",n);
return 0;
}
int fill(int x, int y)
{
int left,right,up,down;
座標(x,y)がinputの範囲外であればダメ(0を返す)
inputの座標(x,y)を調べる．黒(1)でなければダメ(0を返す)
outputの座標(x,y)を調べる．すでに出力があれば(1ならば)ダメ(0を返す)
そうでないなら
outputの(x,y)を黒(1)に置き換える．
自分の上下左右を調べる．
つまり，left = fill(x-1, y);
right = fill(x+1,y);
up = fill(x,y-1);
down = fill(x,y+1);
返値は，left+right+up+down+1; //+1は自分自身の1画素分
}
たったこれだけで，複雑な塗りつぶしルーチンを記述できてしまう．
再帰プログラミングのポイントは，作成中の関数が予定どおりに動作できると思い込んでプログラムすることである．この場合，fillがちゃんと動作して，ちゃんと塗りつぶしを行って面積も正しく返してくれることを期待して，このように書き下す．
実行例
実行開始 5 ←キーボードから入力 20 ←20画素が連結されていた
練習課題
上記を参考にして，次の画像データで同様にある地点からぬりつぶし処理を行った結果，連結された画素数を答えるプログラムを作成せよ．塗りつぶし開始位置は，キーボードから入力させた数字がxのとき，座標(x,x)からとする．画像データは上記と異なり，12×12とする．当然，課題のプログラム中のデータはこれに合わすように変更する点に注意．