三維模型搜索通用支撐平臺的設(shè)計與實現(xiàn)

（西北工業(yè)大學 現(xiàn)代設(shè)計與集成制造技術(shù)教育部重點實驗室， 西安 710072）

摘 要：為滿足模型搜索研究領(lǐng)域?qū)?shù)據(jù)管理、算法配置和算法驗證等工具的集成需求，提出一個模型搜索支撐平臺框架。利用面向?qū)ο蠹夹g(shù)，構(gòu)造一個包含應(yīng)用程序表現(xiàn)層、應(yīng)用程序工具層、算法邏輯層、數(shù)據(jù)抽象層、數(shù)據(jù)訪問層和數(shù)據(jù)層的多層體系結(jié)構(gòu)；基于“一具體類一表”映射策略實現(xiàn)對象型數(shù)據(jù)與關(guān)系型數(shù)據(jù)的映射；采用策略模式實現(xiàn)了算法組合和替換的動態(tài)配置機制。實際應(yīng)用表明，該平臺可為模型搜索研究提供工具支持。

關(guān)鍵詞：模型搜索支撐平臺；面向?qū)ο蠓治龊驮O(shè)計；一具體類一表模式；策略模式

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

文章編號：10013695(2009)01019504

Design and implementation of supporting platform for 3D model retrieval

SHI Yuan， MO Rong， CHANG Zhiyong， CHEN Zefeng

(Key Laboratory of Contemporary Design Integrated Manufacturing Technology of Ministry of Education， Northwestern Polytechnical University， Xi’an710072， China)Abstract:Due to the requirement of integrating tools for model retrievalrelated data management， algorithm configuration and algorithm validation，this paper proposed a general supporting platform for 3D model retrieval.Through objectoriented design and analysis technology，established a multilayer architecture including applications， tools，algorithm， data abstraction， data accessing and data layer.Based on one inheritance path one table mapping strategy，mapped objectoriented model to relational data model，and constructed mechanism of dynamic configuration for displacement of algorithms by adopting strategy pattern. Results of application instance reveal that the platform provides necessary tools for 3D model retrieval.

Key words:model retrieval supporting platform; objectoriented analysis and design; one inheritance path one table; strategy pattern

在基于內(nèi)容的三維模型搜索研究領(lǐng)域，目前已經(jīng)實現(xiàn)并發(fā)布了一些進行理論和算法研究的原型系統(tǒng)以及架構(gòu)于Web平臺上的搜索引擎[1~7]。但是上述原型系統(tǒng)和搜索引擎無論是針對普通模型搜索[1~3]還是專業(yè)模型搜索[4~7]，都存在下列不足：a)未涉及如何實現(xiàn)搜索相關(guān)數(shù)據(jù)對象尤其是算法對象的管理。實際的搜索效果除了與算法實驗的硬件環(huán)境、模型種類、數(shù)據(jù)規(guī)模等因素有關(guān)之外，還與算法本身及算法組合密切相關(guān)。因此，規(guī)范有效管理現(xiàn)有算法，實現(xiàn)算法的組合、替換，以便于再現(xiàn)這些算法并將其與新算法對比，是研究開發(fā)新算法的基礎(chǔ)。b）現(xiàn)有代碼與工具難以直接應(yīng)用。為減少研究工作中的開發(fā)量，許多研究者提供了一些開源的代碼和工具，典型的如文獻[8]提供的系列工具，但是由于語言和算法應(yīng)用背景的不同，在實際應(yīng)用中存在著源代碼移植的困難。c)現(xiàn)有通用框架針對性不強，難以集成現(xiàn)有工具。文獻[9]僅提出了一個面向模型搜索的通用框架（digital shape workbench，DSW），而且由于其針對普通三維模型搜索，規(guī)模過于龐大；另外盡管其提供了一些開源的工具但是由于這些工具并非為該通用框架設(shè)計，在將上述工具集成到該通用框架時比較困難。

鑒于此，本文針對三維模型搜索研究的實際需要，提出了一個通用的三維模型搜索支撐平臺框架（model retrieval supporting platform，MRESUP），可以滿足三維模型搜索研究中各種搜索相關(guān)數(shù)據(jù)對象的柔性管理、算法組合的可配置管理，進而實現(xiàn)算法的驗證與有效性的對比。

