Image halftoning and inverse reconstruction problems with considerations to image watermarking

In this work, we first discuss the image halftoning problem. Halftoning is the rendition of continuous-tone pictures on displays that are capable of producing only two levels. The dot diffusion halftoning method has the advantage of pixel-level parallelism unlike the popular error diffusion method whose halftone quality is still regarded as superior to most of the other known methods. We show how the image quality obtained using dot diffusion can be improved by optimization of the so-called class matrix so that the image quality comparable to error diffusion can be achieved. Later, we introduce LUT (Look Up Table) halftoning and tree-structured LUT halftoning. We demonstrate how different halftoning algorithms including high computational complexity algorithms can be imitated with this algorithm. Thus very good halftone image quality can be achieved with a much lower computational complexity.; We also discuss the inverse halftoning problem. Inverse halftoning is the reconstruction of a continuous tone image from its halftone. We propose two methods for inverse halftoning of dot diffused images. We then propose a novel and extremely fast method for inverse halftoning called the LUT Method. The LUT is obtained from the histogram gathered from sample halftone images and the corresponding original images. For each pixel, the algorithm looks at the pixel's neighborhood and depending upon the distribution of pixels, it assigns a contone value from a precomputed LUT. The image quality achieved is comparable to the best methods known for inverse halftoning. This method can be applied to any halftoning method.; Next topic is effects of halftoning on watermarked images. Watermarking is the process of embedding a secret signal into a host signal in order to verify ownership or authenticity. We discuss the effects of applying inverse halftoning before detection of watermark in halftoned images and offer methods to improve watermark detection from halftoned images.; Finally, we consider the histogram modification problem which is used in watermarking and codebook selection problem. We show that optimal histogram modification problem and the problem of finding the optimal codebook where the codewords can come from a finite set are integer linear programming problems.