2.6　形狀檢測

除邊緣、角點外，基本的幾何形狀在計算機視覺中也是重要的監測對象。常見的包括直線、直線段、圓和橢圓等具有解析表達式的形狀的檢測。

2.6.1　標準Hough變換及圓形Hough變換

實際上，這些幾何形狀的檢測往往在先前獲得的邊緣圖像上進行，而由于在邊緣檢測中，噪聲往往會使檢測出來的邊緣不連續，因此出現了幾何形狀，但是形狀不連續。如何將這些具有標準幾何形狀的邊緣點連接成標準的形狀呢？如果通過對邊緣點進行投票來確定哪些點是幾何形狀上的點，那么實現起來并不簡單，故目前標準的做法是通過Hough變換來解決這個問題。

Hough變換最簡單的情況就是檢測直線。一般直線可以用下面的解析表達式表示

其中，參數a和b分別表示斜率和截距，兩個參數共同確定一條直線，所有參數的集合（a,b）形成一個參數空間。注意，原方程既表示（x,y）平面的一條直線，又表示（a,b）平面內的一個點，形成了對偶關系，若（x,y）平面內有共線l的兩點（x1,y1）和（x2,y2），則在參數空間中有兩條相交的直線l1和l1，且其交點表示原直線的參數（al,bl）。但對于垂直線的表示則存在問題，即垂直線的表達式為x=c，這條直線無法用上面的方程表達。因此將參數空間采用極坐標來表示

其中，ρ表示原點到直線的距離，實際上就是原點到直線上最近點的距離，角度θ表示這條過原點與直線垂直的線與橫軸的夾角。注意，一對（ρ,θ）就與一條直線相關聯，這時（ρ,θ）形成參數空間，此時（a,b）平面內的一條直線就變換成（ρ,θ）平面內的一條曲線。

從圖2.30可以看出，若任意給定圖像平面直線上的一個點（x,y）則可以計算出相應的（ρ,θ），同一條直線上的所有點（x,y）所對應的（ρ,θ）都一樣，因此我們可以根據這種性質來設計和檢測直線的算法。

首先對原始圖像進行邊緣檢測，然后設計一個稱為累計器的二維陣列，分別表示（ρ,θ）的離散空間，一般可以設置ρ為圖像的寬度與高度的最大值，角度θ的取值范圍為（0,360°）。對圖像的每個邊緣像素點（xi,yi）和變化θ的值，求出對應的ρ值，然后在（ρ,θ）對應的二維矩陣中的對應位置加1。顯然，即使邊緣不連續，但只要在同一條直線上，對應的（ρ,θ）也會增加，從而通過對累計器求其局部極值來檢測對應的直線。累計器中有多少個極值，就存在多少條直線。

同樣，Hough變換也可以用來檢測其他更復雜的形狀對象，尤其是具有解析表達式的形狀，此時稱為廣義Hough變換。例如，圓有對應的圓形Hough變換，此時包含圓心坐標和半徑三個參數，可以表示為以點（a,b）為圓心，以r為半徑，表達式為

其基本思想為：若以該圓上的任意一點為圓心，以r為半徑畫圓，則該圓必定經過圓心（a,b）。因此，圖像中存在半徑為r的圓，但經過邊緣檢測后，若其邊界不連續，則這時以每個邊緣像素為圓心畫半徑為r的圓，這些圓的交點必定是原圓的圓心，從而確定了原圓的圓心。

圖2.31表示了圓心為O、半徑為r的圓，邊界上出現三個像素點（x1,y1）、（x2,y2）、（x3,y3），若以這些點為圓心，畫半徑為r的圓，則這些圓必在圓心O相交。在圖像經過邊緣檢測后，在已知圓半徑r的情況下，對每個像素做半徑為r的圓，這與直線檢測中的二維累計陣列類似，即對該圓通過的位置的值加1，故二維陣列中的局部極大值點就對應半徑為r的圓的圓心。

而若在半徑未知的情況下，則需要進一步假定半徑的范圍。在限定范圍內，對所有可能的半徑值進行遍歷，然后設定閾值，對所有這些累計陣列取其局部極大值點，這樣可檢測出圖像中的所有圓。

