Recent advances in digital halftoning and inverse halftoning methods

Halftoning is the rendition of continuous-tone pictures on displays, paper or other media that are capable of producing only two levels. In digital halftoning, we perform the gray scale to bilevel conversion digitally using software or hardware. In the last three decades, several algorithms have evolved for halftoning. Examples of algorithms include ordered dither, error diffusion, blue noise masks, green noise halftoning, direct binary search (DBS), and dot diffusion. In this paper, we first review some of the algorithms which have a direct bearing on our paper and then describe some of the more recent advances in the field. The dot-diffusion method for digital halftoning has the advantage of pixel-level parallelism unlike the error-diffusion method, which is a popular halftoning method. However, the image quality offered by error diffusion is still regarded as superior to most of the other known methods. We first review error diffusion and dot diffusion, and describe a recent method to improve the image quality of the dot-diffusion algorithm which takes advantage of the Human Visual System (HVS) function. Then, we discuss the inverse halftoning problem. Inverse halftoning is the reconstruction of a continuous tone image from its halftoned version. We give a brief review of the methods used in inverse halftoning, and discuss the advantadges of a recent inverse halftoning algorithm: Look-Up Table (LUT) Method for inverse halftoning. The method is extremely fast (no filtering is required) and the image quality achieved is comparable to the best methods known for inverse halftoning. The LUT inverse halftoning method does not depend on the specific properties of the halftoning method, and can be applied to any method. We then introduce LUT-based halftoning and tree-structured LUT (TLUT) halftoning. This algorithm involves only table look up operations but no arithmetic operations. We demonstrate how error-diffusion characteristics can be achieved with this method. Afterwards, our algorithm will be trained on halftones obtained by DBS which is an algorithm with high computational complexity. The complexity of TLUT halftoning is higher than that of error diffusion but much lower than that of the DBS algorithm. Thus, halftone image quality between that of error diffusion and DBS will be achieved depending on the size of tree structure in TLUT algorithm. Index Terms--DBS, dot diffusion, error diffusion, halftoning, HVS, inverse halftoning, LUT, ordered dither.