学步园

2012-10-11

能用，速度很慢，仅供参考。

基本原理用一句话概括就是，“对共线的各点而言，从图像左上角到此直线的距离相等。”

//------------------------------------------------
//2012-10-11 blueblood7 初创。
//------------------------------------------------

const float PI = 3.141593;
const float PI_HALF = PI / 2;

#define CAST_0_255(x) ((x) < 0 ? 0 : ((x) > 255 ? 255 : (x)))
//使用 Sobel 算子。参考http://zh.wikipedia.org/wiki/Sobel算子
void EdgeDetect(const BYTE* pbyImageData, int nWidth, int nHeight, BYTE* pbyResult)
{
	const int SOBEL_KERNEL_HOR[] = {-1,0,1,-2,0,2,-1,0,1};
	const int SOBEL_KERNEL_VER[] = {-1,-2,-1,0,0,0,1,2,1};

	const int SOBEL_KERNEL_WIDTH = 3;
	const int SOBEL_KERNEL_HEIGHT = 3;

	const int SOBEL_KERNEL_WIDTH_HALF = SOBEL_KERNEL_WIDTH >> 1;
	const int SOBEL_KERNEL_HEIGHT_HALF = SOBEL_KERNEL_HEIGHT >> 1;

	int nImageSize = nWidth * nHeight;
	int i,j;
	for (i=0; i<nHeight; i++)
		for (j=0; j<nWidth; j++)
		{
			int k,l, nSumHor = 0, nSumVer = 0, nKernelIdx = 0;
			for (k=0; k<SOBEL_KERNEL_HEIGHT; k++)
				for (l=0; l<SOBEL_KERNEL_WIDTH; l++, nKernelIdx++)
				{
					int x = j + (SOBEL_KERNEL_WIDTH_HALF - l);
					int y = i + (SOBEL_KERNEL_HEIGHT_HALF - k);
					
					if (x < 0)
						x = 0;
					else if (x >= nWidth)
						x = nWidth - 1;
					
					if (y < 0)
						y = 0;
					else if (y >= nHeight)
						y = nHeight - 1;

					int nImageIdx = y * nWidth + x;
					nSumHor += (SOBEL_KERNEL_HOR[nKernelIdx] * pbyImageData[nImageIdx]);
					nSumVer += (SOBEL_KERNEL_VER[nKernelIdx] * pbyImageData[nImageIdx]);
				}
			
			int nEdgeVal = int(sqrt(float(nSumHor * nSumHor + nSumVer * nSumVer)));
			pbyResult[i*nWidth + j] = CAST_0_255(nEdgeVal);
		}
}

//参考http://zh.wikipedia.org/zh-cn/大津算法
int Ostu(BYTE* pbyImageData, int nImageSize)
{
	int* pnForegroundCount = new int[256];
	int* pnBackgroundCount = new int[256];
	int* pnForegroundSum = new int[256];
	int* pnBackgroundSum = new int[256];
	memset(pnForegroundCount, 0, 256 * sizeof(int));
	memset(pnBackgroundCount, 0, 256 * sizeof(int));
	memset(pnForegroundSum, 0, 256 * sizeof(int));
	memset(pnBackgroundSum, 0, 256 * sizeof(int));
	
	int i;
	for (i=0; i<nImageSize; i++)
	{
		int nVal = pbyImageData[i];
		int j;
		//j是阈值
		//灰度值大于等于阈值时，该像素被作为前景。
		for (j=0; j<=nVal; j++)
		{
			pnForegroundCount[j] ++;
			pnForegroundSum[j] += nVal;
		}
		
		//灰度值小于阈值时，该像素被作为背景。
		for (; j<256; j++)
		{
			pnBackgroundCount[j] ++;
			pnBackgroundSum[j] += nVal;
		}
	}

	float fGMax = -1.0f;
	int nThreshold = -1;
	for (i=0; i<256; i++)
	{
		float fForegroundRate = pnForegroundCount[i] / (float)nImageSize;
		float fBackgroundRate = pnBackgroundCount[i] / (float)nImageSize;
		float fForegroundMean = pnForegroundSum[i] / (float)pnForegroundCount[i];
		float fBackgroundMean = pnBackgroundSum[i] / (float)pnBackgroundCount[i];
		float fG = fForegroundRate * fBackgroundRate * (fForegroundMean - fBackgroundMean) * (fForegroundMean - fBackgroundMean);
		if (fG > fGMax)
		{
			fGMax = fG;
			nThreshold = i;
		}
	}

	delete[] pnForegroundCount;
	delete[] pnBackgroundCount;
	delete[] pnForegroundSum;
	delete[] pnBackgroundSum;

	return nThreshold;
}

