区域增长算法

╰半橙微兮° 2022-05-28 22:53 181阅读 0赞

**[http://blog.csdn.net/byxdaz/article/details/765158][http_blog.csdn.net_byxdaz_article_details_765158]**

**区域增长算法递归实现**

void RegionGrowTwo(int nSeedX, int nSeedY, BYTE \* pUnchInput,BYTE \* D, int nWidth, int nHeight, BYTE \* pUnRegion,int &iLeft,int & iRight,int & iTop,int & iBottom)  
\{  
int nDx\[\] = \{-1,1,0,0\};  
int nDy\[\] = \{0,0,-1,1\};  
int k=0;  
int nCurrX ;  
int nCurrY ;  
int xx=0,yy=0;  
nCurrX = nSeedX;  
nCurrY = nSeedY;  
if(nCurrX<iLeft)  
iLeft = nCurrX;  
if(nCurrX>iRight)  
iRight = nCurrX;  
if(nCurrY<iTop)  
iTop = nCurrY;  
if(nCurrY>iBottom)  
iBottom = nCurrY;  
  
// pUnRegion\[nCurrY\*nWidth+nCurrX\] = 255 ;  
// 对当前点的4邻域进行遍历  
int times = 0;  
for (k=0; k<4; k++)  
\{  
// 4邻域象素的坐标  
xx = nCurrX+nDx\[k\];  
yy = nCurrY+nDy\[k\];

// 判断象素(xx，yy) 是否在图像内部  
// 判断象素(xx，yy) 是否已经处理过  
// pUnRegion\[yy\*nWidth+xx\]==0 表示还没有处理

// 生长条件：判断象素(xx，yy)和当前象素(nCurrX,nCurrY) 象素值差的绝对值  
if ( (xx < nWidth) && (xx>=0) && (yy>=0) && (yy<nHeight)  
&& (pUnRegion\[yy\*nWidth+xx\]==0) && (pUnchInput\[yy\*nWidth+xx\]==1))  
\{  
// 同时也表明该象素处理过  
pUnRegion\[yy\*nWidth+xx\] = 255 ;  
if(xx<iLeft)  
iLeft = xx;  
if(xx>iRight)  
iRight = xx;  
if(yy<iTop)  
iTop = yy;  
if(yy>iBottom)  
iBottom = yy;  
  
RegionGrowTwo(xx,yy,pUnchInput,D,nWidth,nHeight,pUnRegion,iLeft,iRight,iTop,iBottom);  
\}  
else  
times++;  
\}

/\*  
\* 区域增长，递归实现  
\* S,源图象  
D,目标图象  
ImageWidth,ImageHeight,表示图象的宽、高  
\*/  
void RegionGrowOne(BYTE \*S,BYTE \*D,int ImageWidth,int ImageHeight)  
\{  
int iLeft=0,iRight=0,iTop=0,iBottom=0;  
int k1,k2,k3,k4,ii1=0,off=0;  
int i=0,j=0;  
LPBYTE lpFlag = new BYTE\[ImageWidth\*ImageHeight\];  
memset(lpFlag,0,ImageWidth\*ImageHeight);  
memcpy(D,S,ImageWidth\*ImageHeight);  
for (i=0; i<ImageHeight; i++)  
\{  
for (j=0; j<ImageWidth; j++)  
\{  
if (S\[i\*ImageWidth+j\] == 1 && lpFlag\[i\*ImageWidth+j\] == 0)  
\{  
iLeft=65535,iRight=0,iTop=65535,iBottom=0;  
RegionGrowTwo(j,i,S,D,ImageWidth,ImageHeight,lpFlag,iLeft,iRight,iTop,iBottom);  
if((iRight-iLeft)>40 && (iBottom-iTop)>40) //表示区域大于40\*40时就画出边框  
\{  
//画边框  
k1 = (iLeft -1 )<0 ?0:(iLeft -1 );  
k2 = (iRight+1)>=ImageWidth?(ImageWidth-1):(iRight+1);  
k3 = (iTop-1)<0?0:(iTop-1);  
k4 = (iBottom+1)>=ImageHeight?(ImageHeight-1):(iBottom+1);  
for(ii1 = k1;ii1 <= k2;ii1++)  
\{  
off = ii1 + k3\*ImageWidth;  
D\[off\] = 11;  
off = ii1 + k4\*ImageWidth;  
D\[off\] = 11;  
\}  
for(ii1 = k3 ;ii1<=k4;ii1++)  
\{  
off = ii1 \* ImageWidth + k1;  
D\[off\] = 11;  
off = ii1 \* ImageWidth + k2;  
D\[off\] = 11;  
\}  
/  
\}  
\}  
\}  
  
\}

if(lpFlag!=NULL)  
\{  
delete \[\]lpFlag;  
lpFlag = NULL;  
\}

[http://blog.csdn.net/byxdaz/article/details/753236][http_blog.csdn.net_byxdaz_article_details_753236]

**区域增长算法**

cndg

区域增长的算法实现: 1)根据图像的不同应用选择一个或一组种 子,它或者是最亮或最暗的点,或者是位 于点簇中心的点 2...通过像素集合的区域增长算法实现: 区域A 区域B 种子像素增长.3)增长的规则 4)  
结束条件.

BOOL RegionGrow(int nSeedX, int nSeedY, BYTE \* pUnchInput,int nWidth, int nHeight, BYTE \* pUnRegion,CRect &R)  
\{

int nDx\[\] = \{-1,1,0,0\};  
int nDy\[\] = \{0,0,-1,1\};  
int nSaveWidth = nWidth;  
  
// 定义堆栈，存储坐标  
int \* pnGrowQueX ;  
int \* pnGrowQueY ;

// 分配空间  
pnGrowQueX = new int \[nWidth\*nHeight\];  
pnGrowQueY = new int \[nWidth\*nHeight\];

// 定义堆栈的起点和终点  
// 当nStart=nEnd, 表示堆栈中只有一个点  
int nStart ;  
int nEnd ;

//初始化  
nStart = 0 ;  
nEnd = 0 ;

// 把种子点的坐标压入栈  
pnGrowQueX\[nEnd\] = nSeedX;  
pnGrowQueY\[nEnd\] = nSeedY;

// 当前正在处理的象素  
int nCurrX ;  
int nCurrY ;

// 循环控制变量  
int k ;

// 图象的横纵坐标,用来对当前象素的8邻域进行遍历  
int xx;  
int yy;

while (nStart<=nEnd)  
\{  
// 当前种子点的坐标  
nCurrX = pnGrowQueX\[nStart\];  
nCurrY = pnGrowQueY\[nStart\];

// 对当前点的4邻域进行遍历  
for (k=0; k<4; k++)  
\{  
// 4邻域象素的坐标  
xx = nCurrX+nDx\[k\];  
yy = nCurrY+nDy\[k\];

// 判断象素(xx，yy) 是否在图像内部  
// 判断象素(xx，yy) 是否已经处理过  
// pUnRegion\[yy\*nWidth+xx\]==0 表示还没有处理

// 生长条件：判断象素(xx，yy)和当前象素(nCurrX,nCurrY) 象素值差的绝对值  
if ( (xx < nWidth) && (xx>=0) && (yy>=0) && (yy<nHeight)  
&& (pUnRegion\[yy\*nWidth+xx\]==0) && (pUnchInput\[yy\*nSaveWidth+xx\]==1))  
\{  
// 堆栈的尾部指针后移一位  
nEnd++;

// 象素(xx，yy) 压入栈  
pnGrowQueX\[nEnd\] = xx;  
pnGrowQueY\[nEnd\] = yy;

// 把象素(xx，yy)设置成逻辑1（255）  
// 同时也表明该象素处理过  
pUnRegion\[yy\*nWidth+xx\] = 255 ;  
\}  
\}  
nStart++;  
\}  
  
  
//找出区域的范围  
int nMinx=pnGrowQueX\[0\], nMaxx=pnGrowQueX\[0\], nMiny=pnGrowQueY\[0\], nMaxy = pnGrowQueY\[0\];  
for (k=0; k<nEnd; k++)  
\{  
if (pnGrowQueX\[k\] > nMaxx)  
nMaxx = pnGrowQueX\[k\];  
if (pnGrowQueX\[k\] < nMinx)  
nMinx = pnGrowQueX\[k\];  
if (pnGrowQueY\[k\] > nMaxy)  
nMaxy = pnGrowQueY\[k\];  
if (pnGrowQueY\[k\] < nMiny)  
nMiny = pnGrowQueY\[k\];  
\}  
  
if ((nMaxy - nMiny) > 40 && (nMaxx - nMinx) > 40)  
\{  
R.left = nMinx;  
R.right = nMaxx;  
R.top = nMiny;  
R.bottom = nMaxy;  
return TRUE;  
\}  
// 释放内存  
delete \[\]pnGrowQueX;  
delete \[\]pnGrowQueY;  
pnGrowQueX = NULL ;  
pnGrowQueY = NULL ;  
return FALSE;  
\}

//调用方法  
void OnButton(LPBYTE S,int ImageWidth,int ImageHeight)  
\{  
int i=0,j=0;  
CRect rect;  
LPBYTE lpFlag = new BYTE\[ImageWidth\*ImageHeight\];  
memset(lpFlag,0,ImageWidth\*ImageHeight);  
for (i=0; i<ImageHeight; i++)  
\{  
for (j=0; j<ImageWidth; j++)  
\{  
if (S\[i\*ImageWidth+j\] == 1 && lpFlag\[i\*ImageWidth+j\] == 0)  
\{  
RegionGrow(j, i, S, ImageWidth, ImageHeight, lpFlag,rect);  
\}  
\}  
  
\}

if(lpFlag!=NULL)  
\{  
delete \[\]lpFlag;  
lpFlag = NULL;  
\}  
\}

**区域标记算法**

cndg 2006-4-15

这里介绍区域标记算法，所谓区域标记就是把连续区域作同一个标记，常见的四邻域标记算法和八邻域标记算法。现在就介绍它们的基本思想。

1、  四邻域标记算法：

1） 判断此点四邻域中的最左，最上有没有点，如果都没有点，则表示一个新的区域的开始。

2） 如果此点四邻域中的最左有点，最上没有点，则标记此点为最左点的值；如果此点四邻域中的最左没有点，最上有点，则标记此点为最上点的值。

3） 如果此点四邻域中的最左有点，最上都有点，则标记此点为这两个中的最小的标记点，并修改大标记为小标记。

2、  八邻域标记算法：

1） 判断此点八邻域中的最左，左上，最上，上右点的情况。如果都没有点，则表示一个新的区域的开始。

2） 如果此点八邻域中的最左有点，上右都有点，则标记此点为这两个中的最小的标记点，并修改大标记为小标记。

3） 如果此点八邻域中的左上有点，上右都有点，则标记此点为这两个中的最小的标记点，并修改大标记为小标记。

4） 否则按照最左，左上，最上，上右的顺序，标记此点为四个中的一个。

注意：在这个过程中也可以求出每个不同标记点的数量，矩形区域。

3、实例

/\*

l 函数说明：把I\[off\]的连续区域的标识为num，并求出其区域矩形

l 参数说明：I，为图像数组，off为坐标偏移量，num为标记，rect为标记的矩形范围

l 返回值：int，为标记是num的点数。

\*/

intFillAreaFlag(LPBYTEI,intoff,intnum,CRect& rect)

boolbNew;

intm,n,i,j,k,nDot=1,offset,offtemp,yMin;

intdxy\[8\],x,y;

dxy\[0\]=-ImageWidth\-1; dxy\[1\]=-ImageWidth; dxy\[2\]=-ImageWidth\+1;

dxy\[3\]=-1; dxy\[4\]=1;

dxy\[5\]=ImageWidth\-1; dxy\[6\]=ImageWidth; dxy\[7\]=ImageWidth\+1;

rect.left=65535; rect.right=-1;

rect.bottom=65535; rect.top=-1;

if(I\[off\]>0 && I\[off\]!=num)

I\[off\]=num;

x=off%ImageWidth;

y=off/ImageWidth;

if(x<rect.left)

rect.left=x;

if(x>rect.right)

rect.right=x;

if(y<rect.bottom)

rect.bottom=y;

if(y>rect.top)

rect.top=y;

else

return 0;

for(i=y; i<ImageHeight; i\++)

bNew=false;

yMin=i;

for(j=0; j<ImageWidth; j\++)

offset=i\*ImageWidth\+j;

if(I\[offset\]==num)

for(k=0; k<8; k\++)

if(i==0 && k<=2)

continue;

if(i==ImageHeight\-1 && k>=5)

continue;

if(j==0 && (k==0 || k==3 ||  k==5))

continue;

if(j==ImageWidth\-1 && (k==2 ||  k==4 || k==7))

continue;

offtemp=offset\+dxy\[k\];

if(I\[offtemp\]>0 && I\[offtemp\]!=num)

I\[offtemp\]=num;

nDot\++;

m=offtemp/ImageWidth;

n=offtemp%ImageWidth;

if(n < rect.left)

rect.left=n;

if(n > rect.right)

rect.right=n;

if(m < rect.bottom)

rect.bottom=m;

if(m > rect.top)

rect.top=m;

y=offtemp/ImageWidth;

if(y<=yMin)

yMin=y;

if(!bNew)

bNew=true;

if(bNew)

i=yMin\-1;

returnnDot;

[http://blog.csdn.net/byxdaz/article/details/664545][http_blog.csdn.net_byxdaz_article_details_664545]

/\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*  
\*  
\* //函数名称：  
\* RegionGrow()  
\*  
\* //输入参数:  
\* CDib \* pDib - 指向CDib类的指针，含有原始图象信息  
\* unsigned char \* pUnRegion - 指向区域生长结果的指针  
\*  
\* //返回值:  
\* 无  
\*  
\* //说明:  
\* pUnRegion指针指向的数据区存储了区域生长的结果，其中1（逻辑）表示  
\* 对应象素为生长区域，0表示为非生长区域  
\* 区域生长一般包含三个比较重要的问题：  
\* 1. 种子点的选取  
\* 2. 生长准则  
\* 3. 终止条件  
\* 可以认为，这三个问题需要具体分析，而且每个问题解决的好坏直接关系到  
\* 区域生长的结果。  
\* 本函数的种子点选取为图像的中心，生长准则是相邻象素的象素值小于  
\* nThreshold, 终止条件是一直进行到再没有满足生长准则需要的象素时为止  
\*  
\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*  
\*/  
void RegionGrow(CDib \* pDib, unsigned char \* pUnRegion, int nThreshold)  
\{  
static int nDx\[\]=\{-1,0,1,0\};  
static int nDy\[\]=\{0,1,0,-1\};  
  
// 遍历图象的纵坐标  
// int y;  
  
// 遍历图象的横坐标  
// int x;  
  
// 图象的长宽大小  
CSize sizeImage = pDib->GetDimensions();  
int nWidth = sizeImage.cx ;  
int nHeight = sizeImage.cy ;  
  
// 图像在计算机在存储中的实际大小  
CSize sizeImageSave = pDib->GetDibSaveDim();  
  
// 图像在内存中每一行象素占用的实际空间  
int nSaveWidth = sizeImageSave.cx;  
  
// 初始化  
memset(pUnRegion,0,sizeof(unsigned char)\*nWidth\*nHeight);  
  
// 种子点  
int nSeedX, nSeedY;  
  
// 设置种子点为图像的中心  
nSeedX = nWidth /2 ;  
nSeedY = nHeight/2 ;  
  
// 定义堆栈，存储坐标  
int \* pnGrowQueX ;  
int \* pnGrowQueY ;  
  
// 分配空间  
pnGrowQueX = new int \[nWidth\*nHeight\];  
pnGrowQueY = new int \[nWidth\*nHeight\];  
  
// 图像数据的指针  
unsigned char \* pUnchInput =(unsigned char \* )pDib->m\_lpImage;  
  
// 定义堆栈的起点和终点  
// 当nStart=nEnd, 表示堆栈中只有一个点  
int nStart ;  
int nEnd ;  
  
//初始化  
nStart = 0 ;  
nEnd = 0 ;  
  
// 把种子点的坐标压入栈  
pnGrowQueX\[nEnd\] = nSeedX;  
pnGrowQueY\[nEnd\] = nSeedY;  
  
// 当前正在处理的象素  
int nCurrX ;  
int nCurrY ;  
  
// 循环控制变量  
int k ;  
  
// 图象的横纵坐标,用来对当前象素的4邻域进行遍历  
int xx;  
int yy;  
  
while (nStart<=nEnd)  
\{  
// 当前种子点的坐标  
nCurrX = pnGrowQueX\[nStart\];  
nCurrY = pnGrowQueY\[nStart\];  
  
// 对当前点的4邻域进行遍历  
for (k=0; k<4; k++)  
\{  
// 4邻域象素的坐标  
xx = nCurrX+nDx\[k\];  
yy = nCurrY+nDy\[k\];  
  
// 判断象素(xx，yy) 是否在图像内部  
// 判断象素(xx，yy) 是否已经处理过  
// pUnRegion\[yy\*nWidth+xx\]==0 表示还没有处理  
  
// 生长条件：判断象素(xx，yy)和当前象素(nCurrX,nCurrY) 象素值差的绝对值  
if ( (xx < nWidth) && (xx>=0) && (yy<nHeight) && (yy>=0)  
&& (pUnRegion\[yy\*nWidth+xx\]==0) && abs(pUnchInput\[yy\*nSaveWidth+xx\] - pUnchInput\[nCurrY\*nSaveWidth+nCurrX\])<nThreshold )  
\{  
// 堆栈的尾部指针后移一位  
nEnd++;  
  
// 象素(xx，yy) 压入栈  
pnGrowQueX\[nEnd\] = xx;  
pnGrowQueY\[nEnd\] = yy;  
  
// 把象素(xx，yy)设置成逻辑1（255）  
// 同时也表明该象素处理过  
pUnRegion\[yy\*nWidth+xx\] = 255 ;  
\}  
\}  
nStart++;  
\}  
  
// 释放内存  
delete \[\]pnGrowQueX;  
delete \[\]pnGrowQueY;  
pnGrowQueX = NULL ;  
pnGrowQueY = NULL ;  
\}

对于2D图象的组织增长，使用递归也是一种不错的选择，但需要注意栈空间需要设大一些。  
而在3D数据场上，递归几乎是不可行的，栈空间经常会出现溢出的情况，因此不具备实用性。  
2D组织增长伪代码如下  
  
组织增长(Image\* pImage, int i, ing j, byte\* mask)  
\{  
if 不满足增长条件（pImage, i,j, mask)  
return;  
设置标记(mask, i, j);  
组织增长(pImage, i-1, j, mask);  
组织增长(pImage, i+1, j, mask);  
组织增长(pImage, i, j-1, mask);  
组织增长(pImage, i, j+1, mask);  
\}  
  
至于将递归程序改为迭代程序，可以看一看《程序设计方法学》

[http://blog.csdn.net/byxdaz/article/details/626140][http_blog.csdn.net_byxdaz_article_details_626140]

[http_blog.csdn.net_byxdaz_article_details_765158]: http://blog.csdn.net/byxdaz/article/details/765158
[http_blog.csdn.net_byxdaz_article_details_753236]: http://blog.csdn.net/byxdaz/article/details/753236
[http_blog.csdn.net_byxdaz_article_details_664545]: http://blog.csdn.net/byxdaz/article/details/664545
[http_blog.csdn.net_byxdaz_article_details_626140]: http://blog.csdn.net/byxdaz/article/details/626140