1 數(shù)據(jù)分類和需求描述

11 數(shù)據(jù)分類

三維模型搜索研究涉及的數(shù)據(jù)種類繁多，數(shù)據(jù)之間的關(guān)系復(fù)雜，為描述方便，同時也將MRESUP管理的數(shù)據(jù)對象分類，本文作如下約定：

a）三維模型。MRESUP管理三角網(wǎng)格類的立體光造型文件（stereo lithography，STL）模型文件。

b）模型類別。模型所屬的類別。依據(jù)來源于某個標準測試庫（benchmark），本文采用的是普渡大學的ESB（engineering shape benchmark）[10，11］。

c）模型縮略圖。表示模型形狀的圖片，與模型一一對應(yīng)。

d）算法。完成某個任務(wù)所需要的具體步驟和方法，它是按照一定順序調(diào)用的。當前算法的前一個算法稱為前置算法；當前算法的下一個算法稱為后繼算法。如無特殊說明，不再區(qū)分。

e）算法類別。對算法的分類（如本文大致分為規(guī)范化算法、特征抽取算法、相似性度量方法）。

f）算法參數(shù)。算法的輸入?yún)?shù)（在滿足算法調(diào)用匹配的前提下，也可視為前置算法的輸出參數(shù)，如無特殊說明，不再區(qū)分。算法調(diào)用匹配原則，即前置算法輸出參數(shù)的類型與當前算法輸入?yún)?shù)的類型相同，前置算法輸出參數(shù)的個數(shù)等于當前算法輸入?yún)?shù)的個數(shù)）。

g）算法組合。完成某個功能的若干個算法的集合，這些算法必須滿足算法調(diào)用匹配原則。

h）算法參數(shù)數(shù)值。某個算法組合下某個算法參數(shù)的具體數(shù)值。

i）算法組合參數(shù)數(shù)值。某個算法組合下多個算法參數(shù)的具體數(shù)值。

j）形狀特征數(shù)值。某個算法組合參數(shù)數(shù)值下，模型形狀特征的具體數(shù)值，表現(xiàn)形式是多維特征向量或矩陣，存儲形式為文本文件。

k）距離。模型搜索領(lǐng)域常用的相似性度量方法，如明氏距離（Minkowski distance）、霍氏距離（Hausdorff distance）、相關(guān)性度量（correlation metric）等。

算法組合、算法、算法參數(shù)、算法參數(shù)數(shù)值之間的關(guān)系如圖1所示。

12 需求描述

MRESUP作為一個通用支撐平臺，必須為搜索相關(guān)數(shù)據(jù)管理、算法動態(tài)配置和對比等提供支持。具體地說，MRESUP應(yīng)該滿足下面兩個需求：a）能夠管理各種種類的數(shù)據(jù)對象，具體需求如表1所示；b）實現(xiàn)算法組合的可配置管理。

表1 MRESUP需要管理的數(shù)據(jù)對象簡表

在三維模型搜索研究領(lǐng)域，有兩個重要的應(yīng)用場景：a)經(jīng)典算法的重用和新舊算法的對比。在搜索算法研究中，算法的重用和對比是最常見的應(yīng)用，如對模型規(guī)范化算法的重用和新舊特征提取算法的對比。b)模型形狀特征提取和模型搜索必須依據(jù)同樣的算法組合配置。在模型形狀特征提取階段，不僅要記錄特征向量的數(shù)值，還要記錄該特征向量對應(yīng)的算法組合參數(shù)數(shù)值；在模型搜索階段，要能依據(jù)選擇的算法組合參數(shù)數(shù)值提取查詢模型的形狀特征，并依據(jù)相同的算法組合參數(shù)數(shù)值查找在數(shù)據(jù)庫中存儲的備選模型形狀特征，然后將兩者依次比較，根據(jù)相似度排序得到搜索結(jié)果。

