bsearch.c

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

                /* STEP 3 */

    if ( interpErr <= interpErr2 ) {
    newfmy = *fmy;
    newfmx = *fmx;
    }
    else
    {
    newbmy = *bmy;
    newbmx = *bmx;
    interpErr = interpErr2;
    }

    if ( interpErr <= forwardErr ) {
    if ( interpErr <= backErr ) {
        *fmy = newfmy;
        *fmx = newfmx;
        *bmy = newbmy;
        *bmx = newbmx;

        return MOTION_INTERPOLATE;
    }
    else
        return MOTION_BACKWARD;
    } else if ( forwardErr <= backErr ) {
    return MOTION_FORWARD;
    } else {
    return MOTION_BACKWARD;
    }
}


/*===========================================================================*
 *
 * 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
 *
 *===========================================================================*/
static int
BMotionSearchExhaust(currentBlock, prev, next, by, bx, fmy, fmx, bmy, bmx,
            oldMode)
    LumBlock currentBlock;
    MpegFrame *prev;
    MpegFrame *next;
    int by;
    int bx;
    int *fmy;
    int *fmx;
    int *bmy;
    int *bmx;
    int oldMode;
{
    register int mx, my;
    int32 diff, bestDiff;
    int     stepSize;
    LumBlock    forwardBlock;
    int32   forwardErr, backErr;
    int     newbmy, newbmx;
    int     leftMY, leftMX;
    int     rightMY, rightMX;
    boolean result;

                /* STEP 1 */

    BMotionSearchNoInterp(currentBlock, prev, next, by, bx, fmy, fmx,
              &forwardErr, bmy, bmx, &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 ) {
        continue;
    }

    for ( mx = -searchRangeB; mx < rightMX; mx += stepSize ) {
        if ( mx < leftMX ) {
        continue;
        }

        ComputeBMotionLumBlock(prev, next, by, bx, MOTION_FORWARD,
               my, mx, 0, 0, forwardBlock);

        newbmy = my;    newbmx = mx;

        diff = FindBestMatch(forwardBlock, currentBlock, next, by, bx,
                 &newbmy, &newbmx, bestDiff, searchRangeB);

        if ( diff < bestDiff ) {
        *fmy = my;
        *fmx = mx;
        *bmy = newbmy;
        *bmx = newbmx;
        bestDiff = diff;
        result = MOTION_INTERPOLATE;
        }
    }
    }

    return result;
}


/*===========================================================================*
 *
 * 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(block, currentBlock, prev, by, bx, motionY, motionX, bestSoFar, searchRange)
    LumBlock block;
    LumBlock currentBlock;
    MpegFrame *prev;
    int by;
    int bx;
    int *motionY;
    int *motionX;
    int32 bestSoFar;
    int searchRange;
{
    int32   result;

    switch(psearchAlg) {
    case PSEARCH_SUBSAMPLE:
        result = FindBestMatchSubSample(block, currentBlock, prev, by, bx,
                        motionY, motionX, bestSoFar, searchRange);
        break;
    case PSEARCH_EXHAUSTIVE:
        result = FindBestMatchExhaust(block, currentBlock, prev, by, bx,
                      motionY, motionX, bestSoFar, searchRange);
        break;
    case PSEARCH_LOGARITHMIC:
        result = FindBestMatchLogarithmic(block, currentBlock, prev, by, bx,
                          motionY, motionX, bestSoFar, searchRange);
        break;
    case PSEARCH_TWOLEVEL:
        result = FindBestMatchTwoLevel(block, currentBlock, prev, by, bx,
                       motionY, motionX, bestSoFar, searchRange);
        break;
    default:
        fprintf(stderr, "ERROR:  Illegal P-search alg %d\n", psearchAlg);
        exit(1);
    }

    return result;
}


/*===========================================================================*
 *
 * FindBestMatchExhaust
 *
 *  tries to find matching motion vector
 *  see FindBestMatch for generic description
 *
 * DESCRIPTION:  uses an exhaustive search
 *
 *===========================================================================*/
static int32
FindBestMatchExhaust(block, currentBlock, prev, by, bx, motionY, motionX,
             bestSoFar, searchRange)
    LumBlock block;
    LumBlock currentBlock;
    MpegFrame *prev;
    int by;
    int bx;
    int *motionY;
    int *motionX;
    int32 bestSoFar;
    int searchRange;
{
    register int mx, my;
    int32 diff, 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(*motionY, *motionX) ) {
    bestDiff = LumAddMotionError(currentBlock, block, prev, by, bx,
                     *motionY, *motionX, bestSoFar);

    if ( bestSoFar < bestDiff ) {
        bestDiff = bestSoFar;
    }
    }
    else
    {
    *motionY = 0;
    *motionX = 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 = rightMY;
    if ( distance < tempRightMY ) {
        tempRightMY = distance;
    }
    tempRightMX = rightMX;
    if ( distance < tempRightMX ) {
        tempRightMX = distance;
    }

    /* do top, bottom */
    for ( my = -distance; my < tempRightMY;
          my += max(tempRightMY+distance-stepSize, stepSize) ) {
        if ( my < leftMY ) {
        continue;
        }

        for ( mx = -distance; mx < tempRightMX; mx += stepSize ) {
        if ( mx < leftMX ) {
            continue;
        }

        diff = LumAddMotionError(currentBlock, block, prev, by, bx,
                     my, mx, bestDiff);

        if ( diff < bestDiff ) {
            *motionY = my;
            *motionX = mx;
            bestDiff = diff;
        }
        }
    }

    /* do left, right */
    for ( mx = -distance; mx < tempRightMX; mx += max(tempRightMX+distance-stepSize, stepSize) ) {
        if ( mx < leftMX ) {
        continue;
        }

        for ( my = -distance+stepSize; my < tempRightMY-stepSize; my += stepSize ) {
        if ( my < leftMY ) {
            continue;
        }

        diff = LumAddMotionError(currentBlock, block, prev, by, bx,
                     my, mx, bestDiff);

        if ( diff < bestDiff ) {
            *motionY = my;
            *motionX = mx;
            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(block, currentBlock, prev, by, bx, motionY, motionX,
              bestSoFar, searchRange)
    LumBlock block;
    LumBlock currentBlock;
    MpegFrame *prev;
    int by;
    int bx;
    int *motionY;
    int *motionX;
    int32 bestSoFar;
    int searchRange;
{
    register int mx, my;
    int32 diff, 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 ( *motionY > 0 ) {
    if ( ((*motionY) % 2) == 1 ) {
        (*motionY)--;
    }
    } else if ( ((-(*motionY)) % 2) == 1 ) {
    (*motionY)++;
    }

    if ( *motionX > 0 ) {
    if ( ((*motionX) % 2) == 1 ) {
        (*motionX)--;
    }
    } else if ( ((-(*motionX)) % 2) == 1 ) {
    (*motionX)++;
    }

    /* try old motion vector first */
    if ( VALID_MOTION(*motionY, *motionX) ) {
    bestDiff = LumAddMotionError(currentBlock, block, prev, by, bx,
                     *motionY, *motionX, bestSoFar);

    if ( bestSoFar < bestDiff ) {
        bestDiff = bestSoFar;
    }
    }
    else
    {
    *motionY = 0;
    *motionX = 0;

    bestDiff = bestSoFar;
    }

    rightMY++;
    rightMX++;

/* maybe should try spiral pattern centered around  prev motion vector? */