Efficient algorithms for computing two nearest-neighbor problems on a rap |
| |
Authors: | Tzong-Wann Kao Shi-Jinn Horng |
| |
Affiliation: | Department of Electrical Engineering, National Taiwan Institute of Technology, Taipei, Taiwan, R.O.C. |
| |
Abstract: | This paper makes an improvement of computing two nearest-neighbor problems of images on a reconfigurable array of processors (RAP) by increasing the bus width between processors. Based on a base-n system, a constant time algorithm is first presented for computing the maximum/minimum of N log N-bit unsigned integers on a RAP using N processors each with N1/c-bit bus width, where c is a constant and c ≥ 1. Then, two basic operations such as image component labeling and border following are also derived from it. Finally, these algorithms are used to design two constant time algorithms for the nearest neighbor black pixel and the nearest neighbor component problems on an N1/2 × N1/2 image using N1/2 × N1/2 processors each with N1/c-bit bus width, where c is a constant and c ≥ 1. Another contribution of this paper is that the execution time of the proposed algorithms is tunable by the bus width. |
| |
Keywords: | Parallel algorithm Image processing Maximum number Nearest-neighbor Reconfigurable bus system |
本文献已被 ScienceDirect 等数据库收录! |
|