hplx_vert_analysis_by_lifting.c

JPEG2000实现的源码

/*****************************************************************************/
/* Copyright 1998, Hewlett-Packard Company                                   */
/* All rights reserved                                                       */
/* File: "hplx_vert_analysis_by_lifting.c"                                   */
/* Description: Implementation of the `hplx_analysis_stage' object for       */
/*              vertical analysis via lifting.                               */
/* Author: David Taubman                                                     */
/* Affiliation: Hewlett-Packard and                                          */
/*              The University of New South Wales, Australia                 */
/* Acknowledgements: Partly developed in collaboration with                  */
/*                   Christos Chrysafis of HP Labs                           */
/* Version: VM9.0                                                            */
/* Last Revised: 20 April, 2001                                              */
/*****************************************************************************/

/*****************************************************************************/
/* Modifications tagged with comment lines or delimiters involving the       */
/* string, "David T mod" or "mod by David T", have been made by David        */
/* Taubman; they are copyrighted by Hewlett-Packard Company with all rights  */
/* reserved for the modified parts.                                          */
/*****************************************************************************/

/*****************************************************************************/
/* Modifications tagged with comment lines or delimiters involving the       */
/* string "BBDWT mod" have been made to implement the single-sample          */
/* overlap Wavelet transform within the frames paradigm -- this is the       */
/* BBDWT transform proposed by Canon Research France and accepted at the     */
/* meeting in Seoul, Korea.                                                  */
/*****************************************************************************/

/*****************************************************************************/
/* Modifications marked "Christos Chrysafis (HPL)" made to ensure that       */
/* the boundary extension policy for lifting is identical to that used for   */
/* convolution so that convolution vs. lifting is purely an implementation   */
/* decision.  Mods might cause problems for non-symmetric kernels, but that  */
/* should not be relevant to the standard.  The modifications are            */
/* copyrighted by Hewlett-Packard Company with all rights reserved for the   */
/* modified parts.                                                           */
/*****************************************************************************/

/*****************************************************************************/
/* Modified by David Taubman to support arbitrary reference points for the   */
/* transform and the various regular partitions, so as to facilitate         */
/* cropping and geometric transformations in the compressed domain and to    */
/* enable full support for CRF's single-sample overlap Wavelet transform,    */
/* as originally documented in Seoul.  Changes are too numerous to flag      */
/* individually within the code.  Changes copyrighted by HP with all rights  */
/* reserved for the modified parts.                                          */
/*****************************************************************************/

/*****************************************************************************/
/* Modified by David Taubman to support interface modifications, arbitrary   */
/* changes in coding parameters from component to component and from tile    */
/* to tile, to support the full generality of PART-1 of the JPEG2000         */
/* standard, and to support most anticipated generality of PART-2.  Changes  */
/* are too numerous to flag individually within the code, which in some      */
/* places has been completely rewritten.  All changes copyrighted by HP with */
/* all rights reserved for the modified parts.                               */
/*****************************************************************************/

/*****************************************************************************/
/* Modified by David Taubman to allow SSO-DWT style extension at tile        */
/* boundaries.  Changes copyrighted by HP with all rights reserved for the   */
/* modified parts.                                                           */
/*****************************************************************************/

/*****************************************************************************/
/* Modified for general wavelet decompositions.                              */
/* Copyright 2000 Science Applications International Corporation (SAIC).     */
/* Copyright 1995 University of Arizona, Arizona Board of Regents.           */
/* All Rights Reserved for modified parts.                                   */
/*****************************************************************************/

#include <local_services.h>
#include <string.h>
#include <math.h>
#include <assert.h>
#include <ifc.h>
#include "hplx_vert_lifting.h"
#include "hplx_analysis_local.h"

/* ========================================================================= */
/* ------------------------ Extended Object Definition --------------------- */
/* ========================================================================= */

/*****************************************************************************/
/*                     hplx_vert_analysis_by_lifting_obj                     */
/*****************************************************************************/

