## 1.

## Introduction

Most digital color printers operate in a binary mode, where for each color separation, a given pixel is written as a colored spot or it is not written. The human visual system provides the illusion of continuous color tones by spatial averaging of the printed colored spots and intermediate space. Digital halftoning controls the printing of the colored spots and, therefore, defines the appearance of the halftone output. The most common halftone method is screening, which compares requested continuous tone levels to predetermined threshold levels typically defined over a rectangular cell that is tiled to fill the image plane. The output of the screening process is a binary pattern of multiple small “dots,” which are regularly spaced as determined by the addressability of the imaging system. Marking processes such as electrophotography and offset printing typically cluster the small dots (or activated pixels) within a cell because the larger clustered mass prints with more consistent size and density than spots printed with individual isolated pixels. The alignment of the clusters via the halftone-cell tiling defines the geometry of the halftone screen. The resulting halftone structure is a two-dimensionally (2D) repeated pattern, possessing two fundamental spatial frequencies that are completely determined by the geometry of the halftone screen.

A common problem in digital color halftoning is the potential manifestation of moiré patterns. *Moiré* is an undesirable interference pattern that can occur when two or more color halftone separations are printed in overlay. The interference occurs mainly due to the nonlinearity of color mixing of subtractive colorants. Another cause of moiré is development suppression of one colorant by another colorant. As a result, low frequency components can be visibly evident as pronounced interference patterns in the halftone output. To avoid moiré due to misalignment, misregistration, or other related printing conditions, different halftone screens are typically used for different color separations and the fundamental frequency vectors of the different halftone screens are separated by relatively large angles. Given a large angular separation, the vector frequency difference between any two fundamental frequencies of the different screens will be large enough so that no visibly objectionable moiré patterns are produced.

In the printing industry, there is a classical screen combination that provides suitable angular separation for two-colorant printing under most print conditions and provides moiré-free printing for three-colorant printing. This combination consists of three screens constructed by halftone cells that are square in shape, are of identical frequency, and are placed one each at
$15$
,
$45$
, and
$75\phantom{\rule{0.3em}{0ex}}\mathrm{deg}$
.^{1}

The difficulty in avoiding objectionable moiré between halftone screens becomes more challenging when considering that four colorants are used in most printing presses. The four colorants are typically cyan (C), magenta (M), black (K), and yellow (Y). The classical 15/45/75 screen configuration is commonly used for C, M, and K, but screening methods for Y are often less than optimal. One common clustered-dot Y halftone configuration employs a 0-deg screen with a frequency that is
$\approx 10\%$
higher than the other screens.^{2} Under some printing conditions, low contrast moiré can be seen in images printed by such halftone configuration for certain combinations of yellow and other colorants. Another common configuration for Y halftoning uses a stochastic screen or error diffusion. The small isolated dots produced by those methods can result in a high degree of instability when used by many common printing processes. The result is inconsistency of page-to-page color and nonuniformity of color within a page.

There are several high quality, or enhanced, printing applications that require more than four image separations. For example, *high fidelity* (hi-fi) color printing typically uses one or more additional primary colorants to extend the gamut of a print engine. Two common choices of additional primaries are orange and green, but other colorants, such as red, blue, and violet may be used. A well-known example of high fidelity printing is Pantone Hexachrome printing. *Low chroma* printing employs an additional toner or ink with the same or similar hue as a conventional toner. For example, low chroma magenta may be used along with conventional magenta to enable smoother tone gradations and reduced texture in flesh tones compared to using conventional magenta alone. Typical low chroma, or light, colorants include light magenta, light cyan, and gray. Other
$>4$
-colorant enhanced printing methods may employ special colorants, such as white, metallics, and fluorescents, and may have applications in security and special imaging effects.

Due to moiré considerations associated with additional clustered-dot halftone screens, the alternatives currently available for enhanced printing with
$>4$
-channel halftoning suffer from color instability, undesirable halftone structure appearance, or limitations on applications. For example, stochastic screens and error diffusion have been used for hi-fi colorant and low chroma toners, but the small dot sizes tend to produce unstable results for xerography and offset printing. Line screens have also been used, but the line structure tends to be considered undesirable unless used at very high frequencies, which, on the other hand, can be unstable. Some methods use the same screen or same screen frequencies and angles for a hi-fi colorant and for its complimentary colorant (e.g., same screen for cyan and orange), but that method can place limitations on the color management operations and strict requirements on color-to-color registration, and it does not readily apply to low chroma toners.^{3, 4}

The understanding of moiré becomes even more complicated, and the solutions more challenging, when you consider that clustered dot halftoning produces 2D repeated binary patterns. A periodic binary structure contains frequency components other than the fundamentals. Because these harmonics can possess strong amplitude, moiré caused by interference between the various harmonics can be pronounced and unacceptable for certain colorant combinations. Moiré, and moiré within halftones in particular, has been studied extensively. One example is by Amidror ,^{5} where a spectral model based on Fourier analysis was used to explain the moiré due to the superimposition of halftone screens. Amidror further developed an algorithm for moiré minimization, which included minimization of moiré due to interference of high-order harmonics. However, most halftone screen designs, including the classical three-color moiré-free solution, can satisfy only the moiré-free condition for moiré between fundamental frequencies of two or three colors.

One aspect of halftone screen interference that has received much less study is the micromoiré, or rosette pattern, that forms for three superimposed overlapping rotated halftone screens. Several publications in this area analyze rosette formation for the classical three-colorant combination.^{6, 7} Amidror and Hersch^{8} investigated the properties of rosettes and found conditions under which the microstructure varies or is invariant under relative shifts of the superimposed layers.

In this paper, we propose a novel screen configuration, the uniform-rosette configuration, for true moiré-free $N$ -colorant halftoning. Instead of finding solutions as trade-offs between the contradictory tendencies of the various potential moiré frequencies, this new configuration completely eliminates all moiré from all possible colorant combinations. As a result, the halftone output for multiple colorants exhibits a unique 2D spatially periodic structure, a uniformly repeated hexagon-shaped rosette.

