subdivide.c

linux下将各类格式图片转换工具

/*
 *  subdivide.c:	Recursive subdivision of range images
 *
 *  Written by:		Ullrich Hafner
 *		
 *  This file is part of FIASCO (獸籸actal 獻籱age 獳籲d 玈籩quence 獵O籨ec)
 *  Copyright (C) 1994-2000 Ullrich Hafner <[e-mail]>
 */

/*
 *  $Date: 2000/07/15 17:59:31 $
 *  $Author: hafner $
 *  $Revision: 5.4 $
 *  $State: Exp $
 */

#include "config.h"

#if HAVE_STRING_H
#	include <string.h>
#else /* not HAVE_STRING_H */
#	include <strings.h>
#endif /* not HAVE_STRING_H */

#include "types.h"
#include "macros.h"
#include "error.h"

#include "image.h"
#include "cwfa.h"
#include "approx.h"
#include "ip.h"
#include "bintree.h"
#include "control.h"
#include "prediction.h"
#include "domain-pool.h"
#include "mwfa.h"
#include "misc.h"
#include "subdivide.h"
#include "list.h"
#include "coeff.h"
#include "wfalib.h"

/*****************************************************************************

				prototypes

*****************************************************************************/

static void
init_new_state (bool_t auxiliary_state, bool_t delta, range_t *range,
		const range_t *child, const int *y_state,
		wfa_t *wfa, coding_t *c);
static void
init_range (range_t *range, const image_t *image, unsigned band,
	    const wfa_t *wfa, coding_t *c);

/*****************************************************************************

				public code
  
*****************************************************************************/

real_t 
subdivide (real_t max_costs, unsigned band, int y_state, range_t *range,
	   wfa_t *wfa, coding_t *c, bool_t prediction, bool_t delta)
