Printing
Compound Document Labeling and Enhancement for Copiers
In a nutshell laser-based copiers hook up scanners to laser printers. Thanks to the lighting element in the scanner a copier tends to be a high input-SNR environment so that denoising is usually superfluous in a basic pipeline. Regardless, there can be some hairy complications in this otherwise innocuous sounding hookup.
Problems primarily arise from printed input documents. The printing process uses halftoning and many input documents will have large halftone regions that depict color/grayscale variations. Halftones are these tiny little dots/lines/patterns that look like nice continuum of variations to the eye but that can overwhelm a copier pipeline because of their tendency to produce Moire patterns when directly printed.
In a copier one wants to make a very nice copy of the input, nicer than the original if possible. One hence wants to enhance text/graphics (a sharpening or high-frequency boosting operation) and antialias halftones (a smoothing or low-pass filtering operation). These are of course conflicting goals when documents contain both halftones and text/graphics, and more importantly, when text/graphics overlap halftone regions. (If you blur too much text or noticeably sharpen halftones you violate the goal.) A way to separate text/graphics from halftones is needed.
The issue with the separation is that halftones can look remarkably like small font text, especially like small font Chinese characters. Halftones having different directions/dots/lines/etc. can morph and look very different from periodic dots. While halftoning tends to be uniform over a printer output channel, one can never count on it being so. Besides, a printer's idea of cyan/magenta/yellow can be quite different from the actual color. (Printers use color tables to convert their "CMYK" to our notion of CMYK. Print a cyan page, most likely it will be a superposition of several of the printer's color primitives.).
This work uses very low computation and memory to solve this complex problem. It can be thought of as doing multi-scale edge/singularity processing. Noting that documents are meant to be read by humans (yes, this is the rocket science part :) it simulates HVS with an appropriate low-pass filter (lpf). Edge detection at the lpf output marks most of the meant-to-be-seen edges/graphics. Subtracting that output from the output of a fine edge detector directly applied to the input (that indiscriminately marks up all high frequencies, i.e., edges/graphics/halftones) results in output that primarily consists of halftones.
The project accomplishes further refined labeling and robust enhancement based on the detected labels.
Line buffered, fixed-point computations that need less than 1% of full-page memory (active memory requirements ~.02% of full-page memory). ~98% detection with under 2% false alarm.
Needs few magic parameters and is surprisingly resilient (see sensitivity analysis in the published JEI article - not included in the pre-print below.) The key "documents are meant to be read" observation (the rocket science part :) again works in one's favor. One can quite readily calculate just noticeable differences and work out edge-detection thresholds for example.
Font Smoothing and Super-resolution using Over-complete Wavelet Dictionaries and Lookup Tables
Rendering high resolution fonts and maintaining high pages-per-minute (ppm) are at odds in inexpensive printing pipelines.
High resolution font rendering takes significant computation which is not desirable in a printer. If one rendered in a more computation-friendly environment say, in the computer trying to print, one would then have to deal with bandwidth to the printer, buffering, and related slow-downs.
Laser printers have an internal sub-dpi resolution that can be taken advantage of in rendering sharper fonts. (Think of a dot as a pulse and sub-dpi as smaller pulses that can be obtained through pulse-width-modulation.) It is difficult for standard font engines to take advantage of this resolution since it is very printer dependent and very nonlinear in operation (how narrower pulses will stick or not stick on paper can be very unintuitive.)
Comment: Some key differences between displays and printers in my opinion: (i) In printers you write once so you only have one try to get it right (no temporal processing, delays, tricks, etc.), (ii) except for the most charitable companies you are never allowed to use anything even remotely close to full-page memory, (iii) "finish processing asap, that line is printing already!" (no looking ahead, no multi-pass, no varying computation across the output), (iv) allowed computational envelope is super tight, (v) most importantly what you think you are printing and what comes out of the printer tend to be very, very different (IMO, display transfer functions are much, much more manageable in comparison).
This project tries to find solutions to the questions: Can one obtain high resolution fonts from low resolution fonts? Can one do so despite many nonlinearities in the system?
Font smoothing and super-resolution accomplished through boundary smoothing.
1-D boundary curves super-resolved using wavelets (one can show that wavelets are optimal in handling 1-D functions with singularities, e.g., corners/seriffs in font boundaries).
Boundary smoothing distilled into small look-up-tables that allow computationally simple online operation. (Super-resolution computations using over-complete wavelet dictionaries are done offline and results stored in LUTs.)
Chromatic Aberrations in Scanners
Scanners can have color aberrations which result in light color distortions in the scanned output. When the output gets aggressively enhanced (as is done in a copier) these light distortions can become quite noticeable and significantly hurt perceived quality.
The color distortions are scanner specific and can vary slightly with time and varying ambient temperatures (we found, for example, that summer time may have different behavior then winter time).
The distortions primarily vary spatially in the scanned output.
This project designs a fast algorithm to compensate for spatially varying aberrations. It does so by differentially warping the color channels, say G and B, with respect to a master color channel, say R, on every printed page.
It infrequently, e.g., when the copier is being serviced, generates calibration data and uses that (or a scanner specific default) to reduce/eliminate color distortions. Calibration data is the 1-D warp/flow that aligns each color channel to the master color channel.
For the above examples the work automatically corrects the left and right sides while leaving the middle unperturbed.
Patents:
O. G. Guleryuz, “Method and Apparatus for Segmentation of Compound Documents,” issued, July 2006. Assigned to Seiko-Epson Corporation. Patent no: 7,079,687.
O. G. Guleryuz, “Method and Apparatus for Segmentation of Compound Documents Having Low Resolution Halftones,” issued, May 2006. Assigned to Seiko-Epson Corporation. Patent no: 7,043,078.
O. G. Guleryuz and A. Bhattacharjya, “Fast Text/Graphics Resolution Improvement with Chain-Code Table Look-Up,” issued, August 2005. Assigned to Seiko-Epson Corporation. Patent no: 6,927,780.
J. Huang, O. G. Guleryuz, A. Bhattacharjya, and J. Shu, “Pwm Rendering for Color/Gray-Scale Text and Graphics for Laser Printer,” issued, September 2007. Assigned to Seiko-Epson Corporation. Patent no: 7,265,876.
O. G. Guleryuz, “Methods and Systems for Correcting Color Distortions,” issued, April 2009. Assigned to Seiko-Epson Corporation. Patent no: 7,525,702.
Papers:
O. G. Guleryuz, “ A Low Complexity Comprehensive Labeling and Enhancement Algorithm for Compound Documents,” Journal of Electronic Imaging, vol. 13, no. 4, pp. 832-859, October 2004, {pdf}.
O. G. Guleryuz and A. Bhattacharjya, “Fast Text/Graphics Resolution Improvement Using Wavelet-Based Denoising and Chain-Code Table Lookup,” Proc. IEEE Int’l Conf. on Image Proc. (ICIP2002), Rochester, NY, Sept. 2002, {pdf}.
J. Huang, O. Guleryuz, A. Bhattacharjya, and J. Shu, “Pulse-width Modulation for Rendering Color Text and Graphics for Laser Printer,” Proc. NIP18: Int’l Conf on Digital Printing Technologies San Diego, CA, Sept. 2002.