深さ優先探索で画像中の島を構成するピクセルを列挙する

動機

Pietという少々変わったプログラミング言語の存在を知った。普通のプログラミング言語において、ソースコードはテキストファイルで作成される。Pietでは、画像がソースコードの役割を果たす。面白いので、インタプリタを作ってみたいのだが、画像中の同色の領域を検知する必要がある。

そこで、準備として、始点のピクセルを与えたとき、そのピクセルに接続されているピクセルを列挙するプログラムを作ってみることにした。ここでは、与えられたピクセル（画素値は非ゼロ）の上下で画素値非ゼロのピクセルを接続されたピクセルと定義することにする。

深さ優先探索(DFS)

DFSで実装することにする。DFSはこんな感じで実装できる。

root nodeをスタックにpushする;
while(stack.size()!=0)
{
    stack.pop();//これが現在node
    現在nodeの全ての子nodeをpushする;
}

実装

#include "CImg.h"
#include <stack>
#include <vector>
#include <iostream>
using namespace cimg_library;
using namespace std;
using Pos = std::pair<int, int>;

bool is_island(const CImg<unsigned char> &img, Pos pos)
{
	int i = pos.first, j = pos.second;
	if (img(i, j, 0, 0) != 0 || img(i, j, 0, 1) != 0 || img(i, j, 0, 2) != 0) return true;
	else return false;
}

int main(int argc, char **argv)
{
	CImg<unsigned char> img(argv[1]);
	int width = img.width();
	int height = img.height();

	stack<Pos> spos;
	Pos pos0(0, 0); // 探索始点
	spos.push(pos0);

	std::vector<Pos> island;
	
	while (!spos.empty())
	{
		Pos pos_cur = spos.top(); spos.pop(); // 現在の探索ノード
		island.push_back(pos_cur);
		
		// 子ノードを全てpushする
		for (int di = -1; di <= 1; di += 2) // 左右を探索
		{
			Pos pos = pos_cur;
			pos.first += di;
			
			if (pos.first < width && pos.first >= 0 && is_island(img, pos))
			{
				if(find(island.begin(), island.end(), pos) == island.end()) spos.push(pos); // 既にpushした要素をpushしないようにする
			}
		}

		for (int dj = -1; dj <= 1; dj += 2) // 上下を探索
		{
			Pos pos = pos_cur;
			pos.second += dj;

			if (pos.second < height && pos.second >= 0 && is_island(img, pos))
			{
				if (find(island.begin(), island.end(), pos) == island.end()) spos.push(pos); // 既にpushした要素をpushしないようにする
			}
		}
	}

	CImg<unsigned char> img_out(width, height, 1, 3, 0);
	for (auto e : island)
	{
		cout << e.first << " " << e.second << std::endl;
		img_out(e.first, e.second, 0, 0) = 255;
		img_out(e.first, e.second, 0, 1) = 255;
		img_out(e.first, e.second, 0, 2) = 255;
	}
	img_out.save("out.bmp");

	return 0;
}

入力画像：

出力画像：

出来てそう。
バグが見つかったら直す。