Fast Affine Invariant Shape Matching from 3D Images Based on the Distance Association Map and the Genetic Algorithm

The decision on whether a pair of closed contours is derived from different views of the same object, a task commonly known as affine invariant matching, can be encapsulated as the search for the existence of an affine transform between them. Past research has demonstrated that such search process can be effectively and swiftly accomplished with the use of genetic algorithms. On this basis, a successful attempt was developed for the heavily broken contour situation. In essence, a distance image and a correspondence map are utilized to recover a closed boundary from a fragmented scene contour. However, the pre-processing task involved in generating the distance image and the correspondence map consumes large amount of computation. This paper proposes a solution to overcome this problem with a fast algorithm, namely labelled chamfer distance transform. In our method, the generation of the distance image and the correspondence map is integrated into a single process which only involves small amount of arithmetic operations. Evaluation reveals that the time taken to match a pair of object shapes is about 10 to 30 times faster than the parent method. © 2012 Springer-Verlag.