TP3

ipynb13 kBPython · 7 cellsSolution of TP 3: DPCM

TP3- Differential Pulse-Code Modulation (DPCM)

Objectifs

To understand and implement Differential Pulse-Code Modulation (DPCM), study lossless and lossy predictive coding, compare open-loop versus closed-loop prediction, analyze quantization effects, and compute error metrics such as MSE and PSNR.

In [ ]
import cv2
import numpy as np


image1 = "image_1_grayscale.jpg"
image2 = "image_2_colored.jpg"

Part 1: Lossless DPCM on Image Data

Step I — Linear Representation of Image Data

Convert a 2D grayscale image matrix into a 1D sequence by flattening rows in raster-scan order. This representation enables sequential predictive processing.

Step II — Inverse Linear Representation

Reconstruct the original 2D image by reshaping the 1D linear sequence back into its height * width structure.

Step III — Lossless DPCM Encoding

Lossless DPCM reduces redundancy using a simple predictor. The prediction is:

x^n=xn−1\hat{x}_n = x_{n-1}

The difference signal is:

dn=xn−x^nd_n = x_n - \hat{x}_n

The first sample must be transmitted explicitly since it has no predictor.

Step IV — Lossless DPCM Decoding

Reconstruction is performed by summing the previous reconstructed value with the difference:

x~n=x~n−1+dn\tilde{x}_n = \tilde{x}_{n-1} + d_n

This results in perfect reconstruction.

In [ ]
# Step 1: Flatten the image into a 1D sequence
def image_to_sequence(image):
    # Convert to int16 to safely handle differences (negative values)
    return image.astype(np.int16).flatten()


# Step 2: Reconstruct the image from the 1D sequence
def sequence_to_image(sequence, shape):
    # Clip to valid range and convert back to uint8 for display/saving
    sequence = np.clip(sequence, 0, 255).astype(np.uint8)
    return sequence.reshape(shape)


# Step 3: Lossless DPCM Encoding
# x̂[n] = x[n-1]
# d[n] = x[n] - x̂[n]
# First sample x[0] is sent explicitly
def lossless_dpcm_encode(sequence):
    error = np.zeros_like(sequence, dtype=np.int16)

    # First sample: no predictor, transmit as-is
    error[0] = sequence[0]

    # Remaining samples: difference with previous sample
    for i in range(1, len(sequence)):
        error[i] = sequence[i] - sequence[i - 1]

    return error


# Step 4: Lossless DPCM Decoding
# x̃[0] = transmitted first sample (error[0])
# x̃[n] = x̃[n-1] + d[n]
def lossless_dpcm_decode(error):
    reconstructed = np.zeros_like(error, dtype=np.int16)

    # First sample
    reconstructed[0] = error[0]

    # Reconstruct rest
    for i in range(1, len(error)):
        reconstructed[i] = reconstructed[i - 1] + error[i]

    return reconstructed


# === Testing with image1 ===
image = cv2.imread(image1, cv2.IMREAD_GRAYSCALE)
sequence = image_to_sequence(image)

error = lossless_dpcm_encode(sequence)
reconstructed_sequence = lossless_dpcm_decode(error)

# Check perfect reconstruction (MSE should be 0)
mse = np.mean((sequence - reconstructed_sequence) ** 2)
print("MSE (lossless DPCM):", mse)

reconstructed_image = sequence_to_image(reconstructed_sequence, image.shape)
# Display reconstructed images
cv2.imshow("Reconstructed Image 1 (Lossless DPCM)", reconstructed_image)
cv2.waitKey(0)
cv2.destroyAllWindows()

Part 2: Lossy DPCM on Image Data (Quantization)

Lossy DPCM introduces a quantizer after the difference computation to reduce bitrate, at the cost of reconstruction accuracy.

Quantizer Step Size

For 8-bit images, the amplitude range of the difference signal is approximately −128-128 to +128+128. The uniform quantizer step size Δ\Delta is:

Δ=256/(2B)\Delta = 256 / (2^B)

where BB is the number of bits used to represent each quantized difference.

Closed-Loop DPCM Encoding

Closed-loop encoding uses the reconstructed (quantized) previous value as the predictor:

x^n=x~n−1\hat{x}_n = \tilde{x}_{n-1}

This ensures that both encoder and decoder use the same prediction reference, which prevents quantization error from accumulating across samples.

Open-Loop DPCM Encoding

Open-loop encoding uses the original previous sample for prediction:

x^n=xn−1\hat{x}_n = x_{n-1}

However, the decoder reconstructs using quantized differences, creating a mismatch:

x~n=x~n−1+d^n\tilde{x}_n = \tilde{x}_{n-1} + \hat{d}_n

This mismatch causes quantization error to accumulate from sample to sample, resulting in noticeable degradation.

Decoding (Both Modes)

Regardless of open- or closed-loop encoding, the decoder reconstructs the signal using:

x~n=x~n−1+d^n\tilde{x}_n = \tilde{x}_{n-1} + \hat{d}_n

The difference between schemes arises solely from the predictor used during encoding.

Error Metrics: MSE and PSNR

Mean Squared Error (MSE) measures the average squared difference between original and reconstructed signals:

MSE=1N∑n=0N−1(xn−x~n)2MSE = \frac{1}{N} \sum_{n=0}^{N-1} (x_n - \tilde{x}_n)^2

Peak Signal-to-Noise Ratio (PSNR) measures reconstruction quality relative to signal amplitude:

PSNR=10⋅log⁡10(MAX2MSE)PSNR = 10 \cdot \log_{10} \left( \frac{MAX^2}{MSE} \right)

For 8-bit images, MAX=255MAX = 255.

In [ ]
import numpy as np
import cv2


# --- 1. Quantizer Function ---
def quantize_uniform(value, bits):
    """
    Uniform quantization of the difference signal.
    Step size delta = 256 / 2^B.
    """
    if bits >= 8:
        return value  # No quantization needed for 8-bit depth

    levels = 2**bits
    delta = 256 / levels

    # Quantize: Divide by delta, round to nearest integer, multiply back
    # We add a small epsilon to avoid rounding issues at exact .5 boundaries if needed,
    # but standard np.round is sufficient here.
    quantized_val = np.round(value / delta) * delta

    return quantized_val.astype(np.int16)


# --- 2. Metrics Functions ---
def compute_metrics(original, reconstructed):
    """Computes MSE and PSNR."""
    mse = np.mean((original - reconstructed) ** 2)
    if mse == 0:
        return 0.0, float("inf")

    max_pixel = 255.0
    psnr = 10 * np.log10((max_pixel**2) / mse)
    return mse, psnr


# --- 3. Open-Loop DPCM (Prone to Drift) ---
def dpcm_open_loop(sequence, bits):
    """
    Predictor = Original previous sample x[n-1].
    Decoder accumulates quantized error, leading to drift.
    """
    n = len(sequence)
    reconstructed = np.zeros(n, dtype=np.int16)

    # First sample sent explicitly
    reconstructed[0] = sequence[0]

    for i in range(1, n):
        # PREDICTOR: Uses the ORIGINAL previous sample
        predictor = sequence[i - 1]

        # Difference
        diff = sequence[i] - predictor

        # Quantize
        q_diff = quantize_uniform(diff, bits)

        # DECODER: Reconstructs using its own previous reconstruction
        # This mismatch (Original Predictor vs Reconstructed History) causes drift
        reconstructed[i] = reconstructed[i - 1] + q_diff

    return np.clip(reconstructed, 0, 255)


# --- 4. Closed-Loop DPCM (Correct Method) ---
def dpcm_closed_loop(sequence, bits):
    """
    Predictor = Reconstructed previous sample x_tilde[n-1].
    Encoder and Decoder stay in sync.
    """
    n = len(sequence)
    reconstructed = np.zeros(n, dtype=np.int16)

    # First sample sent explicitly
    reconstructed[0] = sequence[0]

    for i in range(1, n):
        # PREDICTOR: Uses the RECONSTRUCTED previous sample (Feedback Loop)
        predictor = reconstructed[i - 1]

        # Difference
        diff = sequence[i] - predictor

        # Quantize
        q_diff = quantize_uniform(diff, bits)

        # DECODER & ENCODER UPDATE
        reconstructed[i] = reconstructed[i - 1] + q_diff

    return np.clip(reconstructed, 0, 255)


# --- 5. Main Execution ---

# Parameters
BITS = 3  # Try changing this to 2, 3, or 4 to see the effect!

# Run Open Loop
rec_open = dpcm_open_loop(sequence, BITS)
mse_open, psnr_open = compute_metrics(sequence, rec_open)

# Run Closed Loop
rec_closed = dpcm_closed_loop(sequence, BITS)
mse_closed, psnr_closed = compute_metrics(sequence, rec_closed)

# --- Display Results ---
print(f"--- DPCM Results ({BITS} bits) ---")
print(f"Open Loop   -> MSE: {mse_open:.2f}, PSNR: {psnr_open:.2f} dB")
print(f"Closed Loop -> MSE: {mse_closed:.2f}, PSNR: {psnr_closed:.2f} dB")

# Reshape for display
img_open = sequence_to_image(rec_open, image.shape)
img_closed = sequence_to_image(rec_closed, image.shape)

cv2.imshow(f"Open Loop ({BITS} bits) - Drift Visible", img_open)
cv2.imshow(f"Closed Loop ({BITS} bits) - Corrected", img_closed)

cv2.waitKey(0)
cv2.destroyAllWindows()

Part 3: Application to 1D Audio Signal

This section applies DPCM concepts to real audio data to visualize error reduction and quantization noise.

Step I — Load and Normalize Audio

Load a WAV audio file, extract the samples, and normalize them to a consistent range (e.g., −1-1 to +1+1).

Step II — Lossless DPCM on Audio

Apply lossless DPCM encoding. The difference signal will show reduced dynamic range compared to the original waveform.

Step III — Lossy DPCM with Different Bitrates

Apply lossy closed-loop DPCM with two bit settings:

  • High Quality: B=4B = 4 bits per difference (16 levels)
  • High Compression: B=2B = 2 bits per difference (4 levels)

Lower bit depth introduces more quantization noise, especially in slowly varying regions.

In TP 3: DPCM