motion_est.c

MPEG-4编解码的实现(包括MPEG4视音频编解码)

/**************************************************************************
 *
 *  Modifications:
 *
 *  02.04.2002 add EPZS(^2) as ME algorithm, use PMV_USESQUARES to choose between 
 *             EPZS and EPZS^2
 *  08.02.2002 split up PMVfast into three routines: PMVFast, PMVFast_MainLoop
 *             PMVFast_Refine to support multiple searches with different start points
 *  07.01.2002 uv-block-based interpolation
 *  06.01.2002 INTER/INTRA-decision is now done before any SEARCH8 (speedup)
 *             changed INTER_BIAS to 150 (as suggested by suxen_drol)
 *             removed halfpel refinement step in PMVfastSearch8 + quality=5
 *             added new quality mode = 6 which performs halfpel refinement
 *             filesize difference between quality 5 and 6 is smaller than 1%
 *             (Isibaar)
 *  31.12.2001 PMVfastSearch16 and PMVfastSearch8 (gruel)
 *  30.12.2001 get_range/MotionSearchX simplified; blue/green bug fix
 *  22.12.2001 commented best_point==99 check
 *  19.12.2001 modified get_range (purple bug fix)
 *  15.12.2001 moved pmv displacement from mbprediction
 *  02.12.2001 motion estimation/compensation split (Isibaar)
 *  16.11.2001 rewrote/tweaked search algorithms; [e-mail]
 *  10.11.2001 support for sad16/sad8 functions
 *  28.08.2001 reactivated MODE_INTER4V for EXT_MODE
 *  24.08.2001 removed MODE_INTER4V_Q, disabled MODE_INTER4V for EXT_MODE
 *  22.08.2001 added MODE_INTER4V_Q			
 *  20.08.2001 added pragma to get rid of internal compiler error with VC6
 *             idea by Cyril. Thanks.
 *
 *  Michael Militzer <[e-mail]>
 *
 **************************************************************************/

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>

#include "../encoder.h"
#include "../utils/mbfunctions.h"
#include "../prediction/mbprediction.h"
#include "../global.h"
#include "../utils/timer.h"
#include "sad.h"

// very large value
#define MV_MAX_ERROR	(4096 * 256)

// stop search if sdelta < THRESHOLD
#define MV16_THRESHOLD	192
#define MV8_THRESHOLD	56

/* sad16(0,0) bias; mpeg4 spec suggests nb/2+1 */
/* nb  = vop pixels * 2^(bpp-8) */
#define MV16_00_BIAS	(128+1)

/* INTER bias for INTER/INTRA decision; mpeg4 spec suggests 2*nb */
#define INTER_BIAS	512

/* Parameters which control inter/inter4v decision */
#define IMV16X16			5

/* vector map (vlc delta size) smoother parameters */
#define NEIGH_TEND_16X16	2
#define NEIGH_TEND_8X8		2


// fast ((A)/2)*2
#define EVEN(A)		(((A)<0?(A)+1:(A)) & ~1)


#ifndef MIN
#define MIN(X, Y) ((X)<(Y)?(X):(Y))
#endif
#ifndef MAX
#define MAX(X, Y) ((X)>(Y)?(X):(Y))
#endif
#define ABS(X)    (((X)>0)?(X):-(X))
#define SIGN(X)   (((X)>0)?1:-1)

int32_t PMVfastSearch16(
					const uint8_t * const pRef,
					const uint8_t * const pRefH,
					const uint8_t * const pRefV,
					const uint8_t * const pRefHV,
					const IMAGE * const pCur,
					const int x, const int y,
					const uint32_t MotionFlags,
					const MBParam * const pParam,
					MACROBLOCK * const pMBs,
					VECTOR * const currMV,
					VECTOR * const currPMV);

int32_t EPZSSearch16(
					const uint8_t * const pRef,
					const uint8_t * const pRefH,
					const uint8_t * const pRefV,
					const uint8_t * const pRefHV,
					const IMAGE * const pCur,
					const int x, const int y,
					const uint32_t MotionFlags,
					const MBParam * const pParam,
					MACROBLOCK * const pMBs,
					VECTOR * const currMV,
					VECTOR * const currPMV);


