2dheap.c

一种新的机遇小波变换的压缩存储方法

#include "gwic.h"

/* Construct 2D significance heap */
heap2d *gen_2d_heap(U32 *buf, int width, int height, int levels)
{
  int c1,c2,c3,c4,c,size,h,i,j,k,l,m,w,lev,b,t;
  heap2d *heap;
  BYTE *p;
  int n=0;

  MALLOC(heap,sizeof(heap2d));

  for(size=0, i=1; i<=levels; i++) size += (width>>i)*(height>>i);
  size += (width>>levels)*(height>>levels);
  
  /* Allocate and initialize heap structure */
  MALLOC(heap->heap,size+1);
  MALLOC(heap->lines,(height*sizeof(U32 *)));
  heap->width = width; 
  heap->height = height;
  heap->levels = levels;
  h = height>>levels; 
  w = width>>levels;
  i = h<<1;
  p = heap->heap;
  for(j=0; j<height; j++)
  {
    *(heap->lines+j) = p;
    if (j>=i) {h = h << 1;  w = w << 1;  i += h;}
    p += w;
  }

  /* Prepare the bottom level */
   w = width>>1; h=height>>1; k=h*width;
   for(j=0; j<h; j++) for(i=0; i<w; i++) {
     l = i+j*width;
     c1 = *(buf+w+l) & MASK;
     c2 = *(buf+k+l) & MASK;
     c3 = *(buf+w+k+l) & MASK;
     c = c1>c2 ? (c1>c3?c1:c3) : (c2>c3?c2:c3);
     for(l=0;c>0;l++,c=c>>1); 
     *(*(heap->lines+h+j) + i) = l;
   }
  
   /* Prepare the middle levels */
   for (lev=1; lev < levels; lev++) {
     w = width>>(lev+1); h=height>>(lev+1); k=h*width;
     for(j=0; j<h; j++) for(i=0; i<w; i++) {
       l = i+j*width;
       c1 = *(buf+w+l) & MASK;
       c2 = *(buf+k+l) & MASK;
       c3 = *(buf+w+k+l) & MASK;
       c = c1>c2 ? (c1>c3?c1:c3) : (c2>c3?c2:c3);
       for(l=0;c>0;l++,c=c>>1); c=l;
       l = *(*(heap->lines +(h<<1)+ (j<<1)) + (i<<1)); if(l>c)c=l;
       l = *(*(heap->lines +(h<<1)+ (j<<1)) + (i<<1)+1); if(l>c)c=l;
       l = *(*(heap->lines +(h<<1)+ (j<<1)+1) + (i<<1)); if(l>c)c=l;
       l = *(*(heap->lines +(h<<1)+ (j<<1)+1) + (i<<1)+1); if(l>c)c=l;
       *(*(heap->lines+h+j) + i) = c;
     }
   }

   /* Prepare the top level */
   w = width>>levels; h=height>>levels; k=h*width;
   for(j=0; j<h; j++) for(i=0; i<w; i++) {
     c = *(buf+i+j*width) & MASK;
       for(l=0;c>0;l++,c=c>>1); c=l;
       l = *(*(heap->lines+h+j)+i);
       *(*(heap->lines+j) + i) = l>c ? l : c;
   }
  
  /* Calculate max n */
  h = height>>levels; w = width>>levels;
  for (j=0; j<h; j++) for (i=0; i<w; i++) 
    n = n > *(*(heap->lines+j)+i) ? n : *(*(heap->lines+j)+i);
  heap->max = n;

  return(heap);
}