Regular Articles

Per-separation clustered-dot color halftone watermarks: separation estimation based on spatial frequency content

[+] Author Affiliations
Basak Oztan

University of Rochester, Department of Electrical and Computer Engineering, Rochester, New York 14627-0126

Gaurav Sharma

University of Rochester, Department of Electrical and Computer Engineering and Department of Biostatistics and Computational Biology, Rochester, New York 14627-0126

J. Electron. Imaging. 19(4), 043007 (December 16, 2010). doi:10.1117/1.3497615
History: Received January 05, 2010; Revised August 11, 2010; Accepted August 24, 2010; Published December 16, 2010; Online December 16, 2010
Text Size: A A A

Open Access Open Access

* Currently with the Department of Computer Science, Rensselaer Polytechnic Institute, Troy, New York 12180.

† This paper is available online as an open-access article, with color versions of several of the figures. In particular, Figs. 1, 2, 4 and 29 may be difficult to interpret without color; print readers should refer to the online version at http://SPIEDigitalLibrary.org for these figures.

A framework for clustered-dot color halftone watermarking is considered, wherein watermark patterns are embedded in individual colorant halftones prior to printing and embedded watermarks are detected from scans of the printed images after obtaining estimates of the individual halftone separations. The principal challenge in this methodology arises in the watermark detection phase. Typical three-channel RGB scanner systems do not directly provide good estimates of the four CMYK colorant halftones that are commonly used in color printing systems. To address this challenge, we propose an estimation method that, when used with suitably selected halftone periodicities, jointly exploits the differences in the spatial periodicities and the color (spectra) of the halftone separations to obtain good estimates of the individual halftones from conventional RGB scans. We demonstrate the efficacy of this methodology experimentally using continuous phase modulation for the embedding of independent visual watermark patterns in the individual halftone separations. Watermarks detected from the estimates of halftone separations obtained using the proposed estimation method have a much higher contrast than those detected directly. We also evaluate the accuracy of the estimated halftones through simulations and demonstrate that the proposed estimation method offers high accuracy.

Digital watermarks have recently emerged as an important enabling technology for security and forensics applications for multimedia36 and for hardcopy (Ref. 7, Chap. 5, and Ref. 8). In the hardcopy domain these techniques provide functionality that mimics or extends the capabilities of conventional paper watermarks that have been extensively utilized since their introduction in the late thirteenth century.9

Since most hardcopy reproduction relies on halftone printing, methods that embed the watermark in the halftone structure comprise one of the primary categories of hardcopy digital watermarks. These methods enable printed images to carry watermark data in the form of changes in the halftone structures, which are normally imperceptible but can be distinguished by appropriate detection methods. The proposed methods for detection of halftone watermarks can involve either scanning and digital processing or manual detection, wherein the ordinarily imperceptible watermark pattern is rendered visible by overlaying the printed image with a decoder mask such as a preprinted transparency. Because the manual process can also be simulated in the digital processing, manually detectable watermarks can typically also be detected via digital processing, whereas the converse does not necessarily hold. A number of techniques have been proposed for halftone-based watermarking in black and white, i.e., monochrome, printing systems.10a,10b,11a,11b,12a,12b,13,14a,14b,15a,15b,1617,18a,18b,1920 Most of these 8methods, however, do not directly generalize to color. Thus, there is an unmet need for color halftone watermarking techniques. This need is exacerbated by the fact that image content is often printed in color, particularly as color printing systems become more affordable and accessible.

Since the colorant halftone separations are printed sequentially and overlaid on the paper substrate, per-channel embedding and detection of watermark patterns is an attractive option that would extend monochrome watermarking methods to color. To detect the watermark patterns, one would like to acquire the constituent halftone separations used in the color printing system from the (overlaid) print. This would work, for example, if one could deploy a scanner with N color channels, where each color channel captures only one of the N colorants used in the printing system. In actual practice, desktop scanners commonly use RGB color filters to capture color. For three-color CMY printing, as illustrated in Fig. 1, there is a complementary relationship between the CMY colorants and RGB scanner channels: the cyan (C), magenta (M), and yellow (Y) colorants absorb light, respectively, over the spectral regions in which the red (R), green (G), and blue (B) scanner channels are sensitive. Thus, in an ideal setting, C, M, and Y colorant halftones may be estimated from the scanner R, G, and B channels, respectively. In practice, however, this is usually not feasible for a couple of reasons. First, typical printing systems utilize CMYK (four) colorants. The black (K) colorant absorbs uniformly across the spectrum, and thus it consistently appears in the scanner RGB channels. Second, so-called “unwanted absorptions” of the CMY colorants also cause cross-coupling, i.e., C, M, and Y halftone separations not only appear in the scan R, G, and B channels that complement their spectral absorption bands, respectively, but also in the two other channels as well. The image of Fig. 2 illustrates the couplings between the CMYK halftone separations in the scanner RGB channels. Due to these undesired couplings, the four C, M, Y, and K halftone separations cannot be directly obtained from individual R, G, and B scanner channel responses.

Graphic Jump LocationF1 :

Complementary relation between printer CMY colorants and scanner RGB channels. (Color online only.)

