ebcot_send_bits.c

JPEG2000 EBCOT算法源码

  optimize_bitstream_layer(the_encoder_ref self, int layer_idx,
                           std_int max_rd_threshold,
                           tag_buffer_ptr tags,
                           int max_cumulative_bytes,
                           int previous_cumulative_bytes,
                           int include_makeup_passes)

 /* This function implements the rate-distortion optimization algorithm.
    It saves the state of any previously generated bit-stream layers and
    then invokes `form_bitstream_layer' as often as necessary to find the
    smallest rate-distortion threshold such that the total number of bytes
    required to represent the layer does not exceed `max_cumulative_bytes'
    minus `previous_cumulative_bytes'.  It then restores the state of any
    previously generated bit-stream layers and returns the threshold.  The
    caller must invoke `form_bitstream_layer' directly with this threshold
    to actually generate the new bit-stream layer.  In the extreme case, this
    function can be used to generate all bit-stream layers.  Normally,
    however, it will be used only to generate a small number of layers which
    are of special interest, while any intervening layers can be generated
    directly from some approximate threshold values.
        If `include_makeup_passes' is non-zero (true), the function sets the
    `makeup_layer' of each code block to the `layer_idx' value and it also
    sets the `makeup_passes' value to reflect any additional coding passes
    which can be included to make up the final rate. */

{
  int comp_idx, n, b, m, actual_bytes;
  level_info_ptr lev;
  band_info_ptr band;
  block_info_ptr block;
  std_int min_rd_threshold, rd_threshold;

  if (layer_idx > 0)
    { /* Start by saving the state of the tag trees. */
      for (comp_idx=0; comp_idx < self->num_components; comp_idx++)
        for (lev=self->components[comp_idx].levels,
             n=self->num_levels; n >= 0; n--, lev++)
          for (b=lev->min_band; b <= lev->max_band; b++)
            {
              band = lev->bands + b;
              band->byte_count_bits_copy = band->byte_count_bits;
              tag_tree__copy(band->inclusion_tree,band->inclusion_tree_copy);
              tag_tree__copy(band->insignificant_msbs_tree,
                             band->insignificant_msbs_tree_copy);
              for (block=band->blocks, m=band->band_blocks;
                   m > 0; m--, block++)
                block->old_passes = block->num_passes;
            }
    }

  /* Estimate `min_rd_threshold' from summary information collected during
     compression. */

  for (n=30; n > 0; n--)
    if (self->master.slope_rates[n] >= max_cumulative_bytes)
      break;
  min_rd_threshold = (std_int)(1<<n);
  if (min_rd_threshold >= max_rd_threshold)
    min_rd_threshold = (min_rd_threshold+1)>>1;

  /* Now for the main iterative loop. */

  rd_threshold = (min_rd_threshold+max_rd_threshold+1)>>1;
  if (rd_threshold > (min_rd_threshold<<1))
    rd_threshold = (min_rd_threshold<<1);
  do {
    actual_bytes = previous_cumulative_bytes;
    for (n=0; n <= self->num_levels; n++)
      for (comp_idx=0; comp_idx < self->num_components; comp_idx++)
        {
          lev = self->components[comp_idx].levels + n;
          if (lev->min_band <= lev->max_band)
            actual_bytes +=
              form_bitstream_layer(lev,rd_threshold,NULL,layer_idx,0,tags);
        }
    if (actual_bytes > max_cumulative_bytes)
      min_rd_threshold = rd_threshold;
    else
      max_rd_threshold = rd_threshold;
    rd_threshold = (min_rd_threshold + max_rd_threshold + 1)>>1;
    if (layer_idx > 0)
      { /* Finish up by restoring the state to that of the previous layer. */
        for (comp_idx=0; comp_idx < self->num_components; comp_idx++)
          for (lev=self->components[comp_idx].levels,
               n=self->num_levels; n >= 0; n--, lev++)
            for (b=lev->min_band; b <= lev->max_band; b++)
              {
                band = lev->bands + b;
                band->byte_count_bits = band->byte_count_bits_copy;
                tag_tree__copy(band->inclusion_tree_copy,band->inclusion_tree);
                tag_tree__copy(band->insignificant_msbs_tree_copy,
                               band->insignificant_msbs_tree);
                for (block=band->blocks, m=band->band_blocks;
                     m > 0; m--, block++)
                  block->num_passes = block->old_passes;
              }
      }
  } while (rd_threshold < max_rd_threshold);

  if (include_makeup_passes)
    {
      int remaining_bytes, new_bytes;

      /* Set up the pass counts for the `rd_threshold' being returned. */

      actual_bytes = previous_cumulative_bytes;
      for (n=0; n <= self->num_levels; n++)
        for (comp_idx=0; comp_idx < self->num_components; comp_idx++)
          {
            lev = self->components[comp_idx].levels + n;
            if (lev->min_band <= lev->max_band)
              actual_bytes +=
                form_bitstream_layer(lev,rd_threshold,NULL,layer_idx,0,tags);
          }

      /* Add makeup passes to absorb any remaining spare bytes. */

      remaining_bytes = max_cumulative_bytes - actual_bytes;
      assert(remaining_bytes >= 0);
      while (remaining_bytes > 0)
        {
          new_bytes = add_best_makeup_pass(self,layer_idx,remaining_bytes);
          if (new_bytes == 0)
            break;
          remaining_bytes -= new_bytes;
        }

      /* Finish up by restoring the state to that of the previous layer. */

      for (comp_idx=0; comp_idx < self->num_components; comp_idx++)
        for (lev=self->components[comp_idx].levels,
             n=self->num_levels; n >= 0; n--, lev++)
          for (b=lev->min_band; b <= lev->max_band; b++)
            {
              band = lev->bands + b;
              band->byte_count_bits = band->byte_count_bits_copy;
              tag_tree__copy(band->inclusion_tree_copy,band->inclusion_tree);
              tag_tree__copy(band->insignificant_msbs_tree_copy,
                             band->insignificant_msbs_tree);
              for (block=band->blocks, m=band->band_blocks;
                   m > 0; m--, block++)
                block->num_passes = block->old_passes;
            }
    }
  return(rd_threshold);
}

