Digitisation and Lossy Compression

Lossy Compression

• Lossy compression techniques exploit data redundancy and inherent perceptual redundancies in multimedia content.
• Lossless compression is effective for data with statistical redundancy but offers low compression ratios.
• Lossy compression involves irreversible information loss, reconstructing an approximate version of the original data.
• It is the basis for standards like MPEG and MP3.
• It exploits perceptual redundancy and is suitable when exact source reconstruction is unnecessary.
• It achieves higher compression levels, at least ten times compared to lossless methods.

Perceptual Redundancy

• Perceptual redundancy means removing information from an audio or visual signal without affecting the recipient’s experience.
• Multimedia signals often have inherent characteristics and redundancies that can be exploited during coding.
• In audio data, adjacent samples are often similar (highly correlated).
• In images, neighboring pixels can be spatially similar, containing regions with identical or similar-valued pixels.

Bit Rate and Distortion

• Source coding aims to represent a digital source using the fewest bits possible for a permissible distortion.
• Coding with fewer bits allows a lower bit rate (bandwidth) or smaller file size.
• Permissible distortion defines how much the reconstructed source can differ from the original.
• In MP3 and JPEG, higher compression leads to lower bit rates but increased audible or visual distortion (perceptual distortion).
• The relationship between compression level and distortion is formalized by the rate-distortion (RD) characteristic.
• High compression (better coding efficiency) leads to more distortion (bigger errors) in the reconstructed signal, and vice versa.
• Some coding approaches offer greater coding efficiency for a permissible distortion level.
• Others generate less visible distortion for a given bit rate.
• Distortion can be quantified by the signal-to-noise ratio (S/N ratio), reflecting the difference between the source and the reconstructed output.

Source Digitisation: Pulse Code Modulation (PCM)

• Digitizing an analog source signal generally uses a pulse code modulation (PCM) system.
• PCM comprises three main processing blocks: sampling, quantizing, and encoding.

Sampling

• Sampling converts a continuous analog time signal into a discrete-time representation.
• The sampling rate, $f<em>s$, must be at least twice the maximum signal bandwidth, $f</em>{max}$, to avoid loss of information:
  $f<em>s \geq 2f</em>{max}$
• The sampling period, $T<em>s$, is: $T</em>s = \frac{1}{f_s}$
• Meeting the sampling theorem guarantees the original analog signal can be reconstructed exactly.
• If the sampling theorem is not upheld, aliasing occurs.

Quantising

• Quantization digitizes sample amplitudes. It's usually performed by an analog-to-digital converter (ADC).
• A key ADC characteristic is the number of bits, $n$, it uses in its quantized representations of the samples.
• An n-bit ADC quantizes the signal into $2^n$ amplitudes.
• Quantization inevitably introduces errors because the continuous waveform is approximated by a finite number of discrete levels.
• The higher the number of quantization levels, the lower the resulting errors.
• The difference between the original and digital signals is called quantization noise (quantization error).
• Quantization is lossy, unlike sampling (when the sampling theorem is fulfilled).
• The signal-to-noise ratio (S/N ratio) is:
  $S/N \approx 6.02n \text{ dB}$
• Each bit contributes approximately 6 dB to the S/N ratio.

Non-Uniform Quantisation

• Unequal step sizes (non-uniform quantization) can exploit perceptual characteristics, e.g., in audio signals.
• The ear is not uniformly sensitive across the audible range, so coarser quantization (larger step sizes) can be used in less sensitive regions.
• Companding assigns more quantization levels to samples with low amplitude values and fewer levels to samples with high amplitude values.

Encoding

• Encoding might involve uncompressed bitstream output.
• It could also involve more coding to exploit redundancy in the uncompressed bitstream by compressing it using a lossless coding technique such as run-length encoding (RLE).

Differential PCM (DPCM)

