二值图像分析–直线拟合与极值点寻找

极值点寻找"/>

二值图像分析–直线拟合与极值点寻找

在图像的处理中，会遇到一种情况，根据给定的点集（比如轮廓）拟合出一条直线的情景。

1.最小二乘法拟合直线

最小二乘法多项式直线拟合，根据给定的点，求出它的函数 y = f ( x ) y=f(x) y=f(x)，当然求得准确的函数是不太可能的，但是我们能够求出它的近似曲线 y = φ ( x ) y=φ(x) y=φ(x)。

原理：
假如有点I = 1,2,3,……n,求近似曲线 y = φ ( x ) y=φ(x) y=φ(x)，并且使得 y = φ ( x ) y=φ(x) y=φ(x)与 y = f ( x ) y=f(x) y=f(x)的平方偏差和最小偏差:

现在有点（ x 1 , y 1 x_1,y_1 x1​,y1​)，( x 2 , y 2 x_2,y_2 x2​,y2​)···( x n , y n x_n,y_n xn​,yn​)
设: 拟合多项式为： y = a x + b y=ax+b y=ax+b
平方偏差和如下：
e 2 = ∑ i = 1 n ( y i − y ) 2 = ∑ i = 1 n ( y i − ( a x + b ) ) 2 e^2=\sum_{i=1}^{n}(y_i-y)^2 =\sum_{i=1}^{n}(y_i-(ax+b))^2 e2=i=1∑n​(yi​−y)2=i=1∑n​(yi​−(ax+b))2

其中我们要找到一组最好的a和b，“最好的”就是要使选出的a b能使得所有的误差达到最小化。所以上面得到的 e 2 = ∑ i = 1 n ( y i − ( a x + b ) ) 2 e^2=\sum_{i=1}^{n}(y_i-(ax+b))^2 e2=∑i=1n​(yi​−(ax+b))2就是一个关于a和b的函数。

2.多元函数极值与最值问题的理论依据

二元函数取极值的必要条件(类比一元函数)。

可以看到最小二乘法对各个变量求偏导，使得偏导值为0，即可得到最小值，因为e是关于a、b的函数，导数为0的点必定是最小值。
分别对a、b求偏导：

OpenCV中的API

• 说明
  使线拟合2D或者3D点集。

  函数fitLine通过最小化 ∑ i ρ ( r i ) \sum_i \rho(r_i) ∑i​ρ(ri​)将线拟合到2维或3维点，其中 r i r_i ri​是第 i t h i^{th} ith个点之间的距离，该线和 ρ ( r ) \rho(r) ρ(r)是一个距离函数。

  该算法基于M-estimator技术，该技术使用加权最小二乘算法迭代拟合直线。每次迭代后，权重 w i w_i wi​被调整 ρ ( r i ) \rho(r_i) ρ(ri​)。

• 声明

  void fitLine(InputArray points, OutputArray line, int distType,double param, double reps, double aeps );
  

