局部比對用於CAD模型搜尋之研究

Partial Matching on CAD Model Retrieval

蔡易龍(Yi-Lung Tsai)

指導教授 ： 尤春風

國立臺灣大學/工學院/機械工程學研究所/博士(2010年)

https://doi.org/10.6342/NTU.2010.01152

摘要

產品開發的實務應用上，多半從既有資料中找尋與新產品相似的舊產品，新增、修改或刪除部分功能再利用，提升設計流程的整體效能。目前很多研究都是依照3D物體的整體外形進行相似物件檢索，但是因為機械零件存在很多突起或凹陷之細部特徵，若直接將文獻中的方法套用在設計與製造等應用中，會造成後續應用上的困難。本研究以局部特徵對應關係的觀點，提出以屬性圖為基礎的CAD模型搜尋法則，利用圖結構的特性實現部分比對，依據3D模型的局部特徵對應關係進行相似度判斷，建立相似CAD模型搜尋系統。首先從STEP檔案取得的CAD模型資訊，針對實體模型及汽車板金模型各別建立其對應之屬性圖。接著提出以經驗法則為基礎之圖結構比對法，將CAD模型相似度比對問題轉換為最大圖團問題，並應用模擬退火演算法比對屬性圖之相同結構，以取得CAD模型之間的相似局部特徵。將模擬退火演算法應用於DIMACS測試圖檔上，雖無法百分之百求得所有測試檔的最大圖團，但對於絕大部分的測試範例有不錯的表現。為實現多處局部特徵比對，提出獨立極大圖團搜尋法則求取模型間之相似特徵，並以局部特徵對應關係衡量CAD模型間之相似度。由測試結果可以證明獨立極大圖團搜尋法則適用於相似CAD模型搜尋系統中，應用局部特徵對應關係之特性，可以找到細節特徵與整體外形均相似之零件。

關鍵字

部分比對 ； 相似CAD模型搜尋 ； 局部特徵對應關係 ； 獨立極大圖團 ； 模擬退火

並列摘要

For engineering applications, a new design can be developed efficiently from an existing design with same functions, features, and manufacturing properties. Although several techniques have been developed for assessing the similarity among models, most methods are not sufficiently suitable for design and manufacturing. This work presents a graph-based retrieval architecture based on partial matching and a CAD model retrieval system based on the local feature correspondence. First construct attributed graph for each CAD model that retains the geometric and topological data from STEP format. Then transform the problem of model similarity assessment into the maximum clique problem and use simulated annealing algorithm to solve it. The proposed simulated annealing algorithm that successfully figures out several test files from DIMACS shows its practicability in similarity assessment. To achieve the goal of local feature correspondence, solve the graph-matching problem using independent maximal cliques (IMC) detection method. All independent maximal cliques, which represent common features between models, are identified using simulated annealing. According to IMC detection method, the experimental results demonstrate the practicability of this work for CAD model retrieval based on local feature correspondence.

並列關鍵字

partial matching ； similar CAD model retrieval ； local feature correspondence ； independent maximal cliques ； simulated annealing

參考文獻

[68]陳宗伯，2004，零件搜尋系統之研究與應用，國立臺灣大學機械工程研究所碩士論文

[1]Akutsu, T., 1993, A polynomial time algorithm for finding a largest common subgraph of almost trees of bounded degree, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Science E76-A(9), 1488-1493

[3]Bespalov, D., Regli, W. C., Shokoufandeh, A., 2006, Local feature extraction and matching partial objects, Computer-Aided Design 38(9), 1020-1037

[5]Bomze, I. M., Pelillo, M., Stix, V., 2000, Approximating the maximum weight clique using replicator dynamics, IEEE Transactions on Neural Networks 11(6), 1228-1241

[7]Cardone, A., Gupta, S. K., Karnik, M., 2003, A survey of shape similarity assessment algorithms for product design and manufacturing applications, Journal of Computing and Information Science in Engineering 3(2), 109-118