《北理工賈云德《計(jì)算機(jī)視覺》chapter13三維場景表示》由會員分享，可在線閱讀，更多相關(guān)《北理工賈云德《計(jì)算機(jī)視覺》chapter13三維場景表示（18頁珍藏版）》請?jiān)谘b配圖網(wǎng)上搜索。

1、精選優(yōu)質(zhì)文檔-----傾情為你奉上 第十三章　三維場景表示 三維場景表示是機(jī)器視覺的又一個關(guān)鍵技術(shù)．為了理解場景并與場景中的物體交互作用，必須將場景的三維數(shù)據(jù)進(jìn)行有效的表示．三維場景表示包含有兩個基本問題：場景重建和場景分割．場景重建(reconstruction)是指使用插值或擬合方法從采樣點(diǎn)(稠密深度測量值或稀疏深度測量值)計(jì)算曲面的連續(xù)函數(shù)，實(shí)際中通常使用許多三角片或小平面片構(gòu)成的網(wǎng)面來近似表示場景深度測量值；場景分割是將表示場景的網(wǎng)面分割成若干部分，每一部分表示一個物體或一個特定的區(qū)域，這樣有利于物體識別、曲面精確估計(jì)等后處理算法的實(shí)現(xiàn)． 　　本章從曲面的幾何特征開始，討

2、論場景曲面重建和分割的一些基本方法．這些方法可以將雙目立體測距、主動三角測距、激光雷達(dá)測距等成像系統(tǒng)的輸出值轉(zhuǎn)換成簡單的曲面表示．這些基本方法包括把測量點(diǎn)轉(zhuǎn)變成三角片網(wǎng)面、把距離測量值分割成簡單的曲面片、把測量點(diǎn)擬合成一個光滑曲面以及用測量點(diǎn)匹配一個曲面模型等． 13．1 三維空間曲線 　　討論三維空間曲線的原因主要有兩個，一是一些物體或物體特征可以直接用三維空間曲線表示，二是三維空間曲線表示可以推廣到三維空間曲面表示。曲線表示有三種形式：隱式、顯式和參數(shù)式。在機(jī)器視覺領(lǐng)域中，曲線的參數(shù)表示比隱式和顯式表示更為常用。三維曲線的參數(shù)形式為： (13．1) 上式

3、說明曲線上的一點(diǎn)可由參數(shù)表示的三個函數(shù)來定義，曲線的起點(diǎn)為，終點(diǎn)為。比如，從到的直線段的參數(shù)方程為： 　　　　　　　　　　（13．2） 　　空間曲線的最通常的表示形式是三次多項(xiàng)式，下面我們將詳細(xì)討論． 13．1．1 三次樣條曲線 物體表面上的線條可以是直線、弧線或是任意的曲線．曲線上的每一點(diǎn)位置可以表示成參數(shù)形式．一般的三維曲線都可以方便地用樣條函數(shù)來表示，這和前面討論的平面曲線表示類似．三次樣條函數(shù)是一系列首尾相連的表示復(fù)雜曲線的三次多項(xiàng)式曲線，每一段三次樣條函數(shù)的參數(shù)表示形式為：

4、(13．3) 其中．三次多項(xiàng)式允許曲線通過確定的相切點(diǎn)，三次多項(xiàng)式是對于非平面曲線的最低階的多項(xiàng)式．將上式的系數(shù)表示成如下系數(shù)矢量： (13．4) 而且，則三次多項(xiàng)式曲線可以重寫為如下形式： (13．5) 更復(fù)雜的曲線可以表示為一系列首尾相連的三次多項(xiàng)式： 　 　 (13．6) 其中．如果定義第個三次多項(xiàng)式段在單位區(qū)間上，那么整個區(qū)間則

5、為．可以認(rèn)為，這個三次多項(xiàng)式序列是起點(diǎn)為，終點(diǎn)為的單一參數(shù)曲線．這個三次多項(xiàng)式序列叫做一個三次樣條函數(shù)，它是機(jī)器視覺和計(jì)算機(jī)圖形學(xué)中表示任意曲線的常用方式． 13．1．2 三維B樣條曲線 　　三維B樣條曲線很適合表示由點(diǎn)序列構(gòu)成的曲線，因此可以將二維B樣條的定義擴(kuò)展到控制點(diǎn)位于三維空間的三維B樣條。例如對已知三維點(diǎn)序列，由等式（7.28）給出第階三次多項(xiàng)式，而由等式（7.31）給出．三維B樣條曲線也不通過控制點(diǎn)． 13．2 三維空間曲面的表示 　　本節(jié)將討論機(jī)器視覺中常用的幾種曲面表示． 13．2．1多邊形網(wǎng)面 平面多邊形，也叫平面片(planar patch)，可以組成復(fù)雜的網(wǎng)面

6、（polygon mesh），以表示各種物體的形狀．圖13.1三角形網(wǎng)面和四邊形網(wǎng)面示意圖。本節(jié)將介紹如何用平面片進(jìn)行物體多邊形網(wǎng)面表示． 圖13.1 物體表面的網(wǎng)面表示，(a) 三角形網(wǎng)面表示，(b)四邊形網(wǎng)面表示 第七章討論了如何用若干個直線段端點(diǎn)（頂點(diǎn)）坐標(biāo)表來表示一個多直線段，這一方法也可推廣到平面多邊形，即平面多邊形網(wǎng)面也可以用一系列平面多邊形頂點(diǎn)坐標(biāo)表來表示．一個頂點(diǎn)常常是三個或三個以上多邊形的公共頂點(diǎn)，因此，一個頂點(diǎn)在表中重復(fù)出現(xiàn)多次．為了使多邊形網(wǎng)面的每一個頂點(diǎn)在表中僅出現(xiàn)一次，可以使用一種間接的頂點(diǎn)坐標(biāo)表示方法，即對這些頂點(diǎn)從1到進(jìn)行編號，并按這一順序

