JPEG图像处理技术图书

IEEE TRANSACTIONS ON IMAGE PROCESSING, VOL. 15, NO. 6, JUNE 2006 1365 JPEG Compression History Estimation for Color Images Ramesh (Neelsh) Neelamani, Member, IEEE, Ricardo de Queiroz, Senior Member, IEEE, Zhigang Fan, Senior Member, IEEE, Sanjeeb Dash, and Richard G. Baraniuk, Fellow, IEEE Abstract—We routinely encounter digital color images that were previously compressed using the Joint Photographic Experts Group (JPEG) standard. En route to the image’s current represen- tation, the previous JPEG compression’s various settings—termed its JPEG compression history (CH)—are often discarded after the JPEG decompression step. Given a JPEG-decompressed color image, this paper aims to estimate its lost JPEG CH. We observe that the previous JPEG compression’s quantization step introduces a lattice structure in the discrete cosine transform (DCT) domain. This paper proposes two approaches that exploit this structure to solve the JPEG Compression History Estimation (CHEst) problem. First, we design a statistical dictionary-based CHEst algorithm that tests the various CHs in a dictionary and selects the maximum a posteriori estimate. Second, for cases where the DCT coefficients closely conform to a 3-D parallelepiped lattice, we design a blind lattice-based CHEst algorithm. The blind algorithm exploits the fact that the JPEG CH is encoded in the nearly orthogonal bases for the 3-D lattice and employs novel lattice algorithms and recent results on nearly orthogonal lattice bases to estimate the CH. Both algorithms provide robust JPEG CHEst performance in practice. Simulations demonstrate that JPEG CHEst can be useful in JPEG recompression; the estimated CH allows us to recompress a JPEG-decompressed image with minimal distortion (large signal-to-noise-ratio) and simultaneously achieve a small file-size. Index Terms—Color, compression, history, Joint Photographic Experts Group (JPEG), lattice, quantization, recompression. I. INTRODUCTION ADIGITAL color image is a collection of pixels witheach pixel a three-dimensional (3-D) color vector. The vector elements specify the pixel’s color with respect to a chosen color space; for example, RGB, YCbCr, etc. [1], [2]. The Joint Photographic Experts Group (JPEG) is a commonly used standard to compress digital color images [3]. JPEG Manuscript received June 12, 2004; revised April 29, 2005. This work was supported by grants from the National Science Foundation, Air Force Office of Scientific Research, Office of Naval Research, Defense Advanced Research Projects Agency, and the Texas Instruments Leadership University Program. The associate editor coordinating the review of this manuscript and approving it for publication was Dr. Giovanni Poggi. R. Neelamani is with ExxonMobil Upstream Research Company, Houston, TX 77027-6019 USA (e-mail: neelsh@rice.edu). R. de Queiroz is with the Department of Electrical Engineering, Universidade de Brasilia, Brasilia, DF 70910-900, Brazil (e-mail: queiroz@ieee.org). Z. Fan is with Xerox Research and Technology, Xerox Corporation, Webster, NY 14580 USA (e-mail: ZFan@crt.xerox.com). S. Dash is with the IBM T. J. Watson Research Center, Yorktown Heights, NY 10598 USA (e-mail: sanjeebd@us.ibm.com). R. G. Baraniuk is with the Department of Electrical and Computer Engineering, Rice University, Houston, TX 77005-1892 USA (e-mail: richb@rice.edu). Digital Object Identifier 10.1109/TIP.2005.864171 compresses by quantizing the discrete cosine transform (DCT) coefficients of the image’s three color planes; see Fig. 1 for an overview. However, the various settings employed during JPEG compression and decompression are not standardized [3]. The following JPEG settings can be chosen by the user or an imaging device: 1) the color space used to compress the image’s three color planes independently; 2) the subsampling employed on each color plane during compression and the complementary interpolation em- ployed during decompression; 3) the quantization table used to compress each color plane. We refer to these settings as the image’s JPEG compression history (CH). An image’s CH is often not directly available from its current representation. For example, JPEG images are often imported into Microsoft Powerpoint or Word documents using graphics programs such as Microsoft Clip Gallery and then stored inter- nally using a decompressed format. JPEG images are also rou- tinely converted to lossless compression formats such as Win- dows bitmap (BMP) format (say, to create a background image for Windows or to feed a print driver) or Tagged Image File Format (TIFF). In such cases, the JPEG compression settings are discarded after decompression. We aim to estimate the JPEG CH from a given JPEG-decom- pressed color image. We refer to this problem as JPEG Com- pression History Estimation (CHEst). The CH, if available, can be used for a variety of applica- tions. The file-size of a JPEG image is typically significantly smaller than the file-size after the image’s conversion to BMP or TIFF format. The JPEG CH enables us to effectively recompress such converted BMP and TIFF images; JPEG-compressing the image with previous JPEG settings yields significant file-size reduction without introducing additional distortion. The JPEG CH can also be used by “smart” print servers to reduce arti- facts from received BMP images such as blocking and ringing due to previous JPEG compression. To alleviate such artifacts by adapting techniques described in [4] and [5], the print server would need the image’s JPEG CH. An image’s JPEG CH can also potentially be used as an authentication feature, for covert messaging, or to uncover the compression settings used inside digital cameras. The CHEst problem is relatively unexplored. Fan and de Queiroz proposed a statistical framework to perform CHEst for gray-scale images [6]; for a gray-scale image, the CH comprises only the quantization table employed during previous JPEG 1057-7149/$20.00 © 2006 IEEE 1366 IEEE TRANSACTIONS ON IMAGE PROCESSING, VOL. 15, NO. 6, JUNE 2006 Fig. 1. Overview of JPEG compression and decompression. operations. However, CHEst for color images remains unex- plored. This paper proposes two new frameworks to perform CHEst for color images. First, we derive a statistical framework for CHEst. We ob- serve that JPEG leaves its signature by quantizing the image’s DCT coefficients and forcing them to conform to near-periodic structures. We statistically characterize this near-periodicity for a single color plane. The resulting framework can be exploited to estimate a gray-scale image’s CH, namely, its quantization table. We extend the statistical framework to color images and design a dictionary-based CHEst approach. The dictionary con- sists of typical color transformations, subsampling factors, and interpolations. We adopt a maximum a posteriori (MAP) ap- proach to estimate the color image’s CH from the dictionary (1) with denoting the probability and , , the estimated compression color space, subsampling and associated interpo- lation, and quantization tables, respectively. Second, we consider the case when the transform from the color space used to perform quantization to the image’s current representation color space is affine and when no subsampling is employed during JPEG compression. For such a case, we develop a novel, blind, lattice-based CHEst algorithm. Such a blind approach is required when an unknown proprietary color transform is employed by JPEG. We demonstrate that after JPEG decompression, such an image’s DCT coefficients closely conform to a 3-D parallelepiped1 lattice structure de- termined by the affine color transform. Formally, a lattice is a set of integer linear combinations of a given set of vectors. The minimal set of vectors whose integer linear combinations span all lattice points is a lattice basis. We also demonstrate that the JPEG CH information is encoded in the nearly orthogonal bases that span the DCT lattices. Recently, [7] and [8] derived the geometric conditions for a lattice basis to contain the shortest nonzero lattice vector and the conditions to characterize such bases’ uniqueness. Using these recent insights, and using novel applications of existing lattice algorithms, we estimate the color image’s CH, namely, the affine color transform and the quantization tables. The proposed CHEst algorithms demonstrate excellent per- formance in practice. Further, we verify that CHEst allows us to recompress an image with minimal distortion [large signal-to- noise-ratio (SNR)] and simultaneously achieve a small file-size (see Figs. 7 and 8). 1A solid with six faces, each of which is a parallelogram. The rest of this paper is organized as follows. We first provide a brief overview of color transforms and JPEG in Sections II and III. We derive the statistical CHEst framework for gray-scale im- ages in Section IV and extend this framework to design dictio- nary-based CHEst for color images in Section V. In Section VI, we describe the 3-D lattice structure of a JPEG-decompressed image when JPEG uses an affine color transform and no subsam- pling. Section VII overviews the properties of nearly orthogonal lattice bases and some celebrated CHEst-relevant lattice prob- lems. In Section VIII, we describe lattice-based CHEst and its experimental performance. We demonstrate CHEst’s utility in JPEG recompression in Section IX and conclude in Section X. II. COLOR SPACES AND TRANSFORMS Color perception is a sensation produced when light excites the receptors in the human retina. Color can be described by specifying the light’s spectral power distribution. Such a de- scription is highly redundant because the human retina has only three types of receptors that influence color perception.2 Conse- quently, three numerical components are sufficient to describe a color; this is termed the trichromatic theory [2]. Based on the trichromatic theory, digital color imaging devices use three parameters to specify any color; the three parameters can be viewed as a 3-D vector. The color space is the reference coordinate system with respect to which the 3-D vector describes color [1], [2]. There exist many different coordinate systems or color spaces according to which a color can be specified. For example, the Commission Internationale de L’Éclairage (CIE) defined the CIE color space to specify all visible colors using positive , , and values [1], [2]. Other examples include different varieties of RGB (Red R, Green G, and Blue B) and YCbCr (luminance Y, and chrominances Cb and Cr) color spaces. These color spaces are related to each other and to reference color spaces such as the CIE via linear or nonlinear color transformations. For example, the popular Independent JPEG Group (IJG) JPEG implementation [9] converts the digital color image’s 0–255-valued R, G, B components to 0–255-valued Y, Cb, Cr components using the following transformation: (2) 2A fourth type of receptor is also present in the retina, but it does not affect color perception because it is effective only at extremely low light levels [2]. NEELAMANI et al.: JPEG COMPRESSION HISTORY ESTIMATION FOR COLOR IMAGES 1367 Fig. 2. Examples of JPEG quantization tables for 8 � 8 DCT blocks. The resulting YCbCr space is also referred to as the ITU.BT-601 YCbCr space [1]. The inverse color transformation from the ITU.BT-601 YCbCr space to the RGB space is given by (3) The transforms in both (2) and (3) are affine. Henceforth, we refer to the 3 3 matrix as the affine transform’s linear component and the 3 1 shift as the affine transform’s additive component. Later in this paper, we will invoke a variety of color spaces that are inter-related by affine or nonlinear transforms. We refer the reader to [1] and [2] for additional information on color, different color spaces, and transforms. III. EFFECTS OF JPEG COMPRESSION AND DECOMPRESSION In this section, we review the CHEst-relevant JPEG compres- sion and decompression steps. We do not describe all JPEG op- erations, but present a model that fully accounts for the effects of JPEG compression and decompression on an image. The model folds quantization and dequantization into one step, and ignores all entropy coding steps because these do not affect the final image. For further JPEG details, we refer the reader to [3]. Consider an observed color image represented in the hypothet- ical color space (see Fig. 1); , , and denote the three color planes. We refer to the space as the observation color space. Assume that the image was previously JPEG-compressed in the color space—termed the compression color space. JPEG compression essentially performs the following opera- tions independently on each color plane , , and in the space. 1) Optionally downsample each color plane (for example, retain alternate pixels to downsample by a factor of two); this process is termed subsampling. 2) Split each color plane into nonoverlapping 8 8 blocks. Take the two-dimensional (2-D) DCT of each block. 3) Quantize the coefficients at each DCT frequency to the closest integer multiple of the quantization step-size cor- responding to that frequency. For example, if denotes an arbitrary DCT coefficient and the quantization step- size for the corresponding DCT frequency, then the quan- tized DCT coefficient is obtained by round (4) See Fig. 2 for examples of quantization tables; each entry in the 8 8 quantization table is the quantization step-size for an 8 8 image block’s corresponding DCT coeffi- cient. JPEG decompression performs the following operations. 1) Compute the inverse DCTs of the 8 8 blocks of quan- tized coefficients. 2) Interpolate the downsampled color planes by repetition followed by optional spatial smoothing with a low-pass filter. The popular IJG JPEG implementation [9] uses a impulse response filter to smooth in the horizontal and vertical directions. 3) Transform the decompressed image to the desired color space using the appropriate to transformation. 4) Round-off resulting pixel values to the nearest integer so that they lie in the 0–255 range.3 Henceforth, we will refer to the zero frequency DCT coeffi- cient as the dc coefficient and the remaining 63 DCT coefficients as the ac coefficients. IV. CHEST FOR GRAY-SCALE IMAGES For gray-scale images, JPEG compression and decompres- sion replicates the steps outlined in Section III for a single color plane but without subsampling and interpolation. Hence, the CHEst problem simplifies to estimating the quantization tables employed during the previous JPEG compression. Due to JPEG’s quantization operations, the JPEG-decompressed gray-scale images’ DCT coefficient histograms exhibit a near-periodic structure with the period determined by the quan- tization step-size. In this section, to estimate the quantization table, we derive a statistical framework that characterizes the near-periodic structure. A. Statistical Framework An arbitrary DCT coefficient of a JPEG-decompressed gray-scale image can be obtained by adding to the corre- sponding quantized coefficient [see (4)] a round-off error term (5) 3In reality, round-offs occur also after the inverse DCT step. The model con- solidates all the round-off operations into one step for the sake of simplicity. 1368 IEEE TRANSACTIONS ON IMAGE PROCESSING, VOL. 15, NO. 6, JUNE 2006 As described in [6], we can model using a truncated Gaussian distribution (6) with the Gaussian’s variance, the truncated Gaussian’s support, and the normalizing constant. For example, and . Further, based on studies in [3], [10], we can model the DCT coefficients using a zero-mean Laplacian distribution (7) We have assumed that the parameter is known; in practice, we estimate from the observed decompressed image for each DCT frequency as described later in this section. From (7), we have (8) and hence (9) Now, assuming that the round-off error is independent of and , ’s distribution is obtained by convolving the distribu- tions for and (see Fig. 3); that is (10) for otherwise. (11) Let denote the set of the JPEG-decompressed image’s th-frequency DCT coefficients; that is, comprises one co- efficient from each 8 8 block. Given , we can obtain the MAP estimate of the quantization step used on the th-fre- quency coefficients during previous compression as (12) (13) where the DCT coefficients are assumed to be independent, and denotes the prior on . B. Algorithm Steps Using the statistical framework derived in the previous sec- tion, we can estimate the 8 8 quantization table , with , enumerating the 64 DCT frequencies, using the following steps. Fig. 3. Histogram of quantized DCT coefficients. The DCT coefficients from DCT frequency (4,4) of the gray-scale Lena image were subjected to quantization with step-size q = 10 during JPEG compression and then decompressed. Due to roundoff errors, the DCT coefficients are perturbed from integer multiples of 10. 1) For each frequency , compute the set of the observed decompressed image’s DCT coefficients. 2) Estimate the parameter from the observations as with the number of coefficients in the set . 3) Assuming a uniform prior on , use (11) with suitable parameters and to estimate (14) This algorithm is not entirely new; it is a refinement of the technique proposed by Fan and de Queiroz in [6]. While the core ideas remain the same, the final derived (11) differs because of significant variations in the starting points for the derivation and in the intermediate assumptions. Further, our derivation explicitly accounts for all normalization constants, thereby allowing us to extend the above approach to estimate the CH of color images. V. DICTIONARY-BASED CHEST FOR COLOR IMAGES In this section, we build on the quantization step-size estima- tion algorithm for gray-scale images from Section IV to perform CHEst for color images. A. Statistical Framework For color images, in addition to quantization, JPEG per- forms color transformation and subsampling along with the complementary interpolation. We observe that the DCT coeffi- cient histogram of each color plane exhibits the near-periodic structure of Fig. 3 introduced by quantization only when the image is transformed to the original compression color space and all interpolation artifacts are removed. Hence, we can obtain the MAP estimate of a color image’s CH as in (1) using a simple extension of the statistical framework for gray-scale images. Let denote the set of th-frequency DCT coefficients from the th-color plane, , 2, 3. Assume that is ob- tained by first transforming the image from the to the color NEELAMANI et al.: JPEG COMPRESSION HISTORY ESTIMATION FOR COLOR IMAGES 1369 space representation, then undoing the interpolation , and fi- nally taking the DCT of the color planes. Let denote the set of all . Then (15) assuming that all the coefficients and the choices of , , and are independent. In (15), the DCT coefficients’ conditional probability is computed using (11), which is a metric for how well the image DCT coefficients conform to a near-periodic structure. Hence, if , , and were actually employed during the previous JPEG compression, then the histogram of the th-frequency DCT coefficients would be nearly periodic, and the associated would be large. Consequently, the MAP estimate would be accurate. B. Algorithm Steps In general, the MAP estimation in (15) would require a search over all and . For practical considerations, we constrain the search to a dictionary comprising commonly employed compression color spaces and interpolations. Dictionary-based CHEst steps are as follows. 1) Choose a test color space and interpolation method from the dictionary. 2) Transform the observed color image to the color space . 3) Undo the effects of the test interpolation . To undo interpolation by simple repetition, simply downsample the color plane. To undo interpolation by repetition an