第七章 輪廓表示

稻草人自動(dòng)化培訓(xùn)稻草人自動(dòng)化培訓(xùn)第七章輪廓表示把邊緣連接起來就成為輪廓(contour).輪廓可以是斷開的，也可以是封閉的，封閉輪廓對(duì)應(yīng)于區(qū)域的邊界，而區(qū)域內(nèi)的象素可以通過填充算法來填滿，斷開的輪廓可能是區(qū)域邊界的一部分，也可能是圖像線條特征，如手寫體筆畫、圖畫中的線條等，區(qū)域之間的對(duì)比度太弱或邊緣檢測(cè)閾值設(shè)置太高都有可能產(chǎn)生間斷的輪廓。輪廓可以用邊緣序列表或曲線來表示，曲線通常稱為輪廓的數(shù)學(xué)模型，曲線表示包括線段、二次曲線、三次樣條曲線等，下面幾種輪廓表示的評(píng)價(jià)標(biāo)準(zhǔn)：高效：輪廓應(yīng)該是一種簡潔的表示。精確：輪廓應(yīng)能精確地逼近圖像特征。有效：輪廓應(yīng)適合于后處理階段的計(jì)算。輪廓表示的精確性由以下三個(gè)方面因素決定：①用于輪廓建模的曲線形式；②曲線擬合算法的性能；③邊緣位置估計(jì)的精確度，輪廓的最簡單表示形式是邊緣有序表，這種表示的精確度就是邊緣估計(jì)的精確度，但其表示的緊湊性是最差的，因此不是一種高效的圖像分析表示方法.用適當(dāng)?shù)那€模塑來擬合邊緣會(huì)提髙精確度，這是因?yàn)榍€模型擬合邊緣時(shí)往往具有均值化效應(yīng)，因而可以減少邊緣位置誤差.曲線模型也會(huì)提高輪廓表示的經(jīng)濟(jì)性，為后處理提供了一種更簡單、更緊湊的表示，例如，一條直線上的邊緣集用一直線來擬合是表示這些邊緣的最簡單和最有效的方法，這一表示也簡化了后處理(如確定線的長度和方向)；另外，由于估計(jì)直線與真實(shí)直線的均方差小于真實(shí)直線與任何其它邊緣之間的均方差，因此可以說這種表示也增加了精確度.輪廓曲線擬合通常采用內(nèi)插曲線或逼近曲線來實(shí)現(xiàn)，已知一組稱為控制點(diǎn)的坐標(biāo)點(diǎn)，內(nèi)插是指一條曲線擬合這組控制點(diǎn)，使得曲線通過所有的控制點(diǎn)；逼近是指一條曲線擬合這組控制點(diǎn)，使得這條曲線非常接近這些控制點(diǎn)而無需一定通過這些點(diǎn)，在下面幾節(jié)中，假定由邊緣檢測(cè)器得到的邊緣十分準(zhǔn)確，并使用內(nèi)插值方法進(jìn)行邊緣曲線擬合.在無特別說明的情況下，邊緣通常是指邊緣點(diǎn).對(duì)大多數(shù)曲線擬合算法來說，只需要邊緣的位置信息.在很少的幾種情況下，既鋪要邊緣位置信息，也需要方向信息，此時(shí)的邊緣稱為邊緣段.平面曲線函數(shù)可以表示為三種形式：顯式y(tǒng)=f(x);隱式f(x,y);或參數(shù)式(x(u),y(u)),其中u是某一參數(shù)?函數(shù)的顯式表示很少用在機(jī)器視覺中，主要原因是平面上的曲線可能卷曲，使得一個(gè)x值可能對(duì)應(yīng)曲線上多個(gè)y值.數(shù)字曲線及其表示本節(jié)將討論一組計(jì)算曲線幾何元素的算法，幾何元素包括輪廓長度、正切方向和曲率等.由于相鄰象素之間的量化增量是45°,因此，精確計(jì)算斜率和曲率是很困難的.估計(jì)正切方向的基本思路是使用邊緣表中非鄰接的邊緣點(diǎn)，這就允許存在一個(gè)較大的可能的正切方向集合，設(shè)二■尤"兒)是邊緣表中第i個(gè)邊緣坐標(biāo)，k斜率是在邊緣表相距k個(gè)邊緣點(diǎn)的兩個(gè)邊緣點(diǎn)之間的方向矢量，左k斜率是指向p的方向，右k斜率i-k是"［指向p方向，k曲率是左右k斜率之差值。i+k

假定在邊緣表中有n個(gè)邊緣（x,y）,（x,y）,???，（x,y）數(shù)字曲線的長度1122nn可以近似為象素之間的線段和s=￡y-x^,）2+（兒-）2（7.1）輪廓端點(diǎn)之間的距離為/d=丿（兀一知y+（兒一戸F（1.2}7.1.1鏈碼鏈碼是沿著輪廓記錄邊緣表的一種表示方法.鏈碼規(guī)定了邊緣表中每一個(gè)邊緣點(diǎn)所對(duì)應(yīng)的輪廓方向，其中的輪廓方向被量化為4鄰點(diǎn)鏈碼或8鄰點(diǎn)鏈碼也稱4方向鏈碼或8圖7?1連接邊緣點(diǎn)方向的鏈碼示童圖（a）4鄰點(diǎn)鏈碼;（b）8鄰點(diǎn)鏈碼圖王2—條曲線及其8鄰點(diǎn)鏈碼表示方向鏈碼，如圖7.1所示.圖7.2所示的是一條曲線及其8鄰點(diǎn)鏈碼的表示，8鄰點(diǎn)鏈碼從一個(gè)邊緣點(diǎn)開始，沿著輪廓按逆時(shí)針方向行走，行走方向用八個(gè)鏈碼中的一個(gè)表示。

