codetree.c

SPIHT 源代码

      st_trans |= mask; }
    msk[ps] <<= 1; }

#ifdef ENCODER
  if ((old_st & 0xAA) == 0) {
    data_file.code_symbol(st_trans == 0, group_model[count[0]]);
    if (st_trans == 0) return 0; }
  data_file.code_symbol(b, desc_model[mod]);
#endif

  return st_trans;
}

#endif

// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
// - - Lossless version functions  - - - - - - - - - - - - - - - - - - -

#ifdef LOSSLESS

void Process_Bits(int st, const Image_Coord & pc)
{
  Image_Coord nc;
#ifdef DECODER
  int a, ht = (threshold >> 1) + (threshold == 1);
#endif

  for (int i = 0; i < 4; i++, st >>= 2)
    if (st & 1) {
      nc.x = pc.x + SHF_x[i];  nc.y = pc.y + SHF_y[i];
#ifdef ENCODER
      data_file.code_bit((abs(image[nc]) & threshold) != 0); }
#else
      a = (data_file.decode_bit() ? ht : ht - threshold);
      if (image[nc] < 0) a = -a;
      image[nc] += a; }
#endif
}

// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

void Node_Test(Tree_Node * act_node)
{
  int shift = int((act_node->state & 0xFF00L) >> 9);
  if (threshold_bits < shift) {
    act_node->state |= 0x55L;
    return; }

  threshold = 1 << (threshold_bits - shift);
  int signs, state_trans;
  state_trans = Node_Transition(int(act_node->state & 0xFFL),
    act_node->coord, &signs);

  if (state_trans) {
    act_value = threshold + (threshold >> 1) - (threshold > 1);
    act_node->state |= long(state_trans) << 16;
    Output_Signs(signs, state_trans, act_node->coord); }
}

// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

boolean Refinement_Pass(void)
{
  int node_data, shift;
  Tree_Node * prev = LISP_head, * node = prev;

  for (; node = node->next; prev = node) {

    if (data_file.bytes_used() >= byte_budget) return true;

    shift = int((node->state & 0xFF00L) >> 9);
    if (threshold_bits < shift)
      threshold = 0;
    else {
      threshold = 1 << (threshold_bits - shift);
      if (node_data = int(node->state & 0x55L))
        Process_Bits(node_data, node->coord); }

    node->state |= (node->state & 0xFF0000L) >> 16;
    node->state &= 0xFFFFL;

    if ((threshold <= 1) && ((node->state & 0xAAL) == 0xAAL)) {
      if (LISP_end == node) LISP_end = prev;
      prev->next = node->next;  delete node;  node = prev; } }

  return false;
}

// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

boolean Process_Quadrant(int s, int q, Image_Coord d)
{
  const int NModels = 5;
  Adaptive_Model vl_model[NModels], bt_model[NModels];
  Image_Coord cd, min, max;
  min.x = d.x * SHF_x[q];  min.y = d.y * SHF_y[q];
  max.x = min.x + d.x;   max.y = min.y + d.y;

  threshold = 1 << (s + 1);
  int ht = (threshold >> 1) - (threshold > 1);
  int up, rp1, rp2, ctx, bias = threshold - 1;

  for (int i = 0; i < NModels; i++) {
    vl_model[i].set_symbols(2 * bias + 1);
    bt_model[i].set_symbols(bias + 1); }

  rp1 = rp2 = ctx = 0;
  for (cd.x = min.x; cd.x < max.x; cd.x++) {
    up = cd.x & 1;  cd.y = (up ? min.y : max.y - 1);
    for (;;) {
      if (abs(image[cd]) < threshold)
#ifdef ENCODER
        data_file.code_symbol(image[cd] + bias, vl_model[ctx]);
      else
        data_file.code_symbol(abs(image[cd]) & bias, bt_model[ctx]);
#else
        image[cd] = data_file.decode_symbol(vl_model[ctx]) - bias;
      else
        if (image[cd] < 0)
          image[cd] -= data_file.decode_symbol(bt_model[ctx]) - ht;
        else
          image[cd] += data_file.decode_symbol(bt_model[ctx]) - ht;
#endif

      if (data_file.bytes_used() >= byte_budget) return true;

      rp2 = rp1;  rp1 = Magn_Val(image[cd], 0);
      ctx = Min(NModels - 1, (rp1 + rp2) >> 1);
      if (up) {
        if (++cd.y >= max.y) break; }
      else {
        if (--cd.y < min.y) break; } } }

  return false;
}

// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

void Process_Bits_Left(void)
{
  printf("\n  Switching coding method at rate%5.2f bits/pixel.\n\n",
    rate_mult * data_file.bytes_used());

  Image_Coord d = image.pyramid_dim();
  int l, q, lv = pyramid_levels, shift = lv;
  d.x >>= lv;  d.y >>= lv;

  for (l = lv - 1; l >= 0; l--) {
    for (q = 1; q <= 3; q++) {
      if (shift <= threshold_bits)
        if (Process_Quadrant(threshold_bits - shift, q, d)) return;
      if (q == 2) shift--; }
    d.x <<= 1;  d.y <<= 1; }
}

#else

// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
// - - Lossy version functions - - - - - - - - - - - - - - - - - - - - -

#ifndef BINCODE

void Node_Test(Tree_Node * act_node)
{
  int st_trans, signs;
  st_trans = Node_Transition(int(act_node->state & 0xFFL),
    act_node->coord, &signs);

  if (st_trans) {
    act_node->state |= long(st_trans);
    Output_Signs(signs, st_trans, act_node->coord); }
}

#endif

// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

boolean Refinement_Pass(void)
{
#ifdef DECODER
  float t, ht1, ht2;
#endif
  int b, p, m, n = LSP_plane, k = LSP_dim.y;
  float * ptr, * smk, ** mtx = LSP_mtx[0];

  LSP_mark[LSP_plane++] = (LSP_ptr ? LSP_ptr[LSP_idx] : 0);

  for (m = p = 0; p < n; p++) {
#ifdef DECODER
    t = bias[p];
    bias[p] = threshold * (0.5 - bias_const_2 / Sqr(LSP_plane - p));
    ht1 = bias[p] - t;  ht2 = ht1 + threshold;
#endif
    for (smk = LSP_mark[p], ptr = 0; ptr != smk;) {
      if (!k) {
        mtx = LSP_mtx[++m];  k = LSP_dim.y; }
      ptr = mtx[--k];
#ifdef ENCODER
      if (b = (*ptr >= threshold)) *ptr -= threshold;
      data_file.code_bit(b);
#else
      t = (data_file.decode_bit() ? ht2 : ht1);
      if (*ptr > 0) *ptr += t; else *ptr -= t;
#endif
      if (data_file.bytes_used() >= byte_budget) return true; } }

  return false;
}

#endif


// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
// - - Encoder functions - - - - - - - - - - - - - - - - - - - - - - - -

#ifdef ENCODER

Pel_Type Max_Desc_Val(int l, int s, int x, int y)
{
  Pel_Type t, m = 0;
  Image_Coord ds;
  --l;  --s;
  for (int d = 0; d < 4; d++) {
    ds.x = x + SHF_x[d];  ds.y = y + SHF_y[d];
    t = Magn_Val(image[ds], s);
    if (m < t) m = t;
    if (l > 0) {
      max_image[ds] = t = Max_Desc_Val(l, s, ds.x << 1, ds.y << 1);
      if (m < t) m = t; } }
  return m;
}

// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

int Calc_Max_Image(void)
{
  Image_Coord tc, pc = image.pyramid_dim(), lm = pc;
  int i, sd, lv = pyramid_levels, sp = lv + 1;
  Pel_Type t, max = 0;

  lm.x >>= lv;  lm.y >>= lv;  pc.x >>= 1;  pc.y >>= 1;
  max_image.reset(pc);

  for (pc.x = 0; pc.x < lm.x; pc.x += 2)
    for (pc.y = 0; pc.y < lm.y; pc.y += 2) {
      t = max_image[pc] = Magn_Val(image[pc], sp);
      if (max < t) max = t;
      for (sd = sp, i = 1; i < 4; i++) {
        tc.x = pc.x + SHF_x[i];  tc.y = pc.y + SHF_y[i];
        t = Magn_Val(image[tc], sp);
        if (max < t) max = t;
        if (i == 3) --sd;
        t = max_image[tc] = Max_Desc_Val(lv, sd,
          pc.x + SHF_x[i] * lm.x, pc.y + SHF_y[i] * lm.y);
        if (max < t) max = t; } }

#ifdef LOSSLESS
  return max;
#else
  return int(log(max) / log(2.0));
#endif
}

// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

int main(int numb_arg, char * arg[])
{
  if (numb_arg != 2)
    printf("\n\t* Please read the file `codetree.doc' for "
      "instructions\n\t\tand Copyright/Patent information.\n\t* Use"
      " `%s -u' for command-line usage information\n\n", arg[0]);
  else {
    printf("\n* Usage:\n\n%s image_file coded_file number_lines\n\t"
      "pixels/line bytes/pixel bpp_rate [smoothing]", arg[0]);
#ifdef LOSSLESS
    printf("\n\nFor lossless compression use bpp_rate = 0");
#endif
    puts(" \n");  exit(0); }

  smoothing = 0;
  if ((numb_arg == 7) || (numb_arg == 8)) {
    pic_f_name = arg[1];  cod_f_name = arg[2];
    dimension.x = atoi(arg[3]);  dimension.y = atoi(arg[4]);
    pel_bytes = atoi(arg[5]);
    bit_rate = atof(arg[6]);
    if (numb_arg == 8) smoothing = atoi(arg[7]); }
  else {
    Input_Line("File with original image", pic_f_name);
    Input_Line("File with compressed image", cod_f_name);
    dimension.x = Input_Int("Number of image lines");
    dimension.y = Input_Int("Number of pixels per line");
    pel_bytes = Input_Int("Number of bytes per pixel");
#ifdef LOSSLESS
    bit_rate = Input_Float("Rate (bits/pixel, 0 = lossless)"); }
#else
    bit_rate = Input_Float("Rate (bits/pixel)");
    smoothing = Input_Int("Smoothing (0 = none, 7 = max)"); }
#endif

#ifdef LOSSLESS
  if (bit_rate <= 0) bit_rate = 8;
#endif
  rate_mult = 8.0 / (float(dimension.x) * float(dimension.y));
  if (Max(dimension.x, dimension.y)>8192) Error("Image is too large!");
  byte_budget = long(bit_rate / rate_mult) - 1;

  total_time.start();
  image.read_pic(dimension, pic_f_name, pel_bytes);
  image.transform(smoothing);  pyramid_dim = image.pyramid_dim();
  mean = image.transform_mean();  mean_shift = image.mean_shift();
  pyramid_levels = Min(Max_Levels(pyramid_dim.x),
                       Max_Levels(pyramid_dim.y));

  Chronometer max_time;
  max_time.start("\n  Starting computation of maximum magnitudes...");
  threshold_bits = Calc_Max_Image();
  max_time.display(" Maximum magnitudes computed in");

  data_file.open_file(cod_f_name);
  data_file.code_bits(6, dimension.x >> 8);
  data_file.code_bits(6, dimension.y >> 8);
  data_file.code_bits(8, dimension.x & 0xFF);
  data_file.code_bits(8, dimension.y & 0xFF);
  data_file.code_bits(5, threshold_bits);
  data_file.code_bits(1, pel_bytes - 1);
  data_file.code_bits(3, smoothing);
  data_file.code_bits(4, mean_shift);
  data_file.code_bits(10, mean);

  code_time.start("\n  Starting image compression...");
  Process_Image();
  code_time.display(" Image compressed in");

  data_file.close_file();

  printf("\n  Compressed file size = %ld bytes (%6.3f bits/pixel).\n",
    data_file.bytes_used(), rate_mult * data_file.bytes_used());

  total_time.display("\n  Total execution time (I/O included) =");
  puts(" ");

  return 0;
}


// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
// - - Decoder functions - - - - - - - - - - - - - - - - - - - - - - - -

#else

