page.cpp

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

/******************************************************************************
 * 光学字符识别程序
 * 文件名：page.cpp
 * 功能  ：页面函数实现文件
 * modified by [e-mail]
******************************************************************************/

#include "page.h"

#include <stdlib.h>
#include <math.h>
#include <assert.h>
#include <vector>
#include <set>

#include <qpixmap.h>
#include <qpainter.h>
#include <kmessagebox.h>
#include <kimageeffect.h>

#include "common.h"
#include "common_math.h"
#include "global.h"
#include "word_collector.h"

using std::max;

const float BoundingBox::overhang_ratio		= 0.4;
const float Page::min_area_divisor		= 0.1;
const int Page::very_long_character_ratio	= 20;
const int Page::num_bufferlines			= 2;
const float char_line::vert_line_dist_ratio	= 0.3;
const int char_line::min_correlation_chars	= 3;
const float base_line::y_variance_ratio		= 0.1;
const float base_line::diaresis_ratio		= 0.3;

// 判断包围盒的位置
bool BoundingBox::overhangs( const BoundingBox &bb ) const
{
	const BoundingBox *bb1, *bb2;
	if ( width() < bb.width() )
	{
		bb1 = &bb;
		bb2 = this;
	}
	else
	{
		bb1 = this;
		bb2 = &bb;		
	}	
		
	int min_overhang = qRound( bb2->width() * overhang_ratio );
	
	if ( ( ( bb1->min_x <= bb2->max_x - min_overhang ) && ( bb1->min_x >= bb2->min_x ) ) ||	// box挂在左边界
	     ( ( bb1->max_x >= bb2->min_x + min_overhang ) && ( bb1->max_x <= bb2->max_x ) ) ||	// box挂在右边界
	     ( ( bb1->min_x >= bb2->min_x ) && ( bb1->max_x <= bb2->max_x ) ) || 		// box完全悬空
	     ( ( bb1->min_x <= bb2->min_x ) && ( bb1->max_x >= bb2->max_x ) ) )			// box悬挂在外面
		return true;
	return false;
}

// 增加部分
void MetaBox::add_part( const BoundingBox &bb )
{
	parts.push_back( bb );

	// 更新维数和面积
	min_x = min( min_x, bb.min_x );
	max_x = max( max_x, bb.max_x );
	min_y = min( min_y, bb.min_y );
	max_y = max( max_y, bb.max_y );
	assert( min_x <= max_x && min_y <= max_y );
	area += bb.area;
}

// 遍历过程2
void SizeWalker::walker_process2( int x, int y )
{
	bb.min_x = min( bb.min_x, x );
	bb.min_y = min( bb.min_y, y );
	bb.max_x = max( bb.max_x, x );
	bb.max_y = max( bb.max_y, y );
}

// 遍历过程
void CopyWalker::walker_process( int x, int y )
{
	// 拷贝遍历者路径
	int color = img.get_pixel( x, y ); 
	
	// 忽视已移去的遍历者
	if ( !img.is_background( color ) )
		bb.part->set_pixel( x - bb.min_x, y - bb.min_y, color );
}

// 遍历过程2
void CopyWalker::walker_process2( int x, int y )
{
	// 拷贝边界点
	int color = img.get_pixel( x, y );
	
	if ( color == CharImage::white )
		color--;
	
	bb.part->set_pixel( x - bb.min_x, y - bb.min_y, color );
}

// 基线构造函数
base_line::base_line( const char_line &chars )
{
	assert( chars.get_max_height() != 0 );
	
	for ( char_line::const_iterator mb = chars.begin(); mb != chars.end(); ++mb )
	{
		int num_chars = chars.size(); // 仅能计算一次
		float x = mb->get_x(), y = mb->get_y();
		
		if ( ( mb->height() > diaresis_ratio*chars.get_avg_height() && 	// 不是虚线或者下划线
		       fabs( chars.distance( x, y ) ) < y_variance_ratio*chars.get_max_height() ) || 
		       num_chars < char_line::min_correlation_chars ) 		// 足够的字符计算相关性
		{			
			push_back( point<float>( x, y ) );
			corr.sum_x += x;
			corr.sum_y += y;
			corr.num_points++;
		}
	}

	// 没有发现合适的点
	if ( empty() )
	{
		float x = begin()->get_x(), y = begin()->get_y();
		push_back( point<float>( x, y ) );
		corr.sum_x += x;
		corr.sum_y += y;
		corr.num_points++;
	}

	corr.first = begin();
	corr.last = --end();
	angle = atan2( corr.first->get_y() - corr.last->get_y(), corr.last->get_x() - corr.first->get_x() );
	corr.correlate();
}

