张春柳1,2 李嘉2 熊璟2
1（上海理工大学上海 200093）
2（上海市计算机软件评测重点实验室上海 201112）
摘 要 误差扩散算法是一种常用的数字半色调技术，但传统的误差扩散算法是典型的串行算法。本文在传统误差扩散的基础上，针对误差扩散的像素扩散的原理，叙述了基于线程延迟和基于图像划分的两种误差扩散的并行化算法，并使用OpenMP进行实现。实验结果证明误差扩散算法的并行化是可行的，且是十分高效的，具有良好的应用前景。
教育期刊网 http://www.jyqkw.com
关键词 误差扩散法，OpenMP，并行程序设计
doi:10.3969/j.issn.1674-7933.2015.01.001
Error Diffusion Algorithm Implemented by OpenMP
ZHANG Chunliu1,2 LI Jia2 XIONG Lu2
1( University of Shanghai for Science and Technology, Shanghai 200093, China)
2(Shanghai Key Lab. of Computer Software Evaluating & Testing, Shanghai 201112, China)
Abstract Error diffusion algorithm is a kind of digital halftoning technology used commonly, however thetraditional error diffusion algorithm is a typical serial algorithm. Based on the traditional error diffusion algorithmand according to the principle of pixel error diffusion, this paper describes two kinds of parallel error diffusionalgorithm, one is based on the thread delay and the other is based on the image partition. Finally we implementthe parallel algorithm by OpenMP. The experimental results show that the parallel error diffusion algorithm isfeasible, and is effi cient and has excellent application prospective.
KeyWords Error Diffusion, OpenMP, Parallel Programming Design
0 引言
半色调技术，也称加网技术，是图像处理领域历史最悠久的技术之一[1]。加网技术最初始于19世纪晚期，当人们尝试着使用设备在纸张上打印文字和图像时，这种技术应运而生了。尤其是印刷工业诞生以来，它作为印刷过程中最核心的环节一直受到学术界和产业界的极大关注，并且经历了漫长的发展过程。由于人们把这个由灰度图像得出二值图像的过程看作是在原始图像上增加了一个网屏进行处理，因此称其为“加网技术”，又因为在激光印字、照相复制及各种印刷中，由于要用二值输出表示图像的阶调层次，故又称半色调技术。
更为具体的中文定义是，数字半色调技术是基于人眼的视觉特性和图像的成色特性，利用数学、计算机等工具，在二值设备或多色二值设备上实现图像再现的一门技术，是将连续调图像经过处理后用二值图像实现图像阶调再现的基础性研究闭。半色调技术应用于印刷工业已有一个多世纪，应用在数字输出设备上也有40多年，如今已广泛应用到打印、印刷、显示设备以及数字图像的压缩存储、图像的传输等领域。
数字半色调技术是一种与计算机应用相结合的技术，用来在单色显示打印设备上产生不同灰度的视觉效果，或在彩色显示打印设备上产生彩色视觉效果。这种技术主要取决于如何更合理地对图像区进行分组，并更合理地在每一个由多个像素组成的分组中分配黑白像素比例（对单色显示打印设备）或几种彩色像素比例（对彩色显示打印设备）。由于这些分组很小（通常仅仅是几个像素的级别），因此人眼会将其视为一种由分组中几种颜色共同混合而成的某种单一颜色。这就解决了如何在8位显示设备上显示24位或32位颜色的问题。
误差扩散法是数字半色调技术的一种主要方法[2]。它是由Floyd和Steinberg于1976年首次提出的，并一举成为当时处理效果最好的半色调方法。误差扩散法的出现是半色调技术史上重要的里程碑，它带来了革命性的技术变革，并促进了半色调技术的飞速发展。误差扩散处理后的半色调图像中像素点的分布是各向异性和无规律的，因而色调丰富，视觉效果好。直到今天，它依然以其视觉效果好、易于实现等特征被认为是最理想的半色调算法之一。
图1a是8位灰度图，图1b是经误差扩散处理后的2位半色调图，在这种分辨率下，二者的质量没有明显差异，表现出了良好的相似性。
图2a、图2b分别将图1a、图1b的细节放大，这时我们发现，两幅图像之间的差异非常大，右侧的2位半色调图像的质量只能用粗糙来形容了。
1 OpenMP简介
OpenMP是多处理机上编写并行程序而设计的应用编程接口[2]。它由一个编译器命令集组成，其中包括了一套编译制导语句和一个函数库。OpenMP提供了并行描述的高层抽象方法大大降低了并行程序编写的难度和复杂度，从而编程人员可以将更多的精力投入到算法本身的并行化设计中，而非具体实现细节。对基于数据分集的多线程程序设计，OpenMP是一个很好的选择。
同时，使用OpenMP也提供了更强的灵活性，可以较容易的适应不同的并行系统配置。线程粒度和负载平衡等是传统多线程程序设计中的难题，但在OpenMP中，OpenMP库从程序员手中接管了部分这两方面的工作。OpenMP可通过与标准Fortran，C和C++结合进行工作的，对于同步共享变量、分配负载等任务，都提供了有效的支持，具有简单通用、开发快速的特点。
OpenMP是C语言的一个扩展，其主要目的是为了支持并行程序设计[3]。OpenMP的程序代码C语言程序相似，只是在C程序中加入了OpenMP的编译制导语句来指示，这些编译制导语句描述了程序应该以何种方式来进行并行化。加入了OpenMP的C程序可以由任意支持OpenMP的编译器编译，并且可在不同平台的硬件上执行。OpenMP编译制导语句以#pragma开始，在其后面是omp，名字或者是子句，并用换行表示结束。一些子句可出现在不同的命令中，但需要对它们加以分别的定义。某些命令可作用于整个结构块，而构造是由编译制导语句及跟在其后的结构块所组成。
在C/C++中，OpenMP指令使用格式是#pragmaomp指令[clause [clause]…]。OpenMP的编译制导包括如下几类：
1) 并行域结构
并行域结构中的代码会被所有线程执行，使用#pragma omp parallel[clause[clause]…]常用的clause有firstprivate、lastprivate、if、reduction、private等。
2) 共享任务结构
共享任务结构中的代码划将会被分给线程组中的各个成员执行，分为并行for循环、并行sections、串行执行三种情况。
并行for循环格式为#pragma omp for[clause[[，]clause]…]，一般用于for循环前，将循环分配到多个线程中并行执行。
sections编译制导语句可将其中的代码分配给每一个线程，从而由不同的section由不同的线程执行。与for语句不通的是，如果使用for语句执行并行代码时，任务是由系统自动进行分摊，如果每次循环中没有同步问题，那么分摊是平均的，而使用section来划分任务是依靠程序员来进行线程的任务分摊，且执行性能的好坏完全依赖于程序本身。
single编译制导语句可用于部分代码不可并行的情况，通过single语句向编译器说明该部分代码只有使用线程组中的一个线程执行，其格式为
#pragma omp single[clause[[，]clause]…]
线程组中其他没有执行single语句的线程会等待该代码块的结束，除了使用nowait clause语句声明的代码。
3) 组合并行共享任务
组合并行共享任务可分为parallel for和parallelsections两种编译制导语句，parallel for的格式是#pragma omp parallel for[clause…]
它表明一个并行域包含一个独立的for语句。
parallel sections格式是
#pragma omp parallel sections[clause...]它表明一个并行域包含了单独的一个sections语句。
一般而言，由于使用parallel的命令意味着需要多于一个线程，所以在使用命令前需要先建立线程组
4) 同步结构
同步结构中的编译制导语句有atomic，barrier，master，ordered，thread—private等。
OpenMP编译制导语句可根据需要是否包含子句，在没有其它约束条件下，子句可以无序，也可以任意地选择。
#pragma omp parallel for[clause…]是最频繁使用的编译指导语句，可搭配使用的子句有firstprivate，if，lastprivate，private，reduction，schedule等。
firstprivate clause指定每个线程都拥有自己变量的私有副本，并且变量需要继承主线程中的初始值；lastprivate clause指定将线程中的私有变量值在并行处理结束后需要复制到主线程中的对应变量；privateclause指定每个线程都拥有它自己的变量私有副本；reduction clause指定一个或多个变量是私有的，并且在并行处理结束后这些变量需要执行的指定运算；schedule clause指定如何调度for语句的循环迭代。
2 误差扩散的串行算法
误差扩散算法的执行流程分为三部分：
1) 根据给定的当前像素输入值来计算输出值。
这一步一般采用量化来实现。对于一幅8位的灰度图案，将图像中处于[0,127]范围内的像素值量化为0，同时将处于[128,255]范围内的像素量化为1。
2) 在输出值计算出来之后，再计算输出设备上显示的值与实际显示值之间的误差。
当输出为0时对应像素值为0，当输出为1时，对应像素值为255。举例来讲，假设当前输入像素值是168，因为168大于128，所以其输出为1，对应像素值是255，其误差就是应该显示的值(128)和最终显示的值(255)之间的差，即-87。
3) 将误差分布到区域中相邻的像素上去，如图3所示。
误差扩散的串行算法程序如下：
for(i=0; i < Height; i++)
{
for(j=0; j < Width; j++)
{
if(InputImage[i][j] < 128)
OutputImage[i][j] = 0;
else
OutputImage[i][j] = 1;
//计算误差值
int err = InputImage[i][j]-255* OutputImage[i][j];
//扩散误差
InputImage[i][j+1]+ = err*7/16;
InputImage[i+1][j-1]+ = err*3/16;
InputImage[i+1][j]+ = err*5/16;
InputImage[i+1][j+1]+ = err*1/16;
}
}
3 误差扩散算法的并行化
误差扩散算法看上去是一个典型的串行算法，因为要计算下一个像素就必须知道前面像素的误差值。但是如果我们从接收像素的角度来看误差扩散算法，当像素(i, j)要被处理时，只要(i-1, j-1)、(i-1, j)、(i-1, j+1)和(i,j-1)已经被处理完了就可以了。如图4所示。
下面介绍两种误差扩散的并行化算法：
算法1：这种方法采用线程延迟的方法来实现。根据上述的理论，要开始处理一个像素之前，只需要处理其前一行中的三个误差值和当前行中紧邻其左侧位置的像素误差值。因此，我们可以根据这种处理顺序来确定实现方案：每个线程处理一行数据，只要前已行中的前面几个像素处理完毕，那么负责处理下一行数据的线程就可以开始执行了。即，将不同的行分配给不同的线程处理，每个线程启动时都有一个小的延迟，因为在处理当前行时，需要用到前一行中的误差数据。
算法2：这种方法采用图像划分来实现[4]。在计算点(i, j)时，如图6所示，只要点(i, j)之前的i行和2j+1列到点(i, j)斜线上的点都处理完了，就可以处理点(i, j)了。因此我们可以将图像进行划分，如图7所示，使得每个线程处理一条带状的图片，并且保持相同的节奏，这样就可以实现误差扩散算法的并行化。如图8所示。
这一部分我们将通过程序来实现误差扩散的并行算法，其算法参考之前所述的并行算法1
本文的程序是在Visual Studio .Net 2005中实现的，采用C++语言编写。当前的Visual Studio.Net 2005完全支持OpenMP 2.0标准，通过新的编译器选项/openmp可以支持OpenMP程序的编译和链接。图形的输入采用CImage类，但是由于CImage类不支持多线程的处理，因此我们将CImage处理成一个二维数组：
BYTE InputImage[row][col]，并行处理是在InputImage中进行的。
并行程序实现如下：
int cpunum=omp_get_num_procs(); //CPU数，即线程数
#pragma omp parallel private(row,col) //并行域
{
int threadid=omp_get_thread_num(); //每个线程的线程号
Sleep(20*threadid); //根据线程短延迟
#pragma omp
for (i=0;i<(Height/cpunum);i++)
{
row=row*cpunum+threadid; //任务分配
for (col=0;col<Width;col++)
//同误差扩散串行算法
}
}
本文中的程序是在Intel Xeon Quad-Core 2.0GHz处理器下运行的，我们分别在相同的环境中实现了误差扩散的串行程序和误差扩散的并行程序。其运行结果如表1所示。
从图9、图10对算法的时间消耗和加速比分析结果我们可以看出误差扩散算法的并行化是可以实现且是高效的，如果可以运用在一些慢速的打印设备上则可以大幅度地提高速度。但并行化还是存在一些问题的。比如在统一时钟方面，如果没有一个统一的时钟序列，则后面的线程可能会快于前面的线程，那么并行算法就会失效。
4 结束语
本文实现了一种基于OpenMP的误差扩散的并行化算法，根据实验对比结果表明，该方法相对于串行的误差扩散算法加速比显著，具有明显的时间消耗优势。未来基于并行化的误差扩散算法可广泛地应用于图形处理领域中。
教育期刊网 http://www.jyqkw.com
参考文献
蔡静, 刘小丹. 半色调误差扩散算法研究综述[J]. 大连民族学院学报, 2007, 40(5)：20-26.
叶玉芬, 郭宝龙, 马佳. 基于视觉差的误差扩散半色调算法[J]. 计算机工程, 2006, 32(16)：195-197.
蔡佳佳, 李名世, 郑锋. 多核微机基于OpenMP的并行计算[J]. 计算机技术与发展, 2007, 17(10)：87-91.
Panagiotis T. M. Parallel digital halftoning by error-diffusion[J]. ACM International Conference Proceeding Series,2003, 41：35-41.