abstract_character.cpp

matlab一些常用的处理模块

						curr_mdi.add_line(first.db_cpoint, second.db_cpoint);
					segment_area=euklidian_distance(first.db_cpoint.x,first.db_cpoint.y, second.db_cpoint.x,second.db_cpoint.y);
					new_db_line.start=second.db_cpoint;
				}
				else
				{
					if( mdi )
						curr_mdi.add_line(first.other_cpoint, second.other_cpoint);
					segment_area=euklidian_distance(first.other_cpoint.x,first.other_cpoint.y, second.other_cpoint.x,second.other_cpoint.y);
					*other_line_lower_start=second.other_cpoint;
				}
				total_area+=weight*segment_area*segment_area;
			}
		}

		if( total_area>=divergence )
			return false;

		if( is_equal(euklidian_distance(new_db_line.start.x,new_db_line.start.y, new_db_line.end.x,new_db_line.end.y),0) )
		{
			const_iterator last=db_iter;
			if( ++db_iter==db_end )
				run_loop=false;
			else
			{
				db_line=line(*last, *db_iter);
				new_db_line=db_line;
			}
		}
		else
			db_line=new_db_line;

		if( is_equal(euklidian_distance(new_other_line.start.x,new_other_line.start.y, new_other_line.end.x,new_other_line.end.y),0) )
		{
			const_iterator last=other_iter;
			if( ++other_iter==other_end )
				run_loop=false;
			else
			{
				other_line=line(*last, *other_iter);
				new_other_line=other_line;
			}
		}
		else
			other_line=new_other_line;
	} while( run_loop );

	// 处理未匹配的尾端
	point<float> p=db_line.start;
	while( db_iter!=db_end )
	{
		if( mdi )
			curr_mdi.add_line(p, *db_iter);
		float segment_area=euklidian_distance(p.x,p.y, db_iter->x,db_iter->y);
		total_area+=weight*segment_area*segment_area;
		if( total_area>=divergence )
			return false;
		p=*db_iter;
		++db_iter;
	}

	if( other_iter!=other_end )
	{
		if( mdi )
			curr_mdi.add_line(other_line.start,other_line.end);
		float segment_area=euklidian_distance(other_line.start.x,other_line.start.y, other_line.end.x,other_line.end.y);
		total_area+=weight*segment_area*segment_area;
		if( total_area>=divergence )
			return false;
		p=*other_iter;
		++other_iter;
		while( other_iter!=other_end )
		{
			weight=other_iter.get_weight();
			if( mdi )
				curr_mdi.add_line(p,*other_iter);
			float segment_area=euklidian_distance(p.x,p.y, other_iter->x,other_iter->y);
			total_area+=weight*segment_area*segment_area;
			if( total_area>=divergence )
				return false;
			p=*other_iter;
			++other_iter;
		}
	}

	divergence=total_area;
	if( mdi )
		*mdi=curr_mdi;
	#ifdef DEBUG_MATCHING
		if( mdi )
			cout << "divergence   : " << total_area << endl;
	#endif
	return true;
}

/******************************************************************************
 * 寻找连接
******************************************************************************/
bool abstract_character::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
{
	bool found=false;
	for(list<int>::const_iterator i=current_real_path.get_base_char().aspv[current_singular_point].acl.begin(); i!=current_real_path.get_base_char().aspv[current_singular_point].acl.end(); ++i)
	{
		if( current_real_path.append_connection(*i) )
		{
			int next_singular_point=current_real_path.get_base_char().acv[*i].walk(current_singular_point);
			if( current_real_path.end_point()==next_singular_point ) // connection found
			{
				if( db_path.match_connection(current_real_path,divergence,mdi) )
				{
					found=true;
					real_path=current_real_path;
				}
			}
			else
				found=find_connection(db_path,real_path,divergence,current_real_path,next_singular_point,mdi) || found;
			current_real_path.remove_last_connection();
		}
	}
	return found;
}

