AM-FM hybrids (Fig.~\ref{img63_fig}) refer to halftoning algorithms that vary, according to tone, both the size and spacing of dots \cite{lau_arce_gallagher}.  While various AM-FM halftoning techniques have been introduced over the years, the best techniques are those that generate green-noise halftone patterns -- binary dither patterns created exclusively of mid-frequency spectral components.  The goal of green-noise is to distribute minority pixel clusters in a homogeneous and isotropic fashion.  The average size of these clusters can vary with smaller clusters leading to halftoned images with higher spatial resolution and better edge detail and larger clusters leading increased halftone robustness (the ability of the pattern to resist the distortions introduced during the printing process).  As a tunable model, green-noise has, as a limiting case, blue-noise, and by using green-noise, binary display devices that were previously restricted to AM halftoning techniques can now combine the maximum dispersion attributes of blue-noise with the clustering attributes of AM halftones \cite{lau_arce_gallagher}.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsection{Error Diffusion with Output-Dependent Feedback}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{figure}[t!]

\centerline{\includegraphics{./IMG_files/img66}}

\caption{The error diffusion with output-dependent feedback algorithm.}

\label{chap5_fig03}

\end{figure}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

In an effort to address the ``print-ability'' of stochastic dither patterns produced by error diffusion, Levien \cite{levien} added an output-dependent feedback term (Fig.~\ref{chap5_fig03}) such that the coarseness of resulting dither patterns could be tuned through a scalar constant.  In this algorithm, the output pixel, $y[n]$, is determined as:

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{eqnarray}