• 参数

  points	用于拟合直线的输入点集，可以是2维或者3维点向量。保存在std::vector<>或者Mat中。
  line	输出的直线。对于二维直线而言，类型为cv::Vec4f；对于三维直线类型，则为cv::Vec6f。输出参数的前半部分给出的是直线的方向，而后半部分给出的是直线上的一点（即通常所说的点斜式直线）。
  distType	距离类型。拟合直线时，要使输入点到拟合直线的距离和最小化，可供选择的距离类型如下， r i r_i ri​表示的是输入的点到直线的距离。
  param	某些距离类型的数值参数（C）。跟所选的距离类型有关，值可以设置为0，cv::fitLine()函数本身会自动选择最优化的值如果为0。
  reps	半径的足够精度（坐标原点和直线之间的距离）。
  aeps	角度精度足够。对于reps和aeps，0.01将是一个很好的默认值。

  distType类型

  ① DIST_L2
  ρ ( r ) = r 2 / 2 (the simplest and the fastest least-squares method) \rho(r) = r^2/2 \quad \text{(the simplest and the fastest least-squares method)} ρ(r)=r2/2(the simplest and the fastest least-squares method)
  ② DIST_L1
  ρ ( r ) = r \rho (r) = r ρ(r)=r
  ③ DIST_L12
  ρ ( r ) = 2 ⋅ ( 1 + r 2 2 − 1 ) \rho (r) = 2 \cdot ( \sqrt{1 + \frac{r^2}{2}} - 1) ρ(r)=2⋅(1+2r2​ ​−1)
  ④ DIST_FAIR
  ρ ( r ) = C 2 ⋅ ( r C − log ⁡ ( 1 + r C ) ) where C = 1.3998 \rho \left (r \right ) = C^2 \cdot \left ( \frac{r}{C} - \log{\left(1 + \frac{r}{C}\right)} \right ) \quad \text{where} \quad C=1.3998 ρ(r)=C2⋅(Cr​−log(1+Cr​))whereC=1.3998
  ⑤ DIST_WELSCH
  ρ ( r ) = C 2 2 ⋅ ( 1 − exp ⁡ ( − ( r C ) 2 ) ) where C = 2.9846 \rho \left (r \right ) = \frac{C^2}{2} \cdot \left ( 1 - \exp{\left(-\left(\frac{r}{C}\right)^2\right)} \right ) \quad \text{where} \quad C=2.9846 ρ(r)=2C2​⋅(1−exp(−(Cr​)2))whereC=2.9846
  ⑥ DIST_HUBER
  ρ ( r ) = { r 2 / 2 i f r < C C ⋅ ( r − C / 2 ) o t h e r w i s e where C = 1.345 \rho (r)= \begin{cases} r^2/2 &if \ \ r < C \\ C \cdot (r-C/2) &otherwise \end{cases} \quad \text{where} \quad C=1.345 ρ(r)={r2/2C⋅(r−C/2)​if  r<Cotherwise​whereC=1.345

应用

void apprixiLine() {//创建一个用于绘图的空白图Mat src = Mat::zeros(480, 640, CV_8UC3);//输入需要拟合的点vector<Point> points;points.push_back(Point(48, 58));points.push_back(Point(105, 98));points.push_back(Point(155, 160));points.push_back(Point(212, 220));points.push_back(Point(248, 260));points.push_back(Point(320, 300));points.push_back(Point(350, 360));points.push_back(Point(412, 400));//将拟合点画到空白画板上for (size_t i = 0; i < points.size(); i++){circle(src, points[i], 5, Scalar(0, 0, 255));}imshow("src", src);Vec4f line_para;fitLine(points, line_para, DIST_L2, 0, 1e-2, 1e-2);cout << "line_para: " << line_para << endl;Point point0;point0.x = line_para[2];point0.y = line_para[3];cout << "point0:[" << point0.x << "," << point0.y << "]" << endl;double k = line_para[1] / line_para[0];cout << "k=" << k << endl;//计算直线的端点Point point1, point2;point1.x = 0;point1.y = k * (0 - point0.x) + point0.y;point2.x = 640;point2.y = k * (640 - point0.x) + point0.y;cout << "point1:[" << point1.x << "," << point1.y << "]" << endl;cout << "point2:[" << point2.x << "," << point2.y << "]" << endl;line(src, point1, point2, Scalar(0, 255, 0), 2);imshow("dst", src);
}

2. 事例二

void findFitLine(Mat& src) {//1. 转化灰度图像Mat gray;cvtColor(src, gray, COLOR_BGR2GRAY);//2. 二值化Mat binary;threshold(gray, binary, 0, 255, THRESH_BINARY | THRESH_OTSU);//3. 获得二维点集vector<Point> point_para;Point point_temp;for (size_t i = 0; i < src.rows; i++){for (size_t j = 0; j < src.cols; j++){if (binary.at<unsigned char>(i, j) < 255) {point_temp.x = j;point_temp.y = i;point_para.push_back(point_temp);}}}//4.直线拟合//拟合结果为4元素的容器，比如Vec4f-(vx,vy,x0,y0)//（vx、vy）是直线的方向向量//（x0、y0）是直线上的一个点Vec4f fitline;fitLine(point_para, fitline, DIST_L2, 0, 0.01, 0.01);//4.2 求出直线上的两个点double k = fitline[1] / fitline[0];Point p1(0, k * (0 - fitline[2]) + fitline[3]);Point p2(src.cols - 1, k * ((src.cols - 1) - fitline[2]) + fitline[3]);//4.3 显示拟合出的直线方程cout << "y-" << fitline[3] << "=" << k << "(x-" << fitline[2] << ")" << endl;line(src, p1, p2, Scalar(0, 0, 255), 2);imshow("dst", src);
}int main() {Mat src = imread("D:/test/fitline.png");if (src.empty()) {cout << " input the image error!" << endl;}imshow("src", src);findFitLine(src);waitKey(0);return 0;}

学习：

直线拟合——cv::fitLine()详解
【算法+OpenCV】基于opencv的直线和曲线拟合与绘制（最小二乘法）
opencv学习——最小二乘法拟合直线
OpenCV—直线拟合fitLine
【OpenCV3】直线拟合–FitLine()函数详解