We start with a basic frequency analysis of halftone patterns and moiré in Sec. 2. We use the classical three-color moiré-free solution to demonstrate the spectra of different halftone structures and their superimposition. We describe the moiré-free conditions using frequency vectors that represent individual halftone screens. In Sec. 3, we present uniform-rosette halftoning. We first introduce the concept using a halftone configuration similar to the classical moiré-free solution, but using identical *rectangular* halftone cells of a particular dimension placed at 15, 45, and
$75\phantom{\rule{0.3em}{0ex}}\mathrm{deg}$
, rather than square cells. A general definition of the uniform-rosette configuration is then provided using a lattice conceptualization and nonorthogonal halftones. (Here, the term *nonorthogonal* should be understood as not necessarily orthogonal. So, the square and rectangular halftone screens are not excluded.^{9}) The method is then extended to halftone configurations for
$N$
colorants. In Sec. 4, we translate the frequency-vector specifications for the uniform-rosette configurations to the form of spatial vectors, which defines the geometry of the halftone screens. The spatial vectors allow us to find digital solutions for uniform-rosette configurations using single-cell nonorthogonal halftone screens for color printers with limited resolutions. An example of a practical configuration is described and illustrated. Section 5 discusses the misregistration insensitivity of uniform rosettes, and Sec. 6 briefly summarizes the paper.

## 2.

## Frequency Analysis of Halftone Patterns

## 2.1.

### Frequency Representation

In conventional halftone screening, a halftone cell is replicated to tile across the entire image plane to form a screen that is applied to threshold image pixel values. With any constant input, the halftone output of this halftone screen is a 2D spatially periodic function. From Fourier analysis,^{10} it is understood that such a periodic function can be described as a 2D Fourier series composed of two fundamental frequency vectors and their higher-order harmonics, which are linear integer combinations of the two fundamental frequency vectors.

For the following discussion of moiré elimination, we focus on the locations of the fundamental halftone frequency vectors and their 2D harmonics and ignore the amplitude and phase of each component. For example, the three halftone patterns shown in Fig. 1 demonstrate the outputs of halftoning the C, M, and K separations where the halftone dots provide approximately 30% area coverage. The example illustrates the results from screens constructed of rotated square halftone cells at 75, 15, and $45\phantom{\rule{0.3em}{0ex}}\mathrm{deg}$ , respectively, in the classical three-color moiré-free configuration. The frequency representations, or the Fourier transforms, of the three 2D periodic halftone patterns of Fig. 1 are illustrated by the three plots of Fig. 2 , where we use circular dots to indicate locations of all discrete frequency components including the fundamentals and all high-order harmonics within the frequency limits specified by the plots. Subscript 1 and subscript 2 notations are used as a convention to refer to frequency vectors that are above (0 to $90\phantom{\rule{0.3em}{0ex}}\mathrm{deg}$ ) or below (270 to $360\phantom{\rule{0.3em}{0ex}}\mathrm{deg}$ , or equivalently $-90$ to $0\phantom{\rule{0.3em}{0ex}}\mathrm{deg}$ ) the 0-deg axis, respectively. Unless otherwise noted, we use subscripts $c$ , $m$ , $y$ , and $k$ , to aid in teaching the presently described halftoning processes due to the common practice of four-color printing with cyan, magenta, yellow, and black. Even though we are teaching using that notation, the concepts are general so that other colorants may be used. For example, we may use the notation ${\mathbf{f}}_{m1}$ and use examples that refer to it as a frequency vector for the magenta screen, but it is to be understood that we intend it to generally imply a frequency vector in the first quadrant for some available colorant. Further, we note that colorants for particular screen geometries are interchangeable. For example, we may have yellow halftoned with a screen of a first geometry, and black halftoned with a screen of a second geometry, but it is practical and reasonable to assume that the screens may be interchanged and yellow may be halftoned with the screen of the second geometry and black with the first.

Note that the jargon of the field of halftoning can cause some confusion when discussing screen geometries. *Orthogonal* typically refers to screens constructed of square halftone cells, but screens with cells that are not restricted to square shapes are referred to as *nonorthogonal*. *Orthogonality* does not refer to a 0- and 90-deg alignment of the cells to the grid. Rectangular cells, although geometrically orthogonal, have often been referred to as nonorthogonal halftones due to their departure from classical square shapes.

## 2.2.

### Moiré-Free Conditions

In color printing, more frequency components than the fundamental frequencies are typically created in the halftone image due to the superimposition of halftone screens for different process colors. Using Fourier analysis, we can express the result caused by such superimposition of two different colorants as their frequency-vector combination; for example, ${\mathbf{f}}_{cm}={\mathbf{f}}_{c}+{\mathbf{f}}_{m}$ , where ${\mathbf{f}}_{x}$ represents any of ${\mathbf{f}}_{x1}$ , $-{\mathbf{f}}_{x1}$ , ${\mathbf{f}}_{x2}$ , $-{\mathbf{f}}_{x2}$ , and ${\mathbf{f}}_{cm}$ is the combined vector. The sign definition of frequency vectors is rather arbitrary because each Fourier component has its conjugate; that is, there is always a frequency vector $-{\mathbf{f}}_{c}$ that represents the conjugate component of ${\mathbf{f}}_{c}$ . There are two fundamental frequency vectors for each halftone dot screen, thus the color mixing of two screens for two different colors yields eight unique combined vectors for the fundamental frequency vectors. Considering the other harmonics of the halftone frequency vectors, the combinations can yield a large number of difference vectors. In Fig. 3 , the superimposition of the cyan and magenta halftone patterns depicted in Fig. 1 is shown on the left, and its frequency representation is on the right. The frequency spectrum of the mixed colors is quite complicated and is certainly not a 2D periodic function as are the single-color spectra shown in Fig. 2, and this explains why the halftone pattern of the superimposition in Fig. 3 cannot be described as tiling a simple cell as it does in the monochromatic cases.

