三維模型搜索引擎的研究進展

摘 要：首先簡要介紹了三維模型搜索引擎的發展概況，然后討論了三維模型搜索引擎的關鍵技術及相關的研究進展，最后指出了三維模型搜索引擎進一步的發展前景。

關鍵詞：三維模型； 搜索引擎； 相似度匹配； 形狀描述符

中圖法分類號：TP391文獻標識碼：A

文章編號：1001—3695(2007)02—0010—03

近年來，隨著三維技術的發展，一種新型的多媒體數據——三維模型得到了廣泛地應用。不同于傳統的文本、音頻等多媒體數據，生動、形象、逼真是三維模型的突出特點，這一特點使其在機械制造、娛樂游戲、生物化學、電子商務、藝術欣賞、考古應用以及虛擬現實等眾多領域中有了長足的發展[1]。計算機圖形學和模型數字化工具的進步為構造高質量的三維模型創造了條件，而因特網為傳播這些模型提供了手段。今天三維模型的應用正在滲透到人們工作和生活的各個方面，如何在網絡環境中實現對三維模型的高效檢索是目前搜索技術研究的熱點[2]。

1 三維模型搜索引擎的發展概況

傳統搜索引擎的工作方式是對網頁上的文本建立索引，返回用戶的查詢結果是與這些索引相一致的頁面[3]。所謂搜索引擎（Search Engine），是一種利用自動搜索技術，通過對網絡資源進行標記，以提供檢索服務的工具軟件[4]。多媒體搜索引擎索引的是圖像、視頻或音頻等數據。這些多媒體數據除了文本外，大多是非結構化的數據。目前，大多數多媒體搜索引擎均支持使用關鍵字對多媒體數據進行搜索，這是一種精確檢索。多媒體數據則通過手工標注建立索引，與用戶輸入的關鍵字進行精確匹配[5]。該方式檢索過程實現簡單，可直接獲取語義信息，結果精確；但是手工標注不僅費時費力，而且難以準確反映媒體內容，容易受到標注者個人主觀性的影響。

現在許多研究者都致力于基于內容檢索的研究[7]，這是一種相似度檢索。例如IBM公司的QBIC就是一個通過圖像的顏色、紋理和輪廓等進行查詢的圖像檢索系統[6]。這種方式在預處理階段就對媒體庫中的圖像資源提取顏色、紋理和形狀等特征信息，然后存放到特征庫中；在用戶提出查詢請求后，系統對用戶輸入的查詢對象進行特征提取并與特征庫中的參考特征向量進行相似度匹配；最后按照相似程度大小排序并返回到檢索列表中[7]。由于基于媒體內容進行檢索，具有較強的客觀性，但從底層特征提取高層語義較為困難，檢索結果不夠精確。目前這種技術尚在發展中[8]。

三維模型通常具有顏色、紋理和形狀等特征。用戶搜索三維模型時，一般對顏色和紋理信息使用較少，這主要是因為在實際應用中，人們很容易對其顏色和紋理進行重新渲染。用戶感興趣的主要是三維模型的形狀，形狀是三維模型最為本質的特征，可以作為區分模型的主要依據。通常認為，形狀匹配是三維模型檢索的主要方式。實際應用中三維模型的空間位置、大小和方向都是變化的，對三維模型形狀特征的描述必須考慮到三維模型的幾何變換問題[8]。例如，不能因為待檢索模型的旋轉、縮放和平移就錯誤判定其屬于不相似模型。顯然，三維模型形狀描述符(Shape Descriptor，SD)必須滿足幾何不變性，即對模型的平移、旋轉、縮放等幾何變換具有不變性。

文獻[9]中，普林斯頓大學提供了一種三維模型搜索引擎的研究方案，這是一種基于文本關鍵字、二維和三維形狀及其組合的查詢方式，如圖1所示。方案中對基于二維和三維形狀的查詢采用了球面調和函數作為形狀描述符，該描述符具有幾何變換不變性，適合三維模型的相似度匹配。但是對用戶繪制的具有內部細節的草圖匹配較差。基于形狀的人機接口使用起來還是比較麻煩，用二維草圖和三維草圖進行查詢的效率也不如直接用關鍵字查詢。

文獻[10]中，臺灣大學的三維對象檢索系統提供了一種基于文本關鍵字、二維草圖（可包含內部細節）或選擇現有模型進行查詢的研究方案。相似度是通過對比三維模型的二維投影視圖和二維草圖的MPEG—7[11]基于區域的描述符得到的（圖2）。

文獻[12]中，亞歷山大的一個在線商業系統通過調整模型屬性的權值進行相似度匹配（圖3）。這些屬性包括形狀、顏色和縮放比例。該商業系統擁有4 500個三維模型，其中許多模型僅是在方向上有所不同。

