watersheddoc.cpp

分水岭算法

	{
		INT y1 = 0;
		INT pos1 = x;
		INT inner = x + grawidth;//下一行；
		deltaxarr[pos1] = deltaxarr[inner];
		deltayarr[pos1] = deltayarr[inner];
		INT y2 = graheight-1;
		INT pos2 = y2*grawidth + x;
		inner = pos2 - grawidth;//上一行；
		deltaxarr[pos2] = deltaxarr[inner];
		deltayarr[pos2] = deltayarr[inner];
	}
	
	
	for (y=0; y<graheight; y++)
	{
		for (x=0; x<grawidth; x++)
		{
			INT temppos = y*grawidth + x;
			if ( (deltaxarr[temppos])==0 )
			{
				if (deltayarr[temppos]!=0)
				{
					deltasita[temppos] = 0;//水平方向;
					deltar[temppos] = (FLOAT) abs(deltayarr[temppos]);
				}else
				{
					deltasita[temppos] = -1;//无确定方向;
					deltar[temppos] = (FLOAT) abs(deltayarr[temppos]);
				}
				continue;
			}
			deltasita[temppos] = (FLOAT) ( atan( 
				(FLOAT)deltayarr[temppos]
				/ (FLOAT)deltaxarr[temppos] ) + PI/2. );
			deltar[temppos] = (FLOAT) sqrt((DOUBLE) 
				( deltayarr[temppos]*deltayarr[temppos]
				+ deltaxarr[temppos]*deltaxarr[temppos] ) );
		}
	}
	
	delete [] deltaxarr;
	deltaxarr = NULL; //删除水平和垂直梯度数组；
	delete [] deltayarr;
	deltayarr = NULL;
}

void CWaterShedDoc::RefreshImageObject()
{
	if(NULL!=myImageObject)
	{
		delete myImageObject;		
		myImageObject = NULL;
	}
	myImageObject = new CImageObject;
	myImageObject->CreateDIBFromBits(imageWidth, imageHeight, imageData);
}

