image.cpp

这是树上的代码

// Image.cpp: implementation of the CImage class.
//
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"
#include "Image.h"

#ifdef _DEBUG
#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
#define new DEBUG_NEW
#endif

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

CImage::CImage()
{
	m_lpImgBits=NULL;
	m_lpnMark=NULL;
	m_lpBMPFileData=NULL;
	m_lpShowMark=NULL;
}

CImage::~CImage()
{
	Clear();
}

long CImage::MarkImage(BYTE bObjectGray)
{
//bObjectGray为目标的灰度值，文本可以设为255
/* 申请标记数组空间，记得要在CImage类的构造函数
中将m_lpnMark初始化为NULL 。*/

	if ( m_lpnMark==NULL )
	{	m_lpnMark= new int[m_ulngBitsCount];
		ASSERT( m_lpnMark != NULL );
		m_lpnMarkMove=m_lpnMark;
	}
	::memset((LPBYTE)m_lpnMark,0,m_ulngBitsCount*4); 

	int nMarkValue=1;           
	/* 每次标识的值，nMarkValue会在后边递增，
	来表示不同的区域，从1开始标记。 */
	int nMaxMarkValue=0;     //记录最大的标识的值
	int i,j;                 //循环控制变量

	/* 定义存放等价对的链表，其元素是 EqualMark类型，
	定义list是为了节约存储空间。要使用Clist，
	应该#include <Afxtempl.h>。  */
	CList < EqualMark,EqualMark > lEqualMark;

	//初始化图像移动指针
	m_lpImgBitsMove = m_lpImgBits;

	/*进行第一次扫描，将所得的等价对(EqualMark类型)加到lEqualMark链表中。
	使用nMarkValue来进行每一次新的标记，标记之后将其值加1。
	由于版面关系，这部分代码也同样略去不写。作者提出以下几点编程时要注意
	的地方。
	Note1：图像的四周像素并不会有8个相邻的像素。这时就要根据上、下、左、
	右四种不同的情况做不同的寻找等价对的判断。
	Note2：可以先对等价对进行排序，每次都保证MarkValue1<MarkValue2，
	这样易于管理等价对。
	Note3：在实际工作中，连续寻找出的等价对很容易重复，将本次找出的等价对
	和链表中保存的最后一个等价对相比较，如果不相等的话再存入等价对链表，
	这样可以大大降低链表中等价对的重复。
	Note4：第一次扫描之后，nMarkValue-1即为nMaxMarkValue。 */

/************************************************************************/
//下面为补充代码,完成对图象的第一次扫描

	//初始化图象数组和标识数组的指针
	int nEqualNum=0;
	EqualMark tempEqualMark;    //用以暂时存放每次找到的等价关系
	m_lpnMarkMove=m_lpnMark;
	m_lpImgBitsMove = m_lpImgBits;
	

	//标记图象的第一行、第一列的象素(只有这一个象素)
	if ( *m_lpImgBitsMove==bObjectGray )
	{
		*m_lpnMarkMove=nMarkValue++;
	}
	m_lpnMarkMove++;
	m_lpImgBitsMove++;

	//标记图象的第一行，此时不会出现等价的情况
	for ( i=1; i <= m_lngWidth; i++)
	{
		//需要标记的情况
		if ( *m_lpImgBitsMove==bObjectGray )
		{	
			//前面没有被标记过，则开始一个新的标记
			if ( *(m_lpnMarkMove-1)==0 ) 
			{
				*m_lpnMarkMove=nMarkValue++;
			}
			//前面被标记过，则跟随前一个标记
			else
			{
				*m_lpnMarkMove=*(m_lpnMarkMove-1);
			}
		}
		m_lpnMarkMove++;
		m_lpImgBitsMove++;
	}
	
	//除第一行之外的标记，此时会出现等价的关系
	for ( j=1; j <= m_lngHeight; j++ )
	{
		m_lpImgBitsMove=m_lpImgBits+j*m_lngWidthBytes;
		m_lpnMarkMove=m_lpnMark+j*m_lngWidthBytes;
		
		//对每行的第一个点做处理，总体就是对图象的最左列做处理
		//只需要检视上，右上两个点 
		if ( *m_lpImgBitsMove==bObjectGray )
		{	
			//<上>位置被标记过
			if ( *(m_lpnMarkMove-m_lngWidthBytes)!=0 ) 
			{	
				//跟随<上>标记
				*m_lpnMarkMove=*(m_lpnMarkMove-m_lngWidthBytes);
				if ( *(m_lpnMarkMove-m_lngWidthBytes)!=*(m_lpnMarkMove-m_lngWidthBytes+1) && *(m_lpnMarkMove-m_lngWidthBytes+1)!=0)
				{
					//<上><右上>等价标记
					AttachEqualMark(tempEqualMark,*(m_lpnMarkMove-m_lngWidthBytes),
						*(m_lpnMarkMove-m_lngWidthBytes+1),nEqualNum,lEqualMark);
				}
				
			}
			//<上>没有标记，此时一定不会存在等价关系
			else 
			{
				if ( *(m_lpnMarkMove-m_lngWidthBytes+1)!=0 )	
				{
					*m_lpnMarkMove=*(m_lpnMarkMove-m_lngWidthBytes+1);   //跟随<右上>标记
				}
				//<上>、<右上>都没有标记，则开始新的标记
				else
				{
					*m_lpnMarkMove=nMarkValue++;
				}
			}
		}
		m_lpnMarkMove++;
		m_lpImgBitsMove++;

		//对每行的中间点做标记处理，此时存在<左>、<左上>、<上>、<右上> 4种情况
		for ( i=1; i<=m_lngWidth-1; i++ )
		{	
			//需要标记
			if ( (*m_lpImgBitsMove)==bObjectGray )
			{	
				//<左>被标记过
				if ( *(m_lpnMarkMove-1)!=0 )
				{
					*m_lpnMarkMove=*(m_lpnMarkMove-1);          //跟随<左>
					
					if ( *(m_lpnMarkMove-1)!=*(m_lpnMarkMove-m_lngWidthBytes-1) && *(m_lpnMarkMove-m_lngWidthBytes-1)!=0 )
					{
						//标记<左>、<左上>等价
						AttachEqualMark(tempEqualMark,*(m_lpnMarkMove-1),
						*(m_lpnMarkMove-m_lngWidthBytes-1),nEqualNum,lEqualMark);
					}
					
					if ( *(m_lpnMarkMove-1)!=*(m_lpnMarkMove-m_lngWidthBytes) && *(m_lpnMarkMove-m_lngWidthBytes)!=0)
					{
						//标记<左>、<上>等价
						AttachEqualMark(tempEqualMark,*(m_lpnMarkMove-1),
						*(m_lpnMarkMove-m_lngWidthBytes),nEqualNum,lEqualMark);
					}

					if ( *(m_lpnMarkMove-1)!=*(m_lpnMarkMove-m_lngWidthBytes+1) && *(m_lpnMarkMove-m_lngWidthBytes+1)!=0)
					{
						//标记<左>、<右上>等价
						AttachEqualMark(tempEqualMark,*(m_lpnMarkMove-1),
						*(m_lpnMarkMove-m_lngWidthBytes+1),nEqualNum,lEqualMark);
					}
				}
				//<左>未被标记过
				else
				{
					//<左上>被标记过
					if ( *(m_lpnMarkMove-m_lngWidthBytes-1)!=0 )
					{
						*m_lpnMarkMove=*(m_lpnMarkMove-m_lngWidthBytes-1);

						if ( *(m_lpnMarkMove-m_lngWidthBytes-1)!=*(m_lpnMarkMove-m_lngWidthBytes) && *(m_lpnMarkMove-m_lngWidthBytes)!=0)
						{
							//标记<左上>、<上>等价
							AttachEqualMark(tempEqualMark,*(m_lpnMarkMove-m_lngWidthBytes-1),
								*(m_lpnMarkMove-m_lngWidthBytes),nEqualNum,lEqualMark);
						}
						
						if ( *(m_lpnMarkMove-m_lngWidthBytes-1)!=*(m_lpnMarkMove-m_lngWidthBytes+1) && *(m_lpnMarkMove-m_lngWidthBytes+1)!=0)
						{
							//标记<左上>、<右上>等价
							AttachEqualMark(tempEqualMark,*(m_lpnMarkMove-m_lngWidthBytes-1),
								*(m_lpnMarkMove-m_lngWidthBytes+1),nEqualNum,lEqualMark);
						}


					}
					//<左>、<左上>未标记过
					else 
					{
						if ( *(m_lpnMarkMove-m_lngWidthBytes)!=0 )
						{
							*m_lpnMarkMove=*(m_lpnMarkMove-m_lngWidthBytes);        	//跟随<上>标记
							
							if ( *(m_lpnMarkMove-m_lngWidthBytes)!=*(m_lpnMarkMove-m_lngWidthBytes+1) && *(m_lpnMarkMove-m_lngWidthBytes+1)!=0 )
							{
								//标记<上>和<右上>等价
								AttachEqualMark(tempEqualMark,*(m_lpnMarkMove-m_lngWidthBytes),
									*(m_lpnMarkMove-m_lngWidthBytes+1),nEqualNum,lEqualMark);
							}
						}
						//<左>、<左上>、<上>未标记过，此时不存在等价关系
						else
						{
							if (*(m_lpnMarkMove-m_lngWidthBytes+1)!=0)
							{
								*m_lpnMarkMove=*(m_lpnMarkMove-m_lngWidthBytes+1);    	//跟随<右上>标记
							}
							//<左>、<左上>、<上>、<右上>未标记过，则开始新的标记值
							else
							{
								*m_lpnMarkMove=nMarkValue++;
							}

						}    //<左>、<左上>、<上>未标记过结束
					}   //<左>、<左上>未标记过结束
				}  //<左>未被标记过结束
			}     // else 不需要标记
				
			m_lpnMarkMove++;
			m_lpImgBitsMove++;
		}       //中间点处理的结束

		//对每行的最后一个点做处理，总体就是对图象的最左列做处理
		//此时存在<左>、<左上>、<上> 3种情况
		
		//需要标记
		if ( (*m_lpImgBitsMove)==bObjectGray )
		{	
			//<左>被标记过
			if ( *(m_lpnMarkMove-1)!=0 )
			{
				*m_lpnMarkMove=*(m_lpnMarkMove-1);

				if ( *(m_lpnMarkMove-1)!=*(m_lpnMarkMove-m_lngWidthBytes-1) && *(m_lpnMarkMove-m_lngWidthBytes-1)!=0)
				{
					//标记<左>、<左上>等价
					AttachEqualMark(tempEqualMark,*(m_lpnMarkMove-1),
					*(m_lpnMarkMove-m_lngWidthBytes-1),nEqualNum,lEqualMark);
				}
				
				if ( *(m_lpnMarkMove-1)!=*(m_lpnMarkMove-m_lngWidthBytes) && *(m_lpnMarkMove-m_lngWidthBytes)!=0)
				{
					//标记<左>、<上>等价
					AttachEqualMark(tempEqualMark,*(m_lpnMarkMove-1),
					*(m_lpnMarkMove-m_lngWidthBytes),nEqualNum,lEqualMark);
				}
				
			}
			//<左>未被标记过
			else
			{
				if ( *(m_lpnMarkMove-m_lngWidthBytes-1)!=0 )
				{
					*m_lpnMarkMove=*(m_lpnMarkMove-m_lngWidthBytes-1);    //跟随<左上>

					if ( *(m_lpnMarkMove-m_lngWidthBytes-1)!=*(m_lpnMarkMove-m_lngWidthBytes) && *(m_lpnMarkMove-m_lngWidthBytes)!=0)
					{
						//标记<左上>、<上>等价
						AttachEqualMark(tempEqualMark,*(m_lpnMarkMove-m_lngWidthBytes-1),
							*(m_lpnMarkMove-m_lngWidthBytes),nEqualNum,lEqualMark);
					}
					
				}
				//<左>、<左上>未标记过
				else 
				{
					if ( *(m_lpnMarkMove-m_lngWidthBytes)!=0 )
					{
						*m_lpnMarkMove=*(m_lpnMarkMove-m_lngWidthBytes);   	//跟随<上>标记
					}
					//<左>、<左上>、<上>未标记过,则开始新的标记值
					else
					{
						*m_lpnMarkMove=nMarkValue++;
					}

				}
			}
		}  //对每行的最后一个点做处理，总体就是对图象的最左列做处理
		
	}     //"除第一行之外的标记"的结束
	
	//因为在每次标记完之后，nMarkValue都会自动++
	//所以要通过（-1）操作来记录所标记的最大的个数

	nMaxMarkValue=nMarkValue-1;
/************************************************************************/
	/* 定义双层链表的外层链表，它的元素是一个指向内层链表的指针。
	内层链表的型别也是CptrList，其元素是标记值。 */
	CPtrList exList;
	CPtrList * pInnerList;
	POSITION posExElem;	

	if ( lEqualMark.GetCount() !=0 )
	{
		// pInnerListAdd，每次向exList中添加的新元素
		CPtrList * pInnerListAdd=new CPtrList;     
		ASSERT ( pInnerListAdd != NULL );

		/* 添加第一个等价对到exList的第一个元素所指向的InnerList中。  */
		pInnerListAdd->AddTail(	(void *)lEqualMark.GetHead().MarkValue1);
		pInnerListAdd->AddTail(	(void *)lEqualMark.GetHead().MarkValue2);
		exList.AddTail( (void *)pInnerListAdd );
		lEqualMark.RemoveHead();
				
		/* 定义pFindValue1和pFindValue2， 存放在所有内层链表中找到特定值
		的某个内层链表的头指针，也就是外层链表的某个元素值。 */
		CPtrList * pFindValue1=NULL;
		CPtrList * pFindValue2=NULL;

		//整理剩余的等价对
		while ( !lEqualMark.IsEmpty() )
		{	
			posExElem=exList.GetHeadPosition();
			pFindValue1=NULL;
			pFindValue2=NULL;

			while ( posExElem )
			{
				pInnerList=(CPtrList *)exList.GetAt(posExElem);
				if ( pInnerList->Find( (void *)lEqualMark.GetHead().MarkValue1) )
				{	
					pFindValue1=pInnerList;
				}
				if( pInnerList->Find( (void *)lEqualMark.GetHead().MarkValue2) ) 
				{	
					pFindValue2=pInnerList;
				}
				exList.GetNext(posExElem);
			}

			//该等价对中两个值都在已经整理过的等价关系中
			if ( pFindValue1 && pFindValue2 )
			{	
				//当两个地址不一样时，对链表进行调整
				if ( pFindValue1!=pFindValue2 )
				{		
					pFindValue1->AddTail(pFindValue2);
					/* 清除链表元素，通过new得到的CptrList 类型，
					必须采用delete进行删除，否则会造成内存泄露。*/
					POSITION posDelete = exList.Find((void *)pFindValue2);
					pFindValue2->RemoveAll();
					delete pFindValue2;
					exList.RemoveAt( posDelete );
				}
			}
			/* 只在已经整理过的等价关系中找到Value1，
			那么将Vaule2加到Value1所在的链表中。 */
			else if ( pFindValue1 )
			{
				pFindValue1->AddTail((void *)lEqualMark.GetHead().MarkValue2 );
			}
			else if ( pFindValue2)
			{
				pFindValue2->AddTail( (void *)lEqualMark.GetHead().MarkValue1 );
			}
			/* 等价对中两个值在整理过的等价关系中都
			没有找到，则在exList中增加新元素。 */
			else
			{
				CPtrList * pInnerListAdd=new CPtrList;
				pInnerListAdd->AddTail( (void *)lEqualMark.GetHead().MarkValue1 );
				pInnerListAdd->AddTail( (void *)lEqualMark.GetHead().MarkValue2 );
				exList.AddTail((void *)pInnerListAdd);
			}			
			//去掉此时等价对的头元素
			lEqualMark.RemoveHead(); 
		}  // while ( !lEqualMark.IsEmpty() )循环结束
	}  // if ( lEqualMark.GetCount() !=0 )语句结束
	/* 等价对链表大小为0，说明第一次扫描之后没有产生等价对，标记已经完成。 */
	else   
	{return TRUE; }		

	/*等价关系整理完成，下面建立第一次扫描的标记值和
	第二次扫描的标记值之间的映射关系。*/

	int nTotalEqualNum=0; //列入等价关系的标记个数
	int nMarkRegion=0;   //图像中连通区域个数

	posExElem=exList.GetHeadPosition();
	while ( posExElem )
	{	
		pInnerList=(CPtrList *)exList.GetAt(posExElem);
		nTotalEqualNum += pInnerList->GetCount();
		exList.GetNext(posExElem);
	}
	nMarkRegion=nMaxMarkValue-nTotalEqualNum+exList.GetCount();

	/* 定义第一次扫描和第二次扫描之间的映射向量，要使用vector，
	应该#include <vector>并且使用std命名空间。 */
	vector<MarkMapping> vMarkMap(nMaxMarkValue); 

	//初始化映射向量，令其做自身映射