abstract_character.h

vc++数字图像识别技术典型案例

/******************************************************************************
 * 光学字符识别程序
 * 文件名：abstract_character.h
 * 功能  ：抽象字符类定义文件
 * modified by [e-mail]
******************************************************************************/

#ifndef ABSTRACT_CHARACTER_H
#define ABSTRACT_CHARACTER_H

#include <algorithm>
#include <ext/hash_map>
#include <ext/hash_set>
#include <fstream>

#include "character.h"

using std::fstream;
using __gnu_cxx::hash;
using __gnu_cxx::hash_map;

struct abstract_singular_point : public point<float>
{
	point_type type;
	list<int> acl;			// 与该点的连接列表
	
	void add_connection(int cnr);
};

struct abstract_connection
{
	curvature_type type;	// 曲线类型
	int singular_point_1;	// 起点
	int singular_point_2;	// 终点
	list< point<float> > polyline;	// 至少有两个元素
	bool is_matched;		// 存在已经匹配的连接
	float weight;			// 连接权值

	int walk(int from) const { return from==singular_point_1?singular_point_2:singular_point_1; }
	curvature_type relative_type(int from) const { return from==singular_point_1?type:-type; }
	void reset_matching_state() { is_matched=false; weight=1.0; }
	float unmatched_area(const vector<abstract_singular_point> &aspv);
};

class abstract_character;

template<bool is_forward_iterator> class path_iterator
{
	friend class path;
	private:
		const abstract_character*		base_char;	// 经由的字符
		const point<float>*			cached_point;
		bool					end_state;			// 迭代器到结尾时为真

		int					end_point;				// 当前连接的结束点
		list<int>::const_iterator	  	con_iter;	// 当前连接
		list<int>::const_iterator	  	con_last;	// 最后一个不同连接

		bool					forward;			// true 表示 ++, false --
		list< point<float> >::const_iterator	polyline_iter;	// 连接的当前位置
		list< point<float> >::const_iterator	polyline_last;	// 最后一个不同位置

		void setup_polyline_iterators();
	public:
		path_iterator() : cached_point(NULL), end_state(true) {}
		bool operator==(const path_iterator<is_forward_iterator> &pi) const;
		bool operator!=(const path_iterator<is_forward_iterator> &pi) const;
		const point<float>& operator*() const { return cached_point ? *cached_point : *polyline_iter; }
		const point<float>* operator->() const { return &(operator*()); }
		path_iterator<is_forward_iterator>& operator++();
		float get_weight() const { return base_char->acv[*con_iter].weight; }
		bool is_matched() const { return base_char->acv[*con_iter].is_matched; }
};

class match_debug_info
{
	public:
		struct square
		{
			point<float> data[4];
			int color;
		};
		struct line
		{
			point<float> data[2];
			int color;
		};
		void eat_up( match_debug_info &mdi );
		void add_square(point<float> p1, point<float> p2, point<float> p3, point<float> p4, int color=0);
		void add_line(point<float> p1, point<float> p2, int color=0);
		list<square>::const_iterator square_begin() { return squares.begin(); }
		list<square>::const_iterator square_end() { return squares.end(); }
		list<line>::const_iterator line_begin() { return lines.begin(); }
		list<line>::const_iterator line_end() { return lines.end(); }

	private:
		list<square> squares;
		list<line>   lines;
};

class path
{
	friend ostream& operator<< (ostream& o, const path& t);
	protected:
		abstract_character* base_char;
		int 		singular_point_1;		// 起点
		int 		singular_point_2;		// 终点
		list<int>	connections;

	public:
		typedef class path_iterator<true>	const_iterator;
		typedef class path_iterator<false>	const_reverse_iterator;

		path() : base_char(NULL), singular_point_1(-1), singular_point_2(-1) {}
		path(abstract_character *ac) : base_char(ac), singular_point_1(-1), singular_point_2(-1) {}

		const_iterator begin() const;
		const_iterator end() const { return const_iterator(); }
		const_reverse_iterator rbegin() const;
		const_reverse_iterator rend() const { return const_reverse_iterator(); }

		const abstract_character& get_base_char() const { return *base_char; }
		int start_point() const { return singular_point_1; }
		int end_point() const { return singular_point_2; }

		bool contains_connection(int con) const { return find(connections.begin(),connections.end(),con)!=connections.end(); }
		bool match_connection(const path &other_path, float &divergence, match_debug_info *mdi) const;		
		float get_unmatched_divergence();
		void mark_unmatched();
		void mark();
};

class inner_path : public path
{
	public:
		inner_path(abstract_character &ac, int start_point, int end_point);
		inner_path() : path(NULL) {}
		bool append_connection(int con);
		void remove_last_connection() { connections.pop_back(); }
};

class tree_path  : public path
{
	public:
		tree_path(abstract_character &ac, int start_point=-1);
		tree_path() : path(NULL) {}
		bool append_connection(int con);
		void remove_last_connection();
};

class transformation
{
	private:
		float min_x, max_x, min_y, max_y;