When the superimposition involves three colors, typically, C, M, and K, the situation becomes even more complex. As shown in Fig. 4
, the halftone pattern, often referred to as the *rosette pattern*, is not a simple repeated pattern. Although the fundamental frequencies follow a simple relationship, arrayed at equal angular spacing on a circle in the frequency domain, the set of harmonics and combination of frequency components is significantly more complicated than that for the two-color case, as can be seen in the right sides of Figs. 3 and 4. It has been proved that the rosette pattern resulting from such a halftone configuration is theoretically nonperiodic.^{1} In other words, the rosette pattern never repeats on the same page.

The common strategy to avoid objectionable two-color moiré is to select frequency vectors that ensure that no two-color difference vector of the fundamental halftone frequency vectors is sufficiently small, or short in length, to be perceived as a noticeably low frequency. The two-color moiré-free condition can be summarized by

where ${\mathbf{f}}_{c}$ represents any one of ${\mathbf{f}}_{c1}$ , $-{\mathbf{f}}_{c1}$ , ${\mathbf{f}}_{c2}$ , $-{\mathbf{f}}_{c2}$ ; ${\mathbf{f}}_{m}$ represents any one of ${\mathbf{f}}_{m1}$ , $-{\mathbf{f}}_{m1}$ , ${\mathbf{f}}_{m2}$ , $-{\mathbf{f}}_{m2}$ ; and ${f}_{high}$ is a frequency limit set somewhere between 50 and $70\phantom{\rule{0.3em}{0ex}}\mathrm{cycles}\u2215\mathrm{in.}$ for just noticeable moiré.It is well known that a troublesome moiré is the three-color moiré, which can appear in cyan-magenta-black prints produced by CMYK four-color printers. As an extension of the two-color case, one aspect of the three-color moiré-free condition can be summarized by

where ${\mathbf{f}}_{k}$ represents any one of ${\mathbf{f}}_{k1}$ , $-{\mathbf{f}}_{k1}$ , ${\mathbf{f}}_{k2}$ , $-{\mathbf{f}}_{k2}$ ; and ${f}_{high}$ is set similar to the two-color case. There are altogether 64 combinations that can be obtained by drawing one from ${\mathbf{f}}_{x1}$ , $-{\mathbf{f}}_{x1}$ , ${\mathbf{f}}_{x2}$ , $-{\mathbf{f}}_{x2}$ for $x$ equal to each of $c$ , $m$ , $k$ , but the 64 combinations contain positive and negative conjugate pairs, so in practice we consider 32 unique frequency vectors of interest. Due to the large number of frequency components, it stands as a matter of practicality that to make all three-color difference vectors as well as all two-color difference vectors large enough to avoid any color moiré is very difficult, unless the halftone screens have very high frequency fundamentals, say higher than $200\phantom{\rule{0.3em}{0ex}}\mathrm{cycles}\u2215\mathrm{in.}$ Another approach to achieving the moiré-free condition is to make two of the three-color difference vectors null while keeping the rest large. Given that both the signs and the indices of frequency vectors are defined somewhat arbitrarily, without losing the generality, the three-color moiré-free condition can be specified by the following vector equation: or, equivalently due to the conventional screen configuration,Equations^{3a, 3b}are two of all the possible frequency combinations of the three colors. In most practical applications, the rest of the combinations satisfy the inequality of Eq.

^{2}for ${f}_{high}$ as large as $\mathrm{min}[\mid {\mathbf{f}}_{c}\mid ,\mid {\mathbf{f}}_{m}\mid ,\mid {\mathbf{f}}_{k}\mid ]\u22152$ and are not specially specified, and the combination of halftone outputs produces a rosette appearance rather than an objectionable moiré. The vector additions of Eq.

^{3}are illustrated in Fig. 5 .

Most conventional halftone screens use square-shaped halftone cells for tiling. Therefore, the two fundamental frequency vectors of each screen are not independent of each other. Once one of the two equations, Eqs. ^{3a} or ^{3b}, is satisfied, the other one is automatically held. Recently, we have taught halftone methods^{9} using nonorthogonal halftone cells, or general parallelogram-shaped halftone cells, to construct halftone screens for moiré-free color halftoning, in which case the two fundamental frequencies of each parallelogram-shape–based screen are independent of each other and thus satisfying both Eqs. ^{3a, 3b} is required for the three-color moiré-free condition.

It is also worth pointing out that the three-color moiré-free condition described by Eqs. ^{3a, 3b} is specified for the fundamental frequencies only. However, although it is understood that as a practical matter, fundamental frequencies are always more important than higher-order harmonics, there is never-the-less no guarantee that the moiré caused by combining with high-order harmonics from different colors would not be observable. It is very desirable to have all moirés eliminated, regardless of whether they are caused by the combining of fundamental frequencies only or of any harmonics.

## 3.

## Uniform Rosettes

## 3.1.

### Uniform Rosettes Using Rectangular Halftone Screens

We introduce the uniform, hexagonal rosette halftone configuration using a modification of the previously described classical configuration. Assume again halftone screens rotated to 15, 45, and
$75\phantom{\rule{0.3em}{0ex}}\mathrm{deg}$
, respectively, for three different colors. In the present example, the halftone screens are selected to satisfy Eq. ^{3}, but are constructed of rectangular cells having a specific side-length relationship, rather than square cells. The monochromatic halftone outputs of this configuration, shown as C, M, and K halftone patterns, and their spectra are shown in Figs. 6 and 7
. The halftones have similar appearances as the ones of the classical configuration shown in Fig. 1 with the difference being that the repeated halftone pattern in the current case is a rectangular cell with a specific ratio between the lengths of the two sides equal to 0.866, or exactly
$\mathrm{cos}(30\xb0)$
. The frequency representations of the halftone patterns shown in Fig. 6 are illustrated by the three plots in Fig. 7. Due to the rectangular structure of the cells having this
$\mathrm{cos}(30\xb0)$
side-length relationship, the two fundamental frequency vectors of each pattern are perpendicular to each other and the ratio of the two frequencies is also equal to
$\mathrm{cos}(30\xb0)$
.

