home *** CD-ROM | disk | FTP | other *** search
/ DP Tool Club 9 / CD_ASCQ_09_1193.iso / news / 4441 / mpegcode / src / psearch.c < prev    next >
C/C++ Source or Header  |  1993-09-27  |  20KB  |  824 lines
  1. /*===========================================================================*
  2.  * psearch.c                                     *
  3.  *                                         *
  4.  *    Procedures concerned with the P-frame motion search             *
  5.  *                                         *
  6.  * EXPORTED PROCEDURES:                                 *
  7.  *    SetPixelSearch                                 *
  8.  *    SetPSearchAlg                                 *
  9.  *    SetSearchRange                                 *
  10.  *    MotionSearchPreComputation                         *
  11.  *    PMotionSearch                                 *
  12.  *    PSearchName                                 *
  13.  *    PSubSampleSearch                             *
  14.  *    PLogarithmicSearch                             *
  15.  *                                         *
  16.  *===========================================================================*/
  17.  
  18. /*
  19.  * Copyright (c) 1993 The Regents of the University of California.
  20.  * All rights reserved.
  21.  *
  22.  * Permission to use, copy, modify, and distribute this software and its
  23.  * documentation for any purpose, without fee, and without written agreement is
  24.  * hereby granted, provided that the above copyright notice and the following
  25.  * two paragraphs appear in all copies of this software.
  26.  *
  27.  * IN NO EVENT SHALL THE UNIVERSITY OF CALIFORNIA BE LIABLE TO ANY PARTY FOR
  28.  * DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES ARISING OUT
  29.  * OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN IF THE UNIVERSITY OF
  30.  * CALIFORNIA HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  31.  *
  32.  * THE UNIVERSITY OF CALIFORNIA SPECIFICALLY DISCLAIMS ANY WARRANTIES,
  33.  * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY
  34.  * AND FITNESS FOR A PARTICULAR PURPOSE.  THE SOFTWARE PROVIDED HEREUNDER IS
  35.  * ON AN "AS IS" BASIS, AND THE UNIVERSITY OF CALIFORNIA HAS NO OBLIGATION TO
  36.  * PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS.
  37.  */
  38.  
  39. /*  
  40.  *  $Header: /n/picasso/users/keving/encode/src/RCS/psearch.c,v 1.4 1993/07/22 22:23:43 keving Exp keving $
  41.  *  $Log: psearch.c,v $
  42.  * Revision 1.4  1993/07/22  22:23:43  keving
  43.  * nothing
  44.  *
  45.  * Revision 1.3  1993/06/30  20:06:09  keving
  46.  * nothing
  47.  *
  48.  * Revision 1.2  1993/06/03  21:08:08  keving
  49.  * nothing
  50.  *
  51.  * Revision 1.1  1993/03/02  18:27:05  keving
  52.  * nothing
  53.  *
  54.  */
  55.  
  56.  
  57. /*==============*
  58.  * HEADER FILES *
  59.  *==============*/
  60.  
  61. #include "all.h"
  62. #include "mtypes.h"
  63. #include "frames.h"
  64. #include "search.h"
  65. #include "prototypes.h"
  66. #include "fsize.h"
  67.  
  68.  
  69. /*==================*
  70.  * STATIC VARIABLES *
  71.  *==================*/
  72.  
  73.     /* none */
  74.  
  75.  
  76. /*==================*
  77.  * GLOBAL VARIABLES *
  78.  *==================*/
  79.  
  80. int pixelFullSearch;
  81. int searchRange;
  82. int psearchAlg;
  83.  
  84.  
  85. /*===============================*
  86.  * INTERNAL PROCEDURE prototypes *
  87.  *===============================*/
  88.  
  89.  
  90. /*=====================*
  91.  * EXPORTED PROCEDURES *
  92.  *=====================*/
  93.  
  94. /*===========================================================================*
  95.  *
  96.  * PMotionSearch
  97.  *
  98.  *    compute the best P-frame motion vector we can
  99.  *    
  100.  *
  101.  * RETURNS:    TRUE        =    motion vector valid
  102.  *        FALSE        =    motion vector invalid; should code I-block
  103.  *
  104.  * PRECONDITIONS:    The relevant block in 'current' is valid (it has not
  105.  *            been dct'd).  Thus, the data in 'current' can be
  106.  *            accesed through y_blocks, cr_blocks, and cb_blocks.
  107.  *            This is not the case for the blocks in 'prev.'
  108.  *            Therefore, references into 'prev' should be done
  109.  *            through the struct items ref_y, ref_cr, ref_cb
  110.  *
  111.  * POSTCONDITIONS:    current, prev should be unchanged.
  112.  *            Some computation could be saved by requiring
  113.  *            the dct'd difference to be put into current's block
  114.  *            elements here, depending on the search technique.
  115.  *            However, it was decided that it mucks up the code
  116.  *            organization a little, and the saving in computation
  117.  *            would be relatively little (if any).
  118.  *
  119.  * NOTES:    the search procedure need not check the (0,0) motion vector
  120.  *        the calling procedure has a preference toward (0,0) and it
  121.  *        will check it itself
  122.  *
  123.  * SIDE EFFECTS:    none
  124.  *
  125.  *===========================================================================*/
  126. boolean
  127. PMotionSearch(currentBlock, prev, by, bx, motionY, motionX)
  128.     LumBlock currentBlock;
  129.     MpegFrame *prev;
  130.     int by;
  131.     int bx;
  132.     int *motionY;
  133.     int *motionX;
  134. {
  135.     /* CALL SEARCH PROCEDURE */
  136.  
  137.     switch(psearchAlg) {
  138.     case PSEARCH_SUBSAMPLE:
  139.         PSubSampleSearch(currentBlock, prev, by, bx, motionY, motionX);
  140.         break;
  141.     case PSEARCH_EXHAUSTIVE:
  142.         PLocalSearch(currentBlock, prev, by, bx, motionY, motionX,
  143.              0x7fffffff);
  144.         break;
  145.     case PSEARCH_LOGARITHMIC:
  146.         PLogarithmicSearch(currentBlock, prev, by, bx, motionY, motionX);
  147.         break;
  148.     case PSEARCH_TWOLEVEL:
  149.         PTwoLevelSearch(currentBlock, prev, by, bx, motionY, motionX,
  150.                 0x7fffffff);
  151.         break;
  152.     default:
  153.         fprintf(stderr, "ILLEGAL PSEARCH ALG:  %d\n", psearchAlg);
  154.         exit(1);
  155.     }
  156.  
  157.     return TRUE;
  158. }
  159.  
  160.  
  161. /*===========================================================================*
  162.  *
  163.  * SetPixelSearch
  164.  *
  165.  *    set the pixel search type (half or full)
  166.  *
  167.  * RETURNS:    nothing
  168.  *
  169.  * SIDE EFFECTS:    pixelFullSearch
  170.  *
  171.  *===========================================================================*/
  172. void
  173. SetPixelSearch(searchType)
  174.     char *searchType;
  175. {
  176.     if ( strcmp(searchType, "FULL") == 0 ) {
  177.     pixelFullSearch = TRUE;
  178.     } else if ( strcmp(searchType, "HALF") == 0 ) {
  179.     pixelFullSearch = FALSE;
  180.     } else {
  181.     fprintf(stderr, "ERROR:  Invalid pixel search type:  %s\n",
  182.         searchType);
  183.     exit(1);
  184.     }
  185. }
  186.  
  187.  
  188. /*===========================================================================*
  189.  *
  190.  * SetPSearchAlg
  191.  *
  192.  *    set the P-search algorithm
  193.  *
  194.  * RETURNS:    nothing
  195.  *
  196.  * SIDE EFFECTS:    psearchAlg
  197.  *
  198.  *===========================================================================*/
  199. void
  200. SetPSearchAlg(alg)
  201.     char *alg;
  202. {
  203.     if ( strcmp(alg, "EXHAUSTIVE") == 0 ) {
  204.     psearchAlg = PSEARCH_EXHAUSTIVE;
  205.     } else if (strcmp(alg, "SUBSAMPLE") == 0 ) {
  206.     psearchAlg = PSEARCH_SUBSAMPLE;
  207.     } else if ( strcmp(alg, "LOGARITHMIC") == 0 ) {
  208.     psearchAlg = PSEARCH_LOGARITHMIC;
  209.     } else if ( strcmp(alg, "TWOLEVEL") == 0 ) {
  210.     psearchAlg = PSEARCH_TWOLEVEL;
  211.     } else {
  212.     fprintf(stderr, "ERROR:  Invalid psearch algorithm:  %s\n", alg);
  213.     exit(1);
  214.     }
  215. }
  216.  
  217.  
  218. /*===========================================================================*
  219.  *
  220.  * PSearchName
  221.  *
  222.  *    returns a string containing the name of the search algorithm
  223.  *
  224.  * RETURNS:    pointer to the string
  225.  *
  226.  * SIDE EFFECTS:    none
  227.  *
  228.  *===========================================================================*/
  229. char *
  230. PSearchName()
  231. {
  232.     switch(psearchAlg) {
  233.     case PSEARCH_EXHAUSTIVE:
  234.         return "EXHAUSTIVE";
  235.     case PSEARCH_SUBSAMPLE:
  236.         return "SUBSAMPLE";
  237.     case PSEARCH_LOGARITHMIC:
  238.         return "LOGARITHMIC";
  239.     case PSEARCH_TWOLEVEL:
  240.         return "TWOLEVEL";
  241.     default:
  242.         exit(1);
  243.         break;
  244.     }
  245. }
  246.  
  247.  
  248. /*===========================================================================*
  249.  *
  250.  * SetSearchRange
  251.  *
  252.  *    sets the range of the search to the given number of pixels
  253.  *
  254.  * RETURNS:    nothing
  255.  *
  256.  * SIDE EFFECTS:    searchRange, fCode
  257.  *
  258.  *===========================================================================*/
  259. void
  260. SetSearchRange(pixels)
  261.     int pixels;
  262. {
  263.     searchRange = 2*pixels;    /* +/- 'pixels' pixels */
  264. }
  265.  
  266.  
  267. /*===========================================================================*
  268.  *
  269.  *                USER-MODIFIABLE
  270.  *
  271.  * MotionSearchPreComputation
  272.  *
  273.  *    do whatever you want here; this is called once per frame, directly
  274.  *    after reading
  275.  *
  276.  * RETURNS:    whatever
  277.  *
  278.  * SIDE EFFECTS:    whatever
  279.  *
  280.  *===========================================================================*/
  281. void
  282. MotionSearchPreComputation(frame)
  283.     MpegFrame *frame;
  284. {
  285.     /* do nothing */
  286. }
  287.  
  288.  
  289. /*===========================================================================*
  290.  *
  291.  * PSubSampleSearch
  292.  *
  293.  *    uses the subsampling algorithm to compute the P-frame vector
  294.  *
  295.  * RETURNS:    motion vector
  296.  *
  297.  * SIDE EFFECTS:    none
  298.  *
  299.  * REFERENCE:  Liu and Zaccarin:  New Fast Algorithms for the Estimation
  300.  *        of Block Motion Vectors, IEEE Transactions on Circuits
  301.  *        and Systems for Video Technology, Vol. 3, No. 2, 1993.
  302.  *
  303.  *===========================================================================*/
  304. int32
  305. PSubSampleSearch(currentBlock, prev, by, bx, motionY, motionX)
  306.     LumBlock currentBlock;
  307.     MpegFrame *prev;
  308.     int by;
  309.     int bx;
  310.     int *motionY;
  311.     int *motionX;
  312. {
  313.     register int mx, my;
  314.     int32 diff, bestBestDiff;
  315.     int        stepSize;
  316.     register int x;
  317.     int        bestMY[4], bestMX[4], bestDiff[4];
  318.     int        leftMY, leftMX;
  319.     int        rightMY, rightMX;
  320.  
  321.     stepSize = (pixelFullSearch ? 2 : 1);
  322.  
  323.     COMPUTE_MOTION_BOUNDARY(by,bx,stepSize,leftMY,leftMX,rightMY,rightMX);
  324.  
  325.     if ( searchRange < rightMY ) {
  326.     rightMY = searchRange;
  327.     }
  328.  
  329.     if ( searchRange < rightMX ) {
  330.     rightMX = searchRange;
  331.     }
  332.  
  333.     for ( x = 0; x < 4; x++ ) {
  334.     bestMY[x] = 0;
  335.     bestMX[x] = 0;
  336.     bestDiff[x] = 0x7fffffff;
  337.     }
  338.  
  339.     /* do A pattern */
  340.     for ( my = -searchRange; my < rightMY; my += 2*stepSize ) {
  341.     if ( my < leftMY ) {
  342.         continue;
  343.     }
  344.  
  345.     for ( mx = -searchRange; mx < rightMX; mx += 2*stepSize ) {
  346.         if ( mx < leftMX ) {
  347.         continue;
  348.         }
  349.  
  350.         diff = LumMotionErrorA(currentBlock, prev, by, bx, my, mx, bestDiff[0]);
  351.  
  352.         if ( diff < bestDiff[0] ) {
  353.         bestMY[0] = my;
  354.         bestMX[0] = mx;
  355.         bestDiff[0] = diff;
  356.         }
  357.     }
  358.     }
  359.  
  360.     /* do B pattern */
  361.     for ( my = stepSize-searchRange; my < rightMY; my += 2*stepSize ) {
  362.     if ( my < leftMY ) {
  363.         continue;
  364.     }
  365.  
  366.     for ( mx = -searchRange; mx < rightMX; mx += 2*stepSize ) {
  367.         if ( mx < leftMX ) {
  368.         continue;
  369.         }
  370.  
  371.         diff = LumMotionErrorB(currentBlock, prev, by, bx, my, mx, bestDiff[1]);
  372.  
  373.         if ( diff < bestDiff[1] ) {
  374.         bestMY[1] = my;
  375.         bestMX[1] = mx;
  376.         bestDiff[1] = diff;
  377.         }
  378.     }
  379.     }
  380.  
  381.     /* do C pattern */
  382.     for ( my = stepSize-searchRange; my < rightMY; my += 2*stepSize ) {
  383.     if ( my < leftMY ) {
  384.         continue;
  385.     }
  386.  
  387.     for ( mx = stepSize-searchRange; mx < rightMX; mx += 2*stepSize ) {
  388.         if ( mx < leftMX ) {
  389.         continue;
  390.         }
  391.  
  392.         diff = LumMotionErrorC(currentBlock, prev, by, bx, my, mx, bestDiff[2]);
  393.  
  394.         if ( diff < bestDiff[2] ) {
  395.         bestMY[2] = my;
  396.         bestMX[2] = mx;
  397.         bestDiff[2] = diff;
  398.         }
  399.     }
  400.     }
  401.  
  402.     /* do D pattern */
  403.     for ( my = -searchRange; my < rightMY; my += 2*stepSize ) {
  404.     if ( my < leftMY ) {
  405.         continue;
  406.     }
  407.  
  408.     for ( mx = stepSize-searchRange; mx < rightMX; mx += 2*stepSize ) {
  409.         if ( mx < leftMX ) {
  410.         continue;
  411.         }
  412.  
  413.         diff = LumMotionErrorD(currentBlock, prev, by, bx, my, mx, bestDiff[3]);
  414.  
  415.         if ( diff < bestDiff[3] ) {
  416.         bestMY[3] = my;
  417.         bestMX[3] = mx;
  418.         bestDiff[3] = diff;
  419.         }
  420.     }
  421.     }
  422.  
  423.     /* first check old motion */
  424.     if ( (*motionY >= leftMY) && (*motionY < rightMY) &&
  425.      (*motionX >= leftMX) && (*motionX < rightMX) ) {
  426.     bestBestDiff = LumMotionError(currentBlock, prev, by, bx, *motionY, *motionX, 0x7fffffff);
  427.     } else {
  428.     bestBestDiff = 0x7fffffff;
  429.     }
  430.  
  431.     /* look at Error of 4 different motion vectors */
  432.     for ( x = 0; x < 4; x++ ) {
  433.     bestDiff[x] = LumMotionError(currentBlock, prev, by, bx,
  434.                  bestMY[x], bestMX[x], bestBestDiff);
  435.  
  436.     if ( bestDiff[x] < bestBestDiff ) {
  437.         bestBestDiff = bestDiff[x];
  438.         *motionY = bestMY[x];
  439.         *motionX = bestMX[x];
  440.     }
  441.     }
  442.  
  443.     return bestBestDiff;
  444. }
  445.  
  446.  
  447. /*===========================================================================*
  448.  *
  449.  * PLogarithmicSearch
  450.  *
  451.  *    uses logarithmic search to compute the P-frame vector
  452.  *
  453.  * RETURNS:    motion vector
  454.  *
  455.  * SIDE EFFECTS:    none
  456.  *
  457.  * REFERENCE:  MPEG-I specification, pages 32-33
  458.  *
  459.  *===========================================================================*/
  460. int32
  461. PLogarithmicSearch(currentBlock, prev, by, bx, motionY, motionX)
  462.     LumBlock currentBlock;
  463.     MpegFrame *prev;
  464.     int by;
  465.     int bx;
  466.     int *motionY;
  467.     int *motionX;
  468. {
  469.     register int mx, my;
  470.     int32 diff, bestDiff;
  471.     int        stepSize;
  472.     int        leftMY, leftMX;
  473.     int        rightMY, rightMX;
  474.     int        tempRightMY, tempRightMX;
  475.     int        spacing;
  476.     int        centerX, centerY;
  477.     int        newCenterX, newCenterY;
  478.  
  479.     stepSize = (pixelFullSearch ? 2 : 1);
  480.  
  481.     COMPUTE_MOTION_BOUNDARY(by,bx,stepSize,leftMY,leftMX,rightMY,rightMX);
  482.  
  483.     bestDiff = 0x7fffffff;
  484.  
  485.     /* grid spacing */
  486.     if ( stepSize == 2 ) {    /* make sure spacing is even */
  487.     spacing = (searchRange+1)/2;
  488.     if ( (spacing % 2) != 0 ) {
  489.         spacing++;
  490.     }
  491.     } else {
  492.     spacing = (searchRange+1)/2;
  493.     }
  494.     centerX = 0;
  495.     centerY = 0;
  496.  
  497.     while ( spacing >= stepSize ) {
  498.     newCenterY = centerY;
  499.     newCenterX = centerX;
  500.  
  501.     tempRightMY = rightMY;
  502.     if ( centerY+spacing+1 < tempRightMY ) {
  503.         tempRightMY = centerY+spacing+1;
  504.     }
  505.     tempRightMX = rightMX;
  506.     if ( centerX+spacing+1 < tempRightMX ) {
  507.         tempRightMX = centerX+spacing+1;
  508.     }
  509.  
  510.     for ( my = centerY-spacing; my < tempRightMY; my += spacing ) {
  511.         if ( my < leftMY ) {
  512.         continue;
  513.         }
  514.  
  515.         for ( mx = centerX-spacing; mx < tempRightMX; mx += spacing ) {
  516.         if ( mx < leftMX ) {
  517.             continue;
  518.         }
  519.  
  520.         diff = LumMotionError(currentBlock, prev, by, bx, my, mx, bestDiff);
  521.  
  522.         if ( diff < bestDiff ) {
  523.             newCenterY = my;
  524.             newCenterX = mx;
  525.  
  526.             bestDiff = diff;
  527.         }
  528.         }
  529.     }
  530.  
  531.     centerY = newCenterY;
  532.     centerX = newCenterX;
  533.  
  534.     if ( stepSize == 2 ) {    /* make sure spacing is even */
  535.         if ( spacing == 2 ) {
  536.         spacing = 0;
  537.         } else {
  538.         spacing = (spacing+1)/2;
  539.         if ( (spacing % 2) != 0 ) {
  540.             spacing++;
  541.         }
  542.         }
  543.     } else {
  544.         if ( spacing == 1 ) {
  545.         spacing = 0;
  546.         } else {
  547.         spacing = (spacing+1)/2;
  548.         }
  549.     }
  550.     }
  551.  
  552.     /* check old motion -- see if it's better */
  553.     if ( (*motionY >= leftMY) && (*motionY < rightMY) &&
  554.      (*motionX >= leftMX) && (*motionX < rightMX) ) {
  555.     diff = LumMotionError(currentBlock, prev, by, bx, *motionY, *motionX, bestDiff);
  556.     } else {
  557.     diff = 0x7fffffff;
  558.     }
  559.  
  560.     if ( bestDiff < diff ) {
  561.     *motionY = centerY;
  562.     *motionX = centerX;
  563.     } else {
  564.     bestDiff = diff;
  565.     }
  566.  
  567.     return bestDiff;
  568. }
  569.  
  570.  
  571. /*===========================================================================*
  572.  *
  573.  * PLocalSearch
  574.  *
  575.  *    uses local exhaustive search to compute the P-frame vector
  576.  *
  577.  * RETURNS:    motion vector
  578.  *
  579.  * SIDE EFFECTS:    none
  580.  *
  581.  *===========================================================================*/
  582. int32
  583. PLocalSearch(currentBlock, prev, by, bx, motionY, motionX, bestSoFar)
  584.     LumBlock currentBlock;
  585.     MpegFrame *prev;
  586.     int by;
  587.     int bx;
  588.     int *motionY;
  589.     int *motionX;
  590.     int32 bestSoFar;
  591. {
  592.     register int mx, my;
  593.     int32 diff, bestDiff;
  594.     int        stepSize;
  595.     int        leftMY, leftMX;
  596.     int        rightMY, rightMX;
  597.     int        distance;
  598.     int        tempRightMY, tempRightMX;
  599.  
  600.     stepSize = (pixelFullSearch ? 2 : 1);
  601.  
  602.     COMPUTE_MOTION_BOUNDARY(by,bx,stepSize,leftMY,leftMX,rightMY,rightMX);
  603.  
  604.     /* try old motion vector first */
  605.     if ( VALID_MOTION(*motionY, *motionX) ) {
  606.     bestDiff = LumMotionError(currentBlock, prev, by, bx, *motionY, *motionX, bestSoFar);
  607.  
  608.     if ( bestSoFar < bestDiff ) {
  609.         bestDiff = bestSoFar;
  610.     }
  611.     } else {
  612.     *motionY = 0;
  613.     *motionX = 0;
  614.  
  615.     bestDiff = bestSoFar;
  616.     }
  617.  
  618.     /* try a spiral pattern */    
  619.     for ( distance = stepSize; distance <= searchRange;
  620.       distance += stepSize ) {
  621.     tempRightMY = rightMY;
  622.     if ( distance < tempRightMY ) {
  623.         tempRightMY = distance;
  624.     }
  625.     tempRightMX = rightMX;
  626.     if ( distance < tempRightMX ) {
  627.         tempRightMX = distance;
  628.     }
  629.  
  630.     /* do top, bottom */
  631.     for ( my = -distance; my < tempRightMY;
  632.           my += max(tempRightMY+distance-stepSize, stepSize) ) {
  633.         if ( my < leftMY ) {
  634.         continue;
  635.         }
  636.  
  637.         for ( mx = -distance; mx < tempRightMX; mx += stepSize ) {
  638.         if ( mx < leftMX ) {
  639.             continue;
  640.         }
  641.  
  642.         diff = LumMotionError(currentBlock, prev, by, bx, my, mx, bestDiff);
  643.  
  644.         if ( diff < bestDiff ) {
  645.             *motionY = my;
  646.             *motionX = mx;
  647.             bestDiff = diff;
  648.         }
  649.         }
  650.     }
  651.  
  652.     /* do left, right */
  653.     for ( mx = -distance; mx < tempRightMX;
  654.           mx += max(tempRightMX+distance-stepSize, stepSize) ) {
  655.         if ( mx < leftMX ) {
  656.         continue;
  657.         }
  658.  
  659.         for ( my = -distance+stepSize; my < tempRightMY-stepSize;
  660.           my += stepSize ) {
  661.         if ( my < leftMY ) {
  662.             continue;
  663.         }
  664.  
  665.         diff = LumMotionError(currentBlock, prev, by, bx, my, mx, bestDiff);
  666.  
  667.         if ( diff < bestDiff ) {
  668.             *motionY = my;
  669.             *motionX = mx;
  670.             bestDiff = diff;
  671.         }
  672.         }
  673.     }
  674.     }
  675.  
  676.     return bestDiff;
  677. }
  678.  
  679.  
  680. /*===========================================================================*
  681.  *
  682.  * PTwoLevelSearch
  683.  *
  684.  *    uses two-level search to compute the P-frame vector
  685.  *    first does exhaustive full-pixel search, then looks at neighboring
  686.  *    half-pixel motion vectors
  687.  *
  688.  * RETURNS:    motion vector
  689.  *
  690.  * SIDE EFFECTS:    none
  691.  *
  692.  *===========================================================================*/
  693. int32
  694. PTwoLevelSearch(currentBlock, prev, by, bx, motionY, motionX, bestSoFar)
  695.     LumBlock currentBlock;
  696.     MpegFrame *prev;
  697.     int by;
  698.     int bx;
  699.     int *motionY;
  700.     int *motionX;
  701.     int32 bestSoFar;
  702. {
  703.     register int mx, my;
  704.     register int   loopInc;
  705.     int32 diff, bestDiff;
  706.     int        leftMY, leftMX;
  707.     int        rightMY, rightMX;
  708.     int        distance;
  709.     int        tempRightMY, tempRightMX;
  710.     int        xOffset, yOffset;
  711.  
  712.     /* exhaustive full-pixel search first */
  713.  
  714.     COMPUTE_MOTION_BOUNDARY(by,bx,2,leftMY,leftMX,rightMY,rightMX);
  715.  
  716.     rightMY--;
  717.     rightMX--;
  718.  
  719.     /* try old motion vector first */
  720.     if ( VALID_MOTION(*motionY, *motionX) ) {
  721.     bestDiff = LumMotionError(currentBlock, prev, by, bx, *motionY, *motionX, bestSoFar);
  722.  
  723.     if ( bestSoFar < bestDiff ) {
  724.         bestDiff = bestSoFar;
  725.     }
  726.     } else {
  727.     *motionY = 0;
  728.     *motionX = 0;
  729.  
  730.     bestDiff = bestSoFar;
  731.     }
  732.  
  733.     rightMY++;
  734.     rightMX++;
  735.  
  736.     /* try a spiral pattern */    
  737.     for ( distance = 2; distance <= searchRange; distance += 2 ) {
  738.     tempRightMY = rightMY;
  739.     if ( distance < tempRightMY ) {
  740.         tempRightMY = distance;
  741.     }
  742.     tempRightMX = rightMX;
  743.     if ( distance < tempRightMX ) {
  744.         tempRightMX = distance;
  745.     }
  746.  
  747.     /* do top, bottom */
  748.     loopInc = max(tempRightMY+distance-2, 2);
  749.     for ( my = -distance; my < tempRightMY; my += loopInc ) {
  750.         if ( my < leftMY ) {
  751.         continue;
  752.         }
  753.  
  754.         for ( mx = -distance; mx < tempRightMX; mx += 2 ) {
  755.         if ( mx < leftMX ) {
  756.             continue;
  757.         }
  758.  
  759.         diff = LumMotionError(currentBlock, prev, by, bx, my, mx, bestDiff);
  760.  
  761.         if ( diff < bestDiff ) {
  762.             *motionY = my;
  763.             *motionX = mx;
  764.             bestDiff = diff;
  765.         }
  766.         }
  767.     }
  768.  
  769.     /* do left, right */
  770.     loopInc = max(tempRightMX+distance-2, 2);
  771.     for ( mx = -distance; mx < tempRightMX; mx += loopInc ) {
  772.         if ( mx < leftMX ) {
  773.         continue;
  774.         }
  775.  
  776.         for ( my = -distance+2; my < tempRightMY-2; my += 2 ) {
  777.         if ( my < leftMY ) {
  778.             continue;
  779.         }
  780.  
  781.         diff = LumMotionError(currentBlock, prev, by, bx, my, mx, bestDiff);
  782.  
  783.         if ( diff < bestDiff ) {
  784.             *motionY = my;
  785.             *motionX = mx;
  786.             bestDiff = diff;
  787.         }
  788.         }
  789.     }
  790.     }
  791.  
  792.     /* now look at neighboring half-pixels */
  793.     my = *motionY;
  794.     mx = *motionX;
  795.  
  796.     rightMY--;
  797.     rightMX--;
  798.  
  799.     for ( yOffset = -1; yOffset <= 1; yOffset++ ) {
  800.     for ( xOffset = -1; xOffset <= 1; xOffset++ ) {
  801.         if ( (yOffset == 0) && (xOffset == 0) )
  802.         continue;
  803.  
  804.         if ( VALID_MOTION(my+yOffset, mx+xOffset) &&
  805.          ((diff = LumMotionError(currentBlock, prev, by, bx,
  806.              my+yOffset, mx+xOffset, bestDiff)) < bestDiff) ) {
  807.         *motionY = my+yOffset;
  808.         *motionX = mx+xOffset;
  809.         bestDiff = diff;
  810.         }
  811.     }
  812.     }
  813.  
  814.     return bestDiff;
  815. }
  816.  
  817.  
  818. /*=====================*
  819.  * INTERNAL PROCEDURES *
  820.  *=====================*/
  821.  
  822.     /* none */
  823.  
  824.