三維場(chǎng)景表示

第十三章三維場(chǎng)景表示三維場(chǎng)景表示是機(jī)器視覺(jué)的又一個(gè)關(guān)鍵技術(shù)．為了理解場(chǎng)景并與場(chǎng)景中的物體交互作用，必須將場(chǎng)景的三維數(shù)據(jù)進(jìn)行有效的表示．三維場(chǎng)景表示包含有兩個(gè)基本問(wèn)題：場(chǎng)景重建和場(chǎng)景分割.場(chǎng)景重建(reconstruction)是指使用插值或擬合方法從采樣點(diǎn)(稠密深度測(cè)量值或稀疏深度測(cè)量值)計(jì)算曲面的連續(xù)函數(shù)，實(shí)際中通常使用許多三角片或小平面片構(gòu)成的網(wǎng)面來(lái)近似表示場(chǎng)景深度測(cè)量值；場(chǎng)景分割是將表示場(chǎng)景的網(wǎng)面分割成若干部分，每一部分表示一個(gè)物體或一個(gè)特定的區(qū)域，這樣有利于物體識(shí)別、曲面精確估計(jì)等后處理算法的實(shí)現(xiàn)．本章從曲面的幾何特征開(kāi)始，討論場(chǎng)景曲面重建和分割的一些基本方法．這些方法可以將雙目立體測(cè)距、主動(dòng)三角測(cè)距、激光雷達(dá)測(cè)距等成像系統(tǒng)的輸出值轉(zhuǎn)換成簡(jiǎn)單的曲面表示．這些基本方法包括把測(cè)量點(diǎn)轉(zhuǎn)變成三角片網(wǎng)面、把距離測(cè)量值分割成簡(jiǎn)單的曲面片、把測(cè)量點(diǎn)擬合成一個(gè)光滑曲面以及用測(cè)量點(diǎn)匹配一個(gè)曲面模型等．13．1三維空間曲線討論三維空間曲線的原因主要有兩個(gè)，一是一些物體或物體特征可以直接用三維空間曲線表示，二是三維空間曲線表示可以推廣到三維空間曲面表示。曲線表示有三種形式：隱式、顯式和參數(shù)式。在機(jī)器視覺(jué)領(lǐng)域中，曲線的參數(shù)表示比隱式和顯式表示更為常用。三維曲線的參數(shù)形式為：p=(x,y,z)=(x(t),y(t),z(t))t°<t<[ (13.1)上式說(shuō)明曲線上的一點(diǎn)可由參數(shù)t表示的三個(gè)函數(shù)0來(lái)定義1，曲線的起點(diǎn)為13.2)(x(t0),y(t0),z(t0)),終點(diǎn)為(x(ti),y(ti),z(]))。比如，從pi=(,y”z/到P2=(x2,y2,z13.2)(A(v(V、xx—xx211y=ty-y+y211<z><z—z/<z/空間曲線的最通常的表示形式是三次多項(xiàng)式，下面我們將詳細(xì)討論.13．1．1三次樣條曲線物體表面上的線條可以是直線、弧線或是任意的曲線.曲線上的每一點(diǎn)位置可以表示成參數(shù)形式(x(t),y(t),z(t)).一般的三維曲線都可以方便地用樣條函數(shù)來(lái)表示，這和前面討論的平面曲線表示類似．三次樣條函數(shù)是一系列首尾相連的表示復(fù)雜曲線的三次多項(xiàng)式曲線，每一段三次樣條函數(shù)的參數(shù)表示形式為：x(t)=a13+b12+ct+dx x x xy(t)=a13+b12+ct+d (13.3)y y y yz(t)=a13+b12+ct+d其中0<t<1.z z z z三次多項(xiàng)式允許曲線通過(guò)確定的相切點(diǎn)，三次多項(xiàng)式是對(duì)于非平面曲線的最低階的多項(xiàng)式．將上式的系數(shù)表示成如下系數(shù)矢量：a=(a,a,a)xyz(13．4)b=(b,b,(13．4)xyzc=(c,c,c)xyzd=(d,d,d)xyz而且P(t)=(x(t),y(t),z(t))，則三次多項(xiàng)式曲線可以重寫(xiě)為如下形式:

(13．5)p(t)二at3+bt2+ct+d(13．5)更復(fù)雜的曲線可以表示為一系列首尾相連的三次多項(xiàng)式：p(t)=a13+b12+ct+d11111p(t)=a13+b12+ct+d22222 (13．6)Mp(t)=a13+b12+ct+dnnnnn其中0<t<1.如果定義第i個(gè)三次多項(xiàng)式段在單位區(qū)間i-1<t<i上，那么整個(gè)區(qū)間則為0<t<n.可以認(rèn)為，這個(gè)三次多項(xiàng)式序列是起點(diǎn)為p(0)，終點(diǎn)為p(n)的單一參數(shù)曲線.這0n個(gè)三次多項(xiàng)式序列叫做一個(gè)三次樣條函數(shù)，它是機(jī)器視覺(jué)和計(jì)算機(jī)圖形學(xué)中表示任意曲線的常用方式.13.1.2三維B樣條曲線三維B樣條曲線很適合表示由點(diǎn)序列構(gòu)成的曲線，因此可以將二維B樣條的定義擴(kuò)展到控制點(diǎn)位于三維空間的三維B樣條。例如對(duì)已知三維點(diǎn)序列p,p,A,p，由等式(7.28)0 1n給出第i階三次多項(xiàng)式，而B(niǎo).(t)由等式(7.31)給出.三維B樣條曲線也不通過(guò)控制點(diǎn).13.2三維空間曲面的表示本節(jié)將討論機(jī)器視覺(jué)中常用的幾種曲面表示.13．2．1多邊形網(wǎng)面平面多邊形，也叫平面片(planarpatch)，可以組成復(fù)雜的網(wǎng)面(polygonmesh)，以表示各種物體的形狀.圖13.1三角形網(wǎng)面和四邊形網(wǎng)面示意圖。本節(jié)將介紹如何用平面片進(jìn)行物體多邊形網(wǎng)面表示.第七章討論了如何用若干個(gè)直線段端點(diǎn)(頂點(diǎn))坐標(biāo)表來(lái)表示一個(gè)多直線段，這一方法也可推廣到平面多邊形，即平面多邊形網(wǎng)面也可以用一系列平面多邊形頂點(diǎn)坐標(biāo)表來(lái)表示.一個(gè)頂點(diǎn)常常是三個(gè)或三個(gè)以上多邊形的公共頂點(diǎn)，因此，一個(gè)頂點(diǎn)在表中重復(fù)出現(xiàn)多次.為了使多邊形網(wǎng)面的每一個(gè)頂點(diǎn)在表中僅出現(xiàn)一次，可以使用一種間接的頂點(diǎn)坐標(biāo)表示方法，即對(duì)這些頂點(diǎn)從1到n進(jìn)行編號(hào)，并按這一順序?qū)⒚恳粋€(gè)頂點(diǎn)的坐標(biāo)存入表中?每一個(gè)多邊形可用其頂點(diǎn)編號(hào)表表示.不過(guò)這種頂點(diǎn)表不能明顯地表示相鄰表面的邊界，對(duì)于一給定頂點(diǎn)，也不能有效地發(fā)現(xiàn)所有包含此頂點(diǎn)的表面．這些問(wèn)題可以用翼邊緣數(shù)據(jù)結(jié)構(gòu)（WingedEdgeDataStructure）來(lái)解決.翼邊緣數(shù)據(jù)結(jié)構(gòu)是一種網(wǎng)絡(luò)數(shù)據(jù)結(jié)構(gòu)，它具有三種類型數(shù)據(jù)記錄：頂點(diǎn)、邊和面．沿著數(shù)據(jù)結(jié)構(gòu)包含的數(shù)據(jù)指針可以找到所有元素的鄰接關(guān)系，而無(wú)須搜索整個(gè)網(wǎng)面，也無(wú)須將每一元素的所有鄰接元素都存儲(chǔ)起來(lái).在多邊形網(wǎng)面中，每一個(gè)頂點(diǎn)對(duì)應(yīng)數(shù)據(jù)結(jié)構(gòu)中的一個(gè)頂點(diǎn)記錄，每一個(gè)面對(duì)應(yīng)一個(gè)面記錄、每一條邊對(duì)應(yīng)一個(gè)邊記錄。這樣，可以直接查詢一條邊對(duì)應(yīng)的兩個(gè)頂點(diǎn)和兩個(gè)多邊形面，也可以直接查詢一個(gè)頂點(diǎn)對(duì)應(yīng)的所有多邊形面（或邊），查詢時(shí)間正比于該頂點(diǎn)對(duì)應(yīng)的多邊形面（或邊）的數(shù)量.翼邊緣數(shù)據(jù)結(jié)構(gòu)可以有效地表示三角面網(wǎng)面及其它具有多條邊的多邊形網(wǎng)面，并且不要求各個(gè)多邊形面的邊數(shù)相等.由于各頂點(diǎn)坐標(biāo)包含在頂點(diǎn)記錄中，因此，多邊形面（或邊）的位置可以由頂點(diǎn)的坐標(biāo)計(jì)算出來(lái).每一個(gè)面記錄指向該面的某一個(gè)邊記錄，每一個(gè)頂點(diǎn)記錄指向該頂點(diǎn)對(duì)應(yīng)的邊記錄。因此，邊記錄包含將多邊形面及其頂點(diǎn)連結(jié)成多邊形網(wǎng)面的指針，并且允許對(duì)多邊形網(wǎng)面頂點(diǎn)進(jìn)行快速的掃描.具體地說(shuō)，每一個(gè)邊記錄包含有兩個(gè)端點(diǎn)指針，其兩側(cè)的兩個(gè)多邊形面指針和4個(gè)鄰接翼指針，如圖13.2所示。其中的面、頂點(diǎn)和邊是用指南針的方向表示的，這樣做只是為了方便，實(shí)際上，多邊形網(wǎng)面上的方向與地球方位沒(méi)有任何關(guān)系.每一條翼邊允許對(duì)其對(duì)應(yīng)的多邊形頂點(diǎn)進(jìn)行掃描，例如，可沿著東北翼邊按順時(shí)針?lè)较驋呙钖|多邊形面各頂點(diǎn).圖13.2多邊形網(wǎng)面翼邊示意圖確定多邊形面是在東面還是西面取決于進(jìn)入翼邊緣數(shù)據(jù)結(jié)構(gòu)中多邊形面的順序.當(dāng)掃描一個(gè)多邊形面時(shí)，必須首先檢查此面是在邊緣的東面還是西面.如果此面在這條邊的東面，則沿著東北翼順時(shí)針掃描或沿著東南翼逆時(shí)針掃描；如果此面在此邊的西面，則沿著西南翼順時(shí)針掃描或沿著西北翼逆時(shí)針掃描.順時(shí)針、逆時(shí)針?lè)较蚴且杂^察者為中心的.順時(shí)針?lè)较蚴沁@樣確定的：左手大拇指指向此平面的法線方向，左手的其它手指方向就是沿此面的順時(shí)針?lè)较?；右手大拇指指向此面的法線方向，右手的其它手指方向就是沿此面的逆時(shí)針?lè)较?如果多邊形網(wǎng)面表示一個(gè)物體完整表面，則所有面的法線都向外.如果此多邊形網(wǎng)面表示一個(gè)曲面，則所有法線都指向此曲面的同一邊.如果此曲面是圖形曲面，則法線指向圖形空間坐標(biāo)的正坐標(biāo)軸方向，例如，如果多邊形網(wǎng)面為圖形表面zf（x,y），則此表面法線指向正z軸.在多邊形網(wǎng)面上增加一個(gè)多邊形面的方法見(jiàn)算法13.1，沿某一方向掃描多邊形面各頂點(diǎn)（或邊）的方法見(jiàn)算法13.2.在算法13.1中，假定頂點(diǎn)是沿著平面順時(shí)針?lè)较蚺帕械?適當(dāng)改進(jìn)算法13.2，可用于搜索一個(gè)給定頂點(diǎn)對(duì)應(yīng)的所有邊（或面）.算法13．1翼邊緣數(shù)據(jù)結(jié)構(gòu)上增加一個(gè)多邊形面的算法輸入是一個(gè)按順時(shí)針?lè)较蚺帕械亩噙呅蚊娴捻旤c(diǎn)表，包括頂點(diǎn)個(gè)數(shù)和頂點(diǎn)坐標(biāo)．1．對(duì)于頂點(diǎn)表中的每一個(gè)頂點(diǎn)，如果沒(méi)有出現(xiàn)在數(shù)據(jù)結(jié)構(gòu)中，則可增加該頂點(diǎn)記錄．2．對(duì)于每一對(duì)相鄰的頂點(diǎn)（包括起點(diǎn)和終點(diǎn)），如果其對(duì)應(yīng)的邊沒(méi)有出現(xiàn)在此數(shù)據(jù)結(jié)構(gòu)中，則可增加該邊記錄．3．對(duì)于多邊形的每一個(gè)邊記錄，增加翼邊，以便順時(shí)針或逆時(shí)針掃描該多邊形面．4．產(chǎn)生一個(gè)多邊形面記錄，并增加指針指向其中一個(gè)邊緣．算法13．2沿著多邊形面順時(shí)針跟蹤邊緣輸入是一個(gè)指向面記錄的指針和一個(gè)調(diào)用待訪問(wèn)邊的進(jìn)程．1．從面記錄中取出第一條邊，使之成為當(dāng)前邊．2．處理當(dāng)前邊，即對(duì)被訪問(wèn)的每一條邊完成所有的操作，如，沿著多邊形面順時(shí)針?lè)较蚓庉嬳旤c(diǎn)表，沿掃描方向記錄邊緣端點(diǎn)（頂點(diǎn)）．3．如果正在掃描當(dāng)前邊的西側(cè)面，則下一條邊將是西南翼．4．如果正在掃描當(dāng)前邊的東側(cè)面，則下一條邊將是東南翼．5．如果當(dāng)前邊是第一條邊，則掃描結(jié)束．6．否則，回到第2步．13．2．2曲面片曲面上的各部分可以用一個(gè)雙多項(xiàng)式表示．例如，平面可以表示為：z=a+ax+ay （13.7）012曲面片可以用更高階的多項(xiàng)式來(lái)表示.雙線性曲面片（線性是指任何平行于坐標(biāo)軸的截面的截線是一直線）：雙二次曲面片：z=a+ax+ay+axy0 1 2 3(13.8)z=a+ax+ay+axy+ax2+ay20 1 2 3 4 5(13.9)雙三次曲面片：(13.10)z=a+ax+ay+axy+ax2+ay20 1 2 3 4 5+ax3+ax2y+axy2+ay36 7 8 9雙四次曲面片z=a+ax+ay+axy+ax2+ay20 1 2 3 4 5+ax3+ax2y+axy2+ay36 7 8 9+ax4+ax3y+ax2y2+axy3+ay410 11 12 13 14(13.11)在機(jī)器視覺(jué)中，上述雙多項(xiàng)式經(jīng)常被用來(lái)表示曲面片.多項(xiàng)式曲面片非常適合于局部表面的表示，例如一個(gè)點(diǎn)的鄰域，但整個(gè)表面的表示不是很方便，而且不能表示非圖形曲面.更復(fù)雜的曲面可以用三次樣條函數(shù)來(lái)表示，這將在下節(jié)討論.13．2．3張量積曲面13.1.1節(jié)介紹了如何用參數(shù)形式將一個(gè)復(fù)雜曲線表示成一個(gè)三次多項(xiàng)式，此方法可以推廣到復(fù)雜曲面的參數(shù)表示.一個(gè)三次多項(xiàng)式參數(shù)方程的矩陣形式為：u3p(u)=u3p(u)=a aa012a〕3u2u(13．12)其中，每一個(gè)系數(shù)都是一個(gè)三元矢量．張量積曲面是由兩條曲線合成的，其參數(shù)形式如下：p(up(u,v)=u3a0a1v3u2 u1〕u2 u1lbbbb]v2a0 1 2 3v2a31(13．13)其中，a是三元行矢量，b是三元列矢量，a,b的積是每一個(gè)坐標(biāo)系數(shù)的雙積.此系數(shù)ijij曲面可以寫(xiě)為：p(p(u,v)=UTMV其中，(13．14)u3v3U2V=v2Uv11M是4X4矩陣，其元素是參數(shù)曲面的每一個(gè)坐標(biāo)系數(shù)的矢量.在這種表示中，我們可以看到張量積曲面確實(shí)是兩曲線的積：一條曲線以u(píng)為坐標(biāo)，另一條以v為坐標(biāo).任何平行于坐標(biāo)軸的平面和張量積三次多項(xiàng)式曲面的交線都是三次多項(xiàng)式曲線．換句話說(shuō)，如果其中一坐標(biāo)是常數(shù)，那么結(jié)果就是一條以其它兩個(gè)坐標(biāo)為參數(shù)的三次多項(xiàng)式曲線．13．2．4超二次曲面超二次曲面(superquadrics)由二次方程添加參數(shù)生成，這樣可以通過(guò)調(diào)整參數(shù)很方便地改變物體的形狀。增加的參數(shù)數(shù)目等同于物體的維數(shù)，比如，曲線是一個(gè)參數(shù)，曲面是兩個(gè)參數(shù)。(1)超橢圓在超橢圓相應(yīng)的方程中，允許x和y項(xiàng)的指數(shù)是變量，這樣可以得到橢圓的笛卡兒表示式。笛卡兒超橢圓方程的表示形式之一是：X2 y2()s+(—)s=1 (12.15)rrxy其中S參數(shù)是任何實(shí)數(shù)。當(dāng)s二1時(shí)，可以得到一般橢圓表示式。相對(duì)于方程(12.15)，超橢圓參數(shù)參數(shù)方程可以表示成：x=rcoss0x. —兀<0<兀 (12.16)y=rsins0y圖13.3表示了運(yùn)用不同的參數(shù)s值產(chǎn)生的超橢圓面形狀。

圖13.3不同參數(shù)值s對(duì)應(yīng)的超橢圓圖形（r=r）xy圖13.3不同參數(shù)值s對(duì)應(yīng)的超橢圓圖形（r=r）xy2）超橢圓球超橢圓球面的笛卡兒表達(dá)式是由橢圓球面方程增加二個(gè)指數(shù)參數(shù)而得：（蘭）:+（丄）:rrxyZ2+Clsi=1rz（12.17）當(dāng)s=s=1時(shí)，得到一般的橢球面。12對(duì)超橢球面的方程（12.17），我們可以得到相應(yīng)的參數(shù)表示式：x=rcoss1pcoss20x .八 一兀/2＜p＜兀/2y=rcoss1psins20y —兀＜0＜兀z=rsins1pz12.18）圖13?4表示了由不同參數(shù)si和s2值生成的超圓球形狀。這些及其它超二次曲面形狀的可以生成很復(fù)雜的形狀，如家具、閃電和其它金屬構(gòu)成。圖13?4不同參數(shù)s1和s2值生成的超圓球形狀（s1=叮13．3曲面插值本節(jié)將討論如何將上述曲面表示用于實(shí)際采樣值的曲面插值計(jì)算，比如，用均勻分布網(wǎng)面表示雙目立體測(cè)距或主動(dòng)三角測(cè)距系統(tǒng)獲得的深度圖。但是，如果原始深度圖不是均勻分布的，則無(wú)法用均勻分布的網(wǎng)面表示，此時(shí)就需要曲面插值．一般來(lái)說(shuō)，在對(duì)原始圖像進(jìn)行處理（如邊界檢測(cè)和分割）之前，首先需要將深度圖通過(guò)插值運(yùn)算將其表示成一個(gè)均勻變化的網(wǎng)面模式．

13．3．1三角形面插值假定通過(guò)雙目立體視覺(jué)系統(tǒng)或主動(dòng)三角測(cè)量系統(tǒng)得到一個(gè)曲面z=f(x,y)在離散點(diǎn)(x,y)處的采樣值z(mì)，k=1,2,A,n，下面討論如何在圖像陣列點(diǎn)［i,j］上通過(guò)三角面進(jìn)行kk k深度值插值計(jì)算．我們知道，不共線的空間三點(diǎn)可以構(gòu)成一個(gè)平面，平面方程為：(13．19)Z=a0+aiX+a2y(13．19)所以，已知非共線的空間三點(diǎn)，則可以確定上述方程的三個(gè)系數(shù)．我們知道，在nxm的圖像陣列上，每一點(diǎn)的坐標(biāo)(x,y)由下式計(jì)算:ji對(duì)于圖像陣列的每一點(diǎn)(x,y)，在深度圖中找出在x-y平面上包含該點(diǎn)的三個(gè)非共面的ji(13．20)點(diǎn)，根據(jù)(13．20)z=a+ax+ayij0 1j2i13．3．2二元線性插值二元線性函數(shù)可以表示為:f(x,y)=a+ax+ay+axy (13．21)0123如果把上式的一個(gè)變量設(shè)定為常數(shù)，則函數(shù)對(duì)于另一個(gè)變量就是線性變化的．換句話說(shuō)，任何一個(gè)平行于坐標(biāo)軸的平面和此二元線性表面片的交線都是一個(gè)直線段．對(duì)于四條邊皆平行于坐標(biāo)軸的任何矩形平面，有唯一的用于矩形頂點(diǎn)插值的二元線性多項(xiàng)式．假定我們要在一個(gè)矩形網(wǎng)格的四個(gè)頂點(diǎn)中間的一點(diǎn)(x,y)進(jìn)行插值，并設(shè)點(diǎn)(x,y)由四條邊都平行于坐標(biāo)軸的矩形包圍．此矩形的頂點(diǎn)坐標(biāo)是(x,y)，(x,y)， (x,y)，000110(x,y)，其函數(shù)值為z,z,z,z，見(jiàn)圖13.5.1100011011二元線性插值的系數(shù)是由矩形的4個(gè)頂點(diǎn)確定的，把每一個(gè)頂點(diǎn)的坐標(biāo)代入方程13.20，則系數(shù)滿足如下方程:z=a+ax+ay+axyTOC\o"1-5"\h\z00 0 10 20 300z=a+ax+ay+axy01 0 10 21 301 (13.22)z=a+ax+ay+axy0 11 20 310z=a+ax+ay+axy0 11 21 311聯(lián)立上述四個(gè)方程，得到系數(shù)求解出:a0a1a2xyz-xyz-xyz+a0a1a21100 1001 0110 0011(x1-x0)(y1-y0)yz+yz+yz-yz ^-00 ^-01 ^0 (13.23)(x1-x0)(y1-y0)(13.23)xz+xz+xz-xz ^-00 ^-04 ^^0 (x-x)(y-y)1010當(dāng)矩形網(wǎng)格是-00 01 10 11(x當(dāng)矩形網(wǎng)格是-00 01 10 11(x1-x0)(y1-y0)個(gè)行距和列距都是單位值的方格時(shí)，元線性插值有一個(gè)非常簡(jiǎn)單的表示.設(shè)要插值的點(diǎn)(X,y)示.設(shè)要插值的點(diǎn)(X,y)離方格的左上頂點(diǎn)的偏移量為(5x,Sy)，則雙線性插值公式為:f(址Sy)=z00+Sx(z10-z00)+Sy(z01-z00)+SxSy(z00此公式可用于插入像元之間的圖像點(diǎn)的像素值.-z-z+z)011011(13.24)圖13圖13．5二元線性插值示意圖13．3．3魯棒插值在7．4．3節(jié)中，我們介紹了用直線擬合含有局外點(diǎn)的邊緣集的最小中值二乘法(least-median-squares,LMS).最小中值二乘法也可用于曲面片擬合具有局外點(diǎn)的深度測(cè)量值集合．最小中值二乘法是一種魯棒回歸算法，其潰點(diǎn)值為50％，正好對(duì)應(yīng)于待擬合點(diǎn)集的中值的地方.局部最小中值二乘估計(jì)器使用最小中值二乘法求出擬合一個(gè)局部區(qū)域來(lái)的模型參數(shù)，即通過(guò)極小化殘差平方求解模型參數(shù)：(13.25)min{med[(z-f(x,y;a))2]}(13.25)a (Xi,ya (Xi,yi)eN 7y;a丿是在測(cè)量點(diǎn)(x,y,zi iii)處圖形曲面實(shí)際值的估計(jì).a是估計(jì)的參數(shù)矢量，i最小中值二乘法可以用于含有局外點(diǎn)的曲面采樣擬合模型的參數(shù)求解.例如，雙目立體視覺(jué)的錯(cuò)誤匹配，會(huì)造成錯(cuò)誤的深度測(cè)量值，即局外點(diǎn)，測(cè)距雷達(dá)也可能在曲面不連續(xù)點(diǎn)處產(chǎn)生局外點(diǎn).如果在用曲面片擬合深度測(cè)量值時(shí)使用最小中值二乘法，則這種曲面擬合對(duì)局外點(diǎn)不是十分敏感.特別需要指出，最小中值二乘法對(duì)曲面片擬合含有局外點(diǎn)的稀疏深度測(cè)量值是非常有用的.將最小中值二乘法簡(jiǎn)明地表示出來(lái)不是一件易事，但對(duì)此算法的實(shí)現(xiàn)卻很容易解釋.假設(shè)在每一個(gè)網(wǎng)格點(diǎn)附近的局部區(qū)域使用曲面片來(lái)擬合深度測(cè)量值.本算法可以很容易地推廣到使用更高階的曲片塊擬合?對(duì)于每一個(gè)網(wǎng)格點(diǎn)，選擇離此點(diǎn)最近的n個(gè)深度測(cè)量值，從n個(gè)測(cè)量值中任取m數(shù)據(jù)作為一個(gè)待擬合子集，則所有可能的數(shù)據(jù)子集為1＞個(gè)。用曲面片擬m合第k個(gè)數(shù)據(jù)點(diǎn)子集，a表示相關(guān)參數(shù)矢量，計(jì)算殘差平方中值：kX2=med[(z-f(x,y;a))2] (13.26)k i iiki用曲面片擬合所有的子集后，取最小的殘差平方中值對(duì)應(yīng)I的參數(shù)矢量ak.本方法計(jì)算成本較高，因?yàn)閷?duì)每一局部區(qū)域擬合都要進(jìn)行＞次.然而每一個(gè)曲面擬合m是獨(dú)立的，程序可以實(shí)現(xiàn)高度并行計(jì)算．在實(shí)際中，可以嘗試幾種可能的組合，使得無(wú)局外點(diǎn)子集的概率接近于1，這樣可以大大地減少許多不必要的擬合．13．4曲面逼近由于深度測(cè)量值存在誤差，因此找一個(gè)曲面來(lái)逼近深度數(shù)據(jù)比曲面插值更重要．如果深度測(cè)量值是一個(gè)連續(xù)曲面z=f(x,y)上的采樣點(diǎn)，那么完全可以由這些采樣點(diǎn)重建這個(gè)曲面．設(shè)重建曲面的模型為：z二f(X,y；a,a,A,a) (13.27)01 m-1該模型共包含m個(gè)參數(shù).該曲面重建問(wèn)題實(shí)際上成為確定最適合數(shù)據(jù)的曲面模型參數(shù)的回歸問(wèn)題，回歸函數(shù)為：X2二遲(z-f(X,y;a,a,A,a))2 (13.28)iii01 m-1i=0如果我們沒(méi)有曲面的參數(shù)模型，則只能使用一.個(gè)普通(或非參數(shù)化〕曲面模型來(lái)擬合此數(shù)據(jù)，即求解這些數(shù)據(jù)的一個(gè)最佳擬合曲面z=f(x,y):X2=^(z-f(x,y))2 (13.29)i iii=0這是一個(gè)不適定(ill-posed)問(wèn)題，因?yàn)樵S多函數(shù)多可以對(duì)該數(shù)據(jù)集實(shí)現(xiàn)最佳擬合(實(shí)際上，這樣的函數(shù)有無(wú)窮多個(gè)).不適定這一術(shù)語(yǔ)的意思是問(wèn)題的求解不唯一，反過(guò)來(lái)，適定問(wèn)題(well-posed)會(huì)有唯一的最優(yōu)解.為了能使方程13.29變?yōu)檫m定，可以增加一個(gè)逼近約束函數(shù)，使得所選擇的曲面擬合函數(shù)有唯一解.選擇約束函數(shù)的標(biāo)準(zhǔn)有許多，一種比較常用的標(biāo)準(zhǔn)是選擇既能擬合數(shù)據(jù)又是光滑表面的函數(shù). ( )已知數(shù)據(jù)點(diǎn)集｛(x,y,z)｝，i=1,2,A,n，則使下式達(dá)到極小化的z=f(x,y)是該數(shù)據(jù)iii點(diǎn)集的最佳擬合，X2=藝(z-f(x,y))2+aJJ(學(xué)+2f雪+學(xué))dxdy (13.30)iii ox2 oxdyoy2i=0其中a>0。該方程與13.29式不同之處是增加了一項(xiàng)加權(quán)光滑約束項(xiàng)?光滑約束項(xiàng)叫做正則項(xiàng)或穩(wěn)定函數(shù).權(quán)重系數(shù)a稱為正則化參數(shù)，a較小時(shí)，可以使得逼近函數(shù)十分靠近數(shù)據(jù)點(diǎn)集，而a較大時(shí)，則強(qiáng)迫逼近函數(shù)更平滑.上面方程的第一個(gè)項(xiàng)稱為問(wèn)題約束，在該約束上通過(guò)增加穩(wěn)定函數(shù)將不適定問(wèn)題變?yōu)檫m定問(wèn)題的過(guò)程叫正則化(regularization).適定這一的概念遠(yuǎn)比求唯一解嚴(yán)格的多，比如，方程13．29的擬合問(wèn)題可能有唯一解，但是解空間中還有其它許多完全不同的解可能也是好的解，而一個(gè)適定問(wèn)題只有一個(gè)解空間，該解對(duì)應(yīng)的范數(shù)的最小值不僅是唯一的，而且肯定比其它解更好．13．4．1回歸樣條回歸樣條法是另一種曲面擬合方法。用曲面模型(如張量積樣條函數(shù))代替方程13．29的擬合函數(shù)，該方程就變?yōu)橐粋€(gè)回歸問(wèn)題，求解這一問(wèn)題，就得到了該曲面模型的參數(shù)．當(dāng)然，如果知道曲面模型，那么就可以直接列出回歸問(wèn)題的方程，而不必經(jīng)過(guò)方程13．29。許多曲面函數(shù)，包括張量積樣條函數(shù)，可以表示為基本函數(shù)的線性組合:f(x,y;a,a,A,a)=aB(x,y) (13．31)01 m-1 iii=0a為函數(shù)系數(shù)，B為基本函數(shù)．使用張量積樣條可以將基本函數(shù)組合成為一個(gè)網(wǎng)格:iiSn—1乙a..B..(x,y) (13.32)ijiji=0 .=0將方程13.31或13.32的曲面模型代入方程13．28，得到一組求解回歸參數(shù)的線性方程組．因?yàn)榉匠探M是稀疏的，因此，用稀疏矩陣方法求解比用奇異值求解要好．下面將從一維情況開(kāi)始，詳細(xì)介紹回歸樣條計(jì)算方法.一維B樣條函數(shù)是基本函數(shù)的線性組合:

