5 April 2012 Moiré-free color halftoning using hexagonal geometry and spot functions
Author Affiliations +
Hexagons are widely observed as a packing or tiling geometry in nature, yet they appear to have been avoided in conventional halftone tiling. A goal of the present study is to understand the potential barriers that have prevented their use and present new halftone geometry options that overcome the issues while offering several potential benefits. While conventional halftone geometries often include the fourth screen (e.g., yellow) in a suboptimal manner, the hexagonal geometry presented here can include a clustered-dot fourth screen moiré-free. Hexagonal screens can appear to have smoother texture. Due to differences in packing geometry and touch point geometry, hexagons have the potential to possess different tone reproduction characteristics, which may be favorable for some marking processes. We also present a parametrically controlled hexagonal halftone spot function that allows for optimization of dot touch points and provides compact growth. The controllable touch points can prevent a tone reproduction discontinuity, while the compact growth throughout the gray range ensures maximum stability. Additionally, we present a three-colorant dot-off-dot halftone configuration using hexagonal geometry. Examples are provided.



Hexagons are widely observed as a packing or tiling geometry in nature, yet they appear to have been avoided in conventional halftone tiling. A goal of the present study is to understand the potential barriers that have prevented their use and present new halftone geometry options that overcome the issues while offering several potential benefits.

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. A common halftone method is screening, which compares requested continuous tone levels of a colorant to predetermined thresholds typically defined over a square cell that is tiled to fill the image plane. The output of screening is a binary pattern of multiple small spots, 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 spots within a cell because the larger clustered mass prints with more consistent size and density than spots printed with isolated pixels. The alignment of the clusters in the tiling defines the geometry of the halftone screen. The resulting halftone structure is a two-dimensionally periodic pattern, possessing two fundamental spatial frequencies 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 primarily due to the nonlinearity of color mixing of subtractive colorants, and suppression of printing one colorant by another colorant. As a result, low frequency components can be visibly evident as interference patterns in the halftone print. To avoid moiré and color shifts due to misalignment and misregistration, 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. The large angular separation produces a large frequency difference vector between any two fundamental frequencies of the different screens so that no visibly objectionable moiré patterns are produced. There is a classical screen combination that provides suitable angular separation for two-colorant printing and moiré-free three-colorant printing. This combination consists of three screens constructed by square halftone cells of identical scalar frequency with one screen each placed at 15, 45, and 75 deg.1

The difficulty in avoiding objectionable moiré between halftone screens is 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 deg screen configuration is commonly used for C, M, and K, while the classical screening method for Y uses a screen at 0 deg and is 8% to 10% different in frequency than the other screens so that the moiré is relatively high frequency and low contrast.2 Other common solutions for Y have also been suboptimal, such as stochastic screens, which can be prone to noise and tone instability. The understanding of moiré becomes increasingly complicated, and moiré-free solutions more challenging, when you consider that clustered-dot halftoning produces binary patterns, which are rich in harmonics that can cause unacceptable interference for certain colorant combinations. Moiré within halftones has been studied extensively. One example is by Amidror et al.,3 in which a spectral model based on Fourier analysis was used to explain the moiré due to the superimposition of halftone screens. Amidror et al. 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, only can satisfy the moiré-free condition for moiré between fundamental frequencies of two or three colors. They neglect subtle moiré patterns due to interaction of harmonics, and employ an unnecessary constraint of square or rectangular cells.

Halftone designers consider many options to deliver a screen with desirable characteristics, such as smooth texture, textures that are compatible with the image subject matter, low noise, tone stability, and lack of moiré. The designer often must settle for less than desirable results due to physical constraints such as a digital pixel grid and due to goals that sometimes lead to conflicting design strategies.

In this paper we propose a new option to halftone screen designers with several potential beneficial properties compared to conventional square-cell-based screens. We propose hexagonally tiled screens that can be produced with a conventional orthogonal pixel grid. Halftones with hexagonal shape clusters are visually pleasing4 and theoretically the most compact halftone structure. Hexagonal halftones have been discussed in several publications and patents56.7 but a frequency analysis and connection to moiré in color printing is lacking. The proposed screens can appear to have smoother texture, and avoid moiré between fundamental and harmonic frequencies. Due to differences in packing geometry and touch point geometry, hexagons have the potential to possess different tone reproduction characteristics, which may be favorable for some marking processes. A fourth screen (e.g., yellow) can be included moiré-free, thereby avoiding problems associated with suboptimal halftoning for yellow. We also present a corresponding parametrically controlled hexagonal halftone spot function that allows for optimization of dot touch points and provides compact growth. The optimized touch points can prevent a tone reproduction discontinuity, while the compact growth throughout the gray ranges ensures maximum stability.

Additionally, we present a three-colorant dot-off-dot (DOD) halftone configuration using hexagonal geometry. The geometry is based on a hexagonal base screen, where the three colorants are printed with specific displacements of the screen. DOD screens are used to produce smoother textures than rotated dot screens when colorant-to-colorant registration can be held to very tight tolerance, thereby avoiding the need for registration insensitivity enabled by rotated screens. Two previous DOD halftone methods8,9 provided pleasing texture for two and fourcolorants but did not describe three-colorant DOD. Harrington10 taught a method that can perform DOD halftoning with an arbitrary number of colors but the dot growth is along a curve rather than according to a conventional spot function.




Frequency Representation of Periodic Halftone Patterns