Graphic Jump LocationF2 :

RGB scan of a printed image that was divided into four stripes, where the stripes from left to right contain only C, M, Y, and K colorants, respectively. The K colorant can be consistently observed in all scan channels and cross-coupling between C, M, and Y colorant halftone separations can also be clearly seen in the scan R, G, and B channels. (a) RGB scan of CMYK halftone; (b) scan R channel; (c) scan G channel, and (d) scan B channel. (Color online only.)

In this paper, we present a methodology for estimating individual C, M, Y, and K halftones from RGB scans of printed images by jointly exploiting the differences between suitably selected spatial halftone periodicities and the differences in the spectral characteristics of the colorants. We use the proposed joint estimation scheme to extend, to color halftone printing, the halftone watermarking method using continuous phase modulation21 (CPM), which embeds and detects a visual watermark pattern. Our experiments demonstrate that the estimated halftones obtained via the proposed method improve the detection of the embedded CPM watermarks, offering much higher contrast for the detected watermark patterns than direct detection. Because the estimation methodology works only with electronic processing, the proposed method is not applicable to direct detection of the watermark in the printed image by physical overlay using a suitable decoder mask.

The framework we present may also be independently viewed as a general method for estimating CMYK halftone separations from RGB scans. We evaluate the accuracy of the proposed method in this context via simulations and compare against alternatives that use either the difference in spatial periodicities or in spectral characteristics alone (for the estimation of the halftones). Our results demonstrate that the combined methodology offers a significant advant-age.

The presented work builds on and extends our prior work in this area1 that addressed the more limited setting of three-color CMY printing and improves on our preliminary report on this effort2a,2b by utilizing a suitable model for analysis and processing. Note that our framework relies on data embedding in the individual spatial patterns of the constituent CMYK halftones. This is complementary to alternate methods2226 that have previously been proposed for data hiding in printed color images using spectral characteristics alone. Also, dot-on-dot27 color halftone watermarking with the same watermark embedded in each colorant channel can be viewed as an alternative, though rather restrictive, framework for extending monochrome halftone watermarking methods to color.28a,28b

The rest of the paper is organized as follows. Section 2 describes our framework for clustered-dot color halftone watermarking. Section 3 describes our method for estimating CMYK halftone separations from RGB scans exploiting the differences in spatial frequency and colorant spectra. The watermarking technique used to test our framework is described in Sec. 4, and the experimental results are presented in Sec. 5. Finally, in Sec. 6, we present conclusions.

For typical CMYK printing, the overall watermark embedding and extraction scheme that we consider is illustrated in Fig. 3. The input cover image

IC,M,Y,K(x,y)
is a contone CMYK image that is typically obtained by transforming a device-independent colorimetric representation of the image to the device-dependent CMYK values via a set of color conversions.29 The watermark wi for the i'th colorant separation Ii(x,y), where i is one of C, M, Y, or K, is embedded in the halftone separation Iih(x,y) in the halftoning stage. For the method we demonstrate, the watermark wi will in fact be a spatial pattern wi(x,y) corresponding, for instance, to rasterized text or a logo. The color halftone image IC,M,Y,Kh(x,y) is obtained by printing the constituent halftone separations in overlay. For the detection of the watermark patterns embedded in these separations, a scan IR,G,Bs(x,y) of the printed image is obtained using a conventional RGB scanner.

Graphic Jump LocationF3 :

Overview of per-channel basis clustered-dot color halftone watermarking by exploiting spatial frequency and color separation methodology.

To obtain estimates of the four constituent halftone separations from these three channels, additional information is required. Here, we rely on the spatial and spectral characteristics of rotated clustered-dot color halftones27 to provide a solution to this problem. If the halftone frequencies are suitably chosen, the differences in spatial periodicities and colorant spectra can be jointly exploited to obtain estimates of the C, M, Y, and K halftone separations from the R, G, and B channels

Iks(x,y)
, k ∈ {R, G, B}, of the scanned image—as is described in Sec. 3. Once the estimate Îih(x,y) is obtained for the ith colorant halftone, the monochrome watermark detection method can be applied to the separation in order to recover (an estimate of) the corresponding watermark wi.

Our goal is to obtain estimates of the CMYK halftone separations

Îih(x,y)
, i ∈ {C, M, Y, K}, from the RGB channels of the scanned image Iks(x,y), k ∈ {R, G, B}. The halftones Iih(x,y) and their estimates Îih(x,y), i ∈ {C, M, Y, K}, are binary images, where we adopt the convention that the values 1 and 0 correspond, respectively, to whether ink/toner i is, or is not, deposited (or estimated to be deposited) at the pixel position (x, y). On the other hand, the kth color channel of the scanner Iks(x,y) is a contone image, where the image value at pixel position (x, y) represents the fraction of the light reflected from the pixel (x, y) within the transmittance band of the kth scanner channel.

