Shortest Path-based Gray Level Selection for Minimum Halftone Noise

Abstract

Halftone techniques, which represent full gray levels using fewer gray levels than required, are used for various printing applications such as newspapers, journals, and photographs. Recently, people began to use the halftone techniques to enhance the gray level representation of display devices such as plasma display panels (PDPs) and medical display devices. PDPs employ the halftone techniques because they need to use fewer gray levels in order to reduce the false contour noise. On the other hand, the medical display devices use the halftone techniques for representing full gray levels as the gray depth of a medical image is higher than that of an output image displayed on the devices. Although the halftone techniques improve the quality of image representation, they also induce the halftone noise. Since the halftone noise can be quite noticeable in many cases, especially in case of still images or slowly moving images, it is desirable to suppress it as much as possible.This dissertation presents a new approach to selecting the optimal gray levels using a special-case shortest path algorithm. The proposed approach suppresses the halftone noise by selecting optimal gray levels adaptively for a given input image. The proposed method uses a shortest path algorithm for selecting optimal gray levels, which finds the shortest path containing a given number of nodes on it. Unfortunately, the existing shortest path algorithms find a shortest path regardless of the number of nodes on it. Thus, we propose a new special-case shortest path algorithm that finds the shortest path containing only a specified number of nodes on it. The proposed method consists of two steps for selecting optimal gray levels: constructing a graph representing the halftone noise and finding optimal gray levels using the special-case shortest path algorithm. The proposed method for optimal gray level selection can be used to minimize the halftone noise on several types of display devices that employ the halftone techniques. In this dissertation, two subfield coding methods developed for PDP applications using the proposed gray level selection method are presented: adaptive incremental subfield coding for PDPs and adaptive subfield weight selection for active glasses-type 3D PDPs.The incremental subfield coding methods sacrifice the number of gray levels to use in order to remove the false contour noise. Instead, they use halftone techniques to represent full gray levels, and the halftone noise is induced. The proposed adaptive incremental subfield coding (AISC) suppresses the halftone noise, while completely removing false contour noise like the existing incremental subfield coding methods. Experimental results, using 109 test images, illustrated that the AISC method improved PSNR by 4.4~6.2dB on the average in the halftone noise, when compared to the existing incremental subfield coding methods. The hardware requirement to implement AISC is a capability to process data at 45 MFLOPS. A modem microprocessor or a DSP can sufficiently perform the proposed method in real time.The adaptive subfield weight selection (ASWS-3D) uses the proposed optimal gray level selection method to suppress the halftone noise of the active glasses-type 3D PDPs. The ASWS-3D method consists of two steps: finding the optimal gray levels for minimum halftone noise and determining the optimal subfield weights to implement the selected gray levels. Experimental results using 1,146 test images illustrated that the ASWS-3D method improved PSNR by 7.22dB and reduced the perception probabilities of visible differences by 36.38% on the average in the halftone noise, when compared to the existing subfield coding method with fixed subfield weights. We also compared the proposed ASWS-3D method to the exact quadratic programming in terms of PSNR of simulated images for the halftone noise. Experimental results using 1,146 test images illustrated that, in case of the halftone noise, the proposed method reduced the PSNR by 0.24dB and reduced the perception probabilities of visible differences by 3.55% on the average, when compared to the quadratic programming. It is known that the false contour noise also accounts for the total image noise on PDPs. In the experiment to estimate the total image noise of halftone noise and false contour noise, the proposed ASWS-3D improved PSNR by 2.08~6.87dB on /the average, when compared to the existing subfield coding method with fixed subfield weights.