《北理工賈云德《計(jì)算機(jī)視覺(jué)》chapter07輪廓表示(共25頁(yè))》由會(huì)員分享，可在線閱讀，更多相關(guān)《北理工賈云德《計(jì)算機(jī)視覺(jué)》chapter07輪廓表示(共25頁(yè))（25頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、精選優(yōu)質(zhì)文檔-----傾情為你奉上 第七章 輪廓表示 把邊緣連接起來(lái)就成為輪廓(contour)．輪廓可以是斷開(kāi)的，也可以是封閉的．封閉輪廓對(duì)應(yīng)于區(qū)域的邊界，而區(qū)域內(nèi)的像素可以通過(guò)填充算法來(lái)填滿．?dāng)嚅_(kāi)的輪廓可能是區(qū)域邊界的一部分，也可能是圖像線條特征，如手寫(xiě)體筆畫(huà)、圖畫(huà)中的線條等．區(qū)域之間的對(duì)比度太弱或邊緣檢測(cè)閾值設(shè)置太高都有可能產(chǎn)生間斷的輪廓． 　　輪廓可以用邊緣序列表或曲線來(lái)表示．曲線通常稱為輪廓的數(shù)學(xué)模型．曲線表示包括線段、二次曲線、三次樣條曲線等．下面是幾種輪廓表示的評(píng)價(jià)標(biāo)準(zhǔn)： 　　高效：輪廓應(yīng)該是一種簡(jiǎn)單和緊湊的表示． 　　精確：輪廓應(yīng)能精確地逼近圖像特征． 　　

2、有效：輪廓應(yīng)適合于后處理階段的計(jì)算． 　　輪廓表示的精確性由以下三個(gè)方面因素決定：① 用于輪廓建模的曲線形式；② 曲線擬合算法的性能；③ 邊緣位置估計(jì)的精確度．輪廓的最簡(jiǎn)單表示形式是邊緣有序表．這種表示的精確度就是邊緣估計(jì)的精確度，但其表示的緊湊性是最差的，因此不是一種有效的后續(xù)圖像分析表示方法．用適當(dāng)?shù)那€模型來(lái)擬合邊緣會(huì)提高精確度，這是因?yàn)榍€模型擬合邊緣時(shí)往往具有均值化效應(yīng)，因而可以減少邊緣位置誤差．曲線模型也會(huì)提高輪廓表示的經(jīng)濟(jì)性，為后處理提供了一種更適合、更緊湊的表示，例如，一條直線上的邊緣集用一直線來(lái)擬合是表示這些邊緣的最簡(jiǎn)單和最有效的方法，這一表示也簡(jiǎn)化了后續(xù)處理（如確定線的長(zhǎng)

3、度和方向）；另外，由于估計(jì)直線與真實(shí)直線的均值方差小于真實(shí)直線與任何其它邊緣之間的均值方差，因此可以說(shuō)這種表示也增加了精確度． 輪廓曲線擬合通常采用內(nèi)插曲線或逼近曲線來(lái)實(shí)現(xiàn)．已知一組稱為控制點(diǎn)的坐標(biāo)點(diǎn)，內(nèi)插是指一條曲線擬合這組控制點(diǎn)，使得曲線通過(guò)所有的控制點(diǎn)；逼近是指一條曲線擬合這組這組控制點(diǎn)，使得這條曲線非常接近這些控制點(diǎn)而無(wú)需一定通過(guò)這些點(diǎn)．在下面幾節(jié)中，假定由邊緣檢測(cè)器得到的邊緣十分準(zhǔn)確，并使用內(nèi)插值方法進(jìn)行邊緣曲線擬合． 　　定義7．1 邊緣表是邊緣點(diǎn)或邊緣段的有序集合． 　　定義7．2 輪廓是邊緣表或用于表示邊緣表的曲線． 　　定義7．3 邊界是包圍一個(gè)區(qū)域的封閉輪廓

4、． 　　在無(wú)特別說(shuō)明的情況下，邊緣通常是指邊緣點(diǎn)．對(duì)大多數(shù)曲線擬合算法來(lái)說(shuō)，只需要邊緣的位置信息。在很少的幾種情況下，即需要邊緣位置信息，也需要方向角信息，此時(shí)的邊緣是指邊緣段． 　　平面曲線函數(shù)可以表示為三種形式：顯式, 隱式，或參數(shù)式, 其中是某一參數(shù)．函數(shù)的顯式表示很少用在機(jī)器視覺(jué)中，主要原因是平面上的曲線可能卷曲，使得一個(gè)值可能對(duì)應(yīng)曲線上多個(gè)值． 7．1 數(shù)字曲線及其表示 　　本節(jié)將討論一組計(jì)算曲線幾何元素的算法，幾何元素包括輪廓長(zhǎng)度、正切方向角和曲率等．由于鄰接像素之間的量化增量是，因此，精確計(jì)算斜率和曲率是很困難的． 　　估計(jì)正切方向角的基本思路是使用邊緣表中非鄰接的邊緣

5、點(diǎn)，這就允許存在一個(gè)較大的可能正切方向角集合．設(shè)是邊緣表中第個(gè)邊緣坐標(biāo)．斜率是在邊緣表相距個(gè)邊緣點(diǎn)的兩個(gè)邊緣點(diǎn)之間的方向向量．左斜率是指向的方向，右斜率是指向方向．曲率是左右斜率之差值． 　　假定在邊緣表中有個(gè)邊緣．?dāng)?shù)字曲線的長(zhǎng)度可以近似為像素之間的線段和： (7．1) 輪廓端點(diǎn)之間的距離為： 　 (7．2) 7．1．1 鏈碼 　　鏈碼是沿著輪廓記錄邊緣表的一種表示方法．鏈碼規(guī)定了邊緣表中每一個(gè)邊緣點(diǎn)所對(duì)應(yīng)的輪廓方向，其中的輪廓方向被量化為４－鄰接鏈碼或８－鄰接鏈碼中的一個(gè)，如圖7．1所示．圖7．2 所

6、示的是一條曲線及其８－鄰接鏈碼的表示，8－鄰接鏈碼從邊緣表中第一個(gè)邊緣開(kāi)始，沿著輪廓按逆時(shí)針?lè)较蛐凶?，行走方向用八鏈碼中的一個(gè)表示． 　　　　　　　 　（a）　 　　　 　　 　 （b）　 圖7．1 連接邊緣點(diǎn)方向的鏈碼示意圖，（a）４－鄰接鏈碼，(b) 8－鄰接鏈碼 　　鏈碼有一些很特殊的的性質(zhì)．一個(gè)物體很容易實(shí)現(xiàn)角旋轉(zhuǎn)．如果一個(gè)物體旋轉(zhuǎn)，旋轉(zhuǎn)后的物體鏈碼可由原鏈碼加上倍的模8得到．鏈碼的微分，也稱差分碼，可由原碼的一階差分求得．鏈碼差分是關(guān)于旋轉(zhuǎn)不變的邊界描述方法．比如， 　　圖７．２曲線的鏈碼是： 　　　　　　其差分鏈碼是： 2011

7、1 圖７．３是圖７．２曲線逆時(shí)針旋轉(zhuǎn)后得到的， 　　　　曲線的鏈碼是：11234 　　　　 　其差分鏈碼是： 0111 由此可見(jiàn)，一條曲線旋轉(zhuǎn)到不同的位置將對(duì)應(yīng)不同的的鏈碼，但其差分鏈碼不變，即差分鏈碼關(guān)于曲線旋轉(zhuǎn)是不變的． 區(qū)域的一些其它性質(zhì)，如面積和角點(diǎn)，也可以由鏈碼直接求得．這種表示的局限性是表示某一點(diǎn)正切方向的集合是有限的（４－鄰接鏈碼有4個(gè)，8－鄰接鏈碼有8個(gè)），這一局限性可以通過(guò)下面幾節(jié)介紹的曲線表示方法來(lái)克服． 圖7．2 一條曲線及其８－鄰接鏈碼表示 圖7．３ 一條曲線及其８－鄰接鏈碼表示 7．1．2 斜率表示法 　　用任意

8、的正切方向來(lái)表示輪廓可以克服鏈碼的只能用有限個(gè)正切方向來(lái)表示輪廓的局限性．假定從邊緣表開(kāi)始，使用上面給出的公式計(jì)算正切和弧長(zhǎng)，可以畫(huà)出正切同弧長(zhǎng)的關(guān)系圖，稱作圖．圖是輪廓形狀在空間的表示，是一種輪廓形狀的緊湊描述．圖７．４所示的是包含有直線段和圓弧段的輪廓在空間中的表示，它是一個(gè)直線段序列．對(duì)于封閉輪廓，圖是一個(gè)周期曲線．在圖中，水平方向的直線段對(duì)應(yīng)輪廓中的直線段，這是由于直線段對(duì)應(yīng)的斜率是恒定值。其它方向的直線段對(duì)應(yīng)圓弧段，非直線段部分對(duì)應(yīng)曲線基元． 如果把圖分割成直線段，也就把輪廓分割成直線段和圓弧段．許多研究人員采用這一方法來(lái)分割輪廓，由此產(chǎn)生了輪廓分段方法的多種形式．