As we pointed out earlier, for typical desktop RGB scanners, coupling between the different colorant halftones in the scanned RGB image is inevitable. Figures 4 to 4 show enlarged views of a region from the digital M halftone separation, digital CMYK halftone separation overlay, scanned RGB image, and scan G channel of an image used in our experiments to test our framework, respectively. It is apparent not only is the halftone structure of the desired M separation visible, but due to the fact that the C, Y, and K separations also have absorption in the scanner G channel, the undesired halftone structure for these separations can be seen in the G channel with varying intensities. This interference can be also observed in the frequency domain. Figure 5 shows enlarged view of the log -magnitude Fourier spectrum of the G channel image for the experimental data around low-frequency regions. The Fourier spectrum exhibits peaks not only about the fundamental frequency vectors (and higher order harmonics) of the M separation, but also at the fundamental frequency vectors of C, Y, and K separations, and moiré frequencies. We exploit the fact that, when suitably designed, these peaks appear at distant locations in the frequency domain and unwanted frequency components can be eliminated by spatial filtering.

Graphic Jump LocationF4 :

(a) Enlarged view of a region from the digital M halftone separation of “Hats” halftone image used in our experiments

IMh(x,y), (b) the same region from the digital CMYK halftone overlay IC,M,Y,Kh(x,y), (c) approximately the same region from the RGB scanned color halftone print IR,G,Bs(x,y), (d) the region from the G channel image of the scanned print showing the couplings between the halftone structures of M and C, Y, and K separations IGs(x,y), and (e) the region from the M halftone estimate obtained using our methodology ÎMh(x,y). (Color online only.)

Graphic Jump LocationF5 :

Enlarged view of the log-magnitude Fourier spectrum of the G channel of the scanned “Hats” halftone print used in our experiments. For illustration purposes, the frequencies of the constituent halftone separations are indicated by arrow and text labels.

A schematic overview of our color halftone separation estimation algorithm is shown in Fig. 6. First, we obtain, via spatial filtering, an estimate of (black) K halftone separation using the scan RGB channel images jointly. Detailed description of this process is presented in Sec. 3b. The estimate of the K halftone separation is then utilized together with each of the scanner R, G, and B channel images to obtain estimates of the complementary C, M, and Y halftone separations, respectively, where once again, the spatial and spectral information is used jointly. The estimation process of CMY halftone separations is described in detail in Sec. 3c and a sample estimate obtained from the scanned image of Fig. 4 for the magenta separation, for approximately the same regions as Fig. 4, is shown in Fig. 4. For better understanding of the method and its limitations, we first present a joint spatial-spectral analysis for clustered-dot color halftones and also carry through a 1-D example for which the results are easy to interpret.

Graphic Jump LocationF6 :

Overview of CMYK halftone separation estimation using the RGB channels of the scanned image.

Fourier Analysis of Clustered-Dot Color Halftones

We analyze a general setting where the periodicities of the individual colorant halftones are defined by 2-D lattice tilings of the plane.30 The lattice

Λi
for the ith colorant separation is defined as Λi={Vin|nZ2}, where Vi is a 2×2 real-valued matrix, whose columns are the two linearly independent basis vectors that represent the periodicity of the halftone separation, n=[nxny]T, and Z denotes the set of integers. We first investigated the case where the contone image for the ith colorant, i ∈ {C, M, Y, K}, is a constant gray-level image Ii(x,y)=Ii, where x and y represent the spatial coordinates along the horizontal and vertical directions, respectively. In this case, the corresponding halftone image corresponds to shifted replicates of a single spot function si(x,y;Ii) placed at each point in Λi (Refs. 31 to 33). As this halftone is periodic on the lattice, it can be represented in terms of a Fourier series3133 as Display Formula
1Iih(x,y)=nx=ny=cnx,nyIiexp[j2π(Win)Tx],
where Display Formula
2cnx,nyIi=1UiUisi(x,y;Ii)exp[j2π(Win)Tx]dxdy,
are the Fourier series coefficients for the halftone spot function si(x,y;Ii), the matrix Wi=(Vi1)T includes the two linearly independent fundamental screen frequency vectors for the ith halftone separation as its columns, Ui is the unit cell for the lattice Λi and Ui is its area, n=[nxny]T and x=[xy]T. Recall, that in our notational convention halftone image Iih(x,y) values of 1 and 0 correspond, respectively, to regions with and without the ith colorant. The lattice Λi*={Win|nZ2} constitutes the reciprocal spatial frequency lattice for the lattice Λi. The Fourier spectrum of Iih(x,y) is comprised of impulses at frequencies uΛi*, that correspond to the Fourier spectrum of the halftone spot function si(x,y;Ii) sampled at u=Win, where u=[u,v]T, and u and v represent the frequency coordinates along the horizontal and vertical directions, respectively. To aid understanding, we include in Fig. 7 an illustration of a halftone periodicity lattice Λi and its reciprocal spatial frequency lattice Λi*, where the basis vectors corresponding to the columns of Vi and Wi are also indicated. Additional illustrations and mathematical details of the representation can be found in Refs. 8,3334.

Graphic Jump LocationF7 :

(a) Example of a halftone periodicity lattice

Λi and (b) the corresponding reciprocal spatial frequency lattice Λi*.

A similar representation can be obtained for the halftone image for a contone image with varying image content by decomposing the contone image in the form of a sifting integral and combining it with the Fourier series representation for the halftone for a constant gray level image as3536Display Formula