i1i1ii—□A■i\LIJ?.I二二一2twrL*2圖7.3圖7.2曲線逆吋針轉(zhuǎn)妙及其8鄰點(diǎn)饒瑪表示鏈碼有一些很特殊的性質(zhì).一個(gè)物體很容易實(shí)現(xiàn)45°角旋轉(zhuǎn).如果一個(gè)物體旋轉(zhuǎn)nX45。，旋轉(zhuǎn)后的物體鏈碼可由原鏈碼加上n倍的模8得到?鏈碼的微分，也稱差分碼，可由原碼的一階差分求得.鏈碼差分是關(guān)于旋轉(zhuǎn)不變的邊界描述方法.比如，圖7.2曲線的鏈碼是:60222220210134444454577012其真差分鏈碼是2200006277121000017120111圖7.3是圖7.2曲線逆時(shí)針旋轉(zhuǎn)90°后得到的，曲線的鏈碼是：024444424323566666676711234其差分鏈碼是：22000062771210000017120111由此可見，一條曲線旋轉(zhuǎn)到不同的位置將對(duì)應(yīng)不同的鏈碼，但其差分鏈碼不變，即差分鏈碼關(guān)于曲線旋轉(zhuǎn)是不變的。區(qū)域的一些其它性質(zhì)，如面積和角點(diǎn)，也可以由鏈碼直接求得.這種表示的局限性是表示某一點(diǎn)正切方向的集合是有限的（4鄰點(diǎn)鏈碼有4個(gè)，8鄰點(diǎn)鏈碼有8個(gè)），這一局限性可以通過下面幾節(jié)介紹的曲線表示方法來克服.7.1.2斜率表示法用任意的正切方向來表示輪廓可以克服鏈碼的有限正切方向表示輪廓的局限性.假定從邊緣表開始，使用上面給出的公式計(jì)算正切和弧長，可以畫出正切①同弧長s關(guān)系圖，稱作es圖，es圖是輪廓形狀在①s空間的表示，是一種輪廓形狀的緊湊描述.圖7.4所示的是包含有直線段和圓弧段的輪廓在es空間中的表示，它是一個(gè)直線段序列.對(duì)于封閉輪廓，es圖是一個(gè)周期曲線?在es圖中，水平方向的直線段對(duì)應(yīng)輪廓中的直線段，這是由于直線段對(duì)應(yīng)的斜率是恒定值.其它方向的直錢段對(duì)應(yīng)圓弧段，非直線段部分對(duì)應(yīng)曲線基元.

圖7-4輪廓的斜率表7T如果把①S圖分割成直線段，也就把輪廓分割成直線段和圓弧段.許多研究人員采用這一方法來分割輪廓，由此產(chǎn)生了多種輪廓分段方法.曲線擬合本章將討論三種常用的曲線模型擬合邊緣點(diǎn)的方法：直線段，圓錐曲線段和三次樣條曲線段.一般來說，在用曲線模型擬合邊緣點(diǎn)之前應(yīng)考慮如下兩個(gè)問題：用什么方法進(jìn)行邊緣點(diǎn)曲線模型擬合？如何測(cè)量擬合的逼近程度？下面幾節(jié)將討論曲線模型擬合邊緣點(diǎn)方法，其中假設(shè)邊緣位置足夠精確，不會(huì)對(duì)擬合結(jié)果產(chǎn)生影響.設(shè)dl是邊緣點(diǎn)到一條擬合曲線的距離，該距離值有正負(fù)符號(hào)，在曲線同一側(cè)的邊緣具有相同的正負(fù)符號(hào).目前有許多種擬合曲線與候選邊緣點(diǎn)擬合效果的測(cè)量方法，每一種都取決于擬合曲線和候選點(diǎn)之間的誤差.下面是一些常用的方法.(7.3)最大絕對(duì)誤差(maximumabsoluteerror,MAE)(7.3)MAE=maxid.I均方差(meansquarederror，MSE)給出邊緣點(diǎn)偏離擬合曲線的總的測(cè)度(7.4)規(guī)范化最大誤差(normalizedmaximumerror，NME)最大絕對(duì)誤差與曲線長度S之比稻草人自動(dòng)化培訓(xùn)稻草人自動(dòng)化培訓(xùn)稻草人自動(dòng)化培訓(xùn)稻草人自動(dòng)化培訓(xùn)稻草人自動(dòng)化培訓(xùn)稻草人自動(dòng)化培訓(xùn)(79稻草人自動(dòng)化培訓(xùn)(79稻草人自動(dòng)化培訓(xùn)(7+5)max|d-I(7+5)誤差符號(hào)變化次數(shù)這里的誤差就是指4，即邊緣點(diǎn)偏離擬合曲線的距離.誤差符號(hào)變化次數(shù)可作為輪廓邊緣模型與邊緣點(diǎn)曲線適合程度的測(cè)度.曲線長度與端點(diǎn)距離之比曲線復(fù)雜程度的測(cè)度.符號(hào)變化是一種評(píng)價(jià)擬合好壞的很有用的參數(shù).比如，用直線段逼近邊緣表.如果符號(hào)變化一次，則說明邊緣點(diǎn)可以由直線段來逼近，符號(hào)變化兩次，說明邊緣可以由二次曲線逼近，符號(hào)變化三次，說明邊緣模型是三次曲線，依此類推.如果符號(hào)變化數(shù)量很大，則意味著曲線復(fù)雜度增加一點(diǎn)將不能顯著地改善擬合效果.一種好的擬合所對(duì)應(yīng)的符號(hào)變化具有隨機(jī)模式.相同符號(hào)連續(xù)出現(xiàn)多次說明存在擬合系統(tǒng)誤差，這種誤差可能是由于錯(cuò)誤的曲線模型引起的。曲線擬合模型的選擇取決于應(yīng)用場合.如果場景是由直線段組成，則使用直線段（或多線段）模型比較合適。直線段模型也可作為其它擬合模型的初始擬合模型.圓弧段是估計(jì)曲率的最有用的一種表示，因?yàn)榍€可以分割成具有分段恒定曲率的曲線段.圓錐曲線段是一種表示直線段和圓弧段序列以及橢圓和高次弧段序列的有效方法.三次樣條曲線適合于平滑曲線模型，因?yàn)槿螛訔l曲線并不要求正切矢量和曲率的估計(jì)值一定是分段恒定的。7.2.1多直線段多直線段是指端點(diǎn)連接端點(diǎn)的直線段序列，直線段序列的連接點(diǎn)稱為頂點(diǎn).多直線段適合具有線段序列的邊緣列表的擬合?多線段算法的輸入值是邊緣點(diǎn)有序表｛（X1,yi），（x2,y）,???，（x,y）｝。邊緣點(diǎn)坐標(biāo)可以計(jì)算到子象素精度.由于線段的兩個(gè)端點(diǎn)對(duì)應(yīng)兩個(gè)2nn邊緣點(diǎn)，即線段擬合在這兩個(gè)邊緣點(diǎn)之間進(jìn)行，因此僅需要精確計(jì)算對(duì)應(yīng)端點(diǎn)的兩個(gè)邊緣點(diǎn)的坐標(biāo)。擬合邊緣表并把第一個(gè)邊緣點(diǎn)（x，y）和最后一個(gè)邊緣點(diǎn)（x，y）連接起來的直線11kk段公式如下：(7.6)上式可以改寫為由端點(diǎn)表示的隱武函數(shù)（7-7）Ax+Uy+（7-7）其中A=（y*-Ji）B-（xk-C=x｝yk-xkyA而D=vzA2+是邊緣點(diǎn)（利，門）和（秤，yJ之間的距離.任給一點(diǎn)（龜』J,設(shè)r二血：+0竹+G則r的符號(hào)可用來計(jì)算符號(hào)變化次數(shù).點(diǎn)（旺,譏）與擬合直線段的距離為(7.8)規(guī)范化最大誤差為maxIdLI

