韓曉軍，武嘉慶，王志寬

（天津工業(yè)大學 電子與信息工程學院，天津 300387）

關(guān)于三維服裝的CAD設(shè)計有許多重大進展，但是CAD中虛擬試穿部分仍然存在問題，仿真的穩(wěn)定性和速度都沒有達到要求，性能與高效無法達到平衡.基于圖像空間的碰撞檢測算法[1]包括兩類經(jīng)典的算法：層級包圍盒法與空間剖分法.空間剖分法[2]對同處于一個分割區(qū)域的對象進行檢測.由于虛擬環(huán)境中物體數(shù)量增大，此類碰撞檢測算法檢測效率不高.層次包圍盒算法[3]是用體積略大但幾何特性簡單的包圍盒來替換復(fù)雜的幾何對象，并通過構(gòu)造層次包圍盒樹逼近真實物體，碰撞檢測時通過遍歷層次包圍盒樹來粗略地確定物體的相交狀況[4].不少學者對傳統(tǒng)的包圍盒算法進行了改進，形成了雙層樹結(jié)構(gòu)和分層樹結(jié)構(gòu)[5].雙層樹結(jié)構(gòu)是在包圍盒樹的每個節(jié)點上構(gòu)造雙層結(jié)構(gòu)，容易造成數(shù)據(jù)的冗余；分層樹結(jié)構(gòu)分別采用不同的包圍盒，對不同類型包圍盒間兩兩進行相交測試，計算開銷很大，嚴重影響了碰撞檢測的實時性.

為了克服上述碰撞檢測算法效率低下的缺陷，本文提出基于純粹的幾何方法以解決模型碰撞問題，簡化了幾何位置點修正而產(chǎn)生的碰撞回響，不需要重新計算動態(tài)方程的碰撞模型也具有很好的穩(wěn)定性；并提出一種三維人體模型區(qū)域生長的優(yōu)化分割算法，使用橢圓體結(jié)構(gòu)包圍盒替換人體模型分割區(qū)域，提高了虛擬試穿過程中的碰撞檢測效率，獲得了滿意的衣物虛擬試穿效果.

1 三維人體模型分割

本文使用的人體模型數(shù)據(jù)以點云或者表面網(wǎng)格的數(shù)據(jù)形式通過專業(yè)軟件Makehuman獲取.三維人體模型如圖1所示.

圖1 三維人體模型Fig.1 3D human body model

1.1 區(qū)域生長原理

區(qū)域生長的基本思想是將具有相似性質(zhì)的像素集合起來構(gòu)成區(qū)域.首先對每個需要分割的區(qū)域找一個種子點作為生長的起點，然后將種子點周圍鄰域中具有相同或相似性質(zhì)的點合并到種子點所在的區(qū)域中，生成一個具有目標特征的區(qū)域[6].基于區(qū)域生長的方法對人體模型進行分割，將人體的骨骼信息作為分割最初的種子點.計算機動畫里的骨骼通常定義為一組分層的骨架，制作標準的骨架需要20塊骨頭和與其相當數(shù)量的關(guān)節(jié)點[7].設(shè)計方案中，選取的種子點作為每塊骨頭的中心點，每個骨骼的信息都包括與其關(guān)聯(lián)的骨骼和三維轉(zhuǎn)換所需的位置、長度和方向信息.

第1階段，種子點或者種子區(qū)域的選擇以及閾值的設(shè)定.種子點位于待分割的區(qū)域內(nèi)，由一個或者一系列體素點構(gòu)成，同時建立一個空棧，并將種子點存入其中.

第2階段，研究種子點鄰域中尚未經(jīng)過處理的體素點T，表示為

式中：N（x）表示點x的鄰域；Ai表示被選取的種子點或者種子區(qū)域.按照相似性準則判斷，將滿足條件的體素歸入棧中.相似性判據(jù)可表示為

式中：d（x，y）表示種子點x與待測體素點y之間的歐幾里得距離；α為設(shè)定的閾值.將閾值參數(shù)化表示時，可將其表示為任一體素點與種子點歐幾里得距離的值.設(shè)種子點所在骨骼為Bi，其長度為dBi，則α可表示為