typedef
  struct hplx_vert_analysis_by_lifting_obj {
    hplx_analysis_stage_obj base;
    int kernel_type;
    int num_steps;
    hplx_lifting_step_ptr steps;
    int num_buffering_stages;
    hplx_buffering_stage_ptr buffering_stages;
    hplx_buffering_stage_ptr branch_output_stages[2];
    int branch_next_row_idx[2];
    int branch_needs_scaling[2]; /* Only for float-lifting. */
    float branch_scale[2]; /* Only for float-lifting. */
    hplx_row_buffer_heap heap;
    int num_frames, frame_rows, frame_ref, frame_idx, first_frame_rows;
    int current_frame_rows, first_row_idx_in_frame;
    int rows_left_in_tile, rows_left_in_frame;
    int ovlp_top, ovlp_bottom;
  } hplx_vert_analysis_by_lifting_obj, *hplx_vert_analysis_by_lifting_ref;
  /* This structure defines the extended `hplx_analysis_stage' object.
         `kernel_type' is one of INFO__FLOAT_LIFTING or INFO__INT_LIFTING.
         `num_steps' identifies the number of lifting steps.
         `steps' points to an array with `num_steps' entries, which describes
     each of the lifting steps.
         `num_buffering_stages' identifies the number of entries in the
     `buffering_stages' array.  There are always exactly two more buffering
     stages than lifting steps.  The first two buffering stages correspond
     to unfiltered odd and even line sub-sequences, respectively.  Subsequent
     buffering stages hold the results produced by each consecutive lifting
     step.  Remember that the first lifting step generates odd lines by
     updating an odd target line using filtered even source lines, while
     the second lifting step generates even lines and so forth.  In this
     way the even indexed entries of the `buffering_stages' array correspond
     to odd numbered lines and vice-versa.
         `branch_output_stages' identifies the buffering stages whose
     generators produce the output for each of the two branches.  The first
     branch (index 0) corresponds to the vertically low-pass subband, while
     the second (index 1) corresponds to the vertically high-pass subband.
     Whenever a new line is pushed into the analysis stage object, it is
     added to the first or second buffering stage as appropriate, after which
     an attempt is made to alternately extract lines from the branch output
     stages; the function returns only when nothing more can be produced.  In
     this way, we always produce output lines in the most timely fashion
     possible.  The next line to be requested from each of the output
     branches is identified by the corresponding entries in the
     `branch_next_row_idx' array.
         The `banch_needs_scaling' and `branch_scale' arrays are used only
     for float-lifting kernels.  If `branch_needs_scaling[b]' is non-zero
     then the subband samples for branch b (0=low-pass, 1=high-pass) must
     be scaled by `branch_scale[b]' before being sent out to the next
     analysis stage object.
         `heap' manages a heap for recycled line buffers, so that they can
     be distributed amongst the buffering stages in the most efficient
     manner.
         The `num_frames' field holds the number of frames.  The SSO-DWT
     is applied if and only if `num_frames' is not equal to 1.  Even
     though the SSO-DWT is an overlapping transform, the number of frames
     is computed based upon a disjoint partition.  The overlap samples
     are then determined subsequently.  This is important, since it can
     happen that the overlap sample is an entire frame.
         The `frame_rows' field holds the nominal vertical frame
     dimension; it is meaningful only if `num_frames' > 1.
         The `frame_ref' field holds the vertical anchor coordinate
     for the frame partition.
         The `frame_idx' field runs from 0 to `num_frames'-1 and is used
     to determine whether we are processing and internal frame or one
     which abuts a boundary.
         The `current_frame_rows' and `first_row_idx_in_frame' hold the
     absolute size and location of the current frame which is being
     processed, with respect to the canvas coordinate system.
         The `ovlp_top' and `ovlp_bottom' fields indicate whether the
     frame which is currently being processed contains an extra overlap
     row (i.e. outside the nominal frame partition) at the top or bottom
     of the frame (exactly one of these must be true for internal frames
     being processed using the SSO-DWT).  These fields are used to mimic
     the type of processing which would be used to build an efficient
     hardware implementation of the SSO-DWT. */


/* ========================================================================= */
/* ---------------------------- Internal Functions ------------------------- */
/* ========================================================================= */

/*****************************************************************************/
/* STATIC                       start_vertical_frame                         */
/*****************************************************************************/

static void
  start_vertical_frame(hplx_vert_analysis_by_lifting_ref self)

 /* Performs the initialization code required to restart the vertical
    buffering at the start of each vertical frame.  The function administers
    the `self->first_row_idx_in_frame', `self->current_frame_rows',
    `self->ovlp_top' and `self->ovlp_bottom' fields, as well as
    setting up the fields in each buffering stage in preparation for the
    new frame. */

