spiht.c

该源码是SPIHT即分层树集合划分算法的c代码,希望对搞压缩编码的朋友们有用.

  int offspring_row[4];
  int offspring_col[4];
  int num_offspring;
  int offspring;
  int return_value;
  
  num_offspring = 
    QccSPIHTGetOffspring(subband_pyramid,
			 row, col,
			 offspring_row, offspring_col,
			 block_size);
  
  if (!num_offspring)
    return(-1);
  
  for (offspring = 0; offspring < num_offspring; offspring++)
    if ((return_value = 
	 QccSPIHTDescendantsSignificance(subband_pyramid,
					 offspring_row[offspring],
					 offspring_col[offspring],
					 threshold,
					 block_size)))
      return(return_value);
  
  return(0);
}


static int QccSPIHTInputOutputRefinementBit(QccWAVSubbandPyramid
					    *subband_pyramid,
					    QccBitBuffer *buffer,
					    double threshold,
					    QccSPIHTCoefficientBlock
					    *coefficient,
					    int method,
					    QccENTArithmeticModel *model,
					    int target_bit_cnt)
{
  int bit;

  if (method == QCCSPIHT_ENCODE)
    {
      bit = 
	(subband_pyramid->matrix[coefficient->row][coefficient->col] >=
	 threshold);
      
      if (bit)
	subband_pyramid->matrix[coefficient->row][coefficient->col] -=
	  threshold;
    }
  
  model->current_context = QCCSPIHT_REFINEMENT_CONTEXT;

  if (QccSPIHTInputOutput(buffer, &bit, method, model, target_bit_cnt))
    {
      QccErrorAddMessage("(QccSPIHTInputOutputRefinementBit): Error calling QccSPIHTInputOutput()");
      return(2);
    }
  
  if (method == QCCSPIHT_DECODE)
    subband_pyramid->matrix[coefficient->row][coefficient->col] +=
      (bit) ? (threshold / 2) : (-threshold / 2);
  
  return(0);
}


static int QccSPIHTUpdateState(int state, int bit, int row, int col,
			       int block_size)
{
  int mask = 0;

  if (bit)
    {
      mask = 1 << (row * block_size + col);
      state |= mask;
    }

  return(state);
}


static int QccSPIHTIsSignificant(int state, int row, int col,
				 int block_size)
{
  int mask = 0;

  mask = 1 << (row * block_size + col);

  return(state & mask);
}


static int QccSPIHTInputOutputSignificanceBits(QccWAVSubbandPyramid
					       *subband_pyramid,
					       QccBitBuffer *buffer,
					       QccSPIHTCoefficientBlock
					       *coefficient_block,
					       double threshold,
					       int method,
					       QccENTArithmeticModel *model,
					       int target_bit_cnt,
					       int block_size)
{
  int base_row, base_col;
  int row, col;
  int bit;
  int mask;
  int symbol = 0;
  int old_state;

  base_row = coefficient_block->row;
  base_col = coefficient_block->col;
  old_state = coefficient_block->state;

  if (model == NULL)
    {
      for (row = 0; row < block_size; row++)
	for (col = 0; col < block_size; col++)
	  if (!QccSPIHTIsSignificant(old_state, row, col, block_size))
	    {
	      if (method == QCCSPIHT_ENCODE)
		bit =
		  subband_pyramid->matrix[base_row + row][base_col + col] >=
		  threshold;
	      if (QccSPIHTInputOutput(buffer, &bit, method, model,
				      target_bit_cnt))
		{
		  QccErrorAddMessage("(QccSPIHTInputOutputSignificanceBits): Error calling QccSPIHTInputOutput()");
		  return(2);
		}
	      coefficient_block->state =
		QccSPIHTUpdateState(coefficient_block->state, bit, row, col,
				    block_size);
	    }
    }
  else
    {
      if (method == QCCSPIHT_ENCODE)
	for (row = 0, mask = 1; row < block_size; row++)
	  for (col = 0; col < block_size; col++)
	    if (!QccSPIHTIsSignificant(old_state, row, col, block_size))
	      {
		bit =
		  subband_pyramid->matrix[base_row + row][base_col + col] >=
		  threshold;
		if (bit)
		  symbol |= mask;
		coefficient_block->state =
		  QccSPIHTUpdateState(coefficient_block->state, bit, row, col,
				      block_size);

		mask <<= 1;
	      }
      
      if (QccSPIHTInputOutput(buffer, &symbol, method, model, target_bit_cnt))
	{
	  QccErrorAddMessage("(QccSPIHTInputOutputSignificanceBits): Error calling QccSPIHTInputOutput()");
	  return(2);
	}

      if (method == QCCSPIHT_DECODE)
	for (row = 0, mask = 1; row < block_size; row++)
	  for (col = 0; col < block_size; col++)
	    if (!QccSPIHTIsSignificant(old_state, row, col, block_size))
	      {
		bit =
		  symbol & mask;
		coefficient_block->state =
		  QccSPIHTUpdateState(coefficient_block->state, bit, row, col,
				      block_size);
		mask <<= 1;
	      }
      
    }

  return(0);
}


