/****************************************************************************** * 光學字符識別程序 * 文件名：page.h * 功能  ：圖像分割實現 * modified by PRTsinghua@hotmail.com******************************************************************************/#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 );}