][プログラミング]輪郭線追跡と細線化処理

細線化処理を追加
ここからtrace.cpp

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

#include<iostream>
#include"img_process.h"

using namespace std;


int OutlineTrace();//輪郭線追跡
int TraceAround(Point searchpt,int direction);//画像の周囲をラベル付けする

int Thinning();	//細線化

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,1,1,1,1,1,1,1,1,0,0,
							 0,0,0,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,
							 0,0,0,0,1,1,1,1,1,0,0,0,0,0,0,0,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,1,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
};

const Point offset[8] = {	{1,0},{1,-1},	//8近傍の相対位置(オフセット)
								{0,-1},{-1,-1},
								{-1,0},{-1,1},
								{0,1},{1,1}
	};

int main()
{
	output();
//	Thinning();			//細線化するときはこっち
	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(){
	Point searchpt;
	for(searchpt.y; searchpt.y < SIZE ; searchpt.y++){
		for(searchpt.x = 0 ; searchpt.x < SIZE ; searchpt.x++){
			if(gaso[searchpt.y][searchpt.x] == BLACK){	//BLACKがあれば周りを走査
//				cout << "画素" << searchpt.y << "," << searchpt.x << "からトレース開始" <<  endl;
				TraceAround(searchpt,0);
//				output();
			}
			 if(gaso[searchpt.y][searchpt.x] == CHECK){	//CHECK済みであれば次のWHITEまで読み飛ばし
				while(gaso[searchpt.y][searchpt.x] != WHITE){
					searchpt.x++;
				}
			}
		}
	}

	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(Point pt,int direction){
	
	Point startpt = pt;	//開始地点を保存
	gaso[pt.y][pt.x] = CHECK;
	
	do{	
		int sd = (direction + 5) % 8;		//探索を開始する方向(SearchDirection)
			for(int i = 0;i < 8; ++i){		//ここでもし周りに何も見つからなかったら無限ループになるので後で修正
				Point arroundpt = pt + offset[(sd + i) % 8];
			
				if(gaso[arroundpt.y][arroundpt.x] != WHITE){
					pt = arroundpt;

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

	return 0;
}

ここからthinning.cpp

/*	細線化処理プログラム　8連結
 *　Hilditchの方法
 *  前提：画像の最外周は画素が存在しないこと(存在すると実行時エラー)
 *　画像は擬似配列を用いている(１が画素とする)
 */


#include<iostream>
#include"img_process.h"
#include<conio.h>

using namespace std;

bool Isgaso(const Point pt);					//条件１：対象領域の画素である条件
bool Isborder(const Point pt);					//条件２：境界画素である条件
bool IsNotContract(Point pt);					//条件３：端点を削除しない条件(接点でなければ真)
bool IsNotIsolate(Point pt);					//条件４：孤立点を削除しない条件(孤立点でなければ真)　・・・なくても動く？
bool IsPreserveContract(Point pt);				//条件５：連結性を保存する条件
bool IsPreserveContract_saveDepth2(Point pt);	//条件６：線幅が２の線分に対して，片側のみ削除する条件
int Nc8(Point pt);								//条件５に書いてあるNc8を求める
void ClearCheck(void);							//CHECKを全てWHITEに変える




const Point offset[8] = {	{1,0},{1,-1},	//8近傍の相対位置(オフセット)
								{0,-1},{-1,-1},
								{-1,0},{-1,1},
								{0,1},{1,1}
	};

//細線化
int Thinning(){
	bool checkflag = false; //一つでも画素がチェックされればTRUE
	do{
		checkflag = false;
		Point searchpt;
		for(searchpt.y = 0 ; searchpt.y < SIZE ; searchpt.y++){
			for(searchpt.x = 0 ; searchpt.x < SIZE ; searchpt.x++){
				if(Isgaso(searchpt) && Isborder(searchpt) && IsNotContract(searchpt) 
					&& IsNotIsolate(searchpt)  && IsPreserveContract(searchpt) && IsPreserveContract_saveDepth2(searchpt)){
					checkflag = true;			//チェックフラグを立てる
					gaso[searchpt.y][searchpt.x] = CHECK;
				}
			}
		}
		output();
		ClearCheck();		//CHECKを全てWHITEに変える
		getch();
	}while(checkflag);		//一つもCHECKが存在しなければ終了
			return 0;
}

//条件１：対象領域の画素である条件
bool Isgaso(const Point pt){
	return gaso[pt.y][pt.x] ? true : false ;
}

//条件２：境界画素である条件
bool Isborder(Point pt){
	int cnt = 0;
	for(int i=0;i < 8;i+=2){
		Point arroundpt =  pt + offset[i];
		if(gaso[arroundpt.y][arroundpt.x] == WHITE){
			cnt++;
		}
	}
	return cnt ? true : false;	//cnt > 0で真
}

//条件３：端点を削除しない条件(接点でなければ真)
bool IsNotContract(Point pt){
	int cnt = 0;
	for(int i=0;i < 8;++i){
		Point arroundpt =  pt + offset[i];
		if(gaso[arroundpt.y][arroundpt.x] == BLACK || gaso[arroundpt.y][arroundpt.x] == CHECK){
			cnt++;
		}
	}
	return cnt >= 2? true : false;
}

//条件４：孤立点を削除しない条件(孤立点でなければ真)
bool IsNotIsolate(Point pt){
	for(int i=0;i < 8;++i){
		Point arroundpt =  pt + offset[i];
		if(gaso[arroundpt.y][arroundpt.x] == BLACK){
			return true;
		}
	}
	return false;
}

//条件５：連結性を保存する条件
bool IsPreserveContract(Point pt){
	
	return Nc8(pt) == 1? true : false;
}

//条件６：線幅が２の線分に対して，片側のみ削除する条件
bool IsPreserveContract_saveDepth2(Point pt){
	for(int i = 0;i < 8;++i){
		Point arroundpt =  pt + offset[i];
		if(gaso[arroundpt.y][arroundpt.x] == CHECK){
	//		Point copypt = arroundpt;	//一時的に保存
			gaso[arroundpt.y][arroundpt.x] = WHITE;	//B(Pi) = 0としてNc8(pt)を計算する
			if(Nc8(pt) != 1){
				gaso[arroundpt.y][arroundpt.x] = CHECK;	//元に戻す
				return false;
			}
			gaso[arroundpt.y][arroundpt.x] = CHECK;	//元に戻す
		}
	}
	
	return true;
}

//条件５に書いてあるNc8を求める
int Nc8(Point pt){
	int cnt = 0;
	for(int i = 0;i < 8;i += 2){
		Point Pk[3] = { pt + offset[i],pt + offset[(i + 1) % 8],pt + offset[(i + 2) % 8]	
		};										//Pk,Pk+1,Pk+2を求める
		int cp[3];								//C^(P) = 1 - |C(P)|
		for(int j = 0;j < 3;++j){		
			cp[j] = 1 - abs(gaso[Pk[j].y][Pk[j].x]);
		}
		cnt += cp[0] - cp[0] * cp[1] * cp[2];	//C(Pk)-C(Pk)C(Pk+1)C(Pk+2)
	}

	return cnt; 
}

//全てのCHECKをWHITEに変える
void ClearCheck(){
	Point searchpt;
	for(searchpt.y = 0 ; searchpt.y < SIZE ; searchpt.y++){
		for(searchpt.x = 0 ; searchpt.x < SIZE ; searchpt.x++){
			if(gaso[searchpt.y][searchpt.x] == CHECK){
				gaso[searchpt.y][searchpt.x] = WHITE;
			}
		}
	}
}

ここからimg_process.h

#ifndef IMG_PROCESS_H
#define IMG_PROCESS_H

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

//絶対値を返すマクロ
//#define abs(x)	( (x > 0) ? x : -x )	

void output(void);	//擬似画像表示関数
extern gaso[SIZE][SIZE];	//擬似画像

class Point{	//座標クラス
public:
	int x;
	int y;
	Point operator+(Point pt){
		Point tmp;
		tmp.x = x + pt.x;
		tmp.y = y + pt.y;
		return tmp;
	}
	bool operator==(Point pt){
		return x == pt.x && y == pt.y;
	}
};

#endif