Abstract: In this paper, we propose an algorithm for the registration of multiple range images. Our registration algorithm is an integration of the iterative closest point (ICP) algorithm with random sampling having rejects and least squares (LS) estimation. The estimated motion parameters are evaluated by an adapted criterion in the coarse and fine registration, and the best updated estimation is used as the next initial value of the ICP algorithm. The algorithm uses an octree spline representation of surfaces to quickly compute the distances between points and surface and the closest point using trilinear interpolation. The proposed registration method is computationally efficient and robust to outliers. We have experimented successfully with the registration algorithm on synthetic and real range images.