Rocky的部落格

http://www.cnblogs.com/cvart/archive/2011/07/07/2100564.html

查找圖像中橢圓輪廓的快速隨機hough變換

　　圖像中橢圓輪廓的查找在視頻監控等領域有著廣泛的應用，經典hough變換給我們提供了一種查找各種圖形輪廓的方法，特別是在直線查找方面具有非常高的精確度。但是由於經典hough變換的基本原理是將圖像空間轉換到參數空間，所以對於橢圓這種參數較多的圖形輪廓來說計算量較大，實時性有所降低。

　　隨機hough變換是經典hough變換的一個變型，這種算法在查找直線、圓以及橢圓等方法都具有較高的魯棒性。從Range的角度來看，隨機hough變換的本質就是一種基於可更新模板的模板匹配方法。下圖是一張Range基於這種方法檢測行人頭部的效果。

　　下面對隨機hough進行一個簡單的介紹：

　　隨機hough變換是經典hough變換的蓋然論變型。被廣泛應用到圓弧等圖形（線、圓、橢圓等）的檢測中。Hough變換的基本思想是對圖像上的潛在圓弧采用一種投票機制，最後算法通過檢查最高的投票分數來確定具有最高分圓弧的存在。隨機hough變換和經典hough的不同在於通過分析幾何性質避免把時間浪費在給每個非零像素投票的過程上。因此，有效地改進了處理時間並且減少了所需要的存儲空間。

產生背景

       雖然hough變換被廣泛應用到圖形檢測上，但它主要有兩點不足：(1) 對於圖像上的每個非零像素，不管是不是要查找的形狀的參數都會在投票過程中被累加；(2) 累加器數組（或者hough空間）以一種啟發方式定義。要想計算的精度越好，就需要定義越高的參數空間。這兩點往往使得系統需要較大的存儲開銷，而且影響系統的實時性。

實現

       圓弧可以完全由它上面的一定數量的點來決定，和HT比起來，RHT正是利用了這個優勢。例如，兩點決定一條直線，一個橢圓或圓可由三點確定。為了闡述RHT的思想，我們可以想象下一個橢圓的確定過程：1) 由隨機選擇的點進行橢圓擬合；2) 更新累加器數組以及相應的匹配度；3) 輸出那些大於預定義閾值的橢圓。

橢圓擬合

       定義橢圓的一般公式為：a(x − p)² + 2b(x − p)(y − q) + c(y − q)² + 1 = 0，約束條件：ac − b² > 0。

       但是要確定一個橢圓我們僅需要三個點。

RHT由在橢圓上隨機選擇三個點開始，設為X₁,X₂和X₃。第一步是找到這三個點處的切線，可以通過對其相鄰像素的一個小窗口進行最小二乘擬合一條直線來找到該點處的切線；

第二步是要找出這些切線的交叉點，這點很容易做到。設交叉點為T12和T23，設兩條線段X₁X₂以及X₂X₃的中點分別是M₁₂和M₂₃。然後橢圓的中心就是T₁₂M₁₂和T₂₃M₂₃的交點。

假設上步求出的橢圓中心坐標為(X₀,Y₀)，設x』=x-x₀，y』=y-y₀，那麼橢圓方程為：

ax'² + 2bx'y' + cy'² = 1。現在，我們可以通過帶入X₁,X₂和X₃的坐標來解方程求出參數a、b和c。

累加

       橢圓參數被計算出來後，累加器數組就可以相應的更新了。和經典的hough變換不同，RHT沒有維護一個"grid of buckets"作為累加器數組。它首先計算新檢測到得橢圓和已保存在累加器數組中的橢圓的相似度。可以采用不同計算標准來計算相似度。一旦相似度超出了預定義的門限值，就用這兩個橢圓的平均來替換掉累加器數組中的橢圓，同時將它的score加1。.

終止

       一旦某個候選橢圓的score超過了門限值，這個橢圓就是一個被檢測出的橢圓。將其從圖像和累加器數組中刪除，以便該算法更快的找到其他橢圓。當算法循環數目達到最大值或者所有橢圓都被檢測出時，算法停止。

偽代碼

while (we find ellipses OR not reached the maximum epoch) {

    for(a fixed number of iterations) {

        Find a potential ellipse.

        if(the ellipse is similar to an ellipse in the accumulator)

            Replace the one in the accumulator with the average of two ellipses and add 1 to the score;

        else

            Insert the ellipse into an empty position in the accumulator with a score of 1;

    }

    Select the ellipse with the best score and save it in a best ellipse table;

    Elliminate the pixels of the best ellipse from the image;

    Empty the accumulator;

}

　　隨機hough和經典的hough有些不同，如果你不了解經典hough可以參考下《hough變換原理》一文，這裡不再贅述。

相關參考

1.http://blog.csdn.net/icerain_3321/article/details/1665280

2. D.H. Ballard, "Generalizing the Hough Transform to Detect Arbitrary Shapes", Pattern Recognition, Vol.13, No.2, p.111-122, 1981

3. L. Xu, E. Oja, and P. Kultanan, "A new curve detection method: Randomized Hough transform (RHT)", Pattern Recog. Lett. 11, 1990, 331-338.

4. S. Inverso, 「Ellipse Detection Using Randomized Hough Transform」, www.saminverso.com/res/vision/EllipseDetectionOld.pdf, May 20, 2002