Compression: the process of coding that will effectively reduce the total number of bits

needed to represent certain information.

A General Data Compression Scheme

Image compression is a type of data compression applied to digital images, to reduce their
cost for storage or transmission.

 Lossy compression
 Lossless compression

If the compression and decompression processes induce no information loss, then the
compression scheme is lossless; otherwise, it is lossy.

Lossless compression: In lossless lossless data compression, data compression, the integrity
of the data is the integrity of the data is preserved preserved. The original data and the data
after . The original data and the data after compression and decompressi compression and
decompression are exactly the same on are exactly the same because, in these methods,
because, in these methods, the compression and the compression and decompression
algorithms ar decompression algorithms are exact inverses of each e exact inverses of each
other: no part of the data is : no part of the data is lost in the process. lost in the process.

Redundant data is removed in compression Redundant data is removed in compression and

added during decompression added during decompression. Lossless compression . Lossless
compression methods are normally used wh methods are normally used when we cannot
afford to en we cannot afford to lose any data.

Lossy compression: Our eyes and ears cannot distinguish subtle changes. In such cases, we
can use a lossy such cases; we can use a lossy data compression method. Lossy methods are
especially suitable for natural images such as photographs in applications where minor
(sometimes imperceptible) loss of fidelity is acceptable to achieve a substantial reduction in
bit rate.

Lossy compression that produces negligible differences may be called visually lossless.

Lossless image compression techniques are:

1. Run-length encoding – used in PCX, BMP, TGA, TIFF

2. variable-length coding (Huffman, Arithmetic Coding )
3. Bit Plane coding
4. DPCM and Predictive Coding
5. Entropy encoding
6. LZW coding
7. Adaptive dictionary algorithms – used in GIF and TIFF
8. Deflation – used in PNG, MNG, and TIFF
9. Chain codes

Lossy compression techniques are:

1. Reducing the color space.

2. Chroma subsampling.
3. Fractal compression
4. Transform coding (DCT and Wavelet):

 Discrete cosine transform (DCT) used in JPEG.

 Wavelet transform (reversible or irreversible) used in JPEG2000
 Run-length encoding
It is a simplest data compression technique.

Run-length encoding (RLE) is a form of lossless data compression in which runs of data
(sequences in which the same data value occurs in many consecutive data elements) are
stored as a single data value and count, rather than as the original run. This is most useful on
data that contains many such runs.

The general idea behind this method is to replace consecutive repeating occurrences of
a symbol by one occurrence of the symbol followed by the number of occurrences.

For example, simple graphic images such as icons, line drawings etc.

Example 1: Suppose string is AAAAAAA then Run-length encoding is A7 (A is character

and 7 is number of times appear that string)

Example 2: If input string is “WWWWAAADEXXXXXX”, then the Run-length encoding

is W4A3D1E1X6.
Explain JPEG Compression Encoding and decoding

JPEG stands for Joint Photographic Experts Group. We perform such type of compression
to reduce the size of the file without damaging its quality. By reducing the size we can store
it in a huge amount which was not possible earlier. Reducing the size of images will also
improve the efficiency of the system as it will give less load on it.

Process of JPEG Compression:

Firstly, we convert the R, G, B color format to Y, Cb, Cr format. Some colors are more
sensitive to human eyes and thus are high-frequency colors. Some colors of chromium
compounds like Cb and Cr are less sensitive to human eyes thus can be ignored. Then we
reduce the size of pixels in downsampling. We divide our image into 8*8 pixels and perform
forward DCT(Direct Cosine Transformation). Then we perform quantization using quantum
tables and we compress our data using various encoding methods like run-length encoding
and Huffman encoding.

In the second stage, we decompress our data, It involves decoding where we decode our data,
and we again de-quantize our data by referring to the quantization table. Then we perform
Inverse DCT and upsampling to convert it into original pixels and finally, color
transformation takes place to convert the image into its original color format.
Algorithm of JPEG Data Compression:

1. Splitting –
We split our image into the blocks of 8*8 blocks. It forms 64 blocks in which each
block is referred to as 1 pixel.

2. ColorSpaceTransform –
In this phase, we convert R, G, B to Y, Cb, Cr model. Here Y is for brightness, Cb is
color blueness and Cr stands for Color redness. We transform it into chromium colors
as these are less sensitive to human eyes thus can be removed.

3. Apply DCT –
We apply Direct cosine transform on each block. The discrete cosine transform (DCT)
represents an image as a sum of sinusoids of varying magnitudes and frequencies.

4. Quantization –
In the Quantization process, we quantize our data using the quantization table.
5. Serialization –
In serialization, we perform the zig-zag scanning pattern to exploit redundancy.