9、圖7．4 輪廓的斜率表示 7．2曲線擬合 本章將討論三種常用的曲線模型擬合邊緣點(diǎn)的方法：直線段(Line Segment)，圓錐曲線段(Conic Section)和三次樣條曲線段(Cubic Spline)．一般來(lái)說(shuō)，在用曲線模型擬合邊緣點(diǎn)之前應(yīng)考慮如下兩個(gè)問(wèn)題： 1. 用什么方法進(jìn)行邊緣點(diǎn)的曲線模型擬合？ 2. 如何測(cè)量擬合的逼近程度？ 下面幾節(jié)將討論曲線模型擬合邊緣點(diǎn)方法，其中假設(shè)邊緣位置足夠精確，不會(huì)對(duì)擬合結(jié)果產(chǎn)生影響． 設(shè)是邊緣點(diǎn)到一條擬合曲線的距離，該距離值有正負(fù)符號(hào)，在曲線同一側(cè)的邊緣具有相同的正符號(hào)或負(fù)符號(hào)．目前有許多種測(cè)量曲線與候選邊緣點(diǎn)

10、的擬合效果方法，每一種都取決于擬合曲線和候選點(diǎn)之間的誤差．下面是一些常用的方法． (1) 最大絕對(duì)誤差 測(cè)量最壞情況下邊緣點(diǎn)偏離曲線的距離： (7．3) (2) 均方差 給出邊緣點(diǎn)偏離擬合曲線的總的測(cè)度： (7．4) (3) 最大規(guī)范（normal）誤差 最大絕對(duì)誤差與曲線長(zhǎng)度之比： (7．5) (4) 誤差符號(hào)變化次數(shù) 這里的誤差就是指，即邊緣點(diǎn)偏離擬合曲線的距離。誤差符號(hào)變化次數(shù)可用來(lái)表示輪廓邊緣模

11、型的曲線適合程度的測(cè)度． (5) 曲線長(zhǎng)度與端點(diǎn)距離之比 曲線復(fù)雜程度的測(cè)度． 符號(hào)變化是一種評(píng)價(jià)擬合好壞的很有用的參數(shù)．比如，用直線段逼近邊緣表，并檢測(cè)符號(hào)變化數(shù)．如果符號(hào)變化一次，則說(shuō)明邊緣點(diǎn)可以由直線段來(lái)逼近；符號(hào)變化兩次，說(shuō)明邊緣可以由二次曲線逼近；符號(hào)變化三次，說(shuō)明邊緣模型是三次曲線，依此類推．如果符號(hào)變化數(shù)量很大，則意味著曲線復(fù)雜度增加一點(diǎn)將不能顯著地改善擬合效果．一種好的擬合所對(duì)應(yīng)的符號(hào)變化具有隨機(jī)模式．相同符號(hào)連續(xù)出現(xiàn)多次說(shuō)明存在擬合系統(tǒng)誤差，這種誤差可能是由于錯(cuò)誤的曲線模型引起的． 曲線擬合模型的選擇取決于應(yīng)用場(chǎng)合．如果場(chǎng)景是由直線段組成，則使

12、用直線段（或多線段）模型比較合適．直線段模型也可作為其它擬合模型的初始擬合模型．圓弧段是估計(jì)曲率的最有用的一種表示，因?yàn)榍€可以分割成具有分段恒定曲率線段．圓錐曲線段是一種表示直線段和圓弧段序列以及橢圓和高次弧段序列的有效方法．三次樣條曲線適合于平滑曲線模型，因?yàn)槿螛訔l曲線并不要求正切向量和曲率的估計(jì)值一定是分段恒定的． 7．2．1 多直線段 　　多直線段是指端點(diǎn)連結(jié)端點(diǎn)的直線段序列，直線段序列的連接點(diǎn)稱為頂點(diǎn)．多直線段適合具有線段序列的邊緣列表的擬合．多線段算法的輸入值是邊緣點(diǎn)有序表．邊緣點(diǎn)坐標(biāo)可以計(jì)算到子像素精度．由于線段的兩個(gè)端點(diǎn)對(duì)應(yīng)兩個(gè)邊緣點(diǎn)，即線段擬合在這兩個(gè)邊緣點(diǎn)之間進(jìn)行，因

13、此僅需要精確計(jì)算對(duì)應(yīng)端點(diǎn)的兩個(gè)邊緣點(diǎn)的坐標(biāo)． 擬合邊緣表并把第一和最后一個(gè)邊緣點(diǎn)和連接起來(lái)的直線線公式如下： (7．6) 上式可以改寫(xiě)為由端點(diǎn)表示的隱式函數(shù)： 　　　　　　　 (7．7) 其中，　　　　　　 　　　　　　　　 而是邊緣點(diǎn)和之間的距離． 　　任意一點(diǎn)，設(shè)，則的符號(hào)可以用來(lái)計(jì)算符號(hào)變化次數(shù)C．點(diǎn)與上述直線段的距離為： 　　　　 (7．8) 最大規(guī)范誤差為： (7．9) 最大規(guī)范誤差常常作為線段擬合邊緣列表好壞的量度．需

14、要指出的是上面的公式都是在點(diǎn)向直線段的垂直投影落在線段內(nèi)這個(gè)假設(shè)下進(jìn)行的．對(duì)于其它情況，則應(yīng)修正公式，以便計(jì)算點(diǎn)到最近的線段端點(diǎn)的距離．下面介紹兩種擬合多線段的方法：自頂而下的分裂和自底而上的合并． (1) 多直線段分裂 自頂而下的分裂算法(top-down splitting)是將整條曲線作為初始曲線，通過(guò)反復(fù)增加頂點(diǎn)數(shù)來(lái)進(jìn)行直線段擬合曲線．考慮圖7．5所示的邊緣點(diǎn)曲線（可以認(rèn)為是由離散邊緣點(diǎn)構(gòu)成），將第一個(gè)和最后一個(gè)邊緣點(diǎn)連成的直線作為曲線的初始擬合，用AB標(biāo)記．在邊緣表中計(jì)算最大規(guī)范誤差，如果該誤差值高于某一閾值，則在離直線段最遠(yuǎn)的邊緣點(diǎn)上設(shè)置一個(gè)頂點(diǎn)，用C來(lái)標(biāo)記．這樣

15、，將形成兩個(gè)擬合直線段AC和CB，邊緣表也分割成對(duì)應(yīng)于兩個(gè)新直線段的兩個(gè)子邊緣表．在每一個(gè)子邊緣表中，重復(fù)上面所述的分裂算法，形成兩個(gè)新的直線段及對(duì)應(yīng)的兩個(gè)更小的子邊緣表．這樣的分裂過(guò)程可以一直進(jìn)行下去，直到所有的直線段對(duì)應(yīng)的最大規(guī)范誤差均低于某一閾值為止．多線段分裂也稱為迭代分解． (2) 線段合并 　　線段合并(merging)是指用一條直線段盡量多地?cái)M合邊緣表中的邊緣點(diǎn)．當(dāng)邊緣點(diǎn)離直線段太遠(yuǎn)而無(wú)法用該直線段擬合時(shí)，則開(kāi)始新的直線段擬合．合并方法也稱為自底而上(bottom-up merging)的多線段擬合方法． 確定邊緣點(diǎn)離直線段的距離有許多種方法．一種方法是使用

16、序貫最小二乘法，完成直線段到邊緣點(diǎn)的最小二乘法擬合，并在每次處理新的邊緣點(diǎn)時(shí)遞增地更新線段參數(shù)．?dāng)M合算法將計(jì)算直線段模型和邊緣點(diǎn)之間的殘差平方．當(dāng)誤差超過(guò)某一閾值時(shí)，引進(jìn)一個(gè)頂點(diǎn)，并將上一個(gè)線段的端點(diǎn)作為新的起點(diǎn)開(kāi)始新的直線段擬合． 　　誤差帶算法是另一種確定頂點(diǎn)位置的方法，如圖7．6所示，主要工作是計(jì)算兩條離中心線距離為且平行于擬合邊緣點(diǎn)的直線段．值表示離有差擬合直線的絕對(duì)偏離值．只要新的邊緣在誤差帶內(nèi)，就把這些邊緣增加到當(dāng)前線段內(nèi)．當(dāng)新的邊緣增加到線段內(nèi)時(shí)，線段的參數(shù)要重新計(jì)算．逼近直線段沒(méi)有與誤差帶邊保持平行．位于線段端點(diǎn)的頂點(diǎn)是下一線段的起點(diǎn)．這一方法常常產(chǎn)生大量的線段．由于算法須行