第3階段，隨著迭代的進行，當模型內(nèi)所有的體素都經(jīng)過算法處理，則區(qū)域生長法結(jié)束.此時棧中所有體素構(gòu)成的區(qū)域即為分割結(jié)果.

1.2 基于Span算法的模型分割實現(xiàn)

區(qū)域生長理論包括Floodfill（泛洪法）、Scanline（掃描法）、Span（區(qū)段法）3種算法.其中，F(xiàn)loodfill算法屬于從圖像中尋找連通區(qū)域的經(jīng)典算法，其思路類似于洪水從一個區(qū)域擴散到所有都能到達的區(qū)域[8]，但它的分割效率較低.Scanline算法是Floodfill的改進算法，首先填充當前掃描線上的位于給定區(qū)域內(nèi)的一個區(qū)段，然后確定與這一區(qū)段相鄰的兩條掃描線上位于該區(qū)段內(nèi)是否存在需要填充的新區(qū)段，如果存在，則依次把它們保存起來.反復(fù)這個過程，直到所保存的各區(qū)段都填充完畢[9].

基于Span的算法本質(zhì)思想和Scanline一樣.Span即“區(qū)段”，表示圖像上縱坐標相等的一段連續(xù)像素集合[10].其不同之處在于，基于Span的算法采用顯式的區(qū)段數(shù)據(jù)結(jié)構(gòu)作為填充和出入堆棧的單元，這樣能夠加快堆棧操作的效率，所以選擇基于Span的算法來實現(xiàn)區(qū)域生長對人體模型的分割以提高時效.Span算法流程示意如圖2所示.

圖2 基于Span算法流程示意Fig.2 Span algorithm flow diagram

算法反復(fù)執(zhí)行的操作步驟如下：①彈出區(qū)段；②區(qū)段伸展；③檢查鄰接區(qū)段并建立新區(qū)段入棧.循環(huán)一直持續(xù)到堆棧為空.

棧中已檢測區(qū)段被彈出后，首先進行左右延伸到xleft和 xright；然后在延伸后形成的[xleft-xright，y]范圍的上方區(qū)間[xleft-xright，y-1]進行考察，還要對 y+1、z-1、z+1方向區(qū)間進行考察；考察的過程中發(fā)現(xiàn)了3個新區(qū)段span1、span2和span3，將符合測度條件的區(qū)段壓入堆棧.重復(fù)步驟（3），直至模型內(nèi)沒有未處理的區(qū)段.

在步驟（3）操作過程中，發(fā)現(xiàn)算法并不能避免重復(fù)檢查已經(jīng)訪問過的或者已經(jīng)被確認無所需點的區(qū)域，這樣會導(dǎo)致一些無謂的計算.所以在原有的算法基礎(chǔ)上，對每個訪問過的區(qū)段都添加標記，這樣可以有效地避開重復(fù)檢查的情況.由此，在區(qū)段算法中，步驟（3）的操作每找到一個區(qū)段，就會為每個區(qū)段新建一個span結(jié)構(gòu)，記錄下其左右邊界和Y坐標，同時對區(qū)段內(nèi)的點做已訪問標記，然后再推入堆棧.

新形成的span根據(jù)自己在區(qū)段 [xleft-xright，y-1]中的位置，賦予其4種標記：LeftRequired、Right Required、AllRez、UnRez.若產(chǎn)生新的span的左端接觸左界，但右端不接觸右界，這個span就屬于Left Required；方向反過來的為RightRequired；兩邊都不接觸左右界的為AllRez；兩邊都接觸則為UnRez.

在定義了這些標記之后，根據(jù)不同的標記可以有效避開已經(jīng)訪問過的或者已經(jīng)被確認無所需點的區(qū)域，避免了不必要的回溯，提高了算法的效率.

2 碰撞檢測與響應(yīng)