￡-—__D~~~

規(guī)范化最大誤差常作為線段擬合邊緣列表好壞的置度.需要指出，上面的公式都是在點(diǎn)向直線段的垂直投影落在線段內(nèi)這個(gè)假設(shè)下進(jìn)行的.對(duì)于其它情況,則應(yīng)修正公式，以便計(jì)算點(diǎn)到最近的線段端點(diǎn)的距離.下面介紹兩種擬合多線段的方法：自頂面下的分裂和自底而上的合并.多直線段分裂自頂而下的分裂算法(top-downsplitting)是將整條曲線作為初始曲線，通過反復(fù)增加頂點(diǎn)數(shù)來進(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來標(biāo)記，從而形成兩個(gè)擬合直線段AC和CB,邊緣表也分割成對(duì)應(yīng)于兩個(gè)新直線段的兩個(gè)子邊緣表?在每一個(gè)子邊緣表中，重復(fù)上面所述的分裂算法，形成兩個(gè)新的直線段及對(duì)應(yīng)的兩個(gè)更小的子邊這樣的分裂過程可以一直進(jìn)行下去，直到所有的直線段對(duì)應(yīng)的規(guī)范化最大誤差均低于某一庖值為止?多線段分裂也稱為迭代分解。線段合并線段合并(merging)是指用一條直線段盡量多地?cái)M合邊緣表中的邊緣點(diǎn).當(dāng)邊緣點(diǎn)離直線段太遠(yuǎn)而無法用該直線段擬合時(shí)，則開始新的直線段擬合.合并方法也稱為自底而上合并(boltom-upmerging)的多線段擬合方法.圖7』多直線段分裂方法確定邊緣點(diǎn)離直線段的距離有許多種方法.一種方法是使用序貫最小二乘法，完成直線段到邊緣點(diǎn)的最小二乘法擬合，并在每次處理新的邊緣點(diǎn)時(shí)遞增地更新線段參數(shù).擬合算法將計(jì)算邊緣點(diǎn)與直線段模型之間的偏差(殘差)平方.當(dāng)偏差超過某一閾值時(shí)，引進(jìn)一圖7』多直線段分裂方法個(gè)頂點(diǎn)，并將上—個(gè)線段的端點(diǎn)作為新的起點(diǎn)開始新的直線段擬合。誤差帶算法是另一種確定頂點(diǎn)位置的方法，如圖7.6所示，主要工作是計(jì)算兩條平行且離中心線距離為￡的直線段，￡值表示離中心直線的絕對(duì)偏離值，擬合直線段就位于誤差帶內(nèi).當(dāng)新的邊緣在誤差帶內(nèi)，就可以用當(dāng)前擬合直線表示該邊緣，然后重新計(jì)算誤差帶的位置.擬合直線段不必與誤差帶邊保持平行.位于線段端點(diǎn)的頂點(diǎn)是下一線段的起點(diǎn).顯然，這一方法常產(chǎn)生大量的線段.由于擬合直線段行進(jìn)到誤差帶邊界時(shí)才產(chǎn)生角點(diǎn)，因此，不能精確估計(jì)角點(diǎn)位置和角度。分裂和合并自頂而下的迭代分解方法和自底而上的合并方法組合起來，形成合并和分裂算法.單獨(dú)使用分裂或合并算法時(shí)，成功率往往不是很高，改進(jìn)的方法是交叉使用分裂和合并算法.分解過程以后，如果新的線段能以很小的規(guī)范化誤差擬合邊緣，則可用單一直線段代替相鄰的幾個(gè)線段.請(qǐng)注意，由于多直線段總是比單直線段的擬合誤差小，因此很有必要使用規(guī)范化誤差.在線段合并后，新的線段可能在不同點(diǎn)處分裂.這樣，分裂和合并交替作用直到?jīng)]有一種有效的分裂和合并算法是從邊緣表中的前k個(gè)邊緣構(gòu)成的子列表開始，而不是整個(gè)邊緣列表.用直線段擬合子表中第一和最后一個(gè)邊緣點(diǎn)之間的邊緣點(diǎn).如果某點(diǎn)的規(guī)范化最大誤差太大，則將子列表縮到最大誤差對(duì)應(yīng)的邊緣點(diǎn)處，這樣一直進(jìn)行下去，就可以得到第一條擬合直線段，這實(shí)際上是分裂算法.置當(dāng)前擬合的直線段為舊線段，再在剩下的邊緣點(diǎn)集中取前k個(gè)邊緣構(gòu)成新子列表，用分裂算法求取第二條擬合直線段.比較當(dāng)前直線段和原直線段的方向，如果它們具有相似的方向，則將這兩條直線段合并，這是合并算法。實(shí)際的輪廓曲線并不全是由直線段組成，可能還包含有各種弧線或肖由曲線.因此，僅使用直線段得到的擬合結(jié)果比較粗糙，人們自然想到了用弧線段逼近.通常的弧線有二次、三次或更高次的曲線，這些通稱為多項(xiàng)式曲線，下面主要討論次曲線和三次樣條曲線.7.2.2二次曲線下面討論如何用二次曲線逼近邊緣表.二次曲線的一般表示如下