17、進(jìn)到邊緣直到誤差帶表示的邊界才產(chǎn)生角點(diǎn)，因此，不能精確估計(jì)角點(diǎn)位置和角度． 圖7．5 多直線段分裂方法 圖 7．6 擬合直線段的誤差帶方法圖 (3) 分裂和合并 　　自頂而下的迭代分解方法和自底而上的合并方法組合起來(lái)，形成合并和分裂算法．單獨(dú)使用分裂或合并算法時(shí)，成功率往往不是很高，改進(jìn)的方法是交叉使用分裂和合并算法．分解過(guò)程以后，如果新的線段以很小的規(guī)范誤差擬合邊緣，則允許用單一直線段代替鄰接線段．請(qǐng)注意，由于多直線段總是比單直線段的擬合誤差小，因此很有必要使用規(guī)范誤差．在線段合并后，新的線段可能在不同點(diǎn)處分裂．這樣，分裂和合并交替作用直到?jīng)]有線段被

18、合并和分裂為止．圖7．7所示的是先分裂后合并來(lái)修補(bǔ)壞頂點(diǎn)位置的示意圖． 　　一種有效的分裂和合并算法是從邊緣表中的前k個(gè)邊緣構(gòu)成的子列表開(kāi)始，而不是整個(gè)邊緣列表．用直線段擬合子表中第一和最后一個(gè)邊緣點(diǎn)之間的邊緣點(diǎn)．如果最大規(guī)范誤差太大，則將子列表縮到最大誤差對(duì)應(yīng)的邊緣點(diǎn)處，這樣一直進(jìn)行下去，就可以得到第一條擬合直線段，這實(shí)際上是分裂算法．置當(dāng)前擬合的直線段為舊線段，再在剩下的邊緣點(diǎn)集中取前k個(gè)邊緣構(gòu)成新子列表，用分裂算法求取第二條擬合直線段．比較當(dāng)前直線段和原直線段的方向，如果它們具有相似的方向，則將這兩條直線段合并，這是合并算法． 　　實(shí)際的輪廓曲線并不全是由直線段組成，可能還包含有各種

19、弧線或自由曲線．因此，僅使用直線段擬合比較粗糙，自然人們想到了用弧線段逼近．通常的弧線有二次／三次或更高次的曲線，這些都稱為多項(xiàng)式曲線．下面我們主要討論二次曲線和三次樣條曲線． 圖7．7 (a)　原始邊緣點(diǎn)集．(b)自底而上的邊緣合并方法產(chǎn)生的壞角點(diǎn)估計(jì)． (c) 漏掉的真實(shí)角點(diǎn)位置由分裂和合并過(guò)程來(lái)修補(bǔ) 7．2．2　圓錐曲線 　　下面討論如何用圓錐曲線逼近邊緣表．圓錐曲線的一般表示如下： (7．10) 圓錐曲線也稱二次曲線，因?yàn)槎吻€都是用平面切割正圓錐面的截線，如圖7．8所示．若平面不通過(guò)錐頂，且不平行任一母線，則截線為橢圓，其中圓是橢圓

20、的一種特殊情況，此時(shí)的平面垂直于錐軸；若平面不通過(guò)錐頂?shù)叫杏谝粭l母線時(shí)，截線為拋物線；若平面不通過(guò)錐頂，且平行于錐軸，截線為雙曲線．當(dāng)平面通過(guò)通過(guò)錐頂時(shí)，橢圓變?yōu)橐稽c(diǎn)，雙曲線變?yōu)橐粚?duì)相交的直線，拋物線變?yōu)榕c圓錐相切的一條直線．由此可見(jiàn)，使用二次曲線來(lái)逼近數(shù)字輪廓曲線，可以有效地?cái)M合數(shù)字曲線中的直線和圓弧等各種二次曲線．由于二次曲線中除了特殊的直線外，最簡(jiǎn)單的情況時(shí)圓弧，因而得到了大量的研究．我們將單獨(dú)討論圓弧逼近方法． 圖7．8 圓錐和平面定義的圓錐曲線 (1) 圓弧段 用直線段逼近邊緣表以后，其中的一些直線段序列可以由圓弧段來(lái)代替，比如，用直線段擬合一個(gè)

21、圓弧是可能需要許多個(gè)直線段才能滿足擬合誤差．如果將這些直線段用用圓弧段來(lái)擬合，則僅需要一條圓弧段即可．因此可見(jiàn)，圓弧段擬合是在多邊形的頂點(diǎn)上進(jìn)行的． 具有半徑r和圓心坐標(biāo)的圓弧隱式方程為： （7．11） 考慮三點(diǎn)，，，不失一般性，設(shè)位于坐標(biāo)原點(diǎn)，即．把點(diǎn)，，代入上述方程： 　　　　　　　　?。? ．12） 分別用第二和第三方程減去第一方程，得到如下兩個(gè)方程： 　 　 （7．13） 這是兩個(gè)關(guān)于未知參數(shù)的非線性方程，求解,即可由（7．12）的第一個(gè)式子得到園的半徑. 為了計(jì)算圓弧擬合誤差，將點(diǎn)Q到圓的距離定義為沿著通過(guò)園心

22、直線方向點(diǎn)Q與圓的距離．計(jì)算點(diǎn)到園中心的距離: (7．14) 點(diǎn)Q到圓弧段的距離是 (7．15) 用圓弧段擬合多直線段時(shí)，圓弧段的兩個(gè)端點(diǎn)要經(jīng)過(guò)多直線段的某兩個(gè)頂點(diǎn)，第三個(gè)點(diǎn)位于這兩個(gè)頂點(diǎn)之間。選擇第三個(gè)點(diǎn)時(shí)可能有如下幾種情況： １． 選用距離連接這兩個(gè)頂點(diǎn)直線最遠(yuǎn)的多直線段頂點(diǎn)． ２． 選用距離連接這兩個(gè)頂點(diǎn)直線最遠(yuǎn)的邊緣點(diǎn)． 　?。常x用這兩個(gè)頂點(diǎn)之間所有頂點(diǎn)的中點(diǎn)． 　?。矗x用這兩個(gè)頂點(diǎn)之間所有邊緣的中點(diǎn) 　　計(jì)算所有邊緣點(diǎn)和圓弧段之間的距離誤差，計(jì)算最大絕對(duì)誤差和符號(hào)變化次數(shù)

23、．如果最大規(guī)范誤差低于某一閾值，而符號(hào)變化次數(shù)很大，則接受這一圓弧段；否則，保留多線段逼近．關(guān)于圓弧段逼近的文獻(xiàn)很多，感興趣的讀者可以參見(jiàn)文獻(xiàn)[]。 用直線段和圓弧段可以有效地表示數(shù)字輪廓曲線，但是用兩種不同的線段基元表示輪廓會(huì)造成不便．下一節(jié)我們將討論圓錐曲線，圓錐曲線允許直線段、圓弧段、和其它基元共同出現(xiàn)在同一種表示中．圓錐曲線段表示也提供了曲線之間平滑過(guò)渡的方法，也是角點(diǎn)的顯式表示． (2) 圓錐曲線 　　圓錐曲線可以擬合輪廓多直線段上的三個(gè)頂點(diǎn)．將圓錐曲線段連接在一起的點(diǎn)稱為結(jié)點(diǎn)．圓錐樣條曲線是圓錐曲線的一個(gè)序列，它們的端點(diǎn)和端點(diǎn)連接在一起，在結(jié)點(diǎn)處具有相等的正

24、切，以便使兩個(gè)鄰接曲線段之間平滑過(guò)渡．設(shè)多直線段端點(diǎn)為．圓錐逼近如圖7．9所示． 圖7．9 由三點(diǎn)定義的圓錐曲線逼近 圖7．10 由兩個(gè)端點(diǎn)、三頂點(diǎn)構(gòu)成的正切和第三點(diǎn)定義的圓錐曲線 圓錐樣條中的每一個(gè)圓錐曲線由兩個(gè)端點(diǎn)、兩個(gè)正切和第三點(diǎn)確定．結(jié)點(diǎn)位于多線段頂點(diǎn)之間： (7．16) 其中取0和1之間的數(shù)值．正切由三個(gè)頂點(diǎn), 和組成的三角形來(lái)定義．第三點(diǎn)如圖7．10所示，由下面式子計(jì)算

25、(7．17) 有幾種特殊的情況可以通過(guò)如下方法來(lái)處理．如果，那么第個(gè)圓錐樣條曲線是到的直線段．如果和，那么，和對(duì)應(yīng)于同一點(diǎn)，在圓錐曲線序列中有一個(gè)角點(diǎn)．這些性質(zhì)使得直線段和角點(diǎn)可以明顯地表示出來(lái)，無(wú)需求助于不同的基元和特殊的標(biāo)志． 圖7．11 圓錐曲線的導(dǎo)向形式 這里所示的計(jì)算圓錐樣條算法使用了一個(gè)圓錐曲線的導(dǎo)向形式，以表示由三條直線約束的圓錐曲線，如圖7．11所示．直線方程為 (7．18) 設(shè)多直線段中的第一和最后一個(gè)頂點(diǎn)為A和B，C是多線段的中間頂點(diǎn)，用弦AB連接第一和最后一個(gè)頂點(diǎn)．圓錐曲線導(dǎo)向形式是端點(diǎn)位于A