關(guān)于碰撞的檢測和響應(yīng)是非常重要的問題[11].一個粒子和一個對象之間的碰撞檢測通常就是檢測每個時間間隔中是否有碰撞發(fā)生[12].一旦檢測到碰撞，響應(yīng)的粒子的速度和加速度就會改變，以避免碰撞，這就需要重新計算動態(tài)方程[13-14].像這樣的碰撞檢測方案計算結(jié)果精確，但計算量巨大.為此，學者們提出了一些改進的方法，這些方法采用包圍體來減少邊界的交叉檢測[15-16]，首先檢測在邊界的碰撞，然后檢測粒子本身的碰撞[17].在此基礎(chǔ)上，本文提出了更簡潔有效的方法，利用橢圓體包圍盒擬合人體模型分割區(qū)域，檢測碰撞粒子是否在目標對象（橢圓體）里，如果在目標對象里面，粒子就會被移動到目標對象的表面，為了更簡單和快速，粒子會從橢圓體的內(nèi)部移動到正確的發(fā)生碰撞的橢圓體邊界位置上.

當織物與環(huán)境中剛性物體發(fā)生碰撞時，兩者之間接觸產(chǎn)生摩擦，摩擦對于質(zhì)點的運動速度起阻尼作用[18].假設(shè)質(zhì)點P以速度v與物體在點Pc發(fā)生碰撞，物體表面在點Pc的單位法向量為n，可以將v分解為垂直于表面的速度vn和平行于表面的速度vt，即vn=（v·n）n，vt=v-vn.

設(shè)織物的摩擦系數(shù)為 Cf，如果‖vt‖≥Cf‖vn‖，質(zhì)點會在物體表面上作水平摩擦運動，它的速度減小為

如果‖vt‖≥Cf‖vn‖，質(zhì)點會在水平方向上保持靜止.

摩擦系數(shù)Cf為織物的物理特性.當Cf=0時，質(zhì)點會在物體表面上做無摩擦滑動；當Cf=∞時，質(zhì)點在表面上不會滑動[19].

碰撞有兩種形式：彈性碰撞和非彈性碰撞.彈性碰撞不會發(fā)生動能損失，將使質(zhì)點以同樣大小的速度沿相反方向運動，非彈性碰撞則會有動能的損失[20].為了增強仿真織物的真實性，采用非彈性碰撞響應(yīng)，引入織物的反彈系數(shù)Cr（0≤Cr≤1），Cr的大小由織物的材料決定.不考慮摩擦因素，碰撞后質(zhì)點的運動速度為

綜上所述，質(zhì)點P在碰撞前的速度為v，碰撞后的速度調(diào)整為

假設(shè)質(zhì)點P以速度v從位置P0移動到P1，移動過程中與橢球O發(fā)生碰撞，如圖3所示.

圖3 點與橢圓體的碰撞Fig.3 Collision of point with ellipsoid

在檢測到碰撞發(fā)生時，碰撞響應(yīng)將需要強制修改質(zhì)點位置為碰撞點位置.此處碰撞點位置是質(zhì)點運動軌跡與橢球面的交點，需要求解非線性方程.為了簡易處理，碰撞響應(yīng)修改質(zhì)點位置為P1在橢球表面上徑向投影的位置，即將質(zhì)點沿著P1和P0的連線方向移動到橢球表面，表示為

式中：Pc為質(zhì)點調(diào)整后的位置.

根據(jù)方向P1P0，速度可以分解為平行于P1P0的方向vt和垂直于P1P0的方向vn，則有

將vt與vn的值分別代入式（6）可以得到碰撞后質(zhì)點的運動速度.空間點與橢球體碰撞可能會發(fā)生的3種情況如圖4所示.上述算法在只有一個橢圓體時可以實現(xiàn)預(yù)想結(jié)果.但是它不能在處理重疊層級的橢圓體時使粒子移動到正確的位置.

（1）第一種情況如圖4藍色所示，當檢測到一個橢圓體的碰撞時，粒子被移動到橢圓體表面的位置，此時粒子和另一個橢圓體發(fā)生了碰撞，它又被移動到了第二個橢圓體表面的位置.然而，第二個橢圓體的部分在第一個橢圓體里，所以粒子在移動后有可能依然在第一個橢圓體內(nèi).

