throbber
UNITED STATES PATENT AND TRADEMARK OFFICE
`____________________
`
`BEFORE THE PATENT TRIAL AND APPEAL BOARD
`_____________________
`
`LG Electronics, Inc.
`Petitioner,
`
`v.
`FastVDO LLC
`Patent Owner.
`
`
`
`Patent No. 5,850,482
`________________________
`
`Inter Parte Review No. ____________
`
`___________________________________________________________
`
`Wallace, “The JPEG Still Picture Compression Standard,” IEEE
`Transactions on Consumer Electronics, Vol. 38, No. 1, Feb. 1992
`
`Exhibit 1007
`
`
`
`

`
`xviii
`
`IEEE Transactions on Consumer Electronics, Vol. 38, No. 1, FEBRUARY 1992
`
`THE JPEG STILL PICTURE COMPRESSION STANDARD
`Gregory K. Wallace
`Multimedia Engineering
`Digital Equipment Corporation
`May nard, Massachusetts
`
`This paper is a revised version of an article by the same
`title and author which appeared in the April I991 issue
`of Communications of the ACM.
`
`Abstract
`For the past few years, a joint ISO/CCITT committee
`known as JPEG (Joint Photographic Experts Group)
`has been working to establish the first international
`compression standard for continuous-tone still images,
`both grayscale and color. JPEG’s proposed standard
`aims to be generic, to support a wide variety of
`applications for continuous-tone images. To meet the
`differing needs of many applications, the JPEG
`standard includes two basic compression methods, each
`with various modes of operation. A DCT-based method
`is specified for “lossy” compression, and a predictive
`method for “lossless” compression. JPEG features a
`simple lossy technique known as the Baseline method,
`a subset of the other DCT-based modes of operation.
`The Baseline method has been by far the most widely
`implemented JPEG method to date, and is sufficient in
`its own right for a large number of applications. This
`article provides an overview of the JPEG standard, and
`focuses in detail on the Baseline method.
`
`1 Introduction
`Advances over the past decade in many aspects of
`digital technology - especially devices for image
`acquisition, data storage, and bitmapped ptlnting and
`display - have brought about many applications of
`digital imaging. However, these applications tend to be
`specialized due to their relatively high cost. With the
`possible exception of facsimile, digital images are not
`commonplace in general-purpose computing systems
`the way text and geomemc graphics are. The majority
`of modem business and consumer usage of photographs
`and other types of images takes place through more
`traditional analog means.
`The key obstacle for many applications is the vast
`amount of data required to represent a digital image
`
`directly. A digitized version of a single, color picture
`at TV resolution contains on the order of one million
`bytes; 35”
`resolution requires ten times that amount.
`Use of digital images often is not viable due to high
`storage or transmission costs, even when image capture
`and display devices are quite affordable.
`
`technology offers a
`image compression
`Modem
`possible solution.
`State-of-the-art techniques can
`compress typical images from 1/10 to 1/50 their
`uncompressed size without visibly affecting image
`quality. But compression technology alone is not
`sufficient. For digital image applications involving
`storage or transmission to become widespread in
`today’s marketplace, a standard image compression
`method
`is needed
`to enable
`interoperability of
`equipment from different manufacturers. The CCITT
`recommendation for today’s ubiquitous Group 3 fax
`machines E171 is a dramatic example of how a standard
`compression method can enable an important image
`application. The Group 3 method, however, deals with
`bilevel images only and does not address photographic
`image compression.
`
`For the past few years, a standardization effort known
`by the acronym JPEG, for Joint Photographic Experts
`Group, has been working toward establishing the first
`international digital image compression standard for
`continuous-tone
`(multilevel)
`still
`images, both
`grayscale and color. The “joint” in JPEG refers to a
`collaboration between CCITT and ISO.
`JPEG
`convenes officially as the IS0 committee designated
`JTCl/SC2/WGlO, but operates in close informal
`collaboration with CCIlT SGVIII. JPEG will be both
`an IS0 Standard and a CCITT Recommendation. The
`text of both will be identical.
`
`Photovideotex, desktop publishing, graphic arts, color
`facsimile, newspaper Wirephoto transmission, medical
`imaging, and many other continuous-tone image
`applications require a compression standard in order to
`develop significantly beyond their present state. JPEG
`has undertaken the ambitious task of developing a
`
`Presented at 3rd Annual Digital Video Workshop
`Revised manuscript received December 6, 1991
`
`0098 3063/92 $03.00 CJ 1992 IEEE
`
`-
`
`I~
`
`1
`
`1
`
`
`
`_ _ _ _ _ ~ -
`
`~
`
`~
`
`Apple Inc. Exhibit 1007 Page 1
`
`