void CWaterShedDoc::FloodVincent(MyImageGraPt *imiarr, INT *graddarr, INT minh, INT maxh, INT *flagarr, INT &outrgnumber)
{
	const INT INIT = -2;
	const INT MASK = -1;
	const INT WATERSHED = 0;
	INT h = 0;
	INT imagelen = imageWidth * imageHeight;
	for (INT i=0; i<imagelen; i++)
	{
		flagarr[i] = INIT;
	}
	//memset(flagarr, INIT, sizeof(INT)*imagelen);
	INT* imd = new INT[imagelen];//距离数组，直接存取；
	for (i=0; i<imagelen; i++)
	{
		imd[i] = 0;
	}
	//memset(imd, 0, sizeof(INT)*imagelen);
	std::queue <int> myqueue;
	INT curlabel = 0;//各盆地标记；

	for (h=minh; h<=maxh; h++)
	{
		INT stpos = graddarr[h];
		INT edpos = graddarr[h+1];
		for (INT ini=stpos; ini<edpos; ini++)
		{
			INT x = imiarr[ini].x;
			INT y = imiarr[ini].y;
			INT ipos = y*imageWidth + x;
			flagarr[ipos] = MASK;
			//以下检查该点邻域是否已标记属于某区或分水岭，若是，则将该点加入fifo;
			INT left = ipos - 1;
			if (x-1>=0) 
			{
				if (flagarr[left]>=0)
				{
					imd[ipos] = 1;
					myqueue.push(ipos);//点位置压入fifo;
					continue;
				}				
			}
			INT right = ipos + 1;
			if (x+1<imageWidth) 
			{
				if (flagarr[right]>=0) 
				{
					imd[ipos] = 1;
					myqueue.push(ipos);//点位置压入fifo;
					continue;
				}
			}
			INT up = ipos - imageWidth;
			if (y-1>=0) 
			{
				if (flagarr[up]>=0)
				{
					imd[ipos] = 1;
					myqueue.push(ipos);//点位置压入fifo;
					continue;
				}				
			}
			INT down = ipos + imageWidth;
			if (y+1<imageHeight)
			{
				if (flagarr[down]>=0) 
				{
					imd[ipos] = 1;
					myqueue.push(ipos);//点位置压入fifo;
					continue;
				}			
			}
		}

    	//以下根据先进先出队列扩展现有盆地；
		INT curdist = 1; myqueue.push(-99);//特殊标记；
		while (TRUE)
		{
			INT p = myqueue.front();
			myqueue.pop();
			if (p == -99)
			{
				if ( myqueue.empty() )
				{
					break;
				}else
				{
					myqueue.push(-99);
					curdist = curdist + 1;
					p = myqueue.front();
					myqueue.pop();
				}
			}

			//以下找p的邻域；
			INT y = (INT) (p/imageWidth);
			INT x = p - y*imageWidth;
			INT left = p - 1;
			if  (x-1>=0)
			{
				if ( ( (imd[left]<curdist) && flagarr[left]>0)
					|| (flagarr[left]==0) ) 
				{
					if ( flagarr[left]>0 )
					{
						//ppei属于某区域（不是分水岭）；
						if ( (flagarr[p]==MASK) 
							|| (flagarr[p]==WATERSHED) )
						{
							//将其设为邻点所属区域；
							flagarr[p] = flagarr[left];
						}else if (flagarr[p]!=flagarr[left])
						{
							//原来赋的区与现在赋的区不同，设为分水岭；
							//flagarr[p] = WATERSHED;
						}
					}else if (flagarr[p]==MASK)//ppei为分岭；
					{
						flagarr[p] = WATERSHED;
					}
				}else if ( (flagarr[left]==MASK) && (imd[left]==0) )
				//ppei中已MASK的点，但尚未标记（即不属某区也不是分水岭）;
				{
					imd[left] = curdist + 1; myqueue.push(left);
				}
			}
			
			INT right = p + 1;
			if (x+1<imageWidth) 
			{
				if ( ( (imd[right]<curdist) &&  flagarr[right]>0)
					|| (flagarr[right]==0) )
				{
					if ( flagarr[right]>0 )
					{
						//ppei属于某区域（不是分水岭）；
						if ( (flagarr[p]==MASK) 
							|| (flagarr[p]==WATERSHED) )
						{
							//将其设为邻点所属区域；
							flagarr[p] = flagarr[right];
						}else if (flagarr[p]!=flagarr[right])
						{
							//原来赋的区与现在赋的区不同，设为分水岭；
							//flagarr[p] = WATERSHED;
						}
					}else if (flagarr[p]==MASK)//ppei为分岭；
					{
						flagarr[p] = WATERSHED;
					}
				}else if ( (flagarr[right]==MASK) && (imd[right]==0) )
					//ppei中已MASK的点，但尚未标记（即不属某区也不是分水岭）;
				{
					imd[right] = curdist + 1; myqueue.push(right);
				}
			}
			
			INT up = p - imageWidth;
			if (y-1>=0) 
			{
				if ( ( (imd[up]<curdist) &&  flagarr[up]>0)
					|| (flagarr[up]==0) )
				{
					if ( flagarr[up]>0 )
					{
						//ppei属于某区域（不是分水岭）；
						if ( (flagarr[p]==MASK) 
							|| (flagarr[p]==WATERSHED) )
						{
							//将其设为邻点所属区域；
							flagarr[p] = flagarr[up];
						}else if (flagarr[p]!=flagarr[up])
						{
							//原来赋的区与现在赋的区不同，设为分水岭；
							//flagarr[p] = WATERSHED;
						}
					}else if (flagarr[p]==MASK)//ppei为分岭；
					{
						flagarr[p] = WATERSHED;
					}
				}else if ( (flagarr[up]==MASK) && (imd[up]==0) )
					//ppei中已MASK的点，但尚未标记（即不属某区也不是分水岭）;
				{
					imd[up] = curdist + 1; myqueue.push(up);
				}
			}
			
			INT down = p + imageWidth;
			if (y+1<imageHeight) 
			{
				if ( ( (imd[down]<curdist) &&  flagarr[down]>0)
					|| (flagarr[down]==0) )
				{
					if ( flagarr[down]>0 )
					{
						//ppei属于某区域（不是分水岭）；
						if ( (flagarr[p]==MASK) 
							|| (flagarr[p]==WATERSHED) )
						{
							//将其设为邻点所属区域；
							flagarr[p] = flagarr[down];
						}else if (flagarr[p]!=flagarr[down])
						{
							//原来赋的区与现在赋的区不同，设为分水岭；
							//flagarr[p] = WATERSHED;
						}
					}else if (flagarr[p]==MASK)//ppei为分岭；
					{
						flagarr[p] = WATERSHED;
					}
				}else if ( (flagarr[down]==MASK) && (imd[down]==0) )
					//ppei中已MASK的点，但尚未标记（既不属某区也不是分水岭）;
				{
					imd[down] = curdist + 1; myqueue.push(down);
				}	
			}

		}//以上现有盆地的扩展；

		//以下处理新发现的盆地；
		for (ini=stpos; ini<edpos; ini++)
		{
			INT x = imiarr[ini].x;
			INT y = imiarr[ini].y;
			INT ipos = y*imageWidth + x;
			imd[ipos] = 0;//重置所有距离
			if (flagarr[ipos]==MASK)
			{
				//经过前述扩展后该点仍为MASK，则该点必为新盆地的一个起始点;
				curlabel = curlabel + 1;
				myqueue.push(ipos); 
				flagarr[ipos] = curlabel;
				
				while ( myqueue.empty()==FALSE )
				{
					INT ppei = myqueue.front();
					myqueue.pop();
					INT ppeiy = (INT) (ppei/imageWidth);
			        INT ppeix = ppei - ppeiy*imageWidth;
					
					INT ppeileft = ppei - 1;
					if ( (ppeix-1>=0) && (flagarr[ppeileft]==MASK) )
					{
						myqueue.push(ppeileft);//点位置压入fifo;
						flagarr[ppeileft] = curlabel;
					}
					INT ppeiright = ppei + 1;
					if ( (ppeix+1<imageWidth) && (flagarr[ppeiright]==MASK) )
					{
						myqueue.push(ppeiright);//点位置压入fifo;
						flagarr[ppeiright] = curlabel;
					}
					INT ppeiup = ppei - imageWidth;
					if ( (ppeiy-1>=0) && (flagarr[ppeiup]==MASK) )
					{
						myqueue.push(ppeiup);//点位置压入fifo;
						flagarr[ppeiup] = curlabel;
					}
					INT ppeidown = ppei + imageWidth;
					if ( (ppeiy+1<imageHeight) && (flagarr[ppeidown]==MASK) )
					{
						myqueue.push(ppeidown);//点位置压入fifo;
						flagarr[ppeidown] = curlabel;
					}					
				}				
			}
		}//以上处理新发现的盆地；

	}

	outrgnumber = curlabel;	
	delete [] imd; imd = NULL;
}