二次曲線也稱圓錐曲線，因?yàn)槎吻€都是用平面切割正圓錐面的截線，如圖7.8所示.若平面不通過錐頂，且不平行任一母線,則截線為橢圓，其中圓是橢圓的一種特殊情況，此時(shí)的平面垂直于錐軸；若平面不通過錐頂?shù)叫杏谝粭l母線時(shí)，截線為拋物線；若平面不通過錐頂，且平行于錐軸，截線為雙曲線.當(dāng)平面通過錐頂時(shí),橢圓變?yōu)橐稽c(diǎn)，雙曲線變?yōu)橐粚?duì)相交的直線，拋物線變?yōu)榕c圓錐相切的一條直線.由此可見，使用二次曲線來逼近數(shù)字輪廓曲線，可以有效地?cái)M合數(shù)字曲線中的直線和圓弧等各種二次曲線.由于二次曲線中除了特殊的直線外，最簡單的情況是圓弧，因而得到了大量的研究.我們將單獨(dú)討論圓弧逼近方法.圓弧段雙曲線如，用直線用直線段逼近邊緣表以后，其中的一些直線段序列可以由圓弧段來代替，比段擬合一個(gè)圓弧可能需要許多個(gè)直線段才能滿足擬合誤差，如果對(duì)這些樹段用圓弧段來擬合，則僅需要一條圓弧段即可，因此可見，圓弧段擬合此直線段能擬合得更緊湊，下面討論的圓弧擬合是在多邊形頂點(diǎn)上進(jìn)行的?！p曲線如，用直線具有半徑r和圓心坐標(biāo)（x°，y）的圓弧隱式方程為（%-x0）2+（y-y0）2=r2（7-11）考慮三點(diǎn)Pi=（街，加），pg=（如，咒），戸3=（知，旳），不失一般性，設(shè)Pi位于羋標(biāo)原點(diǎn)，即X）=0,/j=0.把點(diǎn)pi+p2,p3代人上述方程得xl+Jq-r2=a（叼—%o）2+（兀一刑）2lF二0（7,12j（叭-肌尸+-r2=0分別用第一和第三方程減去第…方程，得到如下兩個(gè)方程：2x2x0+2y2y0=於+處2也％』+——這是兩個(gè)關(guān)丁未知參數(shù)恥，九的非線性方程，求解坯，九，即可由（7.12）的第-個(gè)式子得到圓的半徑。為了計(jì)算圓弧擬合誤差，將點(diǎn)◎到圓的距離定義為沿著通過圓心直線方向的點(diǎn)Q與惻的距離,計(jì)算點(diǎn)03，“到圓中心（磯）的距離g=xG）-+-h,）"（7.14）點(diǎn)Q到圓弧段的距離是d=q-r（7,15）用圓弧段擬合多直線段時(shí)，圓弧段的網(wǎng)個(gè)端點(diǎn)要經(jīng)過多直線段的某構(gòu)個(gè)頂點(diǎn)，第三個(gè)點(diǎn)位于這兩個(gè)頂點(diǎn)之間，第三個(gè)點(diǎn)可能有如下幾種情況：離兩個(gè)頂點(diǎn)定義的直線最遠(yuǎn)的多直線段頂點(diǎn)；離兩個(gè)頂點(diǎn)定義的直線最遠(yuǎn)的邊緣點(diǎn)；兩個(gè)頂點(diǎn)之間所有頂點(diǎn)的中點(diǎn)；兩個(gè)頂點(diǎn)之間所有邊緣的中點(diǎn)。計(jì)算所有邊緣點(diǎn)和圓弧段之間的距離誤差，檢查最大絕對(duì)誤差和符號(hào)變化次數(shù)，如果規(guī)范化最大誤差低于某一閾值，而符號(hào)變化次數(shù)很大,則接受這一圓弧段；否則，保留多線段逼近?關(guān)于圓弧段逼近的文獻(xiàn)很多,感興趣的讀者可以參見文獻(xiàn)［Jiar1992,Chen1996］。用直線段和圓弧段可以有效地表示數(shù)字輪廓曲線，但是用兩種不同的線段基元表示輪廓會(huì)造成不便.下一節(jié)討論的圓錐曲線允許直線段、圓弧段和其它基元共同出現(xiàn)在同一種表示中.圓錐曲線段表示也提供了曲線之間平滑過渡的方法,也是角點(diǎn)的顯式表示。圓錐曲線圓錐曲線可以擬合輪廓多直線段上的三個(gè)頂點(diǎn).將圓錐曲線段連接在一起的點(diǎn)稱為結(jié)點(diǎn).圓錐樣條曲線是圓錐曲線的一個(gè)序列,它們的端點(diǎn)和端點(diǎn)連接在一起,在結(jié)點(diǎn)處具有相等的正切，使兩個(gè)鄰接曲線段之間平滑過渡?設(shè)多直線段端點(diǎn)為Vj,圓錐逼近如圖7.9所示。圖由三點(diǎn)定義的圓錐曲線逼近圓錐樣條中的每一個(gè)圓錐曲線由兩個(gè)端點(diǎn)、兩個(gè)正切和第三點(diǎn)確定.結(jié)點(diǎn)位于多線段頂點(diǎn)之間K=(1-；+凋+i⑺⑹其中叫取土和［之間的遨值.正切由三個(gè)頂點(diǎn)化山+1和v［+2tE成的三角形來定義.第三f如圖7-商示，由下面式子計(jì)算：乙=yj；+1+(1—兒)'(7.17)

