Haar Transform and Queuing Techniques Quiz

Podcast

Play an AI-generated podcast conversation about this lesson

Questions and Answers

What does the first half of the sequence {xn, i} represent in the context of the Haar transform?

A coarser approximation of the original signal (correct)

Detail errors of the original signal

An exact replica of the original signal

A sequence of the original signal's maximum values

In the 2-D Haar Wavelet Transform, what type of features are represented in the top right subimage?

Random noise patterns

Near-horizontal edges

Near-vertical edges (correct)

Uniform regions of intensity

What mathematical operation is primarily utilized in the Haar Wavelet Transform to create the new sequence?

Summation of all pixel values

Pairwise average and difference (correct)

Multiplication of pixel values

Matrix inversion

How is the resulting sequence {xn, i , dn-1, i} structured after applying the Haar Transform?

It includes averages followed by the differences. Signup and view all the answers

Which statement is true regarding the energy distribution in the 2-D Haar Transform?

Most energy is contained in the top left subimage. Signup and view all the answers

What is a consequence of having a long transmit queue in the context of software queuing?

Poor performance of the software queuing system Signup and view all the answers

In Weighted Fair Queuing (WFQ), which flow type is prioritized for reduced response time?

Interactive flows Signup and view all the answers

What does Class-Based Weighted Fair Queuing (CBWFQ) extend from standard WFQ?

Support for user-defined traffic classes Signup and view all the answers

What is the primary benefit of Low Latency Queuing (LLQ) in conjunction with CBWFQ?

High-priority traffic is policed during congestion Signup and view all the answers

What happens when a router interface experiences congestion?

Additional incoming packets are dropped Signup and view all the answers

What is a significant limitation of tail drop as a congestion management technique?

It affects TCP synchronization and may cause TCP starvation Signup and view all the answers

How does WFQ address the issue of unfairness among flows?

By introducing weight to give more bandwidth to lower precedence flows Signup and view all the answers

What is a characteristic of packets belonging to a class in CBWFQ?

They are routed based on user-defined match criteria Signup and view all the answers

What is the primary benefit of using a difference operator in lossless image compression?

Minimizes spatial redundancy in images Signup and view all the answers

Which of the following is NOT part of the process in lossless JPEG compression?

Using a linear transform Signup and view all the answers

What method is used to achieve a narrower histogram in the difference image?

Defining the difference between pixel values Signup and view all the answers

In the context of lossless image compression, what does the term 'entropy' refer to?

The amount of uncertainty or information Signup and view all the answers

What is the purpose of using the discrete 2-D Laplacian operator in lossless image compression?

To define a difference image Signup and view all the answers

Which of the following statements about lossy image compression is true?

It eliminates some image data to achieve higher compression. Signup and view all the answers

What role do neighboring pixel values play in lossless JPEG compression?

They serve as comparators for predictive modeling. Signup and view all the answers

The efficiency of coding in lossy image compression is enhanced by reducing which aspect of the input vector?

Correlation between components Signup and view all the answers

What is the total number of samples included in a frame for Layer 2 or Layer 3?

1,152 samples Signup and view all the answers

Which feature does Layer 3 of MPEG-1 audio NOT incorporate?

A fixed filter bank Signup and view all the answers

What type of light do laser sources produce?

A single wavelength Signup and view all the answers

How does the human eye process images in low light levels?

Using rods which produce grayscale images Signup and view all the answers

Which color is least sensitive to cones in the human eye?

Blue Signup and view all the answers

What is a key change introduced in Layer 2 of MPEG-1 audio?

Complexity increase for better quality Signup and view all the answers

What is the primary function of the retina in human vision?

Receiving light signals through rods and cones Signup and view all the answers

Which characteristic differentiates a ruby laser from other light sources?

It produces a bright, scarlet-red beam Signup and view all the answers

What happens in the RED mechanism when the average queue size is between 0 and the minimum threshold?

No packets are dropped. Signup and view all the answers

Which of the following best describes the Weighted Random Early Detection (WRED) mechanism?

It utilizes multiple profiles identified by thresholds and probabilities. Signup and view all the answers

What is the primary purpose of traffic policing?

Restricting bandwidth by dropping or marking excess traffic. Signup and view all the answers

How does WRED differ from standard RED in terms of packet drop behavior?

WRED drops less important packets more aggressively. Signup and view all the answers

Which mode of RED is in effect when the average queue size exceeds the maximum threshold?

Full drop (tail drop). Signup and view all the answers