`
`Wallace: The JPEG Still Picture Compression Standard
`
`xix
`
`general-purpose compression standard to meet the
`needs of almost all continuous-tone still-image
`applications.
`
`If this goal proves attainable, not only will individual
`applications flourish, but exchange of images across
`application boundaries will be facilitated. This latter
`feature will become increasingly important as more
`image applications are implemented on general-purpose
`computing systems, which are themselves becoming
`increasingly interoperable and intemetworked. For
`applications which require specialized VLSI to meet
`their
`compression
`and
`decompression
`speed
`requirements, a common method will provide
`economies of scale not possible within a single
`application.
`
`This article gives an overview of JPEG’s proposed
`image-compression standard. Readers without prior
`knowledge of JPEG or compression based on the
`Discrete Cosine Transform (DCT) are encouraged to
`study first the detailed description of the Baseline
`sequential codec, which is the basis for all of the
`DCT-based decoders. While this article provides many
`details, many more are necessarily omitted. The reader
`should refer to the IS0 draft standard [2] before
`attempting implementation.
`
`Some of the earliest industry attention to the JPEG
`proposal has been focused on the Baseline sequential
`codec as a motion image compression method - of the
`“intraframe” class, where each frame is encoded as a
`separate image. This class of motion image coding,
`while providing less compression than “interframe”
`methods like MPEG, has greater flexibility for video
`editing. While this paper focuses only on JPEG as a
`still picture standard (as IS0 intended), it is interesting
`to note that JPEG is likely to become a “de facto”
`intraframe motion standard as well.
`
`2 Background: Requirements and Selec-
`tion Process
`JPEG’s goal has been to develop a method for
`continuous-tome image compression which meets the
`following requirements:
`
`1) be at or near the state of the art with regard to
`compression
`rate and accompanying
`image
`fidelity, over a wide range of image quality ratings,
`and especially in the range where visual fidelity to
`the original is characterized as “very good” to
`“excellent”: also,
`the encoder
`should be
`parameterizable, so that the application (or user)
`can set the desired compression/quality tradeoff;
`
`be applicable
`to practically any kind of
`continuous-tone digital source image (i.e. for most
`practical purposes not be restricted to images of
`certain dimensions, color spaces, pixel aspect
`ratios, etc.) and not be limited to classes of imagery
`with restrictions on scene content, such as
`range of colors, or
`statistical
`complexity,
`properties:
`
`3) have tractable computational complexity, to make
`feasible software implementations with viable
`performance on a range of CPU’s, as well as
`hardware implementations with viable cost for
`applications requiring high performance;
`
`4)
`
`have the following modes of operation:
`
`Sequential encoding: each image component is
`encoded in a single left-to-right, top-to-bottom
`scan;
`
`Progressive encoding: the image is encoded in
`multiple scans for applications in which
`transmission time is long, and the viewer
`prefers to watch the image build up in multiple
`coarse-to-clear passes;
`
`Lossless encoding: the image is encoded to
`guarantee exact recovery of every source
`image sample value (even though the result is
`low compression compared to the
`lossy
`modes):
`
`Hierarchical encoding: the image is encoded at
`multiple resolutions so that lower-resolution
`versions may be accessed without first having
`to decompress the image at its full resolution.
`
`In June 1987, JPEG conducted a selection process
`based on a blind assessment of subjective picture
`quality, and narrowed 12 proposed methods to three.
`Three informal working groups formed to refine them,
`and in January 1988, a second, more rigorous selection
`process [19] revealed that the “ADCT” proposal [ll],
`based on the 8x8 DCT, had produced the best picture
`quality.
`
`At the time of its selection, the DCT-based method was
`only partially defined for some of the modes of
`operation. From 1988 through 1990, JPEG undertook
`the sizable task of defining, documenting, simulating,
`testing, validating, and simply agreeing on the plethora
`of details necessary for genuine interoperability and
`universality. Further history of the JPEG effort is
`contained in [6,7,9, 183.
`
`Apple Inc. Exhibit 1007 Page 2
`
`

`
`xx
`
`IEEE Transactions on Consumer Electronics, Vol. 38, No. 1, FEBRUARY 1992
`
`3 Architecture of the Proposed Standard
`The proposed standard contains the four “modes of
`operation” identified previously. For each mode, one
`or more distinct codecs are specified. Codecs within a
`mode differ according to the precision of source image
`samples they can handle or the entropy coding method
`they use. Although the word codec (encoder/decoder)
`is used frequently in this article, there is no requirement
`that implementations must include both an encoder and
`a decoder. Many applications will have systems or
`devices which require only one or the other.
`
`The four modes of operation and their various codecs
`have resulted from JPEG’s goal of being generic and
`from the diversity of image formats across applications.
`The multiple pieces can give the impression of
`undesirable complexity, but they should actually be
`regarded as a comprehensive “toolkit” which can span a
`wide range of continuous-tone image applications. It is
`unlikely that many implementations will utilize every
`tool -- indeed, most of the early implementations now
`on the market (even before final IS0 approval) have
`implemented only the Baseline sequential codec.
`
`The Baseline sequential codec is inherently a rich and
`sophisticated compression method which will be
`sufficient for many applications. Getting this minimum
`JPEG
`capability
`implemented
`properly
`and
`interoperably will provide
`the
`industry with an
`important initial capability for exchange of images
`across vendors and applications.
`
`4 Processing Steps for DCT-Based Coding
`Figures 1 and 2 show the key processing steps which
`are the heart of the DCT-based modes of operation.
`These
`figures
`illustrate
`the
`special case of
`single-component (gray scale) image compression. The
`reader can grasp
`the essentials of DCT-based
`compression by
`thinking of
`it as essentially
`compression of a stream of 8x8 blocks of grayscale
`image samples. Color image compression can then be
`approximately regarded as compression of multiple
`grayscale images, which are either compressed entirely
`one at a time, or are compressed by alternately
`interleaving 8x8 sample blocks from each in turn.
`
`For DCT sequential-mode codecs, which include the
`Baseline sequential codec, the simplified diagrams
`indicate how single-component compression works in a
`fairly complete way. Each 8x8 block is input, makes
`its way through each processing step, and yields output
`in compressed form into the data stream. For DCT
`progressive-mode codecs, an image buffer exists prior
`to the entropy coding step, so that an image can be
`stored and then parceled out in multiple scans with suc-
`cessively improving quality. For the hierarchical mode
`
`of operation, the steps shown are used as building
`blocks within a larger framework.
`
`4.1 8x8 FDCT and IDCT
`At the input to the encoder, source image samples are
`grouped into 8x8 blocks, shifted from unsigned integers
`with ran e [0, 2’
`- 11 to signed integers with range
`[-2‘-’, 2$-l-1], and input to the Forward DCT (FDCT).
`At the output from the decoder, the Inverse DCT
`(IDCT) outputs 8x8 sample blocks to form the
`reconstructed image. The following equations are the
`idealized mathematical definitions of the 8x8 FDCT
`and 8x8 IDCT:
`
`7
`
`7
`
`
`
`F O y=o
`
`C(U), C(v) = 1 otherwise.
`
`The DCT is related to the Discrete Fourier Transform
`(DFT).
`Some simple
`intuition for DCT-based
`compression can be obtained by viewing the FDCT as a
`harmonic analyzer and the IDCT as a harmonic
`synthesizer. Each 8x8 block of source image samples
`is effectively a 64-point discrete signal which is a
`function of the two spatial dimensions x and y. The
`FDCT takes such a signal as its input and decomposes
`it into 64 orthogonal basis signals. Each contains one
`the 64 unique two-dimensional (2D) “spatial
`of
`frequencies” which comprise the
`input signal’s
`“spectrum.” The ouput of the FDCT is the set of 64
`basis-signal amplitudes or “DCT coefficients” whose
`values are uniquely determined by
`the particular
`@-point input signal.
`
`The DCT coefficient values can thus be regarded as the
`relative amount of the 2D spatial frequencies contained
`in the @-point input signal. The coefficient with zero
`frequency in both dimensions is called the “DC
`coefficient” and the remaining 63 coefficients are
`called the “AC coefficients.” Because sample values
`
`Apple Inc. Exhibit 1007 Page 3
`
`