aB(x) (13.33)iii=0假設(shè)B樣條基本函數(shù)均勻分布整數(shù)位置，B樣條基本函數(shù)在區(qū)間［i,i+4)是非零的，基本函數(shù)位于從0到m，所以決定B樣條基本曲線的形狀的有m個(gè)系數(shù)(見(jiàn)圖13.6)。有一個(gè)B樣條曲線是定義在區(qū)間從x=3到x=m+1,在x=0點(diǎn)的基本函數(shù)跨越3個(gè)區(qū)間到此曲線的左端，在x=m+1點(diǎn)的基本函數(shù)跨越3個(gè)區(qū)間到達(dá)此曲線的右端.曲線端點(diǎn)以外的額外區(qū)間建立了曲線端點(diǎn)的邊界條件，而且必須要包括進(jìn)來(lái)，那樣才能正確地定義第一個(gè)曲線段［0，1)和最后一個(gè)曲線段［m,m+1).每一個(gè)B樣條函數(shù)在4個(gè)整數(shù)區(qū)間上都是非零的，因?yàn)榛竞瘮?shù)重疊，每一區(qū)間都被4個(gè)基本函數(shù)覆蓋.基本函數(shù)B(x)的每一段b.(x)是僅定義它的單位區(qū)間上的三次多項(xiàng)式，ii如圖13.7所示，B樣條函數(shù)的每一段的三次多項(xiàng)式如下：b(x)=‘67/、 1+3x+3x2-3x3b(x)=(13.(13.34)7/、 4-6x2+3x3b(x)=21—3x+3x2—x3b(x)=36如果簡(jiǎn)單地把這些三次多項(xiàng)式相加以得到B樣條基本函數(shù)是不正確的，因?yàn)槊恳欢味枷拗朴谒膮^(qū)間，這就是，每一段在它適用的區(qū)間之外必須被視為非零的.為了在特殊點(diǎn)x估計(jì)特殊B樣條基本函數(shù)，有必要確定x位于哪一段和估計(jì)相對(duì)應(yīng)的三次多項(xiàng)式.假設(shè)x位于區(qū)間［i,i+1)，B樣條曲線是每m+1個(gè)B樣條基本函數(shù)的線性組合如式13.33.因?yàn)槊恳粋€(gè)B樣條基本函數(shù)占四個(gè)區(qū)間(單位)，［i,i+1)上是B(x)，左邊順次是B1C),B2(x),B3(x),所以為了估計(jì)當(dāng)x在區(qū)間[i,i+1)上的B樣條曲線，只需估計(jì)此區(qū)間上的四個(gè)B樣條基本函數(shù)的線性組合:)aBvx)+aBvx)+aBvx)+aBvx) (13.35)i—3i—3 i—2i—2 i—1i—1 ii因?yàn)槊恳粋€(gè)B樣條基本函數(shù)包含4個(gè)三次多項(xiàng)式，其中每一段都定義在其各自的區(qū)間上，只需估計(jì)在三次樣條曲線被估計(jì)的區(qū)間上的三次多項(xiàng)式段即可.在區(qū)間[i,i+1)上的x點(diǎn)B樣條曲線的值為：(1一3x+3x2一x3)a—+(1一3x+3x2一x3)a—+(4一6x2+3x3)a i—2(1+3x+3x2—3x3)a. x3ai1 i66(13.36)為了在任何位置估計(jì)B樣條曲線，有必要確定x所在的區(qū)間，并代入方程13.36,下標(biāo)i表示區(qū)間的起點(diǎn)，那么4個(gè)B樣條基本函數(shù)的系數(shù)才是正確的.方程13.36中的估計(jì)B樣條曲線的公式可以用于線性回歸，因?yàn)槟Ｐ驮谙禂?shù)上是線性的.方程包含術(shù)語(yǔ)x的幕，這并沒(méi)有什么影響.此模型可以用于下面的回歸算法，此算法用于從一系列數(shù)據(jù)點(diǎn)(x,z)中確定B樣條的系數(shù).每一數(shù)據(jù)點(diǎn)可得到一個(gè)約束4個(gè)B樣條系ii數(shù)的方程：(1—3x+3x2—x3)a (4—6x2+3x3)ai i ii—3i ii_266(1+3x+3x2—3x3)a x3a+ i i i +―i——J=Z66i這些方程組成一個(gè)線性方程組：Ma二b(13.37)(13.38)其中，a是B樣條系數(shù)a?的列矢量，方程右側(cè)的列矢量b是z的矢量，除了在相對(duì)應(yīng)在包ii含x的區(qū)間上的B樣條基本函數(shù)的系數(shù)的4個(gè)元素外，矩陣M的其它元素都為0此線性方程組可用單值求解法來(lái)求.但因?yàn)榇朔匠探M是稀疏的，最好用稀疏矩陣方法.對(duì)于三維曲面擬合，模型是一張量積B樣條曲面：f(x,y)二SSaB(x,y)二SSaB(x)B(y)ijij ijj ii=0j=0 i=0j=0曲面擬合問(wèn)題可以通過(guò)使下式最小化來(lái)求解.X2=S(z(k)—f(x,y))2=S[z(k)—(SSaB(x,y)]2ijijk=0 k=0 i=0j=0(13.39)(13.40)數(shù)據(jù)值之涉及一個(gè)下標(biāo)，因?yàn)榇藬?shù)據(jù)只在此平面的離散點(diǎn)上，每一個(gè)數(shù)據(jù)值z(mì)k位于x-y平面的點(diǎn)(x,y).kk確定張量積b樣條曲面系數(shù)的回歸問(wèn)題的公式化是和以前介紹的一維情況有點(diǎn)相似.每一個(gè)基本函數(shù)B..(x，y)占16個(gè)網(wǎng)面矩形[i,i+4]X[j,j+4].因?yàn)榛竞瘮?shù)重疊，所以每一ij個(gè)網(wǎng)面矩形上有16個(gè)基本函數(shù).每一個(gè)基本函數(shù)包括16個(gè)二元三次多項(xiàng)式塊.每一塊定義在一個(gè)網(wǎng)面矩形上，在此網(wǎng)面矩形外是非零的.假設(shè)此網(wǎng)面是均勻的，所以所有網(wǎng)面矩形都是大小相同的方格.此B樣條基本函數(shù)中的二元三次多項(xiàng)式塊的公式對(duì)每一方格都是相同的.每一張量積基本函數(shù)可分寫(xiě)成一維基本函數(shù)的積：Bij(x,y)=Bj(x)Bi(y) (13.41)ij j i每一個(gè)一維基本函數(shù)包括4個(gè)三次多項(xiàng)式，定義在小網(wǎng)面矩形上的16個(gè)多項(xiàng)式塊中的每一個(gè)都是兩個(gè)三次多項(xiàng)式的積，其中一個(gè)以x為變量，另一個(gè)以y為變量，以x為變量的4個(gè)三次多項(xiàng)式見(jiàn)式13.34，同樣有以y為變量的4個(gè)三次多項(xiàng)式為：b(y)=—06b(y)=1+3y+3y2-3y31 6 (13.42)b(y)=4-6y2+3y326b(y)=1-3y+3y2-y336B樣條基本函數(shù)的16個(gè)多項(xiàng)式塊是由前面給的多項(xiàng)式兩兩相乘得到的，在網(wǎng)面的點(diǎn)(x,y),估計(jì)B樣條前面的公式如下：乙乙ab.(x)b.(y)ijjii=0j=0用此公式代替一維三次多項(xiàng)式就得到估計(jì)B樣條曲面的公式，16個(gè)系數(shù)的每(13．43)項(xiàng)為：a x3(13．43)項(xiàng)為：a x3.18+(x3y+x3y2一x3y3).6i,j-1 'a 2x39—x3y2..3—x3y3.6i,j-2a x3-3x3y+3x3y2-x3y^.-18i,j-3a (1+3x+3x2-3x3)y3：18i-1,ja (1+3x+3x2-3x3).18+(1+3x+3x2-3x3)y6i-1,j-1 .+(1+3x+3x2-3x3)y2J6-(1+3x+3x2-3x3)y3J6a2(1+3x+3x2—3x3)■■9—(1+3x+3x2—3x3)y2■■3i-1,j—2+(1+3x+3x2-3x3)y3/6a (1+3x+3x2-3x3)18-(1+3x+3x2-3x3)y.6i-1,j-3+(1+3x+3x2-3x3)y2/6-(1+3x+3x2-3x3)y3^18a (4-6x2+3x3)y3.18i-2,j 'a (4-6x2+3x3).：18+(4-6x2+3x3)y6i-2,j-1+(4-6x2+3x3)y2/6-(4-6x2+3x3)y3J6a2(4-6x2+3x3)9-(4-6x2+3x3)y2i-2,j-2 '+(4-6x2+3x3)y3/6a (4-6x2+3x318-(4-6x2+3x3)y6i-2,j-3 '+(4-6x2+3x3)y2/6-(4-6x2+3x3)y3/18a (1-3x+3x2-x3)y318i-3,ja (1-3x+3x2-x3)18+(1-3x+3x2-x3)y.6i-3,j-1+(1-3x+3x2-x3)y2/6-(1-3x+3x2-x3)y3/6a 2(1-3x+3x2-x3)9-(1-3x+3x2-x3)y26i-3,j-2+(1-3x+3x2-x3)y3/6a (1-3x+3x2-x3).18-(1-3x+3x2-x3)y6i-3,j-3 '+(1-3x+3x2-x3)y2/6-(1-3x+3x2-x3)y3^18

