codetree.c

SPIHT 源代码

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

//      V E C T O R - T R E E   I M A G E   C O M P R E S S I O N

// = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =
//           > > > >    C++ version  7.10  -  06/25/95   < < < <

// Amir Said - [e-mail]
// University of Campinas (UNICAMP)
// Campinas, SP 13081, Brazil

// William A. Pearlman - [e-mail]
// Rensselaer Polytechnic Institute
// Troy, NY 12180, USA

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

// Copyright (c) 1995 Amir Said & William A. Pearlman

// This program is Copyright (c) by Amir Said & William A. Pearlman.
// It may be freely redistributed in its entirety provided that this
// copyright notice is not removed. It may not be sold for profit or
// incorporated in commercial programs without the written permission
// of the copyright holders. This program is provided as is, without any
// express or implied warranty, without even the warranty of fitness
// for a particular purpose.


// - - Inclusion - - - - - - - - - - - - - - - - - - - - - - - - - - - -

#include "general.h"
#include "image_bw.h"

#ifdef BINCODE
#include "bincode.h"
#else
#include "aritcode.h"
#endif


// - - Definitions - - - - - - - - - - - - - - - - - - - - - - - - - - -

struct Tree_Node
{
  Image_Coord coord;
  long state;
  Tree_Node * next;
};


// - - Static variables  - - - - - - - - - - - - - - - - - - - - - - - -

const int SHF_x[4] = { 0, 0, 1, 1 }, SHF_y[4] = { 0, 1, 0, 1 };

char names[3][80], * pic_f_name = names[0], * cod_f_name = names[1],
      * new_f_name = names[2];

Chronometer code_time, total_time;

int pel_bytes, threshold_bits, min_bits, pyramid_levels, smoothing,
    mean, mean_shift;

long byte_budget, root_code;

Pel_Type act_value, threshold;

float bit_rate, rate_mult;

Tree_Node * LISP_head, * LISP_end;

Image_Coord dimension, pyramid_dim, root_dim;

Image_BW image;

#ifdef ENCODER

  Encoder data_file;

  Image_BW max_image;

#else

  Decoder data_file;

#endif

#ifndef BINCODE

  Adaptive_Model group_model[5], node_model[34], desc_model[34];

#endif

#ifndef LOSSLESS

  Image_Coord LSP_dim;

  int LSP_plane, LSP_part, LSP_idx;

  float bias_const_1, bias_const_2, bias[32];

  float * LSP_mark[32], *** LSP_mtx, ** LSP_ptr;

#endif


// - - Function prototypes - - - - - - - - - - - - - - - - - - - - - - -

boolean Sorting_Pass(void);

boolean Refinement_Pass(void);

void Node_Test(Tree_Node *);

void Desc_Test(Tree_Node *);

#ifndef BINCODE

  int Node_Transition(int, const Image_Coord &, int *);

  int Desc_Transition(int, const Image_Coord &);

#endif

#ifdef LOSSLESS

  void Process_Bits_Left(void);

#endif



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

//  Function Implementations

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

int Max_Levels(int n)
{
  int l1, l2;
  for (l1 = 0; !(n & 1); l1++) n >>= 1;
  for (l2 = l1 - 2; n; l2++) n >>= 1;
  return (l1 < l2 ? l1 : l2) - 1;
}

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

#ifdef LOSSLESS

int Magn_Val(int n, int s)
{ int k;
  if (n < 0) n = -n;
  if (n < 3) return n + s;
  n >>= 2;
  for (int k = 2; n; k++) n >>= 1;
  return k + s;
}

#else
inline float Magn_Val(float & p, int & s) { return fabs(p); }
#endif

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

boolean Sorting_Pass(void)
{
#ifndef LOSSLESS
  act_value = threshold + (bias[LSP_plane] = bias_const_1 * threshold);
#endif

  Tree_Node * prev = LISP_head, * node = prev;

  for (; node = node->next; prev = node)
    if ((node->state & 0x55L) != 0x55L) {
      Node_Test(node);
      if (data_file.bytes_used() >= byte_budget) return true; }

  for (node = prev = LISP_head; node = node->next; prev = node) {
    if ((node->state & 0xAAL) != 0xAAL) {
      Desc_Test(node);
      if (data_file.bytes_used() >= byte_budget) return true; }
#ifndef LOSSLESS
    if ((node->state & 0xFFL) == 0xFFL) {
      if (LISP_end == node) LISP_end = prev;
      prev->next = node->next;  delete node;  node = prev; }
#endif
  }

  return false;
}

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

