www.pudn.com > Hough.rar > HoughTransform.cpp


#include "StdAfx.h"
#include "HoughTransform.h"

/***************************************************************************************
* 函数名: HoughTransform
* 参数： ptr --- 指向图像像素的指针
* width --- 图像的宽
* height --- 图像的高
* threshod --- 计数值的门限
* pPos --- 检测出的圆心在数组ptr[]中的位置
* 功能： Hough变换检测圆。
* 说明： 1、Hough变换的原理是：把平面上点共圆的问题，转化为
* 参数平面上圆共点的问题
* 2、因为圆是圆环的特例(圆是宽度为1的圆环)，故而作为
* 检测圆的hough变换通常检测的是一个有一定宽度
* (本函数中宽度为3)的圆环。
* 3、此Hough变换针对的是二值图像。
* 4、此函数是根据计数值的门限来检测圆，
* 即检测出所有计数值超过门限的点作为检测到的圆心点。
* 5、不能检测出圆心靠近图像边界的圆(即不能检测出有一部分在图像边界外部的圆)
****************************************************************************************/
void HoughTransform(unsigned char* ptr, int width, int height, int threshold,
int*&amt; pPos, int&amt; detectedPointsCount)
{
int* pCount; // 计数数组，图象上的每一个像素点对应一个计数值，用来确定该点是否是某个圆的圆心。
int* ixCor; // X坐标数组，其中的元素是圆环上点的X坐标。
int* iyCor; // Y坐标数组，其中的元素是圆环上点的Y坐标。
int* ixCalCor;
int* iyCalCor;
int iPointNum;
int ixBegin, iyBegin;
int iMinRadius;
int iMaxRadius;
int iRadius;
int i, j;
int n;
// int BmpHeight, BmpWidth;
int iNumOfCircle;

// BmpHeight = height;
// BmpWidth = ( ( width + 3 ) / 4 ) * 4; // 为了符合Bmp格式的规定
iPointNum = (int)( 8.0 * 3.14 * 30 * 1.5 ); // 圆环上点的个数? 2*PI*16 + 2*PI*15 + 2*PI*14 =2*3.14*45 = 282 ，每个点占4个字节，共 8*3.14*45 = 1128个字节
// 等价于 pCount = new int[height*width];
pCount = (int*)malloc(height*width*sizeof(int)); // 图像上的每一个像素对应一个计数值。pCount指针指向存放图像中各个像素点的计数值的内存块
for ( i = 0; i < height*width; i++ )
{
pCount[i] = 0; // 各个像素点的初始计数都设为0
}
ixCor = (int*)malloc( iPointNum * sizeof(int) );
iyCor = (int*)malloc( iPointNum * sizeof(int) ); // ixCor指针和iyCor指针指向 存放圆环上像素点的坐标 的内存块
ixCalCor = (int*)malloc( iPointNum * sizeof(int) );
iyCalCor = (int*)malloc( iPointNum * sizeof(int) ); // ixCalCor指针和iyCalCor指针指向 存放图像中其他同样大小的圆环上像素点的坐标 的内存块
for ( i = 0; i < iPointNum; i++ )
{
ixCor[i] = 0;
iyCor[i] = 0;
ixCalCor[i] = 0;
iyCalCor[i] = 0; // 坐标全部初始化为0
}
iMinRadius = 14; // 要检测的圆环的内半径
iMaxRadius = 16; // 要检测的圆环的外半径 ，即圆环的检测宽度为3，像素在这个圆环内，都视作圆上的点。
//ixBegin = 16; // 初始圆心的X坐标
//iyBegin = 16; // 初始圆心的Y坐标
ixBegin = iMaxRadius; // 初始圆心的X坐标
iyBegin = iMaxRadius; // 初始圆心的X坐标

// 功能：检测初始圆环。
// 具体说明：把以(ixBegin, iyBegin)为圆心，宽度为3，外半径为iMaxRadius，
// 内半径为iMinRadius的圆环上的元素的x，y坐标放到数组ixCor和iyCor中。
iNumOfCircle = 0; // 圆环上的象素点个数初始为0
for ( iRadius = iMinRadius; iRadius <= iMaxRadius; iRadius++ ) // iRadius为圆的半径
{
for ( i = iyBegin - iRadius; i <= iyBegin + iRadius; i++ ) // i 为 圆内像素点的X坐标
{
for ( j = ixBegin - iRadius; j <= ixBegin + iRadius; j++ ) // j 为 圆内像素点的Y坐标
{
// 若(i,j)在以(ixBegin, iyBegin)为圆心, 以iRadius为半径的圆环上
if ( abs( (j-ixBegin)*(j-ixBegin) + (i-iyBegin)*(i-iyBegin) - iRadius*iRadius ) < 15 ) // 圆的方程：(X-X0)*(X-X0) + (Y-Y0)*(Y-Y0) = R*R
{
iyCor[iNumOfCircle] = i;
ixCor[iNumOfCircle] = j; // 把圆环上点的x、y坐标分别放到数组iyCor和ixCor中
iNumOfCircle++; // 圆环上像素点的个数，也是圆环上的当前点在数组iyCor和ixCor中的序号
}
}
}
}

// 功能：检测整个图像范围内同样大小的圆环。不检测圆心在靠近图像边界附近的圆。
// 具体说明：在整个图像范围内平移圆环，同时检测圆环上像素值为255的象素点，
// 每检测到一个这样的点，则将该圆的圆心点对应的计数器值加1。
// (j, i)是圆心坐标
for ( i = iMaxRadius; i < height - iMaxRadius; i++ ) // 圆心位置的y坐标变动范围
{
for ( j = iMaxRadius; j < width - iMaxRadius; j++ ) // 圆心位置的x坐标变动范围
{
for ( n = 0; n < iNumOfCircle; n++ ) // 对于初始圆环上的每个点，在图像上进行平移，平移距离从1个像素开始，逐步递增
{
iyCalCor[n] = iyCor[n] + ( i - iMaxRadius ); // 平移后的圆环上的点的X坐标
ixCalCor[n] = ixCor[n] + ( j - iMaxRadius ); // 平移后的圆环上的点的X坐标
}

for ( n = 0; n < iNumOfCircle; n++ ) // 对圆环上的点进行操作
{
// 在把图像从文件读到内存中时，已经把每行末尾可能添加的0跳过了。
// if ( ptr[iyCalCor[n]*BmpWidth+ixCalCor[n]] == 255 ) // 如果圆环上的某个点值为255
if ( ptr[iyCalCor[n]*width + ixCalCor[n]] == 255) // 如果圆环上的某个点值为255
{
pCount[i*width+j]++; // 则此圆环的圆心(j,i)对应的计数值应该增加1。
// 此计数值表示以(j,i)为圆心，以14~16为半径的圆上落有多少个白点
// 计数值越高表示，这个圆环上落的白点越多，表明这些白点组成的图形越象一个圆。
}
}
}
}

int nfoundPointNum = 0;
for(i=0; i<height*width; i++)
{
if(pCount[i] > threshold)
{
nfoundPointNum++;
}
}
pPos = new int[nfoundPointNum];
j = 0;
for(i=0; i<height*width; i++)
{
if(pCount[i] > threshold)
{
pPos[j] = i;
j++;
}
}
detectedPointsCount = nfoundPointNum;

free(pCount);
free(ixCor);
free(iyCor);
free(ixCalCor);
free(iyCalCor);
}