基也雖Lffi丄M間的數(shù)值.有幾種特殊的情況可以通過如下方法來處理.如果p[+1=0,那么第i個(gè)圓霍蔭礦臭?到％"的直線段.如果叫=1和p1+1"，那么&,K占和卩“對(duì)應(yīng)于同一點(diǎn)，在圓傕曲線序列中有一個(gè)角點(diǎn)?這些性質(zhì)使得直線段和角點(diǎn)可以明顯地表示出來，無需求助于不同的基元和特殊的標(biāo)志.圖7.11圓錐曲線的導(dǎo)旬形式示意圖由兩個(gè)喘點(diǎn)、三頂.點(diǎn)構(gòu)成的正切和第二點(diǎn)定文的圓卷曲線這里所示的計(jì)算圓錐樣條算法使用了一個(gè)圓錐曲線的引導(dǎo)形式，以表示由三條直線約束的圓錐曲線，如圖7.11圖7.11圓錐曲線的導(dǎo)旬形式示意圖由兩個(gè)喘點(diǎn)、三頂.點(diǎn)構(gòu)成的正切和第二點(diǎn)定文的圓卷曲線這里所示的計(jì)算圓錐樣條算法使用了一個(gè)圓錐曲線的引導(dǎo)形式，以表示由三條直線約束的圓錐曲線，如圖7.11所示.直線方程為設(shè)多直線段中的第一和最后一個(gè)頂點(diǎn)為A和B,C是多線段的中間頂點(diǎn)，用弦連AB連接第一和最后一個(gè)頂點(diǎn)?圓錐曲線導(dǎo)向形式是端點(diǎn)位于A和B的圓錐曲線族，正切AC和BC由下面方程定義（a0+?|%4-a2y）（60++i2y）=卩（珈+me+一吐『）~（7.19）其中rz?+aYxi-a2y=0是包含直線段AC的直線；bn+bfx+b2y=0是包含直線段BC的直線；牝+明工十U2y=0是包含弦AB的直線.圓錐曲線族由參數(shù)p來定義?圓錐曲線擬合邊緣表的算法是從直線段開始的■頂點(diǎn)分為角點(diǎn)（tom亡r）、軟頂點(diǎn)（^i際rt傑）和結(jié)點(diǎn)（knot）二類-軟頂點(diǎn)對(duì)應(yīng)的角接近180°,相鄰的直線段幾乎共線，并町以用圓錐曲線來代替.軟頂點(diǎn)序列對(duì)應(yīng)于緩變方向角的直線段序列,很可能是對(duì)光滑曲線的采樣點(diǎn)進(jìn)行擬合的結(jié)果?角點(diǎn)對(duì)應(yīng)的頂點(diǎn)角大180°+',或小于180°-T]，其中'是閾值，角點(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)V和V的角度分別是A和A.如果ii+1ii+1A=A，那么結(jié)點(diǎn)可以位于頂點(diǎn)的中間，也就是說，在式（7.16）中V1/2.由于圓錐曲線ii+1不可能偏離直線段而足夠迅速地彎曲去跟蹤角點(diǎn)，因此如果角度不相等，那么，結(jié)點(diǎn)位置應(yīng)該偏離具有較大角度的那個(gè)角點(diǎn)?式（7.16）的V值可以由下式計(jì)算(7.20)由軟頂點(diǎn)連接的每一個(gè)直線段序列可由穿過第一和最后一個(gè)頂點(diǎn)（或結(jié)點(diǎn)）的導(dǎo)向圓錐代替.第一和最后一個(gè)直線段的方向角定義了正切.正切和端點(diǎn)確定圓錐5個(gè)自由度的4個(gè).讓圓錐穿過位于序列中央的軟頂點(diǎn)可以完全確定圓錐。樣條曲線早期繪圖員在制圖時(shí),使用一種富有彈性的細(xì)長條，稱為樣條.用壓鐵將樣條固定在若干樣點(diǎn)上,然后沿樣條可以畫出很光滑的曲線，人們將該曲線稱為樣條曲線.從數(shù)學(xué)上講,樣條曲線是用分段多項(xiàng)式表示的一個(gè)函數(shù)，在其連接點(diǎn)處具有連續(xù)的一階和二階導(dǎo)數(shù)。樣條曲線有著許多應(yīng)用.在數(shù)據(jù)分析中，當(dāng)沒有合適的函數(shù)模型時(shí)，可以選用樣條函數(shù)擬合數(shù)據(jù)點(diǎn).在計(jì)算機(jī)圖形和計(jì)算機(jī)輔助設(shè)計(jì)中，樣條函數(shù)用來表示自由曲線.在機(jī)器視覺中，若沒有表示曲線的合適模型時(shí)，樣條函數(shù)可以提供曲線的通用表示形式。需要指出，幾何等效和參數(shù)等效是兩個(gè)不同的概念.兩條曲線在幾何上等效，是指它們連接相同的點(diǎn)集，即它們?cè)诳臻g上對(duì)應(yīng)著相同的形狀（或點(diǎn)集）.如果兩條曲線的方程一樣，則兩條曲線在參數(shù)上等效.顯然，參數(shù)等效比幾何等效更穩(wěn)定.兩條曲線可以是幾何上等效但可以具有不同的參數(shù)表示式，這是機(jī)器視覺中曲線擬合的一個(gè)重要概念.比如，機(jī)器視覺系統(tǒng)可以產(chǎn)生基于三次樣條曲線的表示，其在幾何上非常接近于物體輪廓的真實(shí)表示，但在參數(shù)意義上，表示可能完全不同.在物體識(shí)別應(yīng)用方面和工業(yè)零件圖像與其模型匹配應(yīng)用中，通過比較三次樣條曲線的參數(shù)實(shí)現(xiàn)匹配幾乎是不可能的，在這種情況下，比較必須基于幾何等效性。三次樣條曲線樣條函數(shù)最常見的形式是三次樣條函數(shù)，它是分段三次多項(xiàng)式的一個(gè)序列.上一節(jié)所討論的直線段、圓弧段和圓錐曲線序列是樣條函數(shù)的典型實(shí)例.三次樣條函數(shù)可以用很少幾個(gè)樣條段表示很復(fù)雜的曲線.二次樣條函數(shù)已經(jīng)廣泛用于計(jì)算機(jī)圖形學(xué)和字符輪廓表示。三次樣條具有足夠的自由度來逼近邊緣段位置和方向.我們知道，大多數(shù)邊緣檢測(cè)算法同時(shí)提供邊緣方向（梯度角）和邊緣位置估計(jì).在直線段、圓弧段和圓錐曲線的擬合中僅僅使用了邊緣的位置信息.下面介紹一種在三次樣條曲線擬合中如何使用由邊緣檢測(cè)器產(chǎn)生的方向信息的例子。平面三次曲線方程如下：

(7.21；(7.22))=a*+hxii4-cxil+dTu

y(n)=ar+byti+c^u2+dvil

