霍夫轉換

霍夫轉換（Hough transform）藉由讓邊緣點為它們可能所屬的形狀投票，再找出獲得許多票的形狀，來偵測形狀——直線、圓、橢圓或任意模板。其直覺把慣常的問題反過來。它不是對每條候選直線問「哪些邊緣像素落在它上面」（既慢、又得試遍每條線），而是對每個邊緣像素問「有哪些直線可能通過它」，並讓它為所有這些線投一票。影像中真正的直線，是許多邊緣像素各自獨立投票的那一條，因此它會在計票中顯現為一個明亮的尖峰。

以直線精確化之，每條直線用兩個參數描述；穩健的選擇是它到原點的垂直距離（rho）與該垂線的角度（theta），這可避開垂直線的無限斜率。位於 (x,y) 的單一邊緣像素與一整族直線相容——也就是所有滿足 rho = x·cos(theta) + y·sin(theta) 的 (rho, theta) 對——這在 rho–theta 參數空間（稱為累加器，accumulator）中描出一條正弦曲線。每個邊緣像素為其正弦曲線沿線的每個累加器格子加一。許多正弦曲線交會之處，對應的 (rho, theta) 格子累積到許多票，標示出一條許多像素都認同的直線。你藉由在累加器中找出高於票數門檻的局部極大值來偵測直線。圓以三參數累加器（圓心 x、圓心 y、半徑）以同樣方式運作，而廣義霍夫轉換（generalized Hough transform）則為儲存在查找表中的任意形狀的參考點投票。

霍夫轉換最大的長處是穩健性：由於偵測是全域投票，它能容忍直線的斷裂（遮擋）、雜訊與離群點——一條部分被遮的直線只要露出夠多仍能勝出，而零散的邊緣像素只是撒下無害的票。它的代價是維度詛咒（累加器隨形狀參數數量呈指數成長，因此對直線與圓可行，超過則昂貴）以及對格子解析度與門檻的敏感。它至今仍是偵測人造結構的常備工具——駕駛輔助中的車道線、文件與表格邊框、工業對位、用於瞳孔與硬幣的圓霍夫——而其核心想法「在參數空間中以投票累積證據」也再現於廣義霍夫匹配、隱式形狀模型（implicit shape model），以及某些現代 3D 與姿態網路所用的霍夫投票頭。