数字半色调是一种使用黑白二值的像素点来表现连续灰度图像的技术。在数字半色调处理的各种技术中,误差扩散算法以其较好的半色调图像质量和较快的算法运行速度,得到了非常广泛的应用。　　 多年以来,研究者们对误差扩散算法进行了大量的研究和改进。在早期的研究中,由于技术条件的限制,图像尺寸大小有限,同时大规模并行处理的硬件成本较高,无法在嵌入式设备上使用,从而对误差扩散算法的改进集中在半色调处理质量上。最近出现的几种误差扩散算法已经可以生成质量极高的半色调图像。　　 近年来,随着数字图像精度越来越高,半色调算法处理的图像尺寸也越来越大。在例如在线数码印花、即时相片打印、数字高精度医学影像等一些新兴的数字图像应用中,对图像显示的实时性也提出了很高的要求。在如此情况下,不论是学术领域还是生产厂家,都对半色调算法的处理速度越来越重视。而并行误差扩散算法无论是半色调图像质量还是算法运行速度都是数字半色调算法中较为优秀的。另一方面,随着近年来多核桌面CPU和GPGPU的普及,并行计算的硬件成本大幅降低。这在客观上也推动了并行误差扩散算法在实际生产中的应用。　　 本文比较了改进误差扩散算法半色调质量和提升该算法处理速度的各种途径,深入分析和总结了并行误差扩散算法近十年来的主流技术。在此基础之上,提出了若干分属不同种类的新颖的并行误差扩散算法:　　 1)提出了一种基于分块的阈值调制并行误差扩散算法　　 在镶嵌分块的并行误差扩散算法中,由于需要顾及块间误差传递,块内的半色调处理往往会产生特殊的瑕疵,如对角线状的纹理结构。本文通过在块内使用斜向45度的S形扫描路径使得块内误差传递和块间误差传递均更为平滑,同时在半色调处理过程中引入阈值调制方法,提升了半色调图像的整体质量。相比于其他的基于分块的误差扩散算法,我们的算法产生的半色调图像完全没有块『白J的边缘效应,同时也有效的消除了块内的特殊纹理。　　 2)提出了一种基于跳跃扫描路径的并行误差扩散算法　　 传统的误差扩散算法,无论是沿着光栅扫描路径还是S形扫描路径,处理图像同一行中像素的顺序都是连续的。在中间灰度区域附近的某些特定灰度值的单一均匀图像上,这会产生结构化的特殊纹理。本文通过在一定条件下进行扫描路径的跳跃,有效的减轻了这种特殊纹理的产生。进一步的分析表明,在那些传统误差扩散算法容易产生特殊纹理的灰度值上,我们的算法能够产生更加均匀的、无特殊纹理结构的图像。同时,各个跳跃产生的子路径可以被并行的处理。　　 3)提出了一种基于分段误差补偿的并行误差扩散算法　　 在S形扫描路径中像素点的数据依赖是全局性的,无法直接进行同步的并行化处理。而现在半色调图像质量最好的几种串行误差扩散算法均使用了S形扫描路径。本文提出了一种全新的并行处理方法,即通过交错顺序的分段处理和补偿间断点误差,可以将这些基于S形扫描路径的串行误差扩散算法改造成为基于同步的并行误差扩散算法。实验表明,改造后的并行算法输出的半色调图像可以达到和原串行算法输出图像相同的质量。由于受益于并行性,这种算法可以显著缩短半色调处理的运行时间。