6. Vectoring –
We apply DPCM (differential pulse code modeling) on DC elements. DC elements
are used to define the strength of colors.

7. Encoding –
In the last stage, we apply to encode either run-length encoding or Huffman
encoding. The main aim is to convert the image into text and by applying any
encoding we convert it into binary form (0, 1) to compress the data.
Explain the JPEG 2000 Compression standard?
JPEG2000
Introduction/History

In 1997, the Joint Photographic Experts Group (JPEG) began work on the next version of the JPEG Image
Compression Standard. Members of the group had identified some problems with the original JPEG standard as
well compiled a "wish list" of new features and enhancements the next version of the standard should possess.
The new standard was named the JPEG2000 Image Compression Standard.

Many of the features and enhancements of JPEG2000 are described in the subsection Features/Enhancements as
well as the problems of the original standard that were addressed by JPEG2000. The mathematics behind the
Discrete Wavelet Transformation used in JPEG2000 is described in the Wavelet Transformations section and
the subsection Quantization gives more information about the quantization process in lossy JPEG2000
compression. The goal of this section is to describe a very basic algorithm for performing JPEG2000
compression on a digital grayscale image.

Basic Algorithm
Like JPEG, the JPEG2000 Image Compression Standard consists of four basic steps in the
algorithm - preprocess, transformation, quantization, encoding. Unlike JPEG, the
quantization step is optional if the user wishes to perform lossless compression. Where JPEG
uses an advanced version of Huffman coding, JPEG2000 utilizes a new coding method
called Embedded Block Coding with Optimized Truncation (EBCOT).

To explain the steps of the algorithm, we will use as a running example, the image above.
The dimensions of the image 160 x 240 pixels.

Step 1 - Preprocessing

The only preprocessing step we will use is the centering of the grayscale intensity values.
Towards this end, we subtract 127 from each intensity value in the image matrix. If we were
compressing a color image, we would first convert to YCbCr space and then center each of
the Y, Cb, and Cr channels.

Step 2 - Transformation

One of the major changes in the JPEG2000 standard is the use of the Discrete Wavelet
Transformation (DWT) instead of the DCT. If we are performing lossy compression, we use
the DWT with the CDF97 filter. For lossless compression, we use the DWT in conjunction
with the LeGall53 filter and perform the computation using the lifting method due to Wim
Sweldens. In both cases, we compute 2-3 iterations of the DWT. In our example, we compute
two iterations of each transformation.

Step 3 - Quantization

If we are performing lossless compression, the DWT pictured above right is encoded and
the algorithm is concluded. For lossy compression, JPEG2000 employs a quantization
scheme somewhat similar to that used by JPEG on the 8 x 8 blocks. For two iterations, the
DWT creates seven blocks and each of these blocks are quantized separately. Values in
each block are either moved closer to zero or converted to zero and then converted to an
integer via the floor function. More details regarding the quantization process can be found in
the Quantization subsection. The result for our running example is displayed at right.

Step 4 - Encoding

For the final step in the compression standard, we use Embedded Block Coding with
Optimized Truncation. We do not cover the EBCOT method here.

For lossless compression, we simply use EBCOT to code the elements of the wavelet
transformation constructed with the LeGall filter. In this case, we can store the image using
215,544 bits. The original image, in raw format, requires 307,200 bits of storage so the
lossless method represents a savings of about 30%. The compression rate is 5.6bpp.

For lossy compression, EBCOT allows us to use only 84,504 bits as opposed to the original
size of 160*240*8 = 307,200 bits. The compression rate is about 2.2bpp. If we compress the
same image using JPEG, we need 103,944 bits for a compression rate of 2.7bpp. The original
image, the JPEG2000-compressed image, and the JPEG-compressed image.

APPLICATIONS USES JPEG 2000

Digital Cinema
As the video coding standard for digital cinema since 2004, JPEG 2000 allows for high-
quality, high-resolution video compression, which is a key requirement in the film industry.

Medical Imaging

JPEG 2000 is often the format of choice in the field of medical imaging. Its ability to
maintain high image quality at lower bit-rates makes it suitable for detailed imagery like
MRI, CT scans, and X-rays, where loss of information could be critical.

Geographic Information Systems (GIS)

In GIS applications, the superior compression and quality benefits of JPEG 2000 are used for
satellite imagery and large-scale maps. Its capabilities in handling large image files make it
particularly useful in this field.

Remote Sensing In remote sensing applications, where data is collected from satellite or
high-flying aircraft, JPEG 2000’s efficient compression algorithms make it easier to transmit
data back to Earth without losing critical details.

Print and Publishing

While not as commonly used as other formats like TIFF, JPEG 2000 is also useful in print
and publishing for its high-quality image representation.