// 获得基线的y坐标
float base_line::get_base_y( const MetaBox &mb ) const
{
	assert( corr.num_points > 0 );
	
	if ( corr.num_points < 2 )	// 至少需要两个点
		return 0;
	else
		return corr.function( mb.get_x() ) - mb.get_y();
}

// 计算点与线的距离
float base_line::distance( int x, int y ) const
{
	if ( corr.num_points < 2 )	// 至少需要两个点
		return 0;
	
	else
	{
		float x2, y2;
		corr.construct_perpendicular( x, y, x2, y2 );
		float dist = euklidian_distance( static_cast<float>( x ), static_cast<float>( y ), x2, y2 );
		
		if ( y < y2 )
			dist = -dist;
		
		return dist;
	}
}

// 扩展字符
void char_line::extend_char( char_line::iterator mb, const BoundingBox &bb, bool correlate )
{
	// 通过相关性计算包围盒
	base.sum_x  -= mb->get_x();
	base.sum_y  -= mb->get_y();
	sum_heights -= mb->height();	// 移除旧的高度
	
	mb->add_part( bb );	
						
	base.sum_x += mb->get_x();
	base.sum_y += mb->get_y();
	sum_heights += mb->height();	// 增加新的高度

	if ( correlate )
		base.correlate();
}

// 扩展字符
void char_line::extend_char( char_line::iterator mb1, const MetaBox &mb2 )
{
	assert( &( *mb1 ) != &mb2 );
	
	for ( list< BoundingBox >::iterator i = const_cast<MetaBox&>( mb2 ).parts.begin();
              i != const_cast<MetaBox&>( mb2 ).parts.end(); ++i )
		extend_char( mb1, *i, false );
	
	base.correlate();
}

// 添加字符
void char_line::add_char( const BoundingBox &bb )
{
	// 重置记住的位置
	if ( empty() || marker->min_x > bb.min_x || marker == end() )
		marker = begin();
	
	// 更新指针到最近的
	while ( marker != end() && ++iterator( marker ) != end() && ( ++iterator( marker ) )->min_x < bb.min_x )
		++marker;

	max_width = max( max_width, bb.width() );
	max_height = max( max_height, bb.height() );
	last_x_pos = ( bb.min_x + bb.max_x ) / 2;
	
	bool found = false;
	char_line::iterator i = marker, found_char = end();
	
	while( i != end() && bb.max_x > i->min_x )
	{
		for ( list< BoundingBox >::iterator j = i->parts.begin(); j != i->parts.end(); ++j )
		{
			if ( i == found_char )		// 删除一行结尾
				return;					// 同样的不检查
			
			if ( j->overhangs( bb ) ) 	// 检查该部分之上是否悬挂着另一个
			{
				if ( found_char == end() )
				{
					extend_char( i, bb );	// 在存在的metabox中添加
					found_char = i;
				}
				else
				{
					extend_char( found_char, *i );
					i = remove_char( i );
				}
				found = true;
				break;
			}
		}
		
		if ( found_char != end() )
		{
			if ( found )
				found = false;
			else
				return;
		}
		++i;
	}
	if ( found_char != end() )
		return;
	
	MetaBox mb;
	mb.add_part( bb ); // 创建新的metabox
	                                            
	// 在链表中插入新元素
	char_line::iterator iter = insert_sorted( mb, marker );

	// 更新相关性信息
	if ( iter == begin() )
		base.first = iter;
	
	if ( iter == --end() )
		base.last = iter;
	
	base.sum_x += mb.get_x();
	base.sum_y += mb.get_y();
	base.num_points++;

	sum_heights += mb.height();
	
	base.correlate();
}

// 添加字符
void char_line::add_char( const MetaBox &mb )
{
	for ( list< BoundingBox >::iterator i = const_cast<MetaBox&>( mb ).parts.begin();
	      i != const_cast<MetaBox&>( mb ).parts.end(); ++i )
		add_char( *i );
}

// 合并字符行
bool char_line::merge_line( char_line *line2 )
{
	bool retval = true;
	char_line *line1 = this;
	
	if ( base.num_points < line2->base.num_points ) 
	{
		line1 = line2;
		line2 = this;
		retval = false;
	}
	
	for ( iterator i = line2->begin(); i != line2->end(); ++i )
		line1->add_char( *i );
	
	line2->clear();
	
	return retval;
}