• Differential pulse-code modulation (DPCM) converts an analog signal into a digital representation with a lower bit rate by including sample prediction in its coding.
• It codes the first sample, followed by the differences between successive values.
• The number of bits allocated to the difference values must accommodate the largest possible change between adjacent samples in both positive and negative directions.
• At the decoder, the reverse process is performed to reconstruct an approximation of the source from the received DPCM sequence.
• The encoder and decoder predict that the next sample will be the same as the current one, and the transmitted difference value is then the error in that prediction (prediction errors).

Predictive Coding

• Instead of assuming the next sample will be identical to the current sample, you can look back at how the samples have been changing and assume they will continue to change in the same way.
• The encoded data consists of differences (or prediction errors) between the predicted sample and the current sample ($\epsilon$):
  $\epsilon<em>n = x</em>s - \hat{x}$
• The error bitstream is quantized and compressed using a lossless coding technique before transmission.
• Parametric models exploit the correlation between multiple consecutive previous samples to estimate the next sample more accurately.

Image and Video Coding

• Video coding technologies, supported by unified international compression standards, enable the creation, communication, and consumption of visual information.
• Digital television (DTV) allows more channels in a given bandwidth than analog television because of compression.
• A 720 × 480 standard-definition (SD) color TV picture at 25 frames per second requires about 165 Gbytes of raw (uncompressed) data for 90 minutes of video.
• The most popular compression algorithms are the MPEG (Moving Picture Experts Group) family.

MPEG Standards

• MPEG-1: Efficient storage of moving pictures for multimedia on CD-ROM. Gave rise to CIF and SIF.
• MPEG-2: Optimized compression techniques for DTV systems to support SD and HD resolutions at bit rates between 4 and 20 Mbit s −1.
• MPEG-1 and -2 also include related audio standards, one of which – layer 3 – is the basis of MP3 coding.
• MPEG-4: Extended to provide flexible standards for multimedia materials, offering enhanced functionality. Includes AAC.
• The H.264/advanced video coding (AVC) standard is now formally incorporated into MPEG-4.
• MPEG-7: Specifies how multimedia content can be indexed and searched for and covers intellectual property aspects.
• MPEG-21: Extends this notion further by including digital rights management (DRM) into MPEG systems.

Coding Principles

• The objective of JPEG and MPEG coding is to remove as much statistical and perceptual redundancy as possible.

Spatial Compression

• Exploits the similarity (correlation) between neighboring areas of an image.
• Allows each individual picture (or frame) to be compressed (intra-frame compression).
• Basis of the JPEG image compression standard.

Temporal Compression

• Exploits the fact that very little changes between consecutive frames.
• Offers further significant lossy compression opportunities (inter-frame compression).
• The underlying details of the techniques for spatial compression are based upon the JPEG image coding standard.

JPEG Coding

• JPEG is the de facto lossy compression standard for color and grayscale images.
• Provides an improvement in coding efficiency of typically between 5 and 15 times over the data bitmap format of TIFF.
• Although categorized as a lossy coding technique, JPEG does have a lossless mode.

JPEG Encoder Block Diagram

• Image pre-processing (splitting into n × n pixel sections or macroblocks).
• Transform coding of each macroblock using a discrete cosine transform (DCT).
• Quantization.
• Lossless (Huffman) compression.

Pre-processing

• The source image is divided into equally sized macroblocks.
• JPEG generally uses 8 ×8 pixel macroblocks, which transform into 64 coefficients following the application of the DCT.

Discrete Cosine Transform (DCT)

• Transform coding converts a signal from one representation to another.
• For an image, spatial pixel values are transformed to a numerical representation in an alternative domain.
• In the transform representation, it is easier to see redundant information in the source image because energy that is unevenly distributed spatially across the image becomes concentrated in only a few significant transform coefficients.
• In the transform representation, it is easier to see redundant information in the source image because energy that is unevenly distributed spatially across the image becomes concentrated in only a few significant transform coefficients.
• The DCT is a special version of the Fourier transform that works by separating the spatial values of a signal into differing frequencies.
• For images, all frequency components are cosine functions in both the horizontal and vertical directions.

DCT Basis Functions

