朱文博 王朝 陳龍

摘 要：為實現(xiàn)資源重復(fù)利用與產(chǎn)品創(chuàng)新，通過檢索出數(shù)據(jù)庫中的相似零件為設(shè)計者提供幫助。首先對機械零件模型進行方位歸一化與預(yù)處理，以起始點為圓心作最大內(nèi)切圓，劃分連通區(qū)，在連通區(qū)內(nèi)根據(jù)距離變換值判定鄰域像素，進而確定新的骨架點，迭代生成完整骨架。將骨架轉(zhuǎn)換成直方圖曲線，劃分網(wǎng)格生成骨架點數(shù)矩陣，根據(jù)矩陣特征值和之間的差計算兩模型間的差異度，從而判定機械零件相似度。通過實例驗證以及與D2形狀分布算法及遞歸分割算法比較，發(fā)現(xiàn)該方法檢索速度高于遞歸分割算法，準確性高于D2形狀分布算法和遞歸分割算法。

關(guān)鍵詞：機械零件;模型檢索;骨架提取;距離變換;直方圖;差異度

DOI：10. 11907/rjdk. 192110 開放科學(xué)（資源服務(wù)）標識碼（OSID）：

中圖分類號：TP319文獻標識碼：A 文章編號：1672-7800（2020）005-0107-05

0 引言

隨著企業(yè)的發(fā)展與信息數(shù)字化應(yīng)用的逐步深入，零件生產(chǎn)與創(chuàng)新可從許多現(xiàn)有零件模型中獲取靈感，并在原有基礎(chǔ)上進行部分創(chuàng)新，以重用企業(yè)資源，避免重復(fù)勞動。因此，如何在眾多現(xiàn)有案例中快速、準確地找出所需零件，是目前亟待解決的問題，很多學(xué)者也對該問題進行了大量研究。如Liu等[1]提出基于視圖的三維模型檢索方法，該方法利用聚類對模型進行視圖提取，采用游走算法對每個代表視圖進行權(quán)重更新，通過圖匹配解決模型相似性度量問題，但檢索過程較為復(fù)雜;Zhang等[2]提出從模型外部輪廓和內(nèi)在結(jié)構(gòu)中提取填充描述符，并采用二分圖匹配算法完成模型檢索，但計算量大，實際應(yīng)用有一定困難;Wai等[3]提出基于帶次序的歐氏距離圖提取連接良好的骨架，給出一種連通性準則，可用于獨立確定給定像素是否為骨架點，但提取的骨架冗余分支較多;Cheng等[4-5]將模型分解成集合基本體的樹結(jié)構(gòu)，并根據(jù)不同類別比較兩個模型的相似性，但對于結(jié)構(gòu)復(fù)雜的模型，分解的樹結(jié)構(gòu)將會有不同方案，使得最終的相似度差異較大;萬雅娟等[6]設(shè)計一種由骨架種子點開始對鄰域進行判定選出下一輪預(yù)備骨架點，迭代生長出完整三維模型骨架的提取算法，但提取的骨架不夠簡化，存在多面結(jié)構(gòu);劉玉杰等[7]提出一種基于手繪圖像融合信息嫡與CNN的三維模型檢索方法，先計算得到模型的代表性視圖，再與手繪草圖進行特征匹配，但手繪草圖差異度較大，失誤率高，且模型具有一定局限性。

針對上述方法存在的問題，本文提出的骨架生成方法能夠消除冗余分支骨架，基于距離變換生成機械零件骨架，并運用判定方法迭代生成骨架，保證了骨架的連續(xù)性，且避免了多面結(jié)構(gòu)，有利于后續(xù)相似度計算。骨架檢索過程清晰、簡潔，計算方式簡單，計算量不大，將骨架轉(zhuǎn)換成直方圖曲線，并生成骨架點數(shù)矩陣，計算矩陣特征值和之間的差，隨之得出機械零件三維模型的相似程度。

1 機械零件三維模型預(yù)處理

1.1 模型歸一化及簡化