int32_t PMVfastSearch8(
					const uint8_t * const pRef,
					const uint8_t * const pRefH,
					const uint8_t * const pRefV,
					const uint8_t * const pRefHV,
					const IMAGE * const pCur,
					const int x, const int y,
					const int start_x, int start_y,
					const uint32_t MotionFlags,
					const MBParam * const pParam,
					MACROBLOCK * const pMBs,
					VECTOR * const currMV,
					VECTOR * const currPMV);

int32_t EPZSSearch8(
					const uint8_t * const pRef,
					const uint8_t * const pRefH,
					const uint8_t * const pRefV,
					const uint8_t * const pRefHV,
					const IMAGE * const pCur,
					const int x, const int y,
					const int start_x, int start_y,
					const uint32_t MotionFlags,
					const MBParam * const pParam,
					MACROBLOCK * const pMBs,
					VECTOR * const currMV,
					VECTOR * const currPMV);


typedef int32_t (MainSearch16Func)(
	const uint8_t * const pRef,
	const uint8_t * const pRefH,
	const uint8_t * const pRefV,
	const uint8_t * const pRefHV,
	const uint8_t * const cur,
	const int x, const int y,
	int32_t startx, int32_t starty,	
	int32_t iMinSAD,
	VECTOR * const currMV,
	const VECTOR * const pmv,
	const int32_t min_dx, const int32_t max_dx, 
	const int32_t min_dy, const int32_t max_dy,
	const int32_t iEdgedWidth, 
	const int32_t iDiamondSize, 
	const int32_t iFcode,
	const int32_t iQuant,
	int iFound);

typedef MainSearch16Func* MainSearch16FuncPtr;


typedef int32_t (MainSearch8Func)(
	const uint8_t * const pRef,
	const uint8_t * const pRefH,
	const uint8_t * const pRefV,
	const uint8_t * const pRefHV,
	const uint8_t * const cur,
	const int x, const int y,
	int32_t startx, int32_t starty,	
	int32_t iMinSAD,
	VECTOR * const currMV,
	const VECTOR * const pmv,
	const int32_t min_dx, const int32_t max_dx, 
	const int32_t min_dy, const int32_t max_dy,
	const int32_t iEdgedWidth, 
	const int32_t iDiamondSize, 
	const int32_t iFcode,
	const int32_t iQuant,
	int iFound);

typedef MainSearch8Func* MainSearch8FuncPtr;

// mv.length table
static const uint32_t mvtab[33] = {
    1,  2,  3,  4,  6,  7,  7,  7,
    9,  9,  9,  10, 10, 10, 10, 10,
    10, 10, 10, 10, 10, 10, 10, 10,
    10, 11, 11, 11, 11, 11, 11, 12, 12
};


static __inline uint32_t mv_bits(int32_t component, const uint32_t iFcode)
{
    if (component == 0)
		return 1;

    if (component < 0)
		component = -component;

    if (iFcode == 1)
    {
		if (component > 32)
		    component = 32;

		return mvtab[component] + 1;
    }

    component += (1 << (iFcode - 1)) - 1;
    component >>= (iFcode - 1);

    if (component > 32)
		component = 32;

    return mvtab[component] + 1 + iFcode - 1;
}


static __inline uint32_t calc_delta_16(const int32_t dx, const int32_t dy, const uint32_t iFcode)
{
	return NEIGH_TEND_16X16 * (mv_bits(dx, iFcode) + mv_bits(dy, iFcode));
}

static __inline uint32_t calc_delta_8(const int32_t dx, const int32_t dy, const uint32_t iFcode)

{
    return NEIGH_TEND_8X8 * (mv_bits(dx, iFcode) + mv_bits(dy, iFcode));
}




/* calculate the min/max range (in halfpixels)
	relative to the _MACROBLOCK_ position
*/