7、將每一個頂點(diǎn)的坐標(biāo)存入表中．每一個多邊形可用其頂點(diǎn)編號表表示．不過這種頂點(diǎn)表不能明顯地表示相鄰表面的邊界，對于一給定頂點(diǎn)，也不能有效地發(fā)現(xiàn)所有包含此頂點(diǎn)的表面．這些問題可以用翼邊緣數(shù)據(jù)結(jié)構(gòu)(Winged Edge Data Structure)來解決． 　　翼邊緣數(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ǎng)面，也無須將每一元素的所有鄰接元素都存儲起來．在多邊形網(wǎng)面中，每一個頂點(diǎn)對應(yīng)數(shù)據(jù)結(jié)構(gòu)中的一個頂點(diǎn)記錄，每一個面對應(yīng)一個面記錄、每一條邊對應(yīng)一個邊記錄。這樣，可以直接查詢一條邊對應(yīng)的兩個頂點(diǎn)和兩個多邊

8、形面，也可以直接查詢一個頂點(diǎn)對應(yīng)的所有多邊形面（或邊），查詢時間正比于該頂點(diǎn)對應(yīng)的多邊形面（或邊）的數(shù)量． 翼邊緣數(shù)據(jù)結(jié)構(gòu)可以有效地表示三角面網(wǎng)面及其它具有多條邊的多邊形網(wǎng)面，并且不要求各個多邊形面的邊數(shù)相等．由于各頂點(diǎn)坐標(biāo)包含在頂點(diǎn)記錄中，因此，多邊形面（或邊）的位置可以由頂點(diǎn)的坐標(biāo)計(jì)算出來． 每一個面記錄指向該面的某一個邊記錄，每一個頂點(diǎn)記錄指向該頂點(diǎn)對應(yīng)的邊記錄。因此，邊記錄包含將多邊形面及其頂點(diǎn)連結(jié)成多邊形網(wǎng)面的指針，并且允許對多邊形網(wǎng)面頂點(diǎn)進(jìn)行快速的掃描．具體地說，每一個邊記錄包含有兩個端點(diǎn)指針，其兩側(cè)的兩個多邊形面指針和4個鄰接翼指針，如圖13．2所示。其中的面、頂點(diǎn)和邊是用指

9、南針的方向表示的，這樣做只是為了方便，實(shí)際上，多邊形網(wǎng)面上的方向與地球方位沒有任何關(guān)系．每一條翼邊允許對其對應(yīng)的多邊形頂點(diǎn)進(jìn)行掃描，例如，可沿著東北翼邊按順時針方向掃描東多邊形面各頂點(diǎn)． 圖13．2 多邊形網(wǎng)面翼邊示意圖 　　確定多邊形面是在東面還是西面取決于進(jìn)入翼邊緣數(shù)據(jù)結(jié)構(gòu)中多邊形面的順序．當(dāng)掃描一個多邊形面時，必須首先檢查此面是在邊緣的東面還是西面．如果此面在這條邊的東面，則沿著東北翼順時針掃描或沿著東南翼逆時針掃描；如果此面在此邊的西面，則沿著西南翼順時針掃描或沿著西北翼逆時針掃描．順時針、逆時針方向是以觀察者為中心的．順時針方向是這樣確定的：左手大拇指指向此平面的法

10、線方向，左手的其它手指方向就是沿此面的順時針方向；右手大拇指指向此面的法線方向，右手的其它手指方向就是沿此面的逆時針方向．如果多邊形網(wǎng)面表示一個物體完整表面，則所有面的法線都向外．如果此多邊形網(wǎng)面表示一個曲面，則所有法線都指向此曲面的同一邊．如果此曲面是圖形曲面，則法線指向圖形空間坐標(biāo)的正坐標(biāo)軸方向，例如，如果多邊形網(wǎng)面為圖形表面，則此表面法線指向正軸． 在多邊形網(wǎng)面上增加一個多邊形面的方法見算法13．1，沿某一方向掃描多邊形面各頂點(diǎn)（或邊）的方法見算法13．2．在算法13．1中，假定頂點(diǎn)是沿著平面順時針方向排列的．適當(dāng)改進(jìn)算法13．2，可用于搜索一個給定頂點(diǎn)對應(yīng)的所有邊(或面)．

11、 　　 算法13．1 翼邊緣數(shù)據(jù)結(jié)構(gòu)上增加一個多邊形面的算法 輸入是一個按順時針方向排列的多邊形面的頂點(diǎn)表，包括頂點(diǎn)個數(shù)和頂點(diǎn)坐標(biāo)． 1．對于頂點(diǎn)表中的每一個頂點(diǎn)，如果沒有出現(xiàn)在數(shù)據(jù)結(jié)構(gòu)中，則可增加該頂點(diǎn)記錄． 2．對于每一對相鄰的頂點(diǎn)(包括起點(diǎn)和終點(diǎn))，如果其對應(yīng)的邊沒有出現(xiàn)在此數(shù)據(jù)結(jié)構(gòu)中，則可增加該邊記錄． 3．對于多邊形的每一個邊記錄，增加翼邊，以便順時針或逆時針掃描該多邊形面． 4．產(chǎn)生一個多邊形面記錄，并增加指針指向其中一個邊緣． 　　 算法13．2　沿著多邊形面順時針跟蹤邊緣 輸入是一個指向面記錄的指針和一個調(diào)用待訪問邊的進(jìn)程． 1．從面記錄中取

12、出第一條邊，使之成為當(dāng)前邊． 2．處理當(dāng)前邊，即對被訪問的每一條邊完成所有的操作，如，沿著多邊形面順時針方向編輯頂點(diǎn)表，沿掃描方向記錄邊緣端點(diǎn)（頂點(diǎn)）． 3．如果正在掃描當(dāng)前邊的西側(cè)面，則下一條邊將是西南翼． 4．如果正在掃描當(dāng)前邊的東側(cè)面，則下一條邊將是東南翼． 5．如果當(dāng)前邊是第一條邊，則掃描結(jié)束． 6．否則，回到第2步． 13．2．2 曲面片 曲面上的各部分可以用一個雙多項(xiàng)式表示．例如，平面可以表示為： (13．7) 曲面片可以用更高階的多項(xiàng)式來表示． 雙線性曲面片（線性是指任何平行于坐標(biāo)軸的截面的