Figure 8 shows the superimposition and frequency representation of the C and M halftone patterns of Fig. 6. Despite the similarity between monochromatic images in Figs. 1 and 6, the superimposition halftone pattern in Fig. 8 reveals significant differences. The difference is even more evident in the superimposition of three colors, as shown in Fig. 9 . An examination of the rosette in Fig. 9 reveals a uniform, hexagonal structure, whereas the conventional superimposition of Fig. 4 showed irregular, aperiodic rosettes. The perfect periodicity of the uniform rosettes is consistent with the absence of moiré: there exists no frequency lower than the frequency defined by the strictly periodic rosettes. An interesting observation can be made from the frequency representation of the halftone superimposition. In the frequency representation of the three-colorant superimposition in Fig. 9, fundamental frequencies and harmonics of each monochromatic screen are illustrated by dots of the color of that screen. Gray dots indicate a frequency formed by the interactions of multiple screens. All frequency components, including all fundamental frequencies and the respective harmonics of the monochromatic halftones, and frequencies due to all possible color combinations, can be located on a hexagonal lattice in the Fourier representation. The lattice can be seen by drawing a line connecting the nearest neighbors of any point in the spectrum.

The uniform, hexagonal rosettes possess a much simpler texture that can be more visually pleasing than aperiodic rosettes. To understand this property, consider the lowest frequency components of the superimpositions of uniform rosettes compared to classical rosettes. The human visual system has a visual transfer function (VTF) that attenuates high frequency components. For suitably high frequency halftones (e.g., $200\phantom{\rule{0.3em}{0ex}}\mathrm{cycles}\u2215\mathrm{in.}$ ), the perception of the uniform rosette is almost completely suppressed by the VTF. Hence, the halftone texture is barely perceived because there are no lower frequencies present in this configuration. In a classical rosette configuration, a multitude of low frequency components exists and can be perceived even when high frequency halftones are employed. We note that a contrary condition can exist for low frequency halftones. The periodicity of the uniform rosette could be well resolved by the human visual system and be objectionable, but the aperiodicity of the classical configuration can suppress the perception of halftone structure.

Though the present example constructed uniform rosettes from rectangular halftone cells having a specific side-length ratio, below we present more general frequency-vector relationships that generate uniform rosettes.

Classical halftone rosettes possess different morphologies depending on the relative shift of the halftone screens. The examples of Fig. 4 aligned the screens such that the center of the holes (white space) between halftone dots are coincident at a reference point in space for the different colorants. This type of alignment produces what is known as *clear-centered rosettes*. We see from Fig. 9 that the uniform-rosette configuration can also be aligned to produce clear-centered rosettes. Similar correspondences occur for uniform-rosette and classical-rosette morphologies for other displacements of the colors. Examples of dot-centered rosettes are shown in Fig. 10
. The focus of the present paper is deriving moiré-free halftone screen sets using the uniform-rosette geometry. The focus is not on displacement-induced changes in rosette morphology, so we limit the remainder of the examples to clear-centered rosettes.

As indicated earlier, unlike halftone outputs by the classical configuration and most other halftone methods, the multiple-color halftone patterns produced by the uniform-rosette configuration with spatially constant input colors are 2D periodic patterns. These periodic patterns can be fully described as a discrete 2D Fourier series with two fundamental frequencies, or rosette frequency vectors, ${\mathbf{f}}_{R1}$ and ${\mathbf{f}}_{R2}$ . Other than the zero-frequency component, there are no frequencies lower than the two fundamentals in the Fourier series. In the current example, ${\mathbf{f}}_{R1}={\mathbf{f}}_{k1}\u22152$ and ${\mathbf{f}}_{R2}={\mathbf{f}}_{c2}\u22152$ . All fundamental frequency vectors defining the three different halftone screens for C, M, and K are harmonics, or linear integer combinations, of the rosette fundamental frequency vectors. Similarly, all higher-order harmonics of the three individual halftones are also linear integer combinations of the rosette fundamental frequencies. As described previously, the interference due to color mixing results in new frequency components that are the combinations of frequency vectors of individual colorants. Because all frequency components of individual colorants in the uniform-rosette configuration are harmonics of rosette fundamental frequencies, there are no components created by color mixing that are not harmonics defined by rosette fundamental frequencies. With a uniform-rosette configuration, all frequency components, regardless of the number of colorants and the order of harmonics, fall on the 2D hexagonal grid defined by the two rosette fundamental frequency vectors. Thus, the frequency representations of Figs. 8 and 9 are much simpler and freer of low frequency components than the classical cases shown in Figs. 4 and 5. In other words, moiré-free conditions are satisfied for all color mixing, as well as for all harmonics. As a result, uniform-rosette halftoning is completely moiré-free.

## 3.2.

### Lattice Description of the Uniform-Rosette Configuration

The uniform-rosette halftone configuration is based on defining rosette fundamental frequency vectors, of sufficiently high frequency and angle separation, that can be used to generate a hexagonal lattice of rosette harmonics. To avoid objectionable low frequency texture due to excessively large rosettes, we require

## Eq. 4

$$\mid {\mathbf{f}}_{R1}\mid >{f}_{min},\phantom{\rule{1em}{0ex}}\mid {\mathbf{f}}_{R2}\mid >{f}_{min},\phantom{\rule{1em}{0ex}}\mid {\mathbf{f}}_{R1}\pm {\mathbf{f}}_{R2}\mid >{f}_{min}.$$To better understand this rosette vector concept, consider the example of Fig. 9, redrawn in Fig. 11
with rosette vectors
${\mathbf{f}}_{R1}$
,
${\mathbf{f}}_{R2}$
shown as red arrows, and the lowest frequency components of the rosette are shown as circles. It is easy to see that the set of lowest frequency components form the vertices of a hexagon. We refer to the hexagon formed by the lowest frequency components as the *first-order spectral hexagon*. The halftone fundamental frequencies as well as their conjugate fundamental frequency vectors are also shown in Fig. 11. The figure shows that the set of all halftone fundamental frequencies can be connected to form a hexagon, illustrated in Fig. 11 as a thin black line. The halftone fundamental frequencies form the vertices as well as define points that roughly bisect the sides of the hexagon. This hexagon connects the frequency components that lie just outside of the first-order spectral hexagon. We refer to this hexagon as the *second-order spectral hexagon*. The relationships between the screen frequency vectors and rosette vectors are given by