（2）第二種情況如圖4綠色所示，粒子在2個或者更多橢圓體交叉的部分中.當依次對碰撞進行檢測時，不同條件下的碰撞檢測會生成不同的粒子正確的位置，這會造成系統(tǒng)的不穩(wěn)定和混亂的結(jié)果.

圖4 空間點與橢球體碰撞可能會發(fā)生的3種情況Fig.4 Three conditions may occur when space point collides with ellipsoid

（3）最后一種情況如圖4所示橙色部分，粒子被準確地移動到了橢圓體表面.

為了解決以上問題，追蹤了這些粒子位置和這些橢圓體表面的交叉部分的集合.不同于傳統(tǒng)的對每個橢圓體的碰撞檢測和響應(yīng)方法，將碰撞處理過程分為2個獨立的階段：第1階段，確定所有橢圓體上有碰撞的粒子，然后計算和記錄每個碰撞點的位置；第2階段，計算這些關(guān)聯(lián)的點與點之間的距離，得到每一個碰撞點的起始位置A0，發(fā)生碰撞的位置在離A0最短的距離處.這種方法可以有效地使粒子遠離橢圓體上的節(jié)點.碰撞檢測和響應(yīng)方法是純粹的幾何方法，比基于物理的方法更加有效率，避免了每個碰撞發(fā)生后動態(tài)方程都要重新修改和計算的問題.

3 分割算法的仿真模擬

實驗?zāi)M仿真選擇在Open GL框架下，使用Visual Studio開發(fā)平臺C#語言編程.人體模型是通過軟件Makehuman獲得的女孩模型，其中包含有15 976個頂點和不到30 000個三角形.分別對Floodfill算法、Scanline算法以及Span算法等3種實現(xiàn)區(qū)域生長分割三維人體模型的算法同時進行了測試與實驗.根據(jù)人體的骨骼框架對三維人體模型進行了分割，并使用橢圓體來近似擬合人體模型的分割區(qū)域，實驗結(jié)果如圖5所示.

采用區(qū)域生長法分割人體模型的3種算法以及添加區(qū)段標記的Span算法對同一人體模型進行分割操作實驗.通過在程序中插入計數(shù)變量記錄下容器最大的容量，可以統(tǒng)計出相應(yīng)的容器空間占有率比例，定義為容器的空間之和與圖像空間的比值，測試結(jié)果如表1所示.

圖5 三維人體模型的分割以及對分割區(qū)域的橢圓體近似擬合Fig.5 Segmentation result of 3D human model and approximate result of ellipsoid fitting in segmentation region

表1 不同算法的容器空間占有比例Tab.1 Ratio of container space in different algorithms

表1中的數(shù)值是按照計數(shù)變量所記錄的容器最大元素容量乘以單位結(jié)構(gòu)所占的字節(jié)數(shù)得到的，按照較小的空間占有計算（int16double，4字節(jié)），計算出的容器占空間大小是最小的可能情況.可以看出泛洪法的容器空間效率最差，1.98的數(shù)值說明假定輸入模型為10 MB大小，則算法除了使用1 MB大小的標記表外，還需使用1.98×10 MB的內(nèi)存用于存放算法執(zhí)行中棧的最大擴張量.再考察其他方法的內(nèi)存占用，發(fā)現(xiàn)其空間占用相比棧式泛洪法可忽略不計.

因為區(qū)域生長算法的效率很大程度上依賴于一些基本操作.為了對比這幾種程序的效率，選擇4個程序中的基本操作，包括對模型的GetPixel操作、對模型的CompPixel操作即對模型體素判定測度操作、對容器的Push和Pop操作，利用向算法運行的程序當中這些操作的位置添加計數(shù)變量，來統(tǒng)計這些操作的執(zhí)行次數(shù)，并與結(jié)果點數(shù)相比，得出的測試結(jié)果如表2所示.表2中的算法運行時間不包含加載圖像的時間，是準確的算法執(zhí)行時間.所有的算法使用相同的標記表、容器等基本結(jié)構(gòu).算法運行時間的計算是“.NET運行庫”中的System.Diagnotics.Stopwatch類完成的，算法運行經(jīng)過多次重復(fù)，多次運行的時間和表中的時間均相差不超過2 ms，4種方法的運行時間充分說明了各自的執(zhí)行效率.