What is a key difference between traffic shaping and traffic policing?

Traffic shaping buffers excess traffic while policing drops it. Signup and view all the answers

In which scenario would class-based WRED (CBWRED) be utilized?

When combined with class-based weighted fair queuing (CBWFQ). Signup and view all the answers

What typically happens to TCP sessions under the effects of RED?

They slow to match output-link bandwidth. Signup and view all the answers

What is the primary approach used in MPEG audio compression for general audio?

Waveform coding Signup and view all the answers

Which frequency range is typical for human hearing?

20 Hz to 20 kHz Signup and view all the answers

What is the dynamic range of human hearing measured in decibels?

120 dB Signup and view all the answers

How does frequency masking affect the perception of sounds?

Lower tones can mask higher tones. Signup and view all the answers

What defines critical bands in hearing?

They define the frequency range where two tones can be heard separately. Signup and view all the answers

What is perceptual coding in the context of audio compression?

A strategy that removes unnoticeable sounds based on hearing psychology. Signup and view all the answers

Which factor influences the effectiveness of masking tones?

The frequency difference between the tones. Signup and view all the answers

In MPEG audio encoding, what characteristic of lossy compression methods is utilized?

Remove sounds that are masked by other louder sounds. Signup and view all the answers

Study Notes

Congestion and Queuing

Congestion can occur at any point in the network where there are points of speed mismatches or aggregation.
Queuing manages congestion to provide bandwidth and delay guarantees.

Queuing Algorithms

First-in, first-out (FIFO)
Priority queuing (PQ)
Round robin
Weighted round robin (WRR)

FIFO

First packet in is first packet out
Simplest of all queuing algorithms
Single queue
All individual queues within the network are FIFO

Priority Queuing

Uses multiple queues
Allows prioritization
Always empties first queue before proceeding to next queue
Empty queue 1; if empty, dispatch queue 2; if both empty dispatch queue 3
Queues 2 and 3 may "starve".

Round Robin Queuing

Uses multiple queues
No prioritization
Dispatches one packet from each queue in each round
One packet from queue 1, then one from queue 2... and so on
Then repeat

Weighted Round Robin Queuing

Allows prioritization
Assigns a weight to each queue
Dispatches packets from each queue proportionately to the assigned weight
Dispatch up to 4 from queue 1
Dispatch up to 2 from queue 2
Dispatch 1 from queue 3
Go back to queue 1

Router Queuing Components

Each physical interface has a hardware and a software queuing system.
Software queuing system can support FIFO, PQ, WRR...
Hardware queue always uses FIFO queuing.

The Software Queue

A full hardware queue indicates interface congestion.
Software queuing is used to manage congestion.
When a packet if being forwarded and the hardware queue has space it, the router can bypass the software queue.

The Hardware Queue

Routers determine the length of the hardware queue based on the configured bandwidth of the interface.
The length of the hardware queue can be adjusted with the tx-ring-limit command.
Reducing the size of the hardware queue has two benefits:
Reduces the maximum amount of time packets wait in the FIFO queue before transmission.
Accelerates the use of QoS in Cisco IOS software.
Improper tuning of the hardware queue may produce undesirable results.
A long transmission queue may result in poor software queuing performance.
A short transmission queue may result in high CPU utilization (interrupts) and low link utilization.

Weighted Fair Queuing (WFQ)

A queuing algorithm that fairly shares bandwidth amongst flows
Reduces response time for interactive flows by scheduling them to the front of the queue.
Prevents high-volume flows from monopolizing an interface.
Conversations are sorted into flows and sent by the order of the last bit crossing the channel.
Unfairness is reinstated by introducing weight to give proportionately more bandwidth to flows with higher IP precedence (lower weight).
The terms WFQ flows and conversations can be used interchangeably.

Class-Based Weighted Fair Queuing (CBWFQ)

A mechanism to guarantee bandwidth to classes.
Extends WFQ functionalities to provide support for user-defined traffic classes.
Classes are based on user-defined matching criteria.
Packets satisfying the class criteria constitute the traffic for that class.
A queue is reserved for each class, and traffic belonging to a class is directed to that class queue.

Low Latency Queuing (LLQ)

Adds a priority queue to CBWFQ for real-time traffic.
High-priority classes are guaranteed low-latency propagation of packets, bandwidth.
High-priority classes are also policed when congestion occurs.
Lower-priority classes use CBWFQ.

Dropping/Congestion Management

Managing Interface Congestion with Tail Drop