• JPEG generally uses 8 × 8 pixel macroblocks, which transforms into 64 DCT coefficients.
• The top-left component is the d.c. coefficient represents the average greyscale value of the full macroblock.
• The remaining 63 DCT frequencies are the a.c. coefficients in the transformed representation, which collectively show how rapidly (finely) the pixel values vary across the macroblock and in which directions.

Quantisation

• Involves carefully deciding the number of bits to be allocated to each coefficient.
• The human eye is much more sensitive to errors in the lower frequency information than the high-frequency information.
• JPEG encodes the important, higher-valued low frequency, a.c. coefficients with more bits (finer quantisation) and achieves compression by encoding the higher frequency coefficients with fewer bits (coarser quantisation).

Q-Table

• The quantisation matrix or Q-table used in JPEG determines the level of lossy compression applied.
• The DCT coefficient value in each element is divided by the corresponding Q-table entry, with only the integer portion retained as the replacement for the original value.
• Q-tables are designed to reflect how our eye works.
• Lossless quality JPEG-coded images have a Q-table full of ones meaning there is no quantisation of the DCT coefficients.

Lossless compression

• The quantised values are rearranged into the zig-zag scanning pattern, placing the quantised DCT coefficients in order of ascending frequency for the horizontal and vertical directions combined.
• This can result in relatively long sequences consisting entirely of zeros.
• The amplitude of the d.c. coefficient (top left) in a macroblock can be large and vary between blocks, though there is often considerable similarity in the values in adjacent blocks.
• DPCM encodes the difference between the d.c. coefficients in the current and previous macroblocks, leading to smaller values and thus fewer bits.
• By using Huffman coding to allocate short codewords to the most commonly occurring patterns and longer codewords to patterns that occur less frequently, further compression of the final JPEG bitstream is achieved.

Qualitative performance of JPEG

• Performance deteriorates at low bit rates.

Limitations

• No interactive functionality – JPEG cannot compress a region of interest (ROI) at a different bit rate from the remainder of the image.
• Lack of coding optimisation for natural and synthetic computer-generated images.
• Degraded performance in noisy (wireless/mobile) channel conditions – picture quality drops when transmission errors occur.
• Poor compression of compound documents containing both images and text.

JPEG2000

• JPEG2000 is a low-bit-rate image compression standard that offers interactive, multi-resolution scalability.
• It supports different image sizes, color depths and ROI coding, and incorporates error correction.

Features

• Bitstream scalability, so the image can change its representation to satisfy the requirements of an application or receiver.
• Coded bitstream consists of a series of embedded sub-bitstreams, encompassing different resolutions and qualities.
• The decoding device reconstructs the image according to its own bit-rate capability.
• Transform coding is used, but instead of the DCT, the orthogonal discrete wavelet transform (DWT) is employed.
• The DWT decomposes an image into four sub-images with each having a different resolution corresponding to a different frequency bands.
• Perceived distortion tends to be more distributed across an image and appreciably less blocky than JPEG at low bit rates, thereby affording a subjectively smoother appearance.

Region-of-Interest (ROI) Coding

• If a particular region of an image is known to be more important, it can be assigned higher priority.
• JPEG2000 bitstream can be constructed so that ROI lossless compression is applied.

Adoption

• Has still to achieve widespread adoption.
• Reasons include web browsers and social media websites not supporting the .jp2 format.
• Computationally the DCT is much more efficient than the DWT.
• Patent and licensing issues have encumbered an open-source image coding standard.

MPEG Video Coding

• Motion-JPEG (M-JPEG) applies JPEG compression to each individual frame (intra-frame).
• M-JPEG does not consider any information in the previous or next frames.
• Inefficient and raises the possibility of exploiting the obvious temporal redundancy between frames.

Motion

• Motion describes the dynamic content in a sequence.
• Global (camera) motion depends on the pan and zoom of the camera.
• Local (object) motion depends on only the velocity and projection angle of the object(s).

Motion Prediction and Compensation

