圓與橢圓偵測(cè)

第六章

圓與橢圓偵測(cè)16.1前言6.2隨機(jī)式測(cè)圓法

6.3隨機(jī)式橢圓測(cè)法6.5視訊場(chǎng)景的變化偵測(cè)6.6作業(yè)6.2.1基本想法6.2.3決定真正圓6.2.2決定候選圓6.2.4演算流程圖6.3.1橢心的決定6.3.3決定候選橢圓6.3.5演算流程圖6.3.2決定剩餘的三個(gè)變數(shù)6.3.4決定真正橢圓26.2隨機(jī)式測(cè)圓法

Q1：哈克轉(zhuǎn)換可否應(yīng)用於圓偵測(cè)上？缺點(diǎn)為何？ANS：pp.204-205。36.2.1基本想法圖6.2.2.1四點(diǎn)決定四個(gè)圓假設(shè)給定的邊點(diǎn)集合為V，我們隨機(jī)的從V中挑出四點(diǎn)。該四點(diǎn)可以決定出四個(gè)圓，如圖6.2.1.1所示。假設(shè)被選出的四個(gè)點(diǎn)皆來(lái)自同一個(gè)圓，則我們可說(shuō)這四點(diǎn)決定出的圓是候選圓。我們已從該影像中求得邊點(diǎn)的集合。我們通常用下列方程式來(lái)表示圓

(6.2.1.1)4Q1：給定3個(gè)邊點(diǎn)V1(5,0)、V2(3,6)、V3(6,10)，在進(jìn)行隨機(jī)式測(cè)圓法來(lái)決定可能圓的過(guò)程中：(1)請(qǐng)判斷此3個(gè)邊點(diǎn)是否可以形成一個(gè)可能圓。(2)請(qǐng)求出此可能圓的圓心與半徑，並詳述其計(jì)算過(guò)程。5ANS：pp.206-207.

66.2.2決定候選圓將式子(6.2.1.1)中的圓方程式改寫(xiě)，可得下式(6.2.2.1)此處。令,i=1,2,3，為影像中邊點(diǎn)集中被隨機(jī)挑選出來(lái)的三個(gè)邊點(diǎn)。假若、和沒(méi)有共線，則他們可以決定一圓，且可以得到圓心和半徑。解圓心和半徑將三個(gè)邊點(diǎn)、和代入式子(6.2.2.1)我們可得此處。7(6.2.2.2)從式(6.2.2.2)和利用克拉瑪公式，我們得圓心的解為(6.2.2.3)利用圓心的解，我們進(jìn)而解得圓半徑如下(6.2.2.4)8、和共線時(shí)若所選定的三個(gè)邊點(diǎn)不幸滿足等式(x2-x1)(y3-y1)-(x3-x1)(y2-y1)=0，則意謂被隨機(jī)挑選的三個(gè)邊點(diǎn)、和為共線。也就是說(shuō)他們無(wú)法形成一個(gè)圓。令為第四個(gè)被挑選的邊點(diǎn)，令該點(diǎn)至圓C123的距離為且(6.2.2.5)假如在圓上，則式(6.2.2.5)為零。圖6.2.2.1數(shù)位圖圖6.2.2.2四個(gè)抽樣邊點(diǎn)在一圓若式(6.2.2.5)中值夠小，則我們都視在圓的邊界上(見(jiàn)圖6.2.2.2)。9給四個(gè)隨機(jī)邊點(diǎn),i=1,2,3,4，這四個(gè)邊點(diǎn)至多造成四個(gè)圓。其中由、和造成的圓表為且其圓心與半徑表示為這裡我們主要的目標(biāo)是從四個(gè)隨機(jī)選取的邊點(diǎn)中決定哪三點(diǎn)可形成一數(shù)位圓。同時(shí)第四個(gè)邊點(diǎn)也落在該圓的邊上。給四個(gè)點(diǎn)，共有個(gè)可能圓需進(jìn)一步檢查來(lái)決定誰(shuí)是最可能的圓。(6.2.2.6)和。令到圓的距離為(參見(jiàn)式子(6.2.2.3)-(6.2.2.5))。例如式子(6.2.2.5)可被改為不理想的情形這種不理想的情形是發(fā)生在三個(gè)代理點(diǎn)中有二點(diǎn)很接近。如此一來(lái)，這個(gè)可能圓有很高的機(jī)率不為一真正圓。為了避免這種不理想的情形，我們希望任二個(gè)代理點(diǎn)之間的距離得超過(guò)一個(gè)門(mén)檻值。加上這個(gè)條件會(huì)讓由三個(gè)代理點(diǎn)決定的候選圓有更強(qiáng)的證據(jù)為真正圓。圖6.2.2.3不理想的情形106.2.3決定真正圓和半徑。接下來(lái)我們加上一個(gè)門(mén)檻值來(lái)檢查這個(gè)候選圓是否為真正圓。令計(jì)數(shù)器C的起始值為0。我們從邊點(diǎn)集V中挑選任何一邊點(diǎn)，然後檢測(cè)距離是否小於門(mén)檻值。若是，則將C的值加一。然後，我們從剩餘的邊點(diǎn)集中再挑一邊點(diǎn)，繼續(xù)上述的距離計(jì)算和比較，一直到所有的邊點(diǎn)被處理完。若這時(shí)C的值大於門(mén)檻值，則由vi、vj和vk形成的候選圓即為真正圓。否則，該候選圓為一假圓。接下來(lái)，我們?cè)賹⑦@C個(gè)邊點(diǎn)還回邊點(diǎn)集V。最後我們補(bǔ)充談一下如何制定C的門(mén)檻值。假設(shè)該候選圓的圓心與半徑為和，則需大於一個(gè)門(mén)檻值，例如