Clustered-dot halftoning methods produce halftone images that possess periodic structures defined by the halftone screens. For the purposes of moiré analysis, these images can be described in the frequency domain by discrete components without regard to amplitude and phase. In this representation, a two-dimensional halftone for a single colorant x forms a frequency lattice defined by two generator vectors Vx1, Vx2. The generator vectors correspond to the two fundamental frequencies of the halftone. Linear combinations of the vectors form the full spectrum with all points (harmonics) located on the lattice defined by the generator vectors and no frequencies are lower than the fundamentals.

Moiré analysis for conventional halftoning focuses on cyan (C), magenta (M), and black (K). Yellow (Y) is usually include in some suboptimal manner, which may or may not be fully acceptable depending upon the visibility of yellow and its interaction with the other colorants. The fundamental vector frequencies for C, M, and K can be denoted by Vc1, Vc2, Vm1, Vm2, Vk1, and Vk2, respectively, where the subscripts 1 and 2 refer to positive and negative angles, respectively. Figure 1(a) illustrates the appearance for an overlay of C, M, Y, and K halftone images based on a traditional configuration, with cyan at 75/15deg; magenta at 15/75deg; black at 45/45deg, and yellow at 0/90deg. The traditional configuration uses the same halftone screen for C, M, and K, with square cells rotated to given angles. The combined halftone texture, often referred to as the rosette pattern, is not a simple repeated pattern and its Fourier representation is complicated. Figure 1(b) shows the frequency vector representation of the C, M, and K screens, which is used below for the moiré analysis.

Fig. 1

(a) Superposition of cyan, magenta, yellow, and black halftones in a conventional configuration (single color area converage=25%) (b) Fourier representation of cyan, magenta, and black halftones.


The Fourier transform is dominated by discrete frequency components shown as circular dots. The discrete components are defined by the two fundamental halftone frequencies for each screen, their two-dimensional higher-order harmonics (which can be considered to be linear combinations of the fundamentals), and linear combinations of components from different screens (which are beats, or forms of moiré). Note that amplitude and phase are not represented in these plots and also that there are many higher-order harmonics of the halftone frequencies that are not shown in the plots.

The superposition of halftone color separations creates more frequency components than exist in the single separations of the various process colors. We can express the resultant vector frequency caused by superposition of two different colors as their frequency-vector difference, e.g., Vcm=Vc±Vm, where Vc and Vm are two frequency components from C and M, and Vcm is the difference vector. Since each Fourier component has its conjugate, i.e., there is always a frequency vector Vc that represents the conjugate component of Vc, the sign definition of frequency vectors is rather arbitrary. For each halftone screen, there are two fundamental frequency vectors, therefore, the color mixing of two screens for two different colors yields eight difference vectors by the fundamental frequencies alone. Considering other harmonics of the halftone frequencies, the combinations can yield a large number of difference vectors.


Moiré-Free Conditions

Multiple periodic phenomena can interfere to produce lower frequencies known as beats. In the field of halftoning, these beats appear as moiré. There are particular configurations of halftones that avoid creating objectionable moiré. The conventional moiré-free halftoning method utilizes screens for C, M, and K, such that three-way combinations of their fundamental frequencies sum to zero frequency or very high frequencies. Typically, the screens are chosen to be composed of square cells, and the frequencies are chosen to be roughly equal with the angles separated by about 30 deg.

A strategy to avoid two-color moiré is to ensure that no two-color difference vector due to fundamental halftone frequencies is too small.11 Using C and M halftones as an example, the two-color moiré-free condition can be summarized by


where Vc represents any one of Vc1, Vc1, Vc2, Vc2; Vm represents any one of Vm1, Vm1, Vm2, Vm2; and Vmin is a frequency limit set around 50 to 70 cycles/inch to avoid visually objectionable moirés.

It is well known that the most troublesome moiré is the three-color moiré that can appear in cyan-magenta-black prints produced by CMYK four-color printers.1 As an extension of the two-color case, one condition for three-color moiré-free printing can be summarized by


where Vk represents any one of Vk1,Vk1, Vk2,Vk2; and Vmin is set similar to the two-color case.

Unless the halftone frequencies are very high, say 200 cycles/inch, it is very difficult to design halftone screens such that all three-color difference vectors, as well as all two-color difference vectors are large enough to avoid any color moiré because there are thirty-two combinations of different components. A common alternative approach is to set two of the three-color difference vectors null while setting the remaining difference vectors large.1 This design practice for three-color moiré-free halftone printing can be specified by the following vector equations:





Equations (3a) and (3b) represent two of all possible frequency combinations of the three colors. In most practical applications, the remaining combinations satisfy the inequality of Eq. (2). It is instructive to view the frequency vectors of the conventional moiré-free configuration. Figure 2(a) shows the fundamental frequency vectors of the individual screens, and Fig. 2(b) shows the vector combinations of Eq. (3).

Fig. 2

(a) Screen fundamental frequency vectors for a conventional halftone design. (b) Conventional screen frequency vectors shown summing to zero frequency.



Nonorthogonal Clustered-Dot Screens

Most halftone screens used in color reproduction are orthogonal screens. That is, the screens are constructed of rectangular cells, or more likely, square cells. However, for most digital printing devices, the size and shape of halftone cells are constrained by a digital rectilinear pixel grid, which defines the locations of printed spots, and therefore, an exact 15 or 75 deg rotation of a clustered-dot screen is not possible. Although there are alternative approaches for moiré-free color halftoning, most of those methods provide approximate solutions and/or have a tendency to generate additional artifacts in the halftone outputs. The difficulty to achieve moiré-free color halftoning is greatly relieved by using non-orthogonal halftone cells, which tile a screen with general parallelogram shapes. Wang et al.12 provide detailed description of the design procedure for moiré-free halftoning using nonorthogonal clustered dot screens.