26、和B的圓錐體的家族，正切AC和BC由下面方程定義： (7．19) 其中 (7．20) 是包含直線段AC的直線，而 (7．21) 是包含直線段BC的直線，以及 (7．22) 是包含弦BC的直線． 圓錐曲線的家族由參數(shù)來(lái)定義． 圓錐曲線擬合邊緣表的算法是從直線段開(kāi)始的，并把頂點(diǎn)分為角點(diǎn)(corner)、軟頂點(diǎn)(soft vertex)或結(jié)點(diǎn)(knot)三類．軟頂點(diǎn)

27、對(duì)應(yīng)的角接近，相鄰的直線段幾乎共線，并可以用圓錐曲線來(lái)代替．軟頂點(diǎn)序列對(duì)應(yīng)于緩變方向角的直線段序列，很可能是對(duì)光滑曲線的采樣點(diǎn)進(jìn)行擬合的結(jié)果．角點(diǎn)對(duì)應(yīng)的頂點(diǎn)角大于或小于，其中是閾值，角點(diǎn)不可能成為圓錐曲線的一部分．結(jié)點(diǎn)位于某一條直線段上，該直線段的端點(diǎn)上具有軟頂點(diǎn)．一個(gè)圓錐曲線不可能有拐點(diǎn)，所以兩個(gè)圓錐曲線在結(jié)點(diǎn)處連接．結(jié)點(diǎn)在直線段上的位置由直線段端點(diǎn)的軟頂點(diǎn)相對(duì)角度確定．設(shè)兩個(gè)軟頂點(diǎn)和的角度分別是和．如果, 那么結(jié)點(diǎn)可以位于頂點(diǎn)的中間，也就是說(shuō)，在方程7．16中，．如果角度不相等，那么，結(jié)點(diǎn)位置應(yīng)該偏離具有較大角度的那個(gè)角點(diǎn)，這是由于圓錐曲線不可能偏離直線段而足夠迅速地彎曲去跟蹤角點(diǎn)．方程7

28、．16的值可以由下式計(jì)算： (7．23) 由軟頂點(diǎn)連接的每一個(gè)直線段序列可由穿過(guò)第一和最后一個(gè)頂點(diǎn)（或結(jié)點(diǎn)）的導(dǎo)向圓錐代替．第一和最后一個(gè)直線段的方向角定義了正切．正切和端點(diǎn)確定圓錐5個(gè)自由度的4個(gè)．讓圓錐穿過(guò)位于序列中央的軟頂點(diǎn)可以完全確定圓錐． 7．３ 樣條曲線 早期繪圖員在制圖時(shí)，使用一種富有彈性的細(xì)長(zhǎng)條，稱為樣條。用壓鐵將樣條固定在若干樣點(diǎn)上，然后沿樣條可以畫(huà)出很光滑的曲線，人們將該曲線稱為樣條曲線．從數(shù)學(xué)上講，樣條曲線是用分段多項(xiàng)式表示的一個(gè)函數(shù)，在其連接點(diǎn)處具有連續(xù)的一階和二階導(dǎo)數(shù)． 樣條曲線有著許多應(yīng)用．在數(shù)據(jù)分析中，

29、當(dāng)沒(méi)有合適的函數(shù)模型時(shí)，可以選用樣條函數(shù)擬合數(shù)據(jù)點(diǎn)．在計(jì)算機(jī)圖形和計(jì)算機(jī)輔助設(shè)計(jì)中，樣條函數(shù)用來(lái)表示自由曲線．在機(jī)器視覺(jué)中，若沒(méi)有表示曲線的合適模型時(shí)，樣條函數(shù)可以提供曲線的通用表示形式． 需要指出，幾何等效和參數(shù)等效是兩個(gè)不同的概念．兩條曲線在幾何上等效，是指它們連接相同的點(diǎn)集，即它們?cè)诳臻g上對(duì)應(yīng)著相同的形狀（或點(diǎn)集）．如果兩條曲線的方程一樣，則兩條曲線在參數(shù)上等效．顯然，參數(shù)等效性比幾何等效性更穩(wěn)定．兩條曲線可以是幾何上等效但可以具有不同的參數(shù)表示式，這是機(jī)器視覺(jué)中曲線擬合的一個(gè)重要概念．比如，機(jī)器視覺(jué)系統(tǒng)可以產(chǎn)生基于三次樣條曲線的表示，其在幾何上非常接近于物體輪廓的真實(shí)表示，但在參數(shù)意

30、義上，表示可能完全不同．在物體識(shí)別應(yīng)用方面和工業(yè)零件圖像與其模型匹配應(yīng)用中，通過(guò)比較三次樣條曲線的參數(shù)形式實(shí)現(xiàn)匹配幾乎是不可能的，在這種情況下，比較必須基于幾何等效性． ７．３．１　三次樣條曲線 樣條函數(shù)最常見(jiàn)的形式是三次樣條函數(shù)，它是分段三次多項(xiàng)式的一個(gè)序列．上一節(jié)所討論的直線段、圓弧段和圓錐曲線序列是樣條函數(shù)的典型實(shí)例．三次樣條函數(shù)可以用很少幾個(gè)樣條段表示很復(fù)雜的曲線．三次樣條函數(shù)已經(jīng)廣泛用于計(jì)算機(jī)圖形領(lǐng)域和字符輪廓表示． 三次樣條具有足夠的自由度來(lái)逼近邊緣段位置和方向．我們知道，大多數(shù)邊緣檢測(cè)算法同時(shí)提供邊緣方向（梯度角）和邊緣位置估計(jì)．在直線段、圓弧段和圓錐曲線的擬合中，僅僅使用

31、了邊緣的位置信息．下面介紹一種三次樣條曲線擬合中如何使用由邊緣檢測(cè)器產(chǎn)生的方向信息的例子． 平面三次曲線方程如下: (7．24) 其中系數(shù)，，，是二元向量，參數(shù)u取值范圍在0和1之間．三次曲線起始點(diǎn)為，終結(jié)點(diǎn)為．三次樣條是由三次曲線段，，．．．，構(gòu)成的一個(gè)序列，這一序列定義在連續(xù)間隔，，．．．，上，并將端點(diǎn)連結(jié)起來(lái)使得在端點(diǎn)處，見(jiàn)圖7．12．樣條中的每一個(gè)三次曲線段稱為樣條段，連結(jié)樣條段的邊緣點(diǎn)稱為結(jié)點(diǎn)． 圖　7.12 個(gè)控制點(diǎn)的分段連續(xù)三次樣條插值曲線 和前面討論的曲線擬合算法一樣，把邊緣點(diǎn)序列分成一個(gè)個(gè)子序列，每一個(gè)子序

32、列的第一個(gè)和最后一個(gè)邊緣點(diǎn)為樣條曲線的結(jié)點(diǎn)，然后再用樣條段擬合這些結(jié)點(diǎn)．由公式7．24可知，樣條中每一個(gè)三次曲線段都需要確定四個(gè)二維向量共計(jì)八個(gè)參數(shù)，其中，曲線段的兩個(gè)端點(diǎn)（或結(jié)點(diǎn)）共提供四個(gè)約束，結(jié)點(diǎn)處的一階連續(xù)性（等正切向量）提供另兩個(gè)約束，結(jié)點(diǎn)處的方向信息僅提供一個(gè)附加約束（由于結(jié)點(diǎn)由兩個(gè)樣條段共享），結(jié)點(diǎn)處的二階連續(xù)性（等曲率）提供兩個(gè)約束，這樣所產(chǎn)生的方程數(shù)量為九個(gè)，多于三次樣條段所需的八個(gè)參數(shù)． 　　在結(jié)點(diǎn)處光滑連接樣條段是非常重要的。在計(jì)算機(jī)圖形學(xué)中，光滑連接是通過(guò)增加二階連續(xù)性來(lái)實(shí)現(xiàn)．由上面分析可知，二階連續(xù)性會(huì)提供兩個(gè)約束，從而對(duì)樣條段產(chǎn)生超約束。為了避免超約束，同時(shí)又要使

