???計(jì)算機(jī)視覺(jué)中經(jīng)常需要識(shí)別或者定位某些幾何圖形，比如直線、圓、橢圓，還有其他一些圖形。檢測(cè)直線的霍夫變換提供了在圖像中尋找直線的一種算法，是最簡(jiǎn)單的一種情形，后來(lái)發(fā)展到檢測(cè)圓、橢圓、還有一般圖形的霍夫變換，其核心思想是把圖像中屬于某種圖形的點(diǎn)集（二維）映射到一個(gè)點(diǎn)（可以是高維）上，這個(gè)點(diǎn)記錄了點(diǎn)集中點(diǎn)的數(shù)目，使得程序通過(guò)搜索峰值找到該點(diǎn)，這個(gè)點(diǎn)就是后面要說(shuō)到的圖形的參數(shù)，而該參數(shù)的范圍就叫做參數(shù)空間。霍夫變換不僅能夠識(shí)別出圖像中有無(wú)需要檢測(cè)的圖形，而且能夠定位到該圖像（包括位置、角度等），這就非常有用了。接下來(lái)將通過(guò)分析從簡(jiǎn)單到復(fù)雜的霍夫變換，導(dǎo)出霍夫變換的實(shí)質(zhì)。

???直線：檢測(cè)直線的霍夫變換使用含極坐標(biāo)參數(shù)的直線表示型式簡(jiǎn)稱(chēng)極坐標(biāo)式（不是極坐標(biāo)方程，因?yàn)檫€是在笛卡爾坐標(biāo)下表示）——?

其中的兩個(gè)參數(shù)的意義如下圖：

?

?

為什么要用極坐標(biāo)式而不直接用一般形式：ax+by=c（歸一化可以去掉參數(shù)c），或者其他的如斜截式、截距式呢？首先它們都會(huì)遇到奇異情況，比如c=0，斜率=無(wú)窮大，其中一個(gè)截距=0；再一個(gè)是某些形式的參數(shù)空間不是閉的，比如斜截式的斜率k，取值范圍從0到無(wú)窮大，給量化搜索帶來(lái)了困難。而極坐標(biāo)式就妙在距離和角度兩個(gè)參數(shù)都是有界的，而且正余弦函數(shù)也有界不會(huì)發(fā)生奇異情況。

??????直線霍夫變換有兩個(gè)參數(shù)，且這兩個(gè)參數(shù)通過(guò)極坐標(biāo)式相關(guān)聯(lián)，所以程序在投票階段（圖形點(diǎn)集轉(zhuǎn)換到一個(gè)點(diǎn)）只需要遍歷其中一個(gè)，搜索峰值在二維參數(shù)空間進(jìn)行。

?

??????圓：霍夫變換檢測(cè)圓使用圓的標(biāo)準(zhǔn)式就可以了——

我們發(fā)現(xiàn)圓的方程又比直線多了一個(gè)參數(shù)，這三個(gè)參數(shù)通過(guò)上面的方程相關(guān)聯(lián)，因此在投票階段需要遍歷其中兩個(gè)，搜索峰值在三維參數(shù)空間進(jìn)行。如果圖像比較大，那么這樣的遍歷搜索是相當(dāng)耗時(shí)的，所以為了滿足實(shí)時(shí)性后來(lái)又發(fā)展出其他檢測(cè)圓的霍夫變換，比如概率霍夫變換，結(jié)合梯度信息的霍夫變換。

??????

??????霍夫變換檢測(cè)橢圓如果使用橢圓的標(biāo)準(zhǔn)式，那么將會(huì)有五個(gè)參數(shù)，它們通過(guò)標(biāo)準(zhǔn)式相關(guān)，檢測(cè)圓就已經(jīng)相當(dāng)耗時(shí)了，如果再用這中方程形式處理勢(shì)必失去實(shí)際用途。

?

??????Ballard (1981)一般化了霍夫變換(Hough，1962)，利用圖形梯度量加快算法速度，形成了廣義霍夫變換。

?

??????透過(guò)前面的檢測(cè)直線、圓、廣義霍夫變換，已經(jīng)可以提取出霍夫變換的一個(gè)本質(zhì)——給出圖形的一個(gè)描述模式，比如圖形點(diǎn)集的方程、函數(shù)、表格等，然后利用這個(gè)模式加上遍歷參數(shù)空間，把屬于該模式的圖形點(diǎn)集投射到參數(shù)空間的一個(gè)點(diǎn)（實(shí)際的離散情況一般不會(huì)完美的集中到一點(diǎn)），這個(gè)點(diǎn)記錄的是圖形點(diǎn)數(shù)目。