3Iih(x,y)=nx=ny=cnx,nyIi(x,y)exp[j2π(Win)Tx],
where Display Formula
4cnx,nyIi(x,y)=1UiUisix,y;Ii(x,y)×exp[j2π(Win)Tx]dxdy
are the Fourier series coefficients for the halftone spot function si[x,y;Ii(x,y)] for the image gray-level Ii(x,y). The functions cnx,nyIi(x,y) have spatial frequency bandwidths that are rather small as compared to the frequencies Win, nZ2. The Fourier spectrum of the halftone image obtained by a Fourier transform of the preceding identity therefore includes the spectrum of the original image (centered at dc) and the spectra of nonlinearly transformed versions cnx,nyIi(x,y) of the original image generated by the halftoning, each shifted to a corresponding frequency u=Win, nZ2 (Refs. 3536).

Having described a model for the individual halftone separations, we now consider an idealized model for the printing and scanning process. For a subtractive color reproduction system37 with transparent (nonscattering) CMYK colorants, the reflectance of the CMYK halftone overlay can be written as Display Formula

5r(x,y;λ)=rW(λ)i{C,M,Y,K}[ti(x,y;λ)]2=rW(λ)i{C,M,Y,K}[ti(λ)]2Iih(x,y),
where ti(λ) is the transmittance of the i'th colorant, and rW(λ) is the reflectance of the paper substrate at wavelength λ. Note that the incoming light is attenuated by traversing each colorant layer twice and also reflected by the paper substrate. The colorant transmittances are further modeled as per the Beer-Bouguer law (Ref. 38, Chap. 7) or the transparent formulation of Kubelka-Munk theory (Ref. 38, Chap. 7) as [ti(λ)]2=10di(λ), where di(λ) is the optical density for the i'th colorant layer (under to and fro passage). Equation 5 becomes Display Formula
6r(x,y;λ)=rW(λ)i{C,M,Y,K}10di(λ)Iih(x,y)=rW(λ)10i{C,M,Y,K}di(λ)Iih(x,y).

The k'th color channel of the scanner

Iks(x,y)
, k ∈ {R, G, B}, measures the fraction of the illuminant light reflected from the print within the transmittance band of the filter k. Using a narrow spectral band assumption for the scanner spectral sensitivities, we approximate the recorded kth scanner channel image as Display Formula
7Iks(x,y)=Iks(W)10i{C,M,Y,K}di(λk)Iih(x,y),
where the k'th scanner channel sensitivity is approximated by an impulse (Dirac delta function) at wavelength λk, and Iks(W)=rW(λk) is the scanned image value corresponding to the paper substrate in the kth color channel. The scanned image values can be converted to density as Display Formula
8dx,y;λk=dk(x,y)=log10Iks(x,y)Iks(W)=i{C,M,Y,K}dkiIih(x,y),
where dki=di(λk) is the optical density of the i’th colorant layer in the k’th scanner channel. Note that the density space representation for the scanned images in Eq. 8 avoids interseparation moiré since the colorants combine additively in the density space. On the other hand, moiré would be observed in the reflectance space representation given in Eq. 5 as the colorants combine multiplicatively in the reflectance space. Therefore, interseparation moiré would remain present in typical scanned clustered-dot color halftone images. Even though we recognize that the model is an extremely idealized approximation, use of the model provides an improvement over an alternate ad hoc approach as we shall subsequently see.

The constituent contone images

Ii(x,y)
, i ∈ {C, M, $$Y, K}, are band-limited to frequencies significantly smaller than the corresponding fundamental screen frequencies. Hence, most of the energy carried by the individual halftones is concentrated in narrow bands around the corresponding fundamental screen frequencies and lower order harmonics. As the colorants combine additively in the optical density space as per Eq. 8, the intensity of any frequency component in the Fourier spectrum of the overlay can be easily obtained by a weighted linear combination of the corresponding intensities in the Fourier spectra of the constituent halftones, where the weights correspond to the optical densities of the colorants in the scanner channel under consideration. Therefore, the frequency components that carry most of the energy in the individual halftone separations continue to carry (depending on the optical density) a significant portion of the energy in the colorant overlays as well. The interference resulting from the unwanted halftone separations can be eliminated/reduced by removing these frequency components. For this purpose, we utilize narrow-band band-reject filters Hi(u,v) to eliminate the unwanted frequency components of the i’th separation, where u and v represent the frequency coordinates along the horizontal and vertical directions, respectively. These filters may be efficiently implemented by utilizing the 2-D fast fourier transform (FFT). Our experimental results indicate that the interference resulting from the unwanted halftone separations is significantly reduced by eliminating the unwanted frequency components in a small circular neighborhood [typically around 3 to 4 lines per inch (lpi) radius] of the corresponding fundamental screen frequencies, their second-order harmonics, and their linear combinations.

Note that in the already described filtering process, we do not want the band-reject filter for the screen frequencies of the i'th separation to eliminate the frequency components that carry significant portions of energy in the other separations. The band-reject filters described in the preceding paragraph eliminate only the lower order harmonics of the unwanted fundamental screen frequencies. Therefore, unless the frequency components of the desired halftone separation intersect with the frequencies eliminated by the band-reject filters, these frequencies will be preserved. Note that for 2-D lattices defined in an underlying regular digital grid of pixels, the least common frequency for the separations in consideration is the least common right multiple39 of the basis matrices