13、截線是一直線）： (13．8) 雙二次曲面片： (13．9) 雙三次曲面片： (13．10) 雙四次曲面片 (13．11) 在機(jī)器視覺中，上述雙多項(xiàng)式經(jīng)常被用來表示曲面片． 多項(xiàng)式曲面片非常適合于局部表面的表示，例如一個點(diǎn)的鄰域，但整個表面的表示不是很方便，而且不能表示非圖形曲面．更復(fù)雜的曲面可以用三次樣條函數(shù)來表示，這將在下一節(jié)討論． 13．2．3張量積

14、曲面 　　13．1．1節(jié)介紹了如何用參數(shù)形式將一個復(fù)雜曲線表示成一個三次多項(xiàng)式，此方法可以推廣到復(fù)雜曲面的參數(shù)表示． 一個三次多項(xiàng)式參數(shù)方程的矩陣形式為： (13．12) 其中，每一個系數(shù)都是一個三元矢量． 張量積曲面是由兩條曲線合成的，其參數(shù)形式如下： (13．13) 其中，是三元行矢量，是三元列矢量，，的積是每一個坐標(biāo)系數(shù)的雙積．此系數(shù)曲面可以寫為： (13．14) 其中，

15、是矩陣，其元素是參數(shù)曲面的每一個坐標(biāo)系數(shù)的矢量．在這種表示中，我們可以看到張量積曲面確實(shí)是兩曲線的積：一條曲線以為坐標(biāo)，另一條以為坐標(biāo)．任何平行于坐標(biāo)軸的平面和張量積三次多項(xiàng)式曲面的交線都是三次多項(xiàng)式曲線．換句話說，如果其中一坐標(biāo)是常數(shù)，那么結(jié)果就是一條以其它兩個坐標(biāo)為參數(shù)的三次多項(xiàng)式曲線． 13．2．4 超二次曲面 超二次曲面（superquadrics）由二次方程添加參數(shù)生成，這樣可以通過調(diào)整參數(shù)很方便地改變物體的形狀。增加的參數(shù)數(shù)目等同于物體的維數(shù)，比如，曲線是一個參數(shù)，曲面是兩個參數(shù)。 （1）超橢圓 在超橢圓相應(yīng)的方程中，允許和項(xiàng)的指數(shù)是變量，這樣可以得到橢圓的笛卡兒表示式。笛

16、卡兒超橢圓方程的表示形式之一是： (12.15) 其中參數(shù)是任何實(shí)數(shù)。當(dāng)時，可以得到一般橢圓表示式。 相對于方程(12.15)，超橢圓參數(shù)參數(shù)方程可以表示成： (12.16) 圖13.3表示了運(yùn)用不同的參數(shù)值產(chǎn)生的超橢圓面形狀。 圖13.3 不同參數(shù)值對應(yīng)的超橢圓圖形 （2）超橢圓球 超橢圓球面的笛卡兒表達(dá)式是由橢圓球面方程增加二個指數(shù)參數(shù)而得： (12.17) 當(dāng)時，得到一般的橢球面。 對超橢球面的方程（12.17），我們可以得到

17、相應(yīng)的參數(shù)表示式： （12.18） 圖13.4表示了由不同參數(shù)和值生成的超圓球形狀。這些及其它超二次曲面形狀的 可以生成很復(fù)雜的形狀，如家具、閃電和其它金屬構(gòu)成。 圖 13.4 不同參數(shù)和值生成的超圓球形狀 13．3　曲面插值 本節(jié)將討論如何將上述曲面表示用于實(shí)際采樣值的曲面插值計(jì)算，比如，用均勻分布網(wǎng)面表示雙目立體測距或主動三角測距系統(tǒng)獲得的深度圖。但是，如果原始深度圖不是均勻分布的，則無法用均勻分布的網(wǎng)面表示，此時就需要曲面插值．一般來說，在對原始圖像進(jìn)行處理（如邊界檢測和分割）之前，首先需要將深度圖通過插值運(yùn)算將其表示成

18、一個均勻變化的網(wǎng)面模式． 13．3．1三角形面插值 假定通過雙目立體視覺系統(tǒng)或主動三角測量系統(tǒng)得到一個曲面在離散點(diǎn)()處的采樣值，，下面討論如何在圖像陣列點(diǎn)上通過三角面進(jìn)行深度值插值計(jì)算．我們知道，不共線的空間三點(diǎn)可以構(gòu)成一個平面，平面方程為： (13．19) 所以，已知非共線的空間三點(diǎn)，則可以確定上述方程的三個系數(shù)． 我們知道，在的圖像陣列上，每一點(diǎn)的坐標(biāo)()由下式計(jì)算： 對于圖像陣列的每一點(diǎn)()，在深度圖中找出在平面上包含該點(diǎn)的三個非共面的點(diǎn)，根據(jù)(13.19) 求出三角面方程，然后計(jì)算該點(diǎn)的

19、深度值： (13．20) 13．3．2二元線性插值 二元線性函數(shù)可以表示為： (13．21) 如果把上式的一個變量設(shè)定為常數(shù)，則函數(shù)對于另一個變量就是線性變化的．換句話說，任何一個平行于坐標(biāo)軸的平面和此二元線性表面片的交線都是一個直線段．對于四條邊皆平行于坐標(biāo)軸的任何矩形平面，有唯一的用于矩形頂點(diǎn)插值的二元線性多項(xiàng)式． 假定我們要在一個矩形網(wǎng)格的四個頂點(diǎn)中間的一點(diǎn)進(jìn)行插值，并設(shè)點(diǎn)由四條邊都平行于坐標(biāo)軸的矩形包圍．此矩形的頂點(diǎn)坐標(biāo)是，， ，，其函數(shù)值為，見