• Continue using JPEG for intra-frame compression but also employ inter-frame compression by introducing the concept of motion vectors (MV).
• The idea is to predict the current frame from the previously stored frame by calculating aset of MVs, then determine the motion prediction error between the predicted and actual frames so that the prediction can be compensated at the decoder.

Prediction

• Calculating the motion vectors in every frame is computationally demanding for the encoder.

Steps Involved In Calculation

• Previous frame is stored and divided into macroblocks, usually 16 × 16 pixels.
• Current frame is split into macroblocks of the same size.
• Similarity between a macroblock in the current frame and each macroblock in the previous frame is computed using a block-matching algorithm.
• The best match (highest similarity value) defines the motion vector for that macroblock in the current frame.
• Motion vectors are expressed using horizontal and vertical coordinate values.

Motion Vectors

• Motion vectors are a simple expression of linear movement (translation) in two dimensions, they do not allow for any rotation or change in the size of objects.

MPEG Picture Types

• I-frames (intra-frame) are JPEG-coded, and used as a reference for random access within MPEG bitstreams. Do not use motion vectors, so they achieve only low compression.
• P-frames (prediction) use motion prediction and compensation to achieve higher compression than I-frames. Used as a reference for both future and past predictions, but do not offer random access capability within the coded bitstream.
• B-frames (bidirectional prediction) are interpolated frames between I- and P-frames in both forward and backward directions. They are not used as a reference, but instead ‘fill in’ missing frames. Provide the highest compression, used to fill in missing frames.

Compensation

• When using motion vectors to predict the motion between frames, errors are inevitable.
• Two steps:
  • Find the best prediction using a block-matching algorithm to determine the set of motion vectors.
  • Calculate the motion prediction or residual error between the estimated and actual object positions, and transmit it alongside the motion vectors.
• The prediction error is normally much smaller, and thus requires far fewer bits to transmit, than the whole frame.

Group of Pictures (GOP)

• The term group of pictures (GOP) is used by MPEG to refer to the particular combination of frames that represents a sequence. Always starting with a reference I-frame, different combinations of P- and B-frames are feasible up until the next I-frame.
• The structure of a GOP is specified by two parameters: the total number of frames in the GOP, N, and the number of adjacent B-frames plus one, M.
• Bidirectional interpolation is involved in constructing the B-frames.

H.264/AVC (Advanced Video Coding)

• Embedded into the MPEG-4 standard as MPEG-4, Part 10.
• Performance is superior to both MPEG-2 and earlier MPEG-4 versions.
• H.264/AVC still employs the key blocks of motion prediction and compensation (motion vectors), transform coding, quantisation and lossless coding, as in earlier MPEG video standards (MPEG-1 and -2), with the differences being in the details of each block.

Features

• Integer block-based transform is employed, that is an approximation to the DCT.
• Supports scalable bitstreams, in terms of spatial resolution, frame rate and picture quality.
• SP- and SI-frames can be seamlessly incorporated into the GOP format, designed to support efficient switching between bitstreams of different qualities or bit rates.

Emerging trends

• Multiview Video Coding (MVC): Shift in video coding has been taking place, from focusing on the efficient coding of ever larger numbers of pixels in a single- view representation to processing more views.
• High Efficiency Video Coding (HEVC) and Versatile Video Coding (VCC): High Efficiency Video Coding (H.265/HEVC) standard, was developed as a successor to H.264/AVC, delivering the same picture quality but at half the bitrate.
• Machine learning in source coding: Machine learning (ML) is a subset of artificial intelligence which is becoming more widely applied in image/video content processing, understanding and compression with Convolutional Neural Networks (CNN) for example.

Digital Audio Coding

• Different digital audio file formats are largely characterized by the way audio samples are arranged and (often) compressed.

The Auditory System

• Humans are more sensitive to frequencies in the range 1 to 5 kHz than to those outside this range.
• Below the perception threshold, sounds are not heard; above the threshold, sounds are audible.
• Perceptual masking occurs when the composition of a sound can alter the ear’s ability to perceive specific frequencies at specific amplitudes.
• There are both frequency masking and temporal masking. Noise may, as a result of either of the two masking effects, fall below the threshold and consequently no longer be perceived

