Rotating non-rotationally symmetrical halftone dots for encoding embedded data in a hyperacuity printer

Description Submit all comments and votes

Cross reference is made to the following, commonly assigned, U.S. patent applications, filed Oct. 28, 1993, and are hereby incorporated by reference: U.S. application Ser. No. 08/144,856, filed Oct. 28, 1993, titled "Hyperacuity Printer Architecture", now U.S. Pat. No. 5,485,289; U.S. application Ser. No. 08/145,009, titled "Interlace Formatting in a Hyperacuity Printer"; Ser. No. 08/144,866, titled "Halftoning in a Hyperacuity Printer", now U.S. Pat. No. 5,410,414; Ser. No. 08/145,014, titled "Two Dimensional Linear Interpolation with Slope Output for a Hyperacuity Printer"; Ser. No. 08/145,011, titled "Two Dimensional Slope Thresholding in a Hyperacuity Printer"; Ser. No. 08/145,013, titled "Two Dimensional Linearity and Registration Error Correction in a Hyperacuity Printer". Also, included are U.S. application Ser. No. 08/155,727, titled "Variable Resolution Processing in a Hyperacuity Printer", filed Nov. 19, 1993 and U.S. application Ser. No. 08/166,327, titled "Micro Segmentation in a Hyperacuity Printer", filed Dec. 10, 1993.

BACKGROUND OF THE INVENTION

This invention relates to halftoning, and more particularly, to rotating non-rotationally symmetrical halftone dots for encoding embedded data in a hyperacuity printer.

Various optical and electronic techniques have been proposed for transforming continuous tone and other types of variably shaded monochromatic and polychromatic images (collectively referred to herein as "toneart images") into halftone images. To simplify this disclosure, substantial portions of the following discussion focus on monochromatic halftoning, but it is to be understood that the same general teachings apply to the halftoning of the color separations of polychromatic images. The halftoning of black and white "grayscale" images is a convenient example of monochromatic halftoning, so it is noted that the term "grayscale" is used herein as a generic descriptor for the tones that can be produced by mixing any two reference colors together in any desired proportions.

As is known, a halftone image is a binary image that is composed by writing "halftone dots" into a spatially periodic, two dimensional, tiled array of dimensionally identical "halftone cells." These halftone cells spatially correspond in the halftoned output image to respective small, spatially distinct areas of the source image. Furthermore, the surface area of the dot that is written into each of the halftone cells is modulated in accordance with a suitable measure of the perceived or "average" grayscale level of the spatially corresponding area of the source image (this "dot area" parameter typically is expressed by referring to the percentage of the halftone cell area that is filled by the halftone dot that is written therein). Thus, halftoning imparts an illusion of shading to the halftoned image because the halftone dots are written at a spatial frequency (usually called the "screen frequency") that exceeds the cyclical acuity of the human eye at normal viewing distances. A conservative rule of thumb is that the human eye is insensitive to cyclical contrast variations that occur at a spatial frequency in excess of about 40 cycles per degree within the field of view.

As will be appreciated, halftoning is an important tool for preserving the shaded appearance of toneart images that are printed using binary printing technologies. Optically screened lithographic halftoning processes have established a challenging benchmark for the imaging fidelity that can be achieved by printing halftoned images on high gamma, photosensitive recording media (i.e., a recording medium having a steeply sloped exposure vs. contrast characteristic). Modern xerographic printers utilize high gamma photoreceptors to print lineart images that approach the fidelity of lithographically printed lineart. Heretofore, however, the electronic halftoning processes that have been available for use in xerographic printers have not had sufficient imaging fidelity to enable xerographic printers to effectively compete with lithographic printing processes in the printing of high fidelity halftoned images. Xerographic printing has made significant inroads into the lithographic printing market because of its cost advantage and the improvements in its imaging fidelity. This trend is expected to continue, but it clearly will be necessary to further improve the fidelity of electronic halftoning for xerographic printers to become a fully acceptable alternative to lithographic printers for the printing of halftoned images.

