// ２値画像の細線化処理（Hilditchの方法）プログラム
// （２値画像は，背景(黒)：MIN_GRAY_LEVEL，図形(白)：MAX_GRAY_LEVELのグレイスケール画像とする。）
// プログラム名：skl_hilditch.cpp

#include "eps-header.hh"

// Hilditchの方法
//
//  注目画素を含む３×３領域の画素番号
//  ┏━┳━┳━┓
//  ┃ 4┃ 3┃ 2┃
//  ┣━╋━╋━┫
//  ┃ 5┃ 0┃ 1┃
//  ┣━╋━╋━┫
//  ┃ 6┃ 7┃ 8┃
//  ┗━┻━┻━┛
//  注目画素番号： 0
//
//  ８近傍画素番号の集合 N8 = {1, 2, 3, 4, 5, 6, 7, 8}
//  ４近傍画素番号の集合 N4 = {1,    3,    5,    7}
//  画素値: a[画素番号]
//          背景(黒)：MIN_GRAY_LEVEL =>  0 (BACKGROUND_LEVEL)
//          図形(白)：MAX_GRAY_LEVEL => +1 (FIGURE_LEVEL)
//          細線化点：SKL_GRAY_LEVEL => -1 (SKELETON_LEVEL)
//
//  注目画素が，条件１〜６を満たすとき，注目画素を細線化点(-1)に変更する。
//  画像全体に適用し，細線化点がなくなるまで繰り返す。
//
//  条件１：図形画素である。   a[0] == 1
//
//  条件２：境界点である。     Σ(1 - |a[k]|) >= 1
//                            k∈N4
//
//  条件３：端点を削除しない。 Σ|a[k]| >= 2
//                            k∈N8
//
//  条件４：孤立点を保存する。 Σc[k] >= 1,   c[k] = 1 (a[k] == 1)
//                            k∈N8                = 0 (a[k] != 0)
//
//  条件５：連結性を保存する。 Nc == 1
//                             Nc = Σ(d[k] - d[k] * d[k + 1] * d[k + 2])
//                                 k∈N4
//                             ここで，d[i] = 1 (|a[i]| == 1), i∈N8
//                                          = 0 (|a[i]| != 1), i∈N8
//
//  条件６：線幅２の線分の片側のみを削除する。
//          すべてのk∈N8に対して，サブ条件(6-1)または(6-2)が成り立つ。
//          サブ条件(6-1) a[k] != -1
//          サブ条件(6-2) a[k]←0 としたとき，Nc == 1
//
const int BACKGROUND_LEVEL =  0;		// 背景
const int FIGURE_LEVEL     = +1;		// 図形
const int SKELETON_LEVEL   = -1;		// 細線化点

const unsigned char SKL_GRAY_LEVEL = 128;	// 細線化点を示す濃度値

// 注目画素の連結度を求める関数
int connect_degree(
	int a[9])	// 符号化された注目画素を含む３×３領域
{
	int d[10];

	for (int i = 0; i <= 8; i ++) {
		d[i] = (abs(a[i]) == 1) ? 1 : 0;
	}
		d[9] = (abs(a[1]) == 1) ? 1 : 0;  // 二順目の近傍画素番号

	int s = 0;
	for (int k = 1; k <= 7; k += 2) {
		s += (d[k] - d[k] * d[k + 1] * d[k + 2]);
	}
	return s;
}

// 元画像(src)をHilditchの方法で細線化処理して処理済画像に入れる関数
void hilditch(
	class image& src,		// 元画像クラス(入力)
	class image& dst)		// 処理済画像クラス(出力)
{
	if (src.p == NULL) {
		printf("元画像がありません。");
		return;
	}

	printf("\n２値画像をHilditchの方法で細線化処理します。\n");

	int nr_lines  = src.get_nr_lines();		// 元画像のライン数   (縦の画素数)
	int nr_pixels = src.get_nr_pixels();	// 元画像のピクセル数 (横の画素数)
	dst.gmake(nr_lines, nr_pixels);			// 処理済画像の配列を確保

	//　２値画像をコピーする。
	for (int iy = 0; iy < nr_lines; iy ++) {
		for (int ix = 0; ix < nr_pixels; ix ++) {
			dst.p[iy][ix] = MIN_GRAY_LEVEL;
			unsigned char b = src.p[iy][ix];
			if (src.p[iy][ix] == MAX_GRAY_LEVEL) dst.p[iy][ix] = b;
		}
	}

	int a[9];		// 符号化された注目画素を含む３×３領域
//            画素番号 0   1   2   3   4   5   6   7   8
	int offset_x[9] = {0, +1, +1,  0, -1, -1, -1,  0, +1};	// 注目画素番号からピクセル方向のオフセット
	int offset_y[9] = {0,  0, -1, -1, -1,  0, +1, +1, +1};	// 注目画素番号からライン方向のオフセット

	int times = 0;	// 細線化処理の回数
	int skl_count;	// 細線化点の画素数