## 5.

## Eq. 5a

$${\mathbf{f}}_{\mathrm{c}1}=2{\mathbf{f}}_{\mathrm{R}1}-{\mathbf{f}}_{\mathrm{R}2}={\mathbf{f}}_{\mathrm{R}1}-{\mathbf{f}}_{\mathrm{R}12},\phantom{\rule{1em}{0ex}}{\mathbf{f}}_{\mathrm{c}2}=2{\mathbf{f}}_{\mathrm{R}2},$$^{5a, 5b, 5c, 5d}"/> define a uniform-rosette configuration with all six halftone fundamental frequencies for three colorants and their conjugates “evenly” distributed angularly.

## 3.3.

### Uniform Rosettes for an Arbitrary Number of Colorants

Though it is interesting and useful to produce uniform, hexagonal screen sets for three colorants, the hexagonal structure can be readily extended to moiré-free printing for the conventional four-colorant CMYK printing. Further, the formalism can address the difficult problem of $N$ -colorant printing.

A mathematical statement of the general principle of $N$ -halftone lattice-based screen configurations can be written by considering the frequency lattice structure defined by rosette vectors ${\mathbf{f}}_{\mathrm{R}1}$ , ${\mathbf{f}}_{\mathrm{R}2}$ . For a screen configuration with $N$ halftone screens, let ${\mathbf{f}}_{i1}$ , ${\mathbf{f}}_{i2}$ , respectively, denote first and second fundamental frequency vectors for screens $i=1,2,\dots ,N$ , where ${\mathbf{f}}_{i1}$ , ${\mathbf{f}}_{i2}$ are chosen to satisfy

## Eq. 6

$$({\mathbf{f}}_{i1},{\mathbf{f}}_{i2})=({m}_{i1}{\mathbf{f}}_{\mathrm{R}1}+{m}_{i2}{\mathbf{f}}_{\mathrm{R}2},{n}_{i1}{\mathbf{f}}_{\mathrm{R}1}+{n}_{i2}{\mathbf{f}}_{\mathrm{R}2})$$## Eq. 7

$$\mid {\mathbf{f}}_{ik}\mid >\mathrm{max}[\mid {\mathbf{f}}_{\mathrm{R}1}\mid ,\mid {\mathbf{f}}_{\mathrm{R}2}\mid ,\mid {\mathbf{f}}_{\mathrm{R}12}\mid ].$$To better understand the $N$ -colorant uniform-rosette halftone configuration, consider extending the rectangular cell example of Fig. 6 to a six-colorant configuration, where the fourth, fifth, and sixth colorants are chosen to be yellow, red, and green, respectively. Exemplary $m$ and $n$ values that are consistent with the present teaching are as follows:

Cyan: | ${m}_{c1}=2$ | ${m}_{c2}=-1$ | ${n}_{c1}=0$ | ${n}_{c2}=2$ |

Magenta: | ${m}_{m1}=1$ | ${m}_{m2}=1$ | ${n}_{m1}=-2$ | ${n}_{m2}=2$ |

Black: | ${m}_{k1}=2$ | ${m}_{k2}=0$ | ${n}_{k1}=-1$ | ${n}_{k2}=2$ |

Yellow: | ${m}_{y1}=3$ | ${m}_{y2}=-2$ | ${n}_{y1}=1$ | ${n}_{y2}=2$ |

Red: | ${m}_{r1}=2$ | ${m}_{r2}=1$ | ${n}_{r1}=-2$ | ${n}_{r2}=3$ |

Green: | ${m}_{g1}=3$ | ${m}_{g2}=-1$ | ${n}_{g1}=-1$ | ${n}_{g2}=3$ |

^{5}:

## 8.

## Eq. 8a

$${\mathbf{f}}_{\mathrm{y}1}=3{\mathbf{f}}_{\mathrm{R}1}-2{\mathbf{f}}_{\mathrm{R}2},\phantom{\rule{1em}{0ex}}{\mathbf{f}}_{\mathrm{y}2}={\mathbf{f}}_{\mathrm{R}1}+2{\mathbf{f}}_{\mathrm{R}2},$$Halftone screen outputs for the fourth, fifth, and sixth screens are shown in Fig. 12 , and the respective fundamental frequency vectors are shown in Fig. 13 . In Fig. 13, it can be seen that the fundamental frequency vectors of these fourth, fifth, and sixth screens deviate from the second-order spectral hexagon. Superimpositions of halftone outputs are shown in Fig. 14 . Figure 14 shows cyan, magenta, black, and yellow; Fig. 14 shows yellow, red and green; and Fig. 14 shows the superimposition of all six colorants. Observe that a regular rosette pattern is formed in all cases and no moiré is present.

Often, it is desirable to avoid dot-off-dot/dot-on-dot configurations due to misregistration sensitivity. That can be achieved by specifying halftone fundamental frequency vectors such that any ( ${\mathbf{f}}_{i1}$ , ${\mathbf{f}}_{i2}$ ) vector pair is not equal to any other ( ${\mathbf{f}}_{j1}$ , ${\mathbf{f}}_{j2}$ ) vector pair. That is, no two screens possess identical fundamental frequency vector pairs. On the other hand, if dot-off-dot/dot-on-dot screens are desired, say for reasons of increased gamut or reduced texture, then at least one ( ${\mathbf{f}}_{i1}$ , ${\mathbf{f}}_{i2}$ ) vector pair is specified to equal another ( ${\mathbf{f}}_{j1}$ , ${\mathbf{f}}_{j2}$ ) vector pair.

It can be desirable to use screens that do not require large $\mid m\mid $ or $\mid n\mid $ , say $>6$ or 8, because the frequency of those screens might be beyond the resolution of common printing processes, but note that certain high resolution processes (e.g., high resolution proofers) may allow a much higher frequency. To achieve a balance between minimizing visibility and maximizing stability, it is often desirable to have particular screens at a relatively low frequency, but not as low as the rosette frequency. For example, screens could be chosen such that

## 9.