20、圖13．5． 二元線性插值的系數(shù)是由矩形的4個頂點(diǎn)確定的，把每一個頂點(diǎn)的坐標(biāo)代入方程13．20，則系數(shù)滿足如下方程： (13．22) 聯(lián)立上述四個方程，得到系數(shù)求解出： (13．23) 當(dāng)矩形網(wǎng)格是一個行距和列距都是單位值的方格時，二元線性插值有一個非常簡單的表示．設(shè)要插值的點(diǎn)(x，y)離方格的左上頂點(diǎn)的偏移量為，則雙線性插值公式為： (13．24) 此公式可用于插入像元之間的圖像點(diǎn)的像素值． 圖 13．5 二元線性插值示意圖 13．3．3 魯棒插值

21、 在7．4．3節(jié)中，我們介紹了用直線擬合含有局外點(diǎn)的邊緣集的最小中值二乘法(least-median-squares, LMS)．最小中值二乘法也可用于曲面片擬合具有局外點(diǎn)的深度測量值集合． 最小中值二乘法是一種魯棒回歸算法，其潰點(diǎn)值為50％，正好對應(yīng)于待擬合點(diǎn)集的中值的地方．局部最小中值二乘估計(jì)器使用最小中值二乘法求出擬合一個局部區(qū)域來的模型參數(shù)，即通過極小化殘差平方求解模型參數(shù)： (13．25) 是估計(jì)的參數(shù)矢量，是在測量點(diǎn)處圖形曲面實(shí)際值的估計(jì)． 最小中值二乘法可以用于含有局外點(diǎn)的曲面采樣擬合模型的參數(shù)求解．例如，雙目立體視覺

22、的錯誤匹配，會造成錯誤的深度測量值，即局外點(diǎn)，測距雷達(dá)也可能在曲面不連續(xù)點(diǎn)處產(chǎn)生局外點(diǎn)．如果在用曲面片擬合深度測量值時使用最小中值二乘法，則這種曲面擬合對局外點(diǎn)不是十分敏感．特別需要指出，最小中值二乘法對曲面片擬合含有局外點(diǎn)的稀疏深度測量值是非常有用的． 將最小中值二乘法簡明地表示出來不是一件易事，但對此算法的實(shí)現(xiàn)卻很容易解釋．假設(shè)在每一個網(wǎng)格點(diǎn)附近的局部區(qū)域使用曲面片來擬合深度測量值．本算法可以很容易地推廣到使用更高階的曲片塊擬合．對于每一個網(wǎng)格點(diǎn)，選擇離此點(diǎn)最近的個深度測量值，從個測量值中任取數(shù)據(jù)作為一個待擬合子集，則所有可能的數(shù)據(jù)子集為個。用曲面片擬合第個數(shù)據(jù)點(diǎn)子集，表示相關(guān)參數(shù)矢量，

23、計(jì)算殘差平方中值： (13．26) 用曲面片擬合所有的子集后，取最小的殘差平方中值對應(yīng)的參數(shù)矢量． 本方法計(jì)算成本較高，因?yàn)閷γ恳痪植繀^(qū)域擬合都要進(jìn)行次．然而每一個曲面擬合是獨(dú)立的，程序可以實(shí)現(xiàn)高度并行計(jì)算．在實(shí)際中，可以嘗試幾種可能的組合，使得無局外點(diǎn)子集的概率接近于1，這樣可以大大地減少許多不必要的擬合． 13．4 曲面逼近 由于深度測量值存在誤差，因此找一個曲面來逼近深度數(shù)據(jù)比曲面插值更重要．如果深度測量值是一個連續(xù)曲面上的采樣點(diǎn)，那么完全可以由這些采樣點(diǎn)重建這個曲面．設(shè)重建曲面的模型為：

24、 (13．27) 該模型共包含個參數(shù)．該曲面重建問題實(shí)際上成為確定最適合數(shù)據(jù)的曲面模型參數(shù)的回歸問題，回歸函數(shù)為： (13．28) 如果我們沒有曲面的參數(shù)模型，則只能使用一個普通(或非參數(shù)化〕曲面模型來擬合此數(shù)據(jù)，即求解這些數(shù)據(jù)的一個最佳擬合曲面： (13．29) 這是一個不適定(ill-posed)問題，因?yàn)樵S多函數(shù)多可以對該數(shù)據(jù)集實(shí)現(xiàn)最佳擬合（實(shí)際上，這樣的函數(shù)有無窮多個）．不適定這一術(shù)語的意思是問題的求解不唯一，反過來，適定問題(well-posed)會有唯一的最優(yōu)解．為了能使方程13．29

25、變?yōu)檫m定，可以增加一個逼近約束函數(shù)，使得所選擇的曲面擬合函數(shù)有唯一解．選擇約束函數(shù)的標(biāo)準(zhǔn)有許多，一種比較常用的標(biāo)準(zhǔn)是選擇既能擬合數(shù)據(jù)又是光滑表面的函數(shù)． 已知數(shù)據(jù)點(diǎn)集{()}，，則使下式達(dá)到極小化的是該數(shù)據(jù)點(diǎn)集的最佳擬合， (13．30) 其中。該方程與13．29式不同之處是增加了一項(xiàng)加權(quán)光滑約束項(xiàng)．光滑約束項(xiàng)叫做正則項(xiàng)或穩(wěn)定函數(shù)．權(quán)重系數(shù)稱為正則化參數(shù)，較小時，可以使得逼近函數(shù)十分靠近數(shù)據(jù)點(diǎn)集，而較大時，則強(qiáng)迫逼近函數(shù)更平滑．上面方程的第一個項(xiàng)稱為問題約束，在該約束上通過增加穩(wěn)定函數(shù)將不適定問題變?yōu)檫m定問題的過程叫正則化（regularization）． 適