表示數(shù)位圓上的邊點(diǎn)需佔(zhàn)圓周的。畢竟圓周上的點(diǎn)數(shù)與半徑是成正比的。這樣設(shè)的門(mén)檻值較不受圓的大小之影響。假設(shè)利用上面方法，vi、vj和vk決定了一個(gè)可能圓且此圓有圓心116.2.4演算流程圖圖6.2.4.1演算流程圖(a)錢(qián)幣影像

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

(c)文具影像

(d)渠洞影像

圖6.2.4.2四張待測(cè)影像12(a)錢(qián)幣影像的邊點(diǎn)圖

(b)餅乾和巧克力棒影像的邊點(diǎn)圖

(c)文具影像的邊點(diǎn)圖

(d)渠洞影像的邊點(diǎn)圖

圖6.2.4.3圖6.2.4.2的邊點(diǎn)圖

13(a)測(cè)得的圓形錢(qián)幣

(b)測(cè)得的圓形餅乾

(c)測(cè)得的圓形文具

(d)測(cè)得的圓形渠洞

圖6.2.4.4測(cè)得的各種圓

14(a)p=0.5(b)p=0.25(a)p=0.5(b)p=0.25圖6.2.5.1對(duì)兩個(gè)不同p值，fRCD(x)和fRHT(x)的比較圖6.2.5.2對(duì)兩個(gè)不同p值，F(xiàn)RCD(x)和FRHT(x)的比較15、和。令橢圓的旋轉(zhuǎn)角度為且兩個(gè)軸的長(zhǎng)度分別為a和b。則式(6.3.1.1)中的五個(gè)變數(shù)可轉(zhuǎn)換為且滿足下列三式6.3隨機(jī)式橢圓測(cè)法