/**********************************************************************************
* 函数名: HoughTransform
* 输入参数： ptr --- 指向图像像素的指针
* width --- 图像的宽
* height --- 图像的高
* circleNum --- 要求检测圆的个数
* nMaxRadius --- 要求检测圆环的外半径
* edgeThick --- 要求检测圆环的宽
* nDistanceBetweenCenters --- 检测的圆环的圆心之间要求保持的最小距离
* 输出参数：
* pCircPos --- 检测出的圆心在数组ptr[]中的位置
* 返回值：
* 无
* 功能：
* Hough变换检测圆。
* 说明： 1、Hough变换的原理是：把平面上点共圆的问题，转化为
* 参数平面上圆共点的问题
* 2、因为圆是圆环的特例(圆是宽度为1的圆环)，故而作为
* 检测圆的hough变换通常检测的是一个有一定宽度
* (本函数中宽度为3)的圆环。
* 3、此Hough变换针对的是二值图像。
* 4、此函数是根据要求检测出的圆的个数circleNum来检测圆，
* 即检测出所有计数值最大的的circleNum个点作为检测到的圆心点。
* 5、可以检测出圆心靠近图像边界的圆(即圆有一部分在图像边界外部的圆)
*************************************************************************************/
void HoughTransform(unsigned char* ptr, int width, int height, int circleNum,
int nMaxRadius, int edgeThick, int nDistanceBetweenCenters, int*&amt; pCircPos)
{
int* pCount; // 计数数组，图象上的每一个像素点对应一个计数值，用来确定该点是否是某个圆的圆心。
int* ixCor; // X坐标数组，其中的元素是圆环上点的X坐标。
int* iyCor; // Y坐标数组，其中的元素是圆环上点的Y坐标。
int* ixCalCor; // X坐标数组，其中的元素是平移后圆环上点的X坐标。
int* iyCalCor; // Y坐标数组，其中的元素是平移后圆环上点的Y坐标。
int iPointNum;
int ixBegin, iyBegin;
int iMinRadius;
int iMaxRadius;
int iRadius;
int i, j;
int n;
// int BmpHeight, BmpWidth;
int iNumOfCircle;

// 在把图像从文件读到内存中时，已经把图像文件中每行末尾可能添加的0跳过了。因此下面的两条语句不需要了, 在程序中BmpWidth可以用width代替
// BmpHeight = height;
// BmpWidth = ( ( width + 3 ) / 4 ) * 4; // 为了符合Bmp格式的规定

// 圆环上的点的个数iPointNum为：2*PI*(Radius1+ Radius2 + ...+ nMaxRadius), * 4 是为了使iPointNum值足够大，避免数组iyCor和ixCor指针越界。
iPointNum = int(PI*(nMaxRadius + (nMaxRadius - edgeThick +1)) * edgeThick) * 4;
// 下面此条语句等价于： pCount = new int[height*width];
pCount = (int*)malloc(height*width*sizeof(int)); // 图像上的每一个像素对应一个计数值。pCount指针指向存放图像中各个像素点的计数值的内存块
for ( i = 0; i < height*width; i++ )
{
pCount[i] = 0; // 各个像素点的初始计数值都设为0
}
ixCor = (int*)malloc( iPointNum * sizeof(int) );
iyCor = (int*)malloc( iPointNum * sizeof(int) ); // ixCor指针和iyCor指针指向 存放圆环上像素点的坐标 的内存块
ixCalCor = (int*)malloc( iPointNum * sizeof(int) );
iyCalCor = (int*)malloc( iPointNum * sizeof(int) ); // ixCalCor指针和iyCalCor指针指向 存放图像中其他同样大小的圆环上像素点的坐标 的内存块
for ( i = 0; i < iPointNum; i++ )
{
ixCor[i] = 0;
iyCor[i] = 0;
ixCalCor[i] = 0;
iyCalCor[i] = 0; // 坐标全部初始化为0
}
iMinRadius = (nMaxRadius - edgeThick + 1); // 要检测的圆环的内半径
iMaxRadius = nMaxRadius; // 要检测的圆环的外半径 ，即圆环的检测宽度为edgeThick，像素在这个圆环内，都视作圆上的点。
ixBegin = iMaxRadius; // 初始圆心的X坐标
iyBegin = iMaxRadius; // 初始圆心的X坐标

// 功能：检测初始圆环。
// 具体说明：把以(ixBegin, iyBegin)为圆心，宽度为edgeThick，外半径为iMaxRadius，
// 内半径为iMinRadius的圆环上的元素的x，y坐标放到数组ixCor和iyCor中。
iNumOfCircle = 0; // 圆环上的象素点个数初始为0
for ( iRadius = iMinRadius; iRadius <= iMaxRadius; iRadius++ ) // iRadius为圆的半径
{
for ( i = iyBegin - iRadius; i <= iyBegin + iRadius; i++ ) // i 为 圆上像素点的Y坐标
{
for ( j = ixBegin - iRadius; j <= ixBegin + iRadius; j++ ) // j 为 圆上像素点的X坐标
{
ASSERT((i>=0)&amt;&amt;(j>=0));
// 若(i,j)在以(ixBegin, iyBegin)为圆心, 以iRadius为半径的圆环上
if ( abs( (j-ixBegin)*(j-ixBegin) + (i-iyBegin)*(i-iyBegin) - iRadius*iRadius ) < 15 ) // 圆的方程：(X-X0)*(X-X0) + (Y-Y0)*(Y-Y0) = R*R
{
iyCor[iNumOfCircle] = i;
ixCor[iNumOfCircle] = j; // 把圆环上点的x、y坐标分别放到数组iyCor和ixCor中
iNumOfCircle++; // 圆环上像素点的个数，也是圆环上的当前点在数组iyCor和ixCor中的序号
}
}
}
}

// 功能：检测整个图像范围内同样大小的圆环。
// 具体说明：在整个图像范围内平移圆环，同时检测圆环上像素值为255的象素点，
// 每检测到一个这样的点，则将该圆的圆心点对应的计数器值加1。
// (j, i)是圆心坐标
for ( i = 0; i < height; i++ ) // 圆心位置的y坐标变动范围。可以检测到圆心位置在图像边界附近的不完全的圆
{
for ( j = 0; j < width; j++ ) // 圆心位置的x坐标变动范围。可以检测到圆心位置在图像边界附近的不完全的圆
{
for ( n = 0; n < iNumOfCircle; n++ ) // 对于初始圆环上的每个点，在图像上进行平移，平移距离从1个像素开始，逐步递增
{
iyCalCor[n] = iyCor[n] + ( i - iMaxRadius ); // 平移后的圆环上的点的X坐标
ixCalCor[n] = ixCor[n] + ( j - iMaxRadius ); // 平移后的圆环上的点的X坐标
}

for ( n = 0; n < iNumOfCircle; n++ ) // 对圆环上的点进行操作
{
if ((iyCalCor[n] < 0)||(ixCalCor[n] < 0) ||(iyCalCor[n] >= height)||(ixCalCor[n] >= width)) // 若平移后圆上的某些点的坐标超出了图像的范围
{
continue; // 则跳过这些点
}

// 对于平移的圆环在图像内的部分
// if ( ptr[iyCalCor[n]*BmpWidth+ixCalCor[n]] == 255 ) // 如果圆环上的某个点值为255
if ( ptr[iyCalCor[n]*width + ixCalCor[n]] == 255) // 如果圆环上的某个点值为255
{
pCount[i*width+j]++; // 则此圆环的圆心(j,i)对应的计数值应该增加1。
// 此计数值表示以(j,i)为圆心，以14~16为半径的圆上落有多少个白点
// 计数值越高表示，这个圆环上落的白点越多，表明这些白点组成的图形越象一个圆。
}
}
}
}


CString info = "";
CString tmpInfo = "";
for ( i=0; i<circleNum; i++ )
{
// 找出计数值最大的circleNum个点(i,j), 则此(i,j)是检测到的circleNum个圆的圆心
int pos = FindMaxAndDeleteAreaForCircle( pCount, height, width, nMaxRadius, nDistanceBetweenCenters); // 返回值pos是该点(i,j)在一维数组中的位置 pos = j*width + i
pCircPos[i] = pos; // circleNum个圆心的坐标
tmpInfo.Format(">d,", pos);
info += tmpInfo;
}

free(pCount);
free(ixCor);
free(iyCor);
free(ixCalCor);
free(iyCalCor);
}

