/*===========================================================================*
* bsearch.c
*
* Procedures concerned with the B-frame motion search
*
*===========================================================================*/
/*
* Copyright (c) 1995 The Regents of the University of California.
* All rights reserved.
*
* Permission to use, copy, modify, and distribute this software and its
* documentation for any purpose, without fee, and without written agreement is
* hereby granted, provided that the above copyright notice and the following
* two paragraphs appear in all copies of this software.
*
* IN NO EVENT SHALL THE UNIVERSITY OF CALIFORNIA BE LIABLE TO ANY PARTY FOR
* DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES ARISING OUT
* OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN IF THE UNIVERSITY OF
* CALIFORNIA HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*
* THE UNIVERSITY OF CALIFORNIA SPECIFICALLY DISCLAIMS ANY WARRANTIES,
* INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY
* AND FITNESS FOR A PARTICULAR PURPOSE. THE SOFTWARE PROVIDED HEREUNDER IS
* ON AN "AS IS" BASIS, AND THE UNIVERSITY OF CALIFORNIA HAS NO OBLIGATION TO
* PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS.
*/
/*
* $Header: /n/picasso/project/mpeg/mpeg_dist/mpeg_encode/RCS/bsearch.c,v 1.10 1995/08/07 21:49:01 smoot Exp $
* $Log: bsearch.c,v $
* Revision 1.10 1995/08/07 21:49:01 smoot
* fixed bug in initial-B-frame searches
*
* Revision 1.9 1995/06/26 21:36:07 smoot
* added new ordering constraints
* (B frames which are backward P's at the start of a sequence)
*
* Revision 1.8 1995/03/27 19:17:43 smoot
* killed useless type error messge (int32 defiend as int)
*
* Revision 1.7 1995/01/19 23:07:20 eyhung
* Changed copyrights
*
* Revision 1.6 1994/12/07 00:40:36 smoot
* Added separate P and B search ranges
*
* Revision 1.5 1994/03/15 00:27:11 keving
* nothing
*
* Revision 1.4 1993/12/22 19:19:01 keving
* nothing
*
* Revision 1.3 1993/07/22 22:23:43 keving
* nothing
*
* Revision 1.2 1993/06/30 20:06:09 keving
* nothing
*
* Revision 1.1 1993/06/03 21:08:08 keving
* nothing
*
* Revision 1.1 1993/03/02 18:27:05 keving
* nothing
*
*/
/*==============*
* HEADER FILES *
*==============*/
#include "pm_c_util.h"
#include "pm.h"
#include "all.h"
#include "mtypes.h"
#include "frames.h"
#include "motion_search.h"
#include "fsize.h"
#include "block.h"
/*==================*
* STATIC VARIABLES *
*==================*/
static int bsearchAlg;
/*===========================*
* INITIALIZATION PROCEDURES *
*===========================*/
/*===========================================================================*
*
* SetBSearchAlg
*
* set the B-search algorithm
*
* RETURNS: nothing
*
* SIDE EFFECTS: bsearchAlg modified
*
*===========================================================================*/
void
SetBSearchAlg(const char * const alg) {
if (strcmp(alg, "SIMPLE") == 0)
bsearchAlg = BSEARCH_SIMPLE;
else if (strcmp(alg, "CROSS2") == 0)
bsearchAlg = BSEARCH_CROSS2;
else if (strcmp(alg, "EXHAUSTIVE") == 0)
bsearchAlg = BSEARCH_EXHAUSTIVE;
else
pm_error("ERROR: Impossible bsearch alg: %s", alg);
}
/*===========================================================================*
*
* BSearchName
*
* return the text of the B-search algorithm
*
* RETURNS: a pointer to the string
*
* SIDE EFFECTS: none
*
*===========================================================================*/
const char *
BSearchName(void)
{
const char *retval;
switch(bsearchAlg) {
case BSEARCH_SIMPLE:
retval = "SIMPLE";break;
case BSEARCH_CROSS2:
retval = "CROSS2";break;
case BSEARCH_EXHAUSTIVE:
retval = "EXHAUSTIVE";break;
default:
pm_error("ERROR: Impossible BSEARCH ALG: %d", psearchAlg);
}
return retval;
}
/*===========================================================================*
*
* FindBestMatchExhaust
*
* tries to find matching motion vector
* see FindBestMatch for generic description
*
* DESCRIPTION: uses an exhaustive search
*
*===========================================================================*/
static int32
FindBestMatchExhaust(const LumBlock * const blockP,
const LumBlock * const currentBlockP,
MpegFrame * const prev,
int const by,
int const bx,
vector * const motionP,
int32 const bestSoFar,
int const searchRange) {
register int mx, my;
int32 bestDiff;
int stepSize;
int leftMY, leftMX;
int rightMY, rightMX;
int distance;
int tempRightMY, tempRightMX;
boolean changed = FALSE;
stepSize = (pixelFullSearch ? 2 : 1);
COMPUTE_MOTION_BOUNDARY(by,bx,stepSize,leftMY,leftMX,rightMY,rightMX);
/* try old motion vector first */
if (VALID_MOTION(*motionP)) {
bestDiff = LumAddMotionError(currentBlockP, blockP, prev, by, bx,
*motionP, bestSoFar);
if (bestSoFar < bestDiff)
bestDiff = bestSoFar;
} else {
motionP->y = motionP->x = 0;
bestDiff = bestSoFar;
}
/* maybe should try spiral pattern centered around prev motion vector? */
/* try a spiral pattern */
for (distance = stepSize;
distance <= searchRange;
distance += stepSize) {
tempRightMY = MIN(distance, rightMY);
tempRightMX = MIN(distance, rightMX);
/* do top, bottom */
for (my = -distance; my < tempRightMY;
my += max(tempRightMY+distance-stepSize, stepSize)) {
if (my >= leftMY) {
for (mx = -distance; mx < tempRightMX; mx += stepSize) {
if (mx >= leftMX) {
int diff;
vector m;
m.y = my; m.x = mx;
diff = LumAddMotionError(currentBlockP, blockP, prev,
by, bx, m, bestDiff);
if (diff < bestDiff) {
*motionP = m;
bestDiff = diff;
}
}
}
}
}
/* do left, right */
for (mx = -distance;
mx < tempRightMX;
mx += max(tempRightMX+distance-stepSize, stepSize)) {
if (mx >= leftMX) {
for (my = -distance+stepSize;
my < tempRightMY-stepSize;
my += stepSize) {
if (my >= leftMY) {
int diff;
vector m;
m.y = my; m.x = mx;
diff = LumAddMotionError(currentBlockP, blockP, prev,
by, bx,
m, bestDiff);
if (diff < bestDiff) {
*motionP = m;
bestDiff = diff;
changed = TRUE;
}
}
}
}
}
}
if (!changed)
++bestDiff;
return bestDiff;
}
/*===========================================================================*
*
* FindBestMatchTwoLevel
*
* tries to find matching motion vector
* see FindBestMatch for generic description
*
* DESCRIPTION: uses an exhaustive full-pixel search, then looks at
* neighboring half-pixels
*
*===========================================================================*/
static int32
FindBestMatchTwoLevel(const LumBlock * const blockP,
const LumBlock * const currentBlockP,
MpegFrame * const prev,
int const by,
int const bx,
vector * const motionP,
int32 const bestSoFar,
int const searchRange) {
int mx, my;
int32 bestDiff;
int leftMY, leftMX;
int rightMY, rightMX;
int distance;
int tempRightMY, tempRightMX;
boolean changed = FALSE;
int yOffset, xOffset;
/* exhaustive full-pixel search first */
COMPUTE_MOTION_BOUNDARY(by,bx,2,leftMY,leftMX,rightMY,rightMX);
--rightMY;
--rightMX;
/* convert vector into full-pixel vector */
if (motionP->y > 0 ) {
if ((motionP->y % 2) == 1)
--motionP->y;
} else if ((-motionP->y % 2) == 1)
++motionP->y;
if (motionP->x > 0 ) {
if ((motionP->x % 2) == 1 )
--motionP->x;
} else if ((-motionP->x % 2) == 1)
++motionP->x;
/* try old motion vector first */
if (VALID_MOTION(*motionP)) {
bestDiff = LumAddMotionError(currentBlockP, blockP, prev, by, bx,
*motionP, bestSoFar);
if (bestSoFar < bestDiff)
bestDiff = bestSoFar;
} else {
motionP->y = motionP->x = 0;
bestDiff = bestSoFar;
}
++rightMY;
++rightMX;
/* maybe should try spiral pattern centered around prev motion vector? */
/* try a spiral pattern */
for ( distance = 2; distance <= searchRange; distance += 2 ) {
tempRightMY = MIN(distance, rightMY);
tempRightMX = MIN(distance, rightMX);
/* do top, bottom */
for (my = -distance; my < tempRightMY;
my += max(tempRightMY+distance-2, 2)) {
if (my >= leftMY) {
for ( mx = -distance; mx < tempRightMX; mx += 2 ) {
if (mx >= leftMX) {
int diff;
vector m;
m.y = my; m.x = mx;
diff = LumAddMotionError(currentBlockP, blockP, prev,
by, bx, m, bestDiff);
if (diff < bestDiff) {
*motionP = m;
bestDiff = diff;
}
}
}
}
}
/* do left, right */
for (mx = -distance;
mx < tempRightMX;
mx += max(tempRightMX+distance-2, 2)) {
if (mx >= leftMX) {
for (my = -distance+2; my < tempRightMY-2; my += 2) {
if (my >= leftMY) {
int diff;
vector m;
m.y = my; m.x = mx;
diff = LumAddMotionError(currentBlockP, blockP, prev,
by, bx, m, bestDiff);
if (diff < bestDiff) {
*motionP = m;
bestDiff = diff;
changed = TRUE;
}
}
}
}
}
}
/* now look at neighboring half-pixels */
my = motionP->y;
mx = motionP->x;
--rightMY;
--rightMX;
for (yOffset = -1; yOffset <= 1; ++yOffset) {
for (xOffset = -1; xOffset <= 1; ++xOffset) {
if ((yOffset != 0) || (xOffset != 0)) {
vector m;
m.y = my + yOffset;
m.x = mx + xOffset;
if (VALID_MOTION(m)) {
int diff;
diff = LumAddMotionError(currentBlockP, blockP,
prev, by, bx, m, bestDiff);
if (diff < bestDiff) {
*motionP = m;
bestDiff = diff;
changed = TRUE;
}
}
}
}
}
if (!changed)
++bestDiff;
return bestDiff;
}
static void
trySpacing(int const spacing,
vector const center,
int const bestDiffSoFar,
vector * const newCenterP,
int32 * const newBestDiffP,
int const leftMY,
int const leftMX,
int const rightMY,
int const rightMX,
const LumBlock * const currentBlockP,
const LumBlock * const blockP,
MpegFrame * const prev,
int const by,
int const bx) {
int tempRightMY, tempRightMX;
int my;
int bestDiff;
vector newCenter;
/* Initial values */
newCenter = center;
bestDiff = bestDiffSoFar;
tempRightMY = MIN(rightMY, center.y + spacing + 1);
tempRightMX = MIN(rightMX, center.x + spacing + 1);
for (my = center.y - spacing; my < tempRightMY; my += spacing) {
if (my >= leftMY) {
int mx;
for (mx = center.x - spacing; mx < tempRightMX; mx += spacing) {
if (mx >= leftMX) {
int32 diff;
vector m;
m.y = my; m.x = mx;
diff = LumAddMotionError(currentBlockP, blockP, prev,
by, bx, m, bestDiff);
if (diff < bestDiff) {
/* We have a new best */
newCenter = m;
bestDiff = diff;
}
}
}
}
}
*newCenterP = newCenter;
*newBestDiffP = bestDiff;
}
static void
chooseNewSpacing(int const oldSpacing,
int const stepSize,
int * const newSpacingP) {
if (stepSize == 2) { /* make sure spacing is even */
if (oldSpacing == 2)
*newSpacingP = 0;
else {
int const trialSpacing = (oldSpacing + 1) / 2;
if ((trialSpacing % 2) != 0)
*newSpacingP = trialSpacing + 1;
else
*newSpacingP = trialSpacing;
}
} else {
if (oldSpacing == 1)
*newSpacingP = 0;
else
*newSpacingP = (oldSpacing + 1) / 2;
}
}
/*===========================================================================*
*
* FindBestMatchLogarithmic
*
* tries to find matching motion vector
* see FindBestMatch for generic description
*
* DESCRIPTION: uses a logarithmic search
*
*===========================================================================*/
static int32
FindBestMatchLogarithmic(const LumBlock * const blockP,
const LumBlock * const currentBlockP,
MpegFrame * const prev,
int const by,
int const bx,
vector * const motionP,
int32 const bestSoFar,
int const searchRange) {
int const stepSize = (pixelFullSearch ? 2 : 1);
int32 diff, bestDiff;
int leftMY, leftMX;
int rightMY, rightMX;
int spacing;
vector center;
COMPUTE_MOTION_BOUNDARY(by, bx, stepSize,
leftMY, leftMX, rightMY, rightMX);
bestDiff = 0x7fffffff;
/* grid spacing */
if (stepSize == 2) { /* make sure spacing is even */
spacing = (searchRange + 1) / 2;
if ((spacing % 2) != 0)
++spacing;
} else
spacing = (searchRange + 1) / 2;
/* Start at (0,0) */
center.y = center.x = 0;
while (spacing >= stepSize) {
trySpacing(spacing, center, bestDiff,
¢er, &bestDiff,
leftMY, leftMX, rightMY, rightMX,
currentBlockP, blockP, prev, by, bx);
chooseNewSpacing(spacing, stepSize, &spacing);
}
/* check old motion -- see if it's better */
if ((motionP->y >= leftMY) && (motionP->y < rightMY) &&
(motionP->x >= leftMX) && (motionP->x < rightMX)) {
diff = LumAddMotionError(currentBlockP, blockP, prev, by, bx,
*motionP, bestDiff);
} else
diff = 0x7fffffff;
if (bestDiff < diff)
*motionP = center;
else
bestDiff = diff;
return bestDiff;
}
/*===========================================================================*
*
* FindBestMatchSubSample
*
* tries to find matching motion vector
* see FindBestMatch for generic description
*
* DESCRIPTION: should use subsampling method, but too lazy to write all
* the code for it (so instead just calls FindBestMatchExhaust)
*
*===========================================================================*/
static int32
FindBestMatchSubSample(const LumBlock * const blockP,
const LumBlock * const currentBlockP,
MpegFrame * const prev,
int const by,
int const bx,
vector * const motionP,
int32 const bestSoFar,
int const searchRange) {
/* too lazy to write the code for this... */
return FindBestMatchExhaust(blockP, currentBlockP, prev,
by, bx, motionP, bestSoFar,
searchRange);
}
/*===========================================================================*
*
* FindBestMatch
*
* given a motion-compensated block in one direction, tries to find
* the best motion vector in the opposite direction to match it
*
* RETURNS: the best vector (*motionY, *motionX), and the corresponding
* error is returned if it is better than bestSoFar. If not,
* then a number greater than bestSoFar is returned and
* (*motionY, *motionX) has no meaning.
*
* SIDE EFFECTS: none
*
*===========================================================================*/
static int32
FindBestMatch(const LumBlock * const blockP,
const LumBlock * const currentBlockP,
MpegFrame * const prev,
int const by,
int const bx,
vector * const motionP,
int32 const bestSoFar,
int const searchRange) {
int32 result;
switch(psearchAlg) {
case PSEARCH_SUBSAMPLE:
result = FindBestMatchSubSample(
blockP, currentBlockP, prev, by, bx,
motionP, bestSoFar, searchRange);
break;
case PSEARCH_EXHAUSTIVE:
result = FindBestMatchExhaust(
blockP, currentBlockP, prev, by, bx,
motionP, bestSoFar, searchRange);
break;
case PSEARCH_LOGARITHMIC:
result = FindBestMatchLogarithmic(
blockP, currentBlockP, prev, by, bx,
motionP, bestSoFar, searchRange);
break;
case PSEARCH_TWOLEVEL:
result = FindBestMatchTwoLevel(
blockP, currentBlockP, prev, by, bx,
motionP, bestSoFar, searchRange);
break;
default:
pm_error("ERROR: Impossible P-search alg %d", psearchAlg);
}
return result;
}
/*===========================================================================*
*
* finds the best backward and forward motion vectors
* if backNeeded == FALSE, then won't find best backward vector if it
* is worse than the best forward vector
*
* *motionP is input as well as output. We do not update it
* if it would make the error worse than the existing value.
*
* RETURNS: *motionP and associated errors *forwardErrP and *backErrP.
*
* SIDE EFFECTS: none
*
*===========================================================================*/
static void
BMotionSearchNoInterp(const LumBlock * const currentBlockP,
MpegFrame * const prev,
MpegFrame * const next,
int const by,
int const bx,
motion * const motionP,
int32 * const forwardErrP,
int32 * const backErrP,
boolean const backNeeded) {
/* CALL SEARCH PROCEDURE */
switch(psearchAlg) {
case PSEARCH_SUBSAMPLE:
*forwardErrP = PSubSampleSearch(currentBlockP, prev, by, bx,
&motionP->fwd,searchRangeB);
*backErrP = PSubSampleSearch(currentBlockP, next, by, bx,
&motionP->bwd, searchRangeB);
break;
case PSEARCH_EXHAUSTIVE:
*forwardErrP = PLocalSearch(currentBlockP, prev, by, bx,
&motionP->fwd,
0x7fffffff, searchRangeB);
if (backNeeded)
*backErrP = PLocalSearch(currentBlockP, next, by, bx,
&motionP->bwd,
0x7fffffff, searchRangeB);
else
*backErrP = PLocalSearch(currentBlockP, next, by, bx,
&motionP->bwd,
*forwardErrP, searchRangeB);
break;
case PSEARCH_LOGARITHMIC:
*forwardErrP = PLogarithmicSearch(currentBlockP, prev, by, bx,
&motionP->fwd, searchRangeB);
*backErrP = PLogarithmicSearch(currentBlockP, next, by, bx,
&motionP->bwd, searchRangeB);
break;
case PSEARCH_TWOLEVEL:
*forwardErrP =
PTwoLevelSearch(currentBlockP, prev, by, bx,
&motionP->fwd, 0x7fffffff, searchRangeB);
if ( backNeeded ) {
*backErrP =
PTwoLevelSearch(currentBlockP, next, by, bx,
&motionP->bwd, 0x7fffffff, searchRangeB);
} else {
*backErrP =
PTwoLevelSearch(currentBlockP, next, by, bx,
&motionP->bwd, *forwardErrP, searchRangeB);
}
break;
default:
pm_error("ERROR: Impossible PSEARCH ALG: %d", psearchAlg);
}
}
/*===========================================================================*
*
* BMotionSearchSimple
*
* does a simple search for B-frame motion vectors
* see BMotionSearch for generic description
*
* DESCRIPTION:
* 1) find best backward and forward vectors
* 2) compute interpolated error using those two vectors
* 3) return the best of the three choices
*
* *fmyP,fmxP,bmyP,bmxP are inputs as well as outputs. We do not update
* them if it would make the error worse than the existing values. Otherwise,
* we update them to the vectors we find to be best.
*
*===========================================================================*/
static int
BMotionSearchSimple(const LumBlock * const currentBlockP,
MpegFrame * const prev,
MpegFrame * const next,
int const by,
int const bx,
motion * const motionP,
int const oldMode) {
int retval;
int32 forwardErr, backErr, interpErr;
LumBlock interpBlock;
int32 bestSoFar;
/* STEP 1 */
BMotionSearchNoInterp(currentBlockP, prev, next, by, bx, motionP,
&forwardErr, &backErr, TRUE);
/* STEP 2 */
ComputeBMotionLumBlock(prev, next, by, bx, MOTION_INTERPOLATE,
*motionP, &interpBlock);
bestSoFar = min(backErr, forwardErr);
interpErr =
LumBlockMAD(currentBlockP, &interpBlock, bestSoFar);
/* STEP 3 */
if (interpErr <= forwardErr) {
if (interpErr <= backErr)
retval = MOTION_INTERPOLATE;
else
retval = MOTION_BACKWARD;
} else if (forwardErr <= backErr)
retval = MOTION_FORWARD;
else
retval = MOTION_BACKWARD;
return retval;
}
/*===========================================================================*
*
* BMotionSearchCross2
*
* does a cross-2 search for B-frame motion vectors
* see BMotionSearch for generic description
*
* DESCRIPTION:
* 1) find best backward and forward vectors
* 2) find best matching interpolating vectors
* 3) return the best of the 4 choices
*
* *fmyP,fmxP,bmyP,bmxP are inputs as well as outputs. We do not update
* them if it would make the error worse than the existing values. Otherwise,
* we update them to the vectors we find to be best.
*===========================================================================*/
static int
BMotionSearchCross2(const LumBlock * const currentBlockP,
MpegFrame * const prev,
MpegFrame * const next,
int const by,
int const bx,
motion * const motionP,
int const oldMode) {
int retval;
LumBlock forwardBlock, backBlock;
int32 forwardErr, backErr;
motion newMotion;
int32 interpErrF, interpErrB, interpErr;
int32 bestErr;
/* STEP 1 */
BMotionSearchNoInterp(currentBlockP, prev, next, by, bx, motionP,
&forwardErr, &backErr, TRUE);
bestErr = min(forwardErr, backErr);
{
/* STEP 2 */
struct motion motion;
motion.fwd = motionP->fwd;
motion.bwd.y = motion.bwd.x = 0;
ComputeBMotionLumBlock(prev, next, by, bx, MOTION_FORWARD, motion,
&forwardBlock);
motion.fwd.y = motion.fwd.x = 0;
motion.bwd = motionP->bwd;
ComputeBMotionLumBlock(prev, next, by, bx, MOTION_BACKWARD, motion,
&backBlock);
}
/* try a cross-search; total of 4 local searches */
newMotion = *motionP;
interpErrF = FindBestMatch(&forwardBlock, currentBlockP,
next, by, bx, &newMotion.bwd,
bestErr, searchRangeB);
bestErr = min(bestErr, interpErr);
interpErrB = FindBestMatch(&backBlock, currentBlockP,
prev, by, bx, &newMotion.fwd,
bestErr, searchRangeB);
/* STEP 3 */
if (interpErrF <= interpErrB) {
newMotion.fwd = motionP->fwd;
interpErr = interpErrF;
} else {
newMotion.bwd = motionP->bwd;
interpErr = interpErrB;
}
if (interpErr <= forwardErr) {
if (interpErr <= backErr) {
*motionP = newMotion;
retval = MOTION_INTERPOLATE;
} else
retval = MOTION_BACKWARD;
} else if (forwardErr <= backErr)
retval = MOTION_FORWARD;
else
retval = MOTION_BACKWARD;
return retval;
}
/*===========================================================================*
*
* BMotionSearchExhaust
*
* does an exhaustive search for B-frame motion vectors
* see BMotionSearch for generic description
*
* DESCRIPTION:
* 1) find best backward and forward vectors
* 2) use exhaustive search to find best interpolating vectors
* 3) return the best of the 3 choices
*
* *fmyP,fmxP,bmyP,bmxP are inputs as well as outputs. We do not update
* them if it would make the error worse than the existing values. Otherwise,
* we update them to the vectors we find to be best.
*===========================================================================*/
static int
BMotionSearchExhaust(const LumBlock * const currentBlockP,
MpegFrame * const prev,
MpegFrame * const next,
int const by,
int const bx,
motion * const motionP,
int const oldMode) {
int mx, my;
int32 bestDiff;
int stepSize;
LumBlock forwardBlock;
int32 forwardErr, backErr;
int leftMY, leftMX;
int rightMY, rightMX;
boolean result;
/* STEP 1 */
BMotionSearchNoInterp(currentBlockP, prev, next, by, bx, motionP,
&forwardErr, &backErr, FALSE);
if (forwardErr <= backErr) {
bestDiff = forwardErr;
result = MOTION_FORWARD;
} else {
bestDiff = backErr;
result = MOTION_BACKWARD;
}
/* STEP 2 */
stepSize = (pixelFullSearch ? 2 : 1);
COMPUTE_MOTION_BOUNDARY(by,bx,stepSize,leftMY,leftMX,rightMY,rightMX);
if (searchRangeB < rightMY)
rightMY = searchRangeB;
if (searchRangeB < rightMX)
rightMX = searchRangeB;
for (my = -searchRangeB; my < rightMY; my += stepSize) {
if (my >= leftMY) {
for (mx = -searchRangeB; mx < rightMX; mx += stepSize) {
if (mx >= leftMX) {
struct motion motion;
vector newMotion;
int32 diff;
motion.fwd.y = my; motion.fwd.x = mx;
motion.bwd.y = 0; motion.bwd.x = 0;
ComputeBMotionLumBlock(prev, next, by, bx, MOTION_FORWARD,
motion, &forwardBlock);
newMotion = motion.fwd;
diff = FindBestMatch(&forwardBlock,
currentBlockP, next, by, bx,
&newMotion, bestDiff, searchRangeB);
if (diff < bestDiff) {
motionP->fwd = motion.fwd;
motionP->bwd = newMotion;
bestDiff = diff;
result = MOTION_INTERPOLATE;
}
}
}
}
}
return result;
}
/*===========================================================================*
*
* search for the best B-frame motion vectors
*
* RETURNS: MOTION_FORWARD forward motion should be used
* MOTION_BACKWARD backward motion should be used
* MOTION_INTERPOLATE both should be used and interpolated
*
* OUTPUTS: *motionP = TWICE the forward motion vectors
*
* SIDE EFFECTS: none
*
* PRECONDITIONS: The relevant block in 'current' is valid (it has not
* been dct'd). Thus, the data in 'current' can be
* accesed through y_blocks, cr_blocks, and cb_blocks.
* This is not the case for the blocks in 'prev' and
* 'next.' Therefore, references into 'prev' and 'next'
* should be done
* through the struct items ref_y, ref_cr, ref_cb
*
* POSTCONDITIONS: current, prev, next should be unchanged.
* Some computation could be saved by requiring
* the dct'd difference to be put into current's block
* elements here, depending on the search technique.
* However, it was decided that it mucks up the code
* organization a little, and the saving in computation
* would be relatively little (if any).
*
* NOTES: the search procedure MAY return (0,0) motion vectors
*
*===========================================================================*/
int
BMotionSearch(const LumBlock * const currentBlockP,
MpegFrame * const prev,
MpegFrame * const next,
int const by,
int const bx,
motion * const motionP,
int const oldMode) {
int retval;
/* If we are an initial B frame, no possibility of forward motion */
if (prev == (MpegFrame *) NULL) {
PMotionSearch(currentBlockP, next, by, bx, &motionP->bwd);
return MOTION_BACKWARD;
}
/* otherwise simply call the appropriate algorithm, based on user
preference
*/
switch(bsearchAlg) {
case BSEARCH_SIMPLE:
retval = BMotionSearchSimple(currentBlockP, prev, next, by, bx,
motionP, oldMode);
break;
case BSEARCH_CROSS2:
retval = BMotionSearchCross2(currentBlockP, prev, next, by, bx,
motionP, oldMode);
break;
case BSEARCH_EXHAUSTIVE:
retval = BMotionSearchExhaust(currentBlockP, prev, next, by, bx,
motionP, oldMode);
break;
default:
pm_error("Impossible B-frame motion search algorithm: %d",
bsearchAlg);
}
return retval;
}
/*===========================================================================*
* *
* UNUSED PROCEDURES *
* *
* The following procedures are all unused by the encoder *
* *
* They are listed here for your convenience. You might want to use *
* them if you experiment with different search techniques *
* *
*===========================================================================*/
#ifdef UNUSED_PROCEDURES
/*===========================================================================*
*
* ValidBMotion
*
* decides if the given B-frame motion is valid
*
* RETURNS: TRUE if the motion is valid, FALSE otherwise
*
* SIDE EFFECTS: none
*
*===========================================================================*/
boolean
ValidBMotion(by, bx, mode, fmy, fmx, bmy, bmx)
int by;
int bx;
int mode;
int fmy;
int fmx;
int bmy;
int bmx;
{
if ( mode != MOTION_BACKWARD ) {
/* check forward motion for bounds */
if ( (by*DCTSIZE+(fmy-1)/2 < 0) || ((by+2)*DCTSIZE+(fmy+1)/2-1 >= Fsize_y) ) {
return FALSE;
}
if ( (bx*DCTSIZE+(fmx-1)/2 < 0) || ((bx+2)*DCTSIZE+(fmx+1)/2-1 >= Fsize_x) ) {
return FALSE;
}
}
if ( mode != MOTION_FORWARD ) {
/* check backward motion for bounds */
if ( (by*DCTSIZE+(bmy-1)/2 < 0) || ((by+2)*DCTSIZE+(bmy+1)/2-1 >= Fsize_y) ) {
return FALSE;
}
if ( (bx*DCTSIZE+(bmx-1)/2 < 0) || ((bx+2)*DCTSIZE+(bmx+1)/2-1 >= Fsize_x) ) {
return FALSE;
}
}
return TRUE;
}
#endif /* UNUSED_PROCEDURES */