標題: | Parallel distance transforms on a linear array architecture |
作者: | Chia, TL Wang, KB Chen, Z Lou, DC 資訊科學與工程研究所 Institute of Computer Science and Engineering |
關鍵字: | distance transformation;linear array;parallel processing;partition method |
公開日期: | 30-四月-2002 |
摘要: | Distance transformation (DT) has been widely used for image matching and shape analysis. In this paper, a parallel algorithm for computing distance transformation is presented. First, it is shown that the algorithm has an execution time of 6N - 4 cycles, for an N x N image using a parallel architecture that requires [N/2] parallel processors. By doing so, the real time requirement is fulfilled and its execution time is independent of the image contents. In addition, a partition method is developed to process an image when the parallel architecture has a fixed number of processing elements (PEs); say two or more. The total execution time for an N x N image by employing a fixed number of PEs is 2[N-2/M + 2(M - 1)], when M is the fixed number of PEs. (C) 2002 Elsevier Science B.V. All rights reserved. |
URI: | http://dx.doi.org/10.1016/S0020-0190(01)00250-2 http://hdl.handle.net/11536/28852 |
ISSN: | 0020-0190 |
DOI: | 10.1016/S0020-0190(01)00250-2 |
期刊: | INFORMATION PROCESSING LETTERS |
Volume: | 82 |
Issue: | 2 |
起始頁: | 73 |
結束頁: | 81 |
顯示於類別: | 期刊論文 |