/*************************************************************************
*
* \函数名称：
* FindMax() - 用于寻找数据中的最大值
* \输入参数:
* int* data - 用于寻找最大值的数据
* int num - 数据个数
* int* maxdata - 最大值
* \返回值:
* int - 返回最大值在数据中的位置
* \Time: 2005\04\23
* \Author:
* Modify:
**************************************************************************/
int FindMaxAndDeleteAreaForCircle(int* TranData, int height, int width, int nMaxRadius, int nDistanceBetweenCenters)
{
int i, j;
int position;

int MaxData = 0;
position = 0;
for (i=0; i<height*width; i++)
{
if ( TranData[i] > MaxData )
{
MaxData = TranData[i];
position = i;
}
}

int TempHeight, TempWidth;
TempHeight = position / width;
TempWidth = position > width; // 检测出的点在图像上的坐标位置。

//防止越界
//int Boundary = int(nMaxRadius/2); //参与计算的数据的边界
int Boundary = nDistanceBetweenCenters;

for ( i=( (TempHeight-Boundary) < 0 ? 0 : (TempHeight-Boundary) ); i<( (TempHeight+Boundary) > height ? height : (TempHeight+Boundary) ); i++ )
{
for ( j=( (TempWidth-Boundary) < 0 ? 0 : (TempWidth-Boundary) ); j<( (TempWidth+Boundary) > width ? width : (TempWidth+Boundary) ); j++ )
{
TranData[i*width+j] = 0; // 以检测出的点为中心，以Boundary*2为边长的正方形内的点的计数值都置为0
}
}
return position;
}

