Results 1 to 3 of 3

Thread: 2D fractal Haar wavelet transform (implemented)

  1. #1
    Member
    Join Date
    Nov 2013
    Location
    Kraków, Poland
    Posts
    645
    Thanks
    205
    Thanked 196 Times in 119 Posts

    Lightbulb 2D fractal Haar wavelet transform (implemented)

    I have recently mentioned a possibility of fractal Haar wavelets in a different thread and finally decided to implement it: https://github.com/JarekDuda/FractalWavelets
    While Fourier transform requires at least O(n*log(n)) time, the cost of this one grows in a linear way, so we can cheaply use as large block as we want here.
    Another advantage is that boundaries between regions (which are fractals - "fraxels"?) are more complex and so blocking artifacts should be less visually disturbing.
    Also, a block has 6 neighbors here, so maybe we could use correlations in a better way.

    Here are examples of such blocking (values -> Haar coefficients, then trim high frequencies: set them to zero, then coefficients -> values. The rest of picture has remained unchanged):
    Click image for larger version. 

Name:	fravelets.png 
Views:	346 
Size:	456.6 KB 
ID:	3139

    The transform loop is a simple recurrence:
    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);}
    }

    Where "center" is the starting point, the region has 2^depth pixels, v[] is the chosen set of shifts, "*coef" is hash-like array of coefficients.
    Zeroth coefficient is the sum of all values, the other are differences between average values of two parts of a block (in hash-like tree) - each coefficient distributes the sum between both sub-blocks.

    Making a lossy image compression is a long way:
    - cover all positions (blocks can have various sizes down to 1 pixel, the dimensions of picture can determine the block structure),
    - choose a quantizer,
    - maybe add some intra-prediction, use correlations,
    - add some entropy coder.

    What do you think of such transform for lossy image compression?
    What other interesting set of shift (v[]) can we use?
    Have you heard of similar approaches?

    Update: I have just found a 15 year old paper on this subject: http://www.fondationricard.com/docum...Pdelft99_6.pdf
    The author was probably not aware or the tame twindragon case, which seems the most appropriate here (?)
    Last edited by Jarek; 11th September 2014 at 19:47.

  2. #2
    Member
    Join Date
    Apr 2012
    Location
    Stuttgart
    Posts
    437
    Thanks
    1
    Thanked 96 Times in 57 Posts
    Quote Originally Posted by Jarek View Post
    What do you think of such transform for lossy image compression? What other interesting set of shift (v[]) can we use? Have you heard of similar approaches?
    I think you should probably look into the research of Antonio Ortega. This looks like a special case of "wavelets on graphs". Here's the talk from ICIP 2013: http://sipi.usc.edu/~ortega/Papers/G...013-Ortega.pdf Here is another reference you may find interesting: Critically sampled graph-based wavelet transforms for image coding Narang, S.K. ; Yung-Hsuan Chao ; Ortega, A. Signal and Information Processing Association Annual Summit and Conference (APSIPA), 2013 Asia-Pacific DOI: 10.1109/APSIPA.2013.6694319 Publication Year: 2013 , Page(s): 1 - 4 HTHH, Thomas

  3. The Following User Says Thank You to thorfdbg For This Useful Post:

    Jarek (12th September 2014)

  4. #3
    Member
    Join Date
    Nov 2013
    Location
    Kraków, Poland
    Posts
    645
    Thanks
    205
    Thanked 196 Times in 119 Posts
    Thanks Thomas. I was working on the eigenspectrum of graphs for my last phd from the perspective of MERW (maximal entropy random walk, simulator) - where mainly the dominant eigenvector was interesting as the other coordinates were vanishing exponentially (thermalization):
    Click image for larger version. 

Name:	eigenvectors.png 
Views:	386 
Size:	75.2 KB 
ID:	3143
    Indeed while Fourier transform can be seen as going to the eigenspectrum of graph being a regular lattice, as in the sources you have provided, we can analogously define transforms for more general graphs - e.g. depending on edges of picture.

    However, they are still using standard box-based lattices.
    Using e.g. shifts v[] from complex base numeral systems like here instead (e.g. as additional edges), we could generalize their approach to nicer fractal-like blocks.
    From the other side, this graph eigenspectrum approach could allow to generalize presented Haar wavelets into some more sophisticated ones.

    ps. We could also made some hybrid fravelet-fourier system: e.g. divide picture into such regular lattice of fractal-like regions, then take e.g. 8x8 block of such regions and perform e.g. discrete cosine transform on their average values (zeroth coefficient). Thanks of it, boundary artifact should be less visually disturbing.

    Update - discussion: https://groups.google.com/forum/#!to...on/VRvoRjwBpzE
    Last edited by Jarek; 20th September 2014 at 01:03.

Similar Threads

  1. Is the BWT an FFT-style transform?
    By nburns in forum Data Compression
    Replies: 25
    Last Post: 22nd October 2013, 02:13
  2. A new transform
    By Yaakov Gringeler in forum Data Compression
    Replies: 6
    Last Post: 28th January 2013, 15:55
  3. Schindler Transform (STX)
    By CUDALIKE in forum Data Compression
    Replies: 15
    Last Post: 29th November 2011, 00:40
  4. SCOTT TRANSFORM
    By biject.bwts in forum Data Compression
    Replies: 34
    Last Post: 14th August 2011, 05:26
  5. a very simple transform for english.dic
    By willvarfar in forum Data Compression
    Replies: 8
    Last Post: 1st March 2010, 15:44

Posting Permissions

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