[發(fā)明專利]一種基于集群計算系統(tǒng)的三維模型庫特征提取方法

無效

• 申請?zhí)枺?/td>: 200810235434.4
• 申請日: 2008-12-02
• 公開（公告）號: CN101441579A
• 公開（公告）日: 2009-05-27
• 發(fā)明（設計）人: 楊育彬;林金杰;阮佳彬
• 申請（專利權）人: 南京大學
• 主分類號: G06F9/50
• 分類號: G06F9/50;G06F17/30
• 代理公司: 南京蘇高專利商標事務所(普通合伙）
• 代理人: 肖明芳

技術領域

本發(fā)明屬于計算機應用技術領域，涉及的是一種在集群計算系統(tǒng)下的三維模型庫特征提取方法。

背景技術

隨著計算機圖形學的發(fā)展、三維模型獲取技術和圖形硬件技術的提高，如今三維模型已成為繼聲音、圖像和視頻之后的第四種多媒體數(shù)據(jù)類型。近年來，三維物體的數(shù)據(jù)量飛速增長，如三維游戲素材庫、工業(yè)機械零件庫、藥物分子模型庫、地形地貌數(shù)據(jù)庫等三維模型庫不斷地被擴充或應用。另一方面，三維模型檢索技術的應用目前已滲透到軍事、生產(chǎn)和生活等領域的各個方面，如虛擬現(xiàn)實、醫(yī)藥分子研究、戰(zhàn)爭仿真模擬、教育軍事訓練、三維游戲、影視動畫、工業(yè)產(chǎn)品設計、機械制造以及電子商務等。因此，如何對海量的三維數(shù)據(jù)庫實現(xiàn)快速和準確的檢索現(xiàn)在已成為多媒體信息檢索領域的一個研究熱點，并且具有巨大的經(jīng)濟價值和重要的現(xiàn)實意義。基于內容的三維模型檢索的本質是利用反映三維模型視覺特征的信息自動建立特征索引，從而達到檢索三維模型的目的。通常一個三維模型數(shù)據(jù)庫所包含的三維模型數(shù)量相當龐大，而特征提取的過程又是一個耗時較大的操作(目前在配置為Pentium(R)43.00GHz?CPU，1G?RAM的計算機上處理時間一個三維模型的時間大都需要超過1秒)，因此，采用普通的單機系統(tǒng)來實現(xiàn)對整個三維模型庫的特征提取將是一項計算時間非常漫長的過程。

發(fā)明內容

本發(fā)明所要解決的技術問題是提供一種基于集群計算系統(tǒng)的三維模型庫特征提取方法，以縮減整個特征提取過程的處理時間。

為解決上述技術問題，本發(fā)明采用的技術方案如下：

一種基于集群計算系統(tǒng)的三維模型庫特征提取方法，包括以下步驟：

(1)操作員按照本發(fā)明所設計的任務說明書(包含對所要提取的三維模型文件的存儲地址、每個三維模型的數(shù)據(jù)量、總的文件個數(shù)等信息的描述)提交整個計算任務；

(2)對計算任務的規(guī)模進行評估，評估的方法是：假設提交的三維模型數(shù)據(jù)庫一共包含N個三維模型，每個三維模型文件的數(shù)據(jù)量分別是m₁，m₂，...，m_N，則總的計算規(guī)模估計為

(3)依據(jù)集群系統(tǒng)中可使用的計算節(jié)點個數(shù)和計算任務的規(guī)模S為每一個計算節(jié)點分配計算任務。假設集群系統(tǒng)當前可用的計算節(jié)點個數(shù)為K，則理想狀態(tài)下每一個計算節(jié)點的計算任務量為S/K，但由于特征提取算法的基本處理單位是單個三維模型文件，而當i≠j時未必有m_i＝m_j，因此，每一個計算節(jié)點所應處理的三維模型文件數(shù)未必是N/K，本發(fā)明采用如下的方法來實現(xiàn)依據(jù)計算規(guī)模為計算節(jié)點分配計算任務：

(a)對所有三維模型按照其數(shù)據(jù)量的大小從小到大排序，假設得到排序結果為m’₁＜m’₂＜，...，＜m’_N；

(b)為每一個計算節(jié)點分配一個變量S₁，S₂，...，S_K，全部初始化為0；

(c)對于每一個計算節(jié)點，循環(huán)地從排序表m’₁＜m’₂＜，...，＜m’_N中取出三維模型作為該節(jié)點需要處理的數(shù)據(jù)。每次都取表中數(shù)據(jù)量最小的那個三維模型，被取過的三維模型將從排序表中去除，同時計算節(jié)點i所對應的變量S_i需要加上它所取的三維模型的大小；

(d)在步驟(c)的過程中，為計算節(jié)點i取得一個三維模型后，都檢測到目前為止它所得到的計算任務總規(guī)模S_i是否超過S/K，如超過則計算節(jié)點i不再參與分配。

(4)依據(jù)步驟(3)得到的分配結果，按照本發(fā)明制定的通信協(xié)議將三維模型文件發(fā)送給各個計算子節(jié)點。具體的通信協(xié)議如下：集群系統(tǒng)的頭節(jié)點向計算節(jié)點i發(fā)送三維模型文件按照如下的過程進行：

(a)頭節(jié)點向計算節(jié)點i發(fā)出信號“DATA_START，節(jié)點編號，文件數(shù)FilesNum”；

(b)計算節(jié)點i收到信號后將接收文件數(shù)計數(shù)器Counter設為FilesNum，然后回發(fā)信號“DATA_READY，節(jié)點編號”給頭節(jié)點，說明本節(jié)點準備好接收數(shù)據(jù)；

(c)頭節(jié)點收到計算節(jié)點i發(fā)來的信號后，按照(3)得到的分配結果，將三維模型文件逐個發(fā)送給計算節(jié)點i；

(d)計算節(jié)點i逐個接收三維模型文件。每次收到一個文件后都將Counter自減1，當發(fā)現(xiàn)Counter為0時，發(fā)送信號“DATA_END，節(jié)點編號”給頭節(jié)點；