Parallel structure-aware halftoning

Structure-aware halftoning technique is one of the state-of-the-art algorithms for generating structure-preserving bitonal images. However, the slow optimization process prohibits its real-time application. This is due to its high computational cost of similarity measurement and iterative refinement. Unfortunately, the structure-aware halftoning cannot be straightforwardly parallelized due to its data dependency nature. In this paper, we propose a parallel algorithm to boost the optimization of the structure-aware halftoning. Our main idea is to exploit the spatial independence during the evaluation of the objective function and temporal independence among the iterations. Specifically, we introduce a parallel Poisson-disk algorithm during the selection of pixel swaps, which guarantees the independency between parallel processes. Graphics processing unit (GPU) implementation of the technique leads to a significant speedup without sacrificing the quality. Our experiments demonstrate the effectiveness of the proposed parallel algorithm in generating structure-preserving bitonal images with much less time, especially for large images.