1. 前言

今天要干什么？在一張圖片上通過傳統算法來檢測矩形。為了防止你無聊，先上一組對比圖片。

 

 

這個算法出自https://stackoverflow.com/questions/8667818/opencv-c-obj-c-detecting-a-sheet-of-paper-square-detection，接下來我們就從源碼角度來理解一下吧。

2. 算法原理

• 對原始圖像進行濾波。(關于濾波器的選擇可以選擇普通的中值濾波，也可以選擇Side Window Filter的中值濾波，這取決于你是否需要圖像保存更多的邊緣和角點)。
• 在圖像的每個顏色通道尋找矩形區域。這可以細分為：
• 在每個顏色通道對應的圖像中使用不同的閾值獲得對應的二值圖像。
• 獲得二值圖像后，使用      findContours算法尋找輪廓區域。
• 對于每個區域，使用      approxPolyDP算法來近似輪廓為多邊形。
• 對上面近似后的多邊形判斷頂點數是否為      4，是否為凸多邊形，且相鄰邊的夾角的      cosin值是否接近0(也即是角度為90度)，如果均滿足代表這個多邊形為矩形，存入結果中。
• 在結果圖中畫出檢測到的矩形區域。

3. 代碼實現

下面給出上面算法的核心代碼實現。

const double eps = 1e-7;

//獲取pt0->pt1向量和pt0->pt2向量之間的夾角
static double angle(Point pt1, Point pt2, Point pt0)
{
	double dx1 = pt1.x - pt0.x;
	double dy1 = pt1.y - pt0.y;
	double dx2 = pt2.x - pt0.x;
	double dy2 = pt2.y - pt0.y;
	return (dx1*dx2 + dy1*dy2) / sqrt((dx1*dx1 + dy1*dy1)*(dx2*dx2 + dy2*dy2) + eps);
}