void ImageThresholding(BYTE* pbyImageData, int nImageSize, int nThreshold)
{
	int i;
	for (i=0; i<nImageSize; i++)
	{
		if (pbyImageData[i] >= nThreshold)
			pbyImageData[i] = 255;
		else
			pbyImageData[i] = 0;
	}
}

#define IS_ZERO(x)	(((x) < 0.000001 && (x) > -0.000001) ? TRUE : FALSE)
#define IS_IN_DIFF_RANGE(x)	(((x) < 1.000001f && (x) > -1.000001f) ? TRUE : FALSE)

//对给定的一组数据M，按值，把相同的分成一组，共N组，N<=M。
//pnElementCountPerGroup、pnElementPermutation、pfGroupVal 由调用者分配内存，大小是 nValCount。
//比如输入数据 pfVal = {0.12, 0.08, 0.12, 0.15, 0.7, 0.08, 0.12, 0.7, 0.08}， nValCount = 9。
//输出是	nGroupCount = 4。
//			pnElementCountPerGroup = {3, 3, 1, 2}。
//			pnElementPermutation = {0, 2, 6, 1, 5, 8, 3, 4, 7}。
//			pfGroupVal = {0.12, 0.08, 0.15, 0.7}。
void CalcGroup(float* pfVal, int nValCount, int& nGroupCount, int* pnElementCountPerGroup, int* pnElementPermutation, float* pfGroupVal)
{
	nGroupCount = 0;
	memset(pnElementCountPerGroup, 0, nValCount * sizeof(int));
	memset(pfGroupVal, 0, nValCount * sizeof(float));
	
	BOOL* pProcessed = new BOOL[nValCount];
	int i;
	for (i=0; i<nValCount; i++)
		pProcessed[i] = FALSE;

	int nGroupIdx = 0;
	int nPermutationIdx = 0;
	for (i=0; i<nValCount; i++)
	{
		if (pProcessed[i])
			continue;

		float fCurVal = pfVal[i];
		pnElementCountPerGroup[nGroupIdx] ++;
		pProcessed[i] = TRUE;

		pnElementPermutation[nPermutationIdx] = i;
		nPermutationIdx ++;

		int j;
		for (j=i+1; j<nValCount; j++)
		{
			if (pProcessed[j])
				continue;

			//属于同一组。
			if (IS_IN_DIFF_RANGE(pfVal[j] - fCurVal))
			{				
				pnElementCountPerGroup[nGroupIdx] ++;

				pnElementPermutation[nPermutationIdx] = j;
				nPermutationIdx ++;
				
				pProcessed[j] = TRUE;
			}
		}

		pfGroupVal[nGroupIdx] = fCurVal;
		nGroupIdx ++;
	}

	delete[] pProcessed;

	nGroupCount = nGroupIdx;
	
	return;
}

//两个点相互在8领域内。
BOOL IsNeighbor(POINT& ptA, POINT& ptB)
{
	int nOffsetX = ptA.x - ptB.x;
	int nOffsetY = ptA.y - ptB.y;

	if (nOffsetX >= -1 && nOffsetX <= 1 && nOffsetY >= -1 && nOffsetY <= 1)
		return TRUE;
	else
		return FALSE;
}

#define MID_CAST(x)		((x) < 0 ? (int((x) - 0.5f)) : (int((x) + 0.5f)))