首先計算出機械零件三維模型的幾何中心，并將該幾何中心作為原點建立坐標系。之后將三維模型用最小凸包圍盒[8]，即最小包圍長方體完全包圍起來，過幾何中心作與最小凸包圍盒最長邊平行的直線，即為X軸;X軸線與最小凸包圍盒兩面交于兩點，比較幾何中心到兩點的距離，距離長的一側(cè)定義為正方向。利用笛卡爾坐標系建立原則，即可確定Y軸和Z軸，完成三維模型的方位歸一化處理，如圖1（a）所示。

在完成模型的方位歸一化后，對機械三維模型上的諸如倒角、倒圓、锪平沉孔等附加特征進行去除。機械模型相似度主要取決于模型主要特征與主干結(jié)構(gòu)[9]，故通過電腦自動過濾掉這些附加特征。模型簡化后如圖1（b）所示。

1.2 投影與像素化處理

將模型分別投影到坐標平面XOZ、平面XOY與平面YOZ上，得到模型的主視圖、俯視圖和左視圖，保留各視圖外輪廓線及所有通孔的圓形視圖，去除其它圖線。如圖2所示為與圖1模型對應(yīng)的處理后投影圖。

隨后對處理后投影圖進行像素化。像素是指由數(shù)字序列表示數(shù)字圖像中的最小單位[10]，根據(jù)投影圖尺寸，選取一個最小包絡(luò)長方形邊框[11]，并在該邊框內(nèi)將圖形劃分為若干個等面積的小正方形。正方形邊長越小，后續(xù)提取出的骨架精度越高，但計算量也隨之增大。綜合考慮精度與計算量之間的關(guān)系，取投影圖長寬中較短邊的1/2 000左右較為適宜。故針對圖1所示模型處理后的投影圖，取邊長為0.1mm進行劃分，如圖3（a）所示為處理后主視圖的像素劃分圖。

1.3 采用距離變換賦值內(nèi)部像素

最小距離值的計算方法采用歐氏距離[12]方法。圖3（b）為圖3（a）圓圈處的局部放大圖，圖中數(shù)字為像素值，填充部分為邊界像素，未填充且標有像素值的方格為內(nèi)部像素。

2 骨架提取算法

本文提取骨架的方法是針對處理后的投影圖，由骨架起始點開始，對其相鄰像素進行判斷，生成新的骨架點并迭代生成骨架。根據(jù)骨架和距離變換的定義[13]，由于骨架中間部位的特征是內(nèi)部像素值較大，且利于骨架向周圍擴散，故本文選擇具有最大值的內(nèi)部像素作為骨架起始點。

利用參考文獻[6]中的方法對模型主視圖的迭代過程如圖4（a）所示，粗實線為骨架。同理，對模型俯、左兩個視圖進行骨架提取，完成所有迭代后，骨架如圖4（b）、（c）所示。

3 相似度計算

通過將骨架表示為二維曲線直方圖，再將曲線圖用矩陣形式予以表現(xiàn)，計算兩個矩陣之間的差異度，并判定兩個機械零件模型之間的相似度。

3.1 骨架直方圖描述

設(shè)骨架起始點為[P0]，骨架點集合為[Pi（i=1，2，？，][K）]，設(shè)[ske（P0，Pi）]為橫坐標，表示從[P0]沿骨架到[Pi]的最短路徑長度[14]，縱坐標[R（Pi）]為[Pi]點的內(nèi)切圓半徑。圖4（a）中完成迭代的主視圖骨架直方圖見圖5（a）。同理可得該模型俯、左兩個視圖的骨架直方圖見圖5（b）、圖5（c）。

3.2 骨架點數(shù)矩陣生成

為了將直方圖轉(zhuǎn)換成骨架點數(shù)矩陣，首先對骨架直方圖進行網(wǎng)格劃分，網(wǎng)格劃分得越密集，矩陣數(shù)據(jù)表示則越細致，但計算量也隨之陡增。綜合考慮計算量與精準度[15]，選取橫向劃分網(wǎng)格數(shù)量在5～15之間，并將每個網(wǎng)格長寬比控制在1～3之間較為合理。按原則劃分后結(jié)果如圖5所示。

生成網(wǎng)格之后，依次計算每個網(wǎng)格中的骨架點數(shù)量，生成骨架點數(shù)矩陣。將網(wǎng)格橫坐標劃分為m等分，縱坐標n等分，每一網(wǎng)格中骨架點數(shù)量記為[hij]，生成骨架點數(shù)矩陣[H]為：