{
  hplx_buffering_stage_ptr stage;
  int b, n, k, num_buffers, even_taps;
  int special_first, special_last, skip_last;
  int top_boundary_odd, bottom_boundary_odd, ovlp_top, ovlp_bottom;
  int subseq_rows[2];

  if (self->frame_idx == 0)
    { /* Set the location and size of the current frame partition. */
      self->current_frame_rows = self->first_frame_rows;
      assert(self->current_frame_rows <= self->rows_left_in_tile);
      if (self->current_frame_rows == 0)
        return;
    }
  else
    {
      /* Adjust counters to reflect the true frame partition, rather than
         the current transform block. */
      self->current_frame_rows -= self->ovlp_top + self->ovlp_bottom;
      self->first_row_idx_in_frame += self->ovlp_top;

      /* Update the location and size of the current frame partition. */
      self->first_row_idx_in_frame += self->current_frame_rows;
      self->rows_left_in_tile -= self->current_frame_rows;
      self->current_frame_rows = self->frame_rows;
      if (self->current_frame_rows > self->rows_left_in_tile)
        self->current_frame_rows = self->rows_left_in_tile;
    }
  assert(self->current_frame_rows > 0);

  top_boundary_odd = self->first_row_idx_in_frame & 1;
  bottom_boundary_odd =
    (self->first_row_idx_in_frame+self->current_frame_rows-1) & 1;
  subseq_rows[0] = (self->current_frame_rows+1-top_boundary_odd) >> 1;
  subseq_rows[1] = (self->current_frame_rows+top_boundary_odd) >> 1;
  special_first = special_last = skip_last = ovlp_top = ovlp_bottom = 0;
  if (self->frame_idx > 0)
    { /* Internal top boundary. */
      special_first = 1;
      if (top_boundary_odd)
        { ovlp_top = 1; subseq_rows[0]++; top_boundary_odd = 0; }
    }
  else if (self->base.sso_ext && !top_boundary_odd)
    special_first = 1; /* Use SSO-DWT style extension at tile boundaries. */
  if (self->frame_idx < (self->num_frames-1))
    { /* Internal bottom boundary. */
      special_last = skip_last = 1;
      if (bottom_boundary_odd)
        { ovlp_bottom = 1; subseq_rows[0]++; bottom_boundary_odd = 0; }
    }
  else if (self->base.sso_ext && !bottom_boundary_odd)
    special_last = 1; /* Use SSO-DWT style extension at tile boundaries. */

  /* Make `first_row_idx_in_frame', `current_frame_rows' and
     `rows_left_in_frame' refer to the transform block, instead of the
     frame partition.  We will restore their interpretations when we
     re-enter this function at the beginning of the next frame (see above). */

  self->ovlp_bottom = ovlp_bottom;
  self->ovlp_top = ovlp_top;
  self->first_row_idx_in_frame -= ovlp_top;
  self->current_frame_rows += ovlp_top + ovlp_bottom;
  self->rows_left_in_frame = self->current_frame_rows;

  /* Now set up working buffers. */

  for (b=0; b < ((hplx_analysis_stage_ref) self)->vert_limit; b++)
    { /* b = 0 corresponds to the sub-sequence of even rows in the frame */
      even_taps = (self->steps->neg_support + self->steps->pos_support+1) & 1;
      for (n=0; n < self->num_buffering_stages; n++)
        {
          stage = self->buffering_stages +n;
          if (stage->odd_lines == b)
            {
              if (even_taps)
                {
                  if (top_boundary_odd)
                    local_error("Cannot start image, tile or frame with an "
                                "odd indexed sample when using even length "
                                "filters!  Use odd length filters!");
                  stage->first_extension =
                    symmetric_extension_type(1,self->current_frame_rows&1,b,0);
                  stage->first_extension =
                    symmetric_extension_type(1,self->current_frame_rows&1,b,1);
                }
              else
                { /* Simple case for odd length filters. */
                  stage->first_extension = (top_boundary_odd^(1-b))?0:1;
                  stage->last_extension = (bottom_boundary_odd^(1-b))?0:1;
                }
              if (b == 0)
                {
                  stage->special_first = special_first;
                  stage->special_last = special_last;
                  stage->skip_last = skip_last;
                  stage->missing_first_row = top_boundary_odd;
                }
              else
                {
                  stage->special_first = 0;
                  stage->special_last = 0;
                  stage->skip_last = 0;
                  stage->missing_first_row = 0;
                }
              stage->rows = subseq_rows[b];
              num_buffers = stage->next_row_idx - stage->min_row_idx;
              for (k=0; k < num_buffers; k++)
                hplx_lift_heap__return_buffer(stage->heap,
                                              stage->row_buffers[k]);
              stage->min_row_idx = 0;
              stage->next_row_idx = 0;
            }
          else
            assert(stage->odd_lines == (1-b));
        }
      self->branch_next_row_idx[b] = 0;
    }
}

/*****************************************************************************/
/* STATIC                   hplx_lift_stage__get_rows                        */
/*****************************************************************************/

static int
  hplx_lift_stage__get_rows(hplx_buffering_stage_ptr stage, int min_row_idx,
                            int num_rows, hplx_row_buffer_state_ptr bufs[])

 /* This function does all the computational work associated with lifting,
    including management of extensions at the vertical boundaries of the
    image, tile or frame.  The function tries to satisfy a request for a range
    of rows from the supplied buffering stage.  If the range extends beyond
    the upper or lower image boundaries, it is modified to include only
    those rows which lie within the image and the missing rows are
    extrapolated using the boundary extension policy.  Once the range of valid
    row indices is determined in this way, the function attempts to generate
    any rows which it does not already have.  If successful, it returns 1 and
    fills in the supplied buffer with pointers to the relevant
    `hplx_row_buffer_state' structures.  Otherwise, it returns 0. */

{
  int ext_before, ext_after, next_row_idx, offset, n, p;
  hplx_lifting_step_ptr step;
  hplx_row_buffer_state_ptr *fp, *lp;

  if ((min_row_idx >= stage->rows) || ((min_row_idx+num_rows) <= 0))
    { /* Request lies entirely outside image.  No extension will be applied
         here; caller should detect NULL buffers and skip the relevant
         lifting step. */
      while (num_rows--)
        *(bufs++) = NULL;