Frequency Masking

• Arises because of the inherent property of the ear that a relatively loud sound at a particular frequency reduces our sensitivity to neighboring frequencies (i.e. it raises the perceptual hearing threshold).

Temporal masking

• Our perceptual hearing sensitivity to sounds in a narrow frequency range is reduced for a short period, before and after the presence of a relatively strong sound in that frequency range.

MPEG Audio Layer 3 (MP3)

• The source input is generally assumed to be an audio data stream from either a CD or studio-recorded material.
• Generally used sampling rates are (fs = 44.1 kHz) or (fs = 48 kHz).

Key Components

• Signal is firstly transform coded.
• Signal being then filtered into 32 critical frequency sub-bands.
• Determines the amount of masking in each sub-band and its effect on adjacent bands (the mask-to-noise ratio (MNR)). This uses the two psychoacoustic masking effects of the ear.
• Output level in any sub-band is below the masking threshold is not encoded; if it is above the masking threshold, it will be coded using variable bit-rate (VBR) coding.
• In VBR coding, the number of bits allocated to represent each frequency component is based upon the level of quantisation noise.
• 6-bit scaling factors for each sub-band are included in the MP3 bitstream, giving a total of 64 possible scaling values.

Other Audio Formats

• Windows Media audio (WMA): Proprietary audio-streaming format developed by Microsoft for its Windows media player platform.
• Ogg Vorbis (OV): Alternative open-source lossy audio coding format that offers superior compression performance to MP3 and AAC.
• Waveform audio format (WAV) and audio interchange file format (AIFF): These do not use compression and provide perceptual quality indistinguishable from the source.
• Free lossless audio codec (FLAC): Lossless format that does apply compression, thus making considerable storage savings whilst retaining the audio fidelity of the source.

MPEG-4 AAC (Advanced Audio Coding)

• Next-generation format designed as the successor to MP3 for low-bit-rate perceptual audio compression, for used in efficient internet multimedia streaming applications in mind.
• The encoder provides better audio quality for the same bit rate as MP3, with greater flexibility and functionality.

Features

• Wider range of sampling rates: from 8 to 96 kHz compared with 16 to 48 kHz.
• Supports up to 48 channels (mono, stereo and multichannel surround sound).
• Uses either 2048 or 256 sub-bands compared to 32 for MP3.
• Audio files do not have to be encoded at a specific streaming speed.
• AAC supports scalable representations in terms of sample amplitudes (or S/N ratio) and sampling rates.

Tools To Advance Standard

• Perceptual noise substitution.
• Spectral band replication.
• Parametric stereo.

Perceptual Noise Substitution

• Processes noise-like signals to save bits and improves the compression achieved.
• Instead of transmitting all the spectral noise components, the bitstream flags to the decoder that the signal in aparticular frequency band is noise and provides some information regarding the corresponding power level in that band

Spectral Band Replication

• SBR: A single-channel technology that extends the perceived audio bandwidth without using very many bits.
• Reconstructs the missing higher frequency information.
• Two steps involved in SBR:
  • Low and mid-range frequency bands, which generally cover the range from 0 kHz to either 5 kHz or 12 kHz, are copied to construct the high-frequency band (SBR component) envelope.
  • This envelope is then adaptively amended to extend the perceptual bandwidth by applying the principles outlined above for tonal and noise-like signals in particular bands.
    *What this does mean is that we need to provide some guidance to the decoder so it can construct a good perceptual estimate of the information discarded during MP3 encoding and modify the high-frequency band envelope accordingly

High-Efficiency AAC (HE-AAC)

• Also known as AACplus.
• Specifically optimized for very-low-bit-rate applications such as audio streaming and podcasting, and is now the standard technology used in digital radio broadcasting.
• Can be independently used with different encoders and produces low-data side information; however, unlike SBR, it is multichannel and analyzes the spatial characteristics between the left and right channels of a stereo signal to exploit inter-channel redundancies.
  *A general rule is, it is backward compatible with existing standards, e.g. . MP3 - a MP3 decoder decode can replay files incorporating SBR by ignoring the higher-frequency replicated components.