顯然，半徑的范圍對算法性能的影響巨大，這時需要存儲所有的累計矩陣的值，還可以通過選定網格的大小來減少計算量，但由于圓形物體的尺寸未知，因此可能會省略比網格尺寸還小的圓形。

在計算機視覺領域中，可以利用圓形的一些先驗性質來減少計算量。例如，在航天器上利用標靶來對接，這時需要通過檢測標靶來計算偏移量，進而對齊接口，若標靶上的目標是圓形，且預先知道尺寸，則可以利用這些信息來減少計算量。其次，處于圓上的邊緣像素點具有類似的曲率信息，這時可以利用曲率信息來減少要計算的邊緣像素點。例如，假設已經計算出邊緣圖以及相應的Ix,Iy,Ixx,Iyy,Ixy，則可以計算出局部方向和曲率k

然后統計曲率直方圖，找出峰值對應的邊緣點而舍棄其余的邊緣點，這樣就減少了計算量，從而加快了檢測過程。

2.6.2　廣義Hough變換

1981年，Ballard首先引入了廣義Hough變換。通過模板匹配的方式使Hough不僅可以處理有解析式的形狀，而且可以檢測用模型描述的任意形狀的對象。

首先對任意需要檢測的形狀通過建立R表來表示，選定待檢測對象內部的一個點作為參考點（xr,yr）。然后對于任意邊界點（xi,yi），連接參考點與邊界點的距離用ri表示。在邊界點處連接線與水平軸的夾角為αi，切線方向與水平軸夾角為φi。此時模板形狀由邊界點到參考點的距離，以及邊界點的梯度方向完全確定。R表如表2.1所示，注意，表格第二列為參數的離散化形式，第三列中的每項對應一個邊緣像素點。廣義Hough變換原理如圖2.32所示。

在進行對象檢測時，同樣使用稱為二維累計陣列的Hough計數空間或者參數空間，邊緣點根據其梯度方向和R表值在這個空間中對假設的參考點進行投票。圖像中的對象等同于模板對象，則累計陣列中對應這個參考點的位置的元素值會獲得最高投票數。理想上，其峰值就表示這個對象邊界點的數目。

一旦要求形狀檢測具有旋轉和尺度的不變性，這時就需要增加旋轉和尺度兩個參數，并相應地進行離散化，這里不再詳細描述。請參考相關文獻。

2.6.3　三種常見Hough變換的區別

目前，常見的Hough變換分為三種，分別是標準的Hough變換（SHT）、廣義的Hough變換（GHT）和隨機的Hough變換（RHT）。SHT和GHT顯然都是一對多的映射，即每個邊緣像素點對參數空間矩陣的很多位置都有貢獻。但RHT變換從邊緣像素的子集來進行處理，每次隨機選取都對應同一個形狀，這時是多對一的映射，如兩個隨機選取的像素可以定義一條直線。對于有n個參數的曲線形狀，隨機選取n個點來計算該曲線的n個參數。同時維持包括一個實值向量和整數投票值的動態累計矩陣。對于計算得到的參數集合，若在一定誤差情況下匹配一個已有集合，則其投票值加一；否則新的參數集合計數值加一。最終從累計矩陣中根據閾值選取候選的曲線形狀，由于在參數空間不進行離散化，因此可以獲得高分辨率的效果。

從可處理的圖像類型來看，三種變換都可以處理二值圖像，但只有GHT可以處理灰度圖像。

從檢測的目標來看，三種變換都可以檢測圓和參數型形狀，但SHT和RHT不能檢測任意形狀的目標而GHT可以。并且SHT和RHT可以檢測直線，而GHT不能檢測直線。

從檢測速度來看，RHT最快速，SHT和GHT都比較慢；從存儲要求來看，RHT要求少量存儲，而SHT和GHT對存儲量的要求比較大；從檢測精度來看，RHT的精度比較高，而SHT和GHT的精度適中，精度與參數空間的量化的要求有關；從參數的分辨能力來看，SHT和GHT都需要對參數進行離散化，因此其參數分辨能力與參數離散化的精度有關，而RHT不需要離散參數空間，因此其精度高。