## 1 Introduction  
Computer recognition of 3-dimensional (3D) objects is of a high interest in all domains where the identification of an a priori unknown object is required, e.g., when repairing a complex machine that consists of thousands of mechanical components. A typical problem that arises is matching a component, possibly damaged, to its drawing, nowadays an STL (Standard Triangle Language) triangulation. For a human, this is a demanding task. Fortunately, the human can be replaced with a robotical system, which scans the surface of the component and matches the resulting point cloud with a unique item from the database of STL triangulations of the mechanical components. The aim of this paper is to provide a fast and robust computational method for this matching.  
We propose the successive use of two methods. The first one relies on the Principal Component Analysis (PCA), which is fast. However, it may not result in a unique match but rather in a small collection of candidates. Therefore, we developed yet another method that relies on decomposition into planar and cylindrical primitives. This is robust, meaning that it typically results in a unique match. This method exhibits a higher computational complexity, which is not critical, so we apply it to the small collection of models preselected by the first method. The overall scheme of our methodology is depicted in Figure 1.  
Principal Component Analysis (PCA) fits the point cloud with an ellipsoid by means of computing the eigenvalues and eigenvectors of a 3-by-3 covariant matrix. In case there is a dominant eigenvalue, the point cloud is decomposed into two clusters to which the PCA is applied recursively. This results in a binary tree, where each vertex (corresponding to a cluster of points) is associated with the three eigenvalues. The algorithm is also applied (preprocessing phase) to all the STL triangulations from the database. The matching is performed by comparing the trees and the triples of eigenvalues. This algorithm has an almost linear complexity with respect to the number of points and a logarithmic complexity with respect to the number of STL triangulations in the database. Hence, on a single processor, it is an optimal complexity method. A drawback is that the method fails in cases with objects differing by small details. The result of the PCA is a small collection of STL triangulations.  
To overcome the lack of robustness of the PCA, we developed another method. It exploits the fact that surfaces of mechanical parts are mostly planar or cylindrical. We decomposed each object in the database (preprocessing phase) as well as the scan into planar and cylindrical primitives. For each STL triangulation and the point cloud, we computed four matrices--two for planar and the other two for cylindrical primitives. One of the two contains distances, and the other one contains angles between the primitives. The construction of such matrices has a quadratic computational complexity with respect to the number of points or triangles. Finally, we evaluate the similarity of the matrices of the point cloud to the respective matrices of STL triangulations. This has an unpleasant combinatorial complexity with respect to the number of primitives; hence, it is crucial that we apply this method to the small collection of objects preselected by PCA.  
Figure 1: The overall scheme of the proposed methodology.