Router interfaces experience congestion when the output queue is full.
Additional incoming packets are dropped.
Dropped packets may cause significant application performance degradation.
Tail drop has significant drawbacks.

Tail Drop Limitations

In some situations, simple tail drop should be avoided because it contains significant flaws.
Dropping can affect TCP synchronization
Dropping can cause TCP starvation
There is no differentiated drop; high-priority traffic is dropped as easily as low priority traffic.

Random Early Detection (RED)

Tail drop can be avoided if congestion is prevented.
RED is a mechanism that randomly drops packets before a queue is full.
RED increases the drop rate as the average queue size increases.
Result of RED: TCP sessions slow to the approximate rate of output-link bandwidth.
Average queue size is small (much less than maximum queue size)
TCP sessions desynchronized by random drops.

RED Drop Profiles

Shows drop probability, minimum and maximum thresholds and average queue size.

RED Modes

No drop: When the average queue size is between 0 and the minimum threshold.
Random drop: When the average queue size is between the minimum and maximum thresholds.
Full drop (tail drop): When the average queue size is above the maximum threshold.
Random drop should prevent congestion, thus preventing tail drops.

Weighted Random Early Detection (WRED)

WRED can use multiple RED profiles.
Each profile is identified by Minimum, Maximum threshold and Mark probability denominator.
WRED profile selection is based on IP precedence (8 profiles) and DSCP (64 profiles).
WRED drops less important packets more aggressively than more important packets.
WRED can be applied at the interface, VC or class level.

WRED Building Blocks

Shows the process of arriving IP packet extraction of IP precedence, calculating average queue size, checking queue fullness, and performing random drop/tail drop.

Class-Based WRED (CBWRED)

Class based WRED is available when configured in combination with CBWFQ.
Using CBWFQ with WRED allows the implementation of DiffServ Assured forwarding PHB.
Class-based configuration of WRED is identical to stand-alone WRED.

Traffic Policing and Shaping

Traffic Conditioners

Policing - Limits bandwidth by discarding traffic. Can re-mark excess traffic and attempt to send. Should be used on higher-speed interfaces. Can be applied inbound or outbound.
Shaping - Limits excess traffic by buffering. Buffering can lead to a delay. Recommended for slower-speed interfaces. Cannot re-mark traffic. Can only be applied in the outbound direction.

Traffic Policing and Shaping Overview

These mechanisms must classify packets before policing or shaping the traffic rate.
Traffic policing typically drops or marks excess traffic within a traffic rate limit.
Traffic shaping queues excess packets to stay within the desired traffic rate.

Why Use Policing? Why Use Shaping?

Limiting access to resources when high-speed access is used but not desired (subrate access) and limiting traffic rate of certain applications or traffic classes.
Marking down (recoloring) exceeding traffic at Layer 2 or Layer 3.
Preventing and managing congestion in ATM, Frame Relay, and Metro Ethernet networks, where asymmetric bandwidths are used along the traffic path.
Regulating the sending traffic rate to match the subscribed (committed) rate in ATM, Frame Relay or Metro Ethernet networks.
Implementing shaping at the network edge.

Policing Versus Shaping

Policing: Incoming and outgoing directions, out-of-profile packets are dropped. Dropping causes TCP retransmits. Policing supports packet marking or re-marking.
Shaping: Outgoing direction only, out-of-profile packets are queued until a buffer gets full. Buffering minimizes TCP retransmits. Marking or re-marking not supported. Shaping supports interaction with Frame Relay congestion indication.

Token Bucket

Mathematical model used by routers and switches to regulate traffic flow.
Tokens represent permission to send a number of bits in to the network.
Tokens are put into the bucket at a certain rate by IOS.
Token bucket holds tokens.
Tokens are removed from the bucket when packets are forwarded.
If there are not enough tokens in the bucket to send the packet, traffic conditioning is invoked (shaping or policing)
Sufficient tokens are available (conform action).
Tokens equivalent to the packet size are removed from the bucket. The packet is transmitted.

Single Token Bucket Exceed Action

Insufficient tokens are available (exceed action).
Drop (or, mark) the packet.

Single Token Bucket Class-Based Policing

Token Arrival Rate (CIR)
Bc is normal burst size.
Tc is the time interval.
CIR is the committed information rate.
CIR = Bc / Tc

MPEG Audio Compression

