Tree-structured method for LUT inverse halftoning and for image halftoning

Recently, the authors proposed a Look Up Table (LUT) based method for inverse halftoning of images. The LUT for inverse halftoning is obtained from the histogram gathered from a few sample halftone images and corresponding original images. Many of the entries in the LUT are unused because the corresponding binary patterns hardly occur in commonly encountered halftones. These are called nonexistent patterns. In this paper, we propose a tree structure which will reduce the storage requirements of an LUT by avoiding nonexistent patterns. We will demonstrate the performance on error diffused images and ordered dither images. Then, we introduce LUT based halftoning and tree-structured LUT (TLUT) halftoning. Even though TLUT method is more complex than LUT halftoning, it produces better halftones and requires much less storage than LUT halftoning. We will demonstrate how error diffusion characteristics can be achieved with this method. Afterwards, our algorithm will be trained on halftones obtained by Direct Binary Search (DBS). The complexity of TLUT halftoning is higher than error diffusion algorithm but much lower than DBS algorithm. Also, the halftone quality of TLUT halftoning increases if the size of TLUT gets bigger. Thus, halftone image quality between error diffusion and DBS will be achieved depending on the size of tree-structure in TLUT algorithm.