基于形狀分布式模型檢索的農(nóng)機(jī)裝備快速設(shè)計(jì)方法

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

(1.山東農(nóng)業(yè)大學(xué)機(jī)械與電子工程學(xué)院，泰安271018;2.山東省農(nóng)業(yè)裝備智能化工程實(shí)驗(yàn)室，泰安271018;3.山東省園藝機(jī)械與裝備重點(diǎn)實(shí)驗(yàn)室，泰安271018)

0 引言

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

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

三維CAD 模型形態(tài)結(jié)構(gòu)逐漸復(fù)雜多樣，單一形式的形狀特征無法綜合反映三維模型主要特征。此外，傳統(tǒng)的形狀分布法生成特征點(diǎn)概率與模型表面網(wǎng)格面積存在不對稱性，即網(wǎng)格面積越大，生成特征點(diǎn)概率越高，但三維模型結(jié)構(gòu)形態(tài)變化主要由小面積網(wǎng)格表示，因此傳統(tǒng)特征點(diǎn)采樣無法反映模型細(xì)節(jié)特征。本文對形狀分布算法的特征點(diǎn)采樣規(guī)則以及多特征融合方式進(jìn)行改進(jìn)，提出一種自適應(yīng)動(dòng)態(tài)加權(quán)的形狀分布模型檢索算法，以促進(jìn)機(jī)械裝備三維模型檢索與設(shè)計(jì)重用。

1 形狀分布特征提取原理

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

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

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

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

2 動(dòng)態(tài)加權(quán)融合形狀分布特征

2.1 組合式特征點(diǎn)采樣

現(xiàn)階段模型表面特征點(diǎn)采樣概率多與網(wǎng)格面積相關(guān)，而三維模型的特征細(xì)節(jié)主要是由一系列微小網(wǎng)格表示，模型特征與特征采樣概率間不對稱性降低了特征提取的區(qū)分度，因此使用組合分類排序法對特征點(diǎn)采樣方式進(jìn)行改進(jìn)。

(1)模型預(yù)處理

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

式中 n——模型頂點(diǎn)總數(shù)量

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

式中 M——?dú)w一化前模型

Ms——?dú)w一化后模型

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

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

(2)網(wǎng)格分類組合

圖2 為驅(qū)動(dòng)橋萬向節(jié)模型網(wǎng)格分類組合過程，首先遍歷模型全部網(wǎng)格頂點(diǎn)，根據(jù)Heron 公式計(jì)算網(wǎng)格面積，設(shè)三角網(wǎng)格頂點(diǎn)為(vi，vj，vk)，則其面積計(jì)算公式為

其中

式中 L——三角網(wǎng)格周長一半

SΔijk——三角網(wǎng)格面積

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

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

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

(3)準(zhǔn)隨機(jī)序列

生成隨機(jī)點(diǎn)是完成網(wǎng)格采樣的關(guān)鍵步驟，計(jì)算機(jī)無法產(chǎn)生絕對均勻分布的隨機(jī)數(shù)，傳統(tǒng)的偽隨機(jī)數(shù)序列均勻性較差，而準(zhǔn)隨機(jī)序列分布更加均勻，常用的準(zhǔn)隨機(jī)性序列包括Halton 序列、Sobol 序列、Latin 超立方序列等［13］，其中Sobol 序列具有較好的計(jì)算精度與計(jì)算效率［14］，因此采用Sobol 準(zhǔn)隨機(jī)序列對分類后的三角網(wǎng)格采樣。

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

然后根據(jù)遞推公式計(jì)算

式中，t ＞p，mt為小于2t的正奇數(shù)，⊕表示二進(jìn)制按位異或運(yùn)算。

對于任何一個(gè)十進(jìn)制整數(shù)y，能夠唯一表示為與數(shù)基b=2 有關(guān)的表達(dá)式

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

Sobol 序列的第z 個(gè)元素可表示為

圖3 為Matlab 中偽隨機(jī)序列與Sobol 準(zhǔn)隨機(jī)序列二維分布，準(zhǔn)隨機(jī)序列分布更加均勻。

圖3 隨機(jī)序列數(shù)二維分布Fig.3 Distributions of random sequences

根據(jù)準(zhǔn)隨機(jī)序列選定不同類別集合中三角網(wǎng)格，以三角網(wǎng)格重心為采樣點(diǎn)，完成模型特征點(diǎn)采樣。

2.2 自適應(yīng)特征融合

特征融合可有效彌補(bǔ)單一特征代表性不足的缺點(diǎn)，現(xiàn)階段的形狀分布算法種類多樣、功能專一、效率不同，對典型形狀分布特征進(jìn)行有機(jī)融合，不同形狀分布特征優(yōu)勢互補(bǔ)，從而提高模型特征代表性與區(qū)分度。

(1)形狀分布函數(shù)融合

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

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

(2)自適應(yīng)動(dòng)態(tài)加權(quán)

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

