1圓與橢圓偵測2內(nèi)容1.1前言1.2隨機式測圓法1.3隨機式橢圓測法1.4查表式的圓和橢圓測法1.5視訊場景的變化偵測1.2.1基本想法1.2.3決定真正圓1.2.2決定候選圓1.2.4演算流程圖1.3.1橢心的決定1.3.3決定候選橢圓1.3.5演算流程圖1.3.2決定剩余的三個變量1.3.4決定真正橢圓31.2隨機式測圓法

范例1：哈克轉(zhuǎn)換可否應(yīng)用于圓偵測上？缺點為何？解答：這里給同學(xué)們討論一下。41.2.1基本想法圖1.2.1.1

四點決定四個圓隨機的從V中挑出四點。該四點可以決定出四個可能圓，如圖1.2.1.1所示。邊點集。我們用下列方程式來表示圓

(1.2.1.1)51.2.2決定候選圓圓方程式改寫，可得下式(1.2.2.1)此處。令,i=1,2,3，為影像邊點集中被隨機挑選出來的三個邊點。假若、和沒有共線，則他們可以決定一圓，且可以得到圓心和半徑。解圓心和半徑、和代入式子(1.2.2.1)此處。

6

(1.2.2.2)

得圓心解為(1.2.2.3)

進(jìn)而解得圓半徑(1.2.2.4)7圖1.2.2.1

數(shù)位圖圖1.2.2.2

四個抽樣邊點在一圓若距離值夠小，則在圓的邊界上(見圖1.2.2.2)。、和共線時若所選定的三個邊點不幸滿足等式(x2-x1)(y3-y1)-(x3-x1)(y2-y1)=0，則意謂被隨機挑選的三個邊點、和為共線。至圓C123的距離為(1.2.2.5)8給四個隨機邊點,i=1,2,3,4，這四個邊點至多造成四個圓。其中由、和造成的圓表為且其圓心與半徑表示為給四個點，共有個可能的圓需進(jìn)一步檢查來決定誰是候選圓。(1.2.2.6)和。令到圓的距離為不理想的情形這種不理想的情形是發(fā)生在三個代理點中有二點很接近。我們希望任二個代理點之間的距離得超過一個門檻值。圖1.2.2.3不理想的情形9范例1：給定3個邊點V1(5,0)、V2(3,6)、V3(6,10)，在進(jìn)行隨機

式測圓法來決定可能圓的過程中：

(1)請判斷此3個邊點是否可以形成一個可能圓。

(2)請求出此可能圓的圓心與半徑，并詳述其計算過程。解答：pp.215-217.101.2.3決定真正圓接下來我們加上一個門檻值來檢查這個候選圓是否為真正圓。令計數(shù)器C的起始值為0。我們從邊點集V中挑選任何一邊點，然后檢測距離是否小于門檻值。若是，則C加1。然后，我們從剩余的邊點集中再挑一邊點，繼續(xù)上述的步驟一直到所有的邊點被處理完。若C>，則候選圓即為真正圓。否則，該候選圓為一假圓。補充談一下如何制定C的門檻值。需大于一個門檻值，例如

表示數(shù)位圓上的邊點需占圓周的80%。

vi、vj和vk決定了一個候選圓。111.2.4演算流程圖圖1.2.4.1

演算流程圖(a)錢幣影像

(b)餅干和巧克力棒影像

(c)文具影像

(d)渠洞影像

圖1.2.4.2四張待測影像12(a)錢幣影像的邊點圖

(b)餅干和巧克力棒影像的邊點圖

(c)文具影像的邊點圖

(d)渠洞影像的邊點圖

圖1.2.4.3圖1.2.4.2的邊點圖

13(a)測得的圓形錢幣

(b)測得的圓形餅干

(c)測得的圓形文具

(d)測得的圓形渠洞

圖1.2.4.4測得的各種圓

14(a)p=0.5(b)p=0.25(a)p=0.5(b)p=0.25圖1.2.5.1對兩個不同p值，fRCD(x)和fRHT(x)的比較圖1.2.5.2對兩個不同p值，F(xiàn)RCD(x)和FRHT(x)的比較151.3隨機式橢圓測法

