Zhang-Suen thinning algorithm

zhangsuen.cpp

#include <iostream>
#include <vector>

using namespace std;

struct Point
{
	size_t x;
	size_t y;
	Point() : x(0), y(0) {}
	Point(size_t x, size_t y) : x(x), y(y) {}
	Point operator+(const Point& other) const
	{
		return Point(x + other.x, y + other.y);
	}
	bool operator==(const Point& other) const
	{
		return x == other.x && y == other.y;
	}
	bool operator!=(const Point& other) const
	{
		return !(x == other.x && y == other.y);
	}
};

const size_t NORTH = 1;
const size_t EAST = 3;
const size_t SOUTH = 5;
const size_t WEST = 7;

const vector<Point> clockwise = {
	Point(-1, -1),
	Point(-0, -1), //north
	Point(+1, -1),
	Point(+1, -0), //east
	Point(+1, +1),
	Point(+0, +1), //south
	Point(-1, +1),
	Point(-1, -0), //west
	Point(-1, -1),
};

class ZhangSuen
{

	int _count_transitions(const Point& pixel) const
	{
		int count = 0;
		//for(const auto& neighbor: clockwise)
		for(size_t i = 1; i < clockwise.size(); i++)
		{
			count += _cell_at(clockwise[i - 1] + pixel) == '0' && _cell_at(clockwise[i] + pixel) == '1';
		}
		return count;
	}

	int _count_black_neighbors(const Point& pixel) const
	{
		Point neighbor;
		int count = 0;
		for(neighbor.x = pixel.x - 1; neighbor.x <= pixel.x + 1; neighbor.x++)
			for(neighbor.y = pixel.y - 1; neighbor.y <= pixel.y + 1; neighbor.y++)
				if(neighbor != pixel)
					count += _cell_at(neighbor) != '0';
		return count;
	}

	char _cell_at(const Point& p) const
	{
		return image[p.y][p.x];
	}

	vector<Point> _all_black_pixels(const vector<string>& data) const
	{
		vector<Point> black;
		for(size_t y = 1; y < data.size() - 1; y++)
			for(size_t x = 1; x < data[y].size() - 1; x++)
				if(_cell_at({x, y}) != '0')
					black.push_back({x, y});
		return black;
	}

	public:
	vector<string> image;
	ZhangSuen(const vector<string>& image) : image(image) {}

	friend ostream& operator<<(ostream& out, const ZhangSuen& o)
	{
		for(const auto& row: o.image)
		{
			for(char cell: row)
				out << (cell == '0' ? ' ' : '#');
			out << endl;
		}
		return out << endl;
	}

	vector<string> run()
	{
		bool done = false;
		vector<Point> black;
		int i = 0;
		while(!done)
		{
			done = true;
			//cout << "Iteration " << i << endl;
			vector<Point> whiten;
			for(const auto& b: _all_black_pixels(image))
			{
				if(2 <= _count_black_neighbors(b) && _count_black_neighbors(b) <= 6)
				{
					//cout << "step 1" << endl;
					if(_count_transitions(b) == 1)
					{
						//cout << "step 2" << endl;
						auto north = _cell_at(b + clockwise[NORTH]) == '0';
						auto east = _cell_at(b + clockwise[EAST]) == '0';
						auto south = _cell_at(b + clockwise[SOUTH]) == '0';
						auto west = _cell_at(b + clockwise[WEST]) == '0';
						if((north || east || south) && (east || south || west))
						{
							//cout << "step 3 : " << b.x << ", " << b.y << endl;
							//cout << _cell_at(b) << endl;
							done = false;
							//image[b.y][b.x] = '0';
							whiten.push_back(b);
						}
					}
				}
			}

			for(const auto& white: whiten)
				image[white.y][white.x] = '0';

			//cout << "Iteration " << i << " (b)" << endl;
			whiten.clear();
			for(const auto& b: _all_black_pixels(image))
			{
				if(2 <= _count_black_neighbors(b) && _count_black_neighbors(b) <= 6)
				{
					if(_count_transitions(b) == 1)
					{
						auto north = _cell_at(b + clockwise[NORTH]) == '0';
						auto east = _cell_at(b + clockwise[EAST]) == '0';
						auto south = _cell_at(b + clockwise[SOUTH]) == '0';
						auto west = _cell_at(b + clockwise[WEST]) == '0';
						if((north || east || west) && (north || south || west))
						{
							done = false;
							whiten.push_back(b);
						}
					}
				}
			}
			for(const auto& white: whiten)
				image[white.y][white.x] = '0';
			//cout << "Iteration " << i++ << endl;
			//cout << ZhangSuen(image) << endl;
		}
		cout << "Done" << endl;
		return image;
	}
};

int main()
{
	vector<string> image;
	string line;
	while(getline(cin, line))
		image.push_back(line);

	ZhangSuen thinner(image);
	cout << "Before thinning :" << endl;
	cout << thinner << endl;
	cout << "After thinning :" << endl;
	thinner.run();
	cout << thinner << endl;
}