根據(jù)上述應(yīng)用場景，同時考慮到任何一個算法組合都是由若干個算法組成，每個算法均會包含若干個參數(shù)，這些參數(shù)可以取不同的數(shù)值。上述算法組合—算法—算法參數(shù)—參數(shù)數(shù)值的對應(yīng)關(guān)系如圖1所示。因此，MRESUP要實現(xiàn)算法組合的可配置管理，就必須構(gòu)建一套有效管理上述四類數(shù)據(jù)對象的機制，以及支持上述四類數(shù)據(jù)對象靈活組合的方法，進而實現(xiàn)算法的驗證與有效性的對比。

2 平臺總體框架設(shè)計

21 平臺設(shè)計的基本原則

MRESUP總體方案設(shè)計采用面向?qū)ο蠓治雠c設(shè)計技術(shù)，遵循下列原則：a)開放性。采用開放式結(jié)構(gòu)，便于添加新的算法到平臺上以支持算法組合的對比實驗。b)層次性。將平臺結(jié)構(gòu)劃分為多個層次，提高平臺的可維護性和可重用性，保證平臺的高內(nèi)聚和低耦合。c)獨立性。與三維模型的編輯平臺無關(guān)，可以擴大適用范圍。

22 平臺架構(gòu)

根據(jù)MRESUP的應(yīng)用需求和設(shè)計原則，MRESUP劃分出六個層次，主要有應(yīng)用程序表現(xiàn)層、應(yīng)用程序工具層、算法邏輯層、數(shù)據(jù)抽象層、數(shù)據(jù)訪問層和數(shù)據(jù)層。

1）應(yīng)用程序表現(xiàn)層 為用戶和平臺的交互提供接口，管理、瀏覽各種數(shù)據(jù)對象（model management tool），配置算法組合（algorithm test tool），執(zhí)行模型搜索（model management tool）等。

2）應(yīng)用程序工具層 包含一些圖形用戶界面工具（GUI tools，如縮略圖顯示控件等）、圖片工具（image tools，如圖片文件解析工具）、共用資源（common resources，如通用進度條）等。

3）算法邏輯層 主要是封裝和實現(xiàn)有關(guān)模型搜索的算法，如規(guī)范化算法（normalization）、特征提取算法（feature Extraction）等，以及對算法組合及其參數(shù)數(shù)值的管理（category/combination/algorithm/parameter manager）。

4）數(shù)據(jù)抽象層 將數(shù)據(jù)庫操作中的諸如獲取表名、獲取數(shù)據(jù)對象ID、名稱等通用的操作進行封裝，按照一種統(tǒng)一的方式來處理數(shù)據(jù)庫要保存的數(shù)據(jù)對象，對應(yīng)于DBObjectBaseClasses組件。

5）數(shù)據(jù)訪問層 直接與數(shù)據(jù)庫交互的接口集合，其中DBUtility組件采用ADO（ActiveX data object）數(shù)據(jù)庫訪問技術(shù)和面向?qū)ο蠹夹g(shù)構(gòu)建數(shù)據(jù)庫訪問類，DBObjectUtility組件根據(jù)對象/關(guān)系的映射機制封裝數(shù)據(jù)對象類的屬性和操作。

6）數(shù)據(jù)層 采用MySQL實現(xiàn)數(shù)據(jù)管理。

除此之外，還有一些必備的模型轉(zhuǎn)換組件、可視化組件等。MRESUP的分層結(jié)構(gòu)如圖2所示。

3 平臺關(guān)鍵技術(shù)

31 基于“一具體類一表”映射策略的數(shù)據(jù)庫設(shè)計

由前面的分析可知，MRESUP需要管理的數(shù)據(jù)對象眾多，數(shù)據(jù)對象之間的關(guān)系復(fù)雜，同時考慮到平臺的可擴展性，因此本文采用面向?qū)ο蟮姆椒▉矸治龊驮O(shè)計應(yīng)用程序。由于面向?qū)ο髷?shù)據(jù)庫的理論和技術(shù)還有待完善，MRESUP仍采用關(guān)系型數(shù)據(jù)庫，這樣就存在業(yè)務(wù)實體的對象型數(shù)據(jù)如何與數(shù)據(jù)庫中關(guān)系型數(shù)據(jù)匹配的問題。

