Complexity analysis of range image segmentation on MasPar MP-1

Many low level vision tasks that are computationally intensive are easily parallelizable. The lack of parallel processing systems, or their prohibitive costs, have prevented the move of vision processing algorithms from single processor systems to multiprocessor systems. With the recent spurt of parallel processing hardware, there is a need to investigate the feasibility of using such machines for some vision algorithms. Speedup is an important factor in determining the feasibility of migration from single processor systems to parallel processors. In this work, we investigate a particular segmentation algorithm and present theoretical speedup results. Our formula can work out numerical speedups by simply plugging in the parameter values