虛擬試穿中的模型分割與碰撞檢測

韓曉軍，武嘉慶，王志寬

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

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

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

1 三維人體模型分割

本文使用的人體模型數據以點云或者表面網格的數據形式通過專業軟件Makehuman獲取.三維人體模型如圖1所示.

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

1.1 區域生長原理

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

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

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

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

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

第3階段，隨著迭代的進行，當模型內所有的體素都經過算法處理，則區域生長法結束.此時棧中所有體素構成的區域即為分割結果.

1.2 基于Span算法的模型分割實現

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

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

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

算法反復執行的操作步驟如下：①彈出區段；②區段伸展；③檢查鄰接區段并建立新區段入棧.循環一直持續到堆棧為空.

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

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

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

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

2 碰撞檢測與響應

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

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

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

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

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

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

綜上所述，質點P在碰撞前的速度為v，碰撞后的速度調整為

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

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

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

式中：Pc為質點調整后的位置.

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

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

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

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

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

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

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

3 分割算法的仿真模擬

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

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

圖5 三維人體模型的分割以及對分割區域的橢圓體近似擬合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中的數值是按照計數變量所記錄的容器最大元素容量乘以單位結構所占的字節數得到的，按照較小的空間占有計算（int16double，4字節），計算出的容器占空間大小是最小的可能情況.可以看出泛洪法的容器空間效率最差，1.98的數值說明假定輸入模型為10 MB大小，則算法除了使用1 MB大小的標記表外，還需使用1.98×10 MB的內存用于存放算法執行中棧的最大擴張量.再考察其他方法的內存占用，發現其空間占用相比棧式泛洪法可忽略不計.

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

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

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

4 虛擬試穿

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

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

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

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

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

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

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

5 結束語

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