Parallel processing approaches to edge relaxation (Q1114433)

This paper describes several parallel algorithms for image edge relaxation on array processors with different numbers of processing elements (PEs) connected by a mesh of hypercube network. The time complexity of Prager's original edge relaxation scheme is \(O(N^ 2)\) per iteration using floating-point operations on a sequential machine, where \(N^ 2\) is the number of pixels in the image. Modifications to the scheme are made so that no multiplications are employed and only integer operations are required. Moreover, with parallel processing, the time complexity per iteration is reduced to some constant value. A time complexity analysis on two parallel algorithms is performed. Although the algorithm on an array processor with \(4N^ 2\) PEs achieved higher degree of parallelism, the algorithm with \(N^ 2\) PEs is preferred. Further modifications on the latter algorithm are made to accomodate to fewer PEs.