基于特征點的三維人臉網格簡化
2008-12-31 00:00:00黎文彥耿國華周明全
計算機應用研究 2008年7期
摘 要：在邊折疊的網格簡化算法的基礎上，針對特定三維網格模型—人臉，提出了一種實用的基于特征點的快速模型簡化算法。該算法把人臉按特征點的分布進行分塊處理，對不同區域采用不同的閾值進行調節。對于需要高細節的區域保留高度細節，而對于其他區域則進行簡化。使用這種方法可以較大地減少虛擬整型手術中的數據量，同時又能保持待手術區域的高度細節。該算法實現簡單、運算速度快，而且能有效保持人臉模型的重要特征。
關鍵詞：網格簡化；遞進網格；特征點；邊折疊
中圖分類號：TP391 文獻標志碼：A
文章編號：1001-3695(2008)07-1992-03
Threedimensional facial mesh simplification based on feature points
LI Wenyan1，GENG Guohua1，ZHOU Mingquan1，2
(1.School of Information Science Technology， Northwest University， Xi’an 710127， China;2.School of Information Sicence Technology， Beijing Normal University， Beijing 100875， China)
Abstract:This paper presented a useful quick mesh simplification algorithm based on edge collapse for the special threedimensional mesh model——human face．According to the distribution of feature points，this algorithm dealt with the face which segmented into several areas.It adjusted different areas through giving different values.Kept the details where requsted，while other areas were simplified in an large extent. When this method was applied ，the data would be reduced and remained the high details of preparative operation in the virtual face lifting.This algorithm can keep the characteristics of the model also implement easily and execute on high speed．
Key words:mesh simplification；progressive mesh；feature point；edge collapse
在計算機圖形學中，一般使用三角網格描述復雜的三維形體。隨著三維數據獲取技術的不斷進步，網格的數據量會非常龐大。這給三維模型的存儲、傳輸和繪制都帶來許多困難，因而必須對這類網格模型進行簡化。國內外對網格簡化的研究已取得一系列成果。Schroeder等人[1]提出了基于頂點刪除的網格刪減方法；Hoppe[2]在網格優化算法的基礎上提出了基于邊折疊的遞進網格生成方法；Isler等人[3]使用邊折疊和三角形折疊操作來實時生成簡化模型；Garland等人[4]利用二次誤差方法來控制網格簡化誤差；周昆等人[5]則結合Isler和Garland的方法，并給出了一種傳遞簡化誤差的方法。
上述簡化方法都是針對整個三維模型進行處理的，而在實際應用領域，如虛擬整形手術中，如果只做隆鼻手術，那么只需要在鼻子附近保持較高的細節，而在其他區域則不必保持高細節。這樣處理后將會大大減少整個模型的數據量。本文正是基于這種思想，在邊折疊簡化算法的基礎上，把人臉按照特征點的分布進行分塊處理，從而達到減少數據量的目的。
1 人臉特征點標定
1．1 人臉特征點的定義
我國古代藝術家早就發現人臉的基本形狀及五官之間的位置存在三庭五眼的比例關系。Farkas[6]定義了一套科學的人臉測量方法，該方法共使用到47個臉部的特征點。圖1描述了部分特征點的定義。命名規則采用解剖學專業名詞的縮寫，如內眼點使用en(endocanthion)、耳屏點使用t(tragion)。由左右任意耳屏點t及下眼點or(orbitale)確定了人臉的標準水平面即法蘭克夫水平面（Frankfurt horizontal），在測量過程中，通常將人臉統一到法蘭克夫坐標系下進行測量。同時，用鼻根點n（nasion）、鼻下點sn(subnasale)及頜下點gn(gnathion)來確定人臉的豎直中軸。
在本文后面部分就是按照圖1所示特征點的分布，根據面部整形常見的手術區域，把人臉分成七大塊：左耳、右耳、左眼、右眼、鼻子、嘴、其他區域。
1．2 采用光線投射法進行特征點標定
1．2．1 光線投射算法
光線投射法是要把用戶給出的二維屏幕坐標點轉換為空間三維點，再從此點引一條三維空間直線，向物體空間延伸，通過計算求得它與三維物體表面的交點。直線可能與多個表面相交，存在多個交點。比較各點與起始點的距離，那個離起始點最近的交點就是所需的點。根據光線投射法原理，可以從屏幕上鼠標所在的點沿視點方向發射一條射線，尋找此射線與三維實體的交點，即可獲取空間三維實體、空間三維實體的坐標點、三維空間實體中三角面片等數據，實現對空間三維實體的標定。該算法的核心是求交算法。所謂求交算法就是依據用戶給出的屏幕坐標點向場景引出一條直線，求得它與場景中三維景物的最近交點P，也就是直線與曲面的求交問題。
這條直線可以由初始位置P0和單位向量U來描述，沿直線離P0點距離為S的任意點P的坐標可由式（1）表示。
其中：P為起始點；初始單位向量U是垂直于屏幕指向內的。為了計算表面交點，可聯立求解直線方程和場景中各物體表面的曲面方程。
為了簡化問題和提高計算速度，可將實際中常用的曲面分割成為多個小多變形(如四邊形、三角形)面片去逼近曲面。這樣，直線與曲面的求交問題就簡化為與簡單多邊形面片的求交問題。三角形是最簡單的多邊形，它容易逼近曲面、計算速度快，因此三角形是逼近曲面多邊形的首選。本文對三維景物進行建模時就是采用三角面片。
1．2．2 算法實現步驟
在計算直線與三角形的交點時，一般是把三角形所在的平面方程寫出來，求出直線與該平面的交點，再判斷交點是否在三角形內。這種求交算法在速度上仍不能滿足要求。常規的改進算法是利用包圍體作求交測試的方法來得到交點，也就是將一個或多個相鄰三角面片作測試；若有交點，則只需由U×N＜0(U為直線的單位向量；N為物體表面的法向量)測試，就可找到最前面的三角面片。另外，還需對面片上滿足直線方程的點P求解平面方程N×P=-D(設三角面片的平面方程為AX+BY+CZ+D=0。其中N=(A，B，C)。若N×(P+SU)=-D，由于點P同時位于平面和直線上，且從起始直線位置到平面的距離為
S=(D+N×P)/（N×U）(2)
通過以上步驟，可求得直線與多邊形所在平面的交點，但該點可能不在多變形邊界內。因此，還需通過內外測試法來確定直線是否與該多邊形內交。若所得交點為內點，就得到了所需的點。
由表面繪制得到的三維模型由百萬級數量的三角面組成，如果直接用直線與其求交會比較費時，所以可以先求出直線和體數據的交點，再求與該交點鄰近的三角面。
從測量的角度來看，直線和體數據的交點是需要的測量點，但為了能夠直觀顯示以及后續的交互性，必須在三角面上定點。從精確度上來看，直線和體數據的交點與該直線和三角面的交點誤差在1個像素以內，即1個空間分辨率(pixel spacing)單位(一般小于1 mm)，因此測量的誤差也是在毫米級，定點的精度可以滿足測量的需要。
如果定點的精度確定為毫米級，那么可以將一個毫米表示成一個像素，這樣既可以減少數據量又可以滿足一定的精度(誤差為1 mm)。例如，若空間分辨率單位為0.5 mm，以一個毫米為最小像素單位約是以一個空間分辨率單位為最小像素單位的數據量的1/8，但精度也只有1/2。圖2、3為采用本文的方法對部分特征點進行標定的結果。
2 基于邊折疊的簡化和遞進網格的構造
2．1 邊折疊簡化算法
Hoppe[2]在網格優化算法中首次提出用邊折疊進行簡化操作。邊折疊操作選擇兩個相鄰的頂點u和v，刪除它們之間的邊(u，v)和這條邊上的兩個三角形，然后將兩頂點合并到一個位置。此處應注意兩個關鍵問題：折疊次序；如何確定邊折疊后新頂點的位置。解決上述兩個問題的原則是折疊的邊及其折疊后新頂點位置的選取應使簡化后的網格與原網格的誤差盡可能小。針對此問題，不同的算法采取了不同的解決途徑。Hoppe在1993年采用能量優化的方式來確定折疊次序和新頂點的位置[6]，能量優化方法計算復雜，所需時間較長，但是生成模型的效果卻是在所有化簡方法中最好的[8]。Garland等人在1997年用局部二次誤差度量來衡量邊折疊的代價，以新頂點到被折疊邊的兩個頂點相關聯平面的距離平方和作為誤差測度[4]。Garland的方法在邊的選擇時采用了二次誤差的方法避免了能量的復雜計算，在時間復雜度和簡化質量兩方面都有較為出色的表現，實現了計算時間與簡化效果之間的協調統一。本文就是在Garland算法的基礎上作進一步研究。
邊折疊算法由于速度、健壯性等優勢，以及其作為增量式簡化算法具有自然生成多分辨率模型的優點，得到了廣泛深入的研究，相關算法較多。
2．2 遞進網格的構造
Hoppe提出了一種基于邊折疊的遞進網格的構造方法。對一個原始網格模型，每執行一次邊折疊操作就得到一個簡化模型，并把這個邊折疊操作記錄下來。當算法得到原始網格模型的最簡表示時，同時也得到了一個邊折疊操作序列。以這個序列的逆序對最簡網格模型執行邊折疊操作的逆操作(頂點分裂)，就可以得到原始網格模型和最簡網格模型之間的任意層次的網格模型，這就是遞進網格的基本思想。
圖4所示正是邊折疊與頂點分裂的對偶操作。從圖中看出，一個初始網格M0經過一系列的刪除邊操作，得到一個粗糙網格Mn，如果將第i個刪除邊操作記為ecoli ，則上述簡化過程可以記為M0ecol1 M1ecol2M2ecol3M3…ecolnMn。邊折疊的逆操作，頂點分裂則從一個初始較為粗糙的網格M0，通過系列拆分一個頂點Vi，Vi被拆分為一條邊(Vi，Vi+1)，網格模型增加一個頂點Vi+1和兩個三角面片。如果將第i次頂點分裂操作記為vspliti，一個拆分點單元操作可以表示為一個五元組{s，l，r，t，A}。其中：s、l、r、t是頂點的索引號；A是新增點的信息。以上過程可以記為M0vsplit1 M1vsplit2M2vsplit3M3…vsplitn
Hoppe定義二元關系( M0，{vsplit1，vsplit2，…，vsplitn}) 為一個遞進網格模型。其中：M0是一個較粗糙的網格模型， 而vspliti是一個頂點分裂五元組。
2．3 遞進網格構造的二義性
從圖5可以看出，同一個網格經過頂點分裂為兩個不同的模型，映射ecol和映射vsplit并不是一一對應，它們之間并不是真正的可逆操作[9]，因此頂點分裂具有二義性。由于映射vsplit存在上述二義性，網格Mi經過一系列頂點分裂操作后可能產生不同于原始網格M0的網格，甚至改變網格模型的拓撲結構。如果要避免出現類似圖5所示的結果，那么就必須進行復雜的合法性判斷。
如果想簡單地解決上述二義性問題，可以在網格簡化時，直接把每次頂點分裂所需要的鄰接三角形信息全部記錄下來。但是，因為網格中每個頂點的鄰接三角形數目不確定，所以，這種遞進網格結構會十分無序和復雜。為此本文不采用遞進網格這一思想，而是將三維模型進行分塊處理，解決了構造遞進網格和解決其二義性的難題，可以非常方便地獲取各區域不同的細節度。
3 基于特征點的網格模型簡化
3．1 基于特征點的模型簡化算法思想
現在的模型簡化算法大多著重于算法本身的效率，而在實際應用中，特定三維模型有許多自身的特性。例如對于三維人臉模型，只要人臉特征點固定，那么整個人臉的大致輪廓就基本可以確定下來。在特定的模型簡化中，如果能很好地利用模型本身的特性，將是一個非常有效的模型簡化途徑。
本文在三維人臉模型簡化中充分利用了人臉模型自身的特性，即在特征點標定之后，把人臉網格按照特征點的分布進行分塊處理。在各分塊中可以分別采用不同的閾值進行調節，針對后續的待手術區域，可以保持較高細節，簡化程度較少，而對于不需要進行手術的區域，可以設定較大的簡化閾值，從而極大地減少了數據量。
對于各區域的邊界處理， 是算法的關鍵之處。本文在后一節將會詳細闡述如何對邊界進行處理。
3．2 邊界處理
對邊界的處理包括三個方面：a)分隔線與三角網格的關系；b)邊界線的處理；c)當前區域是否屬于需簡化區域的判斷。
首先，分割線與三角形的位置關系，如圖6所示。從圖6可以看出，區域分割線與三角形有兩種位置關系：
a)把一個三角行分割為兩個三角形；
b)一個三角形分割成一個三角形和一個四邊形。
對于第一種情況，可以簡單地直接分割為兩個三角形；對于第二種情況，連接四邊形的一條對角線，將四邊形分成兩個三角形。應當注意的是，四邊形分為兩個三角形時，有兩種選擇，即順時針方向和逆時針方向。為了避免二義性，本文規定，被加入的三角形應為順時針方向，如圖7所示。圖8所示是逆時針方向，這是一種錯誤的分割方法。
其次，在把模型分塊后，邊界線既屬于左邊模型，又屬于右邊模型。所以，在進行邊折疊操作時，首先判斷當前邊是否屬于邊界邊。如果是，規定不進行折疊；否則進行折疊。
最后，把模型分成了幾大塊，所以在進行折疊操作時，應先判斷當前區域是否屬于需要折疊的區域。由于被分塊的模型具有封閉性，必須判斷當前區域是否屬于這個封閉區域(只需要將比較該點的坐標值與封閉區域線的x、y、z值的最小最大值進行比較)。如果是，則折疊；否則不折疊。
3．3 詳細算法步驟
通過以上分析，算法流程可以分為以下幾大步驟：
a)采用光線投射算法標定特征點。
b)根據特征點的分布特點，同時為保持模型的真實性，把人臉分成七大塊（圖1）。
c)開始執行邊折疊操作。
d)根據用戶輸入需要簡化的區域和閾值，判斷當前邊是否屬于需要簡化的封閉區域內。如果是，則進行邊折疊簡化操作；否則不進行操作。
e)如果還沒有達到用戶的要求，跳轉到c)，繼續簡化。
f)達到用戶要求，簡化結束，生成最終簡化模型。
3．4 實驗結果及分析
為了驗證算法思想，筆者在VC 6.0+OpenGL環境開發了這個模型簡化程序。圖9是實驗結果的截圖。
從以上結果看出，采用本文基于特征點的分區域處理思想，能夠極大地減少三維模型三角面片數量，同時保持了待手術區域高度的細節特征，為后續工作打下了良好的鋪墊。
4 結束語
雖然計算機硬件的發展日新月異，但在對復雜三維模型操作時依然遠遠不夠，所以網格模型簡化不可或缺。在眾多簡化算法中，本文采用基于邊折疊的簡化算法，針對特定三維人臉，提出基于特征點的分區域處理思想，得到較好的實驗結果，極大地減少了模型的三角面片數量。但是，還存在以下問題有待進一步研究改進：本文算法只適合人臉模型，對其他模型則不適用；本文的工作依賴于基于邊折疊算法，依賴于這種算法思想的進一步改進；在各區域的邊界處，處理方法過于單一。有待于提出更好的連接模型。
參考文獻：
［1］SCHROEDER W J，ZARGE J A，LORENSEN W E.Decimation of triangle meshes[J].ComputerGraphics，1992，26(2):65-70.
[2]HOPPE H.Progressive meshes[J].ACM Computer Graphics，1996，30(1):99108.
[3]ISLER V，LAU R W H，GREEN M.Realtime multiresolution modeling for complex virtual environments[C]//Proc of ACM Symposium on Virtual Reality Software and Technology.Hong Kong:ACM Press，1996:1119.
[4]GARLAND M，HECKBERT P S.Surface simplification using quadric error metrics[J].Computer Graphics，1997，31(3):209-216.
[5]周昆，潘志庚，石教英.基于三角形折疊的網格簡化算法[J].計算機學報，1998，21(6):506-513.
[6]FARKAS L.Anthropometric facial proportions in medicine[M].[S.l.]:Thomas Books，1987.
[7]HOPPE H，DeROSE T，DUCHAMP T，et al.Mesh optimization[C]//Proc of the SIGGRAPH’93.1993.
[8]CIGNONI P，MONTANI C，SCOPIGNO R A.Comparison of mesh simplification algorithm[J].Computer Graphics，1998，22(1):37-54.
[9]陶志良，潘志庚，石教英.支持快速恢復的可逆遞進網格及其生成方法[J].軟件學報，1999，10(5): 503-507.
注：“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文。”