// pImgData -- 输入/输出参数
void DetectCircle(unsigned char* pImgData, int imgDataCount, int height, int width,
int MaxRadius, int edgeThick, int* CenterPos, int CenterCount)
{
BOOL* pFlag = new BOOL[imgDataCount];
for(int k= 0; k<imgDataCount; k++)
{
pFlag[k] = FALSE; // 不是圆上的点
}

int iMinRadius = MaxRadius -edgeThick;
int iMaxRadius = MaxRadius;
int centerX, centerY;
// 对各个圆心对应的圆环上的点进行检测，看是否为255
for(int iCenterNum = 0; iCenterNum < CenterCount; iCenterNum++)
{
centerX = CenterPos[iCenterNum] > width;
centerY = CenterPos[iCenterNum] / width;
for (int iRadius = iMinRadius; iRadius <= iMaxRadius; iRadius++ ) // iRadius为圆的半径
{
for (int i = centerY - iRadius; i <= centerY + iRadius; i++ ) // i 为 圆内像素点的X坐标
{
if (i <0)
{
continue;
}
for (int j = centerX - iRadius; j <= centerX + iRadius; j++ ) // j 为 圆内像素点的Y坐标
{
if (j < 0)
{
continue;
}
// 若(i,j)在以(ixBegin, iyBegin)为圆心, 以iRadius为半径的圆环上
if ( abs( (j-centerX)*(j-centerX) + (i-centerY)*(i-centerY) - iRadius*iRadius ) < 15 ) // 圆的方程：(X-X0)*(X-X0) + (Y-Y0)*(Y-Y0) = R*R 。取15是因为sqrt(15)==4 而我们取的圆环的宽度为3。
{
if(pImgData[i*width + j] == 255)
{
pFlag[i*width + j] = TRUE;
}
}
}
}
}
}

for (int i = 0; i<imgDataCount; i++)
{
pImgData[i] = (pFlag[i]==FALSE)?0:255 ;
}

delete pFlag;
}