由表2可以看出，掃描線算法相比于泛洪法，主要減少了對訪問和對容器的操作，但同時增加了一部分對待測點的重復(fù)訪問；原先的區(qū)段算法較掃描線法相比時間效率提高，但是仍然存在同樣的問題；而本文提出的經(jīng)過改進的區(qū)段算法，在區(qū)段算法的基礎(chǔ)上進一步減少了對訪問和對容器的操作時間，且避免了對待測模型的重復(fù)訪問.從容器效率上來看，泛洪法與其他3種方法相比效率特別低；從時間效率上來看，掃描線法在訪問與容器的操作上較泛洪法更有效，但是卻增添了重復(fù)訪問的問題，區(qū)段法在基本操作上較掃描線法時效更高，但是仍存在重復(fù)訪問的問題.由此驗證了本文提出的區(qū)段法優(yōu)化算法無論從容器效率還是時間效率方面，都是實現(xiàn)區(qū)域生長的最佳三維人體分割算法.

表2 對不同算法程序的單元訪問比例實驗數(shù)據(jù)統(tǒng)計Tab.2 Experimental data of unit access ratio of different algorithms

4 虛擬試穿

虛擬試穿實驗通過在采用Intel Core i7-4910處理器的PC機上對女性上衣、短裙以及長褲進行了模擬.圖6所示為普通半袖與長褲的人體試穿效果，有3個方向的展示，分別為正面視角效果、側(cè)面視角效果以及背面視角效果.

圖6 普通半袖與長褲的人體試穿效果Fig.6 Virtual try-on of T-shirt and trousers

圖7所示為立領(lǐng)上衣與百褶裙套裝的人體試穿效果.

圖7 立領(lǐng)上衣與百褶裙套裝的人體試穿效果Fig.7 Virtual try-on of blouse and eight-panel skirt

由圖6、圖7可以看出，衣物試穿在人體模型上，可以很好地貼合在人體模型表面，衣物的碰撞處理效果與現(xiàn)實情況相近.在實時模擬中，通過記錄的數(shù)據(jù)發(fā)現(xiàn)，碰撞處理速度與發(fā)生碰撞的質(zhì)點數(shù)相關(guān).表3總結(jié)了試穿過程中各不同衣物所需的碰撞處理用時.

表3 衣物試穿過程碰撞處理用時對比Tab.3 Comparison of collision treatment time in clothing fitting process

由表3可以看出，褲子的碰撞處理時間明顯長于T恤和百褶裙，因為褲子與身體接觸的面積更大，質(zhì)點數(shù)量更多，需要處理的沖突碰撞的次數(shù)就更多.結(jié)果表明，本文方法能夠較好地生成仿真模擬結(jié)果，效果逼真且魯棒性好.同時由表3可以看出，與傳統(tǒng)基于純粹物理模型的碰撞檢測與響應(yīng)計算方法相比，本文方法運算時間減少了64%，具有一定的實時性.

5 結(jié)束語

采用基于Span的優(yōu)化算法實現(xiàn)了由區(qū)域生長分割方法對人體模型的分割.使用橢圓體層級模擬模型，采用了基于幾何位置的碰撞檢測與響應(yīng)計算方法，在保證計算結(jié)果準確的前提下，計算速度得到了很大的提升.由實驗結(jié)果可以看出，相較于傳統(tǒng)方法，本文方法在試穿過程中碰撞檢測所用的時間非常短，具有很好的魯棒性與實效性.但是還有一些問題尚待解決和完善，例如在整個系統(tǒng)中，衣物模型模塊還需完善，目前主要模擬的是一些單薄的衣物，厚重服裝如羽絨服、棉服等還需進一步研究效果良好的仿真方法；為了增加用戶體驗和結(jié)果能更符合用戶要求，需增加用戶交互模塊等.