Parallel segmentation of range images on a hypercube-connected distributed computer

This dissertation develops techniques for the segmentation of three-dimensional range images in a parallel environment. An iterative parallel range segmentation process is used to create a view-independent description of the input range data. The system characterizes the underlying scene by using a hierarchical approach where surfaces are segmented using low-order characteristics, under the assumption that most object volumes are bound by relatively smooth surfaces. A parallel connected-component analyzer, implemented by a new algorithm for coarse-grained distributed-memory multiprocessors, is the central element of the system. Furthermore, a general model for distributed-memory algorithms using n-cube topologies is developed and used in the analysis of algorithms necessary for low-level computer vision. This model explicitly relates the concepts of speed-up, efficiency, and load balancing, and provides criteria for the optimum assignment of cube size. To minimize the communication overhead and balance computation with communication, low-level computer vision functions are classified as local or global and parallelization strategies developed for each case.