BOOL CWaterShedDoc::OnSaveDocument(LPCTSTR lpszPathName) 
{
	// TODO: Add your specialized code here and/or call the base class
	
	//return CDocument::OnSaveDocument(lpszPathName);
	if( myImageObject != NULL )
	{
	//	CString strPathName = lpszPathName;
		myImageObject->SaveToFile( lpszPathName );
		SetModifiedFlag(FALSE);
	}	
	return TRUE;
}

	//////////////////////////////////////////////////////////////////////////
	//1、建立各区的邻域数组；
	//2、依次扫描各区域，寻找极小区域；
	//3、对每个极小区（A），在相邻区中找到最相似者；
	//4、与相似区（B）合并（各种信息刷新），在极小区（A）的邻域中
	//   删除相似区（B），在邻域数组中删除相似区（B）对应的项，将
	//   相似区（B）的相邻区s加到极小区（A）的邻域中去；
	//5、记录合并信息，设一数组专门存放该信息，该数组的第A个元素值设为B；
	//6、判断是否仍为极小区，若是则返回3；
	//7、是否所有区域都已处理完毕，若非则返回2；
	//
	//   由于各区的相邻区不会太多，因此采用邻接数组作为存储结构；
	//////////////////////////////////////////////////////////////////////////
void CWaterShedDoc::MergeRgs(MyRgnInfo *rginfoarr, INT rgnumber, INT *flag, INT width, INT height, INT *outmerge, INT &rgnum)
{

	CString* neiarr = new CString[rgnumber+1];//第一个不用；
	INT* mergearr = outmerge;//记录合并情况数组；
	
	//建立邻域数组；
	for (INT y=0; y<height; y++)
	{
		INT lstart = y * width;
		for (INT x=0; x<width; x++)
		{
			INT pos = lstart + x;
			INT left=-1, right=-1, up=-1, down=-1;
			myMath.GetNeiInt(x, y, pos, width, height
				, left, right, up, down);//找pos的四个邻域；
			//确定并刷新邻域区信息；
			INT curid = flag[pos];
			AddNeiOfCur(curid, left, right
				, up, down, flag, neiarr);
		}
	}//建立邻域数组；
	
	//区域信息数组中的有效信息从1开始，第i个位置存放第i个区域的信息；
	for (INT rgi=1; rgi<=rgnumber; rgi++)
	{
		//扫描所有区域，找极小区；
		LONG allpoints = imageWidth * imageHeight;
		LONG nmin = (LONG) (allpoints / 400);
		INT curid = rgi;
		
		//rginfoarr[rgi].isflag初始为FALSE，在被合并到其它区后改为TRUE；
		while ( ( (rginfoarr[rgi].ptcount)<nmin ) 
			&& !rginfoarr[rgi].isflag )
		{
			//该区为极小区，遍历所有相邻区，找最接近者；
			CString neistr = neiarr[curid];
			INT nearid = FindNearestNei(curid, neistr, rginfoarr, mergearr);
			//合并curid与nearid；
			MergeTwoRgn(curid, nearid, neiarr
				, rginfoarr, mergearr);			
		} 
	}
	
	//以下再合并相似区域，（无论大小）,如果不需要，直接将整个循环注释掉就行了；
	INT countjjj = 0;
	//区域信息数组中的有效信息从1开始，第i个位置存放第i个区域的信息；
	for (INT ii=1; ii<=rgnumber; ii++)
	{
		if (!rginfoarr[ii].isflag)
		{
			INT curid = ii;
			MergeNearest(curid, rginfoarr, neiarr, mergearr);
		}
	}
	
	
	
	INT counttemp = 0;
	for (INT i=0; i<rgnumber; i++)