機(jī)器視覺(jué)輪廓表示之曲線擬合

機(jī)器視覺(jué)輪廓表示之曲線擬合7.2曲線擬合本章將討論三種常用的曲線模型擬合邊緣點(diǎn)的方法：直線段，圓錐曲線段和三次樣條曲線段.一般來(lái)說(shuō)，在用曲線模型擬合邊緣點(diǎn)之前應(yīng)考慮如下兩個(gè)問(wèn)題：用什么方法進(jìn)行邊緣點(diǎn)曲線模型擬合？如何測(cè)量擬合的逼近程度？下面幾節(jié)將討論曲線模型擬合邊緣點(diǎn)方法，其中假設(shè)邊緣位置足夠精確，不會(huì)對(duì)擬合結(jié)果產(chǎn)生影響.設(shè)1是邊緣點(diǎn)到一條擬合曲線的距離，該距離值有正負(fù)符號(hào)，在曲線同一側(cè)的邊緣具有相同的正負(fù)符號(hào).目前有許多種擬合曲線與候選邊緣點(diǎn)擬合效果的測(cè)量方法，每一種都取決于擬合曲線和候選點(diǎn)之間的誤差.下面是一些常用的方法.最大絕對(duì)誤差(maximumabsoluteerror,MAE)測(cè)量最壞情況下邊緣點(diǎn)偏離曲線的距離TOC\o"1-5"\h\z\o"CurrentDocument"MAE=irwxId.I (7.3)均方差(meansquarederror，MSE)給出邊緣點(diǎn)偏離擬合曲線的總的測(cè)度MSE=W藻： (7.4)規(guī)范化最大誤差(normalizedmaximumerror，NME)最大絕對(duì)誤差與曲線長(zhǎng)度S之比max|d-Ie= — (7,5)誤差符號(hào)變化次數(shù)這里的誤差就是指d1，即邊緣點(diǎn)偏離擬合曲線的距離.誤差符號(hào)變化次數(shù)可作為輪廓邊緣模型與邊緣點(diǎn)曲線適合程度的測(cè)度.曲線長(zhǎng)度與端點(diǎn)距離之比曲線復(fù)雜程度的測(cè)度.符號(hào)變化是一種評(píng)價(jià)擬合好壞的很有用的參數(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)景是由直線段組成，則使用直線段(或多線段)模型比較合適。直線段模型也可作為其它擬合模型的初始擬合模型圓弧段是估計(jì)曲率的最有用的一種表示，因?yàn)榍€可以分割成具有分段恒定曲率的曲線段圓錐曲線段是一種

