資源描述：
《以一般化視角串聯(lián)霍夫變換(houghtransform),從直線到圓再到廣義霍夫變換.doc》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。
1、計(jì)算機(jī)視覺中經(jīng)常需要識別或者定位某些幾何圖形，比如直線、圓、橢圓，還有其他一些圖形。檢測直線的霍夫變換提供了在圖像中尋找直線的一種算法，是最簡單的一種情形，后來發(fā)展到檢測圓、橢圓、還有一般圖形的霍夫變換，其核心思想是把圖像中屬于某種圖形的點(diǎn)集（二維）映射到一個點(diǎn)（可以是高維）上，這個點(diǎn)記錄了點(diǎn)集中點(diǎn)的數(shù)目，使得程序通過搜索峰值找到該點(diǎn)，這個點(diǎn)就是后面要說到的圖形的參數(shù)，而該參數(shù)的范圍就叫做參數(shù)空間。霍夫變換不僅能夠識別出圖像中有無需要檢測的圖形，而且能夠定位到該圖像（包括位置、角度等），這就非常有用了。接下來將通
2、過分析從簡單到復(fù)雜的霍夫變換，導(dǎo)出霍夫變換的實(shí)質(zhì)。???????直線：檢測直線的霍夫變換使用含極坐標(biāo)參數(shù)的直線表示型式簡稱極坐標(biāo)式（不是極坐標(biāo)方程，因?yàn)檫€是在笛卡爾坐標(biāo)下表示）——?其中的兩個參數(shù)的意義如下圖：為什么要用極坐標(biāo)式而不直接用一般形式：ax+by=c（歸一化可以去掉參數(shù)c），或者其他的如斜截式、截距式呢？首先它們都會遇到奇異情況，比如c=0，斜率=無窮大，其中一個截距=0；再一個是某些形式的參數(shù)空間不是閉的，比如斜截式的斜率k，取值范圍從0到無窮大，給量化搜索帶來了困難。而極坐標(biāo)式就妙在距離和角度兩個
3、參數(shù)都是有界的，而且正余弦函數(shù)也有界不會發(fā)生奇異情況。??????直線霍夫變換有兩個參數(shù)，且這兩個參數(shù)通過極坐標(biāo)式相關(guān)聯(lián)，所以程序在投票階段（圖形點(diǎn)集轉(zhuǎn)換到一個點(diǎn)）只需要遍歷其中一個，搜索峰值在二維參數(shù)空間進(jìn)行。???????圓：霍夫變換檢測圓使用圓的標(biāo)準(zhǔn)式就可以了——我們發(fā)現(xiàn)圓的方程又比直線多了一個參數(shù)，這三個參數(shù)通過上面的方程相關(guān)聯(lián)，因此在投票階段需要遍歷其中兩個，搜索峰值在三維參數(shù)空間進(jìn)行。如果圖像比較大，那么這樣的遍歷搜索是相當(dāng)耗時的，所以為了滿足實(shí)時性后來又發(fā)展出其他檢測圓的霍夫變換，比如概率霍夫變換，
4、結(jié)合梯度信息的霍夫變換。????????????霍夫變換檢測橢圓如果使用橢圓的標(biāo)準(zhǔn)式，那么將會有五個參數(shù)，它們通過標(biāo)準(zhǔn)式相關(guān)，檢測圓就已經(jīng)相當(dāng)耗時了，如果再用這中方程形式處理勢必失去實(shí)際用途。???????Ballard(1981)一般化了霍夫變換(Hough，1962)，利用圖形梯度量加快算法速度，形成了一般霍夫變換。???????透過前面的檢測直線、圓、一般霍夫變換，已經(jīng)可以提取出霍夫變換的一個本質(zhì)——給出圖形的一個描述模式，比如圖形點(diǎn)集的方程、函數(shù)、表格等，然后利用這個模式加上遍歷參數(shù)空間，把屬于該模式的圖
5、形點(diǎn)集投射到參數(shù)空間的一個點(diǎn)（實(shí)際的離散情況一般不會完美的集中到一點(diǎn)），這個點(diǎn)記錄的是圖形點(diǎn)數(shù)目。??????一般霍夫變換之所以能處理任意形狀的圖形并不是找到了可以表示任意圖形的方程（這是不可能的），而是使用表的形式描述一種圖形，把圖形邊緣點(diǎn)坐標(biāo)保存在一張表中，那么該圖形就確定下來了，所以其實(shí)無論是直線（其實(shí)是線段）、圓、橢圓還是其他形狀的幾何圖形，都可以使用同一方法處理，所不同的是這時候的圖形是自定義的，是實(shí)在的，而代數(shù)方程表示的模式是連續(xù)的、抽象的，圓的方程只有一種，但自定義的圓卻是無窮的，只要你認(rèn)為它足夠圓
6、了就可以。當(dāng)然兩種表示都會有各自的優(yōu)勢和局限。有了表之后就需要找到一種可以把圖形點(diǎn)集投射到參數(shù)空間的一點(diǎn)的轉(zhuǎn)換算法，例如直線和圓霍夫變換通過方程（函數(shù)）及遍歷把點(diǎn)集進(jìn)行投射，使得屬于某直線或圓的點(diǎn)集中到一個點(diǎn)；那么僅有一張描述圖形邊緣坐標(biāo)點(diǎn)的表如何進(jìn)行投射呢？我們可以把這張表看作是模板，進(jìn)行模板匹配，大部分的點(diǎn)匹配成功也就可以理解為這些點(diǎn)都投射到一個點(diǎn)上，不過這時候不需要再搜索參數(shù)空間峰值了，這種模式可以認(rèn)為是參數(shù)間沒有任何關(guān)聯(lián)，所以是完全的遍歷。但有旋轉(zhuǎn)加上縮放的情況模板匹配型的霍夫變換是十分耗時的，也可以想象
7、成因?yàn)閰?shù)不相關(guān)所以增加遍歷搜索時間。Ballard(1981)的一般霍夫變換最精妙之處在于為參數(shù)增加了兩個關(guān)聯(lián)，使得有平移和旋轉(zhuǎn)（無縮放）的情況只需要遍歷一個參數(shù)，三個參數(shù)分別是圖形的中心坐標(biāo)（橫縱），旋轉(zhuǎn)角度（相對參考圖形），Ballard的算法預(yù)先把參考圖形邊緣點(diǎn)對中心的徑向量保存起來，利用待搜索圖形邊緣點(diǎn)的梯度方向（用相對坐標(biāo)軸的角度表示）作為索引找到相應(yīng)的徑向量，加上該量后就完成了投射，所以要遍歷的參數(shù)只有旋轉(zhuǎn)角度，所以說有兩個關(guān)聯(lián)。當(dāng)然如果加上縮放就要遍歷兩個參數(shù)，這也只是和霍夫檢測圓的規(guī)模一樣而已。
8、這種一般霍夫變換的圖形表不再是直接保存坐標(biāo)，而是邊緣點(diǎn)的梯度加上徑向量，還有一個中心坐標(biāo)，給出了這些量同樣的也就能夠表示出一種圖形了。然而這種一般霍夫變換也是有缺陷的，不少后來者提出了改進(jìn)方法，這不在本文討論范圍。???????再來強(qiáng)調(diào)一次，霍夫變換就是通過圖形的一種表示模式，加上一種轉(zhuǎn)換方法，把圖形的點(diǎn)集投射到一個點(diǎn)上以便檢測。我們已經(jīng)能夠知道，參數(shù)個數(shù)越少，需要遍歷的