Wi
's. For rotated halftone orientations, this frequency generally appears at higher order harmonics of the fundamental screen frequencies. Thus, the elimination of lower order harmonics of the halftone corresponding to a colorant does not cause the elimination of any lower order harmonics for the other colorant halftones. Note that this argument and our proposed method are restricted to clustered-dot mutually rotated colorant separations. The argument and the proposed method based on using the differences in spatial periodicities are not applicable, for instance, for dot-on/off-dot orientations.27 For dot-on/off-dot configurations, the halftone separations use the same fundamental screen frequency and spatial filtering to eliminate one colorant halftone will also result in the removal of desired frequency components from other colorant halftones as well.

In the following section, we describe the proposed CMYK halftone separation estimation methodology using the densities of the RGB color channels of the scanned images

dk(x,y)
, k ∈ {R, G, B}. As we proceed, we also provide 1-D illustrative examples that help explain the proposed technique. For a 1-D contone image Ii(x), i ∈ {C, M, Y, K}, the halftone spots are rectangular pulses, and for image values normalized between 0 and 1 representing white and black, respectively, the halftone spot for the gray-level Ii(x) is represented as si[x;Ii(x)]=rect[x/Ii(x)]. Note that the rectangular spots result from the halftoning process—a conversion from colorant amount to colorant surface coverage in our idealized model. The coefficient in Eq. 4 for this spot function can be computed as cnIi(x)=Ii(x)sinc[nIi(x)] and Eq. 3 becomes35Display Formula
9Iih(x)=Ii(x)1+2n=1sinc[nIi(x)]cos[2πfinx],
where fi is the fundamental screen frequency of the i’th separation. Using this representation, we generate examples of CMYK halftone separations shown in Fig. 8. For our example, we use the frequencies fC=1/3, fM=1/4, fY=1/7, and fK=1/5 (in arbitrary units). The estimation process works on the RGB scanner densities shown in Fig. 9, where the optical densities of the CMYK colorants were obtained using the scanned RGB image values of the corresponding colorants measured for the printer used in our experiments. Thus, these do reflect the nonidealities in the printing and scanning process that arise from the colorant interactions and are not simply based on our extremely idealized model of Eq. 8.

Graphic Jump LocationF8 :

Sample 1-D halftone patterns for the CMYK halftone separations. (a) Cyan; (b) magenta; (c) yellow; and (d) black.

Graphic Jump LocationF9 :

Predicted RGB scanner channel densities for the halftone images shown in Fig. 8. (a) Red; (b) green; and (c) blue.

Estimation of K Halftone Separation

All scanner channels are jointly used for the estimation of the K halftone separation as K colorant absorbs nearly uniformly across the three scanner RGB channels and therefore contributes similarly to

dk(x,y)
, k ∈ {R, G, B}. Apart from this use of spectral characteristics, the black (K) halftone separation is estimated by exploiting primarily the spatial characteristics of the halftone separations. The overall estimation process is illustrated in Fig. 10. First, we add the scanner channel densities together in dK(x,y)=kR,G,Bdk(x,y) to obtain a monochrome representation for the scanned image.

Graphic Jump LocationF10 :

Detailed overview of K halftone separation estimation exploiting the differences in spatial periodicity.

There are

24=16
possible overlapping combinations of the CMYK colorants on the printed paper that are referred to as Neugebauer primaries.37 As the Neugebauer primaries that include the K colorant are expected to have larger density than the others, one might consider obtaining the estimate of the K halftone from dK(x,y) by a simple thresholding operation. The accuracy of this approach depends on the optical densities of the individual colorants. Among the eight Neugebauer primaries that include the black (K) colorant, the primary with the lowest optical density is the K colorant printed alone. Among the remaining eight Neugebauer primaries that do not include the K colorant, the overlay of C, M, and Y colorants has the highest optical density. Therefore, to not estimate the overlay of CMY colorants as K colorant, the constraint Display Formula
10k{R,G,B}dkCMY<k{R,G,B}dkK
must be satisfied, where dkCMY denotes the density of the overlay of CMY colorants in the k'th color channel of the scanned image. In most color printing systems, these identities differ by small margins, and estimating the K colorant purely based on spectral differences results in poor performance, as shown in Sec. 3d, for the printer used in our experiments.

To reduce the interference caused by CMY colorants, we next use the band-reject filters

Hi(u,v),i{C,M,Y}
, to remove the unwanted frequency components of C, M, and Y halftone separations from dK(x,y) as Display Formula
11d̂K(x,y)=F1F{dK(x,y)}i{C,M,Y}Hi(u,v),
where F denotes the (spatial) Fourier transform operation. Black (K) halftone separation estimate is finally obtained by Display Formula
12ÎKh(x,y)=1ifd̂K(x,y)>τK0otherwise,
where τK is a threshold value, which can be taken as the average of the minimum and maximum values in d̂K(x,y).

