基于openmp实现的误差扩散算法

《基于openmp实现的误差扩散算法》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、基于OpenMP实现的误差扩散算法张春柳1,2李嘉2熊璟21（上海理工大学上海200093）2（上海市计算机软件评测重点实验室上海201112）摘要误差扩散算法是一种常用的数字半色调技术，但传统的误差扩散算法是典型的串行算法。本文在传统误差扩散的基础上，针对误差扩散的像素扩散的原理，叙述了基于线程延迟和基于图像划分的两种误差扩散的并行化算法，并使用OpenMP进行实现。实验结果证明误差扩散算法的并行化是可行的，且是十分高效的，具有良好的应用前景。.jyqkImplementedbyOpenMPZHANGChunliu1

2、,2LIJia2XIONGLu21(UniversityofShanghaiforScienceandTechnology,Shanghai200093,China)2(ShanghaiKeyLab.ofputerSoftp;Testing,Shanghai201112,China)AbstractErrordiffusionalgorithmisakindofdigitalhalftoningtechnologyusedmonly,hoisatypicalserialalgorithm.Basedonthetradi

3、tionalerrordiffusionalgorithmandaccordingtotheprincipleofpixelerrordiffusion,thispaperdescribest,oneisbasedonthethreaddelayandtheotherisbasedontheimagepartition.FinallyplementtheparallelalgorithmbyOpenMP.Theexperimentalresultsshoisfeasible,andisefficientandhasex

4、cellentapplicationprospective.KeyP,ParallelProgrammingDesign0引言半色调技术，也称加网技术，是图像处理领域历史最悠久的技术之一[1]。加网技术最初始于19世纪晚期，当人们尝试着使用设备在纸张上打印文字和图像时，这种技术应运而生了。尤其是印刷工业诞生以来，它作为印刷过程中最核心的环节一直受到学术界和产业界的极大关注，并且经历了漫长的发展过程。由于人们把这个由灰度图像得出二值图像的过程看作是在原始图像上增加了一个网屏进行处理，因此称其为“加网技术”，又因为在激光印

5、字、照相复制及各种印刷中，由于要用二值输出表示图像的阶调层次，故又称半色调技术。更为具体的中文定义是，数字半色调技术是基于人眼的视觉特性和图像的成色特性，利用数学、计算机等工具，在二值设备或多色二值设备上实现图像再现的一门技术，是将连续调图像经过处理后用二值图像实现图像阶调再现的基础性研究闭。半色调技术应用于印刷工业已有一个多世纪，应用在数字输出设备上也有40多年，如今已广泛应用到打印、印刷、显示设备以及数字图像的压缩存储、图像的传输等领域。数字半色调技术是一种与计算机应用相结合的技术，用来在单色显示打印设备上产生不同

6、灰度的视觉效果，或在彩色显示打印设备上产生彩色视觉效果。这种技术主要取决于如何更合理地对图像区进行分组，并更合理地在每一个由多个像素组成的分组中分配黑白像素比例（对单色显示打印设备）或几种彩色像素比例（对彩色显示打印设备）。由于这些分组很小（通常仅仅是几个像素的级别），因此人眼会将其视为一种由分组中几种颜色共同混合而成的某种单一颜色。这就解决了如何在8位显示设备上显示24位或32位颜色的问题。误差扩散法是数字半色调技术的一种主要方法[2]。它是由Floyd和Steinberg于1976年首次提出的，并一举成为当时处理效

7、果最好的半色调方法。误差扩散法的出现是半色调技术史上重要的里程碑，它带来了革命性的技术变革，并促进了半色调技术的飞速发展。误差扩散处理后的半色调图像中像素点的分布是各向异性和无规律的，因而色调丰富，视觉效果好。直到今天，它依然以其视觉效果好、易于实现等特征被认为是最理想的半色调算法之一。图1a是8位灰度图，图1b是经误差扩散处理后的2位半色调图，在这种分辨率下，二者的质量没有明显差异，表现出了良好的相似性。图2a、图2b分别将图1a、图1b的细节放大，这时我们发现，两幅图像之间的差异非常大，右侧的2位半色调图像的质量只

8、能用粗糙来形容了。1OpenMP简介OpenMP是多处理机上编写并行程序而设计的应用编程接口[2]。它由一个编译器命令集组成，其中包括了一套编译制导语句和一个函数库。OpenMP提供了并行描述的高层抽象方法大大降低了并行程序编写的难度和复杂度，从而编程人员可以将更多的精力投入到算法本身的并行化设计中，而非具体实现细节。对基于数据分