33、結(jié)點(diǎn)處光滑，可以采用結(jié)點(diǎn)處二階不連續(xù)性的極小化條件，也就是說(shuō)把結(jié)點(diǎn)處的曲率差值極小化作為一個(gè)約束代替二階連續(xù)性提供兩個(gè)約束。 對(duì)于整個(gè)三次樣條曲線，求 n-1個(gè)結(jié)點(diǎn)處二階導(dǎo)數(shù)差值平方和的極小化： (7．25) 其中兩個(gè)樣條段在其公共結(jié)點(diǎn)處的二階導(dǎo)數(shù)差值是 (7．26) 變量是結(jié)點(diǎn)處的正切向量，該正切向量由邊緣方向（梯度角）和一個(gè)有正負(fù)號(hào)的未知參數(shù)來(lái)決定： (7．27) 換句話說(shuō)，在結(jié)點(diǎn)處的邊緣方向可以用一個(gè)單位向量

34、表示，但三次樣條需要具有大小及正負(fù)號(hào)的正切量，以表示穿越結(jié)點(diǎn)的方向和速度．用該算法求解線性系統(tǒng)方程，可以得到n個(gè)未知數(shù)，由此提供構(gòu)造結(jié)點(diǎn)之間三次樣條段的丟失信息． 本算法沒(méi)有任何附加參數(shù)和閾值，但是，同前面介紹的多線段、圓弧段和圓錐截面擬合算法一樣，結(jié)點(diǎn)必須從邊緣表中選出．使用上面所述的多線段算法進(jìn)行輪廓多線段逼近可以確定結(jié)點(diǎn)位置。多線段頂點(diǎn)也可以作為結(jié)點(diǎn)的位置。調(diào)節(jié)結(jié)點(diǎn)的位置和數(shù)量可以改善三次樣條對(duì)整個(gè)邊緣點(diǎn)集的擬合． 三次樣條擬合算法僅僅需要求解一個(gè)小的線性系統(tǒng)就可以得到正切值的符號(hào)和量值，因此該算法十分有效．如果需要的話，可以使用許多交互式圖形界面，在其上可以很方便地調(diào)節(jié)三次樣條曲線

35、． 7．3．2 樣條曲線 樣條曲線是由結(jié)點(diǎn)引導(dǎo)的逐段多項(xiàng)式曲線，是一種平滑和內(nèi)插技術(shù)．樣條與上述樣條曲線不同，它不必通過(guò)結(jié)點(diǎn)，我們將這種結(jié)點(diǎn)稱為引導(dǎo)結(jié)點(diǎn)．樣條曲線的三次多項(xiàng)式是最常用的，因?yàn)檫@些樣條曲率連續(xù)度為最低．已知引導(dǎo)結(jié)點(diǎn)序列為，，．．．，，則三次B－樣條多項(xiàng)式為： 　　　　?。?．28） 式中，，，為參數(shù)的三次多項(xiàng)式．下面確定上式四個(gè)多項(xiàng)式所對(duì)應(yīng)的16個(gè)參數(shù)．對(duì)任意的，相鄰曲線段，以及二階導(dǎo)數(shù)必須連續(xù)的條件提供15個(gè)等式，例如，，則有： 　　　?。?．29） 并提供以下五個(gè)等式： ，，，， 的形狀對(duì)坐標(biāo)轉(zhuǎn)換不變的條件提供了另一個(gè)方程：

36、 （7.30） 通過(guò)解16個(gè)等式，可以得到如下16個(gè)系數(shù)： 　　 　　　　　（7.31） 顯然這四個(gè)多項(xiàng)式都是非負(fù)的，根據(jù)式（7.30），曲線上的任何點(diǎn)都是四個(gè)控制結(jié)點(diǎn)的插補(bǔ)，即曲線段包含在由四個(gè)控制結(jié)點(diǎn)確定的方塊內(nèi)．如圖7．13所示．通常，次的樣條包含在由控制點(diǎn)確定的多邊形內(nèi)。由于樣條的優(yōu)良特性和對(duì)于任何控制點(diǎn)導(dǎo)數(shù)的連續(xù)性，故在實(shí)際中較為常用。 圖7．13 樣條曲線示意圖。（a）直線，(b) 二次樣條曲線，（3）三次樣條曲線 7．４ 曲線回歸逼近 　　目前有許許多多曲線逼近方法，其區(qū)別主要取決于邊緣點(diǎn)組成輪廓點(diǎn)的可靠度。如果將所有邊緣點(diǎn)連接起來(lái)可以組成一個(gè)輪

37、廓，那么就可以用最小二次回歸法來(lái)進(jìn)行邊緣點(diǎn)曲線擬合．如果存在組合誤差（Grouping Error），則可以使用魯棒回歸方法來(lái)進(jìn)行曲線逼近．如果邊緣點(diǎn)組成的輪廓不可靠，或者邊緣點(diǎn)太分散以至于無(wú)法用連接或跟蹤方法來(lái)組成輪廓，那么必須使用聚類分析（Cluster Analysis）技術(shù)同時(shí)進(jìn)行邊緣點(diǎn)的組合和曲線逼近．同時(shí)用組合和曲線逼近方法處理分散邊緣點(diǎn)算法的最好例子是Hough變換，這一內(nèi)容將在下面討論 前面幾節(jié)討論的直線段、圓弧段、圓錐曲線和三次樣條擬合邊緣點(diǎn)的方法屬于一般回歸問(wèn)題，主要用于端點(diǎn)之間的曲線擬合．這些算法都假定邊緣的位置可以精確計(jì)算，甚至可能使用子像素計(jì)算方法．這種回歸算法沒(méi)有

38、使用端點(diǎn)之間的邊緣點(diǎn)信息，因此曲線的擬合精度主要取決于端點(diǎn)的位置精度．本節(jié)討論的曲線最佳逼近方法將使用所有邊緣點(diǎn)信息． 一般曲線擬合問(wèn)題是一個(gè)曲線的回歸問(wèn)題, 曲線用個(gè)參數(shù)的隱函數(shù)表示： (7．32) 曲線預(yù)估問(wèn)題就是指這種曲線模型擬合一個(gè)邊緣點(diǎn)集，． 在無(wú)噪聲情況下，通過(guò)次觀測(cè)產(chǎn)生的個(gè)方程來(lái)求解個(gè)未知曲線參數(shù)．不幸的是在大多數(shù)場(chǎng)合，由于噪聲的原因，這一直接方法不是很有效．實(shí)際的應(yīng)用常常需要使用邊緣表中所有信息來(lái)獲取這些參數(shù)的最佳估計(jì)． 下一節(jié)我們將討論最小二次回歸方法，這種方法在計(jì)算機(jī)視覺(jué)中主要用于曲線擬合．當(dāng)誤差服從正態(tài)分布時(shí)，最小二次方法

39、是最合適的擬合方法．7.4.3將討論曲線擬合的魯棒性方法，這種方法在一些邊緣點(diǎn)被錯(cuò)誤地連接到某一輪廓時(shí)特別有用．這種被錯(cuò)誤地連接的點(diǎn)被稱為局外點(diǎn)（Outlier）． ７．４．1 全回歸方法 傳統(tǒng)的線性回歸方法僅僅在一維獨(dú)立變量空間中對(duì)數(shù)據(jù)和模型差值求極小化．比如，一個(gè)函數(shù)模型具有下列形式， (7．33) 上式把獨(dú)立變量和獨(dú)立變量聯(lián)系起來(lái)，具有個(gè)模型參數(shù)（…），并假定獨(dú)立變量沒(méi)有誤差．在機(jī)器視覺(jué)中，和的坐標(biāo)位置誤差很可能相等，其對(duì)應(yīng)的曲線模型是一條垂直線，這樣就無(wú)法用上述方程來(lái)表示．在機(jī)器視覺(jué)中，邊緣點(diǎn)的直線和曲線模型擬合是通過(guò)使用全回歸方

40、法實(shí)現(xiàn)的，即對(duì)所有的數(shù)據(jù)點(diǎn)與回歸模型之間距離的平方和進(jìn)行極小化，這一技術(shù)的優(yōu)點(diǎn)是能夠補(bǔ)償和方向的誤差． 為了避免垂直直線引起得問(wèn)題，可以使用如下極坐標(biāo)形式來(lái)表示直線方程： (7．34) 求所有點(diǎn)到該直線垂直距離的平方和極小化： (7．35) 全回歸問(wèn)題的解是： (7．36) 其中 (7．37) 全回歸直線方向角為，由下式給出： (7．38) 其中 全回歸方法使用了最小二

41、次誤差范數(shù)，如果誤差服從正態(tài)分布，則誤差范數(shù)是最優(yōu)的。該方法不適用于數(shù)據(jù)中有局外點(diǎn)的情況．在用曲線模型擬合邊緣點(diǎn)時(shí)，如果邊緣連接算法從其它輪廓上吸收一個(gè)或一個(gè)以上邊緣點(diǎn)到本輪廓邊緣表中，即產(chǎn)生了邊緣局外點(diǎn)局外點(diǎn)．即使邊緣連接算法完美無(wú)缺，也免不了局外點(diǎn)的產(chǎn)生．例如，考慮對(duì)應(yīng)一個(gè)矩形兩條鄰接邊的邊緣表，在用直線擬合邊緣前，必須識(shí)別出角點(diǎn)以便把邊緣表分割兩條邊．如果不能正確地識(shí)別角點(diǎn)，那么，一些邊緣點(diǎn)可能被分配給錯(cuò)誤的邊，這些邊緣點(diǎn)即為局外點(diǎn)． 通常在分類時(shí)產(chǎn)生的誤差會(huì)引入到回歸問(wèn)題里，其中的誤差不服從正態(tài)分布．在這種情況下，誤差可以由一個(gè)混合模型來(lái)表示，即把描述正態(tài)分布誤差的高斯分布函