//给定一条直线上的数据点，判断共存在多少线段。
//输入	ptLine - 直线上的点坐标集合。
//		nLinePointCount - 直线上的点数量。
//		fLineAngle - 直线和水平方向的夹角。
//输出	nLineSegmentCount - 线段数量。
//		pnLineSegmentLen - 每条线段的长度。
//		pnLineSegmentLen 的内存由调用者分配，大小是 nLinePointCount。
void FindLineSegment(POINT ptLine[], int nLinePointCount, float fLineAngle, int& nLineSegmentCount, int* pnLineSegmentLen)
{
	nLineSegmentCount = 0;
	memset(pnLineSegmentLen, 0, nLinePointCount*sizeof(int));

	float fAngleTan = tan(fLineAngle);
	
	int i, nLineSegmentLen = 0;
	for (i=0; i<nLinePointCount-1; i++)
	{
		POINT ptCur;
		ptCur.x = ptLine[i].x;
		ptCur.y = ptLine[i].y;
		nLineSegmentLen ++;

		if (IsNeighbor(ptCur, ptLine[i+1]))
			continue;

		//计算直线上和当前点相邻的点。一共有两个相邻点，但由于 ptLine 中的数据的Y坐标递增的，所以只要求一个Y坐标非减的相邻点即可。
		POINT ptNext;
		if (IS_ZERO(fLineAngle - 0))
		{
			ptNext.x = ptCur.x + 1;
			ptNext.y = ptCur.y;
		}
		else if (IS_ZERO(fLineAngle - PI / 2))
		{
			ptNext.x = ptCur.x;
			ptNext.y = ptCur.y + 1;
		}
		else
		{		
			if (fAngleTan < 1 && fAngleTan > -1)
			{
				float fNextX = ptCur.x - 1 / fAngleTan;
				ptNext.x = MID_CAST(fNextX);
				ptNext.y = ptCur.y + 1;
			}
			else
			{
				ptNext.x = ptCur.x - 1;
				float fNextY = ptCur.y + fAngleTan;
				ptNext.y = MID_CAST(fNextY);
			}
		}

		//直线断开。
		if (ptNext.x != ptLine[i+1].x || ptNext.y != ptLine[i+1].y)
		{
			pnLineSegmentLen[nLineSegmentCount] = nLineSegmentLen;
			nLineSegmentLen = 0;
			nLineSegmentCount ++;
		}
	}

	//最后一个点要算在最后一个线段中。
	nLineSegmentLen ++;
	pnLineSegmentLen[nLineSegmentCount] = nLineSegmentLen;
	nLineSegmentCount ++;

	return;
}

typedef vector<POINT*> VEC_LINE;

