segimage.cpp

《Visual C++数字图像识别技术典型案例》之光学字符识别技术源码

/******************************************************************************
 * 光学字符识别程序
 * 文件名：page.h
 * 功能  ：图像分割实现
 * modified by [e-mail]
******************************************************************************/

#include <math.h>
#include <iostream>
#include <string>

#include "common_math.h"
#include "segimage.h"

using std::cout;
using std::endl;

// 设置相反点
void Segimage::point::set_opposite( ringlist_iterator<point> opposite )
{
	opp = opposite;
	length = euklidian_distance( x, y, opp->x, opp->y );
}

// 返回直线
bool Segimage::cs_sequence_start::get_straight_line( float &x1, float &y1, float &x2, float &y2 )
{
	if( sequence->front() == sequence->back() )
		return false;
		
	list<point *>::iterator i = is_start ? sequence->begin() : --sequence->end();
	x1 =( (*i)->x + (*i)->opp->x ) / 2.0;
	y1 =( (*i)->y + (*i)->opp->y ) / 2.0;
	
	is_start ? ++i : --i;
	x2 =( (*i)->x + (*i)->opp->x ) / 2.0;
	y2 =( (*i)->y + (*i)->opp->y ) / 2.0;
	
	return true;
}

// 清空
void Segimage::clear()
{
	for( int i = 0; i < size_x; i++ )
		seg_img[i].resize( size_y );

	for ( int y = 0; y<size_y; y++ )
		for ( int x = 0; x < size_x; x++ )
		{
			pixel &p = get_pixel( x, y );
			p.is_border = false;
			p.is_filled = false;
			p.processed = 0;
			p.segment = 0;
		}

	cs_total_length = 0;
	cs_number = 0;

	min_x=min_y = INT_MAX;
	max_x=max_y = INT_MIN;

	outer_pixel.is_border = false;
	outer_pixel.is_filled = false;
	outer_pixel.processed = 0;
	outer_pixel.segment = 2;
}

// 构造函数
Segimage::Segimage( int x, int y ) : size_x( x ), size_y( y ), seg_img( x )
{
	clear();
}

// 构造函数
Segimage::Segimage( const CharImage& img ) : size_x( img.width() ), size_y( img.height() ), seg_img( size_x )
{
	clear();
	
	for ( int y = 0; y < size_y; y++ )
		for ( int x = 0; x < size_x; x++ )
			if( img.get_bw_pixel( x, y ) )
				if( !( seg_img[x][y].is_border = img.is_border_pixel( x, y ) ) )
					seg_img[x][y].segment = 1;
}

// 填充
void Segimage::fill( int x, int y, pixel &p, int segnr )
{
	assert( p != outer_pixel );

	pixel &me = get_pixel( x, y );
	if( me != p )
		return;
		
	me.segment = segnr;
	fill( x-1, y,   p, segnr );
	fill( x,   y+1, p, segnr );
	fill( x+1, y,   p, segnr );
	fill( x,   y-1, p, segnr );
}

// 检测分段
int Segimage::detect_segments()
{
	pixel pix;
	pix.is_border = false;
	pix.is_filled = false;
	pix.processed = 0;
	pix.segment = 0;
	
	// 填充所有背景点
	for (int y = 0; y < size_y; y++ )
	{
		if( y == 0 || y == size_y-1 )
			for ( int x = 0; x < size_x; x++ )
				fill( x, y, pix, 2 );
		else
		{
			fill( 0, y, pix, 2);
			fill( size_x - 1, y, pix, 2);
		}
	}
	
	// 填充内部分段
	int segnr = 3;
	for (int y = 0; y < size_y; y++ )
		for ( int x = 0; x < size_x; x++ )
			if( get_pixel( x, y ) == pix )
				fill( x, y, pix, segnr++ );
	
	for ( int y = 0; y < size_y; y++ )
		for ( int x = 0; x < size_x; x++ )
		{
			pixel &p = get_pixel( x, y );
			if( p.is_border )
			{
				unsigned int tmp = p.segment;
				set_segment( x-1, y,   tmp);
				set_segment( x,   y-1, tmp);
				set_segment( x+1, y,   tmp);
				set_segment( x,   y+1, tmp);
				p.segment = tmp;
			}
		}

	return segnr - 1;
}