// 移除字符
char_line::iterator char_line::remove_char( char_line::iterator i )
{
	iterator retval;

	if ( marker == i )
		marker++;

	if ( base.first == i )
		base.first++;		// 设置为随后的元素
	
	if ( base.last == i )
	{
		if ( i == begin() )
			base.last++;	// 如果只有一个元素，则将迭代器设置到尾端
		else
			base.last--;	// 设置为前一个元素
	}
	
	base.sum_x -= i->get_x();
	base.sum_y -= i->get_y();
	base.num_points--;
	
	retval = erase( i );
		
	if ( base.num_points > 0 )
		base.correlate();
	
	return retval;
}

// 求距离
float char_line::distance( float x, float y ) const
{
	if ( base.num_points < 1 )
		return 0;

	else if ( base.num_points < min_correlation_chars )
		return y - ( begin()->get_y() + ( --end() )->get_y() )/2;
	
	else
	{
		float x2, y2;
		base.construct_perpendicular( x, y, x2, y2 );
		float dist = euklidian_distance( static_cast<float>( x ), static_cast<float>( y ), x2, y2 );
		
		if ( y < y2 )
			dist = -dist;
		
		return dist;
	}
}

// 判断是否同一条线
bool char_line::same_line( int x, int y, bool store )
{
	if ( distance( x, y ) > get_avg_height()*vert_line_dist_ratio )
	{
		// 确保字符不在同样的线上
		if ( base_line( *this ).distance( x, y ) < get_avg_height()*vert_line_dist_ratio )
			return true;

		if ( store && next_line_pos == 0 )
			next_line_pos = y;	// 第一个发现的点是下一行的起点

		return false; // 另外一行
	}
	return true;
}

// 判断字符行是否相交
bool char_line::intersects( const char_line &cl ) const
{
	float x_intersect = 0, y_intersect = 0;
	
	if ( base.intersect( cl.base, x_intersect, y_intersect ) && 
	     x_intersect >= begin()->min_x && x_intersect <= ( --end() )->max_x )
		return true;
	
	return false;
}

// 求取最大的部分
const BoundingBox* char_line::get_max_part( const base_line* baseline ) const
{
	if ( baseline == NULL )
		baseline = new base_line( *this );

	int max_height = 0;
	const BoundingBox *max_bb = NULL;
	
	for ( const_iterator mb = begin(); mb != end(); ++mb )
		
		for ( list< BoundingBox >::const_iterator bb = mb->parts.begin(); bb != mb->parts.end(); ++bb )
			
			if ( bb->height() > max_height && baseline->get_base_y( *mb ) >= 0 )
			{
				max_bb = &( *bb );
				max_height = bb->height();
			}
	
	assert( max_bb != NULL ); // 至少一个字符在基线之上
			
	return max_bb;
}

// 清空
void char_line::clear() 
{ 
	sum_heights 	= 0;
	max_width 	= 0;
	max_height 	= 0;
	next_line_pos 	= 0;
	last_x_pos 	= 0;
	done 		= false;
	marker 		= begin();
	base 		= correlation<MetaBox>(); 
	slist<MetaBox>::clear(); 
}

// Page构造函数
Page::Page( KognitionApp *app, const char *name ) : 
	QWidget( app, name ), 
	img( NULL ), 
	pix_xpos( 0 ), 
	pix_ypos( 0 ), 
	pix_scale( -1 ),
	pen_size( 1 ), 
	draw_flags( 0 ), 
	app( app )
{
	hist = new Histogram( app );
	setMouseTracking( true );
	setBackgroundMode( NoBackground );
}

// 析构函数
Page::~Page()
{
	if ( hist )
	{
		delete hist;
		hist = NULL;
	}
}

// 加载图像文件
bool Page::load( const QString &filename )
{
	bool success = scan.load( filename );		// 从文件加载图像
	if( success )
	{
		clear(); 				// 清空内部数据
		KImageEffect::toGray( scan, false ); 	// 灰度化图像
		scan = scan.convertDepth( 32 );	
		pix.convertFromImage( scan ); 
		hist->load( scan );
		scan.set_bw_threshold( hist->get_bw_threshold() );
	}
	return success;
}

// 识别
void Page::recognize( const char *data_base_def )
{	
	Image max_height_img;	// 计算旋转后的最高的字符高度
	word_collector collector;
	int last_x = 0; 		// 最后一个字符发现的位置
	int char_count = 0;		// 调试变量
	
	if ( scan.width() == 0 )
		return;
	
	// 插入缓冲行
	for ( int numline = 0; numline < num_bufferlines; numline++ )