//尋找矩形
static void findSquares(const Mat& image, vector<vector<Point> >& squares, int N=5, int thresh=50)
{

	//濾波可以提升邊緣檢測的性能
	Mat timg(image);
	// 普通中值濾波
    medianBlur(image, timg, 9);
	// SideWindowFilter的中值濾波
	// timg = MedianSideWindowFilter(image, 4);
	Mat gray0(timg.size(), CV_8U), gray;
	// 存儲輪廓
	vector<vector<Point> > contours;

	// 在圖像的每一個顏色通道尋找矩形
	for (int c = 0; c < 3; c++)
	{
		int ch[] = { c, 0 };
		// 函數功能：mixChannels主要就是把輸入的矩陣（或矩陣數組）的某些通道拆分復制給對應的輸出矩陣（或矩陣數組）的某些通道中，其中的對應關系就由fromTo參數制定.
		// 接口：void  mixChannels (const Mat*  src , int  nsrc , Mat*  dst , int  ndst , const int*  fromTo , size_t  npairs );
		// src: 輸入矩陣，可以為一個也可以為多個，但是矩陣必須有相同的大小和深度.
		// nsrc: 輸入矩陣的個數.
		// dst: 輸出矩陣，可以為一個也可以為多個，但是所有的矩陣必須事先分配空間（如用create），大小和深度須與輸入矩陣等同.
		// ndst: 輸出矩陣的個數
		// fromTo:設置輸入矩陣的通道對應輸出矩陣的通道，規則如下：首先用數字標記輸入矩陣的各個通道。輸入矩陣個數可能多于一個并且每個矩陣的通道可能不一樣，
		// 第一個輸入矩陣的通道標記范圍為：0 ~src[0].channels() - 1，第二個輸入矩陣的通道標記范圍為：src[0].channels() ~src[0].channels() + src[1].channels() - 1,
		// 以此類推；其次輸出矩陣也用同樣的規則標記，第一個輸出矩陣的通道標記范圍為：0 ~dst[0].channels() - 1，第二個輸入矩陣的通道標記范圍為：dst[0].channels()
		// ~dst[0].channels() + dst[1].channels() - 1, 以此類推；最后，數組fromTo的第一個元素即fromTo[0]應該填入輸入矩陣的某個通道標記，而fromTo的第二個元素即
        // fromTo[1]應該填入輸出矩陣的某個通道標記，這樣函數就會把輸入矩陣的fromTo[0]通道里面的數據復制給輸出矩陣的fromTo[1]通道。fromTo后面的元素也是這個
        // 道理，總之就是一個輸入矩陣的通道標記后面必須跟著個輸出矩陣的通道標記.
		// npairs: 即參數fromTo中的有幾組輸入輸出通道關系，其實就是參數fromTo的數組元素個數除以2.
		mixChannels(&timg, 1, &gray0, 1, ch, 1);

		// 嘗試幾個不同的閾值
		for (int l = 0; l < N; l++)
		{
			// hack: use Canny instead of zero threshold level.
			// Canny helps to catch squares with gradient shading
			// 在級別為0的時候不使用閾值為0，而是使用Canny邊緣檢測算子
			if (l == 0)
			{
				// void Canny(	InputArray image, OutputArray edges, double threshold1, double threshold2, int apertureSize = 3, bool L2gradient = false);
				// 第一個參數：輸入圖像（八位的圖像）
				// 第二個參數：輸出的邊緣圖像
				// 第三個參數：下限閾值，如果像素梯度低于下限閾值，則將像素不被認為邊緣
				// 第四個參數：上限閾值，如果像素梯度高于上限閾值，則將像素被認為是邊緣（建議上限是下限的2倍或者3倍）
				// 第五個參數：為Sobel()運算提供內核大小，默認值為3
				// 第六個參數：計算圖像梯度幅值的標志，默認值為false
				Canny(gray0, gray, 5, thresh, 5);
				// 執行形態學膨脹操作
				dilate(gray, gray, Mat(), Point(-1, -1));
			}
			else
			{
				// 當l不等于0的時候，執行 tgray(x,y) = gray(x,y) < (l+1)*255/N ? 255 : 0
				gray = gray0 >= (l + 1) * 255 / N;
			}

			// 尋找輪廓并將它們全部存儲為列表
			findContours(gray, contours, RETR_LIST, CHAIN_APPROX_SIMPLE);

			//存儲一個多邊形（矩形）
			vector<Point> approx;

			// 測試每一個輪廓
			for (size_t i = 0; i < contours.size(); i++)
			{
				// 近似輪廓，精度與輪廓周長成正比,主要功能是把一個連續光滑曲線折線化，對圖像輪廓點進行多邊形擬合。
				// 函數聲明：void approxPolyDP(InputArray curve, OutputArray approxCurve, double epsilon, bool closed)
				// InputArray curve:一般是由圖像的輪廓點組成的點集
				// OutputArray approxCurve：表示輸出的多邊形點集
				// double epsilon：主要表示輸出的精度，就是兩個輪廓點之間最大距離數，5,6,7，，8，，,,，
				// bool closed：表示輸出的多邊形是否封閉

				// arcLength 計算圖像輪廓的周長
				approxPolyDP(Mat(contours[i]), approx, arcLength(Mat(contours[i]), true)*0.02, true);

				// 近似后，方形輪廓應具有4個頂點
				// 相對較大的區域（以濾除嘈雜的輪廓）并且是凸集。
				// 注意: 使用面積的絕對值，因為面積可以是正值或負值-根據輪廓方向
				if (approx.size() == 4 &&
					fabs(contourArea(Mat(approx))) > 1000 &&
					isContourConvex(Mat(approx)))
				{
					double maxCosine = 0;

					for (int j = 2; j < 5; j++)
					{
						// 找到相鄰邊之間的角度的最大余弦
						double cosine = fabs(angle(approx[j % 4], approx[j - 2], approx[j - 1]));
						maxCosine = MAX(maxCosine, cosine);
					}

					// 如果所有角度的余弦都很小(所有角度均為90度)，將頂點集合寫入結果vector
					if (maxCosine < 0.3)
						squares.push_back(approx);
				}
			}
		}
	}
}

//在圖像上畫出方形
void drawSquares(Mat &image, const vector<vector<Point> >& squares) {
	for (size_t i = 0; i < squares.size(); i++)
	{
		const Point* p = &squares[i][0];

		int n = (int)squares[i].size();
		//不檢測邊界
		if (p->x > 3 && p->y > 3)
			polylines(image, &p, &n, 1, true, Scalar(0, 255, 0), 3, LINE_AA);
	}
}

在上面的代碼中，完全是按照算法原理的步驟來進行實現，比較容易理解。我在測試某張圖片的時候發現，如果把Side Window Filter應用到這里有時候會產生更好的效果，因此實現了一下用于中值濾波的Side Window Filter，介于篇幅原因請到我的github查看，地址為：https://github.com/BBuf/Image-processing-algorithm/blob/master/MedianSideWindowFilter.cpp。關于SideWindowFilter可以看我們前兩天的文章：【AI移動端算法優化】一，CVRR 2018 Side Window Filtering 論文解讀和C++實現

4. 普通中值濾波的結果

 

 

這個例子普通中值濾波就做得比較好了，也就沒必要用Side Window Filter的中值濾波了。

5. 對比普通中值濾波和Side Window Filter中值濾波的結果

 

 

 

可以看到在最后這張圖中，因為使用了Side Window Filter，在排除了一些噪聲的同時保住了邊緣和角點，使得檢出率提高了很多，也說明了Side Window Filter的有效性。