LPC and CELP are tuned to speech parameters
Audio compression methods applicable to general audio like music, and broadcast digital TV
Waveform coding approach – makes the decompressed amplitude-versus-time waveform as possible similar to input signal
Use of psychoacoustic model of hearing to evaluate audio content for possible compression
The kind of coding is termed perceptual coding.

Psychoacoustics

Humans can hear 20 Hz to 20 kHz.
Voice frequency is typically 200Hz to 4 kHz
Dynamic range, is approximately 120 dB

Frequency Masking

Lossy audio data compression methods, such as MPEG/Audio encoding, remove some sounds that are masked anyway.
Lower tone masks a higher tone effectively
The reverse is not true: Higher tone doesn't mask a lower tone well
Higher power in the masking tone, wider influence on the broader range of frequency

Critical Bands

Frequency-dependent resolution in human hearing.
Critical bandwidth in a complex tone corresponds to the smallest frequency difference between two tones that can still be perceived separately.
Critical bandwidth represents the ear’s resolving power for simultaneous tones/partials

Temporal Masking

After loud tone, our ears need time to recover.
Loud tone saturates the ear receptors, requiring recovery time
Measuring the time sensitivity of hearing can be done via masking experiments

MPEG Audio

Uses psychoacoustic models to construct a large multi-dimensional lookup table.
Transmits masked frequency components using fewer bits.
Appliers a filter bank to break the input into frequency components
In parallel, Applies psychoacoustic model, and uses bit allocation to quantize the information providing compression

MPEG Audio Strategy

MPEG approach to compression relies on quantization
Human auditory system is not accurate within the width of a critical band. (Perceived loudness and audibility of a frequency).
MPEG encoder employs bank of filters.
Analyzes frequency components, by calculating a frequency transform of a window of signal values.
Decompose the signal into subbands using a bank of filters (Layer 1 & 2: "quadrature-mirror"; Layer 3: adds a DCT; psychoacoustic model: Fourier transform)

Frequency masking – using a psychoacoustic model to estimate the just noticeable noise level:

Encoder balances the masking behavior and the available number of bits by discarding inaudible frequencies.
Scaling quantization according to sound level that’s left over above masking levels.
May take into account actual width of the critical bands.
For practical purposes audible frequencies are divided into 25 main critical bands.
To keep simplicity, adopts a uniform width for all frequency analysis filters, using 32 overlapping subbands.

MPEG Layers

MPEG audio has three compatible layers
Each succeeding layer is able to understand lower layer
Compression effectiveness increases going form Layer 1 to Layer 3 (also, accompanying extra delays)
Objective is a good tradeoff between quality and bit-rate.
Layer 1 is good quality with a high bit-rate
Layer 2 has higher complexity, proposed for digital audio broadcasting
Layer 3 (MP3) – most complex and targeted at audio transmission over ISDN lines

Basic Algorithm

Algorithm proceeds by dividing input into 32 frequency subbands, via a filter bank.
A linear operation taking 32 PCM samples, sampled in time; where output is 32 frequency coefficients
In Layer 1 encoder, sets of 32 PCM values are first assembled into sets 12 groups of 32s.
Layer 2 or Layer 3 frame actually accumulates more than 12 samples for each subband.

MPEG Audio Frame Sizes

Shows how subband filters produce samples in Layer 1 and Layer 2/3 frames.

Layer 2 of MPEG-1 Audio

Small changes to effect bitrate reduction and quality improvement, at the price of increased complexity

Layer 3 of MPEG-1 Audio

Employs similar filter bank as Layer 2 but with non-equal frequencies
Takes into account stereo redundancy
Uses Modified Discrete Cosine Transform (MDCT)

Color in Image and Video

Light and Spectrum

Light: Electromagnetic wave, color is characterized by wavelength content of light.
Laser light consists of a single wavelength.
Most light sources produce contributions over many wavelengths.
Visible wavelengths.
Short wavelengths produce blue sensation, long wavelengths produce red one.

Human Vision

Eye works like a camera, focusing image upside down and reversed onto the retina
Retina consists of rods and three kinds of cones
Rods come into play with low light, producing grayscale image
Cones produce a signal at high light levels
Red (R), Green (G), and Blue (B) light – cones most sensitive to these.
Blue sensitivity is much smaller than others

Color-Matching Functions

Amounts of R, G, and B the subject selects to match each single-wavelength light forms the color-matching curves.

CIE Chromaticity Diagram

Color-matching curves have negative lobes
Fictitious primaries
Matrix chosen such that the middle standard color-matching function Y(λ) equals the luminous-efficiency curve

Transform XYZ to RGB

