codecolr.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  1.04  -  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_3c.h"
#include "aritcode.h"


// - - 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 LSP_plane, LSP_part, LSP_idx, threshold_bits, pyramid_levels;

int mean[3], transf_matrix[3][3];

long byte_budget, root_code;

float act_value, threshold, bit_rate, rate_mult;

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

Tree_Node * LISP_head, * LISP_end;

Image_Coord dimension, pyramid_dim, root_dim, LSP_dim;

Image_3C image;

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

#ifdef ENCODER

  Encoder data_file;

  Image_3C max_image;

#else

  Decoder data_file;

#endif


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

//  Function Implementations

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

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 (fabs(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
    if (max_image(pc.x + SHF_x[i], pc.y + SHF_y[i]) >= threshold) {
      b |= msk[ps];
#else
    if (b & msk[ps]) {
#endif
      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;
}

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

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 ENCODER
      if (image[nc] < 0) b |= m;
#else
      image[nc] = (b & m ? -act_value : act_value);
#endif
      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
      m <<= 1; }

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

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

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); }
}

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

void Desc_Test(Tree_Node * act_node)
{
  Image_Coord pc = act_node->coord;
  int st_trans = Desc_Transition(int(act_node->state & 0xFFL), pc);

  if (!st_trans) return;

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

  Tree_Node * new_node;
  long ns = (act_node->state & 0xFFF00L) - 0x2000L;
  if (ns < 0x3000L) ns |= 0xAAL;
  boolean root = ((act_node->state & 0xFF000) >= 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 -= 0x1000L;
        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 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;
}

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

boolean Sorting_Pass(void)
{
  int color;
  Tree_Node * prev = LISP_head, * node = prev;

  act_value = threshold + (bias[LSP_plane] = 0.38 * threshold);

  for (; node = node->next; prev = node)
    if ((node->state & 0x55L) != 0x55L) {
      color = int(node->state >> 8) & 0x3;
      image.set_color(color);
      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) {
      color = int(node->state >> 8) & 0x3;
      image.set_color(color);
#ifdef ENCODER
      max_image.set_color(color);
#endif
      Desc_Test(node);
      if (data_file.bytes_used() >= byte_budget) return true; }
    if ((node->state & 0xFFL) == 0xFFL) {
      if (LISP_end == node) LISP_end = prev;
      prev->next = node->next;  delete node;  node = prev; } }

  return false;
}

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

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 - 0.25 / Sqr(LSP_plane - p));
    ht1 = bias[p] - t;  ht2 = ht1 + threshold;