Hough Transform 是一種常見用來偵測圖片中特定形狀（直線、圓）的方法；它是透過投票的方式找出最有可能的幾何形狀。
找出二維空間中的直線
一般來說我們用 \(y = ax + b\) 來描述二維空間中的直線。Hough Transform 做的事情是把原本的 \(xy\) 空間轉換成 \(ab\) 空間，並且利用投票的方式找出最有可能的 \(a\) 與 \(b\)，這樣就能偵測出這條直線了。以下我們用 \(y = x\) 當成例子，也就是 \(a = 1, b = 0\)。
為了簡化問題，我們只統計整數的情形。這個演算法的步驟是假設圖片上只有這條直線上的點 intensity 為 1，其他都為 0，而針對每個 intensity 為 1 的點我們找出所有可能的 \((a,b)\) 組合，並將此 \((a,b)\) 組合算上一票。為了再簡化問題我們讓 \(a,b\) 都為三種可能：-1、0、或 1。
當在點 \((0,0)\) 時，所有通過此點的直線為 \(y = 0, y = x, y = -x\)，因此 \((0,0), (1, 0), (-1,0)\) 各加一票。在點 \((1,1)\) 時，所有通過此點的直線為 \(y = 1, y = x\)，因此 \((0,1), (1, 0)\) 各加一票。在統計完以後發現 \((1,0)\) 的票數最高，也就是說想要偵測的直線就是 \(y=x\)。
其他的參數形式
用以上的 \((a,b)\) 參數形式無法表示垂直於 x 軸的直線，因此常見的做法是用極座標來表示這一條直線。
找出二維空間中的圓
二維空間中的圓的式子為 \((x-a)^2+(y-b)^2=r^2\)，因此參數空間為三維 \((a, b, r)\)。對於一般的圖片我們先用 canny edge detector 找出邊緣的點，再針對所有邊緣的點上投下所有經過此點之圓的一票，統計完所有的點以後就能找出圓的位置及半徑了。參考資料 [3] 有精美的影片描述整個過程。
沒有留言:
張貼留言