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 顺序算法。我们希望这项研究将导致更快的打印机和更大的高分辨率显示器的发展。
展开▼