/*
 *  Subdivide the current 'range' recursively and decide whether
 *  a linear combination, a recursive subdivision, or a prediction is
 *  the best choice of approximation.
 *  'band' is the current color band, 'y_state' is the corresponding
 *  state of the Y color component (color image compression only).
 *  If 'prediction' is TRUE then also test motion compensation or
 *  nondeterministic approximation.
 *  If 'delta' is TRUE then current range is already predicted.
 *  
 *  Return value:
 *	costs of the best approximation or MAXCOSTS if costs exceed 'max_costs'
 *
 *  Side effects:
 *	'range'	factors and costs of linear combination are modified
 *      'wfa'	new transitions and prediction coefficients are added
 *	'c'	pixels and inner products are updated
 */
{
   real_t    subdivide_costs;        /* Costs arising from approx. the current
				       range with two childs */
   real_t    lincomb_costs;          /* Costs arising from approx. the current
				       range with a linear combination */
   int	     new_y_state [MAXLABELS];	/* Corresponding state of Y */
   real_t    price;			/* Approximation costs multiplier */
   bool_t    try_mc;			/* YES: try MC prediction */
   bool_t    try_nd;			/* YES: try ND prediction */
   unsigned  states;			/* Number of states before the
					   recursive subdivision starts */
   void     *domain_model;		/* copy of domain pool model */      
   void     *d_domain_model;		/* copy of delta domain pool model */
   void     *lc_domain_model;		/* copy of domain pool model */
   void     *lc_d_domain_model;		/* copy of delta domain pool model */
   void	    *coeff_model;	        /* copy of coefficients model */
   void	    *d_coeff_model;		/* copy of delta coefficients model */
   void	    *lc_coeff_model;	        /* copy of coefficients model */
   void	    *lc_d_coeff_model;		/* copy of delta coefficients model */
   tree_t    tree_model;		/* copy of tree model */
   tree_t    p_tree_model;		/* copy of pred. tree model */
   range_t   lrange;			/* range of lin. comb. approx. */
   range_t   rrange;			/* range of recursive approx. */
   range_t   child [MAXLABELS];		/* new childs of the current range */
   static unsigned percent = 0;		/* status of progress meter */

   if (wfa->wfainfo->level == range->level)
      percent = 0;
   
   range->into [0] = NO_EDGE;		/* default approximation: empty */
   range->tree     = RANGE;

   if (range->level < 3)		/* Don't process small ranges */
      return MAXCOSTS;	

   /*
    *  If image permutation (tiling) is performed and the tiling level
    *  is reached then get coordinates of the new block.
    */
   if (c->tiling->exponent
       && range->level == wfa->wfainfo->level - c->tiling->exponent)
   {
      unsigned width, height;		/* size of range (dummies)*/
      
      if (c->tiling->vorder [range->global_address] < 0)
	 return 0;			/* nothing to do */
      else
	 locate_subimage (wfa->wfainfo->level, range->level,
			  c->tiling->vorder [range->global_address],
			  &range->x, &range->y, &width, &height);
   }

   if (range->x >= c->mt->original->width ||
       range->y >= c->mt->original->height)
      return 0;				/* range is not visible */

   /*
    *  Check whether prediction is allowed or not
    *  mc == motion compensation, nd == nondeterminism
    */
   try_mc = (prediction && c->mt->frame_type != I_FRAME			
	     && range->level >= wfa->wfainfo->p_min_level
	     && range->level <= wfa->wfainfo->p_max_level
	     && (range->x + width_of_level (range->level)
		 <= c->mt->original->width)
	     && (range->y + height_of_level (range->level)
		 <= c->mt->original->height));

   try_nd = (prediction && c->mt->frame_type == I_FRAME
	     && range->level >= wfa->wfainfo->p_min_level
	     && range->level <= wfa->wfainfo->p_max_level);

   if (try_mc)
      clear_norms_table (range->level, wfa->wfainfo, c->mt);

   
   /*
    *  Check if current range must be initialized. I.e. range pixels must
    *  be copied from entire image to bintree pixel buffer. Moreover,
    *  all inner products tables must be initialized.
    */
   if (range->level == c->options.lc_max_level)	
      init_range (range, c->mt->original, band, wfa, c);
   
   price = c->price;
   if (band != Y)			
      price *= c->options.chroma_decrease; /* less quality for chroma bands */

   /*
    *  Compute childs of corresponding state in Y band
    */
   if (band != Y)			/* Cb and Cr bands only */
   {
      unsigned label;

      for (label = 0; label < MAXLABELS; label++)
	 if (ischild (y_state))
	    new_y_state [label] = wfa->tree [y_state][label];
	 else
	    new_y_state [label] = RANGE;
   }
   else
      new_y_state [0] = new_y_state [1] = RANGE;
   
   /*
    *  Store contents of all models that may get modified during recursion
    */
   domain_model   = c->domain_pool->model_duplicate (c->domain_pool->model);
   d_domain_model = c->d_domain_pool->model_duplicate (c->d_domain_pool->model);
   coeff_model    = c->coeff->model_duplicate (c->coeff, c->coeff->model);
   d_coeff_model  = c->d_coeff->model_duplicate (c->d_coeff, c->d_coeff->model);
   tree_model     = c->tree;
   p_tree_model   = c->p_tree;
   states         = wfa->states;	
   
   /*
    *  First alternative of range approximation:
    *  Compute costs of linear combination.
    */
   if (range->level <= c->options.lc_max_level) /* range is small enough */
   {
      lrange                 = *range;
      lrange.tree            = RANGE;
      lrange.tree_bits       = tree_bits (LEAF, lrange.level, &c->tree);
      lrange.matrix_bits     = 0;
      lrange.weights_bits    = 0;
      lrange.mv_tree_bits    = try_mc ? 1 : 0; /* mc allowed but not used */
      lrange.mv_coord_bits   = 0;
      lrange.nd_tree_bits    = 0;	
      lrange.nd_weights_bits = 0;	
      lrange.prediction	     = NO;
      
      lincomb_costs
	 = approximate_range (max_costs, price, c->options.max_elements,
			      y_state, &lrange,
			      (delta ? c->d_domain_pool : c->domain_pool),
			      (delta ? c->d_coeff : c->coeff), wfa, c);
   }
   else
      lincomb_costs = MAXCOSTS;		

   /*
    *  Store contents of models that have been modified
    *  by approximate_range () above ...
    */
   lc_domain_model   = c->domain_pool->model;
   lc_d_domain_model = c->d_domain_pool->model;
   lc_coeff_model    = c->coeff->model;
   lc_d_coeff_model  = c->d_coeff->model;
   /*
    *  ... and restore them with values before lc
    */
   c->domain_pool->model   = c->domain_pool->model_duplicate (domain_model);
   c->d_domain_pool->model = c->d_domain_pool->model_duplicate (d_domain_model);
   c->coeff->model         = c->coeff->model_duplicate (c->coeff, coeff_model);
   c->d_coeff->model       = c->d_coeff->model_duplicate (c->d_coeff,
							  d_coeff_model);
   
   /*
    *  Second alternative of range approximation:
    *  Compute costs of recursive subdivision.
    */
   if (range->level > c->options.lc_min_level) /* range is large enough */
   {
      unsigned label;
      
      memset (&child [0], 0, 2 * sizeof (range_t)); /* initialize childs */

      /*
       *  Initialize a new range for recursive approximation
       */
      rrange                 = *range;
      rrange.tree_bits       = tree_bits (CHILD, rrange.level, &c->tree);
      rrange.matrix_bits     = 0;
      rrange.weights_bits    = 0;
      rrange.err             = 0;
      rrange.mv_tree_bits    = try_mc ? 1 : 0;	/* mc allowed but not used */
      rrange.mv_coord_bits   = 0;
      rrange.nd_tree_bits    = try_nd ?
			       tree_bits (CHILD, lrange.level, &c->p_tree): 0;
      rrange.nd_weights_bits = 0;	
      rrange.prediction	     = NO;

      /*
       *  Initialize the cost function and subdivide the current range.
       *  Every child is approximated by a recursive call of subdivide()
       */
      subdivide_costs = (rrange.tree_bits + rrange.weights_bits
			 + rrange.matrix_bits + rrange.mv_tree_bits
			 + rrange.mv_coord_bits + rrange.nd_tree_bits
			 + rrange.nd_weights_bits) * price;
      
      for (label = 0; label < MAXLABELS; label++) 
      {
	 real_t remaining_costs;	/* upper limit for next recursion */
	 
	 child[label].image          = rrange.image * MAXLABELS + label + 1;
	 child[label].address        = rrange.address * MAXLABELS + label;
	 child[label].global_address = rrange.global_address * MAXLABELS
				       + label;
	 child[label].level          = rrange.level - 1;
	 child[label].x	= rrange.level & 1
			  ? rrange.x
			  : (rrange.x
			     + label * width_of_level (rrange.level - 1));
	 child[label].y = rrange.level & 1
			  ? (rrange.y
			     + label * height_of_level (rrange.level - 1))
			  : rrange.y;
	 
	 /* 
	  *  If neccessary compute the inner products of the new states
	  *  (generated during the recursive approximation of child [0])
	  */
	 if (label && rrange.level <= c->options.lc_max_level)
	    compute_ip_images_state (child[label].image, child[label].address,
				     child[label].level, 1, states, wfa, c);
	 /*
	  *  Call subdivide() for both childs. 
	  *  Abort the recursion if 'subdivide_costs' exceed 'lincomb_costs'
	  *  or 'max_costs'.
	  */
	 remaining_costs = min (lincomb_costs, max_costs) - subdivide_costs;

	 if (remaining_costs > 0)	/* still a way for improvement */
	 {
	    subdivide_costs += subdivide (remaining_costs, band,
					  new_y_state [label], &child [label],
					  wfa, c, prediction, delta);
	 }
	 else if (try_mc && child[label].level >= wfa->wfainfo->p_min_level)
	 {
	    fill_norms_table (child[label].x, child[label].y,
			      child[label].level, wfa->wfainfo, c->mt);
	 }
	 
	 if (try_mc)
	    update_norms_table (rrange.level, wfa->wfainfo, c->mt);
	 
	 /*
	  *  Update of progress meter
	  */