In some cases, a screen may possess low visibility due to the hue of the colorant or amount of colorant required. For example, the human visual system has low acuity for yellow. In such cases, the low visibility screen can be defined by small values of $m$ and $n$ , e.g., one or both of the yellow vectors could equal a rosette vector, ${\mathbf{f}}_{y1}={\mathbf{f}}_{R1}$ , ${\mathbf{f}}_{y2}={\mathbf{f}}_{R2}$ , where ${m}_{y1}=1$ , ${m}_{y2}=0$ , ${n}_{y1}=0$ , ${n}_{y2}=1$ .

Ishii^{11} includes a fourth screen in a halftone configuration in a moiré-free manner by setting its frequency vectors to be the same as the frequency vectors of two other screens (e.g.,
${\mathbf{f}}_{y1}={\mathbf{f}}_{k1}$
,
${\mathbf{f}}_{y2}={\mathbf{f}}_{c1}$
). Because no new frequency vectors are added to the system, no new moiré components are generated. Also note that the fourth screen shares vectors from two different screens, so it is angularly displaced from any one screen. This angular displacement allows the screen to possess a degree of color-shift insensitivity to misregistration similar to other rotated screen designs. Further, note that at least one screen must not be orthogonal to achieve such frequency vector sharing.

Frequency vector sharing can be employed within the uniform-rosette configuration. For example, a first screen can be included in the configuration by setting a first fundamental frequency vector of that screen to be equal to a first fundamental frequency vector of a second screen, but not setting its second fundamental frequency vector equal to the second fundamental frequency vector of the second screen. Because the first screen does not share both fundamental frequency vectors of the second screen, it is still angularly displaced from that second screen. This angular displacement allows the screen to possess color-shift insensitivity to misregistration similar to other rotated screen designs.

Line screens can be employed within the uniform-rosette configuration by selecting $m$ and $n$ values for a given screen such that one halftone fundamental frequency vector of the pair has length $0(\mid {\mathbf{f}}_{i}\mid =0)$ .

## 4.

## Digital Implementation of the Uniform-Rosette Configuration

To implement any moiré-free periodic clustered-dot halftone configuration, it is critical to have very specific and accurate rotation angles for the halftone screens. For example, an angular error of a few tenths of a degree within the classical configuration leads to a moiré period on the order of a few inches. Unfortunately, in digital halftoning, the selection of possible rotations for halftone screens is greatly restricted by the digital grid, or raster, defined by the location of physical pixels. In this section, we show that the uniform-rosette configuration can be produced with common digital resolutions and does not require special “irrational” screening methods or supercells.^{2}

## 4.1.

### Spatial Vectors and Their Relationship to Frequency Vectors

In the previous discussion, the geometry of the halftone screen is defined by two fundamental frequency vectors. Alternatively, the screen geometry can be defined by two spatial vectors as well. For example, if a rectangular cell is tiled in a manner that forms an arbitrarily rotated screen, the spatial structure of the screen tiling can be represented by two orthogonal spatial vectors, ${\mathbf{v}}_{1}$ and ${\mathbf{v}}_{2}$ , which correspond to two orthogonal fundamental frequency vectors, ${\mathbf{f}}_{1}$ and ${\mathbf{f}}_{2}$ , respectively. The frequency vectors are orthogonal to their respective spatial vectors, and the moduli, or the absolute value, $\mid {\mathbf{f}}_{1}\mid $ and $\mid {\mathbf{f}}_{2}\mid $ , are equal to $1\u2215\mid {\mathbf{v}}_{2}\mid $ and $1\u2215\mid {\mathbf{v}}_{1}\mid $ , respectively.

The shape of a halftone cell that can be tiled to fill the image plane is not restricted to square or rectangular. Instead, the cell can be any parallelogram shape, which can be specified using two nonorthogonal vectors, ${\mathbf{v}}_{1}$ ( ${x}_{1}$ , ${y}_{1}$ ) and ${\mathbf{v}}_{2}$ ( ${x}_{2}$ , ${y}_{2}$ ), illustrated in Fig. 15 . Halftone outputs generated by the specified halftone screen can be represented by a 2D Fourier series with two fundamental frequency vectors, ${\mathbf{f}}_{1}$ ( ${f}_{x1}$ , ${f}_{y1}$ ) and ${\mathbf{f}}_{2}$ ( ${f}_{x2}$ , ${f}_{y2}$ ), also shown in Fig. 15. Similar to the orthogonal case, ${\mathbf{f}}_{1}$ and ${\mathbf{f}}_{2}$ are perpendicular to ${\mathbf{v}}_{1}$ and ${\mathbf{v}}_{2}$ , respectively. However, their moduli, $\mid {\mathbf{f}}_{1}\mid $ and $\mid {\mathbf{f}}_{2}\mid $ , are not given by the reciprocals of $\mid {\mathbf{v}}_{2}\mid $ and $\mid {\mathbf{v}}_{1}\mid $ , as for the orthogonal screens. Instead, $\mid {\mathbf{f}}_{1}\mid $ and $\mid {\mathbf{f}}_{2}\mid $ are equal to the reciprocals of ${h}_{1}$ and ${h}_{2}$ , which are the heights of the parallelogram, or the pitches between cells, shown by the dotted lines in Fig. 15. Because the product, $\mid {\mathbf{v}}_{1}\mid {h}_{1}=\mid {\mathbf{v}}_{2}\mid {h}_{2}=A$ , is the area of the specified parallelogram-shape cell, we may write the moduli of the frequency vectors by the following equations:

## Eq. 10

$$\mid {\mathbf{f}}_{1}\mid =1\u2215{h}_{1}=\mid {\mathbf{v}}_{1}\mid \u2215A,\phantom{\rule{1em}{0ex}}\mid {\mathbf{f}}_{2}\mid =1\u2215{h}_{2}=\mid {\mathbf{v}}_{2}\mid \u2215A,$$Because the spatial vector
${\mathbf{v}}_{1}$
(
${x}_{1}$
,
${y}_{1}$
) and the frequency vector
${\mathbf{f}}_{1}$
(
${f}_{x1}$
,
${f}_{y1}$
) are perpendicular to each other, so are
${\mathbf{v}}_{2}$
(
${x}_{2}$
,
${y}_{2}$
) and
${\mathbf{f}}_{2}$
(
${f}_{x2}$
,
${f}_{y2}$
). From Eq. ^{11} it is not difficult to prove that