static int QccSPIHTAddNodeToLSP(QccList *LSP,
				int row,
				int col,
				QccWAVSubbandPyramid *subband_pyramid,
				double threshold,
				int **sign_array,
				QccBitBuffer *buffer,
				int method,
				QccENTArithmeticModel *model,
				int target_bit_cnt)
{
  QccSPIHTCoefficientBlock coefficient_block;
  QccListNode *new_node = NULL;
  
  coefficient_block.row = row;
  coefficient_block.col = col;
  coefficient_block.type = QCCSPIHT_TYPE_A;
  coefficient_block.state = 0;

  if ((new_node =
       QccListCreateNode(sizeof(QccSPIHTCoefficientBlock),
			 (void *)(&coefficient_block))) == NULL)
    {
      QccErrorAddMessage("(QccSPIHTAddNodeToLSP): Error calling QccListCreateNode()");
      return(1);
    }

  if (QccListAppendNode(LSP, new_node))
    {
      QccErrorAddMessage("(QccSPIHTAddNodeToLSP): Error calling QccListAppendNode()");
      return(1);
    }

  model->current_context = QCCSPIHT_SIGN_CONTEXT;

  if (QccSPIHTInputOutput(buffer,
			  &sign_array[row][col],
			  method,
			  model,
			  target_bit_cnt))
    {
      QccErrorAddMessage("(QccSPIHTAddNodeToLSP): Error calling QccSPIHTInputOutput()");
      return(2);
    }

  if (method == QCCSPIHT_ENCODE)
    subband_pyramid->matrix[row][col] -= threshold;
  else
    subband_pyramid->matrix[row][col] = 1.5 * threshold;

  return(0);
}