	do {
		times ++;
		printf("\n細線化処理：第%d回目の処理を実行中です。\n", times);

		skl_count = 0;	// 細線化点の個数

		for (int iy = 0; iy < nr_lines; iy ++) {
			for (int ix = 0; ix < nr_pixels; ix ++) {
				// 注目画素を含む３×３領域を符号化する。
				for (int k = 0; k <= 8; k ++) {
					a[k] = BACKGROUND_LEVEL;									// 背景
					int x = ix + offset_x[k];
					int y = iy + offset_y[k];
					if (0 <= x && x < nr_pixels &&
					    0 <= y && y < nr_lines) {
						unsigned char b = dst.p[y][x];
						     if (b == MAX_GRAY_LEVEL) a[k] = FIGURE_LEVEL;		// 図形
						else if (b == SKL_GRAY_LEVEL) a[k] = SKELETON_LEVEL;	// 細線化点
					}
				}

				// 条件１：図形画素である。
				if (! (a[0] == 1)) continue;	// 条件が不成立のときは，次のforループへ

				//  条件２：境界点である。
				int s = 0;
				for (int k = 1; k <= 7; k += 2) {
					s += (1 - abs(a[k]));
				}
				if (! (s >= 1)) continue;	// 条件が不成立のときは，次のforループへ

				//  条件３：端点を削除しない。
				s = 0;
				for (int k = 1; k <= 8; k ++) {
					s += abs(a[k]);
				}
				if (! (s >= 2)) continue;	// 条件が不成立のときは，次のforループへ

				//  条件４：孤立点を保存する。
				s = 0;
				for (int k = 1; k <= 8; k ++) {
					if (a[k] == 1) s ++;
				}
				if (! (s >= 1)) continue;	// 条件が不成立のときは，次のforループへ

				//  条件５：連結性を保存する。
				if (! (connect_degree(a) == 1)) continue;	// 条件が不成立のときは，次のforループへ

				//  条件６：線幅２の線分の片側のみを削除する。
				s = 0;
				for (int k = 1; k <= 8; k ++) {
					if (a[k] != -1) {		// サブ条件(6-1)
						s ++;
					} else {
						int ak = a[k];		// サブ条件(6-2)
						a[k] = 0;
						if (connect_degree(a) == 1) s ++;
						a[k] = ak;
					}
				}
				if (! (s == 8)) continue;	// 条件が不成立のときは，次のforループへ

				//  細線化点となる条件１〜６をすべて満たした。
				dst.p[iy][ix] = SKL_GRAY_LEVEL;
				skl_count ++;
			}
		}

		if (skl_count != 0) {
			//  細線化点を背景に変更する。
			printf("細線化点は，%d点ありました。\n", skl_count);
			for (int iy = 0; iy < nr_lines; iy ++) {
				for (int ix = 0; ix < nr_pixels; ix ++) {
					if (dst.p[iy][ix] == SKL_GRAY_LEVEL) dst.p[iy][ix] = MIN_GRAY_LEVEL;
				}
			}
		} else {
			printf("細線化処理を終了します。\n");
		}
	} while (skl_count != 0);
}

// 元画像(src)に細線化処理した画像を重ね合わせた画像をつくる関数
void overlay(
	class image& src,		// 元画像クラス(入力)
	class image& dst)		// 細線化処理した画像クラス(入出力)
{
	printf("\n細線化処理した画像に元の２値画像をグレイにして重ね合わせます。\n");

	int nr_lines  = src.get_nr_lines();		// 元画像のライン数   (縦の画素数)
	int nr_pixels = src.get_nr_pixels();	// 元画像のピクセル数 (横の画素数)

	for (int iy = 0; iy < nr_lines; iy ++) {
		for (int ix = 0; ix < nr_pixels; ix ++) {
			if (dst.p[iy][ix] == MAX_GRAY_LEVEL) continue;
			if (src.p[iy][ix] == MAX_GRAY_LEVEL) {
				dst.p[iy][ix] = SKL_GRAY_LEVEL;
			}
		}
	}
}

// プログラムの開始位置
int main()
{
	class image src;	// 元画像クラスを宣言
	class image dst;	// 処理済画像クラスを宣言

	src.gload();		// 元画像をBMPファイルから読み込む
						// BMPファイルを指定したい場合は，
						//   src.gload("パス付きBMPファイル名");
						// とする。

	// 元画像(src)をHilditchの方法で細線化処理して処理済画像に入れる
	hilditch(
		src,		// 元画像クラス(入力)
		dst);		// 処理済画像クラス(出力)

	// 元画像(src)に細線化処理した画像を重ね合わせた画像をつくる。
	overlay(
		src,			// 元画像クラス(入力)
		dst);			// 処理済画像クラス(出力)

	dst.gsave();		// 処理済画像をBMPファイルに保存する
						// BMPファイルを指定したい場合は，
						//   dst.gsave("パス付きBMPファイル名");
						// とする。
}