		float scale_factor;	// x和y比例因子
		float x_0, y_0;		// 新的坐标原点
		float a, b,			// 旋转矩阵
		      c, d;

	public:
		transformation(float angle, float scale, float x, float y);
		void transform(float x, float y, float &t_x, float &t_y);
		float minx() const { return min_x; }
		float maxx() const { return max_x; }
		float miny() const { return min_y; }
		float maxy() const { return max_y; }

		float transformed_width() const { return max_x-min_x; }
		float transformed_height() const { return max_y-min_y; }
};

class abstract_character
{
	public: 
		vector<abstract_singular_point>	aspv;
		vector<abstract_connection>	acv;

		abstract_character(const character &c, float base_line_pos=FLT_MAX, float reference_height=0, float angle=0);
		abstract_character() {}
		void read(fstream &fs);
		void write(fstream &fs) const;
		float match(abstract_character &ac, float cut_off_divergence, match_debug_info *mdi=NULL);
		static float get_real_height(const character &c, float angle);
	private:
		struct sp_mapped
		{
			int	db_index;		// 数据库中的单点下标
			float	dist;		// 与数据库中单个点的距离
			bool	fixed;		// db_index后来可能会改变
		};

		static void stroke(transformation &T, float thickness, float x1, float y1, float x2, float y2);
		static int my_max(int x, int &old_max) { return x>old_max ? old_max=x : x; }
		int resolve_con(const connection *con, hash_map<const singular_point*, int, hash<const singular_point*> > &spmap, 	hash_map<const connection*, int, hash<const connection*> > &conmap, transformation &T);
		int resolve_sp(const singular_point *sp, hash_map<const singular_point*, int, hash<const singular_point*> > &spmap, hash_map<const connection*, int, hash<const connection*> > &conmap, transformation &T);
		void reset_matching_state();
		void mark(const path &p);
		void find_next_cheapest_path(path &db_path, path &real_path, float &divergence,
			tree_path &current_path, abstract_character &ac, const vector< list<int> > &remap,
			match_debug_info *mdi) const;
		bool find_connection(const path &db_path, path &real_path, float &divergence,
			inner_path &current_real_path, int current_singular_point, match_debug_info *mdi) const;
};


// 内联和模板函数

/******************************************************************************
 * 相等比较操作
******************************************************************************/
template<bool is_forward_iterator> inline bool path_iterator<is_forward_iterator>::operator==(const path_iterator<is_forward_iterator> &pi) const
{
	return (end_state || pi.end_state) ?
			end_state==pi.end_state :
			( (cached_point || pi.cached_point) ? cached_point==pi.cached_point :
				con_iter==pi.con_iter && polyline_iter==pi.polyline_iter
			);
}

/******************************************************************************
 * 不等比较操作
******************************************************************************/
template<bool is_forward_iterator> inline bool path_iterator<is_forward_iterator>::operator!=(const path_iterator<is_forward_iterator> &pi) const
{
	return !(*this==pi);
}

/******************************************************************************
 * 设置多边形迭代器
******************************************************************************/
template<bool is_forward_iterator> void path_iterator<is_forward_iterator>::setup_polyline_iterators()
{
	const abstract_connection &ac=base_char->acv[*con_iter];
	if( (forward=(end_point==ac.singular_point_1)==is_forward_iterator) )
	{
		polyline_iter=ac.polyline.begin();
		polyline_last=--ac.polyline.end();
	}
	else
	{
		polyline_iter=--ac.polyline.end();
		polyline_last=ac.polyline.begin();
	}
	end_point=ac.walk(end_point);
}

/******************************************************************************
 * ++操作
******************************************************************************/
template<bool is_forward_iterator> path_iterator<is_forward_iterator>& path_iterator<is_forward_iterator>::operator++()
{
	if( polyline_iter!=polyline_last )
	{
		if( cached_point )
			cached_point=NULL;
		else if( forward )
			++polyline_iter;
		else
			--polyline_iter;
	}
	else
	{
		if( !cached_point )
			cached_point=&(base_char->aspv[end_point]);
		else
		{
			cached_point=NULL;
			if( con_iter==con_last )
				end_state=true;
			else
			{
				if( is_forward_iterator )
					++con_iter;
				else
					--con_iter;
				setup_polyline_iterators();
			}
		}
	}
	return *this;
}

/******************************************************************************
 * <<操作
******************************************************************************/
inline ostream& operator<< (ostream& o, curvature_type t)
{
	switch( t )
	{
		case straight:		o << "straight"; break;
		case left_curved:	o << "left_curved"; break;
		case right_curved:	o << "right_curved"; break;
		default:		o << "undefined";
	}
	return o;
}

/******************************************************************************
 * <<操作
******************************************************************************/
inline ostream& operator<< (ostream& o, point_type t)
{
	switch( t )
	{
		case end_point:		o << "end_point"; break;
		case branching_point:	o << "branching_point"; break;
		case turning_point:	o << "turning_point"; break;
		default:		o << "undefined";
	}
	return o;
}

ostream& operator<< (ostream& o, abstract_character &c);

#endif