1.3.1橢心的決定、和。令橢圓的旋轉(zhuǎn)角度為且兩個軸的長度分別為a和b。則式(1.3.1.1)中的五個變量可轉(zhuǎn)換為且滿足下列三式一個橢圓可以下式表示(1.3.1.1)式(1.3.1.1)中，代表橢心，而另外三個變量為d、e和f，且滿足16和且假設(shè)的切線斜率和的切線斜率不為平行。如此一來，通過和的二條切線會交于一點，且令所交的點為。另外我們令為線段的中點，則可得下列解令為一個橢圓上的四個邊點。在邊點上的斜率設(shè)為。在這四個邊點中挑選任意二個邊點，令這二個邊點為(1.3.1.2)從和之間，存在一個很重要的幾何性質(zhì)，即連接和的直線會通過橢心。這條直線可表示為(1.3.1.3)17接著來討論另外二個剩余的邊點。令這二個剩余的邊點為和且在挑選它們時己確保它們的切線不為平行。利用式子(1.3.1.2)，我們也可得和。如圖1.3.1.1所示，和形成的直線也是通過橢心。(1.3.1.4)利用式子(1.3.1.3)和式子(1.3.1.4)的二個聯(lián)立方程式可解出橢心為隨機選四個邊點，、、和，所以共有三種組合方式、和

可以幫助我們求得三個可能的橢心。圖1.3.1.1橢圓的中心181.3.2決定剩余的三個變量假設(shè)橢圓的橢心為，原點移至橢心上。如此一來，式子(1.3.1.1)的橢圓方程式可簡化為利用挑選出來的四個邊點中的三個邊點即可解出這三個變量。將邊點代入上面式子中可得下列線性系統(tǒng)這里需注意的是為邊點經(jīng)過平移后的坐標(biāo)。從組合的觀點，共可解出四組解。191.3.3決定候選橢圓針對解出的四組，我們進(jìn)一步檢查其是否滿足、和。若是，則對應(yīng)的橢圓為一合法的可能橢圓。若某一組系數(shù)代表一合法的可能橢圓，則該橢圓可否被選為橢圓候選人，得接著對一開始選出的四個邊點進(jìn)行投票的動作。

四個邊點與橢圓的距離皆小于門檻值，我們就說這可能橢圓為一候選橢圓。這里的邊點與橢圓的距離計算公式如下(1.3.3.1)201.3.4決定真正橢圓圖1.3.4.1橢圓周長的估計決定完候選橢圓后，接著得檢查影像中的所有邊點中，到底有多少邊點是屬于橢圓候選上的邊點。如果有足夠的邊點屬于該候選橢圓，則該候選橢圓為真正的橢圓。令橢圓的長軸為2a，而短軸為2b，則外接的長方形之周長為4a+4b而內(nèi)接的菱形之周長為。橢圓的周長可估計為外接長方形周長加上內(nèi)接菱形周長的一半，即。橢圓的周長211.3.5演算流程圖圖1.3.5.1演算流程圖圖1.3.5.2內(nèi)含4顆雞蛋的影像圖1.3.5.3測邊后的結(jié)果圖1.3.5.4偵測到的橢圓1.4查表式的圓和橢圓測法利用查表式(LookupTable)的技巧[5,17]來加快前面兩節(jié)所介紹的隨機式測圓與測橢圓法。假設(shè)我們已經(jīng)找到了候選圓。令候選圓的圓心為(a,b)而半徑為r。先產(chǎn)生一個足夠大的二維陣列。然后植基在Bresenham[20]的畫圓技巧上，我們在二維陣列上畫出一帶狀圓。有了二維陣列上的帶狀圓后，將邊點集上的邊點位置映射到陣列上，若其掉在帶狀圓上，則該邊點貢獻(xiàn)了一票。依此方式，將邊點一一映射到二維陣列上，當(dāng)發(fā)現(xiàn)貢獻(xiàn)的票數(shù)超過門檻值，就找到真正的圓了。22231.5視訊場景的變化偵測Hausdorff對任一張影像而言，一旦找出影像中的各種形狀，例如有直線、圓和橢圓。我們接著求出任二種形狀的所有交點以為影像的代表點集。假設(shè)某影像的代表點集為而下一張影像的代表點集為，A和B的距離被下列的Hausdorff式子所決定

這里。部份Hausdorff部分Hausdorff距離度量定義為我們選定而；是選第k大的而非中的最