IEEE TRANSACTIONS ON IMAGE PROCESSING, VOL. 15, NO. 6, JUNE 2006
`
`1379
`
`Lossless Compression of Color Mosaic Images
`
`Ning Zhang and Xiaolin Wu, Senior Member, IEEE
`
`Abstract—Lossless compression of color mosaic images poses a
`unique and interesting problem of spectral decorrelation of spa-
`tially interleaved R, G, B samples. We investigate reversible loss-
`less spectral-spatial transforms that can remove statistical redun-
`dancies in both spectral and spatial domains and discover that a
`particular wavelet decomposition scheme, called Mallat wavelet
`packet transform, is ideally suited to the task of decorrelating color
`mosaic data. We also propose a low-complexity adaptive context-
`based Golomb–Rice coding technique to compress the coefficients
`of Mallat wavelet packet transform. The lossless compression per-
`formance of the proposed method on color mosaic images is appar-
`ently the best so far among the existing lossless image codecs.
`
`Index Terms—Context quantization, entropy coding, digital
`camera, image compression.
`
`I. INTRODUCTION
`
`M OST digital cameras use image sensors that sample only
`
`one of the three primary colors at each pixel position.
`Specifically, each pixel is covered with a filter and records just
`one of the three primary colors: red, green or blue. These pri-
`mary color samples are interleaved in a two-dimensional (2-D)
`grid, or color mosaic, resembling a three-color checkerboard.
`The most popular single CCD color mosaic pattern is the one
`proposed by Bayer [1]. To reconstruct the true continuous-tone
`color, a procedure called color demosaicking is needed to inter-
`polate the other two missing primary colors at each pixel. The
`image quality of digital cameras largely depends on the perfor-
`mance of the color demosaicking process.
`Image data compression is an important component of dig-
`ital camera design and digital photography. It is more than just
`an issue of saving storage and bandwidth, but rather to be con-
`sidered in light of overall system performance and functionality,
`particularly in relation to color demosaicking. Currently, all dig-
`ital cameras carry out color demosaicking prior to compression,
`apparently due to the considerations of easy user interface and
`device compatibility. However, industrial policy and standard
`issues aside, in our opinion, this design is suboptimal. Color
`demosaicking triples the amount of raw data by generating R,
`G, B bands via color interpolation. Ironically, the task of com-
`pression needs to decorrelate the three bands, which essentially
`attempts to reverse engineer the color interpolation process of
`demosaicking. This demosaicking-first and compression-later
`
`Manuscript received September 29, 2004; revised April 18, 2005. This
`work was supported in part by the Natural Sciences and Engineering Research
`Council of Canada under the NSERC-DALSA Industrial Research Chair in
`Digital Cinema. The associate editor coordinating the review of this manuscript
`and approving it for publication was Dr. Giovanni Poggi.
`The authors are with the Department of Electrical and Computer Engi-
`neering, McMaster University, Hamilton, ON L8K 4K1 Canada (e-mail:
`ningzhang@mail.ece.mcmaster.ca; xwu@ece.mcmaster.ca).
`Digital Object Identifier 10.1109/TIP.2005.871116
`
`design unnecessarily increases algorithm complexity, reduces
`compression ratio, and burdens the on-camera I/O bandwidth.
`In this paper, we propose to compress and store the color
`mosaic data directly, and perform demosaicking to reconstruct
`the R, G, B bands afterward, possibly offline. This relieves the
`camera from the tasks of color demosaicking and color decorre-
`lation and also reduces the amount of input data to compression
`codec in the first place. The new workflow can potentially re-
`duce on-camera computing power and I/O bandwidth. More im-
`portantly, the new design allows lossless or near-lossless com-
`pression of raw mosaic data, which is the main theme of this
`paper.
`For many high-end digital photography applications, such
`as digital archiving of precious museum arts and relics, pro-
`fessional advertising, and digital cinema for which high image
`quality is paramount, it is crucial to have the original color mo-
`saic data in lossless format. Our recent results in color demo-
`saicking research [2] indicate that superior image quality can be
`obtained by more sophisticated color demosaicking algorithms
`than those implemented on camera, provided that original mo-
`saic data are available. Furthermore, other image/video appli-
`cations, such as super-resolution imaging and motion analysis,
`should also benefit from lossless compression of color mosaic
`data, in which even subpixel precision is much desired.
`Lossless compression of mosaic color images poses a unique
`and interesting problem of spectral decorrelation (or more
`generally statistical modeling) of spatially interleaved R, G, B
`samples. Because a color mosaic image consists of interlaced R,
`G, B samples, existing decorrelation techniques such as DPCM,
`DCT, and wavelets may not work effectively by treating a mo-
`saic image as a grayscale one. In this paper, we examine a
`number of interband coding techniques for lossless coding of
`color mosaic images. Our focus is on reversible lossless spec-
`tral-spatial transforms that can remove statistical redundancies
`in both spectral and spatial domains. Interestingly, we discover
`that a unique wavelet decomposition scheme, called the Mallat
`packet transform, is ideally suited to the task of decorrelating
`color mosaic data.
`The presentation is organized as follows. Section II presents
`and evaluates some schemes of coding mosaic images by de-in-
`terleaving R, G, B samples prior to compression. In Section III,
`we consider an alternative approach of compressing color mo-
`saic images directly without de-interleaving the color bands. We
`study the strength and weakness of both DPCM and wavelet-
`based lossless coding methods in the above two different ap-
`proaches. Section IV offers a wavelet analysis of mosaic images.
`The analysis leads to a new wavelet decomposition scheme that
`is well suited for lossless coding of Bayer pattern mosaic data
`directly without de-interleaving. This new wavelet decomposi-
`tion, which resembles the SPACL mode of JPEG 2000 standard,
`
`1057-7149/$20.00 © 2006 IEEE
`
`APPLE v. RED.COM
`
`Page 1 of 10
`
`Apple Ex. 1007
`
`

`