由于矩陣方陣才有特征值[16]，為便于后續(xù)匹配，若[m≠n]，則將行列中較少的一方添0補齊，使列數(shù)與行數(shù)相等。由于[H]矩陣表示骨架點落在指定區(qū)域內(nèi)的個數(shù)，故添0操作相當(dāng)于在已劃分好的網(wǎng)格右側(cè)或上方再添加新的網(wǎng)格，使網(wǎng)格的行與列相等，最后得出的數(shù)據(jù)矩陣與式（1）意義相同[17]。將圖5（a）按照上述方法生成數(shù)據(jù)矩陣[H（a）]，添0后為[H（a）']。

3.3 骨架點數(shù)矩陣匹配

通過將模型骨架轉(zhuǎn)換成直方圖，再根據(jù)直方圖生成數(shù)據(jù)矩陣，模型匹配轉(zhuǎn)換成兩個矩陣之間的匹配。兩個矩陣差異度可以用矩陣特征值之和的差表示。如圖6所示為模型二及完成歸一化與簡化后的模型。

將處理后的投影三視圖用第2節(jié)所述方法生成骨架，如圖7（a）中粗實線所示。將3個骨架依次用直方圖進行描述，并用網(wǎng)格劃分好，如圖7（b）所示。

3.2節(jié)中[H（a）']特征值之和為4.41，[H（1）']特征值之和為7.260 1，[H（a）']與[H（1）']矩陣特征值和之間的差為：|4.41- 7.260 1|= 2.850 1，即為兩個視圖之間的差異度。

3.4 零件模型匹配

模型骨架直方圖與其骨架點數(shù)矩陣特征值之和是互相對應(yīng)的，故比較兩個模型骨架的相似度，可比較矩陣特征值之和的差。分別比較處理后主、俯、左視圖骨架點數(shù)矩陣特征值和的差，取加權(quán)值，即為兩個零件模型之間的差異度值[Dif]，如式（2）所示。

4 實例應(yīng)用

為檢驗本文方法的可行性，將圖1模型數(shù)據(jù)上傳到自行開發(fā)的機械零件檢索系統(tǒng)中，見圖8。

系統(tǒng)運行結(jié)果顯示，排序前三的依次為編號0028、0126、0033的零件，即這3個零件差異度值較小，與圖1模型在形狀上很相似[18]，可以參考這幾個模型的設(shè)計方案。

5 實驗分析

將本文算法與D2形狀分布算法[19]及遞歸分割算法[20]進行對比分析，以驗證本文算法的可行性與準確性。

首先對計算量進行比較，本文的骨架提取算法是對鄰域像素距離變換值大小的比較，計算量較小，且矩陣特征值計算簡便易行。本文以第4節(jié)所述機械零件庫作為測試數(shù)據(jù)庫，在保證其它細節(jié)相同的情況下，依次用3種算法對同一零件模型進行檢索，檢索耗時如表2所示。本文方法計算量不大，耗時比D2形狀分布算法略多0.31s，少于遞歸分割算法。

綜合比較計算量和查準率—查全率后可以得出，本文算法計算量及檢索耗時略高于D2算法，但查準率—查全率優(yōu)于D2算法;本文算法查準率在查全率大于0.18后，優(yōu)于遞歸分割算法，且計算量明顯減小。綜合兩方面，本文算法具有很強的實用性。

6 結(jié)語

（1）本文的骨架生成方法通過迭代將新生成的骨架點重設(shè)為起始點，由起始點出發(fā)對鄰域像素進行判定，生成的骨架點相互鄰接，骨架具有連續(xù)性，有效避免了現(xiàn)有基于距離變換方法的骨架中斷現(xiàn)象。

（2）將處理后的投影圖像素化，并一次性地賦予像素值，骨架點判定是通過對鄰域像素值大小進行比較，故本文骨架生成算法計算量較小;骨架匹配是將骨架直方圖轉(zhuǎn)換為骨架點數(shù)矩陣，根據(jù)矩陣特征值和之間的差計算兩模型間的差異度，數(shù)據(jù)矩陣特征值計算簡便、快速，因此本文檢索方法效率較高。

（3）本文提出的模型骨架提取方法也適用于有通孔結(jié)構(gòu)分布的機械零件，目前已在自行開發(fā)的檢索原型系統(tǒng)中得到應(yīng)用。然而，如果零件上有盲孔，則處理后的骨架與通孔類零件相同。因此，針對本文的骨架提取部分，對于該情況還需作進一步研究。

參考文獻：

[1] LIU A，WANG Z，NIE W，et al. Graph-based characteristic view set extraction and matching for 3D model retrieval[J]. Information Sciences， 2015， 320： 429-442.

[2] ZHANG Y，JIANG F，RHO S，et al. 3D object retrieval with multi-feature collaboration and bipartite graph matching[J]. Neurocomputing， 2016，195（C）：40-49.

[3] CHOI W P，LAM K M，SIU W C. Extraction of the euclidean skeleton based on a connectivity criterion[J]. Pattern Recognition，2003，36（3）：721-729.

[4] CHENG H C，LO C H，et al. Shape similarity measurement for 3D mechanical part using D2 shape distribution and negative feature decomposition[J]. Computers in Industry，2011，62：269-280.

[5] 徐敬華，張樹有. 基于遞歸分割的機械零件三維形狀結(jié)構(gòu)檢索方法[J]. 機械工程學(xué)報，2009，45（11）：176-183.

[6] 萬雅娟，李海生，劉漩，等. 基于距離變換的三維連通骨架提取算法[J]. 計算機仿真，2014，31（6）：256-260.

[7] 劉玉杰，宋陽，李宗民，等. 融合信息熵和CNN的基于手繪的三維模型檢索[J]. 圖學(xué)學(xué)報，2018，39（4）：735-741.

[8] 劉云，戴光明，王茂才. 基于遺傳算法的封閉輪廓最小面積凸包圍盒生成算法[J]. 湖北工程學(xué)院學(xué)報，2007，27（3）：63-66.

[9] 周圍，徐慶華，徐賜軍. 面向機械結(jié)構(gòu)形態(tài)的三維模型信息處理[J]. 湖北理工學(xué)院學(xué)報，2018，142（2）：7-10.

[10] 陳永常. 印刷制版工藝原理[M]. 北京：化學(xué)工業(yè)出版社，2014.

[11] 葉剛. 城市環(huán)境基于三維激光雷達的自動駕駛車輛多目標檢測及跟蹤算法研究[D]. 北京：北京理工大學(xué)，2016.

[12] MISHCHENKO Y. A fast algorithm for computation of discrete Euclidean distance transform in three or more dimensions on vector processing architectures[J]. Signal，Image and Video Processing，2015， 9（1）： 19-27.

[13] LUO S，GUIBAS L J，ZHAO H K. Euclidean skeletons using closest points[J]. Inverse Problems & Imaging， 2017， 5（1）： 95-113.

[14] 張超，蘆勤，羅述謙. 基于距離變換與路徑規(guī)劃的骨架提取算法[J]. 北京生物醫(yī)學(xué)工程，2012，31（6）：551-555.

[15] 張桂梅，鄭加寬，儲珺. 基于骨架和統(tǒng)計直方圖的形狀匹配算法[J]. 計算機工程與應(yīng)用，2015，51（16）：183-188.

[16] 陳宇祺. 基于矩陣填充理論的R-D算法[J]. 軟件導(dǎo)刊，2019，18（1）：92-96.

[17] DEMMEL J W. Applied numerical linear algebra[M]. Beijing： Tsinghua University Press，2011.

[18] 林嫻. 實心皮帶輪參數(shù)化的設(shè)計與實現(xiàn)[J]. 福建電腦，2015，31（1）：108-109.

[19] 趙鵬飛. 針對三維模型檢索中D2形狀分布算法的改進[J]. 煤炭技術(shù)，2013，32（7）：150-152.

[20] 吳延海，潘晨，吳楠. 改進的Otsu遞歸分割單幅圖像去霧算法研究[J]. ?西安科技大學(xué)學(xué)報，2017，37（3）：438-444.

（責(zé)任編輯：黃 ?。?/p>