26、定這一的概念遠(yuǎn)比求唯一解嚴(yán)格的多，比如，方程13．29的擬合問題可能有唯一解，但是解空間中還有其它許多完全不同的解可能也是好的解，而一個適定問題只有一個解空間，該解對應(yīng)的范數(shù)的最小值不僅是唯一的，而且肯定比其它解更好． 13．4．1回歸樣條 回歸樣條法是另一種曲面擬合方法。用曲面模型（如張量積樣條函數(shù)）代替方程13．29的擬合函數(shù)，該方程就變?yōu)橐粋€回歸問題，求解這一問題，就得到了該曲面模型的參數(shù)．當(dāng)然，如果知道曲面模型，那么就可以直接列出回歸問題的方程，而不必經(jīng)過方程13．29。 許多曲面函數(shù)，包括張量積樣條函數(shù)，可以表示為基本函數(shù)的線性組合：

27、 (13．31) 為函數(shù)系數(shù)，為基本函數(shù)．使用張量積樣條可以將基本函數(shù)組合成為一個網(wǎng)格： (13．32) 將方程13.31或13.32的曲面模型代入方程13．28，得到一組求解回歸參數(shù)的線性方程組．因?yàn)榉匠探M是稀疏的，因此，用稀疏矩陣方法求解比用奇異值求解要好． 下面將從一維情況開始，詳細(xì)介紹回歸樣條計(jì)算方法．一維樣條函數(shù)是基本函數(shù)的線性組合： (13．33) 假設(shè)樣條基本函數(shù)均勻分布整數(shù)位置，樣條基本函數(shù)在區(qū)間是非零的，基本函數(shù)位于從0到，所以決定樣條基本曲

28、線的形狀的有個系數(shù)(見圖13．6)。 有一個樣條曲線是定義在區(qū)間從 x=3 到x=m+1， 在x=0點(diǎn)的基本函數(shù)跨越3個區(qū)間到此曲線的左端，在x=m+1點(diǎn)的基本函數(shù)跨越3個區(qū)間到達(dá)此曲線的右端．曲線端點(diǎn)以外的額外區(qū)間建立了曲線端點(diǎn)的邊界條件，而且必須要包括進(jìn)來，那樣才能正確地定義第一個曲線段[0，1) 和最后一個曲線段[m，m+1)． 圖13.6位于整數(shù)位置的基函數(shù)線性組合構(gòu)成一維樣條曲線示意圖 每一個樣條函數(shù)在4個整數(shù)區(qū)間上都是非零的，因?yàn)榛竞瘮?shù)重疊，每一區(qū)間都被4個基本函數(shù)覆蓋．基本函數(shù)的每一段是僅定義它的單位區(qū)間上的三次多項(xiàng)式，如圖13．7所示，樣條函數(shù)的每一

29、段的三次多項(xiàng)式如下： (13．34) 如果簡單地把這些三次多項(xiàng)式相加以得到樣條基本函數(shù)是不正確的，因?yàn)槊恳欢味枷拗朴谒膮^(qū)間，這就是，每一段在它適用的區(qū)間之外必須被視為非零的．為了在特殊點(diǎn)x估計(jì)特殊樣條基本函數(shù)，有必要確定x位于哪一段和估計(jì)相對應(yīng)的三次多項(xiàng)式． 圖13.7 四個三次多項(xiàng)式構(gòu)成的樣條基函數(shù) 假設(shè)x位于區(qū)間，樣條曲線是每m+1個樣條基本函數(shù)的線性組合如式13．33．因?yàn)槊恳粋€樣條基本函數(shù)占四個區(qū)間(單位)，上是，左邊順次是，，，所以為了估計(jì)當(dāng)x在區(qū)間上的樣條曲線，只需估計(jì)此區(qū)間上的四個樣條基本函數(shù)的線性組合：

30、 (13．35) 因?yàn)槊恳粋€樣條基本函數(shù)包含4個三次多項(xiàng)式，其中每一段都定義在其各自的區(qū)間上，只需估計(jì)在三次樣條曲線被估計(jì)的區(qū)間上的三次多項(xiàng)式段即可．在區(qū)間上的x點(diǎn)樣條曲線的值為： (13．36) 為了在任何位置估計(jì)樣條曲線，有必要確定x所在的區(qū)間，并代入方程13．36，下標(biāo)表示區(qū)間的起點(diǎn)，那么4個樣條基本函數(shù)的系數(shù)才是正確的． 方程13．36中的估計(jì)樣條曲線的公式可以用于線性回歸，因?yàn)槟Ｐ驮谙禂?shù)上是線性的．方程包含術(shù)語x的冪，這并沒有什么影響．此模型可以用于下面的回歸算法，此算法用于從一系列數(shù)據(jù)

31、點(diǎn)()中確定樣條的系數(shù)．每一數(shù)據(jù)點(diǎn)可得到一個約束4個樣條系數(shù)的方程： (13．37) 這些方程組成一個線性方程組： (13．38) 其中，a是B樣條系數(shù)的列矢量，方程右側(cè)的列矢量是的矢量，除了在相對應(yīng)在包含x的區(qū)間上的B樣條基本函數(shù)的系數(shù)的4個元素外，矩陣的其它元素都為0．此線性方程組可用單值求解法來求．但因?yàn)榇朔匠探M是稀疏的，最好用稀疏矩陣方法． 對于三維曲面擬合，模型是一張量積樣條曲面： (

32、13．39) 曲面擬合問題可以通過使下式最小化來求解． (13．40) 數(shù)據(jù)值之涉及一個下標(biāo)，因?yàn)榇藬?shù)據(jù)只在此平面的離散點(diǎn)上，每一個數(shù)據(jù)值位于x-y平面的點(diǎn)()． 確定張量積樣條曲面系數(shù)的回歸問題的公式化是和以前介紹的一維情況有點(diǎn)相似．每一個基本函數(shù)占16個網(wǎng)面矩形．因?yàn)榛竞瘮?shù)重疊，所以每一個網(wǎng)面矩形上有16個基本函數(shù)．每一個基本函數(shù)包括16個二元三次多項(xiàng)式塊．每一塊定義在一個網(wǎng)面矩形上，在此網(wǎng)面矩形外是非零的． 假設(shè)此網(wǎng)面是均勻的，所以所有網(wǎng)面矩形都是大小相同的方格．此樣條基本函數(shù)中的二元三次多項(xiàng)式塊的公式對每一方格都是相同的．每一張量積基本函數(shù)可分

