基于形狀分布式模型檢索的農機裝備快速設計方法

劉洪豪 張開興，2 盧 山 劉賢喜，3

(1.山東農業大學機械與電子工程學院，泰安271018;2.山東省農業裝備智能化工程實驗室，泰安271018;3.山東省園藝機械與裝備重點實驗室，泰安271018)

0 引言

模型檢索是一種重要的設計重用方法［1］，可有效促進機械裝備實現快速化設計。現階段基于三維模型的產品設計與制造已成為我國制造業主流模式［2］，研究表明，包括農業機械領域在內的三維模型數量每年以指數方式增長［3］。面對數量與日俱增、種類日新月異的三維模型，快速有效提取模型特征、并實現三維模型相似性檢索已成為制約設計重用技術［4］的關鍵。三維模型檢索方法可分為:形態特征統計法、視圖投影法以及函數變換法，3 類方法側重點不同，但均不同程度提高了三維模型檢索效果。面向工程應用的模型檢索方法需盡可能穩定、高效，其中形狀分布法能夠集魯棒性、簡單易用性于一體，是一種通用、高效的模型檢索算法。

形狀分布算法本質上是一種概率統計方法［5］，該方法以特征點之間距離、角度、面積等特征為樣本，經過概率統計分析，最終以特征頻率分布直方圖作為模型的特征表示形式。ANKERST 等［6］提出了一種基于形狀直方圖特征的空間模型分類方法;OSADA 等［7］成功將5 種形狀分布函數應用于三維模型特征提取;LIN 等［8］對D1、D2、D3 等形狀分布函數的分辨率、不變性、魯棒性進行了多元化測試評估;模型表面采樣點的均勻性影響三維模型特征提取效果，基于此SHIH 等［9］提出一種GD2 形狀分布算法，該方法將三維模型體素化分解，使用體素單元替代隨機采樣點，提高了分布函數的分辨能力;張開興等［10］提出了一種基于距離-夾角的形狀分布算法，實驗證明該方法的特征代表性優于傳統形狀分布算法。形狀分布算法無需對三維模型進行旋轉歸一化處理，具有剛體變換與反射變換不變性［11］。

三維CAD 模型形態結構逐漸復雜多樣，單一形式的形狀特征無法綜合反映三維模型主要特征。此外，傳統的形狀分布法生成特征點概率與模型表面網格面積存在不對稱性，即網格面積越大，生成特征點概率越高，但三維模型結構形態變化主要由小面積網格表示，因此傳統特征點采樣無法反映模型細節特征。本文對形狀分布算法的特征點采樣規則以及多特征融合方式進行改進，提出一種自適應動態加權的形狀分布模型檢索算法，以促進機械裝備三維模型檢索與設計重用。

1 形狀分布特征提取原理

形狀分布函數本質上是一個概率分布函數，以形狀特征分布作為三維模型的特征描述符，可以將復雜的三維模型間相似性度量問題轉換為概率分布匹配。理論上，任何有關三維模型的特征函數均可通過樣本采樣形成特征描述符，例如:模型表面紋理特征、表面隨機點間距離、顏色特征、材質屬性等。在三維模型特征函數中，通過形狀特征函數提取的模型特征描述符最為有效，圖1 為常用的6 種形狀分布函數，表1 為對應形狀分布函數的屬性特征。

圖1 常用形狀分布函數特征示意圖Fig.1 Illustrations of frequently used shape distribution feature

表1 形狀分布函數屬性Tab.1 Property of shape distribution function

對于三維模型，位置方向變動引起的特征提取偏差是影響三維模型相似性匹配的主要因素，且在三維模型歸一化變換過程中，旋轉歸一化處理最為復雜。圖1 所示6 種形狀分布均通過采樣點間特征函數計算獲得，6 種形狀特征提取描述符均具有旋轉不變性，其中角度A3 形狀分布函數不僅具有旋轉不變性，而且尺度不變，特征提取效果不受三維模型縮放、旋轉的影響。此外，形狀分布法是一種通用模型特征提取方法，適用于任何由三角網格表示的三維模型，非三角網格模型經過轉換后同樣適用。

2 動態加權融合形狀分布特征

2.1 組合式特征點采樣

現階段模型表面特征點采樣概率多與網格面積相關，而三維模型的特征細節主要是由一系列微小網格表示，模型特征與特征采樣概率間不對稱性降低了特征提取的區分度，因此使用組合分類排序法對特征點采樣方式進行改進。

(1)模型預處理