An example of a moiré-free nonorthogonal screen is illustrated in Figs. 3 and 4. The three parallelograms in Fig. 3 illustrate the shape and orientation of the halftone cells that define the screens. The corresponding frequency vectors are shown in Fig. 4(a). A halftone image resulting from this configuration is shown in Fig. 4(b).

Fig. 3

Halftone cells for three nonorthogonal screens satisfying moiré-free conditions.


Fig. 4

(a) Fundamental frequency vectors for the nonorthogonal screens of Fig. 3; (b) halftone rosettes formed from that set of moiré-free nonorthogonal halftone screens.



Pellar Spot Function

A halftone cell that is replicated to tile an image plane can be specified by an array of threshold values, along with three parameters: width and height of the array, and an offset of successive rows in tiling the array.13 The threshold values are often selected using what is known as a spot function. The Pellar14,15 spot function, also known as the Euclidean profile,2 is parameterized as a sum of two cosine functions and has several desirable features:


where Q is the threshold function that is compared to the input image pixel values in the halftoning operation. In practice, Q would be scaled and offset to have the same range as the image data, e.g., [0, 255]. The thresholding result by the Pellar spot function is a black compact disk for lower input levels, a diamond at middle input levels where the dots touch, and a compact white hole for higher input levels [contours shown in Fig. 5(a)].

Fig. 5

(a) Contour plot of Pellar (i.e., Euclidean) spot function and (b) associated parameters.


As shown in Fig. 5(b), in instances where the clustered-dot screen is an orthogonal halftone screen, all clusters, or dots, are centered on the intersection points of a grid, or lattice. The lattice is defined by two sets of parallel lines L1 and L2, such that the lines L1 are perpendicular to the lines L2. The periods of the lattice in two different directions, 45 and 45deg directions are defined by the shortest distance between the adjacent parallel lines L1 of the first group, denoted by H1 and the shortest distance between the adjacent parallel lines L2 of the second group, denoted by H2. The threshold value at an arbitrary point p, defined by the distances, h1 and h2, from the point p to the adjacent orthogonal grid lines L1 and L2, respectively, is given by the function Q in Eq. (4). Since the two cosine functions in Q of Eq. (4) are defined with periods h1/H1 and h2/H2, respectively, it does not matter which particular grid lines within each of the twosets are chosen to define the distance h1 or h2.


Hexagonal Halftone Geometry

The novel halftone configuration that we present utilizes three or four rotated hexagonal screens, or more precisely, screens with hexagonally tiled clusters, for moiré-free color printing. Halftone designers consider many options to deliver halftone screens with desirable characteristics, and often must settle for less than desirable results. The present method is a new option with several potential beneficial properties compared to conventional square-cell-based screens. Hexagonal screens can appear to have smoother texture. Due to differences in tiling geometry and touch point geometry, hexagons have the potential to possess different tone reproduction characteristics, which may be favorable for some marking processes. A clustered-dot fourth screen (e.g., Y) can be included moiré-free, thereby avoiding problems associated with suboptimal solutions for Y.

The configuration has the following properties. Each screen is constructed of tessellated convex hexagons, where a screen can be thought of as having three fundamental frequencies that are similar in vector length. One pair of screens possesses frequency vectors that are approximately equal in length and are within one frequency range. A second pair of screens also possesses frequency vectors of approximately equal length and can be constructed from sums and differences of frequency vectors from the first pair. The frequency vectors of the present halftone configuration can be readily achieved with common orthogonal pixel grids, as opposed to methods that relied on a hexagonal pixel grid.6


Hexagonally-Tiled-Cluster Halftone and its Frequency Representation

Although the appearance of hexagonally tiled hexagon clusters is quite different from square or rectangular tiled clusters, spatially repeated hexagons are essentially the result of tiling, or two-dimensional replication using a parallelogram, shown in the example of Fig. 6(a) by blue outlines. Hence, the hexagonal halftone shown in Fig. 6(a) is a two-dimensional periodic structure and can be represented by two fundamental frequency vectors, Vh1 and Vh2, shown in Figs. 6(a) and 6(b), defined for the corresponding nonorthogonal parallelogram screen. As discussed in the previous sections, a two-dimensionally repeated halftone pattern possesses many frequency harmonics as linear combination of the two fundamentals. For a hexagonal halftone pattern, one of the harmonics is noteworthy because its frequency vector length is exactly the same as the length of the two fundamentals if the hexagons are regular (i.e., 0 to 60 to 120 deg). The hexagons in Fig. 6(a) are regular and the noteworthy vector is shown as Vh3=Vh1+Vh2 in Fig. 6(b).

Fig. 6

(a) Halftone pattern hexagonally tiled with hexagon-shape clusters; (b) frequency vector representation of the regular hexagonal halftone pattern of (a).


Any two of the three vectors, Vh1, Vh2 and Vh3, can be used as fundamental frequency vectors and the third is equal to the sum of the two fundamentals (or their conjugates). Thus, we may loosely refer to the set of three as the “fundamentals” of a hexagonal halftone screen. In the following discussion, we use quotation marks for the three “fundamentals” to avoid confusion with the original meaning of fundamental frequencies for two-dimensional periodic functions in Fourier analysis.

We may have arrived at the reason that hexagons have found little use in N-color halftoning. While designers currently struggle under the constraint of using square-based cells that require sums of Npairs of frequency vectors to avoid moiré, hexagonal halftones require Ntriplets of frequency vectors to avoid moiré.