33、寫成一維基本函數(shù)的積： (13．41) 每一個一維基本函數(shù)包括4個三次多項(xiàng)式，定義在小網(wǎng)面矩形上的16個多項(xiàng)式塊中的每一個都是兩個三次多項(xiàng)式的積，其中一個以x為變量，另一個以y為變量，以x為變量的4個三次多項(xiàng)式見式13．34，同樣有以y為變量的4個三次多項(xiàng)式為： (13．42) 樣條基本函數(shù)的16個多項(xiàng)式塊是由前面給的多項(xiàng)式兩兩相乘得到的，在網(wǎng)面的點(diǎn)，估計(jì)樣條前面的公式如下： (13．43) 用此公式代替一維三次多項(xiàng)式就得到

34、估計(jì)樣條曲面的公式，16個系數(shù)的每一項(xiàng)為： 這些表示是在點(diǎn)處估計(jì)的，乘以對應(yīng)的系數(shù)，求和得到在(x，y)處的樣條曲面． 估計(jì)樣條曲面的公式也就是用于確定樣條曲面的回歸問題的模型．在樣條曲面中有(n+1)(m+1)個系數(shù)．每一數(shù)據(jù)點(diǎn)()得到一個包括16個系數(shù)的方程．如同在一維情況下，回歸問題可得到一個線性方程組： (13．44) 其

35、中a是樣條系數(shù)的矢量，右側(cè)的列矢量b是數(shù)據(jù)值，，N 的矢量．除了對應(yīng)在包含()的方格上的基本函數(shù)的16個元素矩陣M的每一行為0． 此方法可通過擬合樣條曲面到均勻像元和采樣樣條曲面來使圖像平滑．對樣條網(wǎng)面來說沒有必要和圖像網(wǎng)面相對應(yīng)；實(shí)際上，如果樣條網(wǎng)面有更大的空間，也就更光滑．樣條基本函數(shù)象高斯光滑濾波器(第四章介紹過)，而且，樣條基本函數(shù)的寬度是由樣條網(wǎng)面的空間決定的．當(dāng)使用以前介紹的用于樣條網(wǎng)面回歸問題的公式時，在圖像上像元值為的位置()被映射到樣條曲面的網(wǎng)面坐標(biāo)系中．樣條曲面可按需采樣，在原始圖像的網(wǎng)面點(diǎn)坐標(biāo)處，為了計(jì)算光滑圖像的像元． 樣條曲面方程的優(yōu)化表明樣條只是

36、一系列13．5．2節(jié)中介紹的二元三次曲面塊．二元三次曲面塊和樣條曲面之間的區(qū)別只是樣條曲面的二元三次塊在塊所在區(qū)域是二階連續(xù)的，而任意二元三次塊根本不需要連續(xù)．張量積樣條曲面是光滑的，而且還是二階連續(xù)的，可以用于如身體器官、車體、飛機(jī)機(jī)身的建模． 　　在許多實(shí)際應(yīng)用中，張量積樣條曲面必須是參數(shù)形式，如13．4．3節(jié)介紹過的一樣，在回歸問題中反應(yīng)曲面的系數(shù)是三元矢量，每一個元素對應(yīng)，，中的一個坐標(biāo)．，空間是平面直角坐標(biāo)系，被分為均勻的網(wǎng)面．最困難的是構(gòu)造把點(diǎn)映射到，空間的公式，那樣此測量點(diǎn)就能正確地和組成樣條曲面的二元三次曲面塊聯(lián)系起來． 13．4．2加權(quán)樣條逼近 　　目前介紹的曲面逼近方

37、法的問題是：甚至在曲面邊界的數(shù)據(jù)不連續(xù)，解還是光滑曲面．在13．6．1節(jié)介紹的回歸樣條的光滑的無參數(shù)函數(shù)是隱含的．如果擬合曲面可以公式化為一系列分段光滑函數(shù)，深度測量值為： (13．45) 以分成數(shù)個區(qū)域，每個區(qū)域?qū)?yīng)一個分段光滑函數(shù)，那樣解能更準(zhǔn)確地反應(yīng)此處曲面的形狀．然而這會得到一些用于計(jì)算某些曲面的算法，這些超出了本書的范圍．13．7節(jié)中將討論曲面分割的問題．我們可以避開曲面表示中的一些比較難的課題，而且通過改變方程13．5．2的光滑性函數(shù)以降低深度數(shù)據(jù)不連續(xù)處的光滑性，仍然獲得了符合不連續(xù)性的非常好的曲面擬合．此方法就是加權(quán)正則化方

38、法． 一維的加權(quán)正則化式子為： (13．46) 如果權(quán)函數(shù)在數(shù)據(jù)不連續(xù)點(diǎn)取值非常小，在其它地方大，那么權(quán)函數(shù)就消去了不連續(xù)點(diǎn)的連續(xù)標(biāo)準(zhǔn)． 在二維情況下，加權(quán)樣條曲面擬合的公式如下： (13．47) 權(quán)函數(shù)為： (13．48) 其中是采樣曲面的梯度．應(yīng)指出的是來自方程13．29的正則化參數(shù)a已溶入權(quán)函數(shù)． 可以用變分法把方程13．47變?yōu)槠⒎址匠?，或者用回歸樣條方法取代具有線性回歸問題的方程13．47．假定在張量積基本函數(shù)定義

