1、三維圖形的表達和分析及其在三維仿真和模型檢索中的應用BA 07011022 何其真 計算機學院概述隨著計算機軟硬件的成熟，三維模型逐漸在電腦游戲、工業輔助設計、醫學仿真虛擬手術、模型的檢索與識別以及虛擬的教學場景等方面得到了廣泛的應用。三維模型在計算機中的存儲是點和面的集合，如何從這些信息中提取有效的特征，表達出模型的性質，是當前急需解決的問題。總體來說，三維模型的表達可以分成兩個方向：物理性質的表達和幾何形狀的表達。問題的難點在于物理性質和幾何形狀的獨立性，模型頂點序列的無序性，采樣點數量的不統一，沒有統一的世界坐標系，模型受旋轉、縮放、平移的影響等。模型物理性質的研究，是在給定的外力作用下

2、研究模型的形變情況。目前國內外學者已經提出了一些解決方案，使用不同的模型來解決這個問題。典型的有彈簧模型1，有限元方法2和張量模型3。彈簧模型是基于線性彈性的假設，用虛擬的彈簧來鏈接各個結點。它的優勢在于結構簡單易于計算，但是彈簧的彈性系數靠經驗指定，缺乏物理力學的基礎。有限元方法是分析不規則物體受力形變的有效方法，它把物體劃分成許多個有限元，通過分析每個有限元的受力性質來得到整個物體的剛度矩陣。它具有物理性質的支持，在應變小于20%的時候計算是準確的。但是它的缺點在于消耗大量的時間和空間，不能實時計算。張量模型是前兩者折衷的一個產物，把物體的剛度矩陣分散到每個節點上，使得結構簡單，加快了計算

3、速度，但是需要很長時間的預處理，而且也很難達到實時的要求4。有學者使用統計模型5的方法對仿真整容手術術前和術后的面部形狀進行建模，通過術前的形狀預測術后的形狀6。該方法的計算非常快，但是它沒有考慮到頜骨的形變過程，只是假定所有患者所經歷的手術是一個完全一致的“標準手術”，而且該方法需要大量的實際樣本訓練統計模型。可以看出，目前的解決方案不能同時滿足準確和高效的要求，而在一些特殊的應用中同時滿足這樣兩個需求是很需要的，比如虛擬整容手術計劃，醫生需要實時地操作虛擬手術刀，立即得到準確的形變模型，就可以更好地和患者進行溝通和交流，選擇最合適的手術方案。所以我們的研究從這個實際的應用入手，試圖尋找既高

4、效又準確的形變計算方法。幾何形狀的表達是為模型檢索、識別和語義標定提供依據。提取的特征要有效地表達三維模型的空間整體形狀，與采樣點的多少、位置、坐標系的選擇以及旋轉縮放平移無關，且具有魯棒性，對噪聲不敏感。模型的匹配現階段主要采用傳統的文本檢索中的匹配方法（余弦模型，語言模型等）。目前國內外的學者采用的特征主要有：1. 全局信息的柱狀圖7,8, 表達頂點、矩、距離等的統計信息，與旋轉縮放平移無關，但是它不能表達局部的幾何形狀。2. 特征地圖9,10 ，把每一個頂點特征（局部信息：曲率，直徑等）映射到物體的外接球上，和旋轉有關，需要額外的傅立葉變換處理。3. 形狀上下文11，一個選定點和 其四周

5、頂點的關系，表達了局部形狀特征。旋轉圖是一種二維的柱狀圖來表達形狀上下文，每個頂點對應一個二維柱狀圖，表達了這個頂點四周的上下文關系。這是一種非常有效的表達方式，被廣泛應用于三維模型檢索和識別13,14,15。但是每個頂點對應一幅圖像，存儲量和計算量都是巨大的。4. 可視化關鍵字16,為了解決上面的問題，把每個頂點的柱狀圖聚類，每一個類是一個關鍵字，幾個關鍵字的組合表達了三維物體。這是一種有效的降維方法，但是聚類之前的預處理也是需要大量的存儲和計算。5. 基于投影的表達12。把三維物體投影到若干平面（通常由PCA主軸決定），用幾個特征投影來表達三維物體, 受噪聲影響較大，不同的投影平面，會得到