/* ========================================================================= */
/* --------------------------- Threshold Estimation ------------------------ */
/* ========================================================================= */

/*****************************************************************************/
/* STATIC                    estimate_layer_threshold                        */
/*****************************************************************************/

static std_int
  estimate_layer_threshold(int target_bytes, std_int *slope_rates,
                           bitstream_layer_info_ptr info)

 /* This function attempts to estimate a rate-distortion threshold which will
    achieve a target number of code bytes close to the supplied `target_bytes'
    value.  It uses information of two types in order to do this.  First,
    the `slope_rates' array contains summary information collected while
    encoding the code blocks (see definition of `block_master' in
    "ebcot_encoder.h" for more information on this).  Secondly, the `info'
    structure contains the rate-distortion threshold and the actual number
    of bytes written to the bit-stream up to and including the last generated
    bit-stream layer. */

{
  int n1, n2;
  double t1, t2, r1, r2, r, t, offset;

  /* Find the smallest index into the `slope_rates' table which yields a
     larger threshold than that used in the last layer. */

  for (n1=29; (n1 >= 0) && ((1<<n1) >= info->rd_threshold); n1--);
  n1++;

  /* Use this point to estimate the offset (in the log-domain) between the
     actual bit-rate and the interpolator estimated bit-rates, where the
     interpolator is taken from `n1' to `n1'-1. */

  if (n1 == 0)
    n1++;
  n2 = n1-1;
  t1 = (double)(1<<n1); r1 = (double)(slope_rates[n1]);
  t2 = (double)(1<<n2); r2 = (double)(slope_rates[n2]);
  r = (double)(info->actual_cumulative_bytes);
  t = (double)(info->rd_threshold);
  if (r1 == 0.0) /* Take care of pathological cases. */
    { r1 += 1.0 + r2; r += 1.0 + r2; r2 += 1.0 + r2; }
  t1 = log(t1); t2 = log(t2); t = log(t);
  r1 = log(r1); r2 = log(r2); r = log(r);
  offset = r - (r1 + (t-t1)*(r2-r1)/(t2-t1));

  /* Now use the offset to correct the target bit-rate. */

  r = (double) target_bytes;
  r = log(r) - offset;
  target_bytes = (int) exp(r);

  /* Now find the two adjacent indices into the `slope_rates' table whose
     rates are closest to the target bit-rate. */

  for (n2=n1; n2 >= 0; n2--)
    if (slope_rates[n2] > target_bytes)
      break;
  if (n2 == 30)
    n2 = 29;
  n1 = n2+1;

  /* Finally, use linear interpolation to estimate the rate-distortion
     threshold. */

  t1 = (double)(1<<n1); r1 = (double)(slope_rates[n1]);
  t2 = (double)(1<<n2); r2 = (double)(slope_rates[n2]);
  if (r1 == 0.0) /* Take care of pathological cases. */
    { r1 += 1.0 + r2; r += 1.0 + r2; r2 += 1.0 + r2; }
  if (r2 == r1)
    r2 += 1.0;
  t1 = log(t1); t2 = log(t2); r1 = log(r1); r2 = log(r2);
  t = t1 + (r-r1)*(t2-t1)/(r2-r1);
  t = exp(t);
  return((std_int) t);
}

/* ========================================================================= */
/* ---------------------------- Start and Finish --------------------------- */
/* ========================================================================= */

