Results 1 to 6 of 6

Thread: DWT Image Compression using Linear Algebra

  1. #1
    Member
    Join Date
    Jun 2016
    Location
    UAE
    Posts
    4
    Thanks
    1
    Thanked 0 Times in 0 Posts

    DWT Image Compression using Linear Algebra

    Hey all,

    Haar DWT image compression is a series of filtering and downsampling. But with the help of linear algebra we just need to compute the following operation: Compressed Image (C) = Transformation Matrix (H) * Original Image (I) * Transformation Matrix Transpose (H^t). How can we relate the subsampling that occurs in the first method with matrix multiplication in the second. The second method will always hold the same matrix size so where is the value of compression?!

    Thanks a lot in advance.

  2. #2
    Member
    Join Date
    Nov 2013
    Location
    Kraków, Poland
    Posts
    645
    Thanks
    205
    Thanked 196 Times in 119 Posts
    Haar coefficients are differences between average values of neighboring regions - it can be found by a simple recurrence - take the main part of https://github.com/JarekDuda/FractalWavelets (below) but replace vectors with powers of 2 (1,2,4,8,...) to get standard Haar.
    void find_coef(){                               // values -> coefficients
    int lt=fn_cf(center, 2, depth-2), rt=fn_cf(center + v[depth-1], 3, depth-2);
    *(coef+1)= rt-lt; *coef = rt + lt;
    }
    int fn_cf(coord cn, int ps, int dp){ // recurrence
    int lt, rt;
    if(dp){lt=fn_cf(cn, ps<<1, dp-1); rt=fn_cf(cn + v[dp], (ps<<1)+1, dp-1);}
    else {lt=getpixel(cn.x, cn.y); rt=getpixel(cn.x + v[0].x, cn.y + v[0].y);}
    *(coef+ps) = rt-lt; return rt+lt;
    }

    void find_val(){fn_vl(*coef, 1, center, depth-1); } // coefficients -> values
    void fn_vl(int sum, int ps, coord cn, int dp){ // recurrence
    int dif = *(coef+ps), lt = (sum - dif)>>1, rt = (sum + dif)>>1;
    if(dp){fn_vl(lt, ps<<1, cn, dp-1); fn_vl(rt, (ps<<1)+1, cn+v[dp], dp-1);}
    else {setpixel(cn.x,cn.y,lt); setpixel(cn.x + v[0].x, cn.y + v[0].y,rt);}
    }

  3. #3
    Member
    Join Date
    Jun 2016
    Location
    UAE
    Posts
    4
    Thanks
    1
    Thanked 0 Times in 0 Posts
    Thank you for your answer. My main concern is that in the linear algebra method where can we see the subsampling that must occur in the first method which will decrease the amount of stored or transmitted data.

  4. #4
    Member
    Join Date
    Nov 2013
    Location
    Kraków, Poland
    Posts
    645
    Thanks
    205
    Thanked 196 Times in 119 Posts
    Haar transform is just a reversible linear transform, e.g. for x0, x1, x2, x3 you get
    c0 = x0 + x1 + x2 + x3
    c1 = (x0 + x1) - (x2 + x3)
    c2 = x0 - x1
    c3 = x2 - x3

  5. #5
    Member
    Join Date
    Apr 2012
    Location
    Stuttgart
    Posts
    437
    Thanks
    1
    Thanked 96 Times in 57 Posts
    Quote Originally Posted by Jessy View Post
    Haar DWT image compression is a series of filtering and downsampling. But with the help of linear algebra we just need to compute the following operation: Compressed Image (C) = Transformation Matrix (H) * Original Image (I) * Transformation Matrix Transpose (H^t).
    Actually, no. First, the transformation doesn't compress anything. Second, there is no transposed matrix. It is simply:

    Transformed image = Transformation matrix * input image.

    Quote Originally Posted by Jessy View Post
    How can we relate the subsampling that occurs in the first method with matrix multiplication in the second.
    The typical way how to deal with that is to use the polyphase matrix notation. That is, you write your image in the Z-domain as I(z) = \sum_k i_k z^k, and then decompose this as a two dimensional vector v(z) that consists of even and odd samples.

    v(z) = (x_even(z),x_odd(z))^T

    The transformed signal then consists of a low-pass and a high pass that are the two components that result from the application of the polyphase matrix of the wavelet filter on the even/odd separation of the input:

    (h(z),g(z))^T = P(z) (x_ev(z),xo_(z))^T

    It is a nice exercise to compute the polyphase matrix of some wavelets.

    Quote Originally Posted by Jessy View Post
    The second method will always hold the same matrix size so where is the value of compression?!
    As said, there is no compression at this stage. Compression happens afterwards, by two steps: First, by quantizing the coefficients, i.e. by removing redunancy (or precision) you do not need. This again does not reduce the size of the matrix, but it already removes information.

    Second, by entropy coding the output of the quantizer, i.e. the quantization indices generated by the quantizer.

    The reason why you can entropy-code the transformed and quantized data is because the *transformed data* consists now of one single large amplitude signal (the low-pass) and many small-amplitude signals (the high-passes), and the latter are easy to compress.

    So what the transformation does is to implement an energy-compaction of the original signal that *enables* compression. The energy-compaction by itself is reversible. The compression happens by first leaving data away (due to quantization) and by entropy coding the outcome.

  6. The Following 2 Users Say Thank You to thorfdbg For This Useful Post:

    Bulat Ziganshin (23rd June 2016),Jessy (28th June 2016)

  7. #6
    Member
    Join Date
    Jun 2016
    Location
    UAE
    Posts
    4
    Thanks
    1
    Thanked 0 Times in 0 Posts
    Thanks a lot for your explanation! I'll read more on the polyphase matrix..

Similar Threads

  1. Image compression for microcontroller
    By branislav in forum Data Compression
    Replies: 6
    Last Post: 16th November 2015, 23:24
  2. Linear and Geometric Mixtures - Analysis
    By toffer in forum Data Compression
    Replies: 0
    Last Post: 27th January 2013, 22:12
  3. 3d image compression
    By m^2 in forum Data Compression
    Replies: 5
    Last Post: 9th July 2012, 08:52
  4. Generator matrix for linear code
    By azizever83 in forum Data Compression
    Replies: 0
    Last Post: 9th June 2012, 08:37
  5. Updating the linear mixer with BFA
    By Shelwien in forum Data Compression
    Replies: 1
    Last Post: 13th November 2010, 14:52

Tags for this Thread

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •