Scribd Logo
Upload

Welcome to Scribd!

  • 29 views

    CH - 10 - 1 VQ Description PDF

    Uploaded by

    Alexandre Cabrel
    Vector quantization (VQ) is a lossy compression technique that groups samples into vectors and quantizes each vector. This exploits correlation between samples to achieve better compression than quantizing samples individually. VQ involves designing a codebook of reconstruction vectors. The encoder finds the closest matching reconstruction vector for each input vector and outputs the index. The decoder uses the index to lookup the reconstruction vector. Increasing the vector dimension improves performance up to a point, but also increases complexity for the encoder.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd

    CH - 10 - 1 VQ Description PDF

    Uploaded by

    Alexandre Cabrel
    29 views13 pages
    Vector quantization (VQ) is a lossy compression technique that groups samples into vectors and quantizes each vector. This exploits correlation between samples to achieve better compression than quantizing samples individually. VQ involves designing a codebook of reconstruction vectors. The encoder finds the closest matching reconstruction vector for each input vector and outputs the index. The decoder uses the index to lookup the reconstruction vector. Increasing the vector dimension improves performance up to a point, but also increases complexity for the encoder.

    Original Title

    Ch_10_1 VQ Description (PPT).pdf

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    Vector quantization (VQ) is a lossy compression technique that groups samples into vectors and quantizes each vector. This exploits correlation between samples to achieve better compression than quantizing samples individually. VQ involves designing a codebook of reconstruction vectors. The encoder finds the closest matching reconstruction vector for each input vector and outputs the index. The decoder uses the index to lookup the reconstruction vector. Increasing the vector dimension improves performance up to a point, but also increases complexity for the encoder.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    29 views13 pages

    CH - 10 - 1 VQ Description PDF

    Uploaded by

    Alexandre Cabrel
    Vector quantization (VQ) is a lossy compression technique that groups samples into vectors and quantizes each vector. This exploits correlation between samples to achieve better compression than quantizing samples individually. VQ involves designing a codebook of reconstruction vectors. The encoder finds the closest matching reconstruction vector for each input vector and outputs the index. The decoder uses the index to lookup the reconstruction vector. Increasing the vector dimension improves performance up to a point, but also increases complexity for the encoder.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    of 13

    Ch.

    10 Vector Quantization

    Overview

    1
    Motivation
    Recall in Lossless Methods:
    • Block Huffman is better than single-symbol Huffman
    – Blocks allow to exploit correlation between symbols (assuming source
    symbols are not independent!)
    • Shannon proved that “blocking taken to the limit” achieves
    optimal compression… exploits correlation

    Recall in Scalar Quantization:


    • It is the lossy version of a single-symbol method
    • Shannon also proved that for lossy we can achieve the
    theoretical bound on compression (R-D curve) via “blocking
    taken to the limit”

    This blocking idea motivates Vector Quantization


    2
    Main Idea of VQ
    That info theory says to consider “blocking” to exploit correlation

    Î Group into vectors (non-overlapping) and “quantize” each vector


    x[n]

    n
    No Need to Limit
    to 2-D Vectors

    Samples in
    ACF of Speech
    vector are highly
    correlated!

    1 2 3
    k
    3
    Illustration of Gain from VQ: Real Speech Data
    Equivalent VQ is
    to SQ Better
    than SQ
    10x10
    Quant.
    x1 Cells x1

    Only quantize
    this band… two
    options!

    x2 x2
    • 100 cells smaller than SQ
    – Same Rate, Lower Distortion
    • Fewer than 100 cells of same size as SQ
    – Lower rate, Same Distortion
    4
    Going to higher dimension: vectors concentrated in smaller
    % of whole space Î Improved Performance

    Same speech signal…


    3-D VQ

    5
    Forming Vectors
    For time signals… we usually form vectors from temporally-sequential samples.

    For images… we usually form vectors from spatially-sequential samples.

    But… you should let the ACF structure guide your choice…
    ACF

    N N
    Note: Book uses upper-
    case italic to indicate a
    vector… I use the
    k more standard lower-
    x1 = [ x[0] x[ N ] x[2 N ] x[3N ]]
    case bold non-italic…

    x 2 = [ x[1] x[ N + 1] x[2 N + 1] x[3N + 1]]

    x 3 = [ x[2] x[ N + 2] x[2 N + 2] x[3N + 2]]


    6
    Designing VQ
    Q: What does it mean to design a VQ?
    A: Similar to SQ… Specify Decision Boundaries and Reconstruction Values…
    except now those are in N-D space… Goal is to minimize MSQE for a given rate
    (or vice versa)
    Example of a VQ Design: For 2-D
    vectors taken from a sequence of
    independent Gaussian samples…
    Decision Somehow we need to design the
    Boundary DBs and RLs…
    However, we really only need to
    specify the RLs…
    Recon
    Level Then the ith Decision Region
    consists of all points closer to the
    ith RL than they are to any other
    RL
    We’ll see how to do this later…

    7
    Figure from book Vector Quantization and Signal Compression by Gersho & Gray
    Structure of a VQ Fig. 10.1 in Textbook

    L-Dim.
    Vectors

    Binary Codes
    ⎡log2M⎤ bits
    1 code per code vector

    M L-Dim Code Vectors


    i.e. Reconstruction Points

    8
    x2
    Example 2

    x[n]: … 0.75 1.27 1.78 2.11 … 1

    -2 -1 1 2
    x1
    -1

    -2

    Encoder Decoder
    Find Closest Table
    Code-Vector Look-Up
    Codebook Index Index Codebook
    -2 -2 00 00 -2 -2
    -1 -1 01 01 -1 -1
    1 1 10 10 1 1
    2 2 11 11 2 2
    9
    Encoder & Decoder Operation
    Encoder: Search codebook for code vector yj that is closest to
    input vector x.
    Codebook {y i }i =1 = C where each y i ∈ℜ L
    M

    x is closest to yj if:
    x − y j ≤ x − yi ∀y i ∈ C d ( x , y j ) ≤ d ( x , y i ) ∀y i ∈ C

    ∑z (Euclidian Notation: If x is closest to yj we


    where z = 2

    i =1
    i Norm) write Q(x) = yj

    for z = [ z1 z2 " z L ]
    T Note: VQ cells are defined by the
    RLs & these equations rather than
    explicit boundaries!!!

    Decoder: Use received binary codeword (the “index”) as an


    address into the codebook (i.e., Table Look-Up) 10
    Complexity of VQ
    Encoder is Computationally Complex
    Must check all M yi for closeness… must compute M norms
    M can be quite large: 256, 512, 1024, etc.
    Decoder is Easy & Fast

    VQ Complexity is Asymmetrical
    • May not work well for Real-Time Encoding
    • But Real-Time Decoding is very easy

    11
    VQ Rate & Performance vs. Rate
    If L-D vectors are quantized using a VQ having M
    reconstruction points we need binary codewords having

    codeword length = ⎡⎢ log 2 M ⎤⎥ bits/vector “Typical” L values:


    • Images: L = 16 (4x4)
    ⎡⎢log 2 M ⎤⎥
    # bits/sample = bits/sample • Speech: L = 3,4,5,6
    L

    Info Theory Says: Increasing L improves the VQ performance

    Practice Says: … only up to a point!


    • Improvement decreases w/ increasing L
    • Design gets harder w/ increasing L
    • Encoder complexity grows w/ increasing L
    12
    13

    You might also like