【小林的OpenCV基礎課番外】霍夫變換原理

03-04

同樣是一篇講解原理的番外，這一篇主要講解CV中常用的霍夫變換的數學原理。

霍夫變換的由來

「霍夫變換於1962年由Paul Hough首次提出，最初的Hough變換是設計用來檢測直線和曲線，起初的方法要求知道物體邊界線的解析方程，但不需要有關區域位置的先驗知識。後於1972年由Richard Duda & Peter Hart推廣使用。」

其實，霍夫變換的中心思想就是通過坐標變換來檢測直線，後來經過改進，就可以檢測橢圓等。

霍夫線變換

坐標系的角度：

說起直線，我們會想到笛卡爾坐標系（即x-y坐標系）下的直線方程，細分之則有點斜式、截距式等， $y=kx+b$ 是我們最熟悉的一種。但直線垂直於x軸時斜率 $k$ 不存在，這給我們帶來許多不便之處。

這時極坐標就carry全場了，它與笛卡爾坐標系的轉換關係： $ho=xcos heta+ysin heta$ ，變形可得 $y= -frac{cos heta}{sin heta}x+frac{ ho}{sin heta}$ ， $ho$ 為原點到直線的距離，也常用 $r$ 表示，示意圖如下：

由此極坐標下，直線可用 $left( ho, heta ight)$ 表示。這就啟發我們，同一直線上的點具有相同的 $left( ho, heta ight)$ ：

x-y坐標系下的一個點在rho-theta坐標系下為正弦曲線

同一直線上的點會有相同的rho和theta，即在rho-theta下交於一點

統計學的角度：

內容出自：Opencv學習筆記-----霍夫變換直線檢測及原理理解 - CSDN博客

如上圖，假定在一個8*8的平面像素中有一條直線，並且從左上角 $left( 1,8 ight)$ 像素點開始分別計算 $heta$ 為0°、45°、90°、135°、180°時的 $ho$ ，圖中可以看出 $ho$ 分別為 $1、frac{9sqrt{2}}{2}、8、frac{7sqrt{2}}{2}、-1$ ，並給這5個值分別記一票，同理計算像素點 $left( 3,6 ight)$ 點 $heta$ 為0°、45°、90°、135°、180°時的 $ho$ ，再給計算出來的5個 $ho$ 值分別記一票，此時就會發現 $ho=frac{9sqrt{2}}{2}$ 的這個值已經記了兩票了，以此類推，遍歷完整個8*8的像素空間的時候 $ho=frac{9sqrt{2}}{2}$ 就記了5票，別的 $ho$ 值的票數均小於5票，所以得到該直線在這個8*8的像素坐標中的極坐標方程為 $frac{9sqrt{2}}{2}=xcosfrac{pi}{4}+ysinfrac{pi}{4}$ ，到此該直線方程就求出來了。