39、的網(wǎng)面的區(qū)域上的權(quán)是常數(shù)，就可以從梯度擬合中計(jì)算出方程13．47中的權(quán)函數(shù)． 13．5曲面分割 一幅距離圖像可以看作是如下分段光滑曲面均勻采樣的網(wǎng)格： (13．49) 本節(jié)將討論如何將定義在均勻網(wǎng)格上的一組距離采樣值分割成具有相似曲率的區(qū)域，并用低階的雙變量多項(xiàng)式來逼近每一個區(qū)域．表面曲率特性可用來選取核區(qū)域，然后增長核區(qū)域以覆蓋鄰近距離采樣值，核區(qū)域的增長準(zhǔn)則是鄰近距離采樣值與逼近核區(qū)域的雙變量多項(xiàng)式之間的偏差小于某一預(yù)先給定的閾值。 曲面分割問題通常表述如下，將分段光滑的曲面分割成光滑曲面基元

40、 (13．50) 其中為特征函數(shù)，表示將曲面劃分成表面片的一種分割， 表示第個區(qū)域，它對應(yīng)一個曲面基元，每一個區(qū)域可以用如下多項(xiàng)式逼近： (12．51) 此模型包括平面、雙線性、雙三次、雙四次多項(xiàng)式曲面片． 特征函數(shù)可以通過每一區(qū)域像素位置的列表來實(shí)現(xiàn)，也可以使用其它表示如模板、四叉樹等來實(shí)現(xiàn)． 13．5．1初始分割 通過計(jì)算曲面的平均曲率H和高斯曲率K，并使用H和K的正負(fù)號，可以估計(jì)用于分割的初始核區(qū)域，以形成初始區(qū)域分割。對應(yīng)于平均曲率和高斯曲率正負(fù)號的曲面有8種類型，表13

41、．1所示，這些曲面類型可以用于構(gòu)造核區(qū)域． + 0 － － 峰 脊 鞍脊 0 平面 最小曲面 + 谷 谷 鞍谷 假設(shè)距離函數(shù)分布在均勻網(wǎng)格上，因此可以按照一般圖象進(jìn)行處理。用可分離濾波器與距離圖象進(jìn)行卷積來估計(jì)距離圖象的一階和二階導(dǎo)數(shù)．使用距離圖像的一階和二階導(dǎo)數(shù)計(jì)算平均曲率和高斯曲率 (13．52) （13．53) 使用下面公式計(jì)算整數(shù)標(biāo)記以實(shí)現(xiàn)平均曲率和高斯曲率正負(fù)號編碼． (13．54) 然后使用序貫連通成份算法（見第三章），將具

42、有相同符號標(biāo)記組成一個連通區(qū)域，并使用收縮或腐蝕算法把每一個連通區(qū)域減少到可作為核區(qū)域的最大尺寸區(qū)域，使用濾波器將那些無法對應(yīng)場景曲面片的太小的區(qū)域?yàn)V掉。最后剩下的區(qū)域構(gòu)成區(qū)域增長的種子． 13．5．2 曲面片增長 距離圖象中的每一個核區(qū)域可以用雙變量多項(xiàng)式有效地?cái)M合。擬合多項(xiàng)式一般從一階（平面）開始，然后逐漸增加多項(xiàng)式（曲面）的階數(shù)，直到曲面能夠很好地?cái)M合核區(qū)域?yàn)橹?。如果多?xiàng)式階數(shù)已經(jīng)很高，但仍然無法得到滿意的擬合結(jié)果，則該區(qū)域不能作為核區(qū)域。接下來的工作是核區(qū)域擴(kuò)展，以便覆蓋核區(qū)域更多相似的鄰近點(diǎn)，即把那些沒有標(biāo)記的距離像素通過增長過程添加到相應(yīng)的核區(qū)域中去。決定鄰近點(diǎn)是否

43、添加到核區(qū)域中的相似性準(zhǔn)則是鄰近點(diǎn)與雙變量多項(xiàng)式之間的偏差均方根，也稱為擬合殘差。如果該殘差小于預(yù)定的閾值，則該鄰近點(diǎn)為區(qū)域侯選點(diǎn)。在找到所有的侯選點(diǎn)以后，再使用雙變量多項(xiàng)式對核區(qū)域和侯選點(diǎn)一起重新進(jìn)行擬合，如果需要的話，可以考慮增加雙變量多項(xiàng)式的階數(shù)，使得所有點(diǎn)都滿足相似性準(zhǔn)則。如果擬合殘差小于預(yù)定的閾值，則所有侯選點(diǎn)與核區(qū)域共同組成一個大區(qū)域；否則，放棄所有的侯選點(diǎn)。當(dāng)沒有區(qū)域能夠再擴(kuò)大時，區(qū)域增長過程終止。用于曲面分割的區(qū)域增長算法見算法13．3． 算法13．3 曲面分割算法 1． 使用可分離濾波器，計(jì)算距離圖象的一階和二階偏導(dǎo)數(shù)， 2． 計(jì)算圖象每一個像素位置的平均曲率

44、和高斯曲率， 3． 對每一像素標(biāo)記曲面類型， 4． 收縮區(qū)域以消除靠近區(qū)域邊界的錯誤標(biāo)記， 5． 使用序貫連通成份算法識別核區(qū)域， 6． 去掉太小的核區(qū)域， 7． 用雙變量多項(xiàng)式擬合每一個核區(qū)域， 8． 從某一核區(qū)域開始，將滿足相似性準(zhǔn)則的核區(qū)域鄰近點(diǎn)標(biāo)記為該區(qū)域侯選點(diǎn)， 9． 重新用雙變量多項(xiàng)式同時擬合核區(qū)域和區(qū)域侯選點(diǎn)，如果擬合結(jié)果滿足相似性準(zhǔn)則，則核區(qū)域和侯選點(diǎn)共同構(gòu)成新區(qū)域，否則，放棄區(qū)域侯選點(diǎn)， 10．選擇未進(jìn)行過增長的核區(qū)域，重復(fù)步驟8和9，直到?jīng)]有核區(qū)域能夠再增長。 13．6　曲面配準(zhǔn) 通過解絕對方位問題(12．2節(jié))，可以確定共軛對集合中的對應(yīng)點(diǎn)之間

