טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
M.Sc Thesis
M.Sc StudentFishkel Fabricio
SubjectVerification of Engineering Models Based on Bipartite
Graph Matching for Inspection Applications
DepartmentDepartment of Mechanical Engineering
Supervisor Professor Anath Fischer


Abstract

Verification of a complex freeform part requires comparison of its 3D scanned model with its reference CAD model. Problems that arise in current methods are mainly the registration accuracy of the models and the influence of scanning errors and noise. The Iterative closest Point (ICP) algorithm is the most common method for registration. However, it requires a pre-alignment stage. This stage is time consuming.

We present a new method for pre-alignment of a scanned part for verification proposes, based on mesh segmentation and graph matching theory. Scanned data passes through noise filtering, and meshes are constructed for each of the scanned and CAD models. The method consists of four main stages. First, both meshes are segmented, and geometrically matching segments are determined by forming a Bipartite Graph. Second, a Combinatorial Matching Tree (CMT) is constructed from the Bipartite Graph, and all matching segments sets are extracted. Third, sets of matching pairs of segments are evaluated and selected by minimizing the mean square distance of their center points. Each set of matched segment pairs serves as a pre-alignment. Finally, the ICP algorithm is applied on the best pre-alignment. The aligned models can be inspected numerically or visually by a color map.

The main advantage of the proposed method is its global convergence compared with the failure of a simple ICP algorithm due to local convergence. Another advantage is the low computational complexity of the proposed method. A small number of segments are considered on each model, thus reducing the registration complexity. High precision alignments are expected even for parts having a high level of shape complexity, shape ambiguities, such as symmetry or repeated features and incomplete scanned models.

The feasibility of the proposed pre-alignment method is be demonstrated by a number of complex objects from the engineering and medical field.