42、數(shù)和描述由于分類不理想而引起的局外點(diǎn)分布的拖尾分布函數(shù)混合起來(lái)． 7．４．2 角點(diǎn)估計(jì) 角點(diǎn)估計(jì)的最佳方法是使用直線段逼近邊緣點(diǎn)來(lái)求出直線段序列，然后計(jì)算直線段之間的交點(diǎn)．這一方法補(bǔ)償了由邊緣檢測(cè)算子對(duì)角點(diǎn)的平滑作用而引入的誤差，并且比利用局部信息的角點(diǎn)檢測(cè)算子求出的角點(diǎn)更精確． 已知兩條直線的隱函數(shù)方程為 (7．39) (7．40) 交點(diǎn)坐標(biāo)為： (7．41) 如果非常接近零，那么兩條直線幾乎平行，沒(méi)有交點(diǎn)． 一種

43、較好的探測(cè)角點(diǎn)方法是沿著輪廓用一對(duì)直線擬合個(gè)邊緣點(diǎn)中的一個(gè)個(gè)連續(xù)子表，其中，參數(shù)是邊緣點(diǎn)數(shù)量，用于精確直線擬合；參數(shù)是位于角點(diǎn)周?chē)挥杩紤]的邊緣點(diǎn)的數(shù)量，即跨越角點(diǎn)圓弧部分的邊緣點(diǎn)．設(shè)置一個(gè)閾值，檢測(cè)的幅值是否大于該閾值即可決定角點(diǎn)是否存在． 7．４．3 魯棒回歸法 如果誤差不服從正態(tài)分布，那么最小二乘法就不是最佳擬合方法．圖7．14所示的是數(shù)據(jù)集合包含一些局外點(diǎn)時(shí)，使用最小二乘法所遇到的問(wèn)題的一個(gè)例子．在實(shí)際中，可能一個(gè)局外點(diǎn)就足夠把回歸直線推向遠(yuǎn)離其正確的位置．魯棒性回歸方法要對(duì)數(shù)據(jù)的各種子集進(jìn)行測(cè)試，從中選擇一個(gè)產(chǎn)生最佳擬合的子集． 圖7．14 使用最小二

44、次回歸曲線擬合方法和魯棒性回歸方法對(duì)包含有局外點(diǎn)的一組數(shù)據(jù)進(jìn)行擬合的差別 圖7．15 最小二次方法對(duì)局外點(diǎn)敏感度的物理模擬圖[Jain]． 圖7．15是一個(gè)物理模擬圖，可以使問(wèn)題變的更加清楚．設(shè)想一下你準(zhǔn)備求出平面上一組點(diǎn)的質(zhì)心．把具有相同彈簧系數(shù)的若干彈簧的一端連接到一個(gè)可以自由運(yùn)動(dòng)的物體上，另一端分別系在不同的固定點(diǎn)上，物體將會(huì)被拉到一個(gè)平衡（平均）位置上．彈簧將通過(guò)彈簧勢(shì)能方程進(jìn)行最小二乘法范數(shù)運(yùn)算．這個(gè)物理模擬對(duì)應(yīng)于一個(gè)均值計(jì)算的微分，其中均值是指殘差平方和（即點(diǎn)與均值之差的平方和）極小化判據(jù)中的均值．現(xiàn)在假定其中的一點(diǎn)可以移動(dòng)，并稱這一點(diǎn)為杠桿點(diǎn)．用力扯

45、動(dòng)杠桿點(diǎn)到足夠遠(yuǎn)的地方，可以迫使平衡點(diǎn)移動(dòng)到任意一個(gè)位置．這一現(xiàn)像說(shuō)明基于最小二乘法的預(yù)估器對(duì)局外點(diǎn)及其敏感．理想情況下，人們希望把彈簧和局外點(diǎn)隔開(kāi)，使得估計(jì)值不受傷害．改變彈簧常數(shù)使得局外點(diǎn)對(duì)估計(jì)值影響最小，可以實(shí)現(xiàn)基于影響函數(shù)的魯棒性預(yù)估．割斷彈簧與局外點(diǎn)的聯(lián)系對(duì)應(yīng)于再取樣策略，其中一致性子集取樣是確定的．再取樣方法是指重復(fù)抽取隨機(jī)子集并選擇可以產(chǎn)生最佳估計(jì)的子集．再取樣算法的例子包括隨機(jī)抽樣一致性、最小中值二次回歸、以及其它計(jì)算機(jī)中常用的回歸方法． 彈簧模擬方法推廣到線性回歸系統(tǒng)也有一樣的結(jié)論，即單一的局外點(diǎn)可以扭曲回歸估計(jì)．對(duì)第個(gè)數(shù)據(jù)點(diǎn)，n階線性多變量模型可以用下面的方程表示：

46、 (7．42) 其中是模型參數(shù)的估計(jì)值．每一點(diǎn)的殘差（預(yù)估模型數(shù)據(jù)點(diǎn)的微分）是．在最小二次回歸算法中，模型參數(shù)的估計(jì)由殘差平方和的極小化求得： (7．43) 同上述的彈簧模擬方法一樣，如果僅有一個(gè)數(shù)據(jù)點(diǎn)是局外點(diǎn)，模型參數(shù)可能是任意的． 通常，噪聲和局外點(diǎn)可以用聯(lián)合分布表示，即噪聲的正態(tài)分布和局外點(diǎn)的寬尾分布的線性組合．在這種情況下可以清楚的看到，預(yù)估器的范數(shù)同小誤差的最小二次范數(shù)一樣，同時(shí)對(duì)大誤差不敏感，這樣就可以忽略局外點(diǎn)的影響．這種方法稱為影響函數(shù)法． 為了定量說(shuō)明局外點(diǎn)對(duì)函數(shù)逼近的影響，我們引進(jìn)潰

47、點(diǎn)（breakdown point）這一術(shù)語(yǔ)。潰點(diǎn)是指局外點(diǎn)占整個(gè)數(shù)據(jù)的一個(gè)最小比例值，當(dāng)局外點(diǎn)數(shù)不超過(guò)這個(gè)值時(shí)，無(wú)論局外點(diǎn)如何不正確，都不會(huì)使預(yù)估算法產(chǎn)生任意的錯(cuò)誤估計(jì)[207]．設(shè)是個(gè)數(shù)據(jù)點(diǎn)的集合，將集合中任意個(gè)點(diǎn)的坐標(biāo)設(shè)置成任意值（局外點(diǎn)），構(gòu)成一個(gè)含有個(gè)任意點(diǎn)的集合．設(shè)一個(gè)回歸預(yù)估器，由局外點(diǎn)造成的預(yù)估偏差為： (7．44) 設(shè)置潰點(diǎn)的基本思想是定量分析局外點(diǎn)的數(shù)量在數(shù)據(jù)點(diǎn)數(shù)量n中所占比例增加時(shí)對(duì)Bias 值的影響程度．當(dāng)增加到一定數(shù)量時(shí)，Bias無(wú)界，這就是潰點(diǎn)．當(dāng)?shù)陀跐Ⅻc(diǎn)時(shí)，回歸估計(jì)器可以完全拒絕局外點(diǎn)，或使得局外點(diǎn)對(duì)預(yù)估結(jié)果影響很?。?dāng)高

48、于潰點(diǎn)時(shí)，局外點(diǎn)可以驅(qū)使預(yù)估器產(chǎn)生任意的解案，答案將取決于局外點(diǎn)而不是合法數(shù)據(jù)．換句話說(shuō)，預(yù)估器所提供的結(jié)果是不可預(yù)估的．潰點(diǎn)定義為： （7．45） 對(duì)于最小二次回歸，，在極限情況下，當(dāng)數(shù)據(jù)點(diǎn)數(shù)量變的很大時(shí)，．換句話說(shuō)，最小二次回歸方法對(duì)局外點(diǎn)無(wú)免疫能力，一個(gè)局外點(diǎn)即可毀掉結(jié)果． 最小二次中值回歸方法是一種非常簡(jiǎn)單的技術(shù)，并被證明是解決大量局外點(diǎn)回歸問(wèn)題的非常有效的方法，算法7．3概括了該算法。最小中值二次方法可以容錯(cuò)高達(dá)百分之五十的局外點(diǎn)，也就意味著數(shù)據(jù)點(diǎn)集內(nèi)，有一半的數(shù)據(jù)可以取任意值而不會(huì)嚴(yán)重地影響回歸結(jié)果．如果有多于百分之五十的點(diǎn)為局外點(diǎn)，最小二次回歸方法不