Figure 11 illustrates the elimination of the unwanted C, M, and Y halftone structures from the Fourier spectrum of the experimental data using the band-reject filters

HC
, HM, and HY shown in Fig. 25 in Sec. 5. The K halftone separation estimate obtained using this method is shown in Fig. 12. Note that the densities dK(x,y) and d̂K(x,y) are transformed back to the reflectance space as IKs(x,y) and ÎKs(x,y) shown in Figs. 12, respectively, for a more meaningful representation. In addition, the estimation of K halftone separation using the 1-D densities shown in Fig. 9 is illustrated in Fig. 13. The elimination of the fundamental screen frequencies and the second-order harmonics of the CMY separations is reflected in the corresponding representations given in Eq. 9 by changing the lower bound of the summations to n = 3.

Graphic Jump LocationF11 :

Spatial filtering for estimation of K halftone

IKh(x): (a) enlarged view of the log-magnitude Fourier spectrum of dK(x,y) for the scanned “Hats” print used in our experiments and (b) the elimination of unwanted frequency components of C, M, and Y halftone separations using the narrow-band band-reject filters shown in Figs. 24 to 24 in Sec. 5, respectively.

Graphic Jump LocationF12 :

Sample estimation result for the K halftone separation for the region shown in Fig. 4 from the “Hats” halftone image used in our experiments: (a) the digital K halftone separation

IKh(x,y), (b) the monochrome representation IKs(x,y), (c) the filtered image 3ÎKs(x,y), and (d) the K halftone estimate 3ÎKh(x,y).

Graphic Jump LocationF13 :

Illustration of the K halftone separation estimation using the scanner channel densities shown in Fig. 9: (a) the density for the monochrome representation

dK=k{R,G,B}dk,(b) the filtered density 5d̂K, and (c) the K halftone estimate, which matches the original shown in Fig. 8.

Graphic Jump LocationF25 :

Narrow-band band-reject filters for eliminating the frequency components of the CMY halftone separations from the densities of the RGB color channels of the scanned images for the frequency vector configuration shown in Fig. 24. (a) cyan, (b) magenta, and (c) yellow.

Estimation of C, M, and Y Halftone Separations

The efficacy of using the differences in spatial periodicity

1
and colorant spectral differences28 for the estimation of CMY halftone separations from the RGB channels of the scanned images has been shown previously for three-colorant CMY printing. For CMYK printing, however, the black (K) colorant introduces additional challenges so that these methods alone are insufficient to provide accurate estimates.

If the additive in density model of Eq. 8 were exact, the spatial filtering procedure to eliminate undesired halftone separations would provide accurate estimates of the C, M, and Y halftones. However, the actual colorant interactions deviate significantly from the ideal model particularly, at high densities associated with overlaps of the K colorant. As a result, when estimating, for example, the C halftone, removal of the frequency components of the K halftone separation from the RGB scans by spatial filtering also eliminates parts of the C halftone that are overlaid with the K colorant halftone. Thus, spatial filtering alone does not enable recovery of the C, M, and Y halftones. An attempt to separate the halftones based purely on the spectral characteristics (i.e., scanner channel densities) faces similar challenges because the scanned the image values for the Neugebauer primaries including K differ only by small margins. We, therefore, address this problem by utilizing both techniques jointly, where in addition to the scan RGB channel images, we use the K halftone separation estimate for the estimation of the complementary CMY halftone separations, respectively.

We describe only the estimation of the M halftone separation, with examples illustrating the images obtained during the process. Other halftone separations can be estimated similarly. A detailed overview of the M halftone separation estimation is illustrated in Fig. 14.

Graphic Jump LocationF14 :

Detailed overview of M separation estimation using the scanner G channel image and the K separation estimate.

The M halftone separation is estimated from its complementary G channel of the scanned image and the K halftone separation estimate obtained previously. First, an estimate of the overlap of M and K halftone separations is obtained by using the G scan channel density

dG(x,y)
. As the colorants combine additively in the density space, the densities of the Neugebauer primaries that include both M and K colorants is larger than the densities of the constituent colorants. In other words, the overlays that include both M and K colorants will appear darker than the constituent colorants in the G color channel of the scanned image. Using this property, we obtain an estimate of the MK halftone overlap as Display Formula
13ÎMKh(x,y)=1ifdG(x,y)>τMK0otherwise,
where τMK is a threshold value and, in our convention, the values 1 and 0 correspond, respectively, whether both M and K toners/inks are, or are not, estimated to be deposited at the pixel position (x, y). The threshold τMK is chosen midway between the G scanner channel densities for the Neugebauer primaries formed by the MK overlay and that of the M or K (alone) primary, whichever is higher. These densities can be measured from scans by segmenting and averaging interior regions corresponding to the Neugebauer primaries.

The accuracy of this estimation step depends on the optical densities of the individual colorants in the scan G channel. There are four Neugebauer primaries that include both the magenta (M) and black (K) colorants. In this group, the primary with the lowest optical density corresponds to the overlay of M and K colorants alone. Among the remaining 12 Neugebauer primaries, the overlay of C, M, and Y, and the overlay of C, Y, and K colorants have the highest optical densities. To ensure that these primaries are not incorrectly assigned as the MK Neugebauer primary, the constraints Display Formula