y[n]  & = & \left\{ \begin{array}{lcl}

    1 & , & \mbox{if } (x[n]+x_e[n]+x_h[n]) \ge 0 \\

        0 & , & \mbox{else}

        \end{array} \right.

\label{err_diff_hyst_thr_eqn}

\end{eqnarray}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

where $x_h[n]$ is the hysteresis or feedback term defined as

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{eqnarray}

x_h[n] & = & h \sum_{i=1}^{N}a_i \cdot y[n-i]

\label{hyst_trm_eqn}

\end{eqnarray}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

with $\sum_{i=0}^{N}a_i=1$ and $h$ an arbitrary constant.  Referred

to as the {\em hysteresis constant}, $h$ acts as a tuning parameter with

larger $h$ leading to coarser output textures \cite{levien} as $h$

increases ($h>0$) or decreases ($h<0$) the likelihood of a minority

pixel if the previous outputs were also minority pixels.  Eqn.~(\ref{hyst_trm_eqn}) can also be written in vector notation as:

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{eqnarray}

x_h[n] & = &  h {\bf a}^{\rm T} {\bf y}[n]

\end{eqnarray}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

where ${\bf a}=[a_1,a_2,\ldots,a_N]^{\rm T}$ and ${\bf y}[n]=[y[n-1],y[n-2],\ldots,y[n-N]]^{\rm T}$.  The calculation of the parameters ${\bf y}_e[n]$ and $x_e[n]$ remain unchanged from ordinary error diffusion.  Unlike ordinary error diffusion, Levien's algorithm produces strong diagonal textures when coupled with a normal left-to-right raster scan.  For this reason, an alternate scanning order such as the serpentine raster scan is mandatory \cite{lau_arce_gallagher}.  Shown in Fig.~\ref{chap5_flt00} is the arrangement of two hysteresis and two error filter coefficients first prescribed by Levien.

Green-noise is a statistical model describing the spatial and spectral characteristics of visually pleasing dither patterns composed of a random arrangement of clustered dots. Point process statisticians have long described cluster processes such as those seen in green-noise by examining the cluster process in terms of two separate processes: (i) the parent process that describes the location (centroid) of clusters, and (ii) the daughter process that describes the shape of clusters. In AM halftoning, clusters are placed along a regular lattice, and therefore, variations in AM patterns occur in the cluster shape. In FM halftoning, cluster shape is deterministic, a single pixel. It is the location of clusters that is of interest in characterizing FM patterns. Green-noise patterns, having variation in both cluster shape and cluster location, require an analysis that looks at both the parent and daughter processes.

    Looking first at the parent process p, p represents a single sample of the parent process such that p = {xi : i = 1, . . . ,Nc} where Nc is the total number of clusters. For the daughter process d, d represents a single sample cluster of d such that d = {yj : j = 1, . . . ,M} where M is the number of minority pixels in cluster d. By first defining the translation or shift in space Tx(B) of a set B = {yi : i = 1, 2, . . .} by x, relative to the origin, as:

Tx(B) = {yi − x : i = 1, 2, . . .} (1.18)

and then defining di as the ith sample cluster for i = 1, . . . ,Nc, a sample G of the green-noise halftone process G is defined as:

G =Xxi2pTxi(di) =Xxi2p {yji − xi : j = 1, . . . ,Mi}, (1.19)

the sum of Nc translated clusters. The overall operation is to replace each point of the parent sample p, of process p, with its own cluster di , of process d.

    In order to derive a relationship between the total number of clusters, the size of clusters and the gray level of a binary dither pattern, Ig is defined as the binary dither pattern resulting from halftoning a continuous-tone discrete-space monochrome image of constant gray level g, and Ig[n] is defined as the binary pixel of Ig with pixel index n. From the definition of (B) as the total number of points of  in B, G(Ig) is the scalar quantity representing the total number of minority pixels in Ig, and p(Ig) is the total number of clusters in Ig with p(Ig) = Nc. The intensity, I, being the expected number of minority pixels per unit area can, now, be written as:

I = G(Ig) N(Ig) , (1.20)

the ratio of the total number of minority pixels in Ig to N(Ig), the total number of pixels composing Ig. Given (1.20), ¯M , the average number of minority pixels per cluster in Ig, is:

¯M = G(Ig) p(Ig) = I · N(Ig) p(Ig) , (1.21)

the total number of minority pixels in Ig divided by the total number of clusters in Ig.

    Although obvious, (1.21) shows the very important relationship between the total number of clusters, the average size of clusters, and the intensity for Ig. AM halftoning is the limiting case where p(Ig) is held constant for varying I, while FM halftoning is the limiting case where ¯M is held constant for varying I. In addition, (1.21) says that the total number of clusters per unit area is proportional to I/ ¯M . For isolated minority pixels (blue-noise), the square of the average separation between minority pixels (b) is inversely proportional to I, the average number of minority pixels per unit area [11]. By determining the proportionality constant using b = p2 for I = 12 , the relationship between b and I is determined as b = D/p I.

    In green-noise, it is the minority pixel clusters that are distributed as homogeneously as possible, leading to an average separation (center-to-center) between clusters (g) whose square is inversely proportional to the average number of minority pixel clusters per unit area, I/ ¯M . Using the fact that limM!1 g = b, the proportionality constant can be determined such that g is defined as:

g = 8><>:D/q(g)/ ¯M , for 0 < g  1/2D/q(1 − g)/ ¯M , for 1/2 < g  1, (1.22)

the green-noise principle wavelength. This implies that the parent process, p, is itself a blue-noise point process with intensity I/ ¯M .

    If we assume a stationary and isotropic green-noise pattern, the pair correlation will have the form of Fig. 1.33 (left) given that:

    1. Daughter pixels, on average, will fall within a circle of radius rc centered around a parent point such that r2 c = ¯M (the area of the circle with radius rc is equal to the average number of pixels forming a cluster).

    2. Neighboring clusters are located at an average distance of g apart.

    3. As r increases, the influence that clusters have on neighboring clusters decreases.

The result is a pair correlation that has: (a) a non-zero component for 0  r < rc due to clustering, (b) a decreasing influence as r increases, and (c) peaks at integer multiples of g indicating the average separation of pixel clusters. Note that the parameter rc is also indicated by a diamond placed along the horizontal axis in Fig. 1.33 (left).

    In the spectral domain, the placement of clusters g apart leads to a strong spectral peak in P(f) at f = fg, the green-noise principle frequency:

fg =8><>:q(g)/ ¯M /D , for 0 < g  1/2q(1 − g)/ ¯M /D , for 1/2 < g  1. (1.23)

From (1.23) we make several intuitive observations: (i) as the average size of clusters increases, fg approaches DC, and (ii) as the size of clusters decreases, fg approaches fb. Fig. 1.33 (right) illustrates the desired characteristics of P(f) for G showing three distinct features: (a) little or no low frequency spectral components, (b) high-frequency spectral components that diminish with increased clustering and (c) a spectral peak at f = fg.

    Noting the gray-scale ramps of Fig. 1.29 which were produced using Levien’s filer kernel with hysteresis constants 0.5, 1.0, and 1.5, Levien’s kernel produces patterns with vertical artifacts at low h (near h = 0) and strong horizontal artifacts at high h (near h = 2). Lau and Arce [33] note that these artifacts can be eliminated by changing the proportions of feedback through the horizontally and vertically aligned feedback weights. Using balanced weights, Lau and Arce are able to produce the gray-scale ramps of Fig. 1.34.

1–3–3 Adaptive Hysteresis

Optimizing the hysteresis constant for a given printing process is achieved by specifying the parameter h according to the desired robustness, but as a constant, error diffusion with output-dependent feedback may, like AM halftoning, sacrifice spatial resolution at certain gray levels for pattern robustness at other levels. In light of this consequence of a hysteresis constant, Lau and Arce [33] propose using an adaptive hysteresis value that varies according to the gray level of the current input pixel. The approach that they first prescribe is to select the minimum h such that the output tone is within a pre-specified tolerance of the input (Fig. 1.35 (left)). A second approach they prescribe is to vary h according to the frequency content of the input image (Fig. 1.35 (right)). In this scheme, the resulting halftoned image will be composed of large clusters in DC regions, where distortions are most noticeable to the human eye, and small clusters near edges where distortions are least noticeable and spatial details require small clusters in order to be preserved.

1–3–4 Green-Noise Masks

In an effort to address the computational complexity of error diffusion with output-dependent feedback, Lau et al [34] introduced an algorithm for the construction of green-noise masks. Just like blue noise masks, green-noise masks offer the absolute minimum in computational complexity – leading to halftone patterns that are faster and less expensive to produce. Figure 1.36 shows a green-noise dither array and its corresponding halftoned image.