`1380
`
`IEEE TRANSACTIONS ON IMAGE PROCESSING, VOL. 15, NO. 6, JUNE 2006
`
`has the nice property of decorrelating color samples both spa-
`tially and spectrally. Section V introduces a fast context-based
`Golomb–Rice coding scheme to compress the coefficients of the
`proposed wavelet transform. Section VI presents experimental
`results and Section VII concludes.
`
`II. DEINTERLEAVED COMPRESSION
`
`Since most digital cameras use CCD sensor arrays of Bayer
`pattern, we are concerned with the lossless compression of color
`mosaic images of Bayer pattern, but the techniques to be de-
`veloped in this paper can be generalized to other mosaic color
`sampling schemes. The Bayer color filter array and a resulting
`mosaic image are presented in Fig. 1.
`Let
`be the color sample at pixel position
`the Bayer color mosaic pattern is defined by
`
`, then
`
`is even
`is odd
`is even
`is even
`is odd
`
`(1)
`
`A natural way of compressing color mosaic images is to first
`deinterleave the three color channels, and then code each of the
`three down-sampled color channels individually. Specifically,
`the Bayer pattern
`
`can be de-interleaved into the following three down-sampled
`color channels:
`
`Fig. 1. Bayer pattern and an example of mosaic image: (a) Bayer color
`filter array; (b) an original color image: Monarch; (c) Bayer pattern mosaic
`image of the selected region in (b). (Color version available online at
`http://ieeexplore.ieee.org.)
`
`square sample grid. We need to transform the green quincunx
`array to rectangular array in preparing it for compression. There
`are many ways of transforming or deinterleaving the diamond
`sample grid into a square sample grid. We examine the following
`four.
`1) Merge: The quincunx array is converted to rectangular
`array by shifting all odd columns one pixel to the left and
`form
`
`2) Reversible de-interlacer:
`
`Let us develop a general framework for de-interleaved com-
`pression of mosaic images. First, we code the green channel be-
`fore the other two channels, because the green channel has twice
`as many samples and, hence, higher intrachannel correlation.
`Once the green samples are coded, we utilize the interchannel
`correlation to compress red and blue channels, but one problem
`needs to be addressed. In the Bayer pattern, the green channel
`consists of a diamond grid (or so-called quincunx array), while
`all existing lossless image compression standards operate on
`
`This scheme was proposed for lossy compression of
`Bayer pattern mosaic data [3], [4]. Odd column data are
`
`APPLE v. RED.COM
`
`Page 2 of 10
`
`Apple Ex. 1007
`
`