解決方案是在對象模型與關(guān)系模型之間建立一個提供數(shù)據(jù)存儲和操作功能的接口界面。這種數(shù)據(jù)訪問模式有三種類型：SQL硬編碼、代理式和模板方法。其中，SQL硬編碼是將數(shù)據(jù)訪問腳本直接嵌入到對象的方法中，直接耦合業(yè)務(wù)類和關(guān)系數(shù)據(jù)庫訪問層，適用于規(guī)模較小的系統(tǒng)中；模板方法是在關(guān)系模型與對象模型之間建立一個中間層——對象持久層，通過對象/關(guān)系映射（object/relation mapping，ORM）技術(shù)將對象映射到關(guān)系數(shù)據(jù)庫中[12]，但是采用ORM會犧牲程序的執(zhí)行效率。另外，為了使算法獲得較高的執(zhí)行效率，MRESUP采用C++語言開發(fā)，無法直接應(yīng)用現(xiàn)有的對象/關(guān)系映射框架，重新開發(fā)則需要較大的開發(fā)工作量。綜合考慮上述因素，本文采用數(shù)據(jù)代理的方式來實現(xiàn)對象與關(guān)系之間的映射。

代理式是在業(yè)務(wù)對象與關(guān)系數(shù)據(jù)庫之間增加一個數(shù)據(jù)類代理層。將業(yè)務(wù)類的SQL語句封裝在一個或者多個數(shù)據(jù)類中。當業(yè)務(wù)對象訪問數(shù)據(jù)庫時，就向數(shù)據(jù)類代理對象發(fā)出請求，然后由代理對象去訪問數(shù)據(jù)庫。這種方法增強了代碼的重用性，適用于中等規(guī)模的系統(tǒng)中。

在對象/關(guān)系映射中，包含屬性映射與對象之間的關(guān)系映射。本文在屬性映射過程中，將具有基本數(shù)據(jù)類型的屬性映射為數(shù)據(jù)庫表的字段。由于本文在設(shè)計類之間的關(guān)系時盡量使用組合/聚合而盡量不使用繼承，在實現(xiàn)對象之間的關(guān)系映射時，采用了one inheritance path one table映射策略，將每個具體類映射成單個數(shù)據(jù)庫表。在這種策略下，因為單個類的所有數(shù)據(jù)都存儲在一張表中，所以訪問數(shù)據(jù)的性能較高，且沒有數(shù)據(jù)冗余。另外，由于對象間的繼承關(guān)系較少，當類需要修改時，修改表的工作量是可控的。上述映射過程用到的具體數(shù)據(jù)類經(jīng)過封裝就形成了圖2中的DBObjectUtility組件（形式為動態(tài)鏈接庫），對應(yīng)的數(shù)據(jù)庫表及表之間的關(guān)系形成了如圖3所示的MRESUP數(shù)據(jù)庫的邏輯模型圖。圖中用數(shù)據(jù)類型為“IMAGE”的屬性統(tǒng)一表示其為二進制大數(shù)據(jù)對象（binary large object，BLOB），可以存儲圖片文件、文本文件和模型文件。

32 基于策略模式的算法動態(tài)配置機制

三維模型搜索算法大致可以分為三類：規(guī)范化算法、形狀特征提取算法和相似性度量方法。一個完整的模型搜索算法也是按照上述順序執(zhí)行的。對這些算法又可以進一步細分，細分的結(jié)果如圖4所示（其中規(guī)范化算法的分類依據(jù)文獻[13]，相似性度量的方法依據(jù)文獻[14]）。由圖4可見，為了構(gòu)建一個通用的算法支撐平臺，必須實現(xiàn)上述三類算法子方法的組合和替換，才能便于作搜索算法之間的對比實驗，便于支撐平臺的擴展，于是必須將算法本身視為數(shù)據(jù)對象，實現(xiàn)上述每個算法的添加、刪除（這里不涉及某個算法具體實現(xiàn)的代碼）。