設三維模型經過三角網格化后頂點集合為V={v1，v2，…，vn}，其中vi=(xi，yi，zi)為網格頂點，則三維模型中心點為

式中 n——模型頂點總數量

將模型中心點平移至坐標原點，完成平移歸一化，計算模型中各頂點到中心點的最大距離，采用最大半徑縮放法［12］，對三維模型進行尺度歸一化處理

式中 M——歸一化前模型

Ms——歸一化后模型

dis(vi，Vm)——頂點vi與中心點Vm之間的歐氏距離

由于形狀分布算法具有旋轉不變性，三維模型無需復雜的旋轉變換處理，在預處理過程中三維模型頂點集合均以矩陣形式存儲。

(2)網格分類組合

圖2 為驅動橋萬向節模型網格分類組合過程，首先遍歷模型全部網格頂點，根據Heron 公式計算網格面積，設三角網格頂點為(vi，vj，vk)，則其面積計算公式為

其中

式中 L——三角網格周長一半

SΔijk——三角網格面積

然后存儲網格面積及位置信息，根據面積對全部三角網格排序，對于排序后的網格有兩種分類方法:網格數量分類與面積分類。模型典型細節特征由一系列面積較小的三角網格表示，數量分類法無法體現網格面積區分度，因此根據面積分類法將三角網格分為Max(Ⅰ類)、Mid(Ⅱ類)、Min(Ⅲ類)。

圖2 模型三角網格分類與組合Fig.2 Classification and combination of model triangular mesh

網格分類后，不同類別依次交叉組合取點，計算網格表面采樣點間形狀特征。由于不同類別間網格位置及面積差異性增大，從而提高了模型提取特征的分辨力與區分度。

(3)準隨機序列

生成隨機點是完成網格采樣的關鍵步驟，計算機無法產生絕對均勻分布的隨機數，傳統的偽隨機數序列均勻性較差，而準隨機序列分布更加均勻，常用的準隨機性序列包括Halton 序列、Sobol 序列、Latin 超立方序列等［13］，其中Sobol 序列具有較好的計算精度與計算效率［14］，因此采用Sobol 準隨機序列對分類后的三角網格采樣。

Sobol 序列主要由一組方向數vt構成，其中vt=mt/2t，構造步驟如下［15］:首先，生成系數c 為0 或1的原始多項式

然后根據遞推公式計算

式中，t ＞p，mt為小于2t的正奇數，⊕表示二進制按位異或運算。

對于任何一個十進制整數y，能夠唯一表示為與數基b=2 有關的表達式

式中，aj系數為0 或1，k 為大于等于lby 的最小整數。

Sobol 序列的第z 個元素可表示為

圖3 為Matlab 中偽隨機序列與Sobol 準隨機序列二維分布，準隨機序列分布更加均勻。

圖3 隨機序列數二維分布Fig.3 Distributions of random sequences

根據準隨機序列選定不同類別集合中三角網格，以三角網格重心為采樣點，完成模型特征點采樣。

2.2 自適應特征融合

特征融合可有效彌補單一特征代表性不足的缺點，現階段的形狀分布算法種類多樣、功能專一、效率不同，對典型形狀分布特征進行有機融合，不同形狀分布特征優勢互補，從而提高模型特征代表性與區分度。

(1)形狀分布函數融合

特征融合需盡可能融合多種類別形狀特征，但同時兼顧效率因素。由表1 可知，單個D3、A3、C1形狀特征樣本需要3 個采樣點，D2 特征與D1 特征同為距離特征且均需要2 個采樣點，體積特征D4需要4 個采樣點。此外，形狀特征采樣具有向下兼容性，即高頻采樣可滿足低頻采樣特征提取需求，因此，3 采樣點作為采樣基本單位的特征提取效率最高。圖4 為單位采樣點數為3 的融合采樣特征，本文對距離D2、面積D3、曲率C1、角度A3 形狀特征進行融合，實現三維模型線與面、內部與表面、距離與曲率綜合特征提取。

圖4 融合特征采樣Fig.4 Fusion feature sample

(2)自適應動態加權

對于不同類型的三維模型，每種形狀分布函數的表現能力不同，為最大限度突出模型主形狀特征并體現次要特征，需計算不同形狀函數權重。常用的加權方法可分為固定權值法與動態加權法［16］，動態加權法更適合數值波動較大的變量，本文基于變異系數采用動態加權法確定形狀函數權重。

變異系數可以度量變量的離散程度［17］，在評價模型融合特征體系中，特征變量幅值變化范圍越大，越能反映模型主特征，因此變異系數能夠度量不同特征變量權重，其計算式為