static void __inline get_range(
	int32_t * const min_dx, int32_t * const max_dx,
	int32_t * const min_dy, int32_t * const max_dy,
	const uint32_t x, const uint32_t y, 
	const uint32_t block_sz,					// block dimension, 8 or 16
	const uint32_t width, const uint32_t height,
	const uint32_t fcode)
{

	const int search_range = 32 << (fcode - 1);
	const int high = search_range - 1;
	const int low = -search_range;

	// convert full-pixel measurements to half pixel
	const int hp_width = 2 * width;
	const int hp_height = 2 * height;
	const int hp_edge = 2 * block_sz;
	const int hp_x = 2 * (x) * block_sz;		// we need _right end_ of block, not x-coordinate
	const int hp_y = 2 * (y) * block_sz;		// same for _bottom end_

	*max_dx = MIN(high,	hp_width - hp_x);
	*max_dy = MIN(high,	hp_height - hp_y);
	*min_dx = MAX(low,	-(hp_edge + hp_x));
	*min_dy = MAX(low,	-(hp_edge + hp_y));

}


/*
 * getref: calculate reference image pointer 
 * the decision to use interpolation h/v/hv or the normal image is
 * based on dx & dy.
 */

static __inline const uint8_t * get_ref(
	const uint8_t * const refn,
	const uint8_t * const refh,
	const uint8_t * const refv,
	const uint8_t * const refhv,
	const uint32_t x, const uint32_t y,
	const uint32_t block,					// block dimension, 8 or 16
	const int32_t dx, const int32_t dy,
	const uint32_t stride)
{

	switch ( ((dx&1)<<1) + (dy&1) )		// ((dx%2)?2:0)+((dy%2)?1:0)
	{
	case 0  : return refn + (x*block+dx/2) + (y*block+dy/2)*stride;
	case 1  : return refv + (x*block+dx/2) + (y*block+(dy-1)/2)*stride;
	case 2  : return refh + (x*block+(dx-1)/2) + (y*block+dy/2)*stride;
	default : 
	case 3  : return refhv + (x*block+(dx-1)/2) + (y*block+(dy-1)/2)*stride;
	}

}


/* This is somehow a copy of get_ref, but with MV instead of X,Y */

static __inline const uint8_t * get_ref_mv(
	const uint8_t * const refn,
	const uint8_t * const refh,
	const uint8_t * const refv,
	const uint8_t * const refhv,
	const uint32_t x, const uint32_t y,
	const uint32_t block,			// block dimension, 8 or 16
	const VECTOR* mv,	// measured in half-pel!
	const uint32_t stride)
{

	switch ( (((mv->x)&1)<<1) + ((mv->y)&1) )
	{
	case 0  : return refn + (x*block+(mv->x)/2) + (y*block+(mv->y)/2)*stride;
    	case 1  : return refv + (x*block+(mv->x)/2) + (y*block+((mv->y)-1)/2)*stride;
	case 2  : return refh + (x*block+((mv->x)-1)/2) + (y*block+(mv->y)/2)*stride;
	default : 
	case 3  : return refhv + (x*block+((mv->x)-1)/2) + (y*block+((mv->y)-1)/2)*stride;
	}

}

#ifndef SEARCH16
#define SEARCH16	PMVfastSearch16
//#define SEARCH16	FullSearch16
//#define SEARCH16	EPZSSearch16
#endif

#ifndef SEARCH8
#define SEARCH8		PMVfastSearch8
//#define SEARCH8	EPZSSearch8
#endif

bool MotionEstimation(
	MACROBLOCK * const pMBs,
	MBParam * const pParam,
	const IMAGE * const pRef,
	const IMAGE * const pRefH,
	const IMAGE * const pRefV,
	const IMAGE * const pRefHV,
	IMAGE * const pCurrent, 
	const uint32_t iLimit)