p(u)=(x(ix),y(u))=a+bu+cu2+du(7.21；(7.22)參數(shù)u取值范圍在0和1之間.三次曲線起始點(diǎn)為p(O)=(x(O),y(O)),終結(jié)點(diǎn)九p(l)=(x(l),y(l)).三次樣條是由三次曲線段Pb(w),p,(M),…，P-(u)構(gòu)成的一個(gè)序列，這-序列定義在連續(xù)區(qū)間[0,1],[1,2],…，[九-1』]上，并將端點(diǎn)連接起來使得在端點(diǎn)處p二見圖7.12.樣條中的每一個(gè)二次曲線段稱為樣條段，連接樣條段兩端的點(diǎn)稱為結(jié)點(diǎn)-設(shè)第1個(gè)結(jié)點(diǎn)連接第i-I樣條段和第i樣條段，該結(jié)點(diǎn)表示為p-(1)或P：(0)*圖7-12n圖7-12n個(gè)分段連續(xù)三次樣條插值曲線和前面討論的曲線擬合算法一樣，把邊緣點(diǎn)序列分成一個(gè)個(gè)子序列，每一個(gè)子序列的第一個(gè)和最后一個(gè)邊緣點(diǎn)為樣條曲線的結(jié)點(diǎn)，然后再用樣條段擬合這些結(jié)點(diǎn).由式(7.21)可知，樣條中每一個(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é)中，光滑連接是通過增加二階連續(xù)性來實(shí)現(xiàn).由上面分析可知，二階連續(xù)性會(huì)提供兩個(gè)約束，從而對(duì)樣條段產(chǎn)生過約束.為了避免過約束，同時(shí)又要使結(jié)點(diǎn)處光滑，可以采用結(jié)點(diǎn)處二階不連續(xù)性的極小化條件，也就是說把結(jié)點(diǎn)處的曲率差值極小化作為一個(gè)約束代替二階連續(xù)性提供的兩個(gè)約束。對(duì)于整個(gè)三次樣條曲線，求n-1個(gè)節(jié)點(diǎn)處二階導(dǎo)數(shù)差值平方和的極小化(7.23)其中兩個(gè)樣條段在結(jié)點(diǎn)處的二階導(dǎo)數(shù)差值是居応⑴“⑹(7.24)=2(t-i+4t+I」+3(p-+PJ)變量t,是結(jié)點(diǎn)』處的正切矢量，該正切矢量由邊緣方向(梯度角)化和一個(gè)有正負(fù)號(hào)的禾知參數(shù)7,來決定(7.25)換句話說，在結(jié)點(diǎn)處的邊緣方向可以用一個(gè)單位矢量表示，但三次樣條需要具有大小及正負(fù)號(hào)的正切量，以表示穿越結(jié)點(diǎn)的方向和速度.用該算法求解線性系統(tǒng)方程，可以得到n個(gè)未知數(shù)yf由此提供構(gòu)造結(jié)點(diǎn)之間三次樣條段的丟失信息。本算法沒有任何附加參數(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é)三次樣條曲線。7.2.3B樣條曲線B樣條曲線是由結(jié)點(diǎn)引導(dǎo)的逐段多項(xiàng)式曲線，是一種平滑和內(nèi)插技術(shù)樣條與上述樣條曲線不同，它不必通過結(jié)點(diǎn)(將這種結(jié)點(diǎn)稱為引導(dǎo)結(jié)點(diǎn)).B樣條曲線的三次多項(xiàng)式是最常用的，因?yàn)檫@些樣條曲率連續(xù)度為最低?已知引導(dǎo)結(jié)點(diǎn)序列為P，p，…，p,則三次B樣條多01n項(xiàng)式為:P((f)=弘a)P-+駕(皿+爲(wèi)⑺p沖+町⑺口+2⑺26】式屮為參數(shù)的三次多項(xiàng)式?下面確定上式四個(gè)多項(xiàng)式所對(duì)應(yīng)的16個(gè)參數(shù).對(duì)任意的=i-l…M+3),相鄰接的曲線段現(xiàn)⑷廚+心)以及二階導(dǎo)數(shù)必須連續(xù)的條件提伏巧個(gè)等式，例^,P[(l)=Pi+J{O)T則有Bq(1)Pi7+舀i(l)Pi+^2(1)Pi+|+民(l)pI+2=Bo(O)pt+(O)p*i+艮(0)Pw+爲(wèi)(0)P+(7-27)并提供以下五個(gè)等式鳳(1)=0,協(xié)(1)=鳳(0),耳(1)工F,(0),艮⑴=￡,(0),￡3<0)=0R仃)的形狀對(duì)坐標(biāo)轉(zhuǎn)換不變的條件提供了另一個(gè)方程：B()(f)+￡](t)+￡)+3^(t)=1(7.28)通過解】6個(gè)等式，可以得到如下16個(gè)系數(shù)：(i)=^(1-03ID7.13￡樣條曲線示意圖仙)直線皿》)B樣條曲線;0)三次占樣條曲線衛(wèi)](f)—￡(3F—bl~+4)ID7.13￡樣條曲線示意圖仙)直線皿》)B樣條曲線;0)三次占樣條曲線民⑴二^-(-3?+3t2+3—1)(7.29)(￡)-*尸顯然這四個(gè)多項(xiàng)式都是非負(fù)的，根據(jù)式(7.27)，曲線上的任何點(diǎn)都是四個(gè)控制結(jié)點(diǎn)的插補(bǔ)，即曲線段包含在由四個(gè)控制結(jié)點(diǎn)確定的方塊內(nèi)?如圖7,13所示.通常，m次的H樣條包含在由m+1控制點(diǎn)確定的多邊形內(nèi)?由于B樣條的優(yōu)良特性和對(duì)于任何控制點(diǎn)導(dǎo)數(shù)的連續(xù)性，故在實(shí)際中較為常用。曲線回歸逼近目前有許多曲線逼近方法，其區(qū)別主要取決于邊緣點(diǎn)組成輪廓點(diǎn)的可靠度.如果將所有邊緣點(diǎn)連接起來可以組成一個(gè)輪廓，那么就可以用最小二乘回歸法來進(jìn)行邊緣點(diǎn)曲線擬合.如果存在組合誤差(groupingerror),則可以使用魯棒回歸方法來進(jìn)行曲線逼近.如果邊緣點(diǎn)組成的輪廓不可靠，或者邊緣點(diǎn)太分散以至于無法用連接或跟蹤方法來組成輪廓，那么必須使用聚類分析(dusteranalysis)技術(shù)同時(shí)進(jìn)行邊緣點(diǎn)的組合和曲線逼近.同時(shí)用組合和曲線逼近方法處理分散邊緣點(diǎn)算法的最好例子是Hough變換，這一內(nèi)容將在下面討論。前面幾節(jié)討論的直線段、圓弧段、圓錐曲線和三次樣條擬合邊緣點(diǎn)的方法屬于一般回歸問題，主要用于端點(diǎn)之間的曲線擬合.這些算法都假定邊緣的位置可以精確計(jì)算.這種回歸算法沒有使用端點(diǎn)之間的邊緣點(diǎn)信息，因此曲線的擬合精度主要取決于端點(diǎn)的位置精度.本節(jié)討論的曲線最佳逼近方法將使用所有邊緣點(diǎn)信息.一般曲線擬合問題是一個(gè)曲線的回歸問題，曲線用P個(gè)參數(shù)的隱函數(shù)表示/(x;aj.,tip)=0(7-30)曲線預(yù)估問題就是指用這種曲線模型擬合一個(gè)邊緣點(diǎn)集”內(nèi)心J,(刼，…觀.在無噪聲情況下，通過P次觀測(cè)產(chǎn)生的P個(gè)方程來求解P個(gè)未知曲線參數(shù).徂是在大多數(shù)場合，由于噪聲的原因，這一直接方法不是很有效.實(shí)際的應(yīng)用常需要使用邊緣表中所有信息來獲取這些參數(shù)的最佳估計(jì)。下一節(jié)我們將討論最小二乘回歸方法，這種方法在計(jì)算機(jī)視覺中主要用于曲線擬合.當(dāng)誤差服從正態(tài)分布時(shí),最小二乘方法是最合適的擬合方法.7.4.3節(jié)將討論曲線擬合的魯棒回歸法，這種方法在些邊緣點(diǎn)被錯(cuò)誤地分配到某一輪廓時(shí)特別有用，這種錯(cuò)誤點(diǎn)被稱為局外點(diǎn)(Outlier).全回歸方法經(jīng)典線性回歸方法僅僅在一維獨(dú)立變量空間中對(duì)數(shù)據(jù)與模型的差值求極小化.比如，一個(gè)函數(shù)模型具有下列形式y(tǒng)-f{x\a}^ay(7.31)上式把獨(dú)立變量y和獨(dú)立變量工聯(lián)系起來，具有卩個(gè)模型參數(shù){佝，…，幻)，并假定獨(dú)立變量沒有誤差-在機(jī)器視覺中2和丁的坐標(biāo)位置誤差很可能相等，瓦對(duì)應(yīng)的曲線模型是一條垂直線，這樣就無決用上述方稈來表示■在機(jī)器視覺中，邊緣點(diǎn)的直線和曲線模型擬合是通過使用全回歸方法實(shí)現(xiàn)的，即對(duì)所有的數(shù)據(jù)點(diǎn)與回歸模型之間距離的平方和進(jìn)行極小化，這一技術(shù)的優(yōu)點(diǎn)是能夠補(bǔ)償％和y方向的誤差.為了避免垂直肓線引起的數(shù)字計(jì)算問題.可以使用如下極坐標(biāo)形式來表示直線方程一'+ysin6—“=0(7.32)對(duì)所有點(diǎn)(兀T1)到該直線垂直距離的平丈和極小化f=2cos0+y；sin^-(o)2(7.33)全回歸問題的解是1-p=xcos^+ysin(9(7.34)其中全回歸直線方向角為比由卜式結(jié)出：tan?/?二fiih(7.35)a=2丈(卻-x)(yt-y)1nnb-￡&—xV-2(y,--yyi=1t=1全回歸方法使用了最小二次誤差范數(shù)，如果誤差服從正態(tài)分布，則誤差范數(shù)是最優(yōu)的.該方法不適用于數(shù)據(jù)中有局外點(diǎn)的情況.在用曲線模型擬合邊緣點(diǎn)時(shí)，如果邊緣連接算法從其它輪廓上吸收一個(gè)或一個(gè)以上邊緣點(diǎn)到本輪廓邊緣表中，即產(chǎn)生了邊緣局外點(diǎn).即使邊緣連接算法完美無缺，也免不了局外點(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ì)引入到回歸問題里，其中的誤差不服從正態(tài)分布.在這種情況下，誤差可以由一個(gè)混合模型來表示，即把描述正態(tài)分布誤差的高斯分布函數(shù)和描述由于分類不理想而引起局外點(diǎn)的拖尾分布函數(shù)混合起來。角點(diǎn)估計(jì)角點(diǎn)估計(jì)的最佳方法是使用直線段逼近邊緣點(diǎn)來求出直線段序列，然后計(jì)算直線段之間的交點(diǎn).這一方法補(bǔ)償了由邊緣檢測(cè)算子對(duì)角點(diǎn)的平滑作用而引入的誤差，并且比利用局部信息的角點(diǎn)檢測(cè)算子求出的角點(diǎn)更精確。已知兩條直線的隱函數(shù)方程為rt,jc+b\y+g二0〔7-36)他第十&汀+6二0(7-37)

兩條直線的交點(diǎn)坐標(biāo)為(738)<?2b〔?c]b?(738)'口Ii?2_a?bi如果百婦-5析非當(dāng)接近零，那么兩條直線幾乎平行，沒有交點(diǎn)-一種較好的探測(cè)角點(diǎn)方法是沿著輪廓用一對(duì)直線擬合2n+決個(gè)邊緣點(diǎn)中的一個(gè)連續(xù)子表，其中，參數(shù)熬是邊緣點(diǎn)數(shù)量，用十精確直線擬合；參數(shù)恥是位十角點(diǎn)周圍不予考慮的邊緣點(diǎn)的數(shù)量，即跨越角點(diǎn)圓弧部分的邊緣點(diǎn)-設(shè)置一個(gè)閾信，檢測(cè)心撾-業(yè)兒是否大于該閾值即可決定角點(diǎn)是否存在.魯棒回歸法如果誤差不服從正態(tài)分布，那么最小二乘法就不是最佳擬合方法.圖7.14所示的是數(shù)據(jù)集合包含一些局外點(diǎn)時(shí),使用最小二乘法所遇到的問題的一個(gè)例子.在實(shí)際中，可能一個(gè)局外點(diǎn)就足夠把回歸直線推向遠(yuǎn)離其正確的位置.魯棒回歸方法要對(duì)數(shù)據(jù)的各種子集進(jìn)行測(cè)一組點(diǎn)的質(zhì)心.把具有相同彈簧系數(shù)的若干彈簧的一端連接到一個(gè)可以自由運(yùn)動(dòng)的物體上，另一端分別系在不同的固定點(diǎn)上，物體將會(huì)被拉到一個(gè)平衡（平均）位置上.彈簧將通過彈簧勢(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).用力扯動(dòng)杠桿點(diǎn)到足夠遠(yuǎn)的地方，可以迫使平衡點(diǎn)移動(dòng)到任意一個(gè)位置.這一現(xiàn)象說明基于最小二乘法的預(yù)估器對(duì)局外點(diǎn)及其敏感.理想情況下，人們希望把彈簧和局外點(diǎn)隔開，使得估計(jì)值不受太大的影響.改變彈簧常數(shù)使得局外點(diǎn)對(duì)估計(jì)值影響最小，可以實(shí)現(xiàn)基于影響函數(shù)的魯棒性估計(jì).割斷彈簧與局外點(diǎn)的聯(lián)系對(duì)應(yīng)于再取樣策略.再取樣方法是指重復(fù)抽取隨機(jī)子集并選擇可以產(chǎn)生最佳估計(jì)的子集.再取樣算法的例子包括隨機(jī)抽樣一致性、最小中值二乘回歸、以及其它計(jì)算機(jī)中常用的回歸方法。彈簧模擬方法推廣到線性回歸系統(tǒng)也有一樣的結(jié)論，即單一的局外點(diǎn)可以扭曲回歸對(duì)干最小二乘回歸，°：=1"■沖極限情況下*半數(shù)據(jù)點(diǎn)數(shù)量變的很大時(shí)，F(xiàn)；=D.換句話說，最?。撼嘶貧w方法對(duì)局外點(diǎn)無免疫能力，一個(gè)局外點(diǎn)即可毀掉結(jié)果.最小中值二乘回歸方法是種非常簡單的技術(shù)，并被證明是解決大量兄外點(diǎn)回歸問題的非常有效的方法，算法7.1概括了該算法.最小中值二乘方法可以容錯(cuò)高達(dá)50%的局外點(diǎn)，也就意味著數(shù)據(jù)點(diǎn)集內(nèi)有一半的數(shù)據(jù)可以取任意值而不會(huì)嚴(yán)重地影響回歸結(jié)果.如果有多于百分之五十的點(diǎn)為局外點(diǎn)，最小中值二乘回歸方法就變得無效，此時(shí)需要更有效的方法，如Hough變換.存最小中值二乘團(tuán)歸方法中，模型參數(shù)價(jià)的估計(jì)曲極小化殘差平方的中值求得imnmed（）（7.43）關(guān)于最小中值二乘回歸方法詳細(xì)討論見[Rousseeuw1987,Efron1988].算法7.1最小中值二乘回歸方法假定有n個(gè)數(shù)據(jù)和p個(gè)參數(shù)的線性模型在n個(gè)數(shù)據(jù)點(diǎn)集中，隨機(jī)地選擇p個(gè)點(diǎn)；用模型擬合p個(gè)點(diǎn)；計(jì)算殘差平方的中值.重復(fù)進(jìn)行上述擬合過程直到得到足夠小的殘差平方中值，或者達(dá)到預(yù)定的再取樣步長數(shù)值.Hough變換最近幾年，使用表決原理的參數(shù)估計(jì)技術(shù)應(yīng)用不斷增加.最常用的表決方法之是Hough變換?在Hough變換中，曲線上的每一點(diǎn)可以表決若干參數(shù)組合，贏得多數(shù)表決的參數(shù)就是勝者?下面考慮一下直線擬合數(shù)據(jù)的方法?直線方程為y=17M；+c（7.44）上述方程中*和了是觀測(cè)值，肌和*表示參數(shù).如果已知參數(shù)值，則該點(diǎn)坐標(biāo)之間的關(guān)系即可礁定?把上述方程重新表示為cy-mx（7.45）假定/n和c是我們感興趣的變量，面%和y是常數(shù)，則上述方程表示的是（尬，小空間中的一條直線，斜率和蔽距由工和y抉定■點(diǎn)（工』）對(duì)應(yīng)空同的直線，如圏7.16（a）所示?如果直線上有“個(gè)點(diǎn)，那么這些點(diǎn)對(duì)應(yīng)參數(shù)空間（叫小匕的一個(gè)直線族，口所有直線都經(jīng)過（肌,c）上的一點(diǎn),該點(diǎn)的坐標(biāo)當(dāng)然反應(yīng)（工*）空間上的直線參數(shù)，如圖7.16（b）所示.需要臘岀，參數(shù)空間曲線的形狀取決于用于表示曲線的原始函數(shù).實(shí)際中，常常使用宜線的極坐標(biāo)形式，而不是其顯式表示，這樣可以避免直線是垂直線時(shí)帶來的問題-直線的極坐標(biāo)方程表示如下：p=+ysin0（7.46）丄述方程中，點(diǎn)d,y）披映射到空間上，如圖7.16（c）所示?如果直線上有”個(gè)點(diǎn)，那么這些點(diǎn)對(duì)應(yīng)參數(shù)空間（宀療）上的矗條正弦曲線，且所有正弦曲線都經(jīng)過（宀刊）上