Some workers have proposed electronic halftoning techniques that more or less directly emulate angularly oriented optical halftone screening functions. See, for example, Perriman et al. U.S. Pat. No. 3,997,911, which issued Dec. 14, 1976. Others have focused on modulating the size of the halftone dots that are written into tiled arrays of electronically generated halftone cells at a selected screen angle. See, for example: Hell et al. U.S. Pat. No. 3,688,033, which issued Aug. 29, 1972; Gall et al. U.S. Pat. No. 4,499,489, which issued Feb. 12, 1985; Dispoto et al. U.S. Pat. No. 4,680,645, which issued Jul. 14, 1987; and, Tai et al. U.S. Pat. No. 5,258,849, which issued Nov. 2, 1993. Also showing various ways of producing halftone dots are Shimano U.S. Pat. No. 4,912,568, which issued Mar. 27, 1990, and Hamilton U.S. Pat. No. 5, 233,441 which issued Aug. 3, 1993.

The invention described in co-pending U.S. patent application Ser. No. 08/144,866, titled "Halftoning in a Hyperacuity Printer" builds on these electronic halftone generators with their x/y addressable table lookup memories for tracking the scan spot as it scans across each of the electronically generated halftone cells at the selected screen angle.

However, as discussed in co-pending, commonly assigned, U.S. patent application titled "Method and Means for Embedding machine Readable Digital Data in Halftone Images" Ser. No. 07/634,990 to Tow, which is hereby incorporated by reference, by applying different angles of rotation to non-rotationally symmetric halftone dots while printing, various forms of encoding or embedded data into the the halftone structure can be implemented. Furthermore, in commonly assigned U.S. Pat. Nos. 5,128,525 to Stearns et al., and 5,221,833 to Hecht describe methods to embed data with certain shape codes called "glyph codes" which allow error detection and correction.

A circle is an example of a rotationally symmetric object. A rotation about its center cannot be detected by a change in its form or shape. On the other hand, an angular change in the orientation of a triangle, for instance, could be detected to some extent. There are varying degrees of angular change which can be detected. Whereas a circle can be rotated any amount about its center without detection, a square's symmetry only allows angular rotations about its center modulo 90 degrees to guarantee detection, and an equilateral triangle modulo 120 degrees. The invention described herein utilizes shapes that allow detection of their shape changes through rotation (hence, non-rotationally symmetric) after being input by appropriate scanning instruments, such as an input scanner.

Images are stored in a computer system as an array of pixels, each pixel being a multi-bit representation of the intensity of the original image at that position. Some pixels are represented by eight bit values, which provide a range of intensities from zero to 255, for example.

Halftone dots can be defined in three regions within this range for the purposes of explaining this invention. The highlight region is the range of densities where the halftone dot is small. The shadow region is the region where the dots are so large that the absence of dot coverage is small. In between these two extremes is the midrange of densities.

Since halftone dots grow from small highlight dots through the midrange densities to the dark shadow dots as the density of the image changes from high to low, and the shape of the dot cannot be controlled well in the highlight or shadow regions, it is only in the midrange of the densities that the shape has enough fidelity to be used to store data. Therefore, images that contain a lot of midrange densities can best contain embedded data.

Therefore, it would advantageous to have a halftoning system wherein a transformation (or rotation) on x-axis and y-axis coordinates of the address into the addressable table look-up memory relocates the memory access inside the halftone cell to a new location for purpose of rotating the halftone dot for embedding data.

The new location accessed by the rotation of the address coordinates could differ from the original location in all cases by a predetermined angle from a central point of rotation, while maintaining a constant radius from the central point of rotation. The angle would determine how much the halftone dot is rotated, where the point of rotation could be picked beforehand as the center of the halftone dot. Application of the transformation could rotate the halftone dot without affecting the screen frequency, screen angle or halftone dot density.

As will be seen, the hyperacuity printer described herein or the hardware halftoners mentioned in the referenced art are an appropriate way to perform such an o