A Caltech Library Service

Image halftoning and inverse reconstruction problems with considerations to image watermarking


Meşe, Murat (2001) Image halftoning and inverse reconstruction problems with considerations to image watermarking. Dissertation (Ph.D.), California Institute of Technology. doi:10.7907/561b-d051.


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. There are several well-known algorithms for half toning. The dot diffusion method for digital half toning has the advantage of pixel-level parallelism unlike the error diffusion method, which is a popular half toning method. The image quality offered by error diffusion is still regarded as superior to most of the other known methods. We show how the image quality obtained using the dot diffusion method can be improved by optimization of the so-called class matrix. By taking the human visual characteristics into account we show that such optimization consistently results in images comparable to error diffusion, without sacrificing the pixel-level parallelism. The dot diffusion algorithm will be discussed and by modifying the algorithm, embedded multiresolution property will be added. Later, we introduce LUT (Look Up Table) based half toning and tree-structured LUT (TLUT) halftoning. We 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) 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. We also discuss the inverse halftoning problem. Inverse halftoning is the reconstruction of a continuous tone image from its halftoned version. We propose two methods for inverse half toning of dot diffused images. The first one uses Projection Onto Convex Sets (POCS) and the second one uses wavelets. We then propose a novel and fast method for inverse halftoning called the Look Up Table (LUT) Method. The LUT for inverse halftoning is obtained from the histogram gathered from a few sample halftone images and the corresponding original images. For each pixel, the algorithm looks at the pixel's neighborhood (template) and depending upon the distribution of pixels in the template, it assigns a contone value from a precomputed LUT. 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 half toning method does not depend on the specific properties of the half toning method, and can be applied to any method. An algorithm for template selection for LUT inverse half toning is introduced. We also extend LUT inverse halftoning to color halftones. The next topic is image watermarking and 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 half toning before detection of watermark in half toned images and offer methods to improve watermark detection from halftoned images. Finally, we consider the optimal histogram modification with MSE metric and optimal codebook selection problem. Watermarking with histogram modification is one of the few watermarking methods which is robust to rotation and scaling. We formulate histogram modification problem as finding a transformation such that the error between the input and the output signal is minimized and the output signal has the desired histogram. It turns out that this problem is equivalent to the integer linear programming problem. Then, we formulate the problem of finding the optimal code book where the codewords can come from a finite set. The equivalent problem again turns out to be a linear integer programming problem and the solution is guaranteed to be globally optimal.

Item Type:Thesis (Dissertation (Ph.D.))
Subject Keywords:Electrical Engineering
Degree Grantor:California Institute of Technology
Division:Engineering and Applied Science
Major Option:Electrical Engineering
Thesis Availability:Public (worldwide access)
Research Advisor(s):
  • Vaidyanathan, P. P.
Thesis Committee:
  • McEliece, Robert J.
  • Divsalar, Dariush
  • Franklin, Joel N.
  • Perona, Pietro
  • Djokovic, Igor
Defense Date:3 May 2001
Funding AgencyGrant Number
Office of Naval Research (ONR)UNSPECIFIED
Record Number:CaltechTHESIS:02222011-105108216
Persistent URL:
Default Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:6252
Deposited By: Benjamin Perez
Deposited On:22 Feb 2011 19:22
Last Modified:16 Apr 2021 23:17

Thesis Files

PDF - Final Version
See Usage Policy.


Repository Staff Only: item control page