void FindLines(const BYTE* pbyBinaryImageData, int nWidth, int nHeight, 
			   int nAngleCount, float arrfAngle[], int nMinPointCountPerLine,
			   int& nLineCount, VEC_LINE* pVecLine, float* pfLineAngle)
{
	int nImageSize = nWidth * nHeight;

	int nForegroundCount = 0;
	int i;
	for (i=0; i<nImageSize; i++)
	{
		if (!pbyBinaryImageData[i])
			continue;
		
		nForegroundCount ++;
	}
	
	//过 (x, y) 点，与水平方向夹角是 alpha 的直线方程是 
	//Y = tan(alpha) * (X - x) + y 。
	//可以化成 sin(alpha) * X - cos(alpha) * Y + (cos(alpha) * y - sin(alpha) * x) = 0 。
	//原点(0, 0) 到上述直线的距离是 fabs(cos(alpha) * y - sin(alpha) * x) 。
	//原点(0, 0) 到上述直线的垂线向量是 (cos(alpha) * y - sin(alpha) * x) 。
		
	float* pfAngleCos = new float[nAngleCount];
	float* pfAngleSin = new float[nAngleCount];
	for (i=0; i<nAngleCount; i++)
	{
		pfAngleCos[i] = cos(arrfAngle[i]);
		pfAngleSin[i] = sin(arrfAngle[i]);
	}

	//共存在 nAngleCount 个角度，每个角度的直线最多包含的点数是 nForegroundCount。
	//同角度的直线可能相互平行，但它们所含像素点的和应小于 nForegroundCount。
	//创建一个二维数组，保存原点到所有可能直线的距离。
	float** ppfRou = new float*[nAngleCount];
	int** ppnCoorX = new int*[nAngleCount];
	int** ppnCoorY = new int*[nAngleCount];
	for (i=0; i<nAngleCount; i++)
	{
		ppfRou[i] = new float[nForegroundCount];
		ppnCoorX[i] = new int[nForegroundCount];
		ppnCoorY[i] = new int[nForegroundCount];
	}
	
	int x, y, nImageIdx = 0, nForegroundIdx = 0;

	for (i=0; i<nAngleCount; i++)
	{
		float fCurAngle = arrfAngle[i];
		//对锐角从右往左扫描，否则从左往右扫描。
		if (fCurAngle < PI_HALF)
		{
			nForegroundIdx = 0;
			for (y=0; y<nHeight; y++)
				for (x=nWidth-1; x>=0; x--)
				{
					nImageIdx = y*nWidth + x;
					if (!pbyBinaryImageData[nImageIdx])
						continue;
					
					// 这里用向量，不用距离，位于原点的两侧等距处的直线应该算两条。
					// 这里 y 取负值，因为普通的直角坐标系 y 从上到下是递减的。
					//ppfRou[i][nForegroundIdx] = (pfAngleCos[i] * (-y) - pfAngleSin[i] * x);
					
					// 这里做个取整处理，降低对连续性的判断难度。 
					ppfRou[i][nForegroundIdx] = MID_CAST(pfAngleCos[i] * (-y) - pfAngleSin[i] * x);
					ppnCoorX[i][nForegroundIdx] = x;
					ppnCoorY[i][nForegroundIdx] = y;

					nForegroundIdx ++;
				}
		}
		else
		{
			nImageIdx = 0, nForegroundIdx = 0;
			for (y=0; y<nHeight; y++)
				for (x=0; x<nWidth; x++, nImageIdx++)
				{
					if (!pbyBinaryImageData[nImageIdx])
						continue;

					ppfRou[i][nForegroundIdx] = MID_CAST(pfAngleCos[i] * (-y) - pfAngleSin[i] * x);
					ppnCoorX[i][nForegroundIdx] = x;
					ppnCoorY[i][nForegroundIdx] = y;

					nForegroundIdx ++;
				}
		}
	}

	nLineCount = 0;

	int nGroupCount;
	int* pnElementCountPerGroup = new int[nForegroundCount];
	int* pnElementPermutation = new int[nForegroundCount];
	float* pfGroupVal = new float[nForegroundCount];
	for (i=0; i<nAngleCount; i++)
	{
		CalcGroup(ppfRou[i], nForegroundCount, nGroupCount, pnElementCountPerGroup, pnElementPermutation, pfGroupVal);

		float fCurLineAngle = arrfAngle[i];
		int j, nPermutationPos = 0;
		for (j=0; j<nGroupCount; j++)
		{
			int nLinePointCount = pnElementCountPerGroup[j];

			if (nLinePointCount >= nMinPointCountPerLine)
			{
				//找到了一条角度为 arrfAngle[i] 的直线。
				
				//找出这条直线中的线段数。

				//取出这条直线上所有点的坐标。
				POINT* ptLine = new POINT[nLinePointCount];
				
				int k;
				for (k=0; k<nLinePointCount; k++)
				{
					int nCoorIdx = pnElementPermutation[nPermutationPos];
					ptLine[k].x = ppnCoorX[i][nCoorIdx];
					ptLine[k].y = ppnCoorY[i][nCoorIdx];
					nPermutationPos++;
				}

				int nLineSegmentCount;
				int* pnLineSegmentLen = new int[nLinePointCount];
				FindLineSegment(ptLine, nLinePointCount, fCurLineAngle, nLineSegmentCount, pnLineSegmentLen);

				int nLineSegmentPos = 0;
				for (k=0; k<nLineSegmentCount; k++)
				{
					int nLineSegmentLen = pnLineSegmentLen[k];
					if (nLineSegmentLen >= nMinPointCountPerLine)
					{
						int l;
						for (l=0; l<nLineSegmentLen; l++, nLineSegmentPos++)
						{
							POINT* pt = new POINT;
							pt->x = ptLine[nLineSegmentPos].x;
							pt->y = ptLine[nLineSegmentPos].y;
							pVecLine[nLineCount].push_back(pt);
						}

						pfLineAngle[nLineCount] = fCurLineAngle;
						nLineCount ++;
					}
					else
						nLineSegmentPos += nLineSegmentLen;
				}

				delete[] ptLine;
				delete[] pnLineSegmentLen;
			}
			else
				nPermutationPos += nLinePointCount;
		}
	}
	
	delete[] pfAngleCos;
	delete[] pfAngleSin;

	for (i=0; i<nAngleCount; i++)
	{
		delete[] ppfRou[i];
		delete[] ppnCoorX[i];
		delete[] ppnCoorY[i];
	}
	delete[] ppfRou;
	delete[] ppnCoorX;
	delete[] ppnCoorY;

	delete[] pnElementCountPerGroup;
	delete[] pnElementPermutation;
	delete[] pfGroupVal;
	
	return;
}

