Abstract: In response to the issues of severe data dependency, low parallelism, and poor real-time performance of the mainstream digital halftone algorithm (the Floyd-Steinberg error diffusion algorithm) adopted in industry when dealing with increasingly large image data, an efficient computation algorithm is proposed. Firstly, a pre-generated pixel-error diffusion value lookup table is utilized to avoid frequent calculation of error and diffusion process. Secondly, memory access optimization is achieved through an efficient data structure based on row buffering. Then, a single instruction, multiple data (SIMD) parallel method for error accumulation is proposed, which uses AVX-512 instruction set parallelism to accumulate errors in the same direction for multiple pixels, enhancing the role of vector registers in the CPU. Finally, a multi core data parallelism method with edge error-constrained column blocking is implemented to eliminate errors caused by data dependency in boundary parts during data parallel processing. Experimental results demonstrate that the proposed algorithm exhibits good scalability, with computational performance linearly increasing with the optimal number of parallel cores. Compared with the traditional Floyd-Steinberg error diffusion algorithm, when processing a 5 120×5 120 grayscale image on a 16-core Intel CoreTM i7-11700 CPU platform, the proposed algorithm achieves a 15-fold performance improvement, completing the task in just 23 ms. This better meets the needs of industrial high-speed printing for large-scale, super-large format, ultra-high resolution, and varied content.

Key words: digital halftone, Floyd-Steinberg error diffusion, single instruction multiple data, parallel computing