static int QccSPIHTTypeA(QccWAVSubbandPyramid
			 *subband_pyramid,
			 int **sign_array,
			 QccBitBuffer *buffer,
			 QccSPIHTCoefficientBlock *coefficient_block,
			 QccListNode *current_list_node,
			 double threshold,
			 QccList *LSP,
			 QccList *LIP,
			 QccList *LIS,
			 int method,
			 QccENTArithmeticModel *model,
			 int target_bit_cnt,
			 int block_size)
{
  int base_row, base_col;
  QccSPIHTCoefficientBlock new_coefficient_block;
  QccListNode *new_node = NULL;
  int bit;
  int offspring_row[4];
  int offspring_col[4];
  int num_offspring;
  int offspring;
  int new_state;
  int cnt;
  int row, col;
  int return_value;

  base_row = coefficient_block->row;
  base_col = coefficient_block->col;

  if (method == QCCSPIHT_ENCODE)
    {
      bit = QccSPIHTDescendantsSignificance(subband_pyramid,
					    base_row, base_col,
					    threshold,
					    block_size);
      
      if (bit == -1)
	return(0);
    }
  
  model->current_context =
    QCCSPIHT_LIS_TYPEA_CONTEXT + coefficient_block->state;

  if (QccSPIHTInputOutput(buffer, &bit, method, model, target_bit_cnt))
    {
      QccErrorAddMessage("(QccSPIHTTypeA): Error calling QccSPIHTInputOutput()");
      return(2);
    }
  
  if (!bit)
    return(0);
  
  num_offspring = 
    QccSPIHTGetOffspring(subband_pyramid,
			 base_row, base_col,
			 offspring_row,
			 offspring_col,
			 block_size);
  
  for (offspring = 0; offspring < num_offspring; offspring++)
    {
      new_coefficient_block.row = 
	offspring_row[offspring];
      new_coefficient_block.col = 
	offspring_col[offspring];
      new_coefficient_block.type = 
	QCCSPIHT_TYPE_A;
      new_coefficient_block.state = 0;

      model->current_context =
	QCCSPIHT_LIS_TYPEA_OFFSPRING_CONTEXT + coefficient_block->state;

      if (QccSPIHTInputOutputSignificanceBits(subband_pyramid,
					      buffer,
					      &new_coefficient_block,
					      threshold,
					      method,
					      model,
					      target_bit_cnt,
					      block_size))
	{
	  QccErrorAddMessage("(QccSPIHTTypeA): Error calling QccSPIHTInputOutputSignificanceBits()");
	  return(2);
	}

      new_state = new_coefficient_block.state;

      cnt = 0;
      for (row = 0; row < block_size; row++)
	for (col = 0; col < block_size; col++)
	  if (QccSPIHTIsSignificant(new_state, row, col, block_size))
	    {
	      cnt++;
	      if ((return_value =
		   QccSPIHTAddNodeToLSP(LSP,
					offspring_row[offspring] + row,
					offspring_col[offspring] + col,
					subband_pyramid,
					threshold,
					sign_array,
					buffer,
					method,
					model,
					target_bit_cnt)))
		{
		  QccErrorAddMessage("(QccSPIHTTypeA): Error calling QccSPIHTAddNodeToLSP()");
		  return(return_value);
		}
	    }

      if (cnt != block_size * block_size)
	{
	  if ((new_node =
	       QccListCreateNode(sizeof(QccSPIHTCoefficientBlock),
				 (void *)(&new_coefficient_block))) == NULL)
	    {
	      QccErrorAddMessage("(QccSPIHTTypeA): Error calling QccListCreateNode()");
	      return(1);
	    }

	  if (QccListAppendNode(LIP, new_node))
	    {
	      QccErrorAddMessage("(QccSPIHTTypeA): Error calling QccListAppendNode()");
	      return(1);
	    }
	}
    }
  
  if (QccListRemoveNode(LIS, current_list_node))
    {
      QccErrorAddMessage("(QccSPIHTTypeA): Error calling QccListRemoveNode()");
      return(1);
    }

  if (QccSPIHTGetOffspring(subband_pyramid,
			   offspring_row[0], offspring_col[0],
			   offspring_row, offspring_col,
			   block_size))
    {
      coefficient_block->type = QCCSPIHT_TYPE_B;
      
      if (QccListAppendNode(LIS, current_list_node))
	{
	  QccErrorAddMessage("(QccSPIHTTypeA): Error calling QccListAppendNode()");
	  return(1);
	}
    }
  
  return(0);
}