表示直線段和圓弧段序列以及橢圓和高次弧段序列的有效方法.三次樣條曲線適合于平滑曲線模型，因?yàn)槿螛訔l曲線并不要求正切矢量和曲率的估計(jì)值一定是分段恒定的。7.2.1多直線段多直線段是指端點(diǎn)連接端點(diǎn)的直線段序列，直線段序列的連接點(diǎn)稱為頂點(diǎn)多直線段適合具有線段序列的邊緣列表的擬合.多線段算法的輸入值是邊緣點(diǎn)有序表｛（x「yi），（%，*），???，（%，yn）｝。邊緣點(diǎn)坐標(biāo)可以計(jì)算到子象素精度.由于線段的兩個(gè)端點(diǎn)對(duì)應(yīng)兩個(gè)邊緣點(diǎn)，即線段擬合在這兩個(gè)邊緣點(diǎn)之間進(jìn)行，因此僅需要精確計(jì)算對(duì)應(yīng)端點(diǎn)的兩個(gè)邊緣點(diǎn)的坐標(biāo)。連接起來(lái)的直線半）擬合邊緣表并把第一個(gè)邊緣點(diǎn)愆］，%）和最后一個(gè)邊緣點(diǎn)（x段公式如下：連接起來(lái)的直線半）：7.6)上式可以改寫(xiě)為由端點(diǎn)表示的隱式函數(shù)（7-7）Ax+By+C=0（7-7）其中A=（處-以）B-（xb- C=x｝yh-與為D=vzA2+是邊緣點(diǎn)（跖，丁i）和（再，耳）之間的距離.任給一點(diǎn)（免，乂），設(shè)r=血；+月當(dāng)+。，則「的符號(hào)可用來(lái)計(jì)算符號(hào)變化次數(shù).點(diǎn)（尋，）與擬合直線段的距離為(7-8)規(guī)范化最大誤差為maxIciP— D規(guī)范化最大誤差常作為線段擬合邊緣列表好壞的置度.需要指出，上面的公式都是在點(diǎn)向直線段的垂直投影落在線段內(nèi)這個(gè)假設(shè)下進(jìn)行的.對(duì)于其它情況,則應(yīng)修正公式，以便計(jì)算點(diǎn)到最近的線段端點(diǎn)的距離.下面介紹兩種擬合多線段的方法：自頂面下的分裂和自底而上的合并.多直線段分裂自頂而下的分裂算法（top-downsplitting）是將整條曲線作為初始曲線，通過(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)記，從而形成兩個(gè)擬合直線段AC和CB,邊緣表也分割成對(duì)應(yīng)于兩個(gè)新直線段的兩個(gè)子邊緣表.在每一個(gè)子邊緣表中，重復(fù)上面所述的分裂算法，形成兩個(gè)新的直線段及對(duì)應(yīng)的兩個(gè)更小的子邊這樣的分裂過(guò)程可以一直進(jìn)行下去，直到所有的直線段對(duì)應(yīng)的規(guī)范化最大誤差均低于某一閾值為止.多線段分裂也稱為迭代分解。線段合并線段合并(merging)是指用一條直線段盡量多地?cái)M合邊緣表中的邊緣點(diǎn).當(dāng)邊緣點(diǎn)離直線段太遠(yuǎn)而無(wú)法用該直線段擬合時(shí)，則開(kāi)始新的直線段擬金合并方法也稱為自底而上合并(boltom-upmerging)的多線段擬合方法.確定邊緣點(diǎn)離直線段的距離有許多種方法.一種方法是使用序貫最小二乘法，完成直線段到邊緣點(diǎn)的最小二乘法擬合，并在每次處理新的邊緣點(diǎn)時(shí)遞增地更新線段參數(shù)擬合算法將計(jì)算邊緣點(diǎn)與直線段模型之間的偏差(殘差)平方.當(dāng)偏差超過(guò)某一閾值時(shí)，引進(jìn)一圖7-5擬合宣線段的誤差帶方法圖個(gè)頂點(diǎn)，并將上一個(gè)線段的端點(diǎn)作為新的起點(diǎn)開(kāi)始新的直線段擬合。誤差帶算法是另一種確定頂點(diǎn)位置的方法，如圖7.6所示，主要工作是計(jì)算兩條平行且離中心線距離為8的直線段，8值表示離中心直線的絕對(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)位置和角度。分裂和合并自頂而下的迭代分解方法和自底而上的合并方法組合起來(lái)，形成合并和分裂算法單獨(dú)使用分裂或合并算法時(shí)，成功率往往不是很高，改進(jìn)的方法是交叉使用分裂和合并算法分解過(guò)程以后，如果新的線段能以很小的規(guī)范化誤差擬合邊緣，則可用單一直線段代替相鄰的幾個(gè)線段.請(qǐng)注意，由于多直線段總是比單直線段的擬合誤差小，因此很有必要使用規(guī)范化誤差.在線段合并后，新的線段可能在不同點(diǎn)處分裂.這樣，分裂和合并交替作用直到?jīng)]有線段被合并和分裂為止，圖7.7所示的是先分裂后合并來(lái)修補(bǔ)壞頂點(diǎn)位置的示意圖。