6.3.1橢心的決定一個(gè)橢圓可以下式表示(6.3.1.1)式(6.3.1.1)中，代表橢心，而另外三個(gè)變數(shù)為d、e和f，且滿足16和且假設(shè)的切線斜率和的切線斜率不為平行。如此一來(lái)，通過(guò)和的二條切線會(huì)交於一點(diǎn)，且令所交的點(diǎn)為。另外我們令為線段的中點(diǎn)，則可得下列解令為一個(gè)橢圓上的四個(gè)邊點(diǎn)。在邊點(diǎn)上的斜率設(shè)為。在這四個(gè)邊點(diǎn)中挑選任意二個(gè)邊點(diǎn)，令這二個(gè)邊點(diǎn)為(6.3.1.2)從和之間，存在一個(gè)很重要的幾何性質(zhì)，即連接和的直線會(huì)通過(guò)橢心。這條直線可表示為(6.3.1.3)17圖6.3.1.1橢圓的中心接著來(lái)討論另外二個(gè)剩餘的邊點(diǎn)。令這二個(gè)剩餘的邊點(diǎn)為和且在挑選它們時(shí)己確保它們的切線不為平行。利用式子(6.9)，我們也可得和。如圖6.3.1.1所示，和形成的直線也是通過(guò)橢心。(6.3.1.4)利用式子(6.3.1.3)和式子(6.3.1.4)的二個(gè)聯(lián)立方程式可解出橢心為由於一開(kāi)始我們是隨機(jī)選四個(gè)邊點(diǎn)，、、和，所以共有三種組合方式、和可以幫助我們求得三個(gè)可能的橢心。186.3.2決定剩餘的三個(gè)變數(shù)假設(shè)橢圓的橢心為，我們將橢圓上的點(diǎn)進(jìn)行平移的動(dòng)作，即將原點(diǎn)移至橢心上。如此一來(lái)，式子(6.3.1.1)的橢圓方程式可簡(jiǎn)化為上式中待解的變數(shù)有三個(gè)，分為是d、e和f。我們只需利用挑選出來(lái)的四個(gè)邊點(diǎn)中的三個(gè)邊點(diǎn)即可解出這三個(gè)變數(shù)。分別將邊點(diǎn)代入上面式子中可得下列線性系統(tǒng)這裡需注意的是為邊點(diǎn)經(jīng)過(guò)平移後的座標(biāo)。從組合的觀點(diǎn)，共可解出四組解。196.3.3決定候選橢圓針對(duì)6.3.2節(jié)解出的四組，我們進(jìn)一步檢查其是否滿足、和。若是，則對(duì)應(yīng)的橢圓為一合法的橢圓；否則，其為假的橢圓。若某一組係數(shù)所代表的橢圓為一合法的橢圓，則該橢圓可否被選為橢圓候選人，得接著對(duì)一開(kāi)始選出的四個(gè)邊點(diǎn)進(jìn)行投票的動(dòng)作。令邊點(diǎn)為四個(gè)邊點(diǎn)中的一個(gè)，若與所代表的橢圓之距離小於一門(mén)檻值，則我們說(shuō)邊點(diǎn)在數(shù)位橢圓上，其餘的三個(gè)邊點(diǎn)也是算各個(gè)邊點(diǎn)與所代表的橢圓之距離。若四個(gè)邊點(diǎn)與橢圓的距離皆小於門(mén)檻值，我們就說(shuō)這橢圓為數(shù)位影像中的一候選橢圓。這裡的邊點(diǎn)與橢圓的距離計(jì)算公式如下(6.3.3.1)206.3.4決定真正橢圓圖6.3.4.1橢圓周長(zhǎng)的估計(jì)決定完橢圓候選人後，接著得檢查看影像中的所有邊點(diǎn)中，到底有多少邊點(diǎn)是屬於橢圓候選上的邊點(diǎn)。如果有足夠的邊點(diǎn)屬於該橢圓候選人，則該橢圓候選人為真正的橢圓。令變數(shù)C為用來(lái)計(jì)數(shù)屬於橢圓候選人的邊點(diǎn)數(shù)。式子(6.3.1.1)和相關(guān)的距離門(mén)檻值仍被用來(lái)檢測(cè)一邊點(diǎn)是否為某一橢圓上的邊點(diǎn)。當(dāng)所有的邊點(diǎn)都對(duì)該橢圓投完票了且C的值為。若的值大於門(mén)檻值，則該橢圓候選人可說(shuō)是符合真正的橢圓之要求。令橢圓的長(zhǎng)軸為2a，而短軸為2b，則外接的長(zhǎng)方形之周長(zhǎng)為4a+4b而內(nèi)接的棱形之周長(zhǎng)為。橢圓的周長(zhǎng)可估計(jì)為外接長(zhǎng)方形周長(zhǎng)加上內(nèi)接棱形周長(zhǎng)的一半，即。橢圓的周長(zhǎng)有時(shí)欲測(cè)的橢圓可能會(huì)被某些東西遮蔽，我們可將估計(jì)出的橢圓周長(zhǎng)乘上個(gè)百分比以達(dá)到增強(qiáng)隨機(jī)測(cè)橢圓的強(qiáng)健性的效果。216.3.5演算流程圖圖6.3.5.1演算流程圖圖6.3.5.2內(nèi)含4顆雞蛋的影像圖6.3.5.3測(cè)邊後的結(jié)果圖6.3.5.4偵測(cè)到的橢圓226.5視訊場(chǎng)景的變化偵測(cè)Hausdorff對(duì)任一張影像而言，一但找出影像中的各種形狀，例如有直線、圓和橢圓。我們接著求出任二種形狀的所有交點(diǎn)以為影像的代表點(diǎn)集。假設(shè)某影像的代表點(diǎn)集為而下一張影像的代表點(diǎn)集為，A和B的距離被下列的Hausdorff式子所決定

這裡。部份Hausdorff部分Hausdorff距離度量定義為我們選定而；是選第k大的而非中的最大的。23圖6.5.1視訊中的部份Hausdorff距離我們利用自己拍攝的視訊片段，視訊的內(nèi)容為一個(gè)籃球在地板上滾動(dòng)的情形。在圖中，我們可看出視訊中，第九張影像到第十張影像有場(chǎng)景變化。由圖6.5.1的結(jié)果，視訊中的第一張影像(見(jiàn)圖6.5.2(a))到第