struct stLineInfo
{
	int nNo;
	int nLineLen;
};

void CopyLines(VEC_LINE* pvecDst, const VEC_LINE* pvecSrc, int nLineCount)
{
	int i;
	for (i=0; i<nLineCount; i++)
	{
		int nSize = pvecSrc[i].size();
		int j;
		for (j=0; j<nSize; j++)
		{
			POINT* pt = new POINT;
			pt->x = pvecSrc[i][j]->x;
			pt->y = pvecSrc[i][j]->y;
			pvecDst[i].push_back(pt);
		}
	}

	return;
}

void EmptyLines(VEC_LINE* pvecLines, int nLineCount)
{
	int i;
	for (i=0; i<nLineCount; i++)
	{
		int nSize = pvecLines[i].size();
		int j;
		for (j=0; j<nSize; j++)
			delete pvecLines[i][j];
		pvecLines[i].clear();
	}

	return;
}

bool CompareLineLen(const stLineInfo& a, const stLineInfo& b)
{
	return a.nLineLen > b.nLineLen;
}

//输入	nWidth / nHeight - 图像宽 / 高。
//		nLineCount - 所有直线数量。
//		pVecLine - 所有直线中的点坐标。
//		pfLineAngle - 所有直线和水平方向的夹角。
//输出	nLineCount - 去除重叠直线后剩余的数量。
//		pVecLine - 剩余直线中的点坐标。
//		pfLineAngle - 剩余直线和水平方向的夹角。
void RemoveOverlapLines(int nWidth, int nHeight, int& nLineCount, VEC_LINE* pVecLine, float* pfLineAngle)
{
	int nImageSize = nWidth * nHeight;
	int nOldLineCount = nLineCount;
	nLineCount = 0;

	//先把直线信息复制一份出来，再把输入的直线数组清空。
	VEC_LINE* _pVecLine = new VEC_LINE[nOldLineCount];
	CopyLines(_pVecLine, pVecLine, nOldLineCount);
	EmptyLines(pVecLine, nOldLineCount);

	float* _pfLineAngle = new float[nOldLineCount];
	memcpy(_pfLineAngle, pfLineAngle, nOldLineCount * sizeof(float));

	//把直线按长度排序。
	stLineInfo* pLineInfo = new stLineInfo[nOldLineCount];
	int i;
	for (i=0; i<nOldLineCount; i++)
	{
		int nLinePointCount = _pVecLine[i].size();
		pLineInfo[i].nNo = i;
		pLineInfo[i].nLineLen = nLinePointCount;
	}
	
	stable_sort(pLineInfo, pLineInfo+nOldLineCount, CompareLineLen);

	//做一个状态表。初始值都是 FALSE，有线经过的点的状态置成 TRUE。
	BOOL* pbState = new BOOL[nImageSize];
	for (i=0; i<nImageSize; i++)
		pbState[i] = FALSE;

	//先从最长的线开始。
	for (i=0; i<nOldLineCount; i++)
	{
		int nNo = pLineInfo[i].nNo;
		int nLinePointCount = pLineInfo[i].nLineLen;

		int nOverlapPointCount = 0;	//表示直线中有多少点被其他直线覆盖，如果完全被覆盖，则去除这条直线。
		int j;
		for (j=0; j<nLinePointCount; j++)
		{
			int x = _pVecLine[nNo][j]->x;
			int y = _pVecLine[nNo][j]->y;
			int nImageIdx = y * nWidth + x;

			//这个点被其他直线覆盖了。
			if (pbState[nImageIdx])
				nOverlapPointCount ++;
			else
				pbState[nImageIdx] = TRUE;
		}

		//没有被完全覆盖，保留直线。
		if (nOverlapPointCount < nLinePointCount)
		{
			CopyLines(&pVecLine[nLineCount], &_pVecLine[nNo], 1);
			pfLineAngle[nLineCount] = _pfLineAngle[nNo];
			nLineCount++;
		}
	}

	EmptyLines(_pVecLine, nOldLineCount);
	delete[] _pVecLine;

	delete[] _pfLineAngle;
	delete[] pLineInfo;
	delete[] pbState;
	return;
}

