超立方体上的Hough变换并行算法

摘要

给出了一个在超立方体 SIMD 计算结构上的 Hough 变换并行算法.对于一个 N×N 的图像与 n 个θ值,这个算法可以在具有 N×N×n 个处理单元的超立方体上在 O(log n)时间内完成计算.另外,还给出了对较大规模图像在固定规模的超立方体上的并行算法.在具有 M×M×m 个 PE 的超立方体上,设 L=N/M,l=n/m,则所需时间为 O(L^2l)=O[(N^2n)/(M^2m)],这样,算法使计算速度随处理机个数而线性增长,使计算效率达到最优.