??????廣義霍夫變換之所以能處理任意形狀的圖形并不是找到了可以表示任意圖形的方程（這是不可能的），而是使用表的形式描述一種圖形，把圖形邊緣點(diǎn)坐標(biāo)保存在一張表中，那么該圖形就確定下來(lái)了，所以其實(shí)無(wú)論是直線（其實(shí)是線段）、圓、橢圓還是其他形狀的幾何圖形，都可以使用同一方法處理，所不同的是這時(shí)候的圖形是自定義的，是實(shí)在的，而代數(shù)方程表示的模式是連續(xù)的、抽象的，圓的方程只有一種，但自定義的圓卻是無(wú)窮的，只要你認(rèn)為它足夠圓了就可以。當(dāng)然兩種表示都會(huì)有各自的優(yōu)勢(shì)和局限。有了表之后就需要找到一種可以把圖形點(diǎn)集投射到參數(shù)空間的一點(diǎn)的轉(zhuǎn)換算法，例如直線和圓霍夫變換通過(guò)方程（函數(shù)）及遍歷把點(diǎn)集進(jìn)行投射，使得屬于某直線或圓的點(diǎn)集中到一個(gè)點(diǎn)；那么僅有一張描述圖形邊緣坐標(biāo)點(diǎn)的表如何進(jìn)行投射呢？我們可以把這張表看作是模板，進(jìn)行模板匹配，大部分的點(diǎn)匹配成功也就可以理解為這些點(diǎn)都投射到一個(gè)點(diǎn)上，不過(guò)這時(shí)候不需要再搜索參數(shù)空間峰值了，這種模式可以認(rèn)為是參數(shù)間沒(méi)有任何關(guān)聯(lián)，所以是完全的遍歷。但有旋轉(zhuǎn)加上縮放的情況模板匹配型的霍夫變換是十分耗時(shí)的，也可以想象成因?yàn)閰?shù)不相關(guān)所以增加遍歷搜索時(shí)間。Ballard (1981)的廣義霍夫變換最精妙之處在于為參數(shù)增加了兩個(gè)關(guān)聯(lián)，使得有平移和旋轉(zhuǎn)（無(wú)縮放）的情況只需要遍歷一個(gè)參數(shù)，三個(gè)參數(shù)分別是圖形的中心坐標(biāo)（橫縱），旋轉(zhuǎn)角度（相對(duì)參考圖形），Ballard的算法預(yù)先把參考圖形邊緣點(diǎn)對(duì)中心的徑向量保存起來(lái)，利用待搜索圖形邊緣點(diǎn)的梯度方向（用相對(duì)坐標(biāo)軸的角度表示）作為索引找到相應(yīng)的徑向量，加上該量后就完成了投射，所以要遍歷的參數(shù)只有旋轉(zhuǎn)角度，所以說(shuō)有兩個(gè)關(guān)聯(lián)。當(dāng)然如果加上縮放就要遍歷兩個(gè)參數(shù)，這也只是和霍夫檢測(cè)圓的規(guī)模一樣而已。這種廣義霍夫變換的圖形表不再是直接保存坐標(biāo)，而是邊緣點(diǎn)的梯度加上徑向量，給出了這些量同樣的也就能夠表示出一種圖形了。然而這種廣義霍夫變換也是有缺陷的，不少后來(lái)者提出了改進(jìn)方法，這不在本文討論范圍。

?????再來(lái)強(qiáng)調(diào)一次，霍夫變換就是通過(guò)圖形的一種表示模式，加上一種轉(zhuǎn)換方法，把圖形的點(diǎn)集投射到一個(gè)點(diǎn)上以便檢測(cè)。我們已經(jīng)能夠知道，參數(shù)個(gè)數(shù)越少，需要遍歷的參數(shù)個(gè)數(shù)約少（關(guān)聯(lián)越多），參數(shù)空間越小則處理速度越快。所以設(shè)計(jì)一種合理的轉(zhuǎn)換方法非常關(guān)鍵。

??????對(duì)于一種圖形，在現(xiàn)實(shí)世界中可以有多種形變，線性的如：平移、旋轉(zhuǎn)、透視；非線性的如：徑變、切變、扭曲。每多考慮一種形變都會(huì)增加參數(shù)，比如把橢圓看作是圓的透視形變，結(jié)果多了兩個(gè)參數(shù)，理論上可以去遍歷每一個(gè)參數(shù)空間，但這不能滿足實(shí)時(shí)性要求，所以參數(shù)之間約束（關(guān)聯(lián)）越多則處理速度越快，Ballard的廣義霍夫變換就是例子，這就需要發(fā)揮主觀創(chuàng)造力了。

總結(jié)

以上是生活随笔為你收集整理的霍夫变换(hough transform)原理的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。