2 三維模型搜索技術

三維模型搜索引擎是一個在網絡中搜索三維模型的軟件。它通過網絡爬蟲（Crawler）搜索網上的三維模型資源，并將這些資源保存到本地數據庫中。用戶可以通過文本對三維模型進行描述，也可以手工繪制三維模型草圖表達所需的三維模型形狀。搜索引擎既可以通過匹配關鍵字檢索用戶描述的三維模型，也可以通過匹配模型草圖的形狀特征檢索三維模型。因此，三維模型搜索引擎的設計思想是通過網絡爬蟲搜索網上三維模型數據，向用戶提供文本輸入和繪制三維模型草圖的查詢接口，采用基于關鍵字和基于形狀特征實現對模型的檢索[13]。

2.1 三維模型搜索引擎的組成

三維模型搜索引擎的總體架構[9]由三部分組成（圖4）：①網絡爬蟲和三維模型庫構成了獲取部分，這部分負責從網絡中搜索可用的三維模型數據；②分析索引模塊和索引元數據庫構成了分析部分，目的是為了對三維模型數據建立索引，并將索引保存在數據庫中；③查詢接口、查詢處理和匹配模塊則構成了匹配部分，對用戶查詢進行匹配并返回結果。

其中，獲取部分的網絡爬蟲由一個Server和多個Clients組成。Server負責維護已訪問和待處理URLs的Hash表、管理站點訪問權限并負責對Client的操作進行調度；Client同時啟動80—100個進程對網絡中的三維模型進行爬取（Crawl）搜索并存入本地數據庫中[9]（圖5）。

分析部分的主要任務是提取三維模型的索引。由于用戶可以通過文本、三維模型草圖或模型的二維視圖草圖三種方式提交查詢，因此三維模型的索引有文本索引、三維索引和二維索引。文本索引可以從爬蟲搜索到的模型網頁以及模型文件本身提取。三維索引和二維索引的提取需要預先將模型文件格式統一轉換為圖形格式，其中三維索引可以直接從模型文件中提取，而二維索引還需要將模型文件投影為二維視圖圖像后才可以提取。這些索引分別被保存到相應的數據庫中。

當用戶提出查詢請求時，由匹配服務器根據用戶的查詢請求分別與索引庫中的模型索引進行文本匹配、三維形狀匹配和二維形狀匹配，按照匹配的相似度將相似的三維模型返回給用戶[9]。獲取與分析部分通常離線進行，匹配部分則在用戶查詢提出后在線運行。

2.2 三維模型的相似度匹配

三維模型的相似度匹配采用關鍵字或形狀特征匹配兩種方法。關鍵字匹配是將用戶輸入的文本與文本數據庫的索引進行匹配。文本索引源有三維模型的文件名、網頁上的文本、URL路徑、網頁上下文、網頁標題、Wordnet[14]中同義詞和上位詞。形狀特征匹配[14]的過程是：首先計算查詢草圖與庫中模型形狀特征之間的距離，然后根據數據庫模型和查詢草圖的鄰近度分類，最后將距離最近的前K個模型返回（圖6）。

下面進一步討論幾種常用的匹配方法：

(1)文本匹配方法。該方法比較的是文本索引的相似度。文本索引是通過計算詞頻/逆文檔頻數（TF/IDF）[15—17]得到的。TF/IDF實際上是一個詞加權向量（vi=∑wi×ti），相似度是兩個模型的詞加權向量的夾角。詞加權wi是根據詞在本文檔和所有文檔中出現的頻率來定義的，公式為tf×log（N/df)，其中tf為本文檔的詞頻，N為文檔數量，df為詞在所有文檔中的頻率。根據wi的公式，文檔集中包含某一詞條的文檔越多，說明它區分文檔類別的能力越低，其權值越小；而文檔中某一詞條出現的頻率越高，且該詞在其他文檔出現的頻率越低，說明它區分文檔類別的能力越強，其權值越大。當df定義為文檔中包含該詞的文檔數時，稱為TF/IDF Log Words法，而df為文檔中包含該詞的總次數時，稱為TF/IDF Log Occur法[18]。當用戶通過輸入關鍵字檢索三維模型時，根據輸入關鍵字在文本索引中的權值確定其查詢結果，權值大小決定了每個模型文件在返回結果中出現的位置。

(2)形狀匹配法。該方法通過計算查詢草圖與數據庫中模型形狀特征的距離進行相似度匹配。形狀特征，也稱為形狀描述符，相似度通常是兩個形狀特征向量的歐式距離[19]。公式如下：

直接匹配法[20]是一種形狀匹配法，其相似度等于模型表面對應點距離的總和。這種方法在進行幾何相似性匹配時，需要將兩個模型以重心為基準點平移對齊，相似度計算簡單，但是對齊操作是一個耗時的工作，對于大型數據模型庫和實時系統來說，使用這種方法的效果不好（圖7）。