圖7.7先分裂后合并修補(bǔ)壞頂點(diǎn)位置的示煮圖（Q原始邊巢.點(diǎn)集Hb）日底而上的邊緣合弁方法產(chǎn)牛的壞角點(diǎn)估計(jì)：卜）漏掉的直實(shí)角震位置由分裂和臺(tái)并算法來(lái)蜂補(bǔ)一種有效的分裂和合并算法是從邊緣表中的前k個(gè)邊緣構(gòu)成的子列表開(kāi)始，而不是整個(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二次曲線下面討論如何用二次曲線逼近邊緣表.二次曲線的一般表示如下:fix=做’+2hxyfix=做’+2hxy+by1+2場(chǎng)+2gy+「二01.圓弧段(7.101圖7.8圓椎和平面定義

的圓錐曲線(7.101用直線段逼近邊緣表以后，其中的一些直線段序列可以由圓弧段來(lái)代替，比如，用直線段擬合一個(gè)圓弧可能需要許多個(gè)直線段才能滿足擬合誤差，如果對(duì)這些直線段用圓弧段來(lái)擬合，則僅需要一條圓弧段即可，因此可見(jiàn)，圓弧段擬合此直線段能擬合得更緊湊，下面討論的圓弧擬合是在多邊形頂點(diǎn)上進(jìn)行的。具有半徑r和圓心坐標(biāo)（％，y0）的圓弧隱式方程為（%-x0）2+（y-y0）2=r2 （7-11）考慮三點(diǎn)Qi=（初）小=（勤）小=（勤，無(wú)），不失一般性，設(shè)Pi位于坐標(biāo)原點(diǎn)，即叫=0,為=0.把點(diǎn)pi.p?,p3代人上述方程得Xo+^-r2=0（x2~第o）'十tJi一To）'—，二。 （7■12j（X,-%n）2+（火-Yn尸-尸=0分別用第一和第三方程減去第…方程，得到如下兩個(gè)方程：2x2x0+2y2y0=德+2用$其口十 =必+招 （7+13，這是兩個(gè)關(guān)丁未知參數(shù)而，為的非線性方程，求解此，為，即可由（7.12）的第-個(gè)式子得到圓的半徑。為了計(jì)算圓弧擬合誤差，將點(diǎn)。到圓的距離定義為沿著通過(guò)圓心直線方向的點(diǎn)。與I圓的距離，計(jì)算點(diǎn)。（阮土）到圓中心（勤.處）的距離q= x0）-+（丸-咒尸 （7.14）點(diǎn)Q到圓孤段的距離是d=q-r （7,15）用圓弧段擬合多直線段時(shí)，圓弧段的網(wǎng)個(gè)端點(diǎn)要經(jīng)過(guò)多直線段的某構(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)很多,感興趣的讀者可以參見(jiàn)文獻(xiàn)［Jiar1992,Chen1996］。用直線段和圓弧段可以有效地表示數(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)處具有相等的正切，使兩個(gè)鄰接曲線段之間平滑過(guò)渡.設(shè)多直線段端點(diǎn)為匕，圓錐逼近如圖7.9所示。

圖7.9由三點(diǎn)定義的圓錐曲城逼近圓錐樣條中的每一個(gè)圓錐曲線由兩個(gè)端點(diǎn)、兩個(gè)正切和第三點(diǎn)確定結(jié)點(diǎn)位于多線段頂點(diǎn)之間=(1一加+心 (7.16)其中七取事1之間的數(shù)直?正切由三個(gè)頂點(diǎn)R,K.i和氣心笙成的三角形來(lái)定義?第三E如圖7麻示，由下面式子計(jì)算：乙+(1『X)一 (7?⑺復(fù)史遂卒同的數(shù)值,有幾種特殊的情況可以通過(guò)如下方法來(lái)處理,如果p[+1=0,那么第￡個(gè)圓矗繇赧夏K,到上]的直線段.如果虬=1和p1+1=0,那么凡,j和V'f對(duì)應(yīng)于同一點(diǎn)，在圓錐曲線序列中有一個(gè)角點(diǎn),這些性質(zhì)使得直線段和角點(diǎn)可以明顯故表示出來(lái)，無(wú)需求助于不同的基元和特殊的標(biāo)志.由兩個(gè)端點(diǎn)、三頂點(diǎn)構(gòu)成的正切和第二點(diǎn)定義的圓錐曲線

這里所示的計(jì)算圓錐樣條算法使用了一個(gè)圓錐曲線的引導(dǎo)形式，以表示由三條直線約束的圓錐曲線，如圖7.11所示.直線方程為+ y二0 （7?⑻設(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）=p（改+心叫+ （7,19）其中％+Gtx1-a2y=0是包含直線段AC的直線；x+b2y=0是包含直線段BC的直線;標(biāo)+蜘工+s=0是包含弦AB的直線,圓錐曲線族由參數(shù)p來(lái)定義，圓錐曲線擬臺(tái)邊緣表的算法是從直線段開(kāi)始的.頂點(diǎn)分為角點(diǎn)（comer）、軟頂點(diǎn)（由I就rtw）和結(jié)點(diǎn)（knot）三類?軟頂點(diǎn)對(duì)應(yīng)的角接近180°,相鄰的直線段幾乎共線，井凹以用圓ii+11/2.由于圓錐曲線

那么，結(jié)點(diǎn)位置應(yīng)錐曲線來(lái)代替.軟頂點(diǎn)序列對(duì)應(yīng)于緩變方向角的直線段序列，很可能是對(duì)光滑曲線的采樣點(diǎn)進(jìn)行擬合的結(jié)果.角點(diǎn)對(duì)應(yīng)的頂點(diǎn)角大180°+二，或小于180°-二，其中T1是閾值，角點(diǎn)不可能成為圓錐曲線的一部分結(jié)點(diǎn)位于某一條直線段上，該直線段的端點(diǎn)上具有軟頂點(diǎn).一個(gè)圓錐曲線不可能有拐