朱文博 王朝 陳龍

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

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

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

中圖分類號(hào)：TP319文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1672-7800（2020）005-0107-05

0 引言

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

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

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

1.1 模型歸一化及簡(jiǎn)化

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

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

1.2 投影與像素化處理

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

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

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

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

2 骨架提取算法

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

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

3 相似度計(jì)算

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

3.1 骨架直方圖描述

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

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

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

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

由于矩陣方陣才有特征值[16]，為便于后續(xù)匹配，若[m≠n]，則將行列中較少的一方添0補(bǔ)齊，使列數(shù)與行數(shù)相等。由于[H]矩陣表示骨架點(diǎn)落在指定區(qū)域內(nèi)的個(gè)數(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 骨架點(diǎn)數(shù)矩陣匹配

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

將處理后的投影三視圖用第2節(jié)所述方法生成骨架，如圖7（a）中粗實(shí)線所示。將3個(gè)骨架依次用直方圖進(jìn)行描述，并用網(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，即為兩個(gè)視圖之間的差異度。

3.4 零件模型匹配

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

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

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

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

5 實(shí)驗(yàn)分析

將本文算法與D2形狀分布算法[19]及遞歸分割算法[20]進(jìn)行對(duì)比分析，以驗(yàn)證本文算法的可行性與準(zhǔn)確性。

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

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

6 結(jié)語(yǔ)

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

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

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

參考文獻(xiàn)：

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

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

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

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

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

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

[11] 葉剛. 城市環(huán)境基于三維激光雷達(dá)的自動(dòng)駕駛車輛多目標(biāo)檢測(cè)及跟蹤算法研究[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] 張桂梅，鄭加寬，儲(chǔ)珺. 基于骨架和統(tǒng)計(jì)直方圖的形狀匹配算法[J]. 計(jì)算機(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ù)化的設(shè)計(jì)與實(shí)現(xiàn)[J]. 福建電腦，2015，31（1）：108-109.

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

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

（責(zé)任編輯：黃 健）