## Eq. 12

$${f}_{x1}={y}_{1}\u2215A,\phantom{\rule{1em}{0ex}}{f}_{y1}=-{x}_{1}\u2215A,\phantom{\rule{1em}{0ex}}{f}_{x2}={y}_{2}\u2215A,\phantom{\rule{1em}{0ex}}{f}_{y2}=-{x}_{2}\u2215A.$$Equation ^{12} provides a transformation from spatial-vector components to frequency-vector components. It may be rewritten to provide the inverse transformation, from frequency-vector components to spatial-vector components,

## Eq. 13

$${x}_{1}=-A{f}_{y1},\phantom{\rule{1em}{0ex}}{y}_{1}=A{f}_{x1},\phantom{\rule{1em}{0ex}}{x}_{2}=-A{f}_{y2},\phantom{\rule{1em}{0ex}}{y}_{2}=A{f}_{x2}.$$^{11}gives an alternative expression for $A$ ,

To implement halftoning based on tiling a halftone cell, the tangent of the rotation angle, specified by the argument of the spatial vector
$\mathbf{v}$
, has to be a rational number. This restriction is due to the fact that tiling a cell on a discrete pixel grid requires the cell dimensions to be defined by integer multiples of the pixel spacing. However, neither 15- nor 75-deg rotation of a halftone screen can be implemented digitally because the tangents of these angles are irrational. The halftone screens defined in the previous section for a general uniform-rosette configuration are specified in the frequency domain and most likely do not have a simple digital implementation. However, a translation of the frequency specification of the uniform rosette of Eqs. ^{5, 6} to a spatial description allows us to show that digital implementations for that particular configuration are readily available.

In designing a screen set, we proceed by defining rosette frequency vectors of suitable size and angular separation that possess even-valued
$x$
and
$y$
components. The even values ensure that integer solutions can be found for halftone frequencies on the second-order spectral hexagon. We then transform these halftones to the frequency domain and apply the moiré-free conditions of Eq. ^{5} to find additional screens. The additional screens can be tested to determine if they can be rendered with an integer solution by applying Eq. ^{13}.

## 4.2.

### Uniform Rosette by Nonorthogonal Halftone Screens

The example of $N$ -colorant uniform-rosette halftoning above was constrained to use classical angles for three of the screens. Here we provide a seven-colorant example using nonorthogonal screens, where the screens are all realizable on a $1200\phantom{\rule{0.3em}{0ex}}\mathrm{dpi}$ (dot-per-inch) pixel grid. We choose the following two spatial vectors to define the shape of the uniform rosette:

where the spatial vectors are defined in pixel units. The corresponding uniform-rosette fundamental frequencies and their vector differences are given by## 16.

## Table 1

Vector specifications for a seven-colorant halftone configuration.

Colorant | fi1 | fi2 | vi1 | vi2 |
---|---|---|---|---|

1 | ${\mathbf{f}}_{11}=2{\mathbf{f}}_{R1}$ $=\left(\mathrm{75,150}\right)$ $=167.7\phantom{\rule{0.3em}{0ex}}\mathrm{lpi}$ at $63.4\xb0$ | ${\mathbf{f}}_{12}={\mathbf{f}}_{R1}+2{\mathbf{f}}_{R2}$ $=(112.5,-75)$ $=135.2\phantom{\rule{0.3em}{0ex}}\mathrm{lpi}$ at $-33.7\xb0$ | ${\mathbf{v}}_{11}=(-4,6)$ | ${\mathbf{v}}_{12}=(8,4)$ |

2 | ${\mathbf{f}}_{21}={\mathbf{f}}_{R1}-{\mathbf{f}}_{R2}$ $=\left(\mathrm{0,150}\right)$ $=150\phantom{\rule{0.3em}{0ex}}\mathrm{lpi}$ at $90\xb0$ | ${\mathbf{f}}_{22}=2{\mathbf{f}}_{R1}+2{\mathbf{f}}_{R2}$ $=(150,0)$ $=150.0\phantom{\rule{0.3em}{0ex}}\mathrm{lpi}$ at $0\xb0$ | ${\mathbf{v}}_{21}=(8,0)$ | ${\mathbf{v}}_{22}=(0,8)$ |

3 | ${\mathbf{f}}_{31}=2{\mathbf{f}}_{R1}+{\mathbf{f}}_{R2}$ $=(112.5,75)$ $=135.2\phantom{\rule{0.3em}{0ex}}\mathrm{lpi}$ at $33.7\xb0$ | ${\mathbf{f}}_{32}=2{\mathbf{f}}_{R2}$ $=(75,-150)$ $=167.7\phantom{\rule{0.3em}{0ex}}\mathrm{lpi}$ at $-63.4\xb0$ | ${\mathbf{v}}_{31}=(8,4)$ | ${\mathbf{v}}_{32}=(-4,6)$ |

4 | ${\mathbf{f}}_{41}=2{\mathbf{f}}_{R1}-{\mathbf{f}}_{R2}$ $=(37.5,225)$ $=228.1\phantom{\rule{0.3em}{0ex}}\mathrm{lpi}$ at $80.5\xb0$ | ${\mathbf{f}}_{42}=2{\mathbf{f}}_{R1}+3{\mathbf{f}}_{R2}$ $=(187.5,-75)$ $=201.9\phantom{\rule{0.3em}{0ex}}\mathrm{lpi}$ at $-21.8\xb0$ | ${\mathbf{v}}_{41}=(2,5)$ | ${\mathbf{v}}_{42}=(-6,1)$ |

5 | ${\mathbf{f}}_{51}=3{\mathbf{f}}_{R1}+2{\mathbf{f}}_{R2}$ $=(187.5,75)$ $=201.9\phantom{\rule{0.3em}{0ex}}\mathrm{lpi}$ at $21.8\xb0$ | ${\mathbf{f}}_{52}=-{\mathbf{f}}_{R1}+2{\mathbf{f}}_{R2}$ $=(37.5,-225)$ $=228.1\phantom{\rule{0.3em}{0ex}}\mathrm{lpi}$ at $-80.5\xb0$ | ${\mathbf{v}}_{51}=(6,1)$ | ${\mathbf{v}}_{52}=(-2,5)$ |