Moiré-Free Condition for Regular Hexagonal Screens

The interference of the various color separations when using multiple hexagonal halftone screens is much more complicated than the interference due to square-cell screens. Because of the presence of three “fundamentals” in a hexagonal halftone screen, the moiré-free conditions, Eqs. (1) through (3), have to be extended to all combinations of frequency vectors chosen from a redefined set of “fundamentals.” For each hexagon screen in the configuration, the third “fundamental” Vh3 is defined as


where Vh1 and Vh2 are the two fundamental frequency vectors defined previously for general non-orthogonal screens.

In the conventional three-color moiré-free halftoning cases, three rotated screens with square cells are separated by 30 deg between the halftone color separations. The same approach does not work for the hexagonal case because rotating a regular hexagon by 60 deg results in an identical tiling yielding screens that are not mutually rotated and therefore sensitive to color-to-color misregistration. Another initial thought is to rotate the three (C, M, and K) hexagonal screens by 1/3 of the symmetry to evenly divide the angle space, similar to rotating the three square-cell screens by 1/3 of their symmetry (90deg/3=30deg). Examination of Eq. (3) shows that angular separation by 20 deg does not produce a moiré-free result. Evidently, it is not straightforward to satisfy moiré-free conditions using rotated regular hexagonal screens. This obstacle may help explain why hexagonal screens seldom appear in practical applications of color halftoning.


Moiré-Free Solution Using Four Regular Rotated Hexagonal Screens

The general principle that defines the configuration is the following. Each screen is constructed of regular hexagons, where a screen can be thought of as having three “fundamental” frequencies of equal vector length separated by 60 deg. In a first pair of screens (A and B), the frequency vectors of screen A are of equal length to the vectors of screen B, and the frequency vectors of screen A are separated by 30 deg from the vectors of screen B. A second pair of screens (C and D) also have equal length frequency vectors and are separated by 30 deg, but their frequency length is 2 greater than those of the first pair of screens and the frequency vectors are rotated 15 deg from the first pair of screens. While we describe four screens in the above configuration, any three of that configuration is a useful configuration (e.g., for CMK three colors).

Let us examine a specific case of interest. We propose a configuration using three or four halftone screens with regular-hexagon-symmetry for moiré-free color halftoning. The proposed configuration is shown by the frequency vectors in Fig. 7. We denote the “fundamentals” of the four screens as VC1, VC2, VC3, VM1, VM2, VM3, VY1, VY2, VY3, VK1, VK2, and VK3. For idealized regular hexagons, |VC1|=|VC2|=|VC3|, |VM1|=|VM2|=|VM3|, |VY1|=|VY2|=|VY3| and |VK1|=|VK2|=|VK3|.

Fig. 7

Moiré-free color halftoning using four regular hexagonally tiling screens.


In Fig. 7, the angle between a pair of screens of the same frequency is given by


pair-to-pair separation is15 deg, i.e.,


and the frequency vector lengths are related by




The images of Fig. 8 compare color halftoning using a classical screen (Fig. 1) to the proposed configuration.

Fig. 8

Moiré-free halftone patterns using (a) four conventional screens, (b) four regular hexagonal screens.



General Solution for Moiré-Free Halftoning Using Four Rotated Tessellated Convex Hexagon Screens

In this section, we provide a general solution for moiré-free halftoning using four rotated screens with tessellating convex hexagon cells. The term “tessellating convex hexagon” implies that the shape of each cell is such that it can tessellate to fully tile the image plane and it is a convex hexagon. This implies that the two fundamental frequency vectors, |Vh1| and |Vh2|, do not necessarily have the relation as in the regular hexagon cases, i.e., |Vh1|=|Vh2| and A(Vh1,Vh2)=60deg.

For two fundamental frequency vectors of the C and M screens, VC1, VC2, VM1, and VM2, defined by the notation illustrated in Fig. 9, the third “fundamental” of C and M are given by




The general moiré-free solution can be described by








And the third “fundamental” of K and Y is given by





Fig. 9

Moiré-free color halftone frequency vector configuration using general convex tessellating hexagons.


For example, consider two convex tessellating hexagons defined for the C and M color separations by

where (fx,fy) notion in units of cycles/inch is used. The solution described by Eqs. (7)(8a)–(9) can be used to find the other two screens as
The corresponding third “fundamentals” of the four screens are

The use of the combination of above four screens provides a moiré-free halftoning solution. Halftone outputs comparing examples of regular hexagon tiling to general convex hexagon tiling are shown in Fig. 10. It is particularly interesting to notice that all four halftone screens illustrated here can be implemented digitally using single-cell nonorthogonal halftone screens specified by two spatial vectors16 listed below (in pixel units), respectively, for color printers with a 4800×4800pixel/inch resolution:


Fig. 10

Moiré-free halftone patterns using four screens with (a) regular hexagonal tiles, (b) general hexagonal tiles.



Hexagonal Spot Function

Halftone spot function design is generally a monochrome consideration and is optimized for a given marking process or for particular image subject matter.2 There are two primary considerations if we restrict the concerns to image quality on general image subject matter printed using laser printing or lithographic offset: maintain compactness as much as possible through the gray range to minimize noise and instability; control the shape of dot-to-dot touch points to avoid sudden shifts in tone that can occur when dots for the same colorant bridge together. A first thought may be to tile the hexagons side-to-side, but an issue arises in the midtones where narrow white tracks are formed between the dots that could be unstable leading to jumps in a tone reproduction curve, and noise and density variations over time. Rather than use a “topologically strong” side connection between dots, we use a “topologically weak” corner connection. The spot function is parameterized as the weighted sum of three cosines that are functions of distance from three respective reference lines defined by the sides of the hexagon. Algebraic powers of the distances control the shape of the sides of the dot and the sharpness of each spot touch point with its neighboring dots. Weights of the cosines control a sequencing of touches, such that contact with the neighboring dots can occur at three different gray levels, thereby avoiding a large instability and tone jump that can occur for simultaneous touching. Dot rotation can also be performed by rotating the coordinate system (Fig. 11).