`
`Wallace: The JPEG Still Picture Compression Standard
`
`DCT-Based Encoder
`8x8 blocks
`/
`- I W
`/
`9 + FDCT -jr Quantizer j Entropy
`Encoder
`
`1
`
`Source
`Image Data
`
`Specifications
`
`Specifications
`
`Compressed
`ImageData
`
`Figure 1. DCT-Based Encoder Processing Steps
`
`Compressed
`Image Data
`
`Specifications
`
`Reconstructed
`Image Data
`
`Figure 2. DCT-Based Decoder Processing Steps
`
`typically vary slowly from point to point across an
`image, the FDCT processing step lays the foundation
`for achieving data compression by concentrating most
`of the signal in the lower spatial frequencies. For a
`typical 8x8 sample block from a typical source image,
`most of the spatial frequencies have zero or near-zero
`amplitude and need not be encoded.
`
`At the decoder the IDCT reverses this processing step.
`It takes the 64 DCT coefficients (which at that point
`have been quantized) and reconstructs a @-point ouput
`image signal by
`summing
`the basis
`signals.
`Mathematically, the DCT is one-to-one mapping for
`64-point vectors between the image and the frequency
`domains. If the FDCT and IDCT could be computed
`with perfect accuracy and if the DCT coefficients were
`not quantized as in the following description, the
`original @-point signal could be exactly recovered. In
`principle, the DCT introduces no loss to the source
`image samples; it merely transforms them to a domain
`in which they can be more efficiently encoded.
`
`Some properties of practical FDCT and IDCT
`implementations raise the issue of what precisely
`should be required by
`the JPEG standard. A
`fundamental property is that the FDCT and IDCT
`equations
`contain
`transcendental
`functions.
`Consequently, no physical
`implementation can
`compute them with perfect accuracy. Because of the
`DCT’s application importance and its relationship to
`the D R , many different algorithms by which the
`
`FDCT and IDCT may be approximately computed have
`Indeed, research in fast DCT
`been devised [16].
`algorithms is ongoing and no single algorithm is
`optimal for all implementations. What is optimal in
`software for a general-purpose CPU is unlikely to be
`optimal in firmware for a programmable DSP and is
`certain to be suboptimal for dedicated VLSI.
`
`Even in light of the finite precision of the DCT inputs
`and outputs, independently designed implementations
`of the very same FDCT or IDCT algorithm which differ
`even minutely in the precision by which they represent
`cosine terms or intermediate results, or in the way they
`sum and round fractional values, will eventually
`produce slightly different outputs from identical inputs.
`
`To preserve freedom for innovation and customization
`within implementations, JPEG has chosen to specify
`neither a unique FDCT algorithm or a unique IDCT
`algorithm in its proposed standard. This makes
`compliance somewhat more difficult to confirm,
`because
`two compliant encoders
`(or decoders)
`generally will not produce identical outputs given
`identical inputs. The JPEG standard will address this
`issue by specifying an accuracy test as part of its
`compliance tests for all DCT-based encoders and
`decoders; this is to ensure against crudely inaccurate
`cosine basis functions which would degrade image
`quality.
`
`Apple Inc. Exhibit 1007 Page 4
`
`

`
`-
`
`, .
`
`xxii
`
`IEEE Transactions on Consumer Electronics, Vol. 38, No. 1, FEBRUARY 1992
`
`For each DCT-based mode of operation, the JPEG
`proposal specifies separate codecs for images with 8-bit
`and 12-bit (per component) source image samples. The
`12-bit codecs, needed to accommodate certain types of
`medical
`and
`other
`images,
`require
`greater
`computational resources to achieve the required FDCT
`or IDCT accuracy.
`Images with other sample
`precisions can usually be accommodated by either an
`8-bit or 12-bit codec, but this must be done outside the
`JPEG standard.
`For example, it would be the
`responsibility of an application to decide how to fit or
`pad a 6-bit sample into the 8-bit encoder’s input
`interface, how to unpack it at the decoder’s output, and
`how to encode any necessary related information.
`
`4.2 Quantization
`After output from the FDCT, each of the 64 DCT
`coefficients is uniformly quantized in conjunction with
`a 64-element Quantization Table, which must be
`specified by the application (or user) as an input to the
`encoder. Each element can be any integer value from 1
`to 255, which specifies the step size of the quantizer for
`its corresponding DCT coefficient. The purpose of
`quantization is to achieve further compression by
`representing DCT coefficients with no greater precision
`than is necessary to achieve the desired image quality.
`Stated another way, the goal of this processing step is
`to discard information which is not visually significant.
`Quantization is a many-to-one mapping, and therefore
`is fundamentally lossy. It is the principal source of
`lossiness in DCT-based encoders.
`Quantization is defined as division of each DCT
`coefficient by its corresponding quantizer step size,
`followed by rounding to the nearest integer:
`
`#(U,
`
`F(u v)
`v ) = Integer Round (-)
`Q ( u 4
`
`(3)
`
`This output value is normalized by the quantizer step
`size. Dequantization is the inverse function, which in
`this case means simply that the normalization is
`removed by multiplying by the step size, which returns
`the result to a representation appropriate for input to the
`IDCT:
`
`When the aim is to compress the image as much as
`possible without visible artifacts, each step size. ideally
`should be chosen as the perceptual threshold or ‘‘just
`noticeable difference” for the visual contribution of its
`corresponding cosine basis function. These thresholds
`are also functions of the source image characteristics,
`display characteristics and viewing distance. For
`applications in which these variables can be reasonably
`well defined, psychovisual experiments can be
`performed to determine the best thresholds. The
`experiment described in [12] has led to a set of
`Quantization Tables for CCIR-601 [4] images and
`displays. These have been used experimentally by
`JPEG members and will appear in the IS0 standard as a
`matter of information, but not as a requirement.
`
`4.3 DC Coding and Zig-Zag Sequence
`After quantization, the DC coefficient is treated
`separately from the 63 AC coefficients. The DC
`coefficient is a measure of the average value of the 64
`image samples. Because there is usually strong
`correlation between the DC coefficients of adjacent 8x8
`blocks, the quantized DC coefficient is encoded as the
`difference from the DC term of the previous block in
`the encoding order (defined in the following), as shown
`in Figure 3. This special treatment is worthwhile, as
`DC coefficients frequently contain a significant fraction
`of the total image energy.
`
`Ac07
`
`...
`
`Differential DC encoding
`
`Zig-zag sequence
`
`ACII
`
`Figure 3. Preparation of Quantized Coefficients for Entropy Coding
`
`Apple Inc. Exhibit 1007 Page 5
`
`

`
`Wallace: The JPEG Still Picture Compression Standard
`
`xxiii
`
`Finally, all of the quantized coefficients are ordered
`into the “zig-zag” sequence, also shown in Figure 3.
`This ordering helps to facilitate entropy coding by
`placing low-frequency coefficients (which are more
`likely
`to be nonzero) before high-frequency
`coefficients.
`
`4.4 Entropy Coding
`The final DCT-based encoder processing step is
`entropy coding.
`This step achieves additional
`compression losslessly by encoding the quantized DCT
`coefficients more compactly based on their statistical
`characteristics. The JPEG proposal specifies two
`entropy coding methods - Huffman coding [8] and
`arithmetic coding 1151. The Baseline sequential codec
`uses Huffman coding, but codecs with both methods
`are specified for all modes of operation.
`
`It is useful to consider entropy coding as a 2-step
`process. The first step converts the zig-zag sequence of
`quantized coefficients into an intermediate sequence of
`symbols. The second step converts the symbols to a
`data stream in which the symbols no longer have
`externally identifiable boundaries. The form and
`definition of the intermediate symbols is dependent on
`both the DCT-based mode of operation and the entropy
`coding method.
`
`Huffman coding requires that one or more sets of
`Huffman code tables be specified by the application.
`The same tables used to compress an image are needed
`to decompress it. Huffman tables may be predefined
`and used within an application as defaults, or computed
`specifically for a given
`image
`initial
`in an
`statistics-gathering pass prior to compression. Such
`choices are the business of the applications which use
`JPEG; the JPEG proposal specifies no required
`Huffman tables. Huffman coding for the Baseline
`sequential encoder is described in detail in section 7.
`
`By contrast, the particular arithmetic coding method
`specified in the JPEG proposal [2] requires no tables to
`be externally input, because it is able to adapt to the
`image statistics as it encodes the image. (If desired,
`statistical conditioning tables can be used as inputs for
`slightly better efficiency, but this is not required.)
`Arithmetic coding has produced 5-10% better
`compression than Huffman for many of the images
`which JPEG members have tested. However, some feel
`it is more complex than Huffman coding for certain
`implementations, for example,
`the highest-speed
`hardware
`implementations.
`(Throughout JPEG’s
`history, “complexity” has proved to be most elusive as
`a practical memc for comparing compression methods.)
`
`If the only difference between two JPEG codecs is the
`entropy coding method, transcoding between the two is
`
`possible by simply entropy decoding with one method
`and entropy recoding with the other.
`
`4.5 Compression and Picture Quality
`For color images with moderately complex scenes, all
`DCT-based modes of operation typically produce the
`following levels of picture quality for the indicated
`ranges of compression. These levels are only a
`- quality and compression can vary
`guideline
`significantly according to source image characteristics
`and scene content. (The units “bits/pixel” here mean
`the total number of bits in the compressed image -
`including the chrominance components - divided by the
`number of samples in the luminance component.)
`
`0.25-0.5 bitdpixel: moderate to good quality,
`sufficient for some applications;
`
`0.5-0.75 bitdpixel: good to very good quality,
`sufficient for many applications:
`
`0.75- 1/5 bits/pixel: excellent quality, sufficient for
`most applications;
`
`0
`
`1.5-2.0 bits/pixel: usually indistinguishable from
`the original, sufficient for the most demanding
`applications.
`
`5 Processing Steps for Predictive Lossless
`Coding
`After its selection of a DCT-based method in 1988,
`JPEG discovered that a DCT-based lossless mode was
`difficult to define as a practical standard against which
`encoders and decoders could be
`independently
`implemented, without placing severe constraints on
`both encoder and decoder implementations.
`
`JPEG, to meet its requirement for a lossless mode of
`operation, has chosen a simple predictive method
`which is wholly independent of the DCT processing
`described previously. Selection of this method was not
`the result of rigorous competitive evaluation as was the
`DCT-based method. Nevertheless, the JPEG lossless
`method produces results which,
`in
`light of
`its
`simplicity, are surpisingly close to the state of the art
`for lossless continuous-tone compression, as indicated
`by a recent technical report [5].
`
`Figure 4 shows the main processing steps for a
`single-component image. A predictor combines the
`values of up to three neighboring samples (A, B, and C )
`to form a prediction of the sample indicated by X in
`Figure 5. This prediction is then subtracted from the
`actual value of sample X, and the difference is encoded
`
`Apple Inc. Exhibit 1007 Page 6
`
`

`
`. -
`
`xxiv
`
`IEEE Transactions on Consumer Electronics, Vol. 38, No. 1, FEBRUARY 1992
`
`Lossless Encoder
`
`Source
`Image Data
`
`p & l
`
`Specifications
`
`Compressed
`Image Data
`
`Figure 4. Lossless Mode Encoder Processing Steps
`
`losslessly by either of the entropy c d n g methods -
`Huffman or arithmetic. Any one of the eight predictors
`listed in Table 1 (under “selection-value”) can be used.
`
`Selections 1, 2, and 3 are one-dimensional predictors
`and selections 4, 5, 6 and 7 are two-dimensional
`predictors. Selection-value 0 can only be used for
`differential coding in
`the hierarchical mode of
`operation. The entropy coding is nearly identical to
`that used for the DC coefficient as described in section
`7.1 (for Huffman coding).
`
`t
`
`.
`
`.
`
` m
`
`I
`
`
`B
`C
`A X
`
`Figure 5. 3-Sample Prediction Neighborhood
`
`For the lossless mode of operation, two different codecs
`are specified - one for each entropy coding method.
`The encoders can use any source image precision from
`2 to 16 bits/sample, and can use any of the predictors
`except selection-value 0. The decoders must handle
`any of the sample precisions and any of the predictors.
`Lossless codecs
`typically produce around 2: 1
`compression for color images with moderately complex
`scenes.
`
`selection-
`value
`0
`1
`2
`3
`4
`5
`6
`7
`
`prediction
`no prediction
`A
`B
`C
`A+B-C
`A+(@ -C)/2)
`B+( (A-C)/2)
`(A+B)12
`
`Table 1. Predictors for Lossless Coding
`
`6 Multiple-Component Images
`The previous sections discussed the key processing
`steps of the DCT-based and predictive lossless codecs
`for the case of single-component source images. These
`steps accomplish the image data compression. But a
`good deal of the JPEG proposal is also concerned with
`the handling and control of color (or other) images with
`multiple components.
`JPEG’s aim for a generic
`compression
`standard
`requires
`its proposal
`to
`accommodate a variety of source image formats.
`
`6.1 Source Image Formats
`The source image model used in the JPEG proposal is
`an abstraction from a variety of image types and
`applications and consists of only what is necessary to
`compress and reconstruct digital image data. The
`reader should recognize that the JPEG compressed data
`format does not encode enough information to serve as
`a complete image representation. For example, JPEG
`does not specify or encode any information on pixel
`aspect ratio, color space, or
`image acquisition
`characteristics.
`
`Apple Inc. Exhibit 1007 Page 7
`
`

`
`Wallace: The JPEG Still Picture Compression Standard
`
`XXV
`
`Ci
`
`top
`
`. I
`
`1
`
`‘Nf
`. ‘Nf- 1
`
`(a) Source image with multiple components
`
`bottom
`(b) Characteristics of an image component
`
`Figure 6. JPEG Source Image Model
`
`Figure 6 illustrates the JPEG source image model. A
`to 255
`source
`image
`image contains from 1
`components, sometimes called color or spectral bands
`or channels. Each component consists of a rectangular
`array of samples. A sample is defined to be an
`unsigned integer with precision P bits, with any value
`in the range [0, 2‘-1]. All samples of all components
`within the same source image must have the same
`precision P. P can be 8 or 12 for DCT-based codecs,
`and 2 to 16 for predictive codecs.
`
`The ith component has sample dimensions xi by yi. To
`accommodate
`formats
`in which
`some
`image
`components are sampled at different rates than others,
`components can have different dimensions. The
`dimensions must have a mutual integral relationship
`defined by Hi and Vi, the relative horizontal and
`vertical sampling factors, which must be specified for
`each component. Overall image dimensions X and Y
`are defined as the maximum xi and yi for all
`components in the image, and can be any number up to
`216. H and V are allowed only the integer values 1
`through 4. The encoded parameters are X, Y, and His
`and Vis for each components. The decoder reconstructs
`the cfimensions xi and yi for each component, according
`to the following relationship shown in Equation 5:
`
`where r 1 is the ceiling function.
`
`6.2 Encoding Order and Interleaving
`A practical image compression standard must address
`how systems will need to handle the data during the
`process of decompression. Many applications need to
`the process of displaying or printing
`pipeline
`multiple-component images in parallel with the process
`
`of decompression. For many systems, this is only
`feasible if the components are interleaved together
`within the compressed data stream.
`
`To make the same interleaving machinery applicable to
`both DCT-based and predictive codecs, the JPEG
`proposal has defined the concept of “data unit.” A data
`unit is a sample in precfictive codecs and an 8x8 block
`of samples in DCT-based codecs.
`
`The order in which compressed data units are placed in
`the compressed data stream is a generalization of
`raster-scan order. Generally, data units are ordered
`from left-to-right and top-to-bottom according to the
`orientation shown in Figure 6. (It is the responsibility
`of applications to define which edges of a source image
`are top, bottom, left and right.) If an image component
`is noninterleaved (i.e., compressed without being
`interleaved with other components), compressed data
`units are ordered in a pure raster scan as shown in
`Figure 7.
`
`top
`
`left
`
`right
`
`bottom
`
`Figure 7. Noninterleaved Data Ordering
`
`When two or more components are interleaved, each
`component Ci is partitioned into rectangular regions of
`Hi by Vi data units, as shown in the generalized
`example of Figure 8. Regions are ordered within a
`component from left-to-right and top-to-bottom, and
`within a region, data units are ordered from left-to-right
`and top-to-bottom. The JPEG proposal defines the
`term Minimum Coded Unit (MCU) to be the smallest
`
`Apple Inc. Exhibit 1007 Page 8
`
`

`
`.
`
`, .
`
`xxvi
`
`IEEE Transactions on Consumer Electronics, Vol. 38, No. 1, FEBRUARY 1992
`
`C S ~ : H1=2, Viz2
`
`3 4 - z
`
`5
`
`C S ~ : H2=2, V2=l
`
`Cs3: H3=1, V3=2 CS4: H4=1, V4=1
`
`0 1 2 3 4 5
`
`0 1 2
`
`7 P a
`
`
`
`e
`.
`
`
`'I
`
`1
`
`2
`3
`
`0
`
`3
`
`Figure 8. Generalized Interleaved Data Ordering Example
`
`group of interleaved data units. For the example
`shown, MCU, consists of data units taken first from the
`top-left-most region of C,, followed by data units from
`the same region of C2, and likewise for C3 and C,.
`MCU, continues the pattem as shown.
`Thus, interleaved data is an ordered sequence of MCUs,
`and the number of data units contained in an MCU is
`determined by the number of components interleaved
`and their relative sampling factors. The maximum
`number of components which can be interleaved is 4
`and the maximum number of data units in an MCU is
`10. The latter restriction is expressed as shown in
`Equation 6, where
`the summation
`is