6 | ${\mathbf{f}}_{61}=3{\mathbf{f}}_{R1}+{\mathbf{f}}_{R2}$ $=\left(\mathrm{150,150}\right)$ $=212.1\phantom{\rule{0.3em}{0ex}}\mathrm{lpi}$ at $45\xb0$ | ${\mathbf{f}}_{62}={\mathbf{f}}_{R1}+3{\mathbf{f}}_{R2}$ $=(150,-150)$ $=212.1\phantom{\rule{0.3em}{0ex}}\mathrm{lpi}$ at $-45\xb0$ | ${\mathbf{v}}_{61}=(4,4)$ | ${\mathbf{v}}_{62}=(-4,4)$ |

7 | ${\mathbf{f}}_{71}=2{\mathbf{f}}_{R1}$ $=\left(\mathrm{75,150}\right)$ $=167.7\phantom{\rule{0.3em}{0ex}}\mathrm{lpi}$ at $63.4\xb0$ | ${\mathbf{f}}_{72}=2{\mathbf{f}}_{R2}$ $=(75,-150)$ $=167.7\phantom{\rule{0.3em}{0ex}}\mathrm{lpi}$ at $-63.4\xb0$ | ${\mathbf{v}}_{71}=(8,4)$ | ${\mathbf{v}}_{72}=(-8,4)$ |

Figure 16 shows the Fourier representation and frequency vectors of the rosettes for this seven-colorant halftone screen configuration. The left side of Fig. 17 shows the halftone outputs as provided by halftone screens 1 [Fig.17(a)] through 7 [Fig. 17(g)], while the right side shows the respective Fourier representations. Figure 18 shows various superimpositions of the seven halftone outputs. Figure 18 depicts the superimposition of the colorants 1, 2, and 3. Figure 18 depicts the superimposition of the colorants 1, 2, 3, and 4. Figure 18 depicts the superimposition of the colorants 5, 6, and 7. Figure 18 depicts the superimposition of the colorants 1 to 7. The figures illustrate that the superimpositions are free of moiré and possess pleasing hexagonal rosettes.

## 5.

## Discussion on Registration Sensitivity

A quick examination of the uniform-rosette configuration has led some observers to conjecture that this configuration may possess color-shift sensitivity to misregistration similar to dot-off-dot and dot-on-dot designs. In the present paper, we provide the intuition for relative insensitivity, and we reserve a future publication to present a rigorous simulation of the phenomenon. The conjecture on high sensitivity is based on observations of figures, such as Fig. 8, and noting that the dots are relatively disjoint and there may be the possibility of much more overlap at other registrations. To understand this phenomenon, consider the dot-on-dot example of Fig. 19
. The two registrations (shifted by a quarter period) generate very different fractional areas for cyan alone, magenta alone, the overlap of cyan and magenta, and white paper. These area types are the Neugebauer primaries.^{12} The Neugebauer model would predict a significant color shift^{13} due to the significant change in the fractional areas of the primaries.

A uniform-rosette pattern with similar dot size and frequency is shown in Fig. 20 . Although, indeed there is a significant amount of disjoint area between the colors, the geometry differs from the dot-on-dot configuration in beneficial ways. Consider the dots within a single rosette. At the top, cyan is to the left and magenta is to the right, and at the bottom, cyan is to the right and magenta is to the left. A similar opposite relationship occurs on the sides of the rosette. On the left, magenta is above and cyan is below, and on the right, cyan is above and magenta is below. As color planes are misregistered in any one direction, the different spatial relationships within the rosette allow the fractional area coverages to remain relatively constant, thereby causing a minimal shift in average color. The right side of Fig. 20 shows the cyan halftone pattern laterally shifted by a quarter period. Although the shape of the rosette changes, it is readily seen that the fractional area coverages are much more constant than the dot-on-dot case shown in Fig. 19.

## 6.

## Summary

Similar to an orchestra, which needs to tune all musical instruments to match a reference pitch for a harmonic performance, the uniform-rosette halftoning method requires all halftone frequencies to match two common fundamentals for a harmonic halftoning. Based on this concept, uniform-rosette halftoning employs higher-order harmonics of a 2D periodic rosette pattern for all halftone screens and, therefore, completely avoids moiré due to color mixing. In addition, the visually pleasant appearance of uniform rosettes and the color stability are other advantages of this novel halftone method. The lattice formalism readily allows designs of uniform-rosette halftone configurations with an arbitrarily large number of colorants. With nonorthogonal screening technology, uniform-rosette halftoning can be easily implemented for most current digital color printers. For example, screen design specified by the vectors of Table 1 is a perfectly moiré-free solution for 1200-dpi color printers.

## references

## Biography

**Shen-Ge Wang** is a principal scientist in the Xerox Research Center Webster, Webster, New York. He received a BS in instrumental mechanics from Changchun Institute of Optics, China, and a PhD in optics from University of Rochester, respectively. His current research includes image processing, digital halftoning, and printer modeling.

**Robert Loce** is a principal scientist in the Xerox Research Center Webster, Webster, New York. He joined Xerox in 1981 with an associate degree in optical engineering technology from Monroe Community College. While working in Optical and Imaging Technology and Research departments at Xerox, he received a BS in photographic science from Rochester Institute of Technology (RIT 1985), an MS in optical engineering from University of Rochester (UR 1987), and a PhD in imaging science (RIT 1993). His current work involves development of image processing methods for color electronic printing. He has publications and many patents in the areas of halftoning, digital image rendering, optics, imaging systems, and digital image enhancement. His publications include book chapters on digital halftoning and digital document processing, and a book on enhancement and restoration of digital documents. He is currently an associate editor for *Journal of Electronic Imaging* and has been an associate editor for *Real-Time Imaging* and *IEEE Transactions on Image Processing*.