A review of recent range image registration methods with accuracy evaluation <s> Line-based algorithm <s> Three-dimensional shape models are often put together from several partial reconstructions. There are good algorithms available to perform the necessary, precise registration automatically, but only after the partial reconstructions have been brought into approximate positions. Providing the initial crude positions is often done manually. This paper proposes a technique to compute these initial positions automatically. The development of this automatic crude registration has allowed us to create a system that can generate complex 3D models from a set of partial reconstructions without any user intervention or prior knowledge of relative positions. <s> BIB001 </s> A review of recent range image registration methods with accuracy evaluation <s> Line-based algorithm <s> We are building a system that can automatically acquire 3D range scans and 2D images to build geometrically and photometrically correct 3D models of urban environments. A major bottleneck in the process is the automated registration of a large number of geometrically complex 3D range scans in a common frame of reference. In this paper we provide a method for the accurate and efficient registration of a large number of complex range scans. The method utilizes range segmentation and feature extraction algorithms. Our algorithm automatically computes pairwise registrations between individual scans, builds a topological graph, and places the scans in the same frame of reference. We present results for building large scale 3D models of historic sites and urban structures. <s> BIB002 </s> A review of recent range image registration methods with accuracy evaluation <s> Line-based algorithm <s> Our goal is the production of highly accurate photorealistic descriptions of the 3D world with a minimum of human interaction and increased computational efficiency. Our input is a large number of unregistered 3D and 2D photographs of an urban site. The generated 3D representations, after automated registration, are useful for urban planning, historical preservation, or virtual reality (entertainment) applications. A major bottleneck in the process of 3D scene acquisition is the automated registration of a large number of geometrically complex 3D range scans in a common frame of reference. We have developed novel methods for the accurate and efficient registration of a large number of 3D range scans. The methods utilize range segmentation and feature extraction algorithms. We have also developed a context-sensitive user interface to overcome problems emerging from scene symmetry. <s> BIB003
Some authors proposed to use lines to find pairs of correspondences. Examples are the straight line-based method proposed by Stamos and Leordeanu BIB002 and the curved line-based method proposed by Wyngaerd BIB001 . The former is based on the extraction of straight segments directly in the range images which are further registered with the aim of computing the motion between the different views. The algorithm is applied to large and structured environments such as buildings in which planar regions and straight lines can be easily found. The segmentation algorithm determines a set of border lines and their corresponding planes. First, a robust algorithm is used to efficiently search pairs of lines based on line length and plane area. Then, the rotation and translation among potential pairs is computed. Finally, the one that maximizes the number of planes is taken as the solution. Some years later, the same authors changed the approach used in computing the motion between straight lines BIB003 . As most part of lines in a structured environment is contained in the three planes of a coordinate system, they proposed to compute first the three main directions of every view. Hence, 24 combinations arise to potential align both views. Then, the rotation matrix is computed for every combination and, finally, the one that maximizes the number of diagonal elements is selected as the rotation solution. The rest of rotation matrices are kept because final results are supervised by an operator. Translation vectors are computed as the one that connect midpoints of two pair of segments. The more repeated vector is selected to become the solution. Finally, the registration is refined by using an ICP-based method. The algorithm obtains good results even considering that it is classified into coarse registration. The main drawback is the difficulty to segment the straight segments as well as the supervisor required to check the final results given by the method. Both drawbacks decrease the number of applications but the method has performed very well in the registration of buildings. The general case of line-based matching is the consideration of curved lines in order to register free-form surfaces Vanden Wyngaerd BIB001 proposed a rough estimation of motion by matching bitangent curves. A bitangent curve is a pair of curves composed by the union of bitangent points, which are simultaneously defined as a pair of points tangent to the same plane. The bitangent curves are found by means of a search in the dual space. The main idea is that all bitangent points are coincident in the dual space. In order to do the search, it is necessary to represent the four parameters of any plane using only three components or coordinates. So, the normal vectors at each point of the range image are computed and their norms are set to one. Using these vectors and the coordinates of their points, it is easy to compute the four parameters of the plane (a, b, c and d) tangent to that point. Since the norms of the normal vectors are set to one, it is possible to represent this vector using just two parameters. The author used a and b to parameterize the normal vector. In theory, it is possible to construct the dual space using a, b and d. However, it is necessary to normalize the parameter d between À1 and +1 to scale the values. Once all the bitangent curves present in a range image are extracted from the dual space, the matching between these curves with the curves in the next range image starts. In this way, an invariant description of a pair of bitangent curves is used with the goal of matching only the most representative curves, i.e. the 15 longest ones. The invariant used is defined as the set of distances between bitangent points. In order to increase efficiency, the curve is divided into segments of equal length. Once a correspondence is found, four corresponding points, that is the two end-points of both bitangent segments, are obtained. With these four correspondences, the Euclidean transformation can be computed, and then the error can be analyzed by transforming all the points with respect to the reference system. The matching of bitangent segments that correspond to the minimum error is selected as the best one among all the potential matches. Compared to other methods in which the correspondence is based on points, this method has the advantage that the range image is previously transformed into the dual space before the search for possible matches starts. This transformation decreases the computing time and increases the robustness. However, depending on the shape of the object, the number of bitangent points can be insufficient to ensure good results.