Full Text:   <1630>

CLC number: TP391

On-line Access: 2013-12-06

Received: 2013-05-22

Revision Accepted: 2013-10-18

Crosschecked: 2013-11-18

Cited: 1

Clicked: 2550

Citations:  Bibtex RefMan EndNote GB/T7714

-   Go to

Article info.
1. Reference List
Open peer comments

Journal of Zhejiang University SCIENCE C 2013 Vol.14 No.12 P.918-929


An improved parallel contrast-aware halftoning

Author(s):  Ling-yue Liu, Wei Chen, Tien-tsin Wong, Wen-ting Zheng, Wei-dong Geng

Affiliation(s):  State Key Lab of CAD & CG, Zhejiang University, Hangzhou 310027, China; more

Corresponding email(s):   liulingyue@zju.edu.cn, wtzheng@cad.zju.edu.cn

Key Words:  Digital image halftoning, Error diffusion, GPU, Quantization, Space-filling curve

Ling-yue Liu, Wei Chen, Tien-tsin Wong, Wen-ting Zheng, Wei-dong Geng. An improved parallel contrast-aware halftoning[J]. Journal of Zhejiang University Science C, 2013, 14(12): 918-929.

@article{title="An improved parallel contrast-aware halftoning",
author="Ling-yue Liu, Wei Chen, Tien-tsin Wong, Wen-ting Zheng, Wei-dong Geng",
journal="Journal of Zhejiang University Science C",
publisher="Zhejiang University Press & Springer",

%0 Journal Article
%T An improved parallel contrast-aware halftoning
%A Ling-yue Liu
%A Wei Chen
%A Tien-tsin Wong
%A Wen-ting Zheng
%A Wei-dong Geng
%J Journal of Zhejiang University SCIENCE C
%V 14
%N 12
%P 918-929
%@ 1869-1951
%D 2013
%I Zhejiang University Press & Springer
%DOI 10.1631/jzus.C1300142

T1 - An improved parallel contrast-aware halftoning
A1 - Ling-yue Liu
A1 - Wei Chen
A1 - Tien-tsin Wong
A1 - Wen-ting Zheng
A1 - Wei-dong Geng
J0 - Journal of Zhejiang University Science C
VL - 14
IS - 12
SP - 918
EP - 929
%@ 1869-1951
Y1 - 2013
PB - Zhejiang University Press & Springer
ER -
DOI - 10.1631/jzus.C1300142

digital image halftoning is a widely used technique. However, achieving high fidelity tone reproduction and structural preservation with low computational time cost remains a challenging problem. This paper presents a highly parallel algorithm to boost real-time application of serial structure-preserving error diffusion. The contrast-aware halftoning approach is one such technique with superior structure preservation, but it offers only a limited opportunity for graphics processing unit (GPU) acceleration. Our method integrates contrast-aware halftoning into a new parallelizable error-diffusion halftoning framework. To eliminate visually disturbing artifacts resulting from parallelization, we propose a novel multiple quantization model and space-filling curve to maintain tone consistency, blue-noise property, and structure consistency. Our GPU implementation on a commodity personal computer achieves a real-time performance for a moderately sized image. We demonstrate the high quality and performance of the proposed approach with a variety of examples, and provide comparisons with state-of-the-art methods.

Darkslateblue:Affiliate; Royal Blue:Author; Turquoise:Article


[1]Analoui, M., Allebach, J.P., 1992. Model-based halftoning using direct binary search. SPIE, p.96-108.

[2]Bayer, B.E., 1973. An Optimum Method for Two-Level Rendition of Continuous-Tone Pictures. IEEE Int. Conf. on Communications, p.26-11-26-15.

[3]Billotet-Hoffmann, C., Bryngdahl, O., 1983. On the error diffusion technique for electronic halftoning. Proc. Soc. Inf. Display, 24(3):253-258.

[4]Chang, J.H., Alain, B., Ostromoukhov, V., 2009. Structure-aware error diffusion. ACM Trans. Graph., 28(5):162:1-162:8.

[5]Chang, T.C., Allebach, J.P., 2003. Memory efficient error diffusion. IEEE Trans. Image Process., 12(11):1352-1366.

[6]Eschbach, R., Knox, K.T., 1991. Error-diffusion algorithm with edge enhancement. J. Opt. Soc. Am. A, 8(12):1844-1850.

[7]Floyd, R.W., Steinberg, L., 1976. An adaptive algorithm for spatial grayscale. Proc. Soc. Inf. Display, 17(2):75-77.

[8]Knuth, D.E., 1987. Digital halftones by dot diffusion. ACM Trans. Graph., 6(4):245-273.

[9]Li, H., Mould, D., 2010. Contrast-aware halftoning. Comput. Graph. Forum, 29(2):273-280.

[10]Li, P.S., Allebach, J.P., 2004. Tone-dependent error diffusion. IEEE Trans. Image Process., 13(2):201-215.

[11]Li, P.S, Allebach, J.P., 2005. Block interlaced pinwheel error diffusion. J. Electron. Imag., 14(2):023007.

[12]Matković, K., Neumann, L., Neumann, A., Psik, T., Purgathofer, W., 2005. Global Contrast Factor—a New Approach to Image Contrast. Proc. 1st Eurographics Conf. on Computational Aesthetics in Graphics, Visualization and Imaging, p.159-167.

[13]Mitsa, T., Parker, K.J., 1992. Digital halftoning technique using a blue-noise mask. J. Opt. Soc. Am. A, 9(11):1920-1929.

[14]Neuhoff, D.L., Pappas, T.N., Seshadri, N., 1997. One-dimensional least-squares model-based halftoning. J. Opt. Soc. Am. A, 14(8):1707-1723.

[15]Ostromoukhov, V., 2001. A Simple and Efficient Error-Diffusion Algorithm. Proc. 28th Annual Conf. on Computer Graphics and Interactive Techniques, p.567-572.

[16]Pang, W.M., Qu, Y.G., Wong, T.T., Cohen-Or, D., Heng, P.A., 2008. Structure-aware halftoning. ACM Trans. Graph., 27(3):89:1-89:8.

[17]Ulichney, R., 1987. Digital Halftoning. MIT Press, Cambridge, MA.

[18]Ulichney, R.A., 1988. Dithering with blue noise. Proc. IEEE, 76(1):56-79.

[19]Velho, L., Gomes, J.D.M., 1991. Digital halftoning with space filling curves. ACM SIGGRAPH Comput. Graph., 25(4):81-90.

[20]Wang, Z., Bovik, A.C., Sheikh, H.R., Simoncelli, E.P., 2004. Image quality assessment: from error visibility to structural similarity. IEEE Trans. Image Process., 13(4):600-612.

[21]Wei, L.Y., 2008. Parallel Poisson disk sampling. ACM Trans. Graph., 27(3):20:1-20:9.

[22]Witten, I.H., Neal, R.M., 1982. Using Peano curves for bilevel display of continuous-tone images. IEEE Comput. Graph. Appl., 2(3):47-52.

[23]Wong, T.T., Hsu, S.C., 1995. Halftoning with Selective Precipitation and Adaptive Clustering. In: Paeth, A.W. (Ed.), Graphics Gems V (IBM Version). Morgan Kaufmann, Burlington, USA, p.302-313.

[24]Wu, H.S., Wong, T.T., Heng, P.A., 2013. Parallel structure-aware halftoning. Multim. Tools Appl., 67(3):529-547.

[25]Zhang, Y.F., Webber, R.E., 1993. Space Diffusion: an Improved Parallel Halftoning Technique Using Space-Filling Curves. Proc. 20th Annual Conf. on Computer Graphics and Interactive Techniques, p.305-312.

[26]Zhou, B.F., Fang, X.F., 2003. Improving mid-tone quality of variable-coefficient error diffusion using threshold modulation. ACM Trans. Graph., 22(3):437-444.

[27]Zhou, Y., Chen, C., Wang, Q., Bu, J.J., 2009. Block-Based Threshold Modulation Error Diffusion. Proc. 16th IEEE Int. Conf. on Image Processing, p.2033-2036.

Open peer comments: Debate/Discuss/Question/Opinion


Please provide your name, email address and a comment

Journal of Zhejiang University-SCIENCE, 38 Zheda Road, Hangzhou 310027, China
Tel: +86-571-87952783; E-mail: cjzhang@zju.edu.cn
Copyright © 2000 - Journal of Zhejiang University-SCIENCE