A review of recent range image registration methods with accuracy evaluation <s> Genetic algorithms <s> We present a new method for precise registration of multiple range images with low overlap based on genetic algorithms (GAs). The proposed method minimizes the alignment error within the common overlap area among a set of views, which is computed by a novel robust evaluation metric, called the surface interpenetration measure. Because they search in a space of transformations, GAs are capable of registering surfaces without need for prealignment, as opposed to methods based on the iterative closest point (ICP) algorithm, the most popular to date. The experimental results confirm that the new method ensures more precise alignments than combined sequential pairwise alignments for multiview registration, providing accurate global alignment among overlapping views. <s> BIB001 </s> A review of recent range image registration methods with accuracy evaluation <s> Genetic algorithms <s> Robust and fast free-form surface registration is a useful technique in various areas such as object recognition and 3D model reconstruction for animation. Notably, an object model can be constructed, in principle, by surface registration and integration of range images of the target object from different views. In this paper, we propose to formulate the surface registration problem as a high dimensional optimization problem, which can be solved by a genetic algorithm (GA) (Genetic Algorithms in Search Optimization and Machine Learning, Addison-Wesley, Reading, MA, 1989). The performance of the GA for surface registration is highly dependent on its speed in evaluating the fitness function. A novel GA with a new fitness function and a new genetic operator is proposed. It can compute an optimal registration 1000 times faster than a conventional GA. The accuracy, speed and the robustness of the proposed method are verified by a number of real experiments. <s> BIB002
Chow et al. BIB002 presented a dynamic genetic algorithm to solve the registration problem. The goal of this method is to find a chromosome composed of the 6 parameters of the motion that aligns a pair of range images accurately. The chromosome is composed of the three components of the translation vector and the three angles of the rotation. In order to minimize the registration error, the median is chosen as the fitness function, as follows: where T is the transformation matrix composed by 6 motion parameters and p i and m i the points of both surfaces. Therefore, only a sample of points of the first image were used to compute the error with the aim of decreasing the computing time. The cross-over operation consisted of combining genes made by two chromosomes to create a new chromosome. The author randomly selected the number of genes to be swapped. The cross-over operation works well when the chromosome is far from the final solution but it is useless for improving the solution in a situation close to convergence. Therefore, the mutation operation was defined as follows: a gene is randomly selected and a value randomly obtained between the limits [ÀMV, +MV] is added. The limits are very wide at the beginning and become narrower at every step in order to guarantee the convergence in the final steps. A similar method was proposed the same year by Silva et al. BIB001 . The main advantage of this work is that a more robust fitness function is used and the initial guess is not required. The author defined the Surface Interpenetration Measure (SIM) as a new robust measurement that quantifies visual registration errors. Another advantage of Chow's method is the multi-view registration approach. Finally, the hillclimbling strategy was used to speed up the convergence. Overall, the use of genetic algorithms has the advantage of avoiding local minima which is a common problem in registration, especially when the initial motion is not provided or it is given with low precision. This algorithm also works well in the presence of noise and outliers given by non-overlapping regions. The main problem of this algorithm is the time required to converge. Additionally, fitness function must be theoretically computed using real correspondences, however, as they are unknown, temporally correspondences are used using the estimated motion. However, as the motion change iteratively, correspondences must be searched several times (for example, every time a better result is found), resulting again in a lot of computing time.