Fig. 11

(a) Intuitive approach to grow dots produces potentially unstable narrow white tracks; (b) corner-touching growth avoids the narrow white tracks but forms two triangular holes in the shadows.


An arbitrary nonorthogonal halftone screen can be defined by two spatial vectors, v1 and v2, as shown in Fig. 12. The vectors v1 and v2 define a parallelogram that can completely tile the plane of the image being halftoned. The dot shape function can be evaluated within such a parallelogram tile to form a cell. Parallelogram cells can be converted to other geometric forms, such as rectangles, or Holladay bricks.13 In Fig. 12, all clusters are centered on the intersection points of a grid defined by two sets of parallel lines L1 and L2. The dot shape function for non-orthogonal clusters can be described by the same threshold function Q used for orthogonal halftone screens in Eq. (4), where the periods of the grid, H1 and H2, are defined in the two directions, perpendicular to the nonorthogonal grid lines. Similar to the orthogonal case, choosing different grid lines within a parallel set of lines as the distance reference does not change the values of the dot shape function.

Fig. 12

Nonorthogonal halftone screen with all clusters centered on the intersection points of a grid defined by two spatial vectors, v1 and v2.


Additional vectors can be used in defining the halftone screen grid. A vector of interest, v3, is the one that connects an intersection point with a second closest neighboring grid point. The spatial vector v3 is the summation of v1 and v2:



For a square-shape orthogonal screen, this vector is longer than v1 and v2 by 2, and is angled 45 deg from those vectors. As the angles of the grid depart from orthogonal, the length of v3 becomes closer to v1 and v2. As shown in the hexagonal halftone screen of Fig. 12, as the angle between v1 and v2 approaches 120 deg, for v1v2 the length of v3 approaches the length of v1 and v2 the halftone screen grid approaches a regular hexagonal lattice. Each intersection point in the hexagonal halftone screen grid has sixnearest neighboring intersection points that are substantially equidistant, and separated from each other in a hexant arrangement.

A third set of parallel lines L3 crossing all intersecting points and parallel to the direction of v3 can be added to the grid, as shown in Fig. 12. The period of the third set of parallel lines is defined as H3. By vector analysis the three periods, H1, H2, and H3, can be described as functions of the three spatial vectors, v1, v2, and v3:






where vi×vj represents the cross product of vectors vi and vj, and |v| is the magnitude of vector v. By the definition of vector v3, or Eq. (10), it can be shown that the magnitudes of all vector products shown in Eqs. (11a) to (11c) are equal and the value of these magnitudes represents the area A of the parallelograms defined by any two of the three vectors v1, v2, and v3:



For the following derivation, we select an intersection point o as a reference point and define the three vectors v1, v2, and v3 as sharing the same origin. Then, the distances from an arbitrary point p to the three lines L1, L2, and L3 defined by the spatial vectors v1, v2, and v3 can be described by the following equations, where the spatial vector v is defined as from the reference point o to the arbitrary point p:







Using Eq. (12), we can rewrite Eqs. (13a) to (13c) as:







where h^1, h^2, and h^3are heights normalized by the grid periods H1, H2, and H3, respectively and have nonnegative values.

We use a new dot shape function for hexagonal shaped clustered-dot screens:





Since the vector v3 is defined as the sum of two vectors v1 and v2, the distance h3 in Eq. (15a) and the corresponding normalized height h^3 in Eq. (15b) are not independent. The vector product in Eq. (14c) can be expressed as:



In Eq. (16) the three vector products are in the same direction but may carry different signs, plus or minus. Depending on the way of defining the spatial vectors, the normalized height h^3 given by Eq. (14c) may be equal to either the sum or the difference of h^1 and h^2. To avoid the ambiguity, we define the two spatial vectors v1 and v2, such that both vectors start from the reference point o and the angle from v1 to v2 is positive and the angle is substantially equal to 120 deg. The vector v3 is defined by Eq. (10) and all distances used for the nonorthogonal hexagonal clustered-dot screen are defined by vector product and Eqs. (13a) to (13c). With these above specified definitions, the following relationship exists between the three normalized heights has been found:



This allows us to eliminate h^3from Eq. (15b) so that the hexagonal dot shape function can be givenas a function of two independent variables h^1and h^2:



By modifying Eq. (15a), a parametrically controlled hexagonal halftone dot shape function Q1 can be defined as:


where the parameter ai is a weight that controls the rate at which the ith vertex of the dot approaches the vertex of a neighboring dot. When the ai are substantially equal, the growth of the dot is substantial equal in all threevector directions (positive and negative directions for each of the three vectors). When an ai value is larger than the other ai values, the dot becomes eccentric, growing at a faster rate in the direction (positive and negative directions) of the vector associated with the larger ai. In this respect, this parameter can be used to control which vertices touch at particular gray levels. For example, the a parameter in Eq. (19), (a1, a2, a3) allows neighbor touching at one, two, or three different respective gray levels, thereby avoiding tone instability caused by touching all neighbors simultaneously (i.e., at the same gray level).