式中 Vj——第j 項特征的變異系數

xi——j 特征的第i 個樣本值

Xj——j 特征的樣本均值

s——樣本總數

特征權重為

式中 Wj——第j 項特征權重

m——融合特征總數

將各形狀分布特征變量值歸一化，然后根據各形狀特征權重，按照D2、D3、C1、A3 順序將不同特征變量拼接成具有多特征的形狀分布直方圖，從而完成自適應加權融合特征(Adaptive weighted shape distribution，AWSD)提取。

(3)相似性度量

為實現模型庫中不同模型相似性檢索，需要根據形狀分布直方圖計算模型間相似性。距離比較是度量模型相似性的典型方法，主要包括Euclidean 距離、Manhattan 距離、Hausdorff 距離等［18］，本文采用χ2距離［19］，計算式為

式中 histA、histB——模型MA和MB直方圖

histA(i)、histB(i)——直方圖第i 個特征分量頻次

S——直方圖特征分量總數

三維模型相似度計算式為

式中 Dmax、Dmin——模型MA與所有參與比較的模

型間距離最大值、最小值

3 實驗與討論

3.1 實驗數據集

選用ESB 模型庫［20］與農業機械裝備CAD 模型庫作為三維模型實驗數據集，其中ESB 數據集由美國普渡大學設計開發，包括薄壁、棱柱、回轉體3 大類共計867 個模型;農機模型庫根據國家重點研發計劃項目“農機裝備智能化設計技術研究”構建，主要以聯合收獲機與拖拉機CAD 模型為主，共包含9大類、23 小類共計2 166 個模型，部分三維模型如圖5 所示。

圖5 三維模型庫節選Fig.5 Part of 3D model database

3.2 評價標準

采用國際通用標準對模型檢索效果進行評價，主要包括6 類指標:

(1)查準率(Precision)與查全率(Recall)計算式為

式中 RA——檢索返回結果中與待檢索模型相關的模型數量

RB——與待檢索模型無關的模型數量

NA——整個模型庫中與待檢索模型相關但未檢索到的模型數量

(2)E 測度計算式為

式中 e——查準率P 與查全率R 相關程度，通常取0.5 或1

(3)平均查準率(MAP)計算式為

式中 Nq——待檢索模型數量總和

Ari——第i 個檢索返回結果中正確相關模型數量

Nri，j——返回結果中截至前j 個相關模型出現時模型數量

(4)最近鄰精度(NN)計算式為

式中 N——檢索精度參數，即檢索返回N 項數量

Rn——返回前N 項中正確相關模型數量，通常采用第一最近鄰精度(N=1)指標

(5)FT 與ST 測度

模型庫中與待檢索模型同類模型數量為C，則FT 與ST 分別為前C -1、2(C -1)個檢索結果的查全率。

(6)排序累積增益(DCG)計算式為

式中 p——檢索返回模型總量

r(i)——第i 個模型的相關性評分

3.3 結果與分析

實驗設備配置環境為Windows 10 操作系統，處理器Intel Core i7-6500U(2.5 GHz)，內存8.0 GB，以VS2010 與Matlab 2016b 為開發環境，以Open Cascade 為幾何造型平臺。表2 為部分典型模型的特征提取結果，由表2 可知，圓盤耙模型距離D2 頻率先增大后減小，撥禾輪模型距離D2 頻率增大后保持，到達峰值后陡然減小，D2 形狀特征隨模型形狀差異而變化，基本能夠反映模型主要特征。表2中發動機模型與圓盤耙模型在幾何形態方面顯著不同，而發動機距離D2 頻率特征與圓盤耙特征相似，這主要因為發動機模型較為復雜，距離D2 特征趨于正態分布，從而降低了特征的區分度與代表性［21］，由此表明單一形狀分布特征的區分度有限。

表2 模型特征分布圖Tab.2 Model charateristic distribution

表2 同時顯示了本文提出的AWSD 融合特征，其中圓盤耙模型融合特征權重為0.25、0.23、0.33、0.19，撥禾輪模型權重為0.28、0.21、0.28、0.23，發動機模型特征權重則為0.23、0.19、0.23、0.35。圓盤耙與發動機模型的D2 特征相似，AWSD 特征具有明顯差異，其主要體現在形狀特征波峰與波谷變化趨勢以及峰值大小上，圓盤耙模型在第3 個波峰時取最大值，撥禾輪模型的4 個波峰值近似，而發動機模型特征最大值體現在第4 個波峰上。融合特征最大峰值即各組成特征最大權重，而特征權重由模型各特征差異性決定，通過自適應加權方式，AWSD融合特征能夠有效弱化低區分度特征，突出模型特征差異性，提高模型特征分辨率。

