• 背景介绍

opencv中有逼近多边形曲线的函数approxPolyDP，但是不能一直做一个调包侠，因此我用opencv实现了一篇论文中介绍的两种多边形拟合算法。论文名称：《图像处理中多边形拟合的快速算法》，作者：张帆等，点此下载。在写代码之前，首先要了解两个简单的数学知识。

1、已知两个点的坐标，，如何确定直线方程 中a、b、c的数值？

整理上式得：

因此：

                                         ，，

2、点到直线的距离公式：

• Opencv实例

该论文中作者提出的多边形拟合算法，我用opencv实现以后发现找到的边缘并不是目标真实的边缘（本人能力水平有限，可能并没有理解作者的真正思想）。因此我对其算法步骤进行了修改，将第六步中的阈值T变为一个比T小的数值，得到下图所示结果。根据结果图可以看出，还是opencv官方的算法效果比较好，不仅速度快而且精度高。其它两种算法速度较慢，且得到的轮廓有些许变形。

效果图：

                                                                                                   原图

                     opencv自带方法                                          迭代端点拟合法                                            多边形拟合法

代码：

/////////////////////////
//opencv4.1.0
/////////////////////////

#include <opencv2/opencv.hpp>
#include <iostream>
#include <math.h>

using namespace cv;
using namespace std;

Mat src, binary, src_gray;
TickMeter tm;


/***** Opencv自带方法*****/
void OpencvFitting(vector<vector<Point>>& contours);

/***** 迭代端点拟合法*****/
float T = 0.9;    //距离阈值
int step = 20;    //步长
vector<Point>ResultContours;
void IterativeEndpointFitting(vector<vector<Point>>& contours);
void fun(int top, int sum, int j, vector<vector<Point>>& contours);
float getDist_P2L(Point pointP, Point pointA, Point pointB);

/***** 多边形拟合法*****/
void PolygonFitting(vector<vector<Point>>& contours);


int main(int argc,char** argv )
{
	//读取图片
	src = imread("3.jpg");
	if (src.empty()){
		printf("读取图像失败n");
		return -1;
	}
	imshow("输入图片",src);

	//二值化
	cvtColor(src,src_gray,COLOR_BGR2GRAY);
	threshold(src_gray,binary,0,255,THRESH_BINARY|THRESH_OTSU);

	//寻找轮廓，并获取坐标点集
	vector<Vec4i>hireachy;
	vector<vector<Point>> contours;
	findContours(binary,contours,hireachy,RETR_TREE,CHAIN_APPROX_NONE,Point());

	//Opencv自带方法
	tm.start();
	OpencvFitting(contours);
	tm.stop();
	cout << "Opencv自带方法运行时间：" << tm.getTimeMilli() << endl;

	//迭代端点拟合法
	tm.start();
	IterativeEndpointFitting(contours);
	tm.stop();
	cout << "迭代端点拟合法运行时间：" << tm.getTimeMilli() << endl;

	//多边形拟合法
	tm.start();
	PolygonFitting(contours);
	tm.stop();
	cout << "多边形拟合法运行时间：" << tm.getTimeMilli() << endl;

	waitKey(0);
	return 0;
}


void OpencvFitting(vector<vector<Point>>& contours) {

	//逼近多边形曲线
	vector<vector<Point>> poly(contours.size());
	for (size_t t = 0; t<contours.size();t++){
		approxPolyDP(contours[t], poly[t], 5, true);
	}

	//画出轮廓
	Mat OpencvResult = Mat::zeros(src_gray.size(), CV_8UC3);
	for (size_t t = 0; t<contours.size();t++){
		drawContours(OpencvResult, poly, t, Scalar(0, 255, 255), 1, 8, Mat(), 0, Point());
	}
	imshow(" OpencvResult", OpencvResult);
}