// 获得边界列表
void Segimage::get_border_lists( Segimage::border_lists &l )
{
	int num_segs = detect_segments();

	// 奇怪的字符
	if ( num_segs > max_segment )
		return;
	
	l.resize( num_segs - 1 );
	
	// 备用内存
	for( vector< vector< qlist< point > > >::iterator i = l.begin(); i != l.end(); i++ )
		i->reserve( vector_def_reserve );

	for ( int y = 0; y < size_y; y++ )
		for ( int x = 0; x < size_x; x++ )
		{
			pixel &p = get_pixel( x, y );
			if( p.is_border && p.segment != p.processed ) // 边界点，且未进行分段处理
			{
				for(int i = 0; i < num_segs; i++ )
				{
					if( ( p.segment & ( 1 << i ) ) && !( p.processed & ( 1 << i ) ) )
					{
						vector< qlist< point > > &v = l[i];
						v.resize( v.size()+1 );
						SegWalker walker( this );
						walker.walk_border( x, y, i, &v.back() );
					}
				}
			}
		}
	
	for( vector< vector< qlist<point> > >::iterator i = l.begin(); i!=l.end(); ++i )
	{
		for( vector< qlist<point> >::iterator n = i->begin(); n!=i->end(); ++n )
		{
			ringlist_iterator< Segimage::point > m(*n);
			for( int o = n->size(); o > 0; ++m, o-- )
			{
				if ( m->x < min_x)
					min_x = m->x;

				if ( m->y < min_y)
					min_y = m->y;

				if ( m->x > max_x)
					max_x = m->x;

				if ( m->y > max_y)
					max_y = m->y;

				pixel &pix = get_pixel( m->x, m->y );
				pix.border_points.push_back(m);
			}
		}
	}
}

// 打印
void Segimage::print( int mark_x, int mark_y )
{
	for ( int y = 0; y < size_y; y++ )
	{
		for ( int x = 0; x < size_x; x++ )
		{
			if( x == mark_x && y == mark_y )
				cout << "\033[34m\033[7m*";
			
			else
			{
				if( get_pixel( x, y ).is_filled )
					cout << "\033[34m\033[7m#";
				
				else if ( get_pixel( x, y ).segment == 9 )
					cout << "\033[32m\033[7m*";
				
				else if ( get_pixel(x,y).is_border )
					cout << "\033[31m\033[7m" << get_pixel( x, y ).segment;
				
				else
					cout << "\033[30m\033[0m" << get_pixel( x, y ).segment;
			}
		}
		cout << "\033[30m\033[0m" << endl;
	}
	cout << endl;
}

// 平均线条粗细
double Segimage::avg_line_thickness()
{
	if ( cs_number )
		return cs_total_length / cs_number;
	else
		return 0;
}

