Combining Digital Halftoning With Sub-pixel Screen

Whitepaper: Combining Digital Halftoning With Sub-Pixel Screen Rendering By Robert M. Case, updated November 14, 2009 ABSTRACT: A method is shown for maintaining quality and reducing file size of transmitted color images by combining digital halftoning with sub-pixel screen rendering. By first creating a lossy digital halftone with acceptable quality and secondarily losslessly compressing the halftone image prior to transmission, a reduction in the bandwidth necessary for color images is achieved. Applications include static web pages and eBooks as well as dynamic video. SPECIFICATION: Current Internet image compression and rendering methods treat image file size and image quality as a trade-off. The JPEG specification and its offshoots offers user-defined percentage compression resulting in quality reduction. Because the user cannot foretell if acceptable quality will be maintained, relatively small reductions are selected, resulting in larger image files than necessary. By far the largest "hog" of Internet "pipes" is image files. From the standard web page to portable documents to Flash animations, images clog today's Internet. The purpose of this paper is to offer an alternative method that separates image quality from image file size. This method combines a primarily subtractive printing process known as halftoning with a primarily additive display process known as sub-pixel rendering. There are two forms of halftoning: photographic halftoning, a process evolving since the 1850's, and digital halftoning, a relatively recent development dating to the 1970's. Briefly, all halftoning uses a high frequency/low frequency dichotomy. In photographic halftoning, the low frequency attribute is a local area of the output image designated a halftone cell. Each equal-sized cell relates to a corresponding area (size and location) of the continuous-tone input image. Within each cell, the high frequency attribute is a centered variable-sized halftone dot composed of ink or toner. The ratio of the inked area to the non-inked area of the output cell corresponds to the luminance or gray level of the input cell. From a suitable distance, the human eye averages both the high frequency apparent gray level approximated by the ratio within the cell and the low frequency apparent changes in gray level between adjacent equally-spaced cells and centered dots. Digital halftoning uses a raster image or bitmap within which each monochrome picture element or pixel may be on or off, ink or no ink. Consequently, to emulate the photographic halftone cell, the digital halftone cell must contain groups of monochrome pixels within the same-sized cell area. The fixed location and size of these monochrome

pixels compromises the high frequency/low frequency dichotomy of the photographic halftone method. Clustered multi-pixel dots cannot "grow" incrementally but in jumps of one whole pixel. In addition, the placement of that pixel is slightly off-center. To minimize this compromise, the digital halftone monochrome pixels must be relatively small. However, digital image processing has also enabled more sophisticated dithering algorithms to decide which pixels to turn black or white. Working on dithering algorithms, research discovered popular methods could be improved. While it was apparent that a checkerboard pattern reproduced the smoothest 50 per cent gray, how to reproduce the rest of the luminance spectrum was not. A method of initiating the output image with a checkerboard pattern was discovered. For local areas, black pixels are turned white to reproduce lighter areas of the input image and white pixels are turned black to reproduce darker areas of the input image (Method for reproducing an image - US Patent 6002493.) By maintaining the checkerboard, transitions from light to dark became more gradual and less noticeable. Another problem with digital halftoning is what to do with differential errors between the local area of the input image and the reduced palette of the corresponding area of the output image. The most popular method still in use today is "error diffusion" discovered by Floyd and Steinberg in the mid-1970's. In that method, errors in previous scan line pixels are spread to subsequent scan line pixels. However, a major problem occurs when small errors accumulate and subsequently drop in areas where the differences become noticeable. To rectify this, a means of interpolating the errors within the halftone cell was discovered, essentially linking macro and micro error underages and overages (Reverse diffusion digital halftone quantization - US Patent 7457002.) Similar to JPEG and other imaging methods, digital halftoning achieves small file sizes in a lossy manner. The key here is to achieve acceptable quality at the final halftone prior to compressing and, from that point, using lossless methods. Because of the above mentioned differences between photographic and digital halftoning, compressing halftones heretofore has proven difficult and computationally expensive. The result is that nearly all digital halftoning currently is done at the client printer from downloaded bitmap images. Work was begun on a method of compression suitable for halftones. The result was a variable-length run-length lossless method that utilizes pixel patterns and Fibonacci exponents to reduce file size (None-of-the-above digital halftone compression and decompression - US Patent 7286264.) Coupled with widely-used partial pattern matching algorithms, digital halftones are able to be losslessly compressed to between 1 and 2 bits (and less) per 24-bit "true color" input pixel. In printing color photographic halftones, four images are utilized, one for each of the subtractive inks (cyan, magenta, yellow, and black). These images are printed in a

standard rotation around a halftone cell axis. Digital color halftones, relying on bitmaps, are much more difficult to force into this axis rotation. It is well-known that luminance is the primary component of the image with color being secondary. Work was begun on integrating color into the luminance (black/white) digital halftone Separating out the luminance, and using it for the base halftone, made color, which is less spatially-sensitive, able to be woven into the luminance image with acceptable results (Method for colorizing a digital halftone - US Patent 7623264.) The result is a pre-compression 3-bit-per-pixel (8 colors) bitmap that displays well on-screen at subpixel levels. Due to cell size, photographic halftoning has not worked on typography and vector images, but digital halftoning can be adjusted to do so. If all font and vector outlines are made to fall on the base checkerboard, their bitmap representations became sharper and simpler (Method for checkerboard-based vector to raster conversion - US Patent Application 20090033678). The above methods may be used for "rich documents" with both images and typography displayed simultaneously similar to a printing plate. Sub-pixel screen rendering has been utilized in the past decade for optimizing the reproduction of fonts (ClearType.) The size of screen pixels has in recent years been reduced with nominal Macintosh 72-pixels-per-inch and Windows 96-ppi being supplanted by the 150-ppi of the iPhone and even 200-ppi screens recently announced. Display screen pixels are bit-dependent with 24-bit "true color" at the high end (16 million colors per pixel) to 8-bit Internet palettes at the low end (216 colors per pixel). The above specified output digital halftone method displays 3-bit pixels in a sub-pixel 2x2 grid, generating a nominal 4,000 colors per input pixel). The results compare favorably with 16-bit methods (65,000 colors per pixel) due to reverse diffusion causing adjacent pixels to be correlational. The Internet currently uses for drawing the screen a combination of vectors (fonts and drawings) and bitmaps (images) to reduce transmitted file size. The relative placement of these elements ultimately is dependent on the browser and the assembly method. The result is a hodgepodge of resolutions and pages that look different on different browser/ OS combinations. The above specified method resolves not only transmitted file-size and client machine re-assembly, but also overall "look-and-feel" issues. However, with a totally image-based Internet, word search would be more difficult but not impossible. Most web page displays already have Unicode or ASCII files associated and, for those that do not, recent accuracy improvements in optical character recognition permit such files to be attached to the image.

With regard to video, it appears the simplified final halftone image relates better to inter-frame compression than more complex images. Not only will YouTube style video and Internet television benefit, but turning-page mechanisms for eBooks as well. CONCLUSION: The combination of digital halftoning with sub-pixel screen rendering shows promise to simplify digital transmission by reducing the size of images, while maintaining image quality and integrity. Further reading: "Cashing In On Electronic Books," by Mark Nelson Copyright Robert M. Case