49、會(huì)工作的很好，此時(shí)需要更有效的方法，如Hough變換． 在最小中值二次回歸方法中，模型參數(shù)的估計(jì)由極小化殘差平方的中值求得： （7．46） 算法7．3 最小中值二次回歸方法 假定有n個(gè)數(shù)據(jù)和p個(gè)參數(shù)的線性模型 1. 在n各個(gè)數(shù)據(jù)點(diǎn)集中，隨機(jī)地選擇p個(gè)點(diǎn)． 2. 用模型擬合p個(gè)點(diǎn)． 3. 計(jì)算殘差平方的中值． 擬合過(guò)程重復(fù)進(jìn)行直到得到足夠小的殘差平方中值，或者達(dá)到預(yù)定的再取樣步長(zhǎng)數(shù)值． 7．5　Hough 變換 最近幾年，使用表決原理的參數(shù)估計(jì)技術(shù)應(yīng)用不斷增加．最常用的表決方法之一是Hough變換．在Houg

50、h變換中，曲線上的每一點(diǎn)可以表決若干參數(shù)組合，贏得多數(shù)表決的參數(shù)就是勝者．下面考慮一下直線擬合數(shù)據(jù)的方法．直線方程為： (7．47) 上述方程中，和是觀測(cè)值，和表示參數(shù)．如果已知參數(shù)值，則該點(diǎn)坐標(biāo)之間的關(guān)系即可確定．把上述方程重新表示為： (7．48) 假定和是我們感興趣的變量，而和是常數(shù)，則上述方程表示的是空間中的一條直線，斜率和截距由和決定．點(diǎn)對(duì)應(yīng)于空間的直線，如圖7．16(a)所示．如果直線上有個(gè)點(diǎn)，那么這些點(diǎn)對(duì)應(yīng)參數(shù)空間上的一個(gè)直線族，且所有直線都經(jīng)過(guò)上的一點(diǎn)，該

51、點(diǎn)的坐標(biāo)當(dāng)然反應(yīng)空間上的直線參數(shù), 如圖7．16(b)所示． 需要指出，參數(shù)空間曲線的形狀取決于用于表示曲線的原始函數(shù)．實(shí)際中，常常使用直線的極坐標(biāo)形式，而不是其顯式表示，這樣可以避免直線是垂直線時(shí)帶來(lái)的問(wèn)題．直線的極坐標(biāo)方程表示如下： (7．49) 上述方程中，點(diǎn)被映射到空間上，如圖7．16（c）所示．如果直線上有個(gè)點(diǎn)，那么這些點(diǎn)對(duì)應(yīng)參數(shù)空間上的一個(gè)正弦曲線族，且所有正弦曲線都經(jīng)過(guò)上的一點(diǎn)。 如果我們對(duì)求點(diǎn)的最佳直線擬合感興趣，那么，我們就可以使用上述圖像空間到參數(shù)空間的映射．這種方法稱為Hough變換．在這種方法中，我們把

52、參數(shù)空間表示為一個(gè)累加器陣列，表示離散參數(shù)值．依照變換方程，圖像中的每一點(diǎn)可以表決幾個(gè)參數(shù)．為了求出表征直線的參數(shù)，我們應(yīng)該探測(cè)參數(shù)空間的峰值．這種一般的想法概括在算法7．4中． 圖7．16 Hough變換示意圖。左邊為圖像空間，右邊為Hough變換空間。 （a）一條直線對(duì)應(yīng)一個(gè)點(diǎn)，(b) 一條直線上的多個(gè)點(diǎn)對(duì)應(yīng)多條交于一點(diǎn)的直線 (c) 一條直線上的多個(gè)點(diǎn)對(duì)應(yīng)多條交于一點(diǎn)的正弦曲線 (b) 圖7.17　Hough變換算法實(shí)驗(yàn)結(jié)果。（a）合成圖像，（b）直角坐標(biāo)參數(shù)空間映射圖，（c）　極坐標(biāo)參數(shù)空間映射圖

53、 算法7．4 Hough變換算法 1. 適當(dāng)?shù)亓炕瘏?shù)空間． 2. 假定參數(shù)空間的每一個(gè)單元都是一個(gè)累加器，把累加器初始化為零． 3. 對(duì)圖像空間的每一點(diǎn)，在其所滿足的參數(shù)方程對(duì)應(yīng)的累加器上加1． 4. 累加器陣列的最大值對(duì)應(yīng)模型的參數(shù)． Hough變換不需要預(yù)先組合或連結(jié)邊緣點(diǎn)．位于感興趣曲線上的邊緣點(diǎn)可能構(gòu)成圖像邊緣的一個(gè)小部分．特別指出，Hough變換可以允許位于曲線上的邊緣數(shù)量少于實(shí)際的邊緣數(shù)量，而大多數(shù)魯棒性回歸算法是無(wú)法適用這種情況．Hough變換所基于的假設(shè)是在大量噪聲出現(xiàn)的情況下，最好是在參數(shù)空間中去求滿足圖像邊緣最大數(shù)量的那個(gè)點(diǎn)．如果參數(shù)空間的峰

54、值包括了一個(gè)以上的累加器，則包含峰值的區(qū)域的矩心就是參數(shù)的一個(gè)估值． 利用上述算法的實(shí)驗(yàn)結(jié)果見(jiàn)圖 7.17 如果圖像中有幾條曲線和給定模型相匹配，則在參數(shù)空間中會(huì)出現(xiàn)幾個(gè)峰值．此時(shí)，可以探測(cè)每一個(gè)峰值，去掉對(duì)應(yīng)于某一個(gè)峰值的曲線邊緣，再檢測(cè)余下的曲線，直到?jīng)]有明顯的邊緣．但是，確定峰值的顯著性是件很困難的事． Hough變換的另一個(gè)問(wèn)題是離散參數(shù)空間隨著參數(shù)的數(shù)量增加迅速增加．對(duì)一個(gè)圓弧段，參數(shù)空間是三維的，對(duì)其它曲線，其維數(shù)可能更高．由于累加器的數(shù)量隨著參數(shù)空間的增加成指數(shù)增加，Hough變換可能對(duì)于復(fù)雜模型的計(jì)算效率很低．已經(jīng)提出幾種方法來(lái)改進(jìn)Hough變換的性能．一種方法是

55、使用邊界梯度信息來(lái)減少參數(shù)空間的工作量．假定曲線模型是圓．模型有三個(gè)參數(shù)，二個(gè)參數(shù)為圓的圓心坐標(biāo)，另一個(gè)是圓的半徑．如果可以得到邊緣梯度角，就可以提供減少自由度數(shù)量的約束，從而得到所要求的參數(shù)空間尺寸．從圓的中心到每一個(gè)邊緣點(diǎn)的向量方向由梯度角確定，剩下的未知參數(shù)只有圓的半徑．其它一些減少參數(shù)空間的方法也在視覺(jué)中得到應(yīng)用． 下面介紹一下使用梯度角減少參數(shù)尺寸的圓擬合方法。算法過(guò)程見(jiàn)算法7．5．圓的方程為： （7．50） 圓的極坐標(biāo)方程為： （7．51） 則圓的參數(shù)為：

56、 （7．52） 在邊緣點(diǎn)處給定梯度角θ，計(jì)算conθ和sinθ．從上述方程中消除半徑，得到： （7．53） 這是一個(gè)用于升級(jí)參數(shù)空間累加器的方程．對(duì)于每一個(gè)在處并具有邊緣方向角θ的邊緣點(diǎn)來(lái)說(shuō)，沿著方程7．53給定的直線，在參數(shù)空間給累加器一個(gè)增量．如果半徑已知，則只需由方程(7．52)在點(diǎn)處給累加器一個(gè)增量． 這里無(wú)需使用參數(shù)來(lái)描述由Hough變換檢測(cè)的曲線．Hough變換可以一般化為表決算法（見(jiàn)算法7.6），這種算法可以有效地完成模板匹配．算法7．6把物體的邊界形狀編碼成表，以便有效地進(jìn)行讀取操作

57、．其中物體上的一點(diǎn)被選為參考點(diǎn)．根據(jù)定義，圖像中參考點(diǎn)的位置就是物體的位置．對(duì)于每一個(gè)在處并具有梯度角θ的圖像梯度點(diǎn)，參考點(diǎn)可能的位置有下面的方程給出： （7．54） 給每一個(gè)可能的參考點(diǎn)的位置一個(gè)增量．參數(shù)空間的峰值位置是物體位置的一個(gè)估計(jì)．把這一技術(shù)推廣到可以處理尺度和旋轉(zhuǎn)變換不太容易． 算法7．5 圓擬合算法 1. 量化參數(shù)空間a和b． 2. 置累加器陣列為零． 3. 計(jì)算梯度值和角． 4. 對(duì)于中的每一個(gè)邊緣點(diǎn)，沿著直線（見(jiàn)方程7.53）給累加器陣列中的所有點(diǎn)一個(gè)增量． 5. 累加器中局部最大值對(duì)應(yīng)于圖像中的圓中