6、完全不同的投影?？梢钥闯瞿壳叭S圖形的特征提取主要還是局限在Topic（主題）級別，即如果兩個模型含有相同的Topic，則認為兩個模型是相同的，但沒有在Context (上下文)的層次上考慮，即沒有考慮Topic之間的位置關系。其中的難點在于三維模型缺乏統一的世界坐標系，因此位置關系缺乏一個統一的描述。所以我們的研究嘗試找出相應的解決方案。參考文獻：1 Gelder, A.V. Approximate simulation of elastic membranes by triangulated spring meshes. J. Graph. Tools, vol.3(2),pp:21-42

7、(1998)2 M Bro-Nielsen, Cotin S. Real-time volumetric deformable models for surgery simulation using finite elements and condensation. Computer Graphics Forum, vol.15(3), pp:57-66 (1996)3 S Cotin, et.al .A hybrid elastic model allowing real-time cutting, deformations and force-feedback for surgery tr

8、aining and simulation. The Visual Computer, 16(88):437-452 (2000)4 W.Mollemans,et. al. Predicting soft-tissue deformations for a maxillofacial surgery planning system: From computational strategies to a complete clinical validation.Medical Image Analysis,vol.11(3)pp:282-301(2007)5 6 S Meller, E Nken

9、ke, W Kalender. Statistical Face Models for the Prediction of Soft-tissue Deformations after Orthognathic Osteotomies. MICCAI, vol. 3750, pp:443-450 (2005)7 Eric Paquet, et al. “Description of shape information for 2-D and 3-D objects,” Signal Processing: Image Communication, vol.16, pp:103-122, 200

10、08 R.Osada, et al., “Matching 3D Models with Shape Distributions,” In Shape Modeling International, May 20019 Meng Yu, et al, “3D Model Retrieval with Morphing-based Geometric and Topological Feature Maps,” Proc. IEEE conf. on Computer Vision and Pattern Recognition(CVPR03), vol.2, pp: 656661,200310

11、 Assfalg, J., Del Bimbo, A., and Pala, P, “Curvature maps for 3D CBR,” Proc. the International Conference on Multimedia and Expo (ICME03), vol.1, pp:301-304, 2003.11 Greg Mori, Serge Belongie, Jitendra Malik, “Shape contexts enable efficient retrieval of similar shapes,” Proc. IEEE Conf. on Computer

12、 Vision and Pattern Recognition (CVPR01), vol.1, pp:723-730, 200112 S Ruiz-Correa, et al. “A New Signature-Based Method for Efficient 3-D Object Recognition,” Proc. IEEE Conf. on Computer Vision and Pattern Recognition (CVPR01), vol.1, pp:769-776, 200113 Jurgen Assfalg, Alberto Del Bimbo, Pietro Pal

13、a, "Content-based Retrieval of 3D Objects using Spin Images", IEEE Transaction on Multimedia, vol. 9(3), pp: 589-599, 200714 Pedro A. de Alarcón, et al. “Spin Images and Neural Networks for Efficient Content-Based Retrieval in 3D Object Databases”, (CIVR02), pp:225-234, 200215 Assfalg

14、, et al. “3D content-based retrieval with spin images”, Proc. of IEEE International Conference on Multimedia and Expo (ICME04), pp: 771-774, 200416 Y. Liu, H. Zha, and H. Qin, “Shape Topics: A Compact Representation and New Algorithms for 3D Partial Shape Retrieval,” (CVPR06), pp.2025-2032, 2006.創新點

15、和可行性分析在本課題的研究中，主要研究以下2個問題。1. 尋找一種高效又準確的三維物體的形變算法。技術路線：1) 使用有限元分析產生大量虛擬樣本定義新的統計樣本，把加在物體上的外力引進統計樣本中2) 從虛擬樣本中訓練，通過PCA分析得到樣本均值和樣本變化參數，從而得到統計模型 (Mr-SDM)3) 根據得到的統計模型，從給定的外力，就可以計算出物體的形變。這是已知一個樣本中的部分信息，補全剩余信息的問題。通過配準已知的部分信息（外力），即可推算出未知的信息（結點位移，即形變）可行性分析：1) 快速 使用統計模型實時計算，大量的有限元分析時間被轉移到離線的訓練階段2) 準確 有限元分析方法保證了物體的材料性質3) 相比其它統計模型, 解決了樣本缺乏的問題, 并在統計模型中引入了外力作用, 使模型更加完備創新點：1) 使用有限元的方法為統計模型虛擬出一些樣本，解決其小樣本的問題2) 在統計模型里 樣本的定義中引入外力的信息，以此來刻畫模型的物理性質（外力和形變的關系）2. 尋找更好地表達三維模型空間幾何形狀的特征。技術路線：1) 用對相對角度分布(Relative Angl