霍夫变换是一种用于寻找简单几何形状的特征提取方法。

1 寻找直线

极坐标与直角坐标的变换关系：

线在极坐标系中的表式：\(r=x\cos \theta +y\sin \theta\)
其中，\(r\)是从原点到直线的距离，\(\theta\)是\(\vec{r}\)和\(x\)轴的夹角

给定一个点\((x_{0},y_{0})\)，通过该点的所有直线的参数\((r, \theta)\)的集合，会在\((r, \theta)\)平面上形成一个三角函数。
\[ r=x_{0}\cos \theta +y_{0}\sin \theta \Rightarrow r={\sqrt {x_{0}^{2}+y_{0}^{2}}}\left({\frac {x_{0}}{\sqrt {x_{0}^{2}+y_{0}^{2}}}}\cos \theta +{\frac {y_{0}}{\sqrt {x_{0}^{2}+y_{0}^{2}}}}\sin \theta \right) \Rightarrow r={\sqrt {x_{0}^{2}+y_{0}^{2}}}\left(\cos \phi \cos \theta +\sin \phi \sin \theta \right) \Rightarrow r={\sqrt {x_{0}^{2}+y_{0}^{2}}}\cos(\theta -\phi ) \]

给定很多点，判断这些点是否共线的问题，经由上述变换之后，变成判断一堆曲线是否在平面\((r, \theta)\)上相交于同一点的问题。

注：之所以使用极坐标系是为了计算方便，因为直角坐标系中当直线趋近于垂直\(x\)轴，它的斜率趋近于无限大

1.1 在OpenCV中使用霍夫变换寻找直线

// Read the image as gray-scale
Mat img = imread('lanes.jpg', IMREAD_COLOR);
// Convert to gray-scale
Mat gray = cvtColor(img, COLOR_BGR2GRAY);
// Store the edges 
Mat edges;
// Find the edges in the image using canny detector
Canny(gray, edges, 50, 200);
// Create a vector to store lines of the image
vector<Vec4i> lines;
// Apply Hough Transform
HoughLinesP(edges, lines, 1, CV_PI/180, thresh, 10, 250);
// Draw lines on the image
for (size_t i=0; i<lines.size(); i++) {
    Vec4i l = lines[i];
    line(src, Point(l[0], l[1]), Point(l[2], l[3]), Scalar(255, 0, 0), 3, LINE_AA);
}
// Show result image
imshow("Result Image", img);

2 寻找圆

圆的表达式：\((x-x_0)^2 + (y-y_0)^2 = r^2\)

2.1 在OpenCV中使用霍夫变换寻找圆

// Read the image as gray-scale
img = imread("circles.png", IMREAD_COLOR);
// Convert to gray-scale
gray = cvtColor(img, COLOR_BGR2GRAY);
// Blur the image to reduce noise 
Mat img_blur;
medianBlur(gray, img_blur, 5);
// Create a vector for detected circles
vector<Vec3f>  circles;
// Apply Hough Transform
HoughCircles(img_blur, circles, HOUGH_GRADIENT, 1, img.rows/64, 200, 10, 5, 30);
// Draw detected circles
for(size_t i=0; i<circles.size(); i++) {
    Point center(cvRound(circles[i][0]), cvRound(circles[i][1]));
    int radius = cvRound(circles[i][2]);
    circle(img, center, radius, Scalar(255, 255, 255), 2, 8, 0);
}

3 参考

Hough Transform with OpenCV (C++/Python)
霍夫变换 - 百科