/*****************************************************************************/
/* STATIC                   start_bitstream_creation                         */
/*****************************************************************************/

static void
  start_bitstream_creation(the_encoder_ref self)
{
  level_info_ptr lev;
  band_info_ptr band;
  int comp_idx, n, b;

  for (comp_idx=0; comp_idx < self->num_components; comp_idx++)
    for (lev=self->components[comp_idx].levels,
          n=0; n <= self->num_levels; n++, lev++)
      for (b=lev->min_band; b <= lev->max_band; b++)
        {
          band = lev->bands + b;
          band->inclusion_tree =
            create_tag_tree(band->blocks_high,band->blocks_wide);
          band->insignificant_msbs_tree =
            create_tag_tree(band->blocks_high,band->blocks_wide);
          band->inclusion_tree_copy =
            create_tag_tree(band->blocks_high,band->blocks_wide);
          band->insignificant_msbs_tree_copy =
            create_tag_tree(band->blocks_high,band->blocks_wide);
        }
}

/*****************************************************************************/
/* STATIC                  finish_bitstream_creation                         */
/*****************************************************************************/

static void
  finish_bitstream_creation(the_encoder_ref self)
{
  level_info_ptr lev;
  band_info_ptr band;
  int comp_idx, n, b;

  for (comp_idx=0; comp_idx < self->num_components; comp_idx++)
    for (lev=self->components[comp_idx].levels,
          n=0; n <= self->num_levels; n++, lev++)
      for (b=lev->min_band; b <= lev->max_band; b++)
        {
          band = lev->bands + b;
          local_free(band->inclusion_tree);
          local_free(band->insignificant_msbs_tree);
          local_free(band->inclusion_tree_copy);
          local_free(band->insignificant_msbs_tree_copy);
        }
}

/* ========================================================================= */
/* ---------------------------- External Functions ------------------------- */
/* ========================================================================= */

/*****************************************************************************/
/* EXTERN                      ebcot_send_bit_stream                         */
/*****************************************************************************/

void
  ebcot_send_bit_stream(the_encoder_ref self)
{
  std_int rd_threshold;
  int comp_idx, layer_idx, max_bytes, actual_bytes, n, include_makeup_passes;
  bitstream_layer_info_ptr info;
  level_info_ptr lev;
  tag_buffer_ptr tags;
  bitstream_sink_ref output;

  start_bitstream_creation(self);
  tags = create_tag_buffer();
  rd_threshold = 1<<30;
  info = self->layer_info;
  output = self->output;
  if ((self->profile & PROFILE__RESOLUTION_PROGRESSIVE) &&
      (self->bitstream_layers > 1))
    output = NULL; /* Cannot generate the bit-stream at the same time as
                      estimating RD thresholds. */
  actual_bytes = 0;
  for (layer_idx=0; layer_idx < self->bitstream_layers; layer_idx++, info++)
    {
      include_makeup_passes = (layer_idx==(self->bitstream_layers-1));
      max_bytes = info->max_cumulative_bytes;
      if (info->optimize)
        rd_threshold =
          optimize_bitstream_layer(self,layer_idx,rd_threshold,tags,
                                   max_bytes,actual_bytes,
                                   include_makeup_passes);
      else
        {
          assert(layer_idx > 0);
          rd_threshold =
            estimate_layer_threshold(max_bytes,self->master.slope_rates,
                                     info-1);
        }
      for (n=0; n <= self->num_levels; n++)
        for (comp_idx=0; comp_idx < self->num_components; comp_idx++)
          {
            lev = self->components[comp_idx].levels + n;
            if (lev->min_band <= lev->max_band)
              actual_bytes +=
                form_bitstream_layer(lev,rd_threshold,output,layer_idx,
                                     include_makeup_passes,tags);
          }
      info->rd_threshold = rd_threshold;
      info->actual_cumulative_bytes = actual_bytes;
    }

  /* The bit-stream might not yet have been generated. */

  if (output == NULL)
    {
      assert(self->profile & PROFILE__RESOLUTION_PROGRESSIVE);
      output = self->output;
      actual_bytes = 0;
      for (n=0; n <= self->num_levels; n++)
        for (comp_idx=0; comp_idx < self->num_components; comp_idx++)
          {
            lev = self->components[comp_idx].levels + n;
            if (lev->min_band <= lev->max_band)
              for (info=self->layer_info, layer_idx=0;
                   layer_idx < self->bitstream_layers; layer_idx++, info++)
                {
                  include_makeup_passes =
                    (layer_idx==(self->bitstream_layers-1));
                  rd_threshold = info->rd_threshold;
                  actual_bytes +=
                    form_bitstream_layer(lev,rd_threshold,output,layer_idx,
                                         include_makeup_passes,tags);
                }
          }
    }

  tag_buffer__destroy(tags);
  finish_bitstream_creation(self);
}