利用光总线高效计算距离图

### 利用光总线高效计算距离图 在图像处理等领域，距离图问题是一个重要的研究方向。为了高效解决距离图问题，研究人员提出了基于可重构流水线总线系统（LARPBS）的算法。下面将详细介绍相关内容。 #### 1. LARPBS模型简介 LARPBS由N个处理器P1, P2, ..., PN通过光总线连接而成。它不仅具有强大的通信能力，还能被划分为k（k ≥ 2）个独立的子阵列LARPBS1, LARPBS2, ..., LARPBSk。每个子阵列LARPBSj包含处理器Pi(j - 1)+1, Pi(j - 1)+2, ..., Pij，其中0 = i0 < i1 < i2 < ... < ik = N。这些子阵列可以像常规的线性阵列一样，使用流水线光总线系统独立运行，互不干扰。 为了便于算法开发和规范，基于重合脉冲处理器寻址技术，已经实现了一系列基本的通信、数据移动和全局操作，包括一对一路由、多播、广播、分段广播、压缩、最小值查找、二进制求和和图像转置等。除了最小值查找操作，其他操作都可以在恒定数量的总线周期内完成。最小值查找操作可以确定性地在O(log log N)时间内完成，或者以高概率在O(1)时间内完成。 #### 2. 使用n²个处理器的算法 在算法描述中，对于每个像素，将图像分为左右两部分。像素(i, j)左侧的像素称为像素(i, j)左平面的像素，右侧的像素称为像素(i, j)右平面的像素。若将像素(i, j)最近的黑色像素记为M(i, j)，则从(i, j)到M(i, j)的距离就是该点的欧几里得距离变换（EDT）值。 为了计算EDT值，我们可以将图像分割成多个部分，分别进行搜索，从而减少搜索时间。具体来说，只需要计算点(i, j)到其左侧黑色像素部分的距离lij，再结合右侧的距离，取两者的最小值即可得到dij。 以下是该算法的具体步骤： 1. **步骤1：计算每个像素在其所在列中，位于该像素所在行或上方的最近黑色像素的行索引** - 初始时，如果像素值aij = 1，则设置UP NEAREST(i * n + j) = i；否则，设置为∞。 - 首先将图像转置为列主序，然后将数组分割成n个子系统，每个子系统包含图像的一列。 - 以UP NEAREST(i * n + j)作为本地数据值，像素值aij作为本地逻辑值，进行右分段广播，结果存储在UP NEAREST(i * n + j)中。 2. **步骤2：计算每个像素在其所在列中，位于该像素所在行或下方的最近黑色像素的行索引** - 初始时，如果像素值aij = 1，则设置DOWN NEAREST(i * n + j) = i；否则，设置为∞。 - 此时图像已经是列主序，处理器数组也已分割成n个子系统。 - 以DOWN NEAREST(i * n + j)作为本地数据值，像素值aij作为本地逻辑值，进行左分段广播，结果存储在DOWN NEAREST(i * n + j)中。 3. **步骤3：计算图像中所有点在其左区域的EDT值** - 首先将图像转置回行主序，然后将数组分割成n个子系统，记为ARR(i)（0 ≤ i ≤ n - 1），每个子系统包含图像的一行。 - 以行i为例，使用子数组ARR(i)计算该行所有点在其左区域的EDT值。具体做法是对每行进行二分，直到计算出该行所有点的左区域EDT值。 - 例如，计算点(i, n/2)的左区域EDT值： - 假设DOWNNEAREST(i, j) = i1，UPNEAREST(i, j) = i2，处理器PE(i, j)先计算DOWN DIST(i, j) = ((i1 - i)² + (j - n/2))¹/²和UP DIST(i, j) = ((i2 - i)² + (j - n/2))¹/²。 - 比较DOWN DIST(i, j)和UP DIST(i, j)，将较小值存入DIST(i, j)