// void CreateCircle( unsigned char* ptr, int height, int width,
// int Radius, int MaxRadius, int* XPosInCircle, int* YPosInCircle)
// {
// int i; // 循环变量
// int MaxPixsInCircle; // 圆环中边缘最大象素的个数
// int XCenter, YCenter; // 模板的圆心坐标，为可识别的最大圆
//
// MaxPixsInCircle = 4 * MaxRadius; // 对于圆上每个 x , 在图象中对应2个y,并且x的最大范围为(-MaxRadius ~ +MaxRadius)
// // 故MaxPixsInCircle为4 * MaxRadius
// XCenter = MaxRadius;
// YCenter = MaxRadius;
//
// //初始化圆的边界
// for ( i = 0; i < MaxPixsInCircle; i++ )
// {
// XPosInCircle[i] = YPosInCircle[i] = 0;
// }
//
// //计算圆环的边界坐标
//
// for ( i = XCenter - Radius; i < XCenter + Radius; i++)
// {
// XPosInCircle[i] = i;
// YPosInCircle[i] = YCenter - (int) ( sqrt( Radius*Radius - ( XPosInCircle[i] - XCenter )*( XPosInCircle[i] - XCenter ) ) );
//
// XPosInCircle[i+2*MaxRadius] = i;
// YPosInCircle[i+2*MaxRadius] = YCenter + (int)( sqrt( Radius*Radius - ( XPosInCircle[i+2*MaxRadius] - XCenter )*( XPosInCircle[i+2*MaxRadius] - XCenter ) ) );
// }
// }
//
// void ComputeStatOfPixs( unsigned char* ptr, int height, int width, int radius, int MaxRadius,
// int* XPosInCircle, int* YPosInCircle, int* pStatOfPoint )
// {
//
// }
//
// void CheckAndVerifyPos( int height, int width, pCirclePoint MatchPoint )
// {
//
// }