`

`ZHANG AND WU: LOSSLESS COMPRESSION OF COLOR MOSAIC IMAGES
`
`1381
`
`passed through a vertical low-pass filter before merging
`with even columns, namely
`
`TABLE I
`LOSSLESS BIT RATES OF GREEN CHANNEL UNDER DIFFERENT
`DEINTERLEAVING TRANSFORMS WHILE BEING COMPRESSED
`BY JPEG-LS AND JPEG 2000
`
`(2)
`
`Since
`by one
`increases the dynamic range of
`bit, the above transform becomes inefficient for lossless
`coding. In other words, if the binary representation of
`has
`bits,
`are required to repre-
`sent
`in order to have lossless inverse transform. Al-
`though
`and
`have the same dynamic range in
`(2), an extra bit is needed to resolve the parity of the sum
`for lossless reconstruction.
`3) Separation
`
`4) Rotation
`
`TABLE II
`LOSSLESS BIT RATES OF RED AND BLUE MOSAIC SAMPLES USING JPEG-LS
`
`After one of the above deinterleaving transforms, the green
`channel can be coded using any of the existing lossless image
`codecs, such as JPEG-LS and JPEG 2000 lossless mode. Table I
`lists the bit rates of the lossless image compression standards
`JPEG-LS [5] and JPEG-2000 [6] (lossless mode) on the out-
`puts of three of the above deinterleaving transforms. In Table I,
`for each test image, the number in bold face represents the best
`result among all deinterleaving transforms. There is no single
`winning transform for all the images. Not surprisingly, the sep-
`aration transform performs the worst on average because it dis-
`regards the correlation between the two resulting subimages
`of green samples. The compression results of the merge and
`rotation transforms are very close for a given lossless image
`codec. In our comparison study JPEG-LS achieves better loss-
`less compression than JPEG-2000 on all test images for the
`de-interleaving methods of separation and merge. For the rota-
`tion method, we present only the results of JPEG-LS not those
`of JPEG 2000, because it is relatively easy to modify JPEG-LS
`to code the rotated image but very difficult to do the same with
`JPEG 2000.
`Once the green channel is coded and made known to the de-
`coder, it can be used as an anchor to facilitate the compression
`of red and blue channels by exploiting the spectral correlation.
`To this end, we estimate the missing green values from the ex-
`isting green samples at the pixel positions where either red or
`blue sample is taken. We denote such estimates by
`, where
`the value of
`is odd, to distinguish them from the existing
`green samples
`, where the value of
`is even. Rather
`
`and
`than code
`two color difference images
`
`separately, we losslessly code the
`
`and
`
`(3)
`
`as the
`from
`
`Since the decoder can make the same estimates
`encoder, it can reconstruct the original
`and
`and
`without any loss. The difference images
`, which can be regarded approximately as two chromi-
`and
`nance components, are more compressible than
`or
`because they are typically low-pass signals due to the inter-
`channel correlation. Furthermore, the color difference images
`and
`provide vital information in many color de-
`mosaicing algorithms [1], [7]–[9]. Therefore, lossless coding of
`and
`serves dual purposes of lossless compression
`of color mosaic data and color demosaicking.
`In estimating the missing green samples
`, we have
`evaluated various interpolation schemes,
`including bilinear
`interpolation, bi-cubic B-Spline [9] and some nonlinear methods
`[7], [8]. Table II lists the lossless bit rates of the red and
`blue mosaic samples obtained by three coding schemes: 1)
`intrachannel coding of red and blue; 2) color difference coding
`with bilinear green interpolation; 3) color difference coding
`with bi-cubic B-spline green interpolation. It is clear from
`Table II that coding color differences is more effective than
`coding the red and blue channels individually. The coding
`gain is more than 7.5% on average, which is a significant
`margin by the standard of lossless image coding. The precision
`of green interpolation can improve the lossless compression
`of color mosaic images, but only marginally. Simple bilinear
`interpolation works satisfactorily.
`Table III presents the overall lossless bit rates of JPEG-LS and
`JPEG 2000 lossless mode on the de-interleaved green channel
`(using the merge deinterleaving transform) and the two color
`difference images
`and with
`being estimated by bilinear
`
`APPLE v. RED.COM
`
`Page 3 of 10
`
`Apple Ex. 1007
`
`

`

