数字加网并行加速算法的研究和实现.pdf

邻未处理的像素上。用资源和缩减存储量,为算法的进一步优化和复杂算
最简单常见的是 FS 误差扩散算法,其误差分配法的实现奠定基础。
表如图 1 所示:
流水线
X 7
并发和流水线是 FPGA 最重要的两个概念。并发
3 5 1 是代码执行的方式,其核心含义是多条指令同时执行,
Figure 1 FS Error diffusion table 多个进程同时进行,程序中位置靠前的语句不一定先
图 1 FS 误差分配表
于后面的语句执行。
该误差分配表中所有数字之和为 16。在进行二值
流水线基于并发概念形成,是并行运算中过程化
化处理时,若 X 处像素的灰度值与量化后的输出值之
计算和重复运算的实现基础。需要顺序执行的运算再
间有误差,则将该误差的 7/16 分配给 X 右侧的像素,
所难免, 也必须考虑兼容顺序执行方式,流水
误差的 3/16 分配给 X 左下方的像素,误差的 5/16 分 FPGA
线要求将顺序操作分解为多个较为独立的步骤,分别
配给 X 正下方的像素,误差的 1/16 分配给 X 右下方
成为流水线的处理级,数据按顺序进入流水线。当某
的像素,再类似地处理图像的下一个像素。FS 算法采
用自上而下、从左向右的固定顺序处理图像,扩散方一个数据进入到流水线中的某一级时,紧跟它的后一
个数据进入流水线的前一级,以此类推。假设有个
向单一容易出现人工纹理。 k
数据,每个数据分别需要 l 个执行周期完成运算,串
算法存在的问题行方式下则要 k*l 个执行周期,并行方式下只需要 k+l
由误差扩散抖动法的基本原理可知,要改进算法个,处理时间大大缩短,尤其在数据量较大的情况下,
的处理效果,主要有以下三种途径:一是改变误差分并行计算执行时间的减少量是非常可观的。
配方式,即改变分配系数或方向;二是改变量化函数使用 FPGA 实现 FS 误差扩散算法,处理一个像
优化阈值;三是改变像素的处理顺序。素需要输出四个误差灰度值,这将会导致写控制信号
无论从哪方面改进,只要算法过程化实现,就无过多。输出数据将进入多个计算单元,而对于这些单
法避免串行执行方式所固有的问题。串行处理器执行元来说,进入的多个误差本身不是同步的,为了保证
指令,依靠其内部的程序计数器,也叫 PC 指针,指不同来源的数据不发生混乱,需要使用较多的同步信
向即将执行的指令。一个执行周期 PC 指针只指向一号,实现较为困难。换个角度再分析,对于一个像素
条指令,无论运算的重复性和逻辑联系如何,PC 指针来说,它需要接收来自于它左侧、左上方、正上方和
只按程序存储的先后顺序执行,使绝大多数的软硬件右上方四个像素所产生的误差,这些像素均先于该像
资源处于等待状态。现有改进算法不但增加了计算量, 素执行,时间符合逻辑,可以简化同步控制,并且只
还增加了对存储空间的要求和 PC 执行路线的复杂度, 需要输出较少的误差数据,便于实现。
使算法和硬件资源的效率降低,应用成本提高。从灰度图像输入到二值图像输出,可以大致分成
对于一幅大小为 m*n 的图像来说,使用误差扩散以下三级流水线:
加网,算法的时间复杂度至少为 T(m*n),需要的存储 1) 读取图像