58、心． 算法7．6廣義Hough變換算法 1. 在物體上取出一個(gè)參考點(diǎn)． 2. 沿著物體的邊界計(jì)算梯度角． 3. 對(duì)每一個(gè)梯度角，存儲(chǔ)對(duì)于參考點(diǎn)的距離和角度． 7．6 傅里葉描述子 由于沿著封閉輪廓的位置函數(shù)是周期性的，因此傅里葉級(jí)數(shù)可以用來(lái)逼近輪廓．輪廓逼近的分辨率由傅里葉級(jí)數(shù)的項(xiàng)數(shù)來(lái)確定． 假定物體的邊界表示為一個(gè)坐標(biāo)的序列，其中．用復(fù)數(shù)來(lái)表示每一個(gè)坐標(biāo)對(duì)，即 （7．55） 其中 ． 換句話說(shuō)，x軸為實(shí)軸，y軸是復(fù)數(shù)序列的虛軸．注意，對(duì)于封閉邊界，這一序列是周期的，其周期是N，這樣，邊界就可以在一維空間表示． 一維序

59、列函數(shù)的離散傅里葉變換（DFT）定義為： （7．56） （7．57） 復(fù)數(shù)系數(shù)稱為邊界的傅里葉描述子． 傅里葉描述子是輪廓表示的簡(jiǎn)潔表示方法．然而，更簡(jiǎn)潔的表示形式是使用傅里葉序列的低階項(xiàng)的低分辨率逼近．如果僅使用前個(gè)系數(shù)，即等同于，則對(duì)的逼近如下： （7．58） 盡管僅使用項(xiàng)來(lái)求邊界的每一項(xiàng)，仍然取0到的區(qū)間．換句話說(shuō)，被逼近的邊界具有相同的點(diǎn)數(shù)，但用于重建每一個(gè)點(diǎn)的項(xiàng)數(shù)不同． 邊界的簡(jiǎn)單幾何變換，如平移、旋轉(zhuǎn)和尺度變換，將關(guān)系到邊界傅里葉描述子的簡(jiǎn)單操作（見(jiàn)練習(xí)7．19）．這使得傅里葉描述子在邊界匹配中的應(yīng)

60、用非常具有吸引力．然而，傅里葉描述子在描述具有遮擋物體是的確存在一些問(wèn)題．使用其它邊界表示也可以得到類似的描述子． 習(xí)題 7.1 什么是輪廓？輪廓與區(qū)域有什么關(guān)系？一個(gè)非封閉輪廓表示什么？ 7.2 請(qǐng)列出選擇輪廓表示的判據(jù)，并討論這些因素在物體識(shí)別中的含義． 7.3 插值和逼近方法有何區(qū)別？那一種方法更好？ 7.4 為了完成的旋轉(zhuǎn)，可能使用16方向的鏈碼編碼．你如何來(lái)完成這一編碼？為什么8方向鏈碼是最常用的鏈碼？ 7.5 逆時(shí)針求取圖7．19所示物體的8-方向鏈碼和鏈碼差分，其中的空心圓點(diǎn)是起點(diǎn)． 圖7.19 思考題7．5的輪廓 7.6 考慮一下7．8．2

61、節(jié)的角點(diǎn)位置估計(jì)方法．當(dāng)兩條直線成直角時(shí)，的值是多少？當(dāng)兩條直線成某一角度θ時(shí)，又為何值？（這是用于設(shè)置角點(diǎn)探測(cè)閾值的公式） 7.7 考慮一下7．8．2節(jié)的角點(diǎn)位置估計(jì)方法．假定邊緣位置x和y的坐標(biāo)誤差服從方差為的正態(tài)分布．角點(diǎn)的位置誤差分布是什么？角點(diǎn)對(duì)應(yīng)的角度是如何影響該誤差的？ 7.8 產(chǎn)生一個(gè)相對(duì)于均勻背景的均勻強(qiáng)度的人工圖像．請(qǐng)使用第五章任何一種邊緣檢測(cè)器計(jì)算邊緣，并用多線段擬合邊緣．請(qǐng)問(wèn)所求得的頂點(diǎn)與真實(shí)角點(diǎn)位置的差距有多大？這種誤差是否一定偏向一個(gè)方向？ 7.9 為什么圖被認(rèn)為是連續(xù)鏈碼？其最吸引人的特點(diǎn)是什么？ 7.10 如何使用圖來(lái)比較兩個(gè)物體？ 7.11 討論一

62、下你所使用的不同的逼近算法誤差測(cè)量．請(qǐng)問(wèn)在逼近算法中，誤差算法測(cè)量起什么作用？ 7.12 為什么說(shuō)三次樣條相對(duì)于多線段和圓錐曲線段是一種更有效的表示方法？ 7.13 試論述幾何等效和參數(shù)等效的差別． 7.14 為什么在全回歸方法中使用最小二次測(cè)量方法？試列出它的優(yōu)點(diǎn)和缺點(diǎn)． 7.15 試說(shuō)明魯棒性方法是如何克服全回歸方法的局限性？為什么魯棒性方法在逼近算法中用的不是很普遍？ 7.16 傅里葉描述子在逼近和表示封閉曲線時(shí)的優(yōu)點(diǎn)和弱點(diǎn)是什么？ 7.17 什么是Hough變換？它是否與魯棒性回歸方法有關(guān)？為什么？ 7.18 你能把Hough變換推廣到檢測(cè)任意物體形狀？如何把Hough變

63、換用于探測(cè)旋轉(zhuǎn)和尺度變換后的物體？ 上機(jī)作業(yè)題 6.1 編制一個(gè)程序求一條給定曲線的鏈碼．你能否利用鏈碼來(lái)確定角點(diǎn)？如果能，請(qǐng)完成這一算法，并用幾幅圖像來(lái)測(cè)試． 6.2 編制一個(gè)用Hough算法檢測(cè)圖像中的直線算法．使用這一算法來(lái)求一幅圖像中的所有大于規(guī)定長(zhǎng)度的直線段，設(shè)規(guī)定的長(zhǎng)度為20點(diǎn)． 6.3 請(qǐng)產(chǎn)生一幅在均勻背景下的具有均勻灰度的矩形物體圖像，使用第五章中任何一種邊緣檢測(cè)方法檢測(cè)矩形物體的邊緣，并用多線段擬合這一邊緣．請(qǐng)問(wèn)多線段中的頂點(diǎn)與真實(shí)的角點(diǎn)接近的程度如何？這些頂點(diǎn)與真實(shí)角點(diǎn)的偏差是否總是在一個(gè)方向上？ 6.4 請(qǐng)產(chǎn)生一幅四個(gè)角點(diǎn)都為圓角的矩形圖像，圓角可用四分圓表示．

64、首先使用邊緣探測(cè)和多線段擬合，然后使用本章介紹的圓弧段擬合方法替代多線段擬合，并測(cè)量圓弧段端點(diǎn)處的誤差．誤差是否對(duì)稱？是否角點(diǎn)不均勻使得矩形變的扭曲？ 6.5 完成用于直線擬合邊緣點(diǎn)集表的最小中值二次回歸算法．在邊緣點(diǎn)集表中增加假邊緣，以模擬成組誤差．請(qǐng)畫(huà)出估計(jì)線段與真實(shí)線段之間的距離相對(duì)于假邊緣數(shù)量的曲線． 6.6 考慮一個(gè)相對(duì)于一個(gè)垂直軸對(duì)稱的物體．假定可以得到物體左右兩邊的兩個(gè)邊緣段表．采取一種三次樣條擬合邊緣的算法以確保這一對(duì)稱性約束，并把這一算法推廣到軸在任意一個(gè)位置． 6.7 假定可以得到一個(gè)相對(duì)于某一個(gè)軸是對(duì)稱的物體的輪廓邊緣點(diǎn)集表．把邊緣表處理成一個(gè)直線段和圓弧段序列．編制一個(gè)匹配直線段和圓弧段算法來(lái)檢測(cè)物體是對(duì)稱的，并估計(jì)出對(duì)稱軸．在確定對(duì)稱軸以后，用這一信息來(lái)改善直線段和圓弧段的估計(jì)．請(qǐng)編制一個(gè)細(xì)化輪廓表示的算法．做迭代算法探測(cè)對(duì)稱軸的實(shí)驗(yàn)，用這一信息細(xì)化輪廓表示，然后用改進(jìn)的輪廓表示細(xì)化軸位置估計(jì)，重復(fù)這一過(guò)程，直到軸和輪廓表示收斂． 專心---專注---專業(yè)