// Bresenham算法画线
void Segimage::lineBresenham( int x0, int y0, int x1, int y1, HandlePixelCallback cb, void *cb_data )
{
	int dy = y1 - y0;
	int dx = x1 - x0;
	int stepx, stepy;

	if ( dy < 0 )		// 起点不是最低点
	{
		dy = -dy;
		stepy = -1;
	}
	else
		stepy = 1;

	if ( dx < 0 )		// 起点不是最左点
	{
		dx = -dx;
		stepx = -1;
	}
	else
		stepx = 1;

	dy *= 2;
	dx *= 2;

	if( !( (this->*cb )( x0, y0, cb_data ) ) )
		return;
	
	if ( dx > dy )	// slopes < 1
	{
		int decision = 2*dy - dx;		// 初始决策变量
		
		while ( x0 != x1 )
		{
			if ( decision <= 0 )
			{
				x0 += stepx;
				decision += dy;			// 更新决策变量
			}
			else
			{
				x0 += stepx;
				y0 += stepy;
				decision += dy - dx;	// 更新决策变量
			}			
			if( !( ( this->*cb )( x0, y0, cb_data ) ) )
				return;
		}
	}
	else
	{
		int decision = 2*dx - dy;		// 初始决策变量
		
		while ( y0 != y1 )
		{
			if ( decision <= 0 )
			{
				y0 += stepy;
				decision += dx;			// 更新决策变量
			}
			else
			{
				x0 += stepx;
				y0 += stepy;
				decision += dx - dy;	// 更新决策变量
			}			
			if( !( ( this->*cb )( x0, y0, cb_data ) ) )
				return;
		}
	}
}

// Bresenham算法画线
void Segimage::lineBresenham(int x0, int y0, float angle, HandlePixelCallback cb, void *cb_data)
{
	const int h = size_x+size_y;
	lineBresenham( x0, y0,
		static_cast< int >( x0 + h*cos( angle ) ),
		static_cast< int >( y0 + h*sin( -angle ) ),
		cb, cb_data );
}

// Bresenham算法画线
void Segimage::lineBresenham(int x0, int y0, int x1, int y1)
{
	lineBresenham( x0, y0, x1, y1, &Segimage::draw_pixel, NULL );
}

// 寻找对立点
bool Segimage::find_opposite_pixel(int x0, int y0, void *cb_data)
{
	bool result = true;
	opposite_data &od = *reinterpret_cast< opposite_data * >( cb_data );


	if( od.first )
		od.first = false;
	else
	{
		pixel &pix = get_pixel( x0, y0 );
		if( pix.is_border || pix.segment != 1 )
			result = false;
	}
	
	if( result )
	{
		od.ax = x0;
		od.ay = y0;
	}
	else
	{
		od.ex = x0;
		od.ey = y0;
	}
	return result;
}

// 通过画线寻找对立点
ringlist_iterator<Segimage::point> &Segimage::find_opposite( const Segimage::point &p )
{
	opposite_data od;
	od.first = true;
	int rx;
	int ry;

	lineBresenham( p.x, p.y, p.ang, &Segimage::find_opposite_pixel, &od );

	pixel pix=get_pixel( od.ex, od.ey );

	if( pix.is_border )	
	{
		rx = od.ex;
		ry = od.ey;
	}
	else if( od.ax == p.x && od.ay == p.y )
	{
		rx = p.x;
		ry = p.y;
	}
	else
	{
		int delta_x = od.ax - od.ex;
		int delta_y = od.ay - od.ey;
		int x_diag_1 = od.ex + delta_x;
		int y_diag_1 = od.ey;
		int x_diag_2 = od.ex;
		int y_diag_2 = od.ey + delta_y;

		float angle_1 = atan2( y_diag_1 - p.y, x_diag_1 - p.x );
		float angle_2 = atan2( y_diag_2 - p.y, x_diag_2 - p.x );

		if ( fabs( p.ang - angle_1 ) < fabs( p.ang - angle_2 ) )
		{
			rx = x_diag_1;
			ry = y_diag_1;
		}
		else
		{
			rx = x_diag_2;
			ry = y_diag_2;	       
		}
	}
	
	pixel &rpix = get_pixel( rx, ry );
	ringlist_iterator< point > *r = NULL;
	float ang = 2*M_PI;
	
	assert( rpix.is_border );
	float angle = normalize_angle_pi( p.ang + M_PI );
	for( list< ringlist_iterator<point> >::iterator i = rpix.border_points.begin(); i != rpix.border_points.end(); ++i )
	{
		assert( (*i)->x == rx && (*i)->y == ry );
		float new_angle = min_angle_between((*i)->ang,angle,2*M_PI);

		if( new_angle < ang )
		{
			ang = new_angle;
			r = &(*i);
		}
	}

	assert( r != NULL );
	return *r;
}