Furthermore, it can be desirable to control the contour (shape) of a dot perimeter and the touch points to compensate for attributes of the marking engine used to print the halftoned image. The parametrically controlled dot shape function Q2 shown in Eq. (20) utilizes an additional set of parameters to control the roundness and convexity/concavity of the dot sides and the sharpness of the vertex touch points:


wherein γi controls the shape of the sides of the dot. In the dot shape function of Eq. (20), the perpendicular distance from the point of interest p to the closest grid lines is used to determine each respective h.

Using a dot shape function Q2 in which γ<1 results in printed hexagonal dots having pincushion (i.e., concave) shaped sides, producing sharper touch points with adjacent dots, which can improve stability of gray tone for marking processes with significant growth. Using a dot shape function Q2 having a γ>1 results in a rounder, convex shape, to the printed dot, which can delay the touching of adjacent dots to darker gray levels. Figure 13 illustrates the effect of γ. Figure 14 illustrates how the dot shape function Q2 can be used to control neighbor halftone dot touching as a function of halftoned image gray level by controlling the a parameters.

Fig. 13

γ series showing control over side shape and sharpness of connection. ai=1.


Fig. 14

ai series showing control over neighbor touching as a function of gray level. γi=1.


Referring to Fig. 13(c), an example halftone screen output generated by the base hexagonal dot shapefunction Q of Eq. (15), which is equivalent to the parametrically controlled dot shape function Q2 of Eq. (20) with a1=a2=a3=1.0 and γ1=γ2=γ3=1.0, is shown producing a halftoned image having a continuously varying gray level progressing from a minimum (e.g., 0 representing the lightest gray level) at the left, to a maximum (e.g., 255, or other scaled number, representing the darkest gray level) at the right. The base hexagonal dot shape function Q of Eq. (15) begins as substantially circular dots at lighter gray levels, growing to some selected form of hexagon, producing for example regular hexagonal dots in Fig. 13(c), at mid-gray levels, and closes producing compact triangular holesbetween adjacent dots in the darker gray levels. Note that for each dot, the hole is split into two triangles. This split does create thepotential for less stable shadow tones.

We note that any halftone dot shape function, such as those represented by the dot function of Eqs. (19) and (20), can be inverted in valueto provide an opposite growth sequence, which could be desirable in some marking processes or image subject matter. Also, the hexagonal dot shape function can be rotated within a fixed position of the hexagonal grid using a coordinate transformation.


Hexagonal Dot-Off-Dot Configuration

DOD screens are sometimes used for uniform tints because they produce much finer textures than conventional rotated dot screens. Rotated dot screens have the negative drawback of possessing a texture frequency component (the rosette) that is roughly half of the halftone frequency.1 Conversely, periodic DOD screens have the desirable attribute of possessing an apparent frequency that is significantly higher than the single-separation halftone frequency. Another positive attribute of DOD screens is that they have the potential to produce colors that are out of the gamut of rotated screens.17 A significant drawback of DOD halftones is that colorant-to-colorant registration must be held to a very tight tolerance (5 to 20 microns for common halftone frequencies) to avoid color shifts, whereas rotated screens are relatively insensitive to colorant-to-colorant misregistration.18 If a print engine can hold tight colorant-to-colorant registration, and hence is able to use DOD screens for tints, the screens would generate acceptable textures using very low frequency halftones, which could drastically reduce noise levels and instability. In addition to the registration sensitivity, another barrier to employing DOD screens occurs when using three colorants. Although methods exist for using two9 or four (Flamenco screens)8 colorants, methods for DOD periodic clustered dot halftoning three colorants have not been previously taught. Harrington10 taught a method that can perform DOD with an arbitrary number of colors, but the dot growth is along a growth curve rather than according to a conventional spot function.

Here, we present a three-colorant dot-off-dot (DOD) halftone configuration using hexagonal geometry. The geometry is based on a hexagonal base screen, where the three colorants are printed with specific displacements of the screen. Figure 15 shows a schematic example of a three-colorant halftone using cyan, magenta and black dots, and Fig. 16 illustrates their displacements. As described above, a hexagonal screen has three “fundamental frequencies” (and three corresponding “fundamental periods”), where any one of the fundamentals can be considered dependent on the other two. We can assume that the base screen is used in a reference position for one colorant and the other two colorants use the base screen displaced from the reference position. The displacements are in two different directions, each along the direction of a fundamental frequency. The amount of displacement is 2/3 of the period of the fundamental frequency in the direction of the frequency.

Fig. 15

Schematic example of a three-colorant DOD hexagonal halftone. The hexagons would not be in the actual image. They are included in the schematic only to better communicate the pattern. The choice of the colorants is arbitrary.


Fig. 16

Example of displacements for three-colorant DOD screens.



Comments on Texture

We will compare Fig. 1 to Figs. 17Fig. 1819 to better understand the nature of the texture difference between a multicolor rotated dot screen and the present three-colorant DOD screen. Figure 17 shows the fundamental periods of a single-colorant hexagonal screen, which corresponds to the spectrum shown in Fig. 6(b). Figure 18 shows the fundamental periods for the three-colorant screen. Note that the frequencies of the texture are higher than in the mono case. Figure 19 shows the frequency vector diagram for the three-colorant hexagonal DOD screen. In comparing Fig. 19 to the frequency diagram in Fig. 1, we see that combining rotated screens produces lower (unwanted) frequency components than what exists in the single-colorant spectrum. These components are considered beats or forms of moiré due to the interaction of the colorants, such as overlap in their optical absorption spectra. Printing DOD using the method described here produces higher frequencies than the single-colorant screen. The overlap in absorption spectra actually suppresses the fundamental frequencies and the combined screens appear to have a higher “combined fundamental frequency.” This phenomenon can be understood by examining a limiting case of optical spectra overlap, where we substitute black halftones for the cyan and magenta halftones in Fig. 18. The additional dots eliminate the single-screen fundamental frequency, and result in a higher “combined fundamental frequency.” Since cyan and magenta absorption spectra do not completely overlap, the single-screen fundamental frequency is not completely suppressed, but its appearance is significantly reduced as is shown in the example below. This suppression of single-screen fundamental frequency allows us to use very low frequency single-colorant screens, which tend to have low noise and high tone stability, while achieving a high frequency appearance for three-color tints.