//输入	pbyImageData / nWidth / nHeight - 灰度图像数据 / 图像宽 / 图像高。
//		nAngleCount - 要检测直线角度的数量。
//		arrfAngle - 每个角度的弧度值。
//		nMinPointCountPerLine - 每条直线最少包含的像素点数量。
//		
//输出	nLineCount - 找到的直线数量。
//		pVecLine - 保存每条直线中所有点的(x,y)坐标。
//		pfLineAngle - 保存每条直线和水平方向的夹角。
//		bBinaryImage - pbyImageData 中的图像是否二值化图。
//		pbyBinaryImage - 保存中间结果的二值图。
//		pVecLine 和 pfLineAngle 的内存由调用者分配，大小是 图像大小 × 所有角度。

void HoughTrans(const BYTE* pbyImageData, int nWidth, int nHeight, 
				int nAngleCount, float arrfAngle[],
				int nMinPointCountPerLine,
				int& nLineCount, VEC_LINE* pVecLine, float* pfLineAngle,
				BOOL bBinaryImage = FALSE,
				BYTE* pbyBinaryImage = NULL)
{
	int nImageSize = nWidth * nHeight;
	BYTE* _pbyBinaryImage = new BYTE[nImageSize];

	if (bBinaryImage)
		memcpy(_pbyBinaryImage, pbyImageData, nImageSize);
	else
	{
		//做边缘检测。
		EdgeDetect(pbyImageData, nWidth, nHeight, _pbyBinaryImage);

		//二值化。
		//	a、求二值化阈值。
		int nThreshold = Ostu(_pbyBinaryImage, nImageSize);
		
		//	b、二值化。
		ImageThresholding(_pbyBinaryImage, nImageSize, nThreshold);
	}

	if (pbyBinaryImage)
		memcpy(pbyBinaryImage, _pbyBinaryImage, nImageSize);

	//确定直线。
	FindLines(_pbyBinaryImage, nWidth, nHeight, nAngleCount, arrfAngle, nMinPointCountPerLine, nLineCount, pVecLine, pfLineAngle);

	//去除相互重叠的直线。
	if (nLineCount > 1)
		RemoveOverlapLines(nWidth, nHeight, nLineCount, pVecLine, pfLineAngle);
	
	delete[] _pbyBinaryImage;

	return;
}

2011-05-27

在我以往的概念里，Hough变换就是“利用直角坐标系中一条线对应极坐标系中一个点的原理，通过点来找线。”，但要动手编程时，问题就来了，把(x,y)换算成(ρ,θ)，是一一对应的，那么一条线上每个点的坐标不同，对应的(ρ,θ)也不同，怎么会对应到一个点上？

昨天看了维基百科中的解释（顺便说一句，我总是先看中文版的，但遗憾的是有的词条没有中文版，有的中文版相当简单，没办法还是要看E文的。），看着看着就不太懂了。今天早上从地铁站出来，一路走一路想，居然想通了，很开心。

道理其实很简单，就是把图像左上角看成原点，对图像中的每个点(x,y)，设通过这个点有N条直线（如果需要检测直线的角度越多，N值就越大，速度就越慢。），原点到这N条直线都有一个距离ρi和夹角θi(i∈[1,N])（需要注意的是这里的(ρ,θ)表示的是从原点到直线的距离和该垂线和x轴的夹角，而不是原点到(x,y)点的距离和夹角。），如图1所示，

图1：N=3的情况，3条直线的角度分别是20°、65°、110°，(x,y)对应的参数集是(ρ1,2π-θ1)、(ρ2,2π-θ2)、(ρ3,θ3)。

那么这个点就对应N个(ρ,θ)值，把每个值看成一个盒子的标签，盒子里有个计数器（初值为0），计数器加1。假设有M点共线，它们就会有一个相同的(ρ,θ)值，对应盒子中计数器的值就为M。把图像中所有点遍历以后，统计每个盒子中的计数器，从大到小排序并设个阈值，就知道图像中有几条线了，根据盒子的标签(ρ,θ)值，就能算出直线方程了，如果要找出该直线在图像中对应的点，只需把点的直角坐标也投入盒子即可。

问题又来了，整个过程貌似和图像内容无关啊，那白纸也能检出直线了，怎么可能呢？再看维基百科，终于清楚了，原来不是遍历图像中的所有点，而是边缘点。从编程角度，就是先做边缘检测，再二值化，再做直线检测即可。盒子的最大数量就是“边缘点数目*N”。