With the development of completely automated methods to extract crest lines and the higher resolution of images, the number of crest lines drastically increased, leading to a much higher density of invariants in the hash table. This could lead to an important number of false positives that would overwhelm the correct matches. The maximum complexity would then be reached and the algorithm could even provide a wrong answer. To address this problem, Thirion reduced once again the image information by keeping only a very small number of specific points on the crest lines: the extremal points. Typically, they represent only 16% of the number of crest line points, but we are still left with 2000 to 5000 points in each image.
Thirion used in  another computer vision based technique: alignment (or prediction-verification) [2,17]. The basic idea is to compute the registration of each triplet of model points with each triplet of scene points, superimpose the two sets of points using this transformation, and verify this match using an iterative closest-point algorithm (see Section 2.4). However, the search for compatible triplets in the model and the scene can be reduced since there are some unary invariants (the principal curvatures k1 and k2), secondary invariants (e.g., the distance between the two points, or the relative orientation of the surface normals and the principal curvatures), and even ternary invariants (involving the whole triplet of extremal points). Thirion used 18 such invariants for each triplet, precomputed and stored them in a hash table to retrieve in constant time the compatible triplets. Thus, the complexity of the algorithm is 0(n4), since there are n3 triplets, and a verification of 0(n) for each triplet match. In practice, this complexity is not reached, as we can stop as soon as a given number of points is matched after verification (typically 10%).
Was this article helpful?