這些表示是在點(diǎn)(x,y)處估計(jì)的，乘以對(duì)應(yīng)的系數(shù)a，求和得到在(x,y)處的B樣條曲面.i,j估計(jì)B樣條曲面的公式也就是用于確定B樣條曲面的回歸問(wèn)題的模型.在B樣條曲面中有(n+l)(m+l)個(gè)系數(shù).每一數(shù)據(jù)點(diǎn)(x,y,z)得到一個(gè)包括16個(gè)系數(shù)的方程.如同在一kkk維情況下，回歸問(wèn)題可得到一個(gè)線性方程組：Ma=b (13.44)其中a是B樣條系數(shù)的矢量，右側(cè)的列矢量b是數(shù)據(jù)值x,k=12,AN,N的矢量.除k了對(duì)應(yīng)在包含(x,y)的方格上的基本函數(shù)的16個(gè)元素矩陣M的每一行為0.kk此方法可通過(guò)擬合B樣條曲面到均勻像元和采樣樣條曲面來(lái)使圖像平滑.對(duì)B樣條網(wǎng)面來(lái)說(shuō)沒(méi)有必要和圖像網(wǎng)面相對(duì)應(yīng);實(shí)際上，如果B樣條網(wǎng)面有更大的空間，也就更光滑.B樣條基本函數(shù)象高斯光滑濾波器(第四章介紹過(guò))，而且，B樣條基本函數(shù)的寬度是由B樣條網(wǎng)面的空間決定的.當(dāng)使用以前介紹的用于B樣條網(wǎng)面回歸問(wèn)題的公式時(shí)，在圖像上像元值為z..的位置(x,y)被映射到B樣條曲面的網(wǎng)面坐標(biāo)系中.B樣條曲面可按需采樣，在原始ijji圖像的網(wǎng)面點(diǎn)坐標(biāo)處，為了計(jì)算光滑圖像的像元.B樣條曲面方程的優(yōu)化表明B樣條只是一系列13.5.2節(jié)中介紹的二元三次曲面塊.二元三次曲面塊和B樣條曲面之間的區(qū)別只是B樣條曲面的二元三次塊在塊所在區(qū)域是二階連續(xù)的，而任意二元三次塊根本不需要連續(xù).張量積B樣條曲面是光滑的，而且還是二階連續(xù)的，可以用于如身體器官、車(chē)體、飛機(jī)機(jī)身的建模.在許多實(shí)際應(yīng)用中，張量積B樣條曲面必須是參數(shù)形式(x,y,z)=(x(u,v)yC,v)zC,v如13.4.3節(jié)介紹過(guò)的一樣，在回歸問(wèn)題中反應(yīng)曲面的系數(shù)是三元矢量，每一個(gè)元素對(duì)應(yīng)x，y，z中的一個(gè)坐標(biāo).u，v空間是平面直角坐標(biāo)系，被分為均勻的網(wǎng)面.最困難的是構(gòu)造把點(diǎn)(x,y,z)映射到u，v空間的公式，那樣此測(cè)量點(diǎn)就能正確地和組成B樣條曲面的二元三次曲面塊聯(lián)系起來(lái).13．4．2加權(quán)樣條逼近目前介紹的曲面逼近方法的問(wèn)題是：甚至在曲面邊界的數(shù)據(jù)不連續(xù)，解還是光滑曲面.在l13.6.1節(jié)介紹的回歸樣條的光滑的無(wú)參數(shù)函數(shù)是隱含的.如果擬合曲面可以公式化為一系列分段光滑函數(shù)，深度測(cè)量值為：l(13.45)l=0以分成數(shù)個(gè)區(qū)域，每個(gè)區(qū)域?qū)?yīng)一個(gè)分段光滑函數(shù)，那樣解能更準(zhǔn)確地反應(yīng)此處曲面的形狀.然而這會(huì)得到一些用于計(jì)算某些曲面的算法，這些超出了本書(shū)的范圍.13.7節(jié)中將討論曲面分割的問(wèn)題.我們可以避開(kāi)曲面表示中的一些比較難的課題，而且通過(guò)改變方程13.5.2的光滑性函數(shù)以降低深度數(shù)據(jù)不連續(xù)處的光滑性，仍然獲得了符合不連續(xù)性的非常好的曲面擬合.此方法就是加權(quán)正則化方法.一維的加權(quán)正則化式子為：工(y工(y-f(x))2+iiJw(x,y)[f(x)]2dxxx(13.46)i=1如果權(quán)函數(shù)w(x)在數(shù)據(jù)不連續(xù)點(diǎn)取值非常小，在其它地方大，那么權(quán)函數(shù)就消去了不連續(xù)點(diǎn)的連續(xù)標(biāo)準(zhǔn).在二維情況下，加權(quán)樣條曲面擬合的公式如下：X2權(quán)函數(shù)為：(13.47)=藝(z-f(x,y))2+JJw(x,y)(學(xué)+2ff+學(xué))dxdyX2權(quán)函數(shù)為：(13.47)iii ex2 oxcy cy2i=0

w(x,y)= (13.48)1+||p(x,y)||2其中P(x,y)是采樣曲面的梯度.應(yīng)指出的是來(lái)自方程13.29的正則化參數(shù)a已溶入權(quán)函數(shù).可以用變分法把方程13.47變?yōu)槠⒎址匠?，或者用回歸樣條方法取代具有線性回歸問(wèn)題的方程13.47.假定在張量積基本函數(shù)定義的網(wǎng)面的區(qū)域上的權(quán)是常數(shù)，就可以從梯度擬合中計(jì)算出方程13.47中的權(quán)函數(shù).13.5曲面分割一幅距離圖像可以看作是如下分段光滑曲面均勻采樣的網(wǎng)格：z=f(x,y) (13.49)本節(jié)將討論如何將定義在均勻網(wǎng)格上的一組距離采樣值分割成具有相似曲率的區(qū)域，并用低階的雙變量多項(xiàng)式來(lái)逼近每一個(gè)區(qū)域.表面曲率特性可用來(lái)選取核區(qū)域，然后增長(zhǎng)核區(qū)域以覆蓋鄰近距離采樣值，核區(qū)域的增長(zhǎng)準(zhǔn)則是鄰近距離采樣值與逼近核區(qū)域的雙變量多項(xiàng)式之間的偏差小于某一預(yù)先給定的閾值。曲面分割問(wèn)題通常表述如下，將分段光滑的曲面z=f(x,y)分割成光滑曲面基元(13.50)z二f(x,y)二尸f(x,y兀(x,y,l)(13.50)ll=0其中g(shù)(x,y,1)為特征函數(shù)，表示將曲面劃分成表面片的一種分割,E(E(x,y,1)=\0如果(x,y)eR1其它lR1表示第1個(gè)區(qū)域，它對(duì)應(yīng)一個(gè)曲面基元，每一個(gè)區(qū)域可以用如下多項(xiàng)式逼近：f(x,y)=工axiyj (x,y)eR (12.51)ij 1i+j<m此模型包括平面、雙線性、雙三次、雙四次多項(xiàng)式曲面片.特征函數(shù)E(x,y,1)可以通過(guò)每一區(qū)域像素位置［i,j］的列表來(lái)實(shí)現(xiàn)，也可以使用其它表示如模板、四叉樹(shù)等來(lái)實(shí)現(xiàn).13．5．1初始分割通過(guò)計(jì)算曲面的平均曲率H和高斯曲率K,并使用H和K的正負(fù)號(hào)，可以估計(jì)用于分割的初始核區(qū)域，以形成初始區(qū)域分割。對(duì)應(yīng)于平均曲率和高斯曲率正負(fù)號(hào)的曲面有8種類型，表13.1所示，這些曲面類型可以用于構(gòu)造核區(qū)域.K[i,j]+0一—峰脊鞍脊0平面最小曲面+谷谷鞍谷假設(shè)距離函數(shù)分布在均勻網(wǎng)格上，因此可以按照一般圖象進(jìn)行處理。用可分離濾波器與距離圖象進(jìn)行卷積來(lái)估計(jì)距離圖象的一階和二階導(dǎo)數(shù)f,f,f,f,f.使用距離圖像的xyxxxyyy一階和二階導(dǎo)數(shù)計(jì)算平均曲率和高斯曲率

(1+f2[i,(1+f2[i,j])f[i,j]+(1+f2[i,j])f[i,j]-2f[i,j]f[i,j]f[i,j]H[i,j]=y xx 卜x 號(hào)x y xy(13．52)+f2[i,j]+f2[i,j]x yf[i,j]f [i,刀—f2[i,j]K[l,j]=xx yy xl(1+f2[i,j]+f2[i,j])2

xy

使用下面公式計(jì)算整數(shù)標(biāo)記以實(shí)現(xiàn)平均曲率和高斯曲率正負(fù)號(hào)編碼．T[i,j]=1+3(1+sgn(H[i,j]))+(1+sgn(K[i,j]))13．53)(13．54)然后使用序貫連通成份算法（見(jiàn)第三章），將具有相同符號(hào)標(biāo)記組成一個(gè)連通區(qū)域，并使用收縮或腐蝕算法把每一個(gè)連通區(qū)域減少到可作為核區(qū)域的最大尺寸區(qū)域，使用濾波器將那些無(wú)法對(duì)應(yīng)場(chǎng)景曲面片的太小的區(qū)域?yàn)V掉。最后剩下的區(qū)域構(gòu)成區(qū)域增長(zhǎng)的種子．13．5．2曲面片增長(zhǎng)距離圖象中的每一個(gè)核區(qū)域可以用雙變量多項(xiàng)式有效地?cái)M合。擬合多項(xiàng)式一般從一階（平面）開(kāi)始，然后逐漸增加多項(xiàng)式（曲面）的階數(shù)，直到曲面能夠很好地?cái)M合核區(qū)域?yàn)橹?。如果多?xiàng)式階數(shù)已經(jīng)很高，但仍然無(wú)法得到滿意的擬合結(jié)果，則該區(qū)域不能作為核區(qū)域。接下來(lái)的工作是核區(qū)域擴(kuò)展，以便覆蓋核區(qū)域更多相似的鄰近點(diǎn)，即把那些沒(méi)有標(biāo)記的距離像素通過(guò)增長(zhǎng)過(guò)程添加到相應(yīng)的核區(qū)域中去。決定鄰近點(diǎn)是否添加到核區(qū)域中的相似性準(zhǔn)則是鄰近點(diǎn)與雙變量多項(xiàng)式之間的偏差均方根，也稱為擬合殘差。如果該殘差小于預(yù)定的閾值，則該鄰近點(diǎn)為區(qū)域侯選點(diǎn)。在找到所有的侯選點(diǎn)以后，再使用雙變量多項(xiàng)式對(duì)核區(qū)域和侯選點(diǎn)一起重新進(jìn)行擬合，如果需要的話，可以考慮增加雙變量多項(xiàng)式的階數(shù)，使得所有點(diǎn)都滿足相似性準(zhǔn)則。如果擬合殘差小于預(yù)定的閾值，則所有侯選點(diǎn)與核區(qū)域共同組成一個(gè)大區(qū)域；否則，放棄所有的侯選點(diǎn)。當(dāng)沒(méi)有區(qū)域能夠再擴(kuò)大時(shí)，區(qū)域增長(zhǎng)過(guò)程終止。用于曲面分割的區(qū)域增長(zhǎng)算法見(jiàn)算法13．3．算法13．3曲面分割算法1．使用可分離濾波器，計(jì)算距離圖象的一階和二階偏導(dǎo)數(shù)，2．計(jì)算圖象每一個(gè)像素位置的平均曲率和高斯曲率，3．對(duì)每一像素標(biāo)記曲面類型，4．收縮區(qū)域以消除靠近區(qū)域邊界的錯(cuò)誤標(biāo)記，5．使用序貫連通成份算法識(shí)別核區(qū)域，6．去掉太小的核區(qū)域，7．用雙變量多項(xiàng)式擬合每一個(gè)核區(qū)域，8．從某一核區(qū)域開(kāi)始，將滿足相似性準(zhǔn)則的核區(qū)域鄰近點(diǎn)標(biāo)記為該區(qū)域侯選點(diǎn)，9．