m3(a)232D(h)A旺AB0(c)\As\圖m3(a)232D(h)A旺AB0(c)\As\圖7.16Hou戲變換示童圖左辿為圖象空間，右邊為1^吸變換空間(G—條直線對(duì)應(yīng)一個(gè)點(diǎn)；(b)—條直線上的多個(gè)點(diǎn)對(duì)應(yīng)多條交于一點(diǎn)的直線;(小一條直線上多個(gè)點(diǎn)對(duì)應(yīng)多條交于一點(diǎn)的正弦曲線的一點(diǎn)。如果對(duì)求點(diǎn)的最佳直線擬合感興趣，那么就可以使用上述圖像空間到參數(shù)空間的映射方法,這種方法稱為Hough變換?在這種方法中，常把參數(shù)空間設(shè)計(jì)成一個(gè)累加器陣列，表示離散參數(shù)值.依照變換方裎，圖像中的每一點(diǎn)可以表決幾個(gè)參數(shù)，而參數(shù)空間(或累加器陣列）的峰值就是表征一條直線的參數(shù)，具體實(shí)現(xiàn)見算法7.2。算法7.2Hough變換算法適當(dāng)?shù)貢灮瘏?shù)空間；假定參數(shù)空間的每一個(gè)單元都是一個(gè)累加器，把累加器初始化為零；對(duì)圖像空間的每一點(diǎn)（x,y）,在其所滿足的參數(shù)方程對(duì)應(yīng)的累加器上加1；累加器陣列的最大值對(duì)應(yīng)模型的參數(shù)。Hough變換不需要預(yù)先組合或連接邊緣點(diǎn).位于感興趣曲線上的邊緣點(diǎn)可能構(gòu)成圖像邊緣的一個(gè)小部分.特別指出，Hough變換允許位于曲線上的邊緣數(shù)董少于實(shí)際的邊緣數(shù)量，而大多數(shù)魯棒回歸算法無法用于這種情況.Hough變換所基于的假設(shè)是在大量噪聲出現(xiàn)的情況下，最好是在參數(shù)空間中去求滿足圖像邊緣最大數(shù)量的那個(gè)點(diǎn).如果參數(shù)空間的峰值包括了一個(gè)以上的累加器，則包含峰值的區(qū)域的矩心就是參數(shù)的一個(gè)估值.利用上述算法的實(shí)驗(yàn)結(jié)果見圖7.17。如果圖像中有幾條曲線和給定模型相匹配，則在參數(shù)空間中會(huì)出現(xiàn)幾個(gè)峰值.此時(shí)，可以探測(cè)每一個(gè)峰值，去掉對(duì)應(yīng)于某一個(gè)峰值的曲線邊緣，再檢測(cè)余下的曲線，直到?jīng)]有明顯的邊緣.但是，確定峰值的顯著性是件很困難的事。Hough變換的另一個(gè)問題是離散參數(shù)空間隨著參數(shù)的數(shù)量增加迅速增加.對(duì)一個(gè)圓弧段，參數(shù)空間是三維的，對(duì)其它曲線，其維數(shù)可能更高.由于累加器的數(shù)量隨著參數(shù)空間的增加成指數(shù)增加，Hough變換可能對(duì)于復(fù)雜模型的