Parallel processing approaches to edge relaxation

DOI10.1016/0031-3203(88)90028-3MaRDI QIDQ1114433zbMATH OpenOpenAlexFDO

Authors Eva Leung, Xiaobo Li

Publication date 1988

Published in Pattern Recognition (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0031-3203(88)90028-3

zbMATH Keywords

edge relaxationinterconnection networkparallel algorithmsSIMD array processor

Mathematics Subject Classification ID

Theory of operating systems (68N25) Pattern recognition, speech recognition (68T10)

Review text

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.

Recommendations

• Processor-time optimal parallel algorithms for digitized images on mesh- connected processor arrays
• Parallel image analysis: Theory and applications
• Parallel matching and reconstruction algorithms in computer vision
• scientific article; zbMATH DE number 1485386
• A parallel thinning algorithm with fine grain subtasking

Cites work

• Boundary and Object Detection in Real World Images
• Parallel Matrix and Graph Algorithms
• Relaxation Processes for Scene Labeling: Convergence, Speed, and Stability
• Scene Labeling by Relaxation Operations

Cited in

(3)

• Parallel edge-region-based segmentation algorithm targeted at reconfigurable MultiRing network
• Parallel implementation of a multiscale edges detection algorithm
• Relaxation algorithm for piecing-error for sub-images

This page was built for publication: Parallel processing approaches to edge relaxation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1114433)