void IterativeEndpointFitting(vector<vector<Point>>& contours) {

	for (int j = 0; j<contours[0].size() - 10; j = j + step)
	{
		fun(step, step, j,contours);
	}
	vector<vector<Point>> contours1;
	contours1.push_back(ResultContours);//一维向量点集转换为二维向量点集：vector<Point>  ——  vector<vector<Point>>，否则drawContours函数崩溃

	//画出轮廓
	Mat MyResult = Mat::zeros(src_gray.size(), CV_8UC3);
	for (size_t t = 0; t<contours1.size();t++)
	{
		drawContours(MyResult, contours1, t, Scalar(0, 255, 255), 1, 8, Mat(), 0, Point());
	}
	imshow(" 迭代端点拟合法", MyResult);
}

//top:在步长范围内，距离最大点的序号
//sum:参与计算的点的个数
//j:  步数*步长
void fun(int top, int sum, int j, vector<vector<Point>>& contours)
{
	Point LeftE, RightE;                       //左右两侧点距离直线距离最大点的坐标
	float LeftH = 0, RightH = 0;                   //左右两侧点距离直线距离最大值
	int MaxValueIndexLeft, MaxValueIndexRight; //左右两侧点距离直线距离最大值对应的索引
	for (int i = 0; i <= top;i++)
	{
		//左侧距离计算
		float DistanceLeft = getDist_P2L(contours[0][i + j], contours[0][0 + j], contours[0][top + j]);
		if (DistanceLeft>LeftH)
		{
			LeftH = DistanceLeft;
			LeftE = contours[0][i + j];
			MaxValueIndexLeft = i;
		}

		//右侧距离计算
		if (sum != top && i <= (sum - top))
		{
			float DistanceRight = getDist_P2L(contours[0][i + j + top], contours[0][top + j], contours[0][sum + j]);
			if (DistanceRight>RightH)
			{
				RightH = DistanceRight;
				RightE = contours[0][i + j + top];
				MaxValueIndexRight = i;
			}
		}
	}
	if (LeftH>T)
	{
		ResultContours.push_back(LeftE);
		fun(MaxValueIndexLeft, top, j, contours);
	}
	if (RightH>T && sum != top)
	{
		ResultContours.push_back(RightE);
		fun(MaxValueIndexRight, top, j, contours);
	}
}

/***** 点P到直线AB的距离*****/
float getDist_P2L(Point pointP, Point pointA, Point pointB)
{
	//求直线方程
	int A = 0, B = 0, C = 0;
	A = pointA.y - pointB.y;
	B = pointB.x - pointA.x;
	C = pointA.x*pointB.y - pointA.y*pointB.x;
	//代入点到直线距离公式
	float distance = 0;
	distance = ((float)abs(A*pointP.x + B*pointP.y + C)) / ((float)sqrtf(A*A + B*B));
	return distance;
}

void PolygonFitting(vector<vector<Point>>& contours) {

	int T = 10;
	Point E;
	vector<Point>ResultContours;
	for (int j = 0; j<contours[0].size() / (4 * T); j++) {
		float H = 0;
		for (int i = 2 * T + 4 * T*j; i <= 3 * T + 4 * T*j;i++) {
			float Distance = getDist_P2L(contours[0][i], contours[0][0 + 4 * T*j], contours[0][4 * T + 4 * T*j]);
			if (Distance>H) {
				H = Distance;
				E = contours[0][i];
			}
		}
		if (H>1) {  //按照论文中描述，此处应该是if(H>T)，但我做了修改
			ResultContours.push_back(E);
		}
	}

	vector<vector<Point>> contours1;
	contours1.push_back(ResultContours);//一维向量点集转换为二维向量点集：vector<Point>  ——  vector<vector<Point>>，否则drawContours函数崩溃

	//画出轮廓
	Mat MyResult = Mat::zeros(src_gray.size(), CV_8UC3);
	for (size_t t = 0; t<contours1.size();t++)
	{
		drawContours(MyResult, contours1, t, Scalar(0, 255, 255), 1, 8, Mat(), 0, Point());
	}
	imshow(" 多边形拟合法", MyResult);
}