{
	const uint32_t iWcount = pParam->mb_width;
	const uint32_t iHcount = pParam->mb_height;
 
	uint32_t i, j, iIntra = 0;

	VECTOR mv16;
	VECTOR pmv16;

	int32_t sad8 = 0;
	int32_t sad16;
	int32_t deviation;

	if (sadInit)
		(*sadInit)();
		
	// note: i==horizontal, j==vertical
	for (i = 0; i < iHcount; i++)
		for (j = 0; j < iWcount; j++)
		{
			MACROBLOCK *pMB = &pMBs[j + i * iWcount];

			sad16 = SEARCH16(pRef->y, pRefH->y, pRefV->y, pRefHV->y, pCurrent, 
					 j, i, pParam->motion_flags,
					 pParam, pMBs, &mv16, &pmv16); 
			pMB->sad16=sad16;


			/* decide: MODE_INTER or MODE_INTRA 
			   if (dev_intra < sad_inter - 2 * nb) use_intra
			*/

			deviation = dev16(pCurrent->y + j*16 + i*16*pParam->edged_width, pParam->edged_width);
	
			if (deviation < (sad16 - INTER_BIAS))
			{
				pMB->mode = MODE_INTRA;
				pMB->mvs[0].x = pMB->mvs[1].x = pMB->mvs[2].x = pMB->mvs[3].x = 0;
				pMB->mvs[0].y = pMB->mvs[1].y = pMB->mvs[2].y = pMB->mvs[3].y = 0;

				iIntra++;
				if(iIntra >= iLimit)	
					return 1;

				continue;
			}

			if (pParam->global_flags & XVID_INTER4V)
			{
				pMB->sad8[0] = SEARCH8(pRef->y, pRefH->y, pRefV->y, pRefHV->y, pCurrent, 
						       2 * j, 2 * i, mv16.x, mv16.y, pParam->motion_flags, 
						       pParam, pMBs, &pMB->mvs[0], &pMB->pmvs[0]); 

				pMB->sad8[1] = SEARCH8(pRef->y, pRefH->y, pRefV->y, pRefHV->y, pCurrent, 
						       2 * j + 1, 2 * i, mv16.x, mv16.y, pParam->motion_flags,
						       pParam, pMBs, &pMB->mvs[1], &pMB->pmvs[1]); 

				pMB->sad8[2] = SEARCH8(pRef->y, pRefH->y, pRefV->y, pRefHV->y, pCurrent, 
						       2 * j, 2 * i + 1, mv16.x, mv16.y, pParam->motion_flags,
						       pParam, pMBs, &pMB->mvs[2], &pMB->pmvs[2]); 
			
				pMB->sad8[3] = SEARCH8(pRef->y, pRefH->y, pRefV->y, pRefHV->y, pCurrent, 
						       2 * j + 1, 2 * i + 1, mv16.x, mv16.y, pParam->motion_flags,
						       pParam, pMBs, &pMB->mvs[3], &pMB->pmvs[3]); 

				sad8 = pMB->sad8[0] + pMB->sad8[1] + pMB->sad8[2] + pMB->sad8[3];
			}

    
			/* decide: MODE_INTER or MODE_INTER4V 
			   mpeg4:   if (sad8 < sad16 - nb/2+1) use_inter4v
			*/

			if (pMB->dquant == NO_CHANGE) {
				if (((pParam->global_flags & XVID_INTER4V)==0) || 
				    (sad16 < (sad8 + (int32_t)(IMV16X16 * pParam->quant)))) { 
			
					sad8 = sad16;
					pMB->mode = MODE_INTER;
					pMB->mvs[0].x = pMB->mvs[1].x = pMB->mvs[2].x = pMB->mvs[3].x = mv16.x;
					pMB->mvs[0].y = pMB->mvs[1].y = pMB->mvs[2].y = pMB->mvs[3].y = mv16.y;
					pMB->pmvs[0].x = pmv16.x;
					pMB->pmvs[0].y = pmv16.y;
				}
				else
					pMB->mode = MODE_INTER4V;
			}
			else 
			{
				sad8 = sad16;
				pMB->mode = MODE_INTER;
				pMB->mvs[0].x = pMB->mvs[1].x = pMB->mvs[2].x = pMB->mvs[3].x = mv16.x;
				pMB->mvs[0].y = pMB->mvs[1].y = pMB->mvs[2].y = pMB->mvs[3].y = mv16.y;
				pMB->pmvs[0].x = pmv16.x;
				pMB->pmvs[0].y = pmv16.y;
			}
		}

	return 0;
}

#define MVzero(A) ( ((A).x)==(0) && ((A).y)==(0) )

