Parallelization of perceptual grouping on distributed memory machines

Abstract

In this paper, we propose architecture-independent parallel algorithms for solving Perceptual Grouping tasks on distributed memory machines. Given an n × n image, using P processors, we show that these tasks can be performed on O(n2/P) computation time and 20√PTd+8(log P)Td + (40n/√P + 20 P)τd communication time, where Td is the communication startup time and τd is the transmission rate. Our implementations show that, given 7 K line segments extracted from a 1K × 1K image, the Line Grouping task can be performed in 1.115 seconds using a partition of CM-5 having 256 processing nodes and in 0.382 seconds using a 16-node Cray T3D. Our code is written in C and MPI message passing standard and can be easily ported to other high performance computing platforms.