霍夫變換

1.What
霍夫變換是一種特征提取手段，用來提取形狀（直線，圓等）邊界[1]。

2.Why
形狀邊界假設是直線，這條線是很多點組成的一個集合。處理這個集合，比處理一個點要復雜的多。簡單講，霍夫變換就是想把一條線（邊界）用點來處理，這樣就會更容易提取出邊界。

3.How
前面提到把線換成點來處理，其實是通過空間變換來實現的，變換后的空間就是霍夫空間。
3.1霍夫空間
直角坐標系（x，y）空間中，每條直線y = mx + c可以由兩個參數確認：
(1)斜率m
(2)Y軸上的截距c
如果將m，c看成是自變量，有c=-xm+y，這個（m，c）空間就是霍夫空間。
3.2霍夫變換
3.2.1概念
對于(x, y)空間上的某個點(x1, y1)有y1?= m*x1?+ c，則c = -x1*m + y1，這也就是霍夫空間上的一條直線。
對于(x, y)空間上的某條直線有y?= m1*x?+ c1，則c1 = -x*m1 + y，這也就是霍夫空間上的一個點(m1, c1)。
總結：(x, y)空間 -> (m, c)空間,點變成直線，直線變成點。

3.2.2特點
如下圖，左邊(x, y)空間，右邊是(m, c)空間
p1，p2，p3，p4是(x, y)空間上4個點。對應(m, c)空間上4條直線l1，l2，l3，l4。l1和l2的焦點的值，(m1, c1)，對應的是(x, y)空間上穿過p1和p2點的直線的斜率和截距。同理l3和l4的焦點的值，(m2, c2)對應的是(x, y)空間上穿過p3和p4點的直線的斜率和截距。明白這個道理，就已經掌握這個變換的整個過程了。

3.2.3檢測直線
檢測(x, y)空間上直線：
(1)在霍夫空間中，統計直線的焦點次數，比如上圖l1，l2，l3這三條直線的焦點，分別是l1，l2； l2，l3； l1，l3。因此次數是3。把這種統計焦點的次數稱為投票。
(2)將統計好的點的次數，列表，如下

Points	No. of Votes
(m11, c81)	50
(m29, c36)	80
(m30, c70)	60

3個點分別是50，80，60次。這樣就可以設定一個閾值，如果閾值為55，那么最終得到的點就是(29, 36), (30, 70)對應的是(x, y)空間上兩條直線。
(3)準確度
準確度是由每次m和c的值增加的步幅來確定的，比如m和c的步幅為step1 = 1和step2 = 2，那么(m, c)在step1遍歷的點比step2要多，因此準確度更高。
(4)問題
如果(x, y)空間上的直線是一個趨近于豎直的線，這時截距可能就是一個無限大的數，這個數要在(m, c)空間上怎么表示呢，在計算機中怎么處理呢？因此這個(m, c)空間不能夠很好的處理這些“特殊”的直線。

3.3極坐標系下的霍夫空間
為解決3.2.3中（4）的問題，我們將霍夫空間換成極坐標表示。(x, y)空間上的直線在極坐標系中表示如下：r = x1cos(Θ)+y1sin(Θ)，r是原點到直線的垂直距離，Θ是“距離”這個線段與x軸的夾角。如下圖[2]

Θ范圍(-90,+90),

r范圍(0,diagonal_length),diagonal_length是原圖對角 線長度。

變換關系
(x, y)空間上的直線對應在(r, Θ)空間仍然是點，但是(x, y)空間上的點對應在(r, Θ)空間是正弦曲線。同樣采用“投票”機制，(r, Θ)空間下，兩條正弦曲線相交一個點，就把這個點被相交的次數+1的。這個交點就是對應(x, y)空間上穿過兩條正弦曲線對應的點的直線。如下圖

為了記錄這些“投票”結果，可以用一個二維矩陣作為累加器來實現，(Θ, r)作為矩陣的元素。對于每個(x, y)空間上的點，變換Θ來得到不同的r。把每個
得到的Θ, r的組合在二維矩陣中對應位置+1。如下表

Points	No. of Votes
(Θ51, r83)	100
(Θ29, r46)	80
(Θ30, r70)	60

得到三組值，第一組表示(Θ51, r83)對應的原圖直線穿過了100個點，因此這條直線得到的投票很高，被提取效果應該比較好。
同樣，可以設定閾值，比如75，那么只提取出第一組和第二組的兩條直線。
準確度控制，可以用Θ的步幅來控制，比如1次增加1度要比一次增加5度提取出來的直線更加準確。

3.4補充
霍夫變換檢測邊緣只對邊緣圖片（經過canny或者sobe算子提取特征后的圖片）有效，對一般的圖片無效[3]。

參考文獻
[1] Hough Transform
[2] https://homepages.inf.ed.ac.uk/rbf/HIPR2/hough.htm
[3] https://aishack.in/tutorials/hough-transform-normal/

總結

以上是生活随笔為你收集整理的霍夫变换详细解释的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。