/******************************************************************************
 * 寻找最优路径
******************************************************************************/
void abstract_character::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
{
	for(list<int>::const_iterator i=aspv[current_path.end_point()].acl.begin(); i!=aspv[current_path.end_point()].acl.end(); ++i) // forall connections of last end_point
	{
		if( (current_path.start_point()!=current_path.end_point() || !acv[*i].is_matched) && current_path.append_connection(*i) )
		{
			if( remap[current_path.end_point()].empty() )
				find_next_cheapest_path(db_path,real_path,divergence,current_path,ac,remap,mdi);
			else
			{
				// search cheapest from all (possible) connections between the 
				// corresponding end points of the path in database char, i.e.
				// the cross product of them
				for(list<int>::const_iterator j=remap[current_path.start_point()].begin();
				    j!=remap[current_path.start_point()].end();
				    ++j)
				{
					for(list<int>::const_iterator k=remap[current_path.end_point()].begin();
					    k!=remap[current_path.end_point()].end();
					    ++k)
					{
						inner_path temp_path(ac,*j,*k);
						if( find_connection(current_path,real_path,divergence,temp_path,*j,mdi) )
							db_path=current_path;
					}
				}
			
			}
			current_path.remove_last_connection();
		}
	}
}

/******************************************************************************
 * 匹配
******************************************************************************/
float abstract_character::match(abstract_character &ac, float cut_off_divergence, match_debug_info *mdi)
{
	reset_matching_state();
	ac.reset_matching_state();

	vector<sp_mapped> map(ac.aspv.size());
	vector< list<int> > remap(aspv.size());
	for(unsigned int i=0; i<ac.aspv.size(); i++)
	{
		map[i].dist=FLT_MAX;
		map[i].db_index=-1;
		for(unsigned int j=0; j<aspv.size(); j++)
		{
			float tdist=euklidian_distance(ac.aspv[i].x, ac.aspv[i].y, aspv[j].x, aspv[j].y);

			if( !map[i].fixed && ac.aspv[i].type==end_point && aspv[j].type==end_point && tdist<0.25)
			{
				map[i].db_index=j;
				map[i].dist=tdist;
				map[i].fixed=true;
			}
			else if( (!map[i].fixed || aspv[j].type==end_point) && tdist<map[i].dist )
			{
				map[i].db_index=j;
				map[i].dist=tdist;
			}
		}
		assert( map[i].db_index!=-1 );
		remap[ map[i].db_index ].push_back( i );
	}

	float total_divergence=0;

	#ifdef DEBUG_MATCHING
		if( mdi )
		{
			cout << "--- match ---" << endl;
			cout << "database char:" << endl << *this << endl;
			cout << "real char:" << endl << ac << endl;
			for(unsigned int i=0; i<remap.size(); i++)
			{
				cout << "#" << i << ": ";
				for(list<int>::iterator j=remap[i].begin(); j!=remap[i].end(); ++j)
					cout << *j << " ";
				cout << endl;
			}
		}
	#endif

	// 首先匹配点
	for(unsigned int i=0; i<aspv.size(); i++)
	{
		int num_dots=0;
		float dist=FLT_MAX;
		for(list<int>::iterator j=remap[i].begin(); j!=remap[i].end(); ++j)
			if( ac.aspv[*j].acl.empty() )
			{
				float tdist=euklidian_distance(aspv[i].x, aspv[i].y, ac.aspv[*j].x, ac.aspv[*j].y);
				if( tdist<dist )
					dist=tdist;
				num_dots++;
			}
		if( aspv[i].acl.empty() )
		{
			if( num_dots )
				total_divergence+=dist*dist + 0.5*(num_dots-1);
			else
				total_divergence+=0.25;
		}
		else
			total_divergence+=0.5*num_dots;
		if( total_divergence>=cut_off_divergence )
			return total_divergence;
	}

	// 匹配所有的连接
	for(unsigned int i=0; i<aspv.size(); i++)
	{
		if( aspv[i].type==end_point && !aspv[i].acl.empty() && !remap[i].empty() )
		{
			float divergence=FLT_MAX;
			path db_path, real_path;
			tree_path temp_path(*this,i);
			match_debug_info curr_mdi;

			find_next_cheapest_path(db_path, real_path, divergence, temp_path, ac, remap, mdi?&curr_mdi:NULL);
			if( divergence!=FLT_MAX ) // 找到路径
			{
				#ifdef DEBUG_MATCHING
					if( mdi )
					{
						cout << "*** end_point_match ***" << endl;
						cout << "database path: " << db_path << endl;
						cout << "real path    : " << real_path << endl;
					}
				#endif
				if( mdi )
					mdi->eat_up(curr_mdi);
				total_divergence+=divergence;
				if( total_divergence>=cut_off_divergence )
					return total_divergence;
				db_path.mark();
				real_path.mark();
			}
		}
	}

	// 匹配所有内部点的连接
	for(unsigned int i=0; i<aspv.size(); i++)
	{
		if( aspv[i].type!=end_point && !remap[i].empty() )
		{
			float divergence;
			path db_path, real_path;
			tree_path temp_path(*this,i);
			match_debug_info curr_mdi;

			do {
				divergence=FLT_MAX;
				find_next_cheapest_path(db_path, real_path, divergence, temp_path, ac, remap, mdi?&curr_mdi:NULL);
				if( divergence!=FLT_MAX ) // 找到路径
				{
					#ifdef DEBUG_MATCHING
						if( mdi )
						{
							cout << "*** inner_point_match ***" << endl;
							cout << "database path: " << db_path << endl;
							cout << "real path    : " << real_path << endl;
						}
					#endif
					if( mdi )
						mdi->eat_up(curr_mdi);
					total_divergence+=divergence;
					if( total_divergence>=cut_off_divergence )
						return total_divergence;
					db_path.mark();
					real_path.mark();
				}
			} while( divergence!=FLT_MAX );
		}
	}

	// 处理未匹配的连接
	for(vector<abstract_connection>::iterator i=acv.begin(); i!=acv.end(); ++i)
	{
		total_divergence+=2*i->unmatched_area(aspv);
		if( total_divergence>=cut_off_divergence )
			return total_divergence;
	}

	for(vector<abstract_connection>::iterator i=ac.acv.begin(); i!=ac.acv.end(); ++i)
	{
		total_divergence+=2*i->unmatched_area(ac.aspv);
		if( total_divergence>=cut_off_divergence )
			return total_divergence;
	}

	return total_divergence;
}

/******************************************************************************
 * 添加矩形
 * 参数：p1      点1
 *       p2      点2
 *       p3      点3
 *       p4      点4
 *       color   颜色
 * 返回：无
******************************************************************************/
void match_debug_info::add_square(point<float> p1, point<float> p2, point<float> p3, point<float> p4, int color)
{
	square sq;
	sq.data[0]=p1;
	sq.data[1]=p2;
	sq.data[2]=p3;
	sq.data[3]=p4;
	sq.color=color;
	squares.push_back(sq);
}

/******************************************************************************
 * 添加线
 * 参数：p1      点1
 *       p2      点2
 *       color   颜色
 * 返回：无
******************************************************************************/
void match_debug_info::add_line(point<float> p1, point<float> p2, int color)
{
	line ln;
	ln.data[0]=p1;
	ln.data[1]=p2;
	ln.color=color;
	lines.push_back(ln);
}

/******************************************************************************
 * 消除
 * 参数：mdi    调试信息结构
 * 返回：无
******************************************************************************/
void match_debug_info::eat_up( match_debug_info &mdi )
{
	if( !mdi.squares.empty() )
		squares.splice(squares.end(),mdi.squares);
	if( !mdi.lines.empty() )
		lines.splice(lines.end(),mdi.lines);
}