變異系數(shù)可以度量變量的離散程度［17］，在評(píng)價(jià)模型融合特征體系中，特征變量幅值變化范圍越大，越能反映模型主特征，因此變異系數(shù)能夠度量不同特征變量權(quán)重，其計(jì)算式為

式中 Vj——第j 項(xiàng)特征的變異系數(shù)

xi——j 特征的第i 個(gè)樣本值

Xj——j 特征的樣本均值

s——樣本總數(shù)

特征權(quán)重為

式中 Wj——第j 項(xiàng)特征權(quán)重

m——融合特征總數(shù)

將各形狀分布特征變量值歸一化，然后根據(jù)各形狀特征權(quán)重，按照D2、D3、C1、A3 順序?qū)⒉煌卣髯兞科唇映删哂卸嗵卣鞯男螤罘植贾狈綀D，從而完成自適應(yīng)加權(quán)融合特征(Adaptive weighted shape distribution，AWSD)提取。

(3)相似性度量

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

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

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

S——直方圖特征分量總數(shù)

三維模型相似度計(jì)算式為

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

型間距離最大值、最小值

3 實(shí)驗(yàn)與討論

3.1 實(shí)驗(yàn)數(shù)據(jù)集

選用ESB 模型庫［20］與農(nóng)業(yè)機(jī)械裝備CAD 模型庫作為三維模型實(shí)驗(yàn)數(shù)據(jù)集，其中ESB 數(shù)據(jù)集由美國普渡大學(xué)設(shè)計(jì)開發(fā)，包括薄壁、棱柱、回轉(zhuǎn)體3 大類共計(jì)867 個(gè)模型;農(nóng)機(jī)模型庫根據(jù)國家重點(diǎn)研發(fā)計(jì)劃項(xiàng)目“農(nóng)機(jī)裝備智能化設(shè)計(jì)技術(shù)研究”構(gòu)建，主要以聯(lián)合收獲機(jī)與拖拉機(jī)CAD 模型為主，共包含9大類、23 小類共計(jì)2 166 個(gè)模型，部分三維模型如圖5 所示。

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

3.2 評(píng)價(jià)標(biāo)準(zhǔn)

采用國際通用標(biāo)準(zhǔn)對模型檢索效果進(jìn)行評(píng)價(jià)，主要包括6 類指標(biāo):

(1)查準(zhǔn)率(Precision)與查全率(Recall)計(jì)算式為

式中 RA——檢索返回結(jié)果中與待檢索模型相關(guān)的模型數(shù)量

RB——與待檢索模型無關(guān)的模型數(shù)量

NA——整個(gè)模型庫中與待檢索模型相關(guān)但未檢索到的模型數(shù)量

(2)E 測度計(jì)算式為

式中 e——查準(zhǔn)率P 與查全率R 相關(guān)程度，通常取0.5 或1

(3)平均查準(zhǔn)率(MAP)計(jì)算式為

式中 Nq——待檢索模型數(shù)量總和

Ari——第i 個(gè)檢索返回結(jié)果中正確相關(guān)模型數(shù)量

Nri，j——返回結(jié)果中截至前j 個(gè)相關(guān)模型出現(xiàn)時(shí)模型數(shù)量

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

式中 N——檢索精度參數(shù)，即檢索返回N 項(xiàng)數(shù)量

Rn——返回前N 項(xiàng)中正確相關(guān)模型數(shù)量，通常采用第一最近鄰精度(N=1)指標(biāo)

(5)FT 與ST 測度

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

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

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

r(i)——第i 個(gè)模型的相關(guān)性評(píng)分

3.3 結(jié)果與分析

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

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

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

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

圖6 查準(zhǔn)率-查全率曲線Fig.6 Recall-precision curves

表3 農(nóng)機(jī)模型檢索效果Tab.3 Retrieval performance metrics

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

表4 模型檢索所需時(shí)間Tab.4 Retrieval efficiency performance

3.4 應(yīng)用實(shí)例

表5 為拖拉機(jī)輪轂CAD 模型檢索結(jié)果，拖拉機(jī)輪轂的曲面特征最典型，因此選用曲率C1 形狀分布算法與本文提出的AWSD 算法比較，距離D2 分布算法作為對照。由表5 可知，3 種算法均能夠檢索出同一類的6 個(gè)輪轂?zāi)Ｐ停曈X主觀上可以觀察出曲率C1 算法與AWSD 算法檢索效果優(yōu)于距離D2 算法，由此表明本文提出的AWSD 算法適用性較高，在檢索主觀滿意度方面與專一特征檢索算法近似。

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

表5 拖拉機(jī)輪轂CAD 模型檢索結(jié)果Tab.5 Retrieval results of tractor wheel hub model

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

圖7 玉米收獲機(jī)割臺(tái)Fig.7 Assemblies of corn harvester header

4 結(jié)論

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

圖8 玉米收獲機(jī)割臺(tái)局部Fig.8 Partial assemblies of corn harvester header

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

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