Facsimile and static presentation processing – Static presentation processing – Attribute control
Reexamination Certificate
1998-08-06
2001-01-09
Rogers, Scott (Department: 2724)
Facsimile and static presentation processing
Static presentation processing
Attribute control
C358S001900, C358S296000
Reexamination Certificate
active
06172769
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to descreening halftoned images and to printing a halftoned picture on different printers with different characteristics.
2. Background Description
Most printers today can print in only a limited number of colors. Digital halftoning is a technique for printing a picture (or more generally displaying it on some two-dimensional medium) using small dots with a limited number of colors such that it appears to consist of many colors when viewed from a proper distance. For example, a picture of black and white dots can appear to contain grey levels when viewed from some distance. For the sake of simplicity, the rest of the discussion will be restricted to the case of grayscale images and their rendering by black and white printers to facilitate the presentation, but those skilled in the art of digital halftoning will understand that the principles apply to color images as well. When we speak of ink, it could mean any material and/or mechanism which produces the black in the image, i.e., it could be toner for a xerographic printer, ink for an inkjet printer, etc.
We will be concerned with bilevel, fixed pixel size printers (for instance laser printers). Such printers have two fundamental characteristics:
1) The print resolution, say d dpi (dots per inch), which can be interpreted as saying that the intended fundamental units of the print are arranged on a grid of squares with each square or pixel of size 1/d inches by 1/d inches, where d typically varies from about 300 to about 3000. In some cases, the pixels lie on a rectangular grid, but since the discussion adapts equally well to this case, we will assume square pixels for definiteness.
2) The dot gain which tells us how the actual printed pixel (or dot) differs from a perfect 1/d by 1/d square in shape and size (notice that in previous sentences, the word “dot” was used in a loose sense). While many printers perform differently, standard theory and much of the prior art on calibration, e.g., “MECCA-A Multiple-Error Correction Computation Algorithm for Bi-Level Image Hardcopy Reproduction”,
IBM Res. Rep.
, RZ1060 (1981) by P. Stucki, “Measurement of Printer Parameters for Model-based Halftoning”,
J. El. Imag.,
2(3) (1993) 193-204, by T. N. Pappas, C. K. Dong and D. L. Neuhoff, and U.S. Pat. No. 5,649,073 to Knox, Hains and Sharma, assumes that printed dots can be reasonably described as round, say with diameter D (or as an ellipse in the case of a rectangular grid), and the dot gain is often described accordingly.
In the sequel, we make the assumption that no printed dot goes beyond a circle with diameter 2/d centered at the middle of the pixel where it is intended to be printed (a circular dot which covers an entire 1/d by 1/d square has diameter at least {square root over (2)}/d. This assumption is made to simplify the discussion and in particular the description of the invention. Adaptation to a more general case is tedious to describe but not difficult to implement by anyone skilled in the art of digital printing.
As taught in the invention disclosed in U.S. patent application Ser. No. 09/085,094 filed by A. R. Rao, G. R. Thompson, C. P. Tresser, and C. W. Wu on May 26, 1998, for “Microlocal Calibration of Digital Printers”, both the probabilistic nature of individual dot printing and the way printing neighboring dots in various configurations affect the dot shapes can be captured by a calibration method. This method characterizes a printer by the probability distribution of what area of ink gets printed at each pixel depending on the configuration of dots to be printed in the neighborhood of that pixel (here we use the word “ink” as a generic name for what gets printed, such as ink or toner). In the sequel, whenever we speak of printer characteristic, we mean the characteristic as given by the method of calibration of digital printers, except where otherwise specified. The probabilistic nature of such printer characterization means in particular that the notation “fixed pixel size” for a printer refers to its idealized properties rather than to actual ones.
Consider now some grayscale image to be printed with a digital printer. We assume an image of size h by v, where h and v are expressed in inches to be consistent with the unit used in the dpi description. It is then convenient to interpret this image as a matrix, I, of size H=h×d by V=v×d in the following way:
one thinks of the image as covered by little squares of size 1/d by 1/d (also called pixels).
each pixel p, can be designated by its horizontal ordering number i (say from left to right) and it vertical ordering number j (say from top to bottom). Thus, the location of p is specified by the pair (i,j).
to the pixel at (i,j) one assigns the value g between 0 and 1, where 0 corresponds to white, 1 corresponds to black, and more generally, g corresponds to the grey level of this particular pixel.
the matrix I is then defined by setting I(i,j)=g.
Given a matrix such as I, a digital halftoning algorithm will associate to it an H by V halftone matrix M whose entries M
(i,j)
are either 0 or 1. Now 0 means that no dot will be printed by the digital printer at pixel (i,j), while a 1 means that a dot is to be printed.
A grayscale image can thus be considered as an array I of B-bit numbers, where typically B ranges from 4 to 12. Because M is an array of single bits of the same size as I, straightforward storage of M instead of I represents a factor B in compression. It often happens that the original grayscale image I is not available and only the halftone (or printing decision) matrix M is retained. Usually, because different printers have different characteristics, a given M will produce different images when used with two different printers. One solution to this problem is to generate an approximation to the original grayscale image I while taking into account the printer characteristics, P, and halftone this approximation taking into account the printer characteristics of a second printer. This invention discloses a method to generate this approximation.
The process of re-creating a grayscale image from a halftoned image is called descreening or inverse halftoning. In all rigor, inverse halftoning is more general since it does not presuppose that halftoning has been done with a screen (or dithering mask), but for brevity, we shall use “descreening” as an equivalent, general term. Early methods of descreening were optical, such as in U.S. Pat. No. 4,231,656 to Dickey et al. Digital methods based on matrices such as M, for instance in U.S. Pat. No. 4,630,125 to Roetling have been proposed, as well as digital methods using a scanned image, such as in European Patent Publication 301,786 to Crosfield or in U.S. Pat. No. 4,907,096 to Stanfield et al.
Because halfoning is based on the spatial integration properties of human vision, a common descreening process consists in (weighted) averaging of the grey levels in the neighborhood of each pixel (i,j) (for example, the neighborhood can be a rectangle centered at (i,j)). To have an image independent process, the averaging is done in the neighborhood of each pixel in the same way (except maybe the boundaries of the image). We shall assume a constant neighborhood and constant weights in the sequel for simplicity, but our invention adapts as well to the more general case. The size and shape of the neighborhood where averaging is performed (or NAP for short in the sequel) is quite crucial, in particular in the case when M has been obtained using a dithering mask. Original averaging methods used pre-determined fixed cell assumptions, which are clearly drawbacks, but as taught in the invention described in U.S. patent application Ser. No. 09/110,900 filed on Jul. 6, 1998, by G. R. Thompson, R. Rao and F. C. Mintzer for “Method and Apparatus for Repurposing Binary Images”, the sole knowledge of M is enough to precisely recover the cell size for screened halftones. In the simplest cases, such masks have a single cell as a
Rao Ravishankar
Thompson Gerhard Robert
Tresser Charles Philipe
Wu Chai Wah
Behpour Golam
International Business Machines - Corporation
Kaufman, Esq. Stephen C.
Rogers Scott
Whitham, Curtis & Whitham
LandOfFree
Printer dependent descreening method does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Printer dependent descreening method, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Printer dependent descreening method will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2555069