プログラム課題6
再帰プログラムを使った二値画像のぬりつぶし
画像処理や迷路を探索するロボットのプログラムでは，塗りつぶしルーチンによく用いられる．例えば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とする．当然，課題のプログラム中のデータはこれに合わすように変更する点に注意．
課題6の画像データ □□□□□□□■■■■■ □□■■□□□□□□□■ □■■□■■■■■■■■ □□□□□■□■□□□■ □■■■□■■■□■■■ □■□□□■■□□■■■ □□□□□□□□□■□■ □□■■■■■■□■□■ □■■□□□■□■□□■ □■□□□□■□■□□■ □■■■■■■■■□□■ ■□□□□□□□□■■■
提出方法
- 課題提出ページにログインし直接解答を記入すること
- 提出には，電子メール(xgate)のIDとパスワードが必要である．
- 課題提出ページは，学内からしかアクセスできない．自宅からは不可能．
- あらかじめ，自分のプログラムは別ファイルとして保存しておき，バックアップしておくこと．
- 正解でないプログラムは提出できないようになっている．
締め切り
- 原則として次回講義の前まで
- ただし，来年一月末までは再提出や遅刻提出を受け付けるのであきらめないこと．(遅刻提出は減点扱い)
- 最初から完璧を目指さないでよい．様子見ぐらいの気持ちで，とりあえず一回提出してみること