This document is available on Docket Alarm but you must sign up to view it.


Or .

Accessing this document will incur an additional charge of $.

After purchase, you can access this document again without charge.

Accept $ Charge
throbber

Still Working On It

This document is taking longer than usual to download. This can happen if we need to contact the court directly to obtain the document and their servers are running slowly.

Give it another minute or two to complete, and then try the refresh button.

throbber

A few More Minutes ... Still Working

It can take up to 5 minutes for us to download a document if the court servers are running slowly.

Thank you for your continued patience.

This document could not be displayed.

We could not find this document within its docket. Please go back to the docket page and check the link. If that does not work, go back to the docket and refresh it to pull the newest information.

Your account does not support viewing this document.

You need a Paid Account to view this document. Click here to change your account type.

Your account does not support viewing this document.

Set your membership status to view this document.

With a Docket Alarm membership, you'll get a whole lot more, including:

  • Up-to-date information for this case.
  • Email alerts whenever there is an update.
  • Full text search for other cases.
  • Get email alerts whenever a new case matches your search.

Become a Member

One Moment Please

The filing “” is large (MB) and is being downloaded.

Please refresh this page in a few minutes to see if the filing has been downloaded. The filing will also be emailed to you when the download completes.

Your document is on its way!

If you do not receive the document in five minutes, contact support at support@docketalarm.com.

Sealed Document

We are unable to display this document, it may be under a court ordered seal.

If you have proper credentials to access the file, you may proceed directly to the court's system using your government issued username and password.


Access Government Site

We are redirecting you
to a mobile optimized page.





Document Unreadable or Corrupt

Refresh this Document
Go to the Docket

We are unable to display this document.

Refresh this Document
Go to the Docket