void Process_Image(void)
{
#ifdef LOSSLESS
  min_bits = 3;
#else
  bias_const_1 = 0.38 - 0.02 * smoothing;
  bias_const_2 = 0.25 + 0.07 * smoothing;
  threshold = pow(2, threshold_bits);  min_bits = -32;
  LSP_idx = LSP_part = LSP_plane = 0;  LSP_ptr = 0;
  LSP_dim.x = pyramid_dim.x >> 2;  LSP_dim.y = pyramid_dim.y << 2;
  NEW_VECTOR(LSP_mtx, LSP_dim.x, float **, "LSP");
#endif

#ifndef BINCODE
  int i, j, k, n = -1, t;
  for (i = 0; i <= 4; i++) {
    group_model[i].set_symbols(2);
    for (j = 0; j <= 4 - i; j++)
      for (k = 0;  k <= 4 - i - j; k++, n++)
        if (n >= 0) {
          if (t = i + k) node_model[n].set_symbols(1 << t);
          if (t = i + j) desc_model[n].set_symbols(1 << t); } }
#endif

  Image_Coord cd;
  Tree_Node * prev, * node;
  NEW_OBJECT(node, Tree_Node, "LISP entry");
  LISP_head = LISP_end = node;

  int m = pyramid_levels;
  root_dim.x = pyramid_dim.x >> m;  root_dim.y = pyramid_dim.y >> m;
  long st = 0x2L + (root_code = long(m + 1) << 9);
  for (cd.x = 0; cd.x < root_dim.x; cd.x += 2)
    for (cd.y = 0; cd.y < root_dim.y; cd.y += 2) {
      NEW_OBJECT(node, Tree_Node, "LISP entry");
      node->coord = cd;  node->state = st;
      LISP_end->next = node;  LISP_end = node; }
  LISP_end->next = NULL;

  for (;--threshold_bits >= min_bits; threshold /= 2) {
    if (Sorting_Pass()) break;
    if (Refinement_Pass()) break; }

#ifdef LOSSLESS
  if ((threshold_bits < min_bits) && (threshold_bits >= 0))
    Process_Bits_Left();
#else
  for (m = LSP_part; m > 0;) delete [] LSP_mtx[--m];
  delete [] LSP_mtx;
#endif
  code_time.stop();

  for (node = LISP_head; node;) {
    prev = node;  node = node->next;  delete prev; }
}


// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
// - - Binary coding functions - - - - - - - - - - - - - - - - - - - - -

#ifdef BINCODE

void Node_Test(Tree_Node * act_node)
{
  int old_st = int(act_node->state), mask = 1;
  Image_Coord nc;
  float * ptr;

  for (int i = 0; i < 4; i++, mask <<= 2)
    if (!(old_st & mask)) {
      nc.x = act_node->coord.x + SHF_x[i];
      nc.y = act_node->coord.y + SHF_y[i];
#ifdef ENCODER
      if (data_file.code_bit(fabs(image[nc]) >= threshold)) {
#else
      if (data_file.decode_bit()) {
#endif
        if (!LSP_idx) {
          NEW_VECTOR(LSP_ptr, LSP_dim.y, float *, "LSP");
          LSP_mtx[LSP_part++] = LSP_ptr;  LSP_idx = LSP_dim.y; }
        LSP_ptr[--LSP_idx] = ptr = image.address(nc);
        act_node->state |= mask;
#ifdef ENCODER
        data_file.code_bit(*ptr < 0);
        *ptr = fabs(*ptr) - threshold; } }
#else
        *ptr = (data_file.decode_bit() ? -act_value : act_value); } }
#endif
}

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