static int QccSPIHTTypeB(QccWAVSubbandPyramid *subband_pyramid,
			 int **sign_array,
			 QccBitBuffer *buffer,
			 QccSPIHTCoefficientBlock *coefficient_block,
			 QccListNode *current_list_node,
			 double threshold,
			 QccList *LIS,
			 int method,
			 QccENTArithmeticModel *model,
			 int target_bit_cnt,
			 int block_size)
{
  int bit;
  int offspring_row[4];
  int offspring_col[4];
  int num_offspring;
  int offspring;
  QccSPIHTCoefficientBlock new_coefficient_block;
  QccListNode *new_node;
  
  if (method == QCCSPIHT_ENCODE)
    {
      bit = QccSPIHTLSignificance(subband_pyramid,
				  coefficient_block->row,
				  coefficient_block->col,
				  threshold,
				  block_size);
      
      if (bit == -1)
	return(0);
    }      

  model->current_context = 
    QCCSPIHT_LIS_TYPEB_CONTEXT + coefficient_block->state;

  if (QccSPIHTInputOutput(buffer, &bit, method, model, target_bit_cnt))
    {
      QccErrorAddMessage("(QccSPIHTTypeB): Error calling QccSPIHTInputOutput()");
      return(2);
    }
  
  if (!bit)
    return(0);
  
  num_offspring = QccSPIHTGetOffspring(subband_pyramid,
				       coefficient_block->row,
				       coefficient_block->col,
				       offspring_row,
				       offspring_col,
				       block_size);
  
  for (offspring = 0; offspring < num_offspring; offspring++)
    {
      new_coefficient_block.row = 
	offspring_row[offspring];
      new_coefficient_block.col = 
	offspring_col[offspring];
      new_coefficient_block.type = 
	QCCSPIHT_TYPE_A;
      new_coefficient_block.state = 0;

      if ((new_node =
	   QccListCreateNode(sizeof(QccSPIHTCoefficientBlock),
			     (void *)(&new_coefficient_block))) == NULL)
	{
	  QccErrorAddMessage("(QccSPIHTTypeB): Error calling QccListCreateNode()");
	  return(1);
	}
      if (QccListAppendNode(LIS, new_node))
	{
	  QccErrorAddMessage("(QccSPIHTTypeB): Error calling QccListAppendNode()");
	  return(1);
	}
    }

  if (QccListDeleteNode(LIS, current_list_node))
    {
      QccErrorAddMessage("(QccSPIHTTypeB): Error calling QccListDeleteNode()");
      return(1);
    }
  
  return(0);
}


static int QccSPIHTSortingPass(QccWAVSubbandPyramid *subband_pyramid,
			       int **sign_array,
			       QccBitBuffer *buffer,
			       double threshold,
			       QccList *LSP,
			       QccList *LIP,
			       QccList *LIS,
			       int method,
			       QccENTArithmeticModel *model,
			       int target_bit_cnt,
			       int block_size)
{
  int return_value;
  int old_state;
  int new_state;
  int row, col;
  int cnt;
  int base_row, base_col;
  QccSPIHTCoefficientBlock *current_coefficient_block;
  QccListNode *current_list_node;
  QccListNode *next_list_node;
  
  current_list_node = LIP->start;
  while (current_list_node != NULL)
    {
      next_list_node = current_list_node->next;
      
      current_coefficient_block =
	QccSPIHTGetCoefficientBlockFromNode(current_list_node);

      old_state = current_coefficient_block->state;

      model->current_context =
	QCCSPIHT_LIP_CONTEXT + old_state;
  
      if (QccSPIHTInputOutputSignificanceBits(subband_pyramid,
					      buffer,
					      current_coefficient_block,
					      threshold,
					      method,
					      model,
					      target_bit_cnt,
					      block_size))
	{
	  QccErrorAddMessage("(QccSPIHTSortingPass): Error calling QccSPIHTInputOutputSignificanceBits()");
	  return(2);
	}

      new_state = current_coefficient_block->state;
      
      base_row = current_coefficient_block->row;
      base_col = current_coefficient_block->col;
      cnt = 0;
      for (row = 0; row < block_size; row++)
	for (col = 0; col < block_size; col++)
	  if (QccSPIHTIsSignificant(new_state, row, col, block_size))
	    {
	      cnt++;
	      if (!QccSPIHTIsSignificant(old_state, row, col, block_size))
		{
		  if ((return_value = QccSPIHTAddNodeToLSP(LSP,
							   base_row + row,
							   base_col + col,
							   subband_pyramid,
							   threshold,
							   sign_array,
							   buffer,
							   method,
							   model,
							   target_bit_cnt)))
		    {
		      QccErrorAddMessage("(QccSPIHTSortingPass): Error calling QccSPIHTAddNodeToLSP()");
		      return(return_value);
		    }
		}
	    }

      if (cnt == block_size * block_size)
	if (QccListRemoveNode(LIP, current_list_node))
	  {
	    QccErrorAddMessage("(QccSPIHTSortingPass): Error calling QccListRemoveNode()");
	    return(1);
	  }
      
      current_list_node = next_list_node;
    }
  
  current_list_node = LIS->start;
  while (current_list_node != NULL)
    {
      next_list_node = current_list_node->next;
      
      current_coefficient_block =