Digital halftoning, or dithering, is the technique commonly used to render a color or grayscale image on a printer, a computer monitor or other bi-level displays. A particular halftoning technique that has been used extensively in the past is the so-called error diffusion technique. For a number of years it was believed that this technique is inherently sequential and could not be parallelized. In this paper we present and analyze a simple, yet optimal, error-diffusion parallel algorithm for digital halftoning and we discuss an implementation on a parallel machine. In particular, we describe implementations on data-parallel computers that contain linear arrays and two-dimensional meshes of processing elements. Our algorithm runs in 2?n+m parallel steps, a considerable improvement over the 10?m?n sequential algorithm. We expect that this research will lead to the development of faster printers and larger high-resolution monitors.
展开▼
机译：数字半色调或抖动是常用于在打印机上呈现颜色或灰度图像的技术，计算机监视器或其他双级显示。在过去使用广泛使用的特定半色调技术是所谓的误差扩散技术。有多岁，据信这种技术本质上是顺序的并且不能并行化。在本文中，我们展示并分析了一种简单，但最佳的误差扩散并行算法，用于数字半色调，我们讨论并行机器上的实现。特别是，我们描述了对包含线性阵列和处理元素的二维网格的数据并行计算机的实现。我们的算法在2？ n + m 并行步骤中，相当大的改进，10？ m ？ n 顺序算法。我们预计该研究将导致更快的打印机和更大的高分辨率监视器的开发。
展开▼