// 计算交叉点
bool Segimage::intersect_pixel( int x0, int y0, void *cb_data )
{
	pixel &pix = get_pixel( x0, y0 );

	intersect_data &cb = *reinterpret_cast< intersect_data * >( cb_data );
	point &p = *cb.p;
	list< point * >::iterator i = pix.start_points.begin();
	
	while( i != pix.start_points.end() )
	{
		if( (*i)->length == -1 ) // 线已经被标记删除
			i = pix.start_points.erase(i);
		else
		{
			if( line_segment( (*i)->x, (*i)->y, (*i)->opp->x, (*i)->opp->y ).intersect( 
				line_segment( p.x, p.y, p.opp->x, p.opp->y ), false) )
			{
				cs_number--; 
				if( (*i)->length > p.length )	// 其它线更长，删除
				{
					cs_total_length -= (*i)->length;
					(*i)->length = -1;
					(*i)->opp->num_ending--;
					i = pix.start_points.erase(i);
					continue;
				}
				else				// 当前线更长或相等，删除
				{
					cs_total_length -= p.length;
					p.length = -1;
					return false;
				}
			}
			++i;
		}
	}

	int delta_x = x0 - cb.ax;
	int delta_y = y0 - cb.ay;

	// 特例：对角线交叉
	if( delta_x && delta_y )
	{
		int x_diag_1 = x0-delta_x;
		int y_diag_1 = y0;
		int x_diag_2 = x0;
		int y_diag_2 = y0-delta_y;

		pixel &pd1 = get_pixel( x_diag_1, y_diag_1 );
		pixel &pd2 = get_pixel( x_diag_2, y_diag_2 );

		i=pd1.start_points.begin();

		// 校验所有的对角线交叉
		while( i != pd1.start_points.end() )
		{
			if( (*i)->length == -1 ) 
				i = pd1.start_points.erase(i);
			else
			{
				list< point * >::iterator j = pd2.start_points.begin();
				while( j != pd2.start_points.end() )
				{
					if( (*j)->length==-1 ) 
						j = pd2.start_points.erase(j);
					else
					{
						if( *i == *j )
						{
							cs_number--;
							if( (*i)->length > p.length )
							{
								cs_total_length -= (*i)->length;
								(*i)->length = -1;
								(*i)->opp->num_ending--;
								i = pd1.start_points.erase(i);
								j = pd2.start_points.erase(j);
								continue;
							}
							else
							{
								cs_total_length -= p.length;
								p.length = -1;
								return false;
							}
						}
						++j;
					}
				}
				++i;
			}
		}
	}
	pix.start_points.push_back( &p );
	cb.ax = x0;
	cb.ay = y0;
	return true; 
}

// 绘制交叉区段
void Segimage::intersect_cs( Segimage::point &p )
{
	cs_total_length += p.length;
	cs_number++;
	intersect_data cb;
	cb.ax = p.x;
	cb.ay = p.y;
	cb.p = &p;

	lineBresenham( p.x, p.y, p.opp->x, p.opp->y, &Segimage::intersect_pixel, &cb );
}

// 绘制孤立点
bool Segimage::draw_singular_pixel( int x0, int y0, void *p )
{
	fill_singular_region( x0, y0, reinterpret_cast< point * >( p ) );
	return true;
}

// 区域填充
void Segimage::fill_region( Segimage::point *sp )
{
	lineBresenham( sp->x, sp->y, sp->opp->x, sp->opp->y, &Segimage::draw_singular_pixel, sp );
}