#define MVequal(A,B) ( ((A).x)==((B).x) && ((A).y)==((B).y) )


#define CHECK_MV16_ZERO {\
  if ( (0 <= max_dx) && (0 >= min_dx) \
    && (0 <= max_dy) && (0 >= min_dy) ) \
  { \
    iSAD = sad16( cur, get_ref(pRef, pRefH, pRefV, pRefHV, x, y, 16, 0, 0 , iEdgedWidth), iEdgedWidth, MV_MAX_ERROR); \
    iSAD += calc_delta_16(-pmv[0].x, -pmv[0].y, (uint8_t)iFcode) * iQuant;\
    if (iSAD <= iQuant * 96)	\
   	iSAD -= MV16_00_BIAS; \
    if (iSAD < iMinSAD) \
    {  iMinSAD=iSAD; currMV->x=0; currMV->y=0; }  }	\
}

#define NOCHECK_MV16_CANDIDATE(X,Y) { \
    iSAD = sad16( cur, get_ref(pRef, pRefH, pRefV, pRefHV, x, y, 16, X, Y, iEdgedWidth),iEdgedWidth, iMinSAD); \
    iSAD += calc_delta_16((X) - pmv[0].x, (Y) - pmv[0].y, (uint8_t)iFcode) * iQuant;\
    if (iSAD < iMinSAD) \
    {  iMinSAD=iSAD; currMV->x=(X); currMV->y=(Y); } \
}

#define CHECK_MV16_CANDIDATE(X,Y) { \
  if ( ((X) <= max_dx) && ((X) >= min_dx) \
    && ((Y) <= max_dy) && ((Y) >= min_dy) ) \
  { \
    iSAD = sad16( cur, get_ref(pRef, pRefH, pRefV, pRefHV, x, y, 16, X, Y, iEdgedWidth),iEdgedWidth, iMinSAD); \
    iSAD += calc_delta_16((X) - pmv[0].x, (Y) - pmv[0].y, (uint8_t)iFcode) * iQuant;\
    if (iSAD < iMinSAD) \
    {  iMinSAD=iSAD; currMV->x=(X); currMV->y=(Y); } } \
}

#define CHECK_MV16_CANDIDATE_DIR(X,Y,D) { \
  if ( ((X) <= max_dx) && ((X) >= min_dx) \
    && ((Y) <= max_dy) && ((Y) >= min_dy) ) \
  { \
    iSAD = sad16( cur, get_ref(pRef, pRefH, pRefV, pRefHV, x, y, 16, X, Y, iEdgedWidth),iEdgedWidth, iMinSAD); \
    iSAD += calc_delta_16((X) - pmv[0].x, (Y) - pmv[0].y, (uint8_t)iFcode) * iQuant;\
    if (iSAD < iMinSAD) \
    {  iMinSAD=iSAD; currMV->x=(X); currMV->y=(Y); iDirection=(D); } } \
}

#define CHECK_MV16_CANDIDATE_FOUND(X,Y,D) { \
  if ( ((X) <= max_dx) && ((X) >= min_dx) \
    && ((Y) <= max_dy) && ((Y) >= min_dy) ) \
  { \
    iSAD = sad16( cur, get_ref(pRef, pRefH, pRefV, pRefHV, x, y, 16, X, Y, iEdgedWidth),iEdgedWidth, iMinSAD); \
    iSAD += calc_delta_16((X) - pmv[0].x, (Y) - pmv[0].y, (uint8_t)iFcode) * iQuant;\
    if (iSAD < iMinSAD) \
    {  iMinSAD=iSAD; currMV->x=(X); currMV->y=(Y); iDirection=(D); iFound=0; } } \
}


#define CHECK_MV8_ZERO {\
  iSAD = sad8( cur, get_ref(pRef, pRefH, pRefV, pRefHV, x, y, 8, 0, 0 , iEdgedWidth), iEdgedWidth); \
  iSAD += calc_delta_8(-pmv[0].x, -pmv[0].y, (uint8_t)iFcode) * iQuant;\
  if (iSAD < iMinSAD) \
  { iMinSAD=iSAD; currMV->x=0; currMV->y=0; } \
}