在實時系統中比較實用的方法是將三維模型表示為形狀描述符，模型的距離為形狀描述符的距離，常用的形狀描述符[21—25]有： 

①形狀直方圖（Shape Histogram）。使用一組同心球作為直方圖劃分網格，統計每個網格內的模型頂點數量，然后通過計算直方圖之間的歐氏距離來獲得三維模型的幾何相似度。

②形狀分布（Distribution Shape）。使用兩點之間的距離作為幾何函數，計算三維模型的幾何分布直方圖，然后通過計算幾何分布直方圖的范數距離來獲得三維模型的幾何相似性。

③球面調和函數（Spherical Harmonics）。首先計算三維模型所有采樣頂點在每個球面經緯度網格中的最大半徑距離，然后計算最大半徑距離的球面調和分析系數，最后通過球面調和分析系數比較來獲得三維模型的幾何相似性。

④三維調和函數向量（3D Harmonics Vector）。首先對三維模型進行頂點采樣，計算一組同心球面與三維模型相交進行體素化，然后計算每個同心球相交的球面調和分析特征向量，最后通過計算球面調和分析特征向量之間的相似距離來獲得三維模型的幾何相似性。

⑤擴展高斯圖像（Extended Gaussian Images）。首先計算三維模型的擴展高斯圖像，然后計算擴展高斯圖像的球面調和分析特征向量，最后通過球面調和分析特征向量之間的相似距離來獲得三維模型的幾何相似性。

(3)球面調和函數法。由于在實際應用中三維模型常常會有旋轉、平移和縮放等幾何變換，因此形狀描述符應滿足幾何變換不變性。球面調和函數法由于其特征向量容易計算和對比，且具有幾何變換不變性，適合用于檢索三維模型。獲取三維模型的形狀描述符需要預先將三維模型體素化，然后提取其二維形狀特征。具體步驟是首先計算出以三維模型重心為球心的最小包圍球，以該球半徑的1/R為單位將這個模型投射到2R×2R×2R的網格中，然后將網格中心與三維模型的重心對齊。每個格子的數值非0即1，如果任何一個格子內部，存在三維模型表面上的點，就將該格子的數值設為1，反之將該格子的數值設為0。這樣，就得到了三維模型的體素化表示，再將網格限制在一系列半徑的球殼上，每個球殼均對應一個二值化的球坐標方程：

最后將每個方程分解為球面調和函數的和，組合系數就是一組具有幾何變換不變性的特征向量，即

將這樣一系列特征向量組合起來，形成一個特征矩陣，該矩陣就是形狀描述符，可以用來比較不同三維模型之間的形狀差異（圖8[13]）。

使用二維草圖與三維模型的二維投影視圖進行匹配時，需要提取二維形狀描述符。其提取過程是：首先對二維圖像的邊界輪廓進行歐式變換，以二維圖像中心為圓心獲取最小包圍圓；給定不同半徑求出一組圓周函數；將圓周函數展開為三角函數的和；由于在相同頻率內進行幾何變換時不會改變幅值，將圓周函數的特征值定義為由三角函數的幅值組成的序列；組合不同的特征值從而得到邊界輪廓的二維形狀描述符。相似度為二維形狀描述符的歐式距離[9]（圖9）。

3 展望

本文首先對三維模型的發展概況進行了簡要介紹，然后對三維模型搜索引擎的關鍵技術與研究進展進行討論，并以球面調和函數為例，詳細討論了形狀特征匹配的方法。顯然，三維模型搜索引擎技術的研究，將極大地推動網上智能化檢索的進展，提高人們生活與工作的質量。

目前看來，三維模型搜索引擎在人機交互[26]和匹配方法上還亟待改進。在人機交互上，首先需要進一步提高人機接口的易用性，如增加用戶輸入指南、用戶草圖后序處理、匹配時可加入內部細節等。另外，亟待開發一種新的三維模型集成交互式繪圖工具[27]，使用戶在繪制三維草圖或二維草圖上不必經過專業培訓就能自由繪制。在匹配方法上，可以加入顏色、紋理和結構屬性進行組合匹配。為了提高查詢速度，可以增加一些常用的模板和訓練集[28]或進行部分形狀匹配等，相似度匹配方法的改進研究也是一個重要方面。

構建用戶個性化分析模塊，實現個性化智能搜索，則是另一個更具挑戰性的課題。我們生活的世界是一個三維世界，隨著三維技術的發展，可以看到多媒體數據的表示一定會逐漸由三維描述替換現有的二維描述方式，對于三維模型搜索技術的研究具有遠大前景，是一個值得我們去深入研究和探索的前沿課題。

本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文。