為確定不同形狀特征提取方法應用效果，選取拖拉機轉向器、變速箱、輪胎3 類，玉米聯合收獲機摘穗輥、押送器2 類進行檢索實驗，以5 類模型平均查全率為X 軸、以平均查準率為Y 軸，繪制查準率-查全率曲線如圖6 所示。理想的查準率-查全率曲線是縱坐標為1 的水平直線，實際以查準率-查全率曲線與X-Y 軸包圍面積即查準率-查全率指數作為檢索效果評價依據，查準率-查全率指數數值與檢索效果正相關。由圖6 可知，特征檢索查準率由大到小依次為D2、C1、A3、D3 特征，本文提出的AWSD融合算法在查全率為0 ～0.5 區間內顯著優于D2特征，在0.5 ～1.0 區間內檢索效果與D2 特征近似。表3 進一步顯示了不同方法的檢索評價參數，AWSD特征各項指標優于其他形狀分布算法，綜合檢索精度較D2 形狀分布算法提高了8.5%。

圖6 查準率-查全率曲線Fig.6 Recall-precision curves

表3 農機模型檢索效果Tab.3 Retrieval performance metrics

表4 給出了不同方法檢索所需時間，由表4 可知，相對于單一特征提出方法，AWSD 特征融合方法特征提取時間、特征匹配時間不同程度增加，其平均檢索時間為6.439 2 s，模型檢索效率略有降低。綜上可知，本文提出的AWSD 模型特征提取方法的檢索精度與準確度均得到提高，檢索效率符合要求。

表4 模型檢索所需時間Tab.4 Retrieval efficiency performance

3.4 應用實例

表5 為拖拉機輪轂CAD 模型檢索結果，拖拉機輪轂的曲面特征最典型，因此選用曲率C1 形狀分布算法與本文提出的AWSD 算法比較，距離D2 分布算法作為對照。由表5 可知，3 種算法均能夠檢索出同一類的6 個輪轂模型，視覺主觀上可以觀察出曲率C1 算法與AWSD 算法檢索效果優于距離D2 算法，由此表明本文提出的AWSD 算法適用性較高，在檢索主觀滿意度方面與專一特征檢索算法近似。

摘穗板是玉米收獲機割臺的重要零部件［22］，不同于拖拉機輪轂大類零件，常用摘穗板結構約10 種，表6 為模型庫中摘穗板CAD 模型檢索結果，其中與輸入模型同一類的模型標記為黃色，非同類模型標記為灰色。由表6 可知，C1、D2 算法檢索出4 種同類模型，而AWSD 算法能夠檢索出6 種，數量上AWSD 算法性能優于C1、D2 算法;輸入的摘穗板模型含2 個方形槽，與其最相似的模型同樣應為方形槽，但D2 算法首先返回U 型槽摘穗板，這可能由采樣點隨機性導致，此外距離D2 特征分辨率過低也將導致該現象發生。對檢索后的模型進行簡單尺寸、顏色編輯后即可設計重用，圖7、8 為使用檢索出CAD 模型進行快速設計的割臺裝配體。

表5 拖拉機輪轂CAD 模型檢索結果Tab.5 Retrieval results of tractor wheel hub model

表6 收獲機摘穗板CAD 模型檢索結果Tab.6 Retrieval results of harvester picking board model

圖7 玉米收獲機割臺Fig.7 Assemblies of corn harvester header

4 結論

(1)基于模型檢索方式的設計重用方法將模型再設計問題轉換為相關模型搜索，在模型數據庫完備的情況下可有效降低設計成本、縮短設計周期。

圖8 玉米收獲機割臺局部Fig.8 Partial assemblies of corn harvester header

(2)單一形式的形狀分布特征提取效果有限，通過計算特征值變異系數確定多特征動態權重，從而實現距離D2、面積D3、曲率C1、角度A3 多特征有機融合，融合后的特征不僅能夠體現模型線與面、內部與表面、距離與曲率綜合特征，而且能夠有效弱化低區分度特征，突出模型特征的差異性，提高模型特征分辨率。

(3)提出的基于形狀分布的AWSD 模型檢索方法能夠保持形狀分布算法原有高穩定性的優點，對農機裝備關鍵零部件模型庫具有較高適用性，其綜合檢索精度較D2 形狀分布算法提高了8.5%。