14dGCMY<dGMKanddGCYK<dGMK
must be satisfied, where dGCMY,dGCYK, and dGMK are the G channel densities for the Neugebauer primaries corresponding to the overlay of the CMY, CYK, and MK colorants, respectively. In addition, to be able to distinguish the optical density of the overlap of M and K colorants from the optical densities of both M and K colorants, neither of the optical densities of the M and K colorants in scan G channel can be ∞, in other words, neither of the M and K colorants can have perfect absorption, which typically is the case in most color printing systems. This can be observed in the experimental data in Fig. 15 that shows the scan RGB values for the 16 Neugebauer primaries for the printer used in our experiments.

Graphic Jump LocationF15 :

Scan RGB (a) reflectance space and (b) density space values for the 16 Neugebauer primaries for the printer used in our experiments.

Next, the estimate

IMKh(x,y)
is subtracted from the previously obtained K halftone separation estimate ÎKh(x,y) to get an estimate of ÎKh(x,y) that represents K halftone structures that are not overlapping with M halftone structures. The unwanted frequency components of C and Y halftone separations are then eliminated from the scan G channel density using the band-reject filters HC and HY, respectively, by Display Formula
15d̂MK(x,y)=F1F{dG(x,y)}i{C,Y}Hi(u,v).
This image approximates the density of the overlay M and K halftone separations in the scanner G channel. Figure 16 illustrates the elimination of the unwanted frequency components of C and Y halftone structures in the Fourier spectrum of the density of the G channel of the experimental data using the band-reject filters HC and HY shown in Sec. 5 in Figs. 24, respectively.

Graphic Jump LocationF16 :

Spatial filtering for estimation of the density of M and K halftone overlay

5d̂MK(x,y): (a) enlarged view of the log-magnitude Fourier spectrum of the G scan channel density of the scanned “Hats” halftone print used in our experiments and (b) the elimination of unwanted frequency components of C and Y halftone separations using the band-reject filters shown in Figs. 4,24, respectively.

Graphic Jump LocationF24 :

Frequency vectors for stable moire-free C, M, Y, and K halftone screens.

We then use

ÎKh(x,y)
as a mask to clean out the K halftone structures that do not overlap with M halftone structures from d̂MK(x,y) as d̂M(x,y)=d̂MK[1ÎKh(x,y)]. The M halftone separation estimate is finally obtained by Display Formula
16ÎMh(x,y)=1ifd̂M(x,y)>τM0otherwise,
where τM is a threshold that is set midway between the scanner G channel densities for the M (alone) Neugebauer primary and the CY Neugebauer primary, which has the next higher density.

We previously showed in Fig. 4 a sample estimate for the M halftone separation using the G color channel of the scanned image shown in Fig. 4 and the K halftone estimate shown in Fig. 12. To illustrate the method, the images obtained in intermediate stages of the proposed estimation process are shown in Fig. 17. Note that the densities

d̂MK(x,y)
and d̂M(x,y) are transformed back to the reflectance space as ÎMKs(x,y) and ÎMs(x,y) shown in Figs. 17 and (e), respectively, for a more meaningful representation. In addition, the estimation of M halftone separation using the 1-D scan G channel density shown in Fig. 9 and the previously obtained K halftone estimate shown in Fig. 13 is illustrated in Fig. 18. The elimination of the fundamental screen frequencies and the second-order harmonics of the C and Y separations is reflected in the corresponding representations given in Eq. 9 by changing the lower bound of the summations to n = 3.

Graphic Jump LocationF17 :

Images obtained during the estimation of M halftone separation corresponding to the region shown in Fig. 4 from the “Hats” halftone image used in our experiments: (a) the estimate of M and K colorant overlap

3ÎMKh(x,y), (b) the K halftone estimate obtained previously 3ÎKh(x,y), (c) the estimate of K halftone structures that are not overlapping with M halftone structures 3ÎKh(x,y), (d) the estimate of M and K halftone overlay 3ÎMKs(x,y), (e) the image after removing the K only halftone structures by 3ÎKh masking 3ÎMs(x,y), and (f) the M halftone estimate 3ÎMKh(x,y).

Graphic Jump LocationF18 :

Illustration of the M halftone separation estimation using the density shown for the G scan channel in Fig. 9 and the K halftone estimate shown in Fig. 13: (a) the estimate of MK halftone overlap, (b) the estimate of K halftone separation not overlapping with M halftone, (c) the filtered density

3d̂MK multiplied by [13ÎKh(x)], and (d) the M halftone estimate, which matches the original shown in Fig. 8.

Performance Analysis: Accuracy of the Estimated Halftones

Given the dot gain and the geometric distortion in the printing and other nonidealities in the print-scan process, it is difficult to experimentally evaluate the performance of the estimation process quantitatively. Therefore, we utilize a simulation framework, where the effect of print-scan is simulated by the Neugebauer model37 and spatial blur. The overview of the simulation is shown in Fig. 19. First, the individual colorant separations of the contone image

