背景
霍夫變換應(yīng)該是在邊緣檢測(cè)的基礎(chǔ)上的蝌以，如果要在如下這張圖中做直線的檢測(cè)地熄，opencv有很多邊緣檢測(cè)的算法得到一個(gè)8bit的圖，本文所述的霍夫變換的原理也是在這個(gè)邊緣檢測(cè)的結(jié)果上進(jìn)行的
算法基礎(chǔ)
極坐標(biāo)變換
笛卡爾坐標(biāo)系中的任意一點(diǎn)（x,y）都可以表示成ρ=x·cosθ+y·sinθ，的形式泰偿，而后者（ρ,θ）是極坐標(biāo)通危。而在這個(gè)極坐標(biāo)系下铸豁，一個(gè)（ρ, θ）是可以表示一條直線，如下圖菊碟。
這樣的直線的表示方式具有以下性質(zhì)：
- 極坐標(biāo)中的一個(gè)點(diǎn)（ρ, θ）就表示笛卡爾坐標(biāo)系中的一條直線
- 笛卡爾坐標(biāo)系中過某一個(gè)點(diǎn)（x,y）的所有直線在極坐標(biāo)中變?yōu)橐粭l正弦曲線
證明：假設(shè)點(diǎn)（x,y）节芥，令sinα=x/sqrt(x2+y2)，cosα=y/sqrt(x2+y2)逆害。
ρ=sqrt(x2+y2)·(sinα·cosθ+cosα·sinθ)=sqrt(x2+y2)·sin(α+θ)头镊。即表示一條振幅為sqrt(x2+y2)，相位為α的正弦曲線魄幕。
- 笛卡爾坐標(biāo)系中過點(diǎn)A和B的直線（直線AB）相艇，在極坐標(biāo)系中表現(xiàn)為兩條正弦曲線的相交（即一條正弦曲線表示過A的所有直線，一條正弦曲線表示過B的所有直線纯陨，兩條正弦曲線的交點(diǎn)就表示直線AB）
算法
現(xiàn)假設(shè)我們已經(jīng)有上文中所述的邊緣檢測(cè)的結(jié)果留储，這個(gè)邊緣檢測(cè)的結(jié)果與原圖等大，邊緣檢測(cè)結(jié)果中的值都是0-255之間的咙轩，假設(shè)一個(gè)原圖為640*480获讳，其中邊緣點(diǎn)有n個(gè)（n<=640*480）。我們可以針對(duì)每一個(gè)邊緣點(diǎn)在極坐標(biāo)中畫一條正弦曲線（上述的性質(zhì)2）活喊，共n條正弦曲線丐膝。然后分別這些正弦曲線兩兩之間的交點(diǎn)坐標(biāo)是多少（只需要0~π之間的交點(diǎn)即可），時(shí)間復(fù)雜度是n(n-1)/2胧弛。然后尋找穿過的線最多的交點(diǎn)尤误，一個(gè)交點(diǎn)有越多的線，就表示有越多點(diǎn)共線结缚。
上述的算法是很顯然的损晤，但是效率是O(n2)，太低了红竭。因此[2]作者做了如下的改進(jìn)：
- 把ρ和θ離散化尤勋，例如ρ（-R<ρ<R）等分為2R份，步長(zhǎng)為1茵宪，θ步長(zhǎng)為1°最冰，把180度等分180分。
- 建立一個(gè)二維數(shù)組（accumulator array）稀火，大小為2R*180暖哨，數(shù)組中的每個(gè)元素代表經(jīng)過當(dāng)前（ρ,θ）的直線的點(diǎn)的數(shù)量。
步驟
- 對(duì)每個(gè)點(diǎn)篇裁，找出他們?cè)趫D中的坐標(biāo)(x,y)
- 根據(jù)公式ρ=x·cosθ+y·sinθ，把x,y和θ（以上圖為例θ=0°赡若、±20°达布、±40°、±60°……±160°）帶入算出ρ逾冬，在找出accumulator array中找到對(duì)應(yīng)的ρ并對(duì)數(shù)組中對(duì)應(yīng)計(jì)數(shù)+1
- 計(jì)算完所有點(diǎn)后黍聂，找出accumulator中最大的一些數(shù)（或設(shè)定一個(gè)閾值），他們的索引(ρ,θ)即為最后索引到的直線
OpenCV中的函數(shù)HoughLines
OpenCV中相關(guān)的函數(shù)有
cv2.HoughLinesP() # 與上述步驟略有不同
cv2.HoughLines() # 與上述步驟幾乎完全相同
cv2.HoughCircles() # 利用霍夫變換畫圓
其中身腻，HoughLins中的參數(shù)产还，rho和theta的含義就是上述表格中的ρ和θ的步長(zhǎng)，threshold是閾值嘀趟，即accumulator中大于threshold的直線會(huì)被選出雕沉，代表至少有threshold個(gè)點(diǎn)經(jīng)過了這條直線。min_theta和max_theta代表的是θ的范圍去件。
可以看出坡椒，HoughLines這個(gè)函數(shù)的執(zhí)行效率取決于rho、theta尤溜、min_theta和max_theta倔叼，當(dāng)然，也取決于邊緣檢測(cè)結(jié)果中邊緣像素的數(shù)量n宫莱。
參考文獻(xiàn)
[1] P.V.C. Hough,Machine Analysis of Bubble Chamber Pictures, Proc. Int. Conf. High Energy Accelerators and Instrumentation, 1959.
[2] Duda, R. O. and P. E. Hart, "Use of the Hough Transformation to Detect Lines and Curves in Pictures,"Comm. ACM, Vol. 15, pp. 11–15 (January, 1972).
[3] https://blog.csdn.net/songzitea/article/details/17027849
[4] https://blog.csdn.net/shanchuan2012/article/details/74010561