Transformations for X, Y, and Z in terms of R, G, and B

Subtractive Color: CMY Color Model

Additive color: light beams combine
Subtractive color: ink subtracts certain colors from white illumination
Yellow ink subtracts blue
Reflects red and green

Transformation from RGB to CMY

Simple model to invert for specifying ink density to obtain a desired RGB color
Inverts the transformation in RGB to CMY

CMYK System

Undercolor removal – calculate part of the CMY mix that be black and remove it to create sharper, cheaper printer colors

Color Models in Video

Largely derived from older analog methods of coding color for TV.
Luminance is separated from color information.
YIQ is used to transmit TV signals in North America and Japan.
PAL or SECAM codings uses matrix transform called YUV.
Digital video mostly uses a matrix transform called YCbCr, which is closely related to YUV.

YUV Color Model

YUV codes a luminance signal (for gamma-corrected signals).
Chrominance refers to the difference between a color and a reference white at the same luminance – use color differences U, V
For gray, R'= G'= B', the luminance Y' equals to that gray
Chrominance (U,V) is zero for grays

Graphics and Image Data Representations

8-bit Gray-level Images

Pixel has gray value between 0 and 255.
One byte represents each pixel.
Bitmap – two-dimensional array of pixel values
Image resolution refers to the number of pixels – higher resolution better quality.
Frame buffer – Hardware to store bitmap, often in video card.
Resolution of video card does not need to match the desired resolution of the image.

Dithering

Used to calculate patterns of dots in relation to 0-255 values for darker pixels, used for 1-bit printing
Strategy to replace pixel with larger patterns (e.g. 22 or 44)
Aims for analog process with varying-sized disks of ink in halftone printing (used for newspaper photos)
Half-tone printing uses smaller or larger filled circles for shading, for newspaper printing
Example of 2*2 dither matrix

24-bit Color Images

Each pixel represented by three bytes (usually represents RGB)
Supports 256 * 256 * 256 possible colors (16,777,216)
Storage penalty. 640*480 24-bit image requires 921.6kB of storage (without compression)

8-bit Color Images

8 bits of color information
Uses lookup table for color information.
Image stores index into a table with 3-byte values that specify the color for each pixel.
Saving is great, 640*480 8-bit color image requires only 300kB (without compression)

Color Look-up Tables (LUTs)

Stores only the index/code value for each pixel.
The value corresponds to a row within the LUT.

JPEG

Most important current standard for image compression
Takes advantage of limitations of the human visual system
Allows to set desired quality/compression ratio (input divided by output)

Lossless and Lossy Image Compression

Lossless Image Compression

Approaches of Differential Coding of Images
Given an original image I(x, y), a difference image D(x,y) is defined as D(x, y) = I(x, y) - I(x - 1, y) OR D(x, y) = 4I(x, y) – I(x - 1, y) – I(x, y + 1) – I(x + 1, y) – I(x, y-1)
Spatial redundancy exists in normal images (difference image has narrower histogram and small entropy)

Lossless JPEG

Special case of JPEG image compression
Differential prediction – predictor combines values of up to three neighboring pixels.
Encodes difference using lossless compression techniques (e.g., Huffman coding)

Lossy Image Compression by Transform Coding

Based on linear transformation of input to a less correlated vector (Y)
Information accurately described by the first few components.
Remaining components are coarsely quantized
Discrete Cosine Transform (DCT)
Karhunen-Loève Transform (KLT)

Spatial Frequency and DCT

Spatial frequency indicates how many times pixel values change across an image block.
DCT formalizes this (measure of how much the image content changes in correspondence to the number of cycles of a cos wave per block).
DCT decomposes signal into DC and AC components.
IDCT reconstructs the signal.

Definition of DCT

Transforms input function (f(i, j)) into a new function (F(u,v))
Formula provided

Wavelet Transform Introduction

Wavelet: a small wave
Converts a signal into a series of wavelets
Objective of wavelet transform is decomposing signal into interpretable components, that have special components.

Haar Wavelet Transform

Simplest wavelet transform
Input sequence {xn,i) = {10, 13, 25...}
Transform (xn-1, i) = (xn,2i + xn,2i+1) / 2 ,dn-1,i = (xn,2i – xn,2i+1) / 2
Concatenation to form new sequence {(xn, i, dn-1, i)}

2-D Haar Wavelet Transform

Apply transform to complete image.
Group pixels into 2 x 2 blocks.
Group top-left components to form the top-left subimage.