IC,M,Y,K(x,y)
are halftoned. Next, the effect of the print-scan is simulated on the digital halftone IC,M,Y,Kh(x,y). Estimates of the halftone separations ÎC,M,Y,Kh(x,y) are then obtained from IR,G,Bs(x,y) using our methodology, and finally, the performance metrics for the estimates of each separation are calculated.

Graphic Jump LocationF19 :

Simulation model for evaluating the performance of the estimation process.

Twenty-four images from the Kodak PhotoCD image set, as shown in Fig. 20, were used in our simulations. The CMYK versions of these images were obtained using Adobe® Photoshop® CS4 with default CMYK settings. We then generated clustered-dot halftones for these images in 3.84- ×2.56-in. format for a 600 dots per inch (dpi) CMYK color printer. Digital rotated clustered-dot CMYK halftone screens with angular orientations close to the conventional singular moiré-free 15-, 75-, and 45-deg rotated clustered-dot halftones were utilized for our simulations.40 The fundamental frequency vectors for these screens are shown in Fig. 21. Since the objective was to evaluate the accuracy of the estimated halftones, no watermarks were utilized in these simulations.

Graphic Jump LocationF20 :

Kodak PhotoCD image set used in the simulations. These images are referred to as Image 1 to Image 24, enumerated from left-to-right and top-to-bottom, respectively.

Graphic Jump LocationF21 :

Frequency vectors for singular moiré-free C, M, Y, and K halftone screens.

The effect of print-scan is simulated for a 600 dpi CMYK color printer and RGB color scanner combination. For this purpose, we utilize a Neugebauer model37 in scanner RGB space. Binary CMYK printer values are mapped to contone RGB scanner values through a look-up table (LUT) transformation. For this purpose, the average RGB values of 16 Neugebauer primaries for the printer used in our experiments were measured from 0.5-×0.5-in.

2
printed patches and stored in the LUT. Figure 15 shows the measured scan RGB values for the 16 Neugebauer primaries. The CMYK values of each pixel in the color halftone are mapped to the RGB scanner values using the LUT. Note that since we use actual measured values, spectral nonidealities in the colorant interactions and in the scanner response are automatically incorporated in the modeling process. To also model spatial nonidealities, we performed a spatial blur on the individual RGB channels of the resulting image, analogous to the methodology of Ref. 41. For this purpose, a 7×7 Gaussian low-pass filter (DC response normalized to 1) with standard deviation approximately equal to 0.96 pixels was employed. For the 600-dpi printer resolution we assumed, this corresponds to a standard deviation of 40 μm, and the blur causes spreading in an approximately 120 μm radius. Note that a more severe blur increases the impact of the spatial interactions, and consequently, the accuracy of the estimates would decrease. Similarly, a milder blur brings the simulation closer to a spatially ideal hard-dot setting,4243 and thus, the accuracy of the estimates would be higher.

Using the described methodology, we obtained estimates of the individual halftone separations. The band-reject filters designed for these frequency vectors are shown in Fig. 22. For purpose of visual comparison, enlarged views of the original CMYK halftone separations and their estimates from a region in Image 3 in Fig. 20 (also referred to as the “Hats” image in the remaining parts of this paper) are shown in Fig. 23.

Graphic Jump LocationF22 :

Narrow-band band-reject filters for eliminating the frequency components of the CMY halftone separations from the densities of the RGB color channels of the scanned images for the frequency vector configuration shown in Fig. 21. (a) cyan, (b) magenta, and (c) yellow.

Graphic Jump LocationF23 :

Enlarged view of the digital halftone separations: (a) to (d) from a region in the “Hats” image and (e) to (h) the corresponding estimates obtained using the differences in spatial periodicity and colorant spectra. (a) and (e), cyan; (b) and (f), magenta; (c) and (g), yellow; (d) and (h), black.

The performance of the described halftone separation estimation methodology is evaluated by the accuracy, sensitivity, and specificity, which are common performance measures for binary data classification techniques.44 In our context, they represent the percentage of overall, majority, and minority pixels that are correctly classified, respectively, and are computed for each colorant as Display Formula

17accuracy=N tp +N tn N tp +N tn +N fp +N fn ×100,sensitivity=N tp N tp +N fn ×100,specificity=N tn N tn +N fp ×100,
where N tp is the number of true positive predictions corresponding to number of majority pixels that are predicted correctly, N tn is the number of true negative predictions corresponding to number of minority pixels that are predicted correctly, N fp is the number of false positive predictions corresponding to the number of minority pixels that are predicted as majority, and N fn is the number of false negative predictions corresponding to the number of majority pixels that are predicted as minority. The estimation performance for each colorant is listed in Table 1. Around 95% accuracy is achieved for C, around 98% accuracy is achieved for K halftone separations, and relatively lower accuracies are achieved for the M and Y halftone separations. This difference is caused by the varying levels of spectral interference observed in the scanner RGB channels. As we can see in Fig. 2, relatively less interference is observed in the scanner R channel compared to the G and Y channels. Therefore, the C and K halftone separations can be estimated better than the M and Y halftone separations. Nevertheless, as we demonstrate later in Sec. 5, these estimates enable successful detection of the embedded watermark patterns.

Table Grahic Jump Location
Performance of the proposed halftone separation estimation methodology for the image set shown in Fig. 20.