Human Speech Coding

• Human generate two main classes of speech sounds
  • Voiced
  • Unvoiced
• Both can be processed and encoded effectively

Voiced sounds

• Voiced speech the vocal cords resonate (vibrate), with the airflow from the lungs then being modulated by these vibrations/ All vowels /a, e, i, o, u/ and certain consonants /m, n, l, w/ create voiced sounds that produce resonances (harmonics), with the main harmonic frequencies being known as formants.

Unvoiced Speech/

• Unvoiced speech occurs when air from the lungs is forced through a narrow constriction, leading to turbulence. The vocal cords do not resonate, so there are no formants (spectral peaks) and the spectrum is much flatter and noise-like.
  Examples include plosive consonants /p, b, t, k/, which involve sudden bursts of air being expelled, and fricative consonants /s, f, h, n, r, z/

Speech-Coding Methods

• Focus is efficient encoding and synthesis techniques for human speech, so proposed solutions may not be appropriate for other audio signal types (such as music).
• Can broadly be divided into two categories:
  • Waveform encoding: processes data using time or frequency techniques (e.g., PCM and DPCM).
  • Vocoder (voice encoder) methods: formulate a mathematical model of the voice production process (significant compression ratio savings).

Linear Predictive Coding (LPC)

• LPC model accurately estimates key speech production parameters relating to the acoustics of the vocal tract for both voiced and unvoiced sounds, despite their different signal characteristics.
• The binary U/V input decision, a gain value G, and a set of N quantised model coefficients need to be transmitted to the decoder in order to synthesise natural-sounding speech.

Code-Excited LP (CELP) Coding

• CELP is specified as the low-bit-rate speech-coding profile in the MPEG-4 AAC standard and a key constituent block in the Adaptive Multi-Rate (AMR) speech-coding standard.
• CELP uses the LPC model, with the key difference that a codebook (dictionary) of quantised excitation vectors, known as ‘codewords’, is used, accessed in real time during LPC modelling of each frame.

Adaptive Multi-Rate (AMR) Coding

• AMR is a speech compression format specifically optimized for low-bit-rate mobile network applications such as Voice over Internet Protocol (VoIP).
• two coding classes:
  • AMR-NB (narrowband): Covers the standard telephone line bandwidth (300 Hz to 3.4 kHz).
  • AMR-WB (wideband):Extends the bandwidth coverage (50 Hz to 7kHz).
• The network dynamically selects one of the modes to provide the best instantaneous speech quality depending on prevailing channel conditions.

AMR Also Supports Transmissions Discontinuous Transmissions

• Transitory powering down of mobile devices when no voice input is present.

Enhanced Voice Systems (EVS)

• Enhanced Voice Services (EVS): This is the low-latency speech and audio coding standard developed for Voice over Long-Term Evolution (VoLTE) which in comparison with 3G, affords superior quality voice calls over 4G LTE networks.
  *Enhanced Voice Services (EVS)This is the low-latency speech and audio coding standard developed for Voice over Long-Term Evolution (VoLTE) which in comparison with 3G, affords superior quality voice calls over 4G LTE networks.

QoS and Source Coding

• This section, I will briefly explore how specific source-coding mechanisms support quality-of-service (QoS) provision in streaming multimedia content over diverse networks (wired, wireless, mobile).

What Is QoS?

• QoS performance can be characterized by many parameters, which include transmission bit rate, BER, S/N ratio, blocking probability, latency and jitter.

Scalable Representations

• These are a central QoS mechanism in coding multimedia standards such as H.264/AVC, JPEG2000 and AMR.
• A scalable representation the compression of source data into a single bitstream, which comprises a variety of different sub- bitstreams and are A scalable representation involves sub- bitstream is obtained by ignoring (dropping) packets from the original single bitstream to lower the bit rate required for the relevant sub-bitstream .