void Desc_Test(Tree_Node * act_node)
{
  Tree_Node * new_node;
  Image_Coord pc = act_node->coord;
  int i, b, mask, old_st = int(act_node->state & 0xFFL);

#ifdef ENCODER
  for (mask = 2, b = i = 0;  i < 4; i++, mask <<= 2)
    if (!(old_st & mask)) {
      if (max_image(pc.x + SHF_x[i], pc.y + SHF_y[i]) >= threshold)
        b |= mask; }
#endif

  if ((old_st & 0xAA) == 0) 
#ifdef ENCODER
    if (data_file.code_bit(b == 0)) return;
#else
    if (data_file.decode_bit()) return;
#endif

  long ns = (act_node->state & 0xFF00L) - 0x200L;
  if (ns < 0x300L) ns |= 0xAAL;
  boolean root = (act_node->state >= root_code);

  for (mask = 2, i = 0; i < 4; i++, mask <<= 2)
    if (!(old_st & mask)) {
#ifdef ENCODER
      if (data_file.code_bit((b & mask) != 0)) {
#else
      if (data_file.decode_bit()) {
#endif
        act_node->state |= long(mask);
        NEW_OBJECT(new_node, Tree_Node, "LISP entry");
        if (root) {
          if (i == 3) ns -= 0x100L;
          new_node->coord.x = pc.x + SHF_x[i] * root_dim.x;
          new_node->coord.y = pc.y + SHF_y[i] * root_dim.y; }
        else {
          new_node->coord.x = (pc.x + SHF_x[i]) << 1;
          new_node->coord.y = (pc.y + SHF_y[i]) << 1; }
        new_node->next = NULL;  new_node->state = ns;
        LISP_end->next = new_node;  LISP_end = new_node;
        Node_Test(new_node); } }
}

#else

// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
// - - Arithmetic coding functions - - - - - - - - - - - - - - - - - - -

void Output_Signs(int nb, int sd, const Image_Coord & pc)
{
  Image_Coord nc;
#ifdef ENCODER
  int m = 1, b = 0;
#else
  int m = 1, b = data_file.decode_bits(nb);
#endif

  for (int i = 0; i < 4; i++, sd >>= 2)
    if (sd & 1) {
    nc.x = pc.x + SHF_x[i];  nc.y = pc.y + SHF_y[i];
#ifdef LOSSLESS
#ifdef ENCODER
      if (image[nc] < 0) b |= m;
#else
      image[nc] = (b & m ? -act_value : act_value);
#endif
#else
      if (!LSP_idx) {
        NEW_VECTOR(LSP_ptr, LSP_dim.y, float *, "LSP");
        LSP_mtx[LSP_part++] = LSP_ptr;  LSP_idx = LSP_dim.y; }
      float * ptr = LSP_ptr[--LSP_idx] = image.address(nc);
#ifdef ENCODER
      if (*ptr < 0) b |= m;
      *ptr = fabs(*ptr) - threshold;
#else
      *ptr = (b & m ? -act_value : act_value);
#endif
#endif
      m <<= 1; }

#ifdef ENCODER
  data_file.code_bits(nb, b);
#endif
}

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

void Desc_Test(Tree_Node * act_node)
{
  Image_Coord pc = act_node->coord;
#ifdef LOSSLESS
  int st_trans = Desc_Transition(int((act_node->state |
    (act_node->state >> 16)) & 0xFFL), pc);
#else
  int st_trans = Desc_Transition(int(act_node->state & 0xFFL), pc);
#endif

  if (!st_trans) return;

  act_node->state |= st_trans;  st_trans >>= 1;

  Tree_Node * new_node;
  long ns = (act_node->state & 0xFF00L) - 0x200L;
  if (ns < 0x300L) ns |= 0xAAL;
  boolean root = ((act_node->state & 0xFF00L) >= root_code);

  for (int i = 0; i < 4; i++, st_trans >>= 2)
    if (st_trans & 0x1) {
      NEW_OBJECT(new_node, Tree_Node, "LISP entry");
      if (root) {
        if (i == 3) ns -= 0x100L;
        new_node->coord.x = pc.x + SHF_x[i] * root_dim.x;
        new_node->coord.y = pc.y + SHF_y[i] * root_dim.y; }
      else {
        new_node->coord.x = (pc.x + SHF_x[i]) << 1;
        new_node->coord.y = (pc.y + SHF_y[i]) << 1; }
      new_node->next = NULL;  new_node->state = ns;
      LISP_end->next = new_node;  LISP_end = new_node;
      Node_Test(new_node); }
}

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

int Node_Transition(int old_st, const Image_Coord & pc, int * signs)
{ int i;
  int st_trans = 0, os = old_st, ps = old_st, mask = 1;
  int msk[3], count[4];

  for (int i = 0; i < 4; i++) count[i] = 0;
  for (i = 0; i < 4; i++, ps >>= 2) ++count[ps&0x3];
  msk[0] = msk[1] = 1;  msk[2] = 1 << count[0];
  int mod = count[2] - count[0] * count[1] - 1 +
    (count[0] * (count[0] * (count[0] - 18) + 107)) / 6 +
    (count[1] * (11 - count[1])) / 2;

#ifdef ENCODER
  int b = 0;
#else
  int b = data_file.decode_symbol(node_model[mod]);
#endif

  for (*signs = i = 0; i < 4; i++, mask <<= 2, os >>= 2) {
    if (old_st & mask) continue;
    ps = os & 0x3;
#ifdef ENCODER
    if (ABS(image(pc.x + SHF_x[i], pc.y + SHF_y[i])) >= threshold) {
      b |= msk[ps];
#else
    if (b & msk[ps]) {
#endif
      st_trans |= mask;  ++(*signs); }
    msk[ps] <<= 1; }

#ifdef ENCODER
  data_file.code_symbol(b, node_model[mod]);
#endif

  return st_trans;
}

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

int Desc_Transition(int old_st, const Image_Coord & pc)
{ int i;
  int os = old_st, ps = os, st_trans = 0, mask = 2;
  int msk[3], count[4];

  for (int i = 0; i < 4; i++) count[i] = 0;
  for (i = 0; i < 4; i++, ps >>= 2) ++count[ps & 0x3];
  msk[0] = 1;  msk[1] = msk[2] = 1 << count[0];
  int mod = count[2] - count[0] * count[1] - 1 +
    (count[0] * (count[0] * (count[0] - 18) + 107)) / 6 +
    (count[1] * (11 - count[1])) / 2;

#ifdef ENCODER
  int b = 0;
#else
  if ((old_st & 0xAA) == 0)
    if (data_file.decode_symbol(group_model[count[0]])) return 0;
  int b = data_file.decode_symbol(desc_model[mod]);
#endif

  for (i = 0; i < 4; i++, mask <<= 2, os >>= 2) {
    if (old_st & mask) continue;
    ps = os & 0x3;
#ifdef ENCODER
#ifdef LOSSLESS
    if (max_image(pc.x + SHF_x[i], pc.y + SHF_y[i]) > threshold_bits) {
#else
    if (max_image(pc.x + SHF_x[i], pc.y + SHF_y[i]) >= threshold) {
#endif
      b |= msk[ps];
#else
    if (b & msk[ps]) {
#endif