Fig. 17

Periods of fundamental frequencies of a single-colorant hexagonal screen.


Fig. 18

Periods of fundamental frequencies of a three-colorant DOD hexagonal screen.


Fig. 19

Frequency vector diagram for three-colorant hexagonal DOD screen. Dashed vectors represent the “fundamentals” of the single-colorant halftone. In this configuration, the single screen components are at lower frequency than the frequencies in the three-color screen.




The example below compares a three-colorant DOD screen with a combined fundamental frequency of roughly 170 cpi to a rotated screen set with fundamental frequencies of roughly 170 cpi.


Parameters for the DOD screen (at 2400pixels/inch)

Base screen: V1=115.2cpi, 60.3 deg; V2=115.2cpi, 60.3deg; V3=114.3, 0 deg.

Spatial vectors (in pixel units): v1=(24,0) and v2=(12,21).

Shift for each screen: ShiftK=0,0; ShiftM=0,17; ShiftC=12,7.


Parameters for rotated screens (at 2400pixels/inch)

Black screen: V1=170cpi, 45 deg; V2=170cpi, 45deg.

Cyan screen: V1=170cpi, 75 deg; V2=170cpi, 15deg.

Magenta screen: V1=170cpi, 15 deg; V2=170cpi, 75deg.

Figure 20 shows a comparison of appearance for the two halftoning methods. Figure 20(a) shows a fine texture, while significant portions of the marking process (exposure, development) operated at only 115 cpi, thereby producing a relatively low-noise print. On the other hand, the rotated screens show less desirable low-feature texture while operating at a noisier, less stable 170 cpi.

Fig. 20

(a) Three-colorant DOD screen; (b) conventional rotated three-colorant screen



Areas for Future Study and Summary


Future Study

While the present study focuses on enabling the use of hexagonal halftone through particular geometric rules and suitable spot functions, we recognize that additional work in needed in the realm of characterization. In particular, study is needed on the tone reproduction behavior and on the smoothness appearance. At least three points arise when considering the tone reproduction: (1) packing density differences, (2) sixtouch points vs. four, (3) splitting each hole into two triangles. Concerning smoothness, visual comparisons tend to indicate that hexagonally tiled screens have a smoother appearance than conventional square tiled screensfor monochrome images (see Fig. 21). This may be due to the more complex frequency spectrum providing some level of masking of the periodic structure. A visual model or empirical study will be needed to better understand this potential smoothness effect. A visual comparison of smoothness for a full color image is not immediately compelling. Consider the example of Fig. 22. The right picture was halftoned by a digital simulation of the conventional square-cell-based halftone screens, and the left one was halftoned by a set of hexagonal screens with the following spatial frequencies (in units of cycles/inch):

The frequencies are very low to make the texture apparent in this publication. Empirical print studies are needed to effectively rate the smoothness of these images. The result may be marking process dependent. Another consideration is that many color prints have substantial regions that are primarily monochrome. The hexagonal screen method presented here will allow full color moiré-free printing, with a certain gain in smoothness benefit in the image regions that are predominantly monochrome.

Fig. 21

Comparison of smoothness appearance for a monochrome (a) square tiled screen; (b) hexagonally tiled screen.


Fig. 22

Comparison of smoothness appearance for full color (a) square tiled screen; (b) hexagonally tiled screen.




Hexagonal halftone geometries for color printing may have been avoided due to the requirement to include additional frequency vectors into the system while remaining moiré free. We have worked through this issue and presented a halftone configuration that utilizes three or four halftone screens with hexagonally tiled cells and clusters for moiré-free color printing. The configuration has the following properties. Each screen is constructed of tessellated convex hexagons, where a screen can be thought of as having three fundamental frequencies that are similar in vector length. One pair of screens possesses frequency vectors that are approximately equal in length and are within one frequency range. A second pair of screens also possesses frequency vectors of approximately equal length and can be constructed from sums and differences of frequency vectors from the first pair. The frequency vectors of this configuration can be readily achieved with common orthogonal pixel grids.

This halftone configuration presents a new option with several potential beneficial properties compared to conventional square-cell-based screens. Hexagonal screens can appear to have smoother texture, at least in image regions that are predominantly monochrome. Due to differences in packing geometry and touch point geometry, hexagons have the potential to possess different tone reproduction characteristics, which may be favorable for some marking processes. A fourth screen (e.g., yellow) can be included moiré-free, thereby avoiding problems associated with stochastic or low contrast moiré solutions for yellow.

Also presented was a corresponding parametrically controlled hexagonal halftone spot function that allows for optimization of dot touch points and provides compact growth. The optimized touch points can prevent a tone reproduction discontinuity, while the compact growth throughout the gray range ensures maximum stability. Examples are provided.