`1382
`
`IEEE TRANSACTIONS ON IMAGE PROCESSING, VOL. 15, NO. 6, JUNE 2006
`
`TABLE III
`LOSSLESS BIT RATES OF DEINTERLEAVED MOSAIC
`IMAGES BY JPEG-LS AND JPEG 2000
`
`interpolation. For comparison purposes, we also give the re-
`sults of coding red and blue channels directly without interband
`decorrelation.
`
`III. INTERLEAVED COMPRESSION
`
`An alternative approach to lossless compression of color
`mosaic images is to process the mosaic data directly without
`de-interleaving the color channels. In other words, the com-
`pression algorithm pretends that the color mosaic image is
`a single-channel grrayscale image. This treatment has the
`advantage of simpler codec design and lower complexity than
`compression after de-interleaving. The simplest way is to apply
`a lossless image coding algorithm directly to raw color mosaic
`images without any preprocessing. For a quick assessment of
`different compression methods, when applied to mosaic images
`directly, the reader is referred to Table VI of Section VI (not
`placed here to save space) for the lossless bit rates of JPEG-LS
`and JPEG 2000 (using the 5-3 integer filter) standards on some
`common test images.
`Interestingly, and somewhat surprisingly, JPEG-2000 outper-
`forms JPEG-LS by a significant margin (more than 10%), when
`both applied to compress color mosaic images without de-in-
`terleaving. Recall from the proceeding section that the perfor-
`mance comparison between the two algorithms in the case of
`de-interleaved compression gave exactly opposite results. This
`reversal in relative coding efficiency is largely due to a funda-
`mental difference in decorrelation mechanisms of the two al-
`gorithms: DPCM for JPEG-LS and lifting integer wavelet for
`JPEG 2000.
`The DPCM scheme is suited to remove long term memory of
`a smooth signal in the spatial domain. It becomes ineffective on
`decorrelating mosaic images of periodic patterns. The energy of
`a mosaic image can be packed into the spatial-frequency domain
`of the wavelet far more efficiently than in the spatial domain. To
`expose this weakness of DPCM on mosaic images, in Fig. 2 we
`present the prediction residual images of JPEG-LS when being
`applied to a natural image [given in Fig. 6(a)] and its mosaic
`counterpart [given in Fig. 6(b)]. The DPCM residual signal of
`the mosaic image has significantly greater amplitude than that
`of the natural image. Moreover, the DPCM residuals still exhibit
`the original mosaic structure, with their statistics far from being
`i.i.d. In other words, the median predictor used by JPEG-LS fails
`to pack the signal energy and decorrelate the samples.
`
`Fig. 2. Residual images of the median predictor of JPEG-LS (the mid-gray
`represents zero). (a) Residual image of Bayer mosaic image. (b) Residual image
`of the original green channel.
`
`Let us compare in Fig. 3 the histograms of the prediction
`residual images Fig. 2(a) and Fig. 2(b) of JPEG-LS, for the mo-
`saic image and the corresponding normal image, respectively. It
`is well known that the DPCM residuals of a normal image signal
`obey a Laplacian distribution, as being evident in Fig. 3(b),
`but this is no longer true for the DPCM residuals of a mosaic
`image. Note that the distribution of Fig. 3(a) is multimodal and
`asymmetric against the origin. The residuals of JPEG-LS for
`mosaic images deviate drastically from a Laplacian distribution,
`and they cannot even be modeled by a generalized Gaussian
`distribution. Unfortunately, the entropy code (Golomb–Rice
`code) of JPEG-LS assumes a Laplacian distribution of the
`prediction residuals. This severe mismatch between the model
`and the source also explains the poor performance of JPEG-LS
`on mosaic images. The problem will be corrected in the next
`two sections.
`
`IV. WAVELET ANALYSIS OF MOSAIC IMAGES
`
`In a sharp contrast to DPCM, the wavelet, being a tool of
`frequency–time analysis, can compactly characterize periodic
`color mosaic signals, as will be demonstrated by the analysis
`of this section. Based on the analysis, we propose a unique
`
`APPLE v. RED.COM
`
`Page 4 of 10
`
`Apple Ex. 1007
`
`

`

`ZHANG AND WU: LOSSLESS COMPRESSION OF COLOR MOSAIC IMAGES
`
`1383
`
`Fig. 4. The 2  2 periodical sampling pattern of (a) Bayer mosaic data and
`(b) 2-D wavelet transform.
`
`Fig. 3. Histograms of JPEG-LS residuals for mosaic image and the original
`green channel. (a) Histogram of the residual image in Fig. 2(a). (b) Histogram
`of the residual image in Fig. 2(b).
`
`so-called Mallat packet wavelet transform for direct compres-
`sion of mosaic images without de-interleaving. As we will see,
`the proposed wavelet transform simultaneously performs spatial
`and spectral decorrelation of color samples with a great ease and
`at a low cost.
`Let us start by examining an interesting interplay between the
`Bayer pattern and the 2-D integer wavelet transform via sep-
`arable one-dimensional (1-D) lifting. One level of the wavelet
`transform produces four subbands that have clear interpretations
`of the attributes of the Bayer color signal. As shown in Fig. 4,
`a 2-D wavelet transform (after decimation) and the Bayer pat-
`tern both have a 2
`2 periodical sampling pattern. This corre-
`spondence makes 2-D wavelet transforms very efficient to rep-
`resent the Bayer pattern in frequency–space domain. The effect
`of performing a 2-D wavelet transform on a mosaic image is il-
`lustrated by Fig. 5. In this example, the Bayer mosaic data of
`a uniform color image are transformed into four constant sub-
`bands, although the input mosaic image is, itself, a high-fre-
`quency signal.
`We can explain the effect of Fig. 5 analytically using, for ex-
`ample, the 5-3 integer wavelet. Other wavelets, such as 9/7M,
`5/11-C [10], behave similarly. The low- and high-pass filers of
`the 5-3 integer wavelet are
`
`(4)
`
`to the Bayer
`After applying the 2-D low-pass filter
`mosaic image, the
`subband can be interpreted as the lu-
`minance channel of the original full color image. In a window
`of smooth color, where red, green, and blue color components
`are approximately constants (i.e.,
`,
`,
`), the coefficients in the
`subband are
`
`Fig. 5. Efficiency of representing Bayer pattern mosaic image in wavelet
`domain: (a) a uniform color image; (b) Bayer mosaic image; (c) 2-D wavelet
`coefficients. (Color version available online at http://ieeexplore.ieee.org.)
`
`of rational coefficients is
`, and
`,
`This linear combination of
`an approximation of the
`(luminance) component of the NTSC
`YUV color space. Interestingly, it is also exactly the same as the
`luminance component of reversible color transform adopted by
`JPEG 2000 in its lossless mode.
`To understand the physical meanings of the three high sub-
`bands (
`,
`, and
`) of a mosaic image, we use a model
`of mosaic images that was originally developed for the purpose
`of color demosaicking [2]. In this model, a Bayer mosaic image
`[see Fig. 6(b)] is viewed as a sum of two component images
`
`The first component image, as shown in Fig. 6(c), is the full
`resolution green (an approximation of luminance) channel. The
`
`APPLE v. RED.COM
`
`Page 5 of 10
`
`Apple Ex. 1007
`
`

`

`1384
`
`IEEE TRANSACTIONS ON IMAGE PROCESSING, VOL. 15, NO. 6, JUNE 2006
`
`Fig. 6. Mosaic image model and effects of wavelet transform on Bayer mosaic images. (a) An original full-color image. (b) Bayer pattern mosaic image of (a).
`(c) The green channel of (a). (d) The checker board color difference signal of (a). The mid-gray (128) represents value 0. Note that image (b) is the sum of images
`(c) and (d). (e) One-level 2-D wavelet transform of the green channel (c). (f) One-level 2-D wavelet transform of the checker board color difference image (d).
`(Color version available online at http://ieeexplore.ieee.org.)
`
`other component, as shown in Fig. 6(d), is a checker board sam-
`pled color difference (a representation of chrominance) image
`
`for odd
`for even
`
`and
`and
`
`(5)
`
`As we argued in the preceeding section, the two color differ-
`ence images
`and
`are low-pass
`
`signals, because natural images mostly consist of pastoral (un-
`saturated) colors that have high correlation between the green
`and red/blue channels. An integer wavelet transform is approx-
`imately a linear operation, if we ignore the rounding. Applying
`wavelet transform directly to a mosaic image is, thus, equiva-
`lent to separately transforming the full resolution green channel
`[resulting in Fig. 6(e)] and the down sampled color difference
`image [resulting in Fig. 6(f)], and then summing up the results.
`
`APPLE v. RED.COM
`
`Page 6 of 10
`
`Apple Ex. 1007
`
`

`

`ZHANG AND WU: LOSSLESS COMPRESSION OF COLOR MOSAIC IMAGES
`
`1385
`
`signals in the first place, the 5-3 high-pass filter actually (or quite
`response even smoother.
`counter intuitively) makes their
`In other words, the 5-3 high-pass filter has the effect of spec-
`subband of a Bayer
`tral decorrelation. As a result, in the
`mosaic image [see the
`subband of Fig. 6(g)], the details of
`the green channel [see the
`subband of Fig. 6(e)] are super-
`imposed on a highly smoothed color difference signal [see the
`subband of Fig. 6(f)]. If we apply the 5-3 integer wavelet
`transform again to
`band [see Fig. 6(h)] we achieve greater
`energy compaction by further separating the green details from
`the smooth color difference signal.
`Similar analysis can be carried out on
`plying the 2-D 5-3
`high-pass filter
`
`subbands. Ap-
`
`/
`
`to position
`
`yields
`
`(g)
`
`(h)
`
`(8)
`
`(9)
`
`(Continued.) Mosaic image model and effects of wavelet transform on
`Fig. 6.
`Bayer mosaic images. (g) One-level 2-D wavelet transform of the mosaic image
`(b), which is approximately the sum of images (e) and (f). (h) Two-level 2-D
`Mallat packet decomposition of the mosaic image (b).
`
`The net effect is the image in Fig. 6(g), whose characteristic is
`very different from a wavelet transformed grayscale image.
`Now, let us analyze the outcome of such an operation. Ap-
`plying the 2-D 5-3
`high-pass filter
`
`to, say, position
`
`, we have
`
`(6)
`
`(7)
`
`subband can be viewed as a composition of a
`The resulting
`luminance component and a chrominance component. The first
`component is the detail signal of the usual
`subband of the
`green channel (luminance). The second component is low-pass
`filtered chrominance signal, in which the color difference image
`is averaged vertically and
`averaged hor-
`izontally. Since color difference images
`are low-passed
`
`and
`
`subband also consists of
`subband, the
`Like the
`luminance and chrominance components. The luminance
`component is the detail signal of the usual
`subband of
`the green channel. The chrominance component is somewhat
`intricate, having two subcomponents:
`the smoothed color
`difference signal
`(the average of a four neighbor
`window), and a horizontally filtered signal
`by
`filter
`. In terms of contributions
`to the energy of the
`subband, the luminance component
`dominates since there is a significant amount of attenuation to
`the chrominance component.
`The signal composition of the
`subband is analogous to
`that of the
`subband. It contains detail signal of the usual
`subband of the green channel, plus a smoothed
`signal in
`a 2-D window and a vertically filtered
`signal using
`.
`The analysis above reveals that all four subbands
`,
`,
`, and
`contain low-frequency components of either
`chrominance or luminance signals, as being evident in Fig. 6(g).
`The next natural step is to decompose these four subbands fur-
`ther to better pack the signal energy. The resulting sixteen
`subbands are shown in Fig. 6(h). The
`subband contains
`down sampled luminance information, while the energy of the
`chrominance signals is packed into the
`,
`, and
`subbands. The other twelve subbands, representing the much of
`image details in both luminance and chrominance, now become
`discontinuous signals of low amplitude very much like the
`
`APPLE v. RED.COM
`
`Page 7 of 10
`
`Apple Ex. 1007
`
`

`

`1386
`
`IEEE TRANSACTIONS ON IMAGE PROCESSING, VOL. 15, NO. 6, JUNE 2006
`
`TABLE IV
`SELF-ENTROPY OF WAVELET COEFFICIENTS OF THE FIVE-LEVEL
`MALLAT PACKET DECOMPOSITION FOR DIFFERENT
`WAVELET FILTERS ON MOSAIC IMAGES
`
`packet
`of Mallat
`(a) Five-level
`7. Wavelet Decompositions.
`Fig.
`decomposition. (b) The decomposition closest to (a) that is realizable by JPEG
`2000 decomposition options.
`
`high-frequency wavelet subbands of normal continuous-tone
`images. Therefore, they should not be decomposed any further.
`Based on these observations, we introduce, for the purpose of
`maximum energy packing of mosaic images, a so-called Mallat
`packet decomposition as depicted in Fig. 7(a). It consists of a
`packet of four Mallat decompositions in
`,
`,
`, and
`subbands, respectively.
`We have also experimented with many other reversible in-
`teger wavelet filters in the Mallat packet for lossless compres-
`sion of color mosaic images. In particular, we compare the en-
`ergy packing capabilities of the popular 5/3, 9/7M, 5/11-C [10]
`and the simplest Haar filters on mosaic images. To evaluate these
`integer filters we tabulate in Table IV the self-entropies achieved
`by them after the five-level Mallat packet decomposition. These
`entropy results show that all integer wavelets, with exception of
`Haar wavelet that is about 4% worse, perform virtually the same.
`Furthermore, we investigated the combination of different filters
`at different decomposition levels of Mallat packet. In column
`six of Table IV the results are obtained by applying 9/7M filter
`in first level decomposition [Fig. 6(g)] and followed by the 5/3
`filter in the other four levels [Fig. 7(a)]. Column seven lists the
`results for the combination of the 5/11C filter in first level and
`the 5/3 filter in other levels.
`As for continuous-tone images, the wavelet transform does
`not generate i.i.d. coefficients on mosaic images. Higher lossless
`compression of mosaic images can be achieved by context mod-
`eling and adaptive arithmetic coding. We code the coefficients
`of Mallat packet transform using the high-order context-based
`entropy coding technique ECECOW [11]. The lossless bit rates
`of different integer wavelets when coded by ECECOW are listed
`in Table V.
`
`V. FAST CONTEXT-BASED COEFFICIENT CODING
`
`Given the capability of integer wavelets in packing energy of
`mosaic images one can certainly use JPEG 2000 standard di-
`rectly for lossless coding of mosaic images, using the options
`of 5-3 integer wavelet and the SPACL decomposition [two-level
`SPACL is equivalent to wavelet packet in Fig. 6(h)]. However,
`JPEG 2000 is not the best solution for this application in terms
`of either compression performance or low complexity. It has
`two disadvantages. First, JPEG 2000 does not support Mallat
`packet [Fig. 7(a)] as we proposed in the proceeding section.
`The closet decomposition that can be realized by JPEG 2000
`
`TABLE V
`LOSSLESS BIT RATES OF MOSAIC IMAGES BY ECECOW
`FOR DIFFERENT INTEGER WAVELET TRANSFORMS
`
`VM8.0 is the one shown in Fig. 7(b), which is obtained by rather
`tedious decomposition option setting “-Fdecomp 31 -Fgen_de-
`comp 11 100 011 000 110 001.”
`Second, and more importantly, the entropy coding module of
`JPEG 2000 is not suitable for Mallat packet. The three subbands
`shaded in Fig. 7(b) of Bayer pattern mosaic images tend to be
`smooth, not like the
`,
`, and
`subbands of full-res-
`olution continuous-tone images. This property makes the con-
`text model of EBCOT [12] for high-frequency subbands ineffec-
`tive. Furthermore, the entropy coding technique of JPEG 2000
`is computationally expensive.
`Aiming for on-camera real-time lossless encoding of mosaic
`images at lower computational complexity, we propose a much
`simpler and hardware-oriented entropy coding solution. Our de-
`sign goal is to meet the requirements of low cost, longer bat-
`tery life (requiring low-power consumption) and short shutter
`lag (requiring high-codec throughput), which are highly desir-
`able features of digital cameras.
`First, consider entropy coding of the twelve high-frequency
`subbands generated by the 2-D two-level Mallat packet trans-
`form. Since the lifting scheme of the integer wavelet essentially
`performs linear prediction operations on pixels [13], the wavelet
`coefficients in the high-frequency subbands can be viewed as
`prediction residuals. It is well known in signal compression
`that
`the distribution of prediction errors is approximately
`Laplacian. This fact and our above-mentioned design objective
`make Golomb code a natural choice for the entropy coding
`of high-frequency subbands. The Golomb code is a low-com-
`plexity adaptive entropy coding technique and is yet optimal
`for geometrical distribution [14].
`The Golomb code operates on random variables of positive
`integer values. A positive integer
`is coded in two parts: The
`quotient
`and the remainder
`, where
`is
`the so-called Golomb parameter which is itself also a positive
`
`APPLE v. RED.COM
`
`Page 8 of 10
`
`Apple Ex. 1007
`
`

`

`ZHANG AND WU: LOSSLESS COMPRESSION OF COLOR MOSAIC IMAGES
`
`1387
`
`is the concatenation of the unary
`integer. The code stream of
`code of
`and the binary code of
`. Obviously, the Golomb pa-
`rameter
`determines the code length of
`. The Golomb code
`affords a very simple implementation if its parameter is an in-
`teger power of two,
`,
`. In this case, the code of
`has a quotient part that is generated by simply right-shifting
`by bits, and the remainder is just the
`least significant bits of
`. This special form of Golomb code is also known as the Rice
`code.
`Next, we develop a simple context-based Rice coding scheme
`to compress integer wavelet coefficients. Coefficients in each
`subband are coded in raster scan order from left to right and
`top to bottom. A wavelet coefficient
`is split into its sign and
`magnitude
`. The sign of
`is kept uncoded and
`is rep-
`resented in Rice code. The key to the performance of Rice code
`. The flexibility of changing the
`is the choice of the parameter
`value of
`per source symbol on the fly makes Rice code adap-
`tive to the changing statistics of the input signal. Specifically
`for lossless wavelet compression of mosaic images, the wavelet
`coefficients are not i.i.d. because wavelet transform clusters co-
`efficients in the spatial domain by magnitudes. It can be readily
`observed from Fig. 6(h) that large wavelet coefficients tend to
`occur in vicinity of edges, and conversely small coefficients
`form large contiguous blocks. To exploit this memory structure
`of the source, we associate the current wavelet coefficient
`,
`which is the random variable to be coded, with the
`-shaped
`neighborhood or context of
`:
`
`is
`and
`is a scalar quantizer of random variable
`where
`the maximum number of Rice parameters to be used. The de-
`sign of the optimal context quantizer
`can be done via dy-
`namic programming [15]. Although it is possible to compute
`the image-dependent optimal context quantizer
`to minimize
`the Rice code length for an input image, this approach is clearly
`impractical for most digital camera applications. However, one
`can compute
`in an offline design process using a training set
`that provides sample statistics of the joint distribution of
`.
`The training set(s) should be chosen for given integer wavelet
`transform, given CCD sensor, and may also be with respect to
`different types of scenes, but we found empirically that the fol-
`lowing simple partition of
`
`(13)
`
`works well on 8-bit mosaic images (within less than 2% from
`the minimum Rice code length achieved by
`computed by dy-
`namic programming).
`For the four smooth subbands:
`, a
`, and
`,
`,
`simple DPCM coding is employed first. For current coefficient
`at position
`, a linear prediction is performed as
`
`After prediction, the prediction residual
`as those coefficients in high subbands. The
`signed integer into no-negative integer
`by
`
`is treated the same
`is mapped from
`
`(14)
`
`and we define the energy of the neighborhood by
`
`A simple context for current value
`
`is formed as
`
`(10)
`
`(15)
`
`(16)
`
`Denote by
`and
`t