// 捕获区段
bool Segimage::take_over_segment( int x, int y, Segimage::singularpoint &sp )
{
	pixel &p = get_pixel( x, y );

	if( p.is_filled )
		return p.start_points.empty();
	else
	{
		if( p.segment == 1 || p.is_border )
		{
			list< point * >::iterator i = p.start_points.begin();
			while( i != p.start_points.end() )
			{
				if( ( *i )->length == -1 )
					i = p.start_points.erase( i );
				else
					return false;
			}
			p.is_filled = true;
			sp.x += x;
			sp.y += y;
			sp.pix_count++;
			return take_over_segment( x-1, y,   sp) &&
			       take_over_segment( x,   y+1, sp) &&
			       take_over_segment( x+1, y,   sp) &&
			       take_over_segment( x,   y-1, sp);
		}
	}
	return true;
}

// 取消捕获区段操作
void Segimage::undo_take_over_segment( int x, int y )
{
	pixel &p = get_pixel( x, y );

	if( p.is_filled && p.start_points.empty() )
	{
		p.is_filled = false;
		undo_take_over_segment( x-1, y);
		undo_take_over_segment( x,   y+1);
		undo_take_over_segment( x+1, y);
		undo_take_over_segment( x,   y-1);
	}
}

// 填充孤立区域
void Segimage::fill_singular_region( int x, int y, Segimage::point *start_point )
{
	pixel &p = get_pixel( x, y );

	if( p.is_filled )
	{
		singularpoint *ssp = start_point->singular_point, 
			      *psp = p.start_points.front()->singular_point;

		if( ssp != psp )
		{
			if( psp->pix_count != 0 )
			{
				if( ssp->pix_count == 0 )
				{
					ssp->x = psp->x;
					ssp->y = psp->y;
				}
				else
				{
					ssp->x += psp->x;
					ssp->y += psp->y;
				}
				ssp->pix_count += psp->pix_count;
				
			}
			for( list<cs_sequence_start>::iterator i = psp->cs_sequences.begin(); i != psp->cs_sequences.end(); ++i )
			{
				ssp->cs_sequences.push_back( *i );
				point &start_point = *( i->is_start ? i->sequence->front() : i->sequence->back() );
				start_point.singular_point = ssp;

			}
			psp->cs_sequences.clear();
		}
	}
	else 
	{
		if( p.segment == 1 || p.is_border )
		{
			bool our_cs = false;
			int nr = 0;
			list< point * >::iterator i = p.start_points.begin();
			
			while( i != p.start_points.end() )
			{
				if( (*i)->length == -1 )			// 行标志擦除
					i = p.start_points.erase( i );
				else
				{
					if( *i == start_point )
						our_cs = true;
					++nr;
					++i;
					
				}
			}
			
			if( p.start_points.empty() || ( our_cs && nr == 1 ) )
			{
				p.is_filled = true;
				singularpoint &sp = *( start_point->singular_point );
				
				if( sp.pix_count == 0 )
				{
					sp.x = x;
					sp.y = y;
				}
				else
				{
					sp.x += x;
					sp.y += y;
				}
				sp.pix_count++;

				p.start_points.clear();
				p.start_points.push_back( start_point );
				
				fill_singular_region( x-1, y,   start_point );
				fill_singular_region( x,   y+1, start_point );
				fill_singular_region( x+1, y,   start_point );
				fill_singular_region( x,   y-1, start_point );
			}
		}
	}
}

// 遍历边界点
void SegWalker::walk_border( int start_x, int start_y, int seg, qlist<Segimage::point> *l )
{
	segment = seg;
	list = l;
	Walker::walk_border( start_x, start_y );
}

// 判断是否一个好的遍历起点
bool SegWalker::is_good_walker_start( int x, int y ) const
{
	Segimage::pixel &pix = img->get_pixel( x, y );
	return ( !pix.is_border && pix.segment == ( segment + 2 ) );
}

// 遍历过程
void SegWalker::walker_process( int x, int y )
{
	list->push_back( Segimage::point( x, y ) );
	Segimage::pixel &pix = img->get_pixel( x, y );
	pix.processed = pix.processed | ( 1 << segment );
}