Additionally, we presented a hexagonal-dot-off-dot configuration for three colorants, where previously taught methods for clustered periodic screens allowed for two or four8,9 colors. These DOD configurations produce very smooth tints at the cost of maintaining very tight color-to-color registration, which may need to be on the order of 5 to 20 microns18 for common screen frequencies.


1. J. A. C. Yule, Principles of Color Reproduction, John Wiley & Sons, New York (1967). Google Scholar

2. P. Fink, Post Script Screening: Adobe Accurate Screens, Adobe Press (1992). Google Scholar

3. I. AmidrorR. D. HerschV. Ostromoukhov, “Spectral analysis and minimization of moiré patterns in color separation,” J. Electron. Imag. 3(3), 295–317 (1994).JEIME51017-9909 http://dx.doi.org/10.1117/12.179355 Google Scholar

4. R. C. StauntonN. Storey, “A comparison between square and hexagonal sampling methods for pipeline image processing,” in Proc. of SPIE Optics, Illumination and Image Sensing for Machine Vision IV 1194, pp. 142–151 (1990).PSISDG0277-786X Google Scholar

5. C. Hains, “Method for reducing 2-color moiré in 4-color printing,” U. S. Patent 5,381,247 (1995). Google Scholar

6. R. Ulichney, Digital Halftoning, The MIT Press, Cambridge, MA, pp. 117–126 (1987). Google Scholar

7. M. Turbeket al., “Comparison of hexagonal and square dot centers for EP halftones,” in Proc. of IS&T PICS: Image Processing, Image Quality, Image Capture Systems Conf., pp. 321–325 (March 2000). Google Scholar

8. C. Eliezer, Description of Flamenco Screens, “Color screening technology: a tutorial on the basic issues,” The Seybold Report on Desktop Publishing 6(2), 3–25 (Oct. 1991). Google Scholar

9. J. Shu, “Apparatus and method for improving black and color separation in halftoned images by printing black dots in a different screen phase,” U.S. patent 5,594,839 (1997). Google Scholar

10. S. Harrington, “Method for multi-color, clustered, dot-off-dot halftoning,” U.S. patent 7,394,571 (2008). Google Scholar

11. I. Amidror, The Theory of the Moiré Phenomenon: Volume I: Periodic Layers, Springer-Verlag, New York City ISBN-10: 1848821808 (2009). Google Scholar

12. S. WangZ. FanZ. Wen, “Non-orthogonal halftone screens,” in Proc. NIP18: International Conf. on Digital Printing Technologies, San Diego, California, pp. 578–584, ISBN: 0-89208-240-2 (2002). Google Scholar

13. T. M. Holladay, “An optimal algorithm for halftone generation for displays and hard copies,” Proc. Soc. Inf. Display 21(2), IS&T, pp. 185–192 (1980).SIDPAA0036-1496 Google Scholar

14. R. Pellar, “Electronic halftone generator,” U. S. Patent 4,196,451 (1980). Google Scholar

15. R. Pellar, “Electronic halftone generator,” U. S. Patent 4,149,183 (1979). Google Scholar

16. C. HainsS. G. WangK. Knox, “Digital color halftones,” in Digital Color Imaging Handbook, G. Sharma, eds., 385–490, CRC Press, New York (2003). Google Scholar

17. W. RhodesC. Hains, “The influence of halftone orientation on color gamut and registration sensitivity,” Proc. IS&T’s 46th Annual Conf., pp. 180–182 (May 1993). Google Scholar

18. B. OztanG. SharmaR. Loce, “Misregistration sensitivity in clustered dot halftones,” J. Electron. Imag. 17(2), 023004 (2008).JEIME51017-9909 http://dx.doi.org/10.1117/1.2917517 Google Scholar



Shen-Ge Wang received his BS in instrumental mechanics from Changchun Institute of Optics in China and his PhD in optics from the University of Rochester. Currently, he is a principal scientist working at the Xerox Research Center Webster in Webster, NY. His recent work has focused on digital halftoning, printer modeling, and digital watermark technologies.


Robert Loce is a principal scientist and technical manager in the Xerox Research Center Webster. He joined Xerox in 1981 with an associate degree in optical engineering technology from MonroeCommunity College. While working in optical and imaging technology and research departments at Xerox, he received a BS in photographic science (RIT 1985), an MS in optical engineering (UR 1987), and a PhD in imaging science (RIT 1993). A significant portion of his earlier career was devoted to development of image processing methods for color electronic printing. His current research activities involve leading an organization and projects into new video technologies that are relevant to transportation and healthcare. He has publications and many patents in the areas of digital image processing, image enhancement, imaging systems, optics, and halftoning. He is a fellow of SPIE and a senior member of IEEE. His publications include a book on enhancement and restoration of digital documents, and book chapters on digital halftoning and digital document processing. 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.

© 2012 SPIE and IS&T
Shen-Ge Wang, Shen-Ge Wang, Robert P. Loce, Robert P. Loce, } "Moiré-free color halftoning using hexagonal geometry and spot functions," Journal of Electronic Imaging 21(1), 013017 (5 April 2012). https://doi.org/10.1117/1.JEI.21.1.013017 . Submission:


Color halftoning by indexing the visual-optimized dot profiles
Proceedings of SPIE (September 06 1998)
Multilevel screen design using direct binary search
Proceedings of SPIE (December 27 2001)
New methods for digital halftoning and inverse halftoning
Proceedings of SPIE (December 27 2001)
Multiresolution binary image embedding
Proceedings of SPIE (June 19 2003)
High capacity image barcodes using color separability
Proceedings of SPIE (January 25 2011)

Back to Top