motion_estimation.c

QccPack implementation in C

/*
 * 
 * QccPack: Quantization, compression, and coding libraries
 * Copyright (C) 1997-2005  James E. Fowler
 * 
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Library General Public
 * License as published by the Free Software Foundation; either
 * version 2 of the License, or (at your option) any later version.
 * 
 * This library is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * Library General Public License for more details.
 * 
 * You should have received a copy of the GNU Library General Public
 * License along with this library; if not, write to the
 * Free Software Foundation, Inc., 675 Mass Ave, Cambridge,
 * MA 02139, USA.
 * 
 */

#include "libQccPack.h"


int QccVIDMotionEstimationExtractBlock(const QccIMGImageComponent *image,
                                       double row,
                                       double col,
                                       QccMatrix block,
                                       int block_size,
                                       int subpixel_accuracy)
{
  int block_row, block_col;
  int step;
  int row2, col2;
  int extraction_row, extraction_col;

  if (image == NULL)
    return(0);
  if (image->image == NULL)
    return(0);
  if (block == NULL)
    return(0);

  switch (subpixel_accuracy)
    {
    case QCCVID_ME_FULLPIXEL:
      step = 1;
      row2 = (int)row;
      col2 = (int)col;
      break;
    case QCCVID_ME_HALFPIXEL:
      step = 2;
      row2 = (int)(row * 2);
      col2 = (int)(col * 2);
      break;
    case QCCVID_ME_QUARTERPIXEL:
      step = 4;
      row2 = (int)(row * 4);
      col2 = (int)(col * 4);
      break;
    case QCCVID_ME_EIGHTHPIXEL:
      step = 8;
      row2 = (int)(row * 8);
      col2 = (int)(col * 8);
      break;
    default:
      QccErrorAddMessage("(QccVIDMotionEstimationExtractBlock): Unrecognized subpixel accuracy (%d)",
                         subpixel_accuracy);
      return(1);
    }

  for (block_row = 0; block_row < block_size; block_row++)
    for (block_col = 0; block_col < block_size; block_col++)
      {
        extraction_row = block_row * step + row2;
        extraction_col = block_col * step + col2;

        if (extraction_row < 0)
          extraction_row = 0;
        else
          if (extraction_row >= image->num_rows)
            extraction_row = image->num_rows - 1;

        if (extraction_col < 0)
          extraction_col = 0;
        else
          if (extraction_col >= image->num_cols)
            extraction_col = image->num_cols - 1;

        block[block_row][block_col] =
          image->image[extraction_row][extraction_col];
      }

  return(0);
}


int QccVIDMotionEstimationInsertBlock(QccIMGImageComponent *image,
                                      double row,
                                      double col,
                                      const QccMatrix block,
                                      int block_size,
                                      int subpixel_accuracy)
{
  int block_row, block_col;
  int step;
  int row2, col2;
  int insertion_row, insertion_col;

  if (image == NULL)
    return(0);
  if (image->image == NULL)
    return(0);
  if (block == NULL)
    return(0);

  switch (subpixel_accuracy)
    {
    case QCCVID_ME_FULLPIXEL:
      step = 1;
      row2 = (int)row;
      col2 = (int)col;
      break;
    case QCCVID_ME_HALFPIXEL:
      step = 2;
      row2 = (int)(row * 2);
      col2 = (int)(col * 2);
      break;
    case QCCVID_ME_QUARTERPIXEL:
      step = 4;
      row2 = (int)(row * 4);
      col2 = (int)(col * 4);
      break;
    case QCCVID_ME_EIGHTHPIXEL:
      step = 8;
      row2 = (int)(row * 8);
      col2 = (int)(col * 8);
      break;
    default:
      QccErrorAddMessage("(QccVIDMotionEstimationInsertBlock): Unrecognized subpixel accuracy (%d)",
                         subpixel_accuracy);
      return(1);
    }

  for (block_row = 0; block_row < block_size; block_row++)
    for (block_col = 0; block_col < block_size; block_col++)
      {
        insertion_row = block_row * step + row2;
        insertion_col = block_col * step + col2;

        if ((insertion_row >= 0) &&
            (insertion_row < image->num_rows) &&
            (insertion_col >= 0) &&
            (insertion_col < image->num_cols))
          image->image[insertion_row][insertion_col] =
            block[block_row][block_col];
      }

  return(0);
}


double QccVIDMotionEstimationMAE(QccMatrix current_block,
                                 QccMatrix reference_block,
                                 QccMatrix weights,
                                 int block_size)
{
  double mae = 0.0;
  int block_row, block_col;

  if (current_block == NULL)
    return(0.0);
  if (reference_block == NULL)
    return(0.0);

  if (weights == NULL)
    for (block_row = 0; block_row < block_size; block_row++)
      for (block_col = 0; block_col < block_size; block_col++)
        mae +=
          fabs(current_block[block_row][block_col] -
               reference_block[block_row][block_col]);
  else
    for (block_row = 0; block_row < block_size; block_row++)
      for (block_col = 0; block_col < block_size; block_col++)
        mae +=
          weights[block_row][block_col] *
          fabs(current_block[block_row][block_col] -
               reference_block[block_row][block_col]);

  return(mae / block_size / block_size);
}


static int QccVIDMotionEstimationWindowSearch(QccMatrix current_block,
                                              QccMatrix reference_block,
                                              int block_size,
                                              const QccIMGImageComponent
                                              *reference_frame,
                                              double search_row,
                                              double search_col,
                                              double window_size,
                                              double search_step,
                                              int subpixel_accuracy,
                                              double *motion_vector_horizontal,
                                              double *motion_vector_vertical)
{
  double u, v;
  double reference_frame_row, reference_frame_col;
  double current_mae;
  double min_mae = MAXDOUBLE;

  for (v = -window_size; v <= window_size; v += search_step)
    for (u = -window_size; u <= window_size; u += search_step)
      {
        reference_frame_row = search_row + v;
        reference_frame_col = search_col + u;
        
        if (QccVIDMotionEstimationExtractBlock(reference_frame,
                                               reference_frame_row,
                                               reference_frame_col,
                                               reference_block,
                                               block_size,
                                               subpixel_accuracy))
          {
            QccErrorAddMessage("(QccVIDMotionEstimationWindowSearch): Error calling QccVIDMotionEstimationExtractBlock()");
            return(1);
          }
        
        current_mae = QccVIDMotionEstimationMAE(current_block,
                                                reference_block,
                                                NULL,
                                                block_size);
        
        if (current_mae < min_mae)
          {
            min_mae = current_mae;
            *motion_vector_horizontal = u;
            *motion_vector_vertical = v;
          }
      }

  return(0);
}


int QccVIDMotionEstimationFullSearch(const QccIMGImageComponent *current_frame,
                                     const QccIMGImageComponent
                                     *reference_frame,
                                     QccIMGImageComponent
                                     *motion_vectors_horizontal,
                                     QccIMGImageComponent
                                     *motion_vectors_vertical,
                                     int block_size,
                                     int window_size,
                                     int subpixel_accuracy)
{
  int return_value;
  QccMatrix current_block = NULL;
  QccMatrix reference_block = NULL;
  int block_row, block_col;
  double u, v;
  double current_search_step;
  double final_search_step;
  int mv_row, mv_col;
  double search_row, search_col;
  double current_window_size;

  if (current_frame == NULL)
    return(0);
  if (reference_frame == NULL)