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 ofcontinuous-tone pictures on displays that are capable of producing only two levels. Thereare several well-known algorithms for half toning. The dot diffusion method for digitalhalf 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 isstill regarded as superior to most of the other known methods. We show how the imagequality obtained using the dot diffusion method can be improved by optimization of theso-called class matrix. By taking the human visual characteristics into account we showthat such optimization consistently results in images comparable to error diffusion, withoutsacrificing the pixel-level parallelism. The dot diffusion algorithm will be discussed andby 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 thismethod. Afterwards, our algorithm will be trained on halftones obtained by Direct BinarySearch (DBS) which is an algorithm with high computational complexity. The complexityof TLUT halftoning is higher than that of error diffusion but much lower than that of theDBS algorithm. Thus, halftone image quality between that of error diffusion and DBS willbe achieved depending on the size of tree structure in TLUT algorithm.We also discuss the inverse halftoning problem. Inverse halftoning is the reconstructionof a continuous tone image from its halftoned version. We propose two methods forinverse 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 forinverse halftoning called the Look Up Table (LUT) Method. The LUT for inverse halftoningis obtained from the histogram gathered from a few sample halftone images and thecorresponding 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 assignsa contone value from a precomputed LUT. The method is extremely fast (no filtering isrequired) 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 specificproperties of the half toning method, and can be applied to any method. An algorithm fortemplate selection for LUT inverse half toning is introduced. We also extend LUT inversehalftoning 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 toverify ownership or authenticity. We discuss the effects of applying inverse half toning beforedetection of watermark in half toned images and offer methods to improve watermarkdetection from halftoned images.Finally, we consider the optimal histogram modification with MSE metric and optimalcodebook selection problem. Watermarking with histogram modification is one of the fewwatermarking methods which is robust to rotation and scaling. We formulate histogrammodification problem as finding a transformation such that the error between the input andthe output signal is minimized and the output signal has the desired histogram. It turnsout that this problem is equivalent to the integer linear programming problem. Then, weformulate the problem of finding the optimal code book where the codewords can come froma finite set. The equivalent problem again turns out to be a linear integer programmingproblem and the solution is guaranteed to be globally optimal.

[发布机构] University:California Institute of Technology;Department:Engineering and Applied Science

[关键词] Electrical Engineering