int main(int numb_arg, char * arg[])
{
  if (numb_arg != 2)
    printf("\n\t* Please read the file `codetree.doc' for "
      "instructions\n\t\tand Copyright/Patent information.\n\t* Use"
      " `%s -u' for command-line usage information\n\n", arg[0]);
  else {
    printf("\n* Usage to compare the recovered image with the original:"
      "\n\n%s  coded_file  original_image  bpp_rate\n", arg[0]);
    printf("\n* Usage to save the recovered image:\n\n%s -s  "
      "coded_file  new_image_file  bpp_rate", arg[0]);
#ifdef LOSSLESS
    printf("\n\nFor lossless recovery use bpp_rate = 0");
#endif
    puts(" \n");  exit(0); }

  FILE * plot_file;
  float mse, psnr, max_rate = 0.0, rate_inc, peak_2 = 0.0;
  boolean cont, comp, interactive, cml;

  if (cml = ((numb_arg == 4) || (numb_arg == 5))) {
    interactive = false;
    if (numb_arg == 4) {
      cod_f_name = arg[1];  pic_f_name = arg[2];
      bit_rate = atof(arg[3]);  comp = true;  peak_2 = 65025.0; }
    else {
      if ((arg[1][0] != '-') || (arg[1][1] != 's'))
        Error("invalid command-line option");
      cod_f_name = arg[2];  new_f_name = arg[3];
      bit_rate = atof(arg[4]);  comp = false; } }
  else {
    interactive = Input_Answer("Interactive mode");
    Input_Line("Name of the compressed image file", cod_f_name);
    comp = !interactive ||
      Input_Answer("Recovered image will be compared to original");
    if (comp)
      Input_Line("File with original image", pic_f_name);
    if (!interactive) {
      plot_file = Open_File("File with rate x PSNR results", "wt");
      bit_rate = Input_Float("First rate (bits/pixel)");
      max_rate = Input_Float("Last rate  (bits/pixel)");
      rate_inc = Input_Float("Rate increment"); } }

  do {

    data_file.open_file(cod_f_name);
    dimension.x = data_file.decode_bits(6) << 8;
    dimension.y = data_file.decode_bits(6) << 8;
    dimension.x += data_file.decode_bits(8);
    dimension.y += data_file.decode_bits(8);
    rate_mult = 8.0 / (float(dimension.x) * float(dimension.y));
    threshold_bits = data_file.decode_bits(5);
    pel_bytes = 1 + data_file.decode_bits(1);
    smoothing = data_file.decode_bits(3);
    mean_shift = data_file.decode_bits(4);
    mean = data_file.decode_bits(10);

    printf("\n  Image size = %d x %d, %d byte(s)/pixel\n",
      dimension.x, dimension.y, pel_bytes);
    if (smoothing)
      printf("  Coded with smoothing factor %d\n", smoothing);
    if (interactive)
#ifdef LOSSLESS
      bit_rate = Input_Float("Code rate (bits/pixel, 0 = lossless)");
#else
      bit_rate = Input_Float("Code rate (bits/pixel)");
#endif

#ifdef LOSSLESS
    if (bit_rate <= 0) bit_rate = 8;
#endif
    byte_budget = long(bit_rate / rate_mult) - 1;

    if (comp && (peak_2 == 0.0))
      peak_2 = (pel_bytes == 1 ? 65025.0 :
        Sqr(Input_Float("Peak value for PSNR computations")));

    code_time.reset();  total_time.reset();  total_time.start();
    image.reset(dimension, pel_bytes, mean, mean_shift, smoothing);
    pyramid_dim = image.pyramid_dim();
    pyramid_levels = Min(Max_Levels(pyramid_dim.x),
                         Max_Levels(pyramid_dim.y));

    code_time.start("\n  Starting image recovery...");
    Process_Image();
    code_time.display(" Image recovered in");

    data_file.close_file();
    image.recover();
    total_time.stop();

    if (comp) {
      printf("\n  Rate =%6.3f bits/pixel --> ", rate_mult *
        data_file.bytes_used());
      mse = image.compare(pic_f_name);
      if (mse > 0.0) {
        psnr = dBW(peak_2 / mse);
        printf("mean squared-error =%8.3f =%7.2f dB PSNR\n",
          mse, psnr); }
      else
        puts("no differences encountered"); }

    total_time.display("\n  Total execution time (I/O included) =");

    if (interactive) {
      if (Input_Answer("Save new image to disk")) {
        Input_Line("Name of the new image file", new_f_name);
        image.write_pic(new_f_name); }
      cont = Input_Answer("Test new rate"); }
    else
      if (cml) {
        if (!comp) image.write_pic(new_f_name);
        cont = false; }
      else {
        fprintf(plot_file, "%9.4f %9.4f\n", bit_rate, psnr);
        bit_rate += rate_inc;
        cont = (bit_rate <= max_rate); }

  } while (cont);

  if (!(cml || interactive)) fclose(plot_file);
  puts(" ");

  return 0;
}

#endif

// = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =

// end of file < CodeTree.C >