45、的變換，也有不需要對應(yīng)點(diǎn)就能實(shí)現(xiàn)兩個表面對準(zhǔn)，例如，無需事先知道采樣點(diǎn)與物體表面點(diǎn)對應(yīng)關(guān)系，就能將一組距離采樣值與物體模型對準(zhǔn)。本節(jié)將介紹迭代最近點(diǎn)算法（iterative closest point, ICP），此算法不用點(diǎn)對應(yīng)關(guān)系，卻可以確定一個物體的兩種視圖之間的剛體轉(zhuǎn)換． 迭代最近點(diǎn)算法可以應(yīng)用在許多物體模型上，包括：點(diǎn)集，二維或三維的以及各種不同的曲面表示．曲線可以表示為：多直線段線、隱式曲線或參數(shù)曲線．曲面可以表示為：多邊形曲面片、隱式或參數(shù)曲面、或張量積樣條．一個物體的兩個視圖沒有必要具有同樣的表示．例如，一個視圖可以是由主動三角測距獲取的一系列空間曲線，而另一個視圖可

46、能是張量積三次樣條曲面．關(guān)鍵的問題是視圖的采樣點(diǎn)可以映射到另一個視圖上最近的點(diǎn)，以逼近共軛對點(diǎn)集．通過對應(yīng)關(guān)系求解絕對方位問題將會改善視圖之間的對準(zhǔn)性．找到最近點(diǎn)的對應(yīng)，并用這些近似的共軛對集求解絕對方位問題的過程可以一直重復(fù)進(jìn)行，直到兩個視圖完全對準(zhǔn)． 下面討論迭代最近點(diǎn)算法用于點(diǎn)集與曲面模型配準(zhǔn)的方法。給定一個物體曲面的點(diǎn)集和此物體的一個模型，確定模型上的點(diǎn)集，使其與采樣點(diǎn)集是最近的。采樣點(diǎn)和模型的距離是： (13．56) 計(jì)算離采樣點(diǎn)集中的每一點(diǎn)最近的點(diǎn)集，．把每一采樣點(diǎn)和模型中最近的點(diǎn)配對以組成一共軛對集{()，(

47、)，．．．，()}．用這一系列共軛對求解絕對方位問題．既使這些點(diǎn)列不是真正的共軛對，也可以獲得視圖之間轉(zhuǎn)換的逼近解法．把這種轉(zhuǎn)換用于點(diǎn)列，而且重新計(jì)算一系列最近點(diǎn)．目前，點(diǎn)列離模型比較近，和的點(diǎn)對更接近真正的共軛對，可以再解一次絕對方位問題，再轉(zhuǎn)換一次點(diǎn)列．本程序可以重復(fù)直到最近點(diǎn)之間平方距離的數(shù)目低于某一個閾值． 在早期的迭代中，最近的點(diǎn)對可能和真正的共軛對相去甚遠(yuǎn)，但是通過應(yīng)用這些相似共軛對來解絕對方位問題，實(shí)現(xiàn)剛體轉(zhuǎn)換，使此點(diǎn)列更接近模型．隨著迭代的繼續(xù)，最近點(diǎn)對變得越來越象有效共軛對了．例如，如果點(diǎn)對起初離模型較遠(yuǎn)，那么所有點(diǎn)可以映射到模型的同一點(diǎn)．很顯然，這樣多對一的映射不

48、可能是有效的一列共軛對，但是第一次迭代使此點(diǎn)列置于此模型上，那樣這些點(diǎn)就位于匹配模型點(diǎn)的中心，而且接下來的迭代把點(diǎn)列的中心和模型的中心對準(zhǔn)．最終的迭代使點(diǎn)列旋轉(zhuǎn)，調(diào)整位置以對準(zhǔn)點(diǎn)列和模型．迭代最近點(diǎn)重合的過程見算法13．4． 算法13．4迭代最近點(diǎn)重合 把一系列點(diǎn)和以多項(xiàng)式塊為模型的曲面重合起來． 1．計(jì)算最近點(diǎn)列， 2．計(jì)算點(diǎn)列之間的重合， 3．應(yīng)用轉(zhuǎn)換來重合點(diǎn)列， 4．返回第一步直到重合誤差低于某一閾值． 圖13.8求網(wǎng)面套準(zhǔn)尋找對應(yīng)點(diǎn) 圖13.9使用最近迭代算法進(jìn)行深度圖像序列配準(zhǔn)示意圖 思考題 13．1 怎樣確定空間4個點(diǎn)是否共面？ 13．2 給出曲面

49、基本曲率、高斯曲率和平均曲率的定義．已知曲面上一點(diǎn)的這些曲率，你能得到此曲面的什么信息？從這些曲率中你能得到曲面的什么局部信息和全局信息？ 13．3 什么是樣條曲線？為什么三次樣條經(jīng)常用于表示曲線？ 13．4 為什么用多邊形片表示任意曲面？用多邊形片能夠多大程度地接近任意曲面？ 13．5 什么是翼邊緣數(shù)據(jù)結(jié)構(gòu)？使用翼邊緣數(shù)據(jù)結(jié)構(gòu)的最大特點(diǎn)是什么？ 13．6 曲面擬合和曲面插值有何區(qū)別？ 13．7 什么是正則化？試舉例說明使用正則化能有效地解決問題． 13．8 如何用B樣條函數(shù)平滑圖像？試舉例說明？ 13．9 使用微分幾何特性將曲面的局部形狀分為8種曲面類型之一．請解釋這些微分幾何特性，并說明劃分曲面的標(biāo)準(zhǔn)是什么？ 計(jì)算機(jī)練習(xí)題 13．1 寫一個程序用于分割圖像（包括舉例圖像），分割可以從基于微分幾何學(xué)特征的局部核區(qū)域開始．用區(qū)域生長方法擬合一個圖像中的雙二次和雙三次曲面．選擇合適的區(qū)域增長和區(qū)域增長終止準(zhǔn)則．將你的程序用于幾幅測試圖像，研究擬合曲面的誤差． 13．2 編制一個程序，可以生成超橢圓和超橢球（如圖13.2和13.3 所示）。 專心---專注---專業(yè)