Surveillance Systems
Some modern surveillance systems employ JPEG 2000 to take advantage of its high
compression ratios and image quality. This is particularly useful for long-term storage of
surveillance footage where quality should not be compromised.

Explain the MPEG Video Compression?

MPEG is a method for video compression, which involves the compression of digital images
and sound, as well as synchronization of the two.

There currently are several MPEG standards.

 MPEG-1 is intended for intermediate data rates, on the order of 1.5 Mbit/sec.
 MPEG-2 is intended for high data rates of at least 10 Mbit/sec.
 MPEG-3 was intended for HDTV compression but was found to be redundant and
was merged with MPEG-2.
 MPEG-4 is intended for very low data rates of less than 64 Kbit/sec.
i. In principle, a motion picture is a rapid flow of a set of frames, where each frame is
an image. In other words, a frame is a spatial combination of pixels, and a video is a
temporal combination of frames that are sent one after another.
ii. Compressing video, then, means spatially compressing each frame and temporally
compressing a set off names.
iii. Spatial Compression: The spatial compression of each frame is done with JPEG
Each frame is a picture that can be independently compressed.
Temporal Compression: In temporal compression, redundant frames are removed.
v. To temporally compress data, the MPEG method first divides frames into three categories:
vi. I-frames, P-frames, and B-frames. Figure1 shows a sample sequence off names.

Fig1: MPEG frameshow I-, P-, and B-frames are constructed from a series of seven frames.

Fig2: MPEG frame construction

I-frames: An intracoded frame (I-frame) is an independent frame that is not related to any
other frame.
They are present at regular intervals. An I-frame must appear periodically to handle some
sudden change in the frame that the previous and following frames cannot show. Also, when
a video is broadcast, a viewer may tune at any time. If there is only one I-frame at the
beginning of the broadcast, the viewer who tunes in late will not receive a complete picture.
I-frames are independent of other frames and cannot be constructed from other frames.
P-frames: A predicted frame (P-frame) is related to the preceding I-frame or P-frame. In
other words, each P-frame contains only the changes from the preceding frame. The changes,
however, cannot cover a big segment. For example, for a fast-moving object, the new
changes may not be recorded in a P-frame. P-frames can be constructed only from previous I-
or P-frames. P-frames carry much less information than other frame types and carry even
fewer bits after compression.
B-frames: A bidirectional frame (B-frame) is related to the preceding and following I-frame
or P-frame. In other words, each B-frame is relative to the past and the future. Note that a B-
frame is never related to another B-frame.
  According to the MPEG standard the entire movie is considered as a video sequence
which consist of pictures each having three components, one luminance component
and two chrominance components (y, u & v).
 The luminance component contains the gray scale picture & the chrominance
components provide the color, hue & saturation.
 Each component is a rectangular array of samples & each row of the array is called
the raster line.
 The eye is more sensitive to spatial variations of luminance but less sensitive to
similar variations in chrominance. Hence MPEG – 1 standard samples the
chrominance components at half the resolution of luminance components.
 The input to MPEG encoder is called the resource data and the output of the MPEG
decoder is called the reconstructed data.
 The MPEG decoder has three parts, audio layer, video layer, system layer.

 The system layer reads and interprets the various headers in the source data and
transmits this data to either audio or video layer.
 The basic building block of an MPEG picture is the macro block as shown:

 The macro block consist of 16×16 block of luminance gray scale samples divided into
four 8×8 blocks of chrominance samples.
 The MPEG compression of a macro block consist of passing each of the °6 blocks
their DCT quantization and entropy encoding similar to JPEG.
 A picture in MPEG is made up of slices where each slice is continuous set of macro
blocks having a similar gray scale component.
 The concept of slice is important when a picture contains uniform areas.
 The MPEG standard defines a quantization stage having values (1, 31). Quantization
for intra coding is:

QDCT =(16×DCT)+sign(DCT)×quantizer scale)2×quantizer - scale×θ

Where
DCT = Discrete cosine transform of the coefficienting encoded
Q = Quantization coefficient from quantization table

Quantization rule for encoding,

QDCT =16×DCT2×quantizer - scale×θ�DCT =16×���2×quantizer - scale×θ

 The quantized numbers Q_(DCT )are encoded using non adaptive Haffman method
and the standard defines specific Haffman code tables which are calculated by
collecting statistic.
 Differential Encoding Scheme
8
 Differential Pulse Code Modulation (DPCM)
9

pn = f ( xˆn −1 , xˆn −2 ,K, xˆ0 )

 Differential Image Coding
36

Consider the predictor

… in combination with 2-bit uniform quantizer & AC

™ 1 bit/pixel encoding—compare to JPEG at the same rate

Diff coded: SNR=22dB, PSNR=31dB JPEG: SNR=33dB, PSNR=42dB