為了實現(xiàn)前述三類算法子方法的組合和替換，便于作搜索算法之間的對比實驗，本文采用了設(shè)計模式中的策略模式來實現(xiàn)各個算法的組合和替換。策略模式是指定義一系列算法，將每一個算法封裝起來并讓它們可以相互替換的模式。策略模式可以讓算法獨立于使用它的客戶而變化。策略模式提供了替代派生的子類，并定義每個類的行為，剔除了代碼中條件的判斷語句，使得擴展和結(jié)合新的行為變得容易，不需要變動應(yīng)用程序。策略模式可以避免使用多重條件轉(zhuǎn)移語句，系統(tǒng)變得更加靈活。在MRESUP中，有多處應(yīng)用了該模式，如三維模型數(shù)據(jù)導(dǎo)入部分，根據(jù)后綴名選擇不同的數(shù)據(jù)導(dǎo)入算法；再如規(guī)范化算法的實現(xiàn)中，根據(jù)用戶的選擇調(diào)用相應(yīng)的算法，如圖5所示。

4 平臺實現(xiàn)與應(yīng)用實例

41 基于MD5算法的文件惟一性判斷

模型搜索的研究目的之一是減少相同模型的個數(shù)，進而控制整個模型數(shù)據(jù)庫的規(guī)模。在管理三維模型的過程中，尤其是在向模型數(shù)據(jù)庫添加模型時應(yīng)判斷新添加的模型是否與數(shù)據(jù)庫中存儲的模型重復(fù)。另外，鑒于模型形狀特征基本上都是多維的，甚至是一個矩陣，多維數(shù)據(jù)直接存儲在數(shù)據(jù)庫表的字段中會帶來數(shù)據(jù)冗余，而且為多維數(shù)據(jù)創(chuàng)建的多維索引反而會降低查詢的效率。本文采用將模型形狀特征寫入文本文件，將文本文件再存儲到數(shù)據(jù)庫的方法，這樣就必須避免在同一算法參數(shù)組合下重復(fù)提取同一模型文件的形狀特征。綜上所述，本支撐平臺需要管理的模型文件、模型形狀特征數(shù)據(jù)文件都存在一個如何判斷惟一性，避免重復(fù)處理和存儲的問題。本文的解決方案是根據(jù)文件的MD5（messagedigest algorithm 5，信息—摘要算法5）碼判斷其惟一性。

在計算機信息安全領(lǐng)域， MD5算法的一個重要應(yīng)用是保證文件系統(tǒng)的完整性。若文件被修改，那么該文件對應(yīng)的MD5碼就會改變，因此可以根據(jù)文件的MD5碼是否相同來判斷文件是否相同。由于MRESUP涉及的文件惟一性判斷只是一種定性的比較，即僅判斷兩個文件是否相同，而不必定位到文件的不同之處。本文采用的方法是基于MD5算法來判斷文件的惟一性：為每個文件生成一個MD5碼作為該文件的數(shù)字身份，在需要判斷文件是否相同時只要比較兩者的MD5碼即可。另外，由于本文中需要處理的文件大小一般不會達到GB量級（在engineering shape benchmark中，最大的模型文件1299492_rg01.stl大小為21.5 MB，計算MD5碼的時間為1 156 ms），計算和比較模型文件MD5碼的效率是較高的。

42 基于visualization toolkit的數(shù)據(jù)可視化方法

三維模型可視化、算法計算過程可視化（驗證算法的正確性）、搜索結(jié)果可視化、算法對比實驗結(jié)果可視化是一個三維模型搜索支撐平臺必備的功能。本文采用visualization toolkit（VTK）實現(xiàn)上述的可視化。

VTK是一個開源的、用于可視化應(yīng)用程序構(gòu)造與運行的支撐環(huán)境， 具有良好的體系結(jié)構(gòu)和高度的靈活性、可移植性[15]。本文將整個VTK的源碼重新編譯，生成vtkCommon等23個動態(tài)鏈接庫作為實現(xiàn)可視化的基礎(chǔ)組件提供給應(yīng)用程序調(diào)用。實現(xiàn)可視化管線（pipeline）的具體方法遵循VTK的SourceFilterMapperActor模式，不再贅述。

43 應(yīng)用實例

