概要

We describe a method for parallel alignment of multiple range images. It is difficult to align a large number of range images simultaneously. Therefore, we developed the parallel method to improve the time and memory performances of the alignment process. Although a general simultaneous alignment algorithm searches correspondences for all pairs of all range images by rejecting redundant dependencies, our method makes it possible to accelerate computation time and reduce the amount of memory used. Since the computation between two range images can be preformed independently, each correspondence pair of range images is assigned to each node. Because the computation time is proportional to the number of vertices assigned to each node, by assigning the pairs so that the number of vertices computed is equal on each node, the load on each node is effectively distributed. The heuristic algorithms for graph partitioning are applied to this problem in order to reduce the amount of memory used on each node. The method was tested on a 16-processor PC cluster, where it demonstrated the high extendibility and the performance improvement in time and memory.