輪郭線追跡

輪郭線追跡プログラム

/*	輪郭線追跡プログラム　8連結
 *　前提：画像の最外周は画素が存在しないこと(存在すると実行時エラー)
 *  ドーナツ型の図形もおそらく対応
 *　画像は擬似配列を用いている(１が画素とする)
 */

#include<iostream>

#define SIZE 20
#define WHITE 0
#define BLACK 1
#define CHECK -1

using namespace std;

void output(void);	//擬似画像表示関数
int OutlineTrace();//輪郭線追跡
int TraceAround(int,int,int);//画像の周囲をラベル付けする

struct Point{	//座標を格納する構造体
	int x;
	int y;
};


int gaso[SIZE][SIZE] =		{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,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,
							 0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,
							 0,0,0,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,0,0,
							 0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,
							 0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,
							 0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0,
							 0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,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,1,0,0,0,0,
							 0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,
							 0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,
							 0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,
							 0,0,1,1,1,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,
							 0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,1,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()
{
	output();
	OutlineTrace();
	output();
	
}

void output()	//擬似画像の出力
{
	for(int i = 0 ; i < SIZE ; i++){
		for(int j = 0 ; j < SIZE ; j++){
			if(gaso[i][j] == WHITE)
				cout << "○";
			else if(gaso[i][j] == BLACK)
				cout << "●";
			else
				cout << "▲";
		}
		cout << endl;
	}
	cout << endl;

}

int OutlineTrace(){
	for(int i = 0 ; i < SIZE ; i++){
		for(int j = 0 ; j < SIZE ; j++){
			if(gaso[i][j] == BLACK){	//BLACKがあれば周りを走査
//				cout << "画素" << i << "," << j << "からトレース開始" <<  endl;
				TraceAround(i,j,0);
//				output();
			}
			 if(gaso[i][j] == CHECK){	//CHECK済みであれば次のWHITEまで読み飛ばし
				while(gaso[i][j] != WHITE){
					j++;
				}
			}
		}
	}

	return 0;
}

//画像の周りをトレース
/*
	Pを取り囲む要素		Pの周囲の座標
	p3 p2 p1			P+offset[3] P+offset[2] P+offset[1]
	p4 P  p0			P+offset[4]     P		P+offset[0]
	p5 p6 p7			P+offset[5] P+offset[6] P+offset[7]

	画素を発見した位置(direction)と探索を開始する位置(sd)には
		sd = (direction + 5) % 8
	の関係がある
　　*/


int TraceAround(int y,int x,int direction){
	const Point offset[8] = {	{1,0},{1,-1},	//8近傍の相対位置(オフセット)
								{0,-1},{-1,-1},
								{-1,0},{-1,1},
								{0,1},{1,1}
	};
	int startx = x,starty = y;	//開始地点を保存
//	gaso[y][x] = CHECK;
	
	do{	
		int sd = (direction + 5) % 8;		//探索を開始する方向(SearchDirection)
			for(int i = 0;i < 8; ++i){		//ここでもし周りに何も見つからなかったら無限ループになるので後で修正
				int arroundx = x + offset[(sd + i) % 8].x;
				int arroundy = y + offset[(sd + i) % 8].y;

				if(gaso[arroundy][arroundx] != WHITE){
					y = arroundy;
					x = arroundx;
					gaso[y][x] = CHECK;
//					cout << "画素" << y << "," << x << "をチェック" << endl;
					direction = (sd + i) % 8;
					break;
				}
		}
	}while(startx != x || starty != y);	//開始地点に戻ってくるまでループ

	return 0;
}