MRESUP以C++作為開發(fā)語言，后臺數(shù)據(jù)庫采用MySQL 5，基于開源的OpenCASCADE 6.2、VTK 5.0.2提供的組件庫開發(fā)，按照便于復(fù)用的原則將功能獨立的模塊以動態(tài)鏈接庫的形式實現(xiàn)（參見圖2中的矩形框），將完成特定業(yè)務(wù)功能集合的模塊以可執(zhí)行程序的形式實現(xiàn)（參見圖2中的圓角矩形框）。MRESUP中算法配置組合工具的一個運行實例如圖6所示（由于圖中當前算法實例無輸入?yún)?shù)，圖中下部參數(shù)信息框顯示為空白）。三維模型管理工具的一個運行實例如圖7所示，其中右上角小圖表示ESB\\clusters\\RectangularCubic Prism\\Machined Blocks類別下HMJ.stl的預(yù)覽。三維模型搜索工具的一個運行實例如圖8所示，其中左上角小圖表示以ESB\\clusters\\RectangularCubic Prism\\Machined Blocks類別下HMJ.stl作為查詢模型的搜索結(jié)果。

5 結(jié)束語

模型搜索通用支撐平臺是三維模型搜索研究領(lǐng)域的重要工具。在本文提出并實現(xiàn)的支撐平臺下，研究人員只要將自己的算法封裝為動態(tài)鏈接庫形式的組件，并置于平臺的算法邏輯層；然后使用算法組合配置工具設(shè)置自己的算法，就可以滿足算法組合動態(tài)配置以及算法對比驗證的需求，使研究人員專注于搜索算法的研究；同時在本平臺的支持下，可以實現(xiàn)對模型搜索相關(guān)數(shù)據(jù)的規(guī)范管理。本平臺下一步的工作將在現(xiàn)有基礎(chǔ)上繼續(xù)擴展，增加對用戶相關(guān)性反饋研究的支持。

參考文獻：

［1］

FUNKHOUSER T， MIN P， KAZHDAN M，et al.A search engine for 3D models[J].ACM Trans on Graphics，2003，22(1):83105.

［2］陳明著，李華.基于網(wǎng)格的3D搜索引擎系統(tǒng)[J].計算機工程，2003 ，32（15）：255257.

［3］王永睿.三維模型檢索實驗引擎系統(tǒng)和算法的設(shè)計[D].北京：中國科學院計算技術(shù)研究所，2005.

［4］ELMEHALAWI M， MILLER R A.A database system of mechanical components based on geometric and topological similarity，part I:representation[J].ComputerAided Design，2003，35(1):8394.

［5］ELMEHALAWI M， MILLER R A.A database system of mechanical components based on geometric and topological similarity，part II: indexing， retrieval， matching， and similarity assessment[J].ComputerAided Design，2003，35(1):95105.

［6］IYER N， KALYANARAMAN Y， LOU Kuiyang，et al.A reconfigurable 3D engineering shape search system，part I:shape representation[C]//Proc of ASME DETC’03 Computers and Information in Engineering (CIE) Conference.2003.

［7］LOU Kuiyang， JAYANTI S， IYER N，et al.A reconfigurable 3D engineering shape search system part II:database indexing， retrieval and clustering[C]//Proc of ASME DETC’03 Computers and Information in Engineering (CIE) Conference.2003.

［8］Princeton Shape Retrieval and Analysis Group[EB/OL].(20050315)[20080111].http://shape.cs.princeton.edu/benchmark/download.cgi?file=download/psb_util.zip.

[9]AIM@SHAPE[EB/OL].(20071018)[20080111].http://www.aimatshape.net/resources.

[10]JAYANTI S，KALYANARAMAN Y，IYER N，et al.Developing an engineering shape benchmark for CAD models[J].ComputerAided Design，2006，38(9):939953.

［11］ Purdue Research and Education Center for Information Sciences in Engineering (PRECISE)[EB/OL].[20080111].http://shapelab.ecn.purdue.edu/Benchmark.aspx.

［12］尹善華.對象模式與關(guān)系數(shù)據(jù)模式的映射研究[D].長沙：中南大學， 2007.

［13］VRANIC D V.3D model retrieval[D]. Leipzig : Universitt Leipzig，2004.

［14］IYER N，JAYANTI S，LOU Kuiyang，et al.Threedimensional shape searching: stateoftheart review and future trends[J].ComputerAided Design，2005，37(5): 509530.

［15］Kitware Inc[EB/OL].[20080111].http://www.vtk.org.