00001 /*===========================================================================*
00002  * psearch.c                                                                 *
00003  *                                                                           *
00004  *      Procedures concerned with the P-frame motion search                  *
00005  *                                                                           *
00006  * EXPORTED PROCEDURES:                                                      *
00007  *      SetPixelSearch                                                       *
00008  *      SetPSearchAlg                                                        *
00009  *      SetSearchRange                                                       *
00010  *      MotionSearchPreComputation                                           *
00011  *      PMotionSearch                                                        *
00012  *      PSearchName                                                          *
00013  *      PSubSampleSearch                                                     *
00014  *      PLogarithmicSearch                                                   *
00015  *                                                                           *
00016  *===========================================================================*/
00017 
00018 /*
00019  * Copyright (c) 1995 The Regents of the University of California.
00020  * All rights reserved.
00021  *
00022  * Permission to use, copy, modify, and distribute this software and its
00023  * documentation for any purpose, without fee, and without written agreement is
00024  * hereby granted, provided that the above copyright notice and the following
00025  * two paragraphs appear in all copies of this software.
00026  *
00027  * IN NO EVENT SHALL THE UNIVERSITY OF CALIFORNIA BE LIABLE TO ANY PARTY FOR
00028  * DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES ARISING OUT
00029  * OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN IF THE UNIVERSITY OF
00030  * CALIFORNIA HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
00031  *
00032  * THE UNIVERSITY OF CALIFORNIA SPECIFICALLY DISCLAIMS ANY WARRANTIES,
00033  * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY
00034  * AND FITNESS FOR A PARTICULAR PURPOSE.  THE SOFTWARE PROVIDED HEREUNDER IS
00035  * ON AN "AS IS" BASIS, AND THE UNIVERSITY OF CALIFORNIA HAS NO OBLIGATION TO
00036  * PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS.
00037  */
00038 
00039 /*  
00040  *  $Header: /misc/elrond0/share/cvs/AFNI/src/mpeg_encodedir/psearch.c,v 1.4 2004/04/02 15:12:41 rwcox Exp $
00041  *  $Log: psearch.c,v $
00042  *  Revision 1.4  2004/04/02 15:12:41  rwcox
00043  *  Cput
00044  *
00045  *  Revision 1.3  2003/12/23 13:50:08  rwcox
00046  *  Cput
00047  *
00048  *  Revision 1.2  2003/12/03 14:46:14  rwcox
00049  *  Cput
00050  *
00051  *  Revision 1.1  2001/12/17 16:11:55  rwcox
00052  *  Cadd
00053  *
00054  * Revision 1.9  1995/01/19  23:09:12  eyhung
00055  * Changed copyrights
00056  *
00057  * Revision 1.9  1995/01/19  23:09:12  eyhung
00058  * Changed copyrights
00059  *
00060  * Revision 1.8  1994/12/07  00:40:36  smoot
00061  * Added seperate P and B search ranges
00062  *
00063  * Revision 1.7  1994/11/12  02:09:45  eyhung
00064  * full pixel bug
00065  * fixed on lines 512 and 563
00066  *
00067  * Revision 1.6  1994/03/15  00:27:11  keving
00068  * nothing
00069  *
00070  * Revision 1.5  1993/12/22  19:19:01  keving
00071  * nothing
00072  *
00073  * Revision 1.4  1993/07/22  22:23:43  keving
00074  * nothing
00075  *
00076  * Revision 1.3  1993/06/30  20:06:09  keving
00077  * nothing
00078  *
00079  * Revision 1.2  1993/06/03  21:08:08  keving
00080  * nothing
00081  *
00082  * Revision 1.1  1993/03/02  18:27:05  keving
00083  * nothing
00084  *
00085  */
00086 
00087 
00088 /*==============*
00089  * HEADER FILES *
00090  *==============*/
00091 
00092 #include "all.h"
00093 #include "mtypes.h"
00094 #include "frames.h"
00095 #include "search.h"
00096 #include "prototypes.h"
00097 #include "fsize.h"
00098 #include "param.h"
00099 
00100 
00101 /*==================*
00102  * STATIC VARIABLES *
00103  *==================*/
00104 
00105 /* none */
00106 
00107 
00108 /*==================*
00109  * GLOBAL VARIABLES *
00110  *==================*/
00111 
00112 int **pmvHistogram = NULL;      /* histogram of P-frame motion vectors */
00113 int **bbmvHistogram = NULL;     /* histogram of B-frame motion vectors */
00114 int **bfmvHistogram = NULL;     /* histogram of B-frame motion vectors */
00115 int pixelFullSearch;
00116 int searchRangeP,searchRangeB;
00117 int psearchAlg;
00118 
00119 
00120 /*===============================*
00121  * INTERNAL PROCEDURE prototypes *
00122  *===============================*/
00123 
00124 
00125 /*=====================*
00126  * EXPORTED PROCEDURES *
00127  *=====================*/
00128 
00129 /*===========================================================================*
00130  *
00131  * PMotionSearch
00132  *
00133  *      compute the best P-frame motion vector we can
00134  *      
00135  *
00136  * RETURNS:     TRUE        =   motion vector valid
00137  *              FALSE       =   motion vector invalid; should code I-block
00138  *
00139  * PRECONDITIONS:       The relevant block in 'current' is valid (it has not
00140  *                      been dct'd).  Thus, the data in 'current' can be
00141  *                      accesed through y_blocks, cr_blocks, and cb_blocks.
00142  *                      This is not the case for the blocks in 'prev.'
00143  *                      Therefore, references into 'prev' should be done
00144  *                      through the struct items ref_y, ref_cr, ref_cb
00145  *
00146  * POSTCONDITIONS:      current, prev should be unchanged.
00147  *                      Some computation could be saved by requiring
00148  *                      the dct'd difference to be put into current's block
00149  *                      elements here, depending on the search technique.
00150  *                      However, it was decided that it mucks up the code
00151  *                      organization a little, and the saving in computation
00152  *                      would be relatively little (if any).
00153  *
00154  * NOTES:       the search procedure need not check the (0,0) motion vector
00155  *              the calling procedure has a preference toward (0,0) and it
00156  *              will check it itself
00157  *
00158  * SIDE EFFECTS:    none
00159  *
00160  *===========================================================================*/
00161 boolean
00162 PMotionSearch(currentBlock, prev, by, bx, motionY, motionX)
00163     LumBlock currentBlock;
00164     MpegFrame *prev;
00165     int by;
00166     int bx;
00167     int *motionY;
00168     int *motionX;
00169 {
00170     /* CALL SEARCH PROCEDURE */
00171 
00172     switch(psearchAlg) {
00173         case PSEARCH_SUBSAMPLE:
00174             PSubSampleSearch(currentBlock, prev, by, bx, motionY, motionX, searchRangeP);
00175             break;
00176         case PSEARCH_EXHAUSTIVE:
00177             PLocalSearch(currentBlock, prev, by, bx, motionY, motionX,
00178                          0x7fffffff, searchRangeP);
00179             break;
00180         case PSEARCH_LOGARITHMIC:
00181             PLogarithmicSearch(currentBlock, prev, by, bx, motionY, motionX, searchRangeP);
00182             break;
00183         case PSEARCH_TWOLEVEL:
00184             PTwoLevelSearch(currentBlock, prev, by, bx, motionY, motionX,
00185                             0x7fffffff, searchRangeP);
00186             break;
00187         default:
00188             fprintf(stderr, "ILLEGAL PSEARCH ALG:  %d\n", psearchAlg);
00189             exit(1);
00190     }
00191 
00192     return TRUE;
00193 }
00194 
00195 
00196 /*===========================================================================*
00197  *
00198  * SetPixelSearch
00199  *
00200  *      set the pixel search type (half or full)
00201  *
00202  * RETURNS:     nothing
00203  *
00204  * SIDE EFFECTS:    pixelFullSearch
00205  *
00206  *===========================================================================*/
00207 void
00208 SetPixelSearch(searchType)
00209     char *searchType;
00210 {
00211     if ( (strcmp(searchType, "FULL") == 0 ) || ( strcmp(searchType, "WHOLE") == 0 )) {
00212         pixelFullSearch = TRUE;
00213     } else if ( strcmp(searchType, "HALF") == 0 ) {
00214         pixelFullSearch = FALSE;
00215     } else {
00216         fprintf(stderr, "ERROR:  Invalid pixel search type:  %s\n",
00217                 searchType);
00218         exit(1);
00219     }
00220 }
00221 
00222 
00223 /*===========================================================================*
00224  *
00225  * SetPSearchAlg
00226  *
00227  *      set the P-search algorithm
00228  *
00229  * RETURNS:     nothing
00230  *
00231  * SIDE EFFECTS:    psearchAlg
00232  *
00233  *===========================================================================*/
00234 void
00235 SetPSearchAlg(alg)
00236     char *alg;
00237 {
00238     if ( strcmp(alg, "EXHAUSTIVE") == 0 ) {
00239         psearchAlg = PSEARCH_EXHAUSTIVE;
00240     } else if (strcmp(alg, "SUBSAMPLE") == 0 ) {
00241         psearchAlg = PSEARCH_SUBSAMPLE;
00242     } else if ( strcmp(alg, "LOGARITHMIC") == 0 ) {
00243         psearchAlg = PSEARCH_LOGARITHMIC;
00244     } else if ( strcmp(alg, "TWOLEVEL") == 0 ) {
00245         psearchAlg = PSEARCH_TWOLEVEL;
00246     } else {
00247         fprintf(stderr, "ERROR:  Invalid psearch algorithm:  %s\n", alg);
00248         exit(1);
00249     }
00250 }
00251 
00252 
00253 /*===========================================================================*
00254  *
00255  * PSearchName
00256  *
00257  *      returns a string containing the name of the search algorithm
00258  *
00259  * RETURNS:     pointer to the string
00260  *
00261  * SIDE EFFECTS:    none
00262  *
00263  *===========================================================================*/
00264 char *
00265 PSearchName()
00266 {
00267     switch(psearchAlg) {
00268         case PSEARCH_EXHAUSTIVE:
00269             return "EXHAUSTIVE";
00270         case PSEARCH_SUBSAMPLE:
00271             return "SUBSAMPLE";
00272         case PSEARCH_LOGARITHMIC:
00273             return "LOGARITHMIC";
00274         case PSEARCH_TWOLEVEL:
00275             return "TWOLEVEL";
00276         default:
00277             exit(1);
00278             break;
00279     }
00280 }
00281 
00282 
00283 /*===========================================================================*
00284  *
00285  * SetSearchRange
00286  *
00287  *      sets the range of the search to the given number of pixels
00288  *
00289  * RETURNS:     nothing
00290  *
00291  * SIDE EFFECTS:    searchRange*, fCode
00292  *
00293  *===========================================================================*/
00294 void
00295 SetSearchRange(pixelsP,pixelsB)
00296     int pixelsP,pixelsB;
00297 {
00298     register int index;
00299 
00300     searchRangeP = 2*pixelsP;   /* +/- 'pixels' pixels */
00301     searchRangeB = 2*pixelsB;
00302     searchRangeB = 2*pixelsB;
00303 
00304     if ( computeMVHist ) {
00305       int max_search;
00306       max_search=(searchRangeP>searchRangeB) ? 
00307         ((searchRangeP>searchRangeB)?searchRangeP:searchRangeB)
00308           : ((searchRangeB>searchRangeB)?searchRangeB:searchRangeB);
00309         
00310         pmvHistogram = (int **) malloc((2*searchRangeP+3)*sizeof(int *));
00311         bbmvHistogram = (int **) malloc((2*searchRangeB+3)*sizeof(int *));
00312         bfmvHistogram = (int **) malloc((2*searchRangeB+3)*sizeof(int *));
00313         for ( index = 0; index < 2*max_search+3; index++ ) {
00314             pmvHistogram[index] = (int *) calloc(2*searchRangeP+3, sizeof(int));
00315             bbmvHistogram[index] = (int *) calloc(2*searchRangeB+3, sizeof(int));
00316             bfmvHistogram[index] = (int *) calloc(2*searchRangeB+3, sizeof(int));
00317         }
00318     }
00319 }
00320 
00321 
00322 /*===========================================================================*
00323  *
00324  *                              USER-MODIFIABLE
00325  *
00326  * MotionSearchPreComputation
00327  *
00328  *      do whatever you want here; this is called once per frame, directly
00329  *      after reading
00330  *
00331  * RETURNS:     whatever
00332  *
00333  * SIDE EFFECTS:    whatever
00334  *
00335  *===========================================================================*/
00336 void
00337 MotionSearchPreComputation(frame)
00338     MpegFrame *frame;
00339 {
00340     /* do nothing */
00341 }
00342 
00343 
00344 /*===========================================================================*
00345  *
00346  * PSubSampleSearch
00347  *
00348  *      uses the subsampling algorithm to compute the P-frame vector
00349  *
00350  * RETURNS:     motion vector
00351  *
00352  * SIDE EFFECTS:    none
00353  *
00354  * REFERENCE:  Liu and Zaccarin:  New Fast Algorithms for the Estimation
00355  *              of Block Motion Vectors, IEEE Transactions on Circuits
00356  *              and Systems for Video Technology, Vol. 3, No. 2, 1993.
00357  *
00358  *===========================================================================*/
00359 int32
00360 PSubSampleSearch(currentBlock, prev, by, bx, motionY, motionX, searchRange)
00361     LumBlock currentBlock;
00362     MpegFrame *prev;
00363     int by;
00364     int bx;
00365     int *motionY;
00366     int *motionX;
00367     int searchRange;
00368 {
00369     register int mx, my;
00370     int32 diff, bestBestDiff;
00371     int     stepSize;
00372     register int x;
00373     int     bestMY[4], bestMX[4], bestDiff[4];
00374     int     leftMY, leftMX;
00375     int     rightMY, rightMX;
00376 
00377     stepSize = (pixelFullSearch ? 2 : 1);
00378 
00379     COMPUTE_MOTION_BOUNDARY(by,bx,stepSize,leftMY,leftMX,rightMY,rightMX);
00380 
00381     if ( searchRange < rightMY ) {
00382         rightMY = searchRange;
00383     }
00384 
00385     if ( searchRange < rightMX ) {
00386         rightMX = searchRange;
00387     }
00388 
00389     for ( x = 0; x < 4; x++ ) {
00390         bestMY[x] = 0;
00391         bestMX[x] = 0;
00392         bestDiff[x] = 0x7fffffff;
00393     }
00394 
00395     /* do A pattern */
00396     for ( my = -searchRange; my < rightMY; my += 2*stepSize ) {
00397         if ( my < leftMY ) {
00398             continue;
00399         }
00400 
00401         for ( mx = -searchRange; mx < rightMX; mx += 2*stepSize ) {
00402             if ( mx < leftMX ) {
00403                 continue;
00404             }
00405 
00406             diff = LumMotionErrorA(currentBlock, prev, by, bx, my, mx, bestDiff[0]);
00407 
00408             if ( diff < bestDiff[0] ) {
00409                 bestMY[0] = my;
00410                 bestMX[0] = mx;
00411                 bestDiff[0] = diff;
00412             }
00413         }
00414     }
00415 
00416     /* do B pattern */
00417     for ( my = stepSize-searchRange; my < rightMY; my += 2*stepSize ) {
00418         if ( my < leftMY ) {
00419             continue;
00420         }
00421 
00422         for ( mx = -searchRange; mx < rightMX; mx += 2*stepSize ) {
00423             if ( mx < leftMX ) {
00424                 continue;
00425             }
00426 
00427             diff = LumMotionErrorB(currentBlock, prev, by, bx, my, mx, bestDiff[1]);
00428 
00429             if ( diff < bestDiff[1] ) {
00430                 bestMY[1] = my;
00431                 bestMX[1] = mx;
00432                 bestDiff[1] = diff;
00433             }
00434         }
00435     }
00436 
00437     /* do C pattern */
00438     for ( my = stepSize-searchRange; my < rightMY; my += 2*stepSize ) {
00439         if ( my < leftMY ) {
00440             continue;
00441         }
00442 
00443         for ( mx = stepSize-searchRange; mx < rightMX; mx += 2*stepSize ) {
00444             if ( mx < leftMX ) {
00445                 continue;
00446             }
00447 
00448             diff = LumMotionErrorC(currentBlock, prev, by, bx, my, mx, bestDiff[2]);
00449 
00450             if ( diff < bestDiff[2] ) {
00451                 bestMY[2] = my;
00452                 bestMX[2] = mx;
00453                 bestDiff[2] = diff;
00454             }
00455         }
00456     }
00457 
00458     /* do D pattern */
00459     for ( my = -searchRange; my < rightMY; my += 2*stepSize ) {
00460         if ( my < leftMY ) {
00461             continue;
00462         }
00463 
00464         for ( mx = stepSize-searchRange; mx < rightMX; mx += 2*stepSize ) {
00465             if ( mx < leftMX ) {
00466                 continue;
00467             }
00468 
00469             diff = LumMotionErrorD(currentBlock, prev, by, bx, my, mx, bestDiff[3]);
00470 
00471             if ( diff < bestDiff[3] ) {
00472                 bestMY[3] = my;
00473                 bestMX[3] = mx;
00474                 bestDiff[3] = diff;
00475             }
00476         }
00477     }
00478 
00479     /* first check old motion */
00480     if ( (*motionY >= leftMY) && (*motionY < rightMY) &&
00481          (*motionX >= leftMX) && (*motionX < rightMX) ) {
00482         bestBestDiff = LumMotionError(currentBlock, prev, by, bx, *motionY, *motionX, 0x7fffffff);
00483     } else {
00484         bestBestDiff = 0x7fffffff;
00485     }
00486 
00487     /* look at Error of 4 different motion vectors */
00488     for ( x = 0; x < 4; x++ ) {
00489         bestDiff[x] = LumMotionError(currentBlock, prev, by, bx,
00490                                  bestMY[x], bestMX[x], bestBestDiff);
00491 
00492         if ( bestDiff[x] < bestBestDiff ) {
00493             bestBestDiff = bestDiff[x];
00494             *motionY = bestMY[x];
00495             *motionX = bestMX[x];
00496         }
00497     }
00498 
00499     return bestBestDiff;
00500 }
00501 
00502 
00503 /*===========================================================================*
00504  *
00505  * PLogarithmicSearch
00506  *
00507  *      uses logarithmic search to compute the P-frame vector
00508  *
00509  * RETURNS:     motion vector
00510  *
00511  * SIDE EFFECTS:    none
00512  *
00513  * REFERENCE:  MPEG-I specification, pages 32-33
00514  *
00515  *===========================================================================*/
00516 int32
00517 PLogarithmicSearch(currentBlock, prev, by, bx, motionY, motionX, searchRange)
00518     LumBlock currentBlock;
00519     MpegFrame *prev;
00520     int by;
00521     int bx;
00522     int *motionY;
00523     int *motionX;
00524     int searchRange;
00525 {
00526     register int mx, my;
00527     int32 diff, bestDiff;
00528     int     stepSize;
00529     int     leftMY, leftMX;
00530     int     rightMY, rightMX;
00531     int     tempRightMY, tempRightMX;
00532     int     spacing;
00533     int     centerX, centerY;
00534     int     newCenterX, newCenterY;
00535 
00536     stepSize = (pixelFullSearch ? 2 : 1);
00537 
00538     COMPUTE_MOTION_BOUNDARY(by,bx,stepSize,leftMY,leftMX,rightMY,rightMX);
00539 
00540     bestDiff = 0x7fffffff;
00541 
00542     /* grid spacing */
00543     if ( stepSize == 2 ) {      /* make sure spacing is even */
00544         spacing = (searchRange+1)/2;
00545         if ( (spacing % 2) != 0 ) {
00546             spacing--;
00547         }
00548     } else {
00549         spacing = (searchRange+1)/2;
00550     }
00551     centerX = 0;
00552     centerY = 0;
00553 
00554     while ( spacing >= stepSize ) {
00555         newCenterY = centerY;
00556         newCenterX = centerX;
00557 
00558         tempRightMY = rightMY;
00559         if ( centerY+spacing+1 < tempRightMY ) {
00560             tempRightMY = centerY+spacing+1;
00561         }
00562         tempRightMX = rightMX;
00563         if ( centerX+spacing+1 < tempRightMX ) {
00564             tempRightMX = centerX+spacing+1;
00565         }
00566 
00567         for ( my = centerY-spacing; my < tempRightMY; my += spacing ) {
00568             if ( my < leftMY ) {
00569                 continue;
00570             }
00571 
00572             for ( mx = centerX-spacing; mx < tempRightMX; mx += spacing ) {
00573                 if ( mx < leftMX ) {
00574                     continue;
00575                 }
00576 
00577                 diff = LumMotionError(currentBlock, prev, by, bx, my, mx, bestDiff);
00578 
00579                 if ( diff < bestDiff ) {
00580                     newCenterY = my;
00581                     newCenterX = mx;
00582 
00583                     bestDiff = diff;
00584                 }
00585             }
00586         }
00587 
00588         centerY = newCenterY;
00589         centerX = newCenterX;
00590 
00591         if ( stepSize == 2 ) {  /* make sure spacing is even */
00592             if ( spacing == 2 ) {
00593                 spacing = 0;
00594             } else {
00595                 spacing = (spacing+1)/2;
00596                 if ( (spacing % 2) != 0 ) {
00597                     spacing--;
00598                 }
00599             }
00600         } else {
00601             if ( spacing == 1 ) {
00602                 spacing = 0;
00603             } else {
00604                 spacing = (spacing+1)/2;
00605             }
00606         }
00607     }
00608 
00609     /* check old motion -- see if it's better */
00610     if ( (*motionY >= leftMY) && (*motionY < rightMY) &&
00611          (*motionX >= leftMX) && (*motionX < rightMX) ) {
00612         diff = LumMotionError(currentBlock, prev, by, bx, *motionY, *motionX, bestDiff);
00613     } else {
00614         diff = 0x7fffffff;
00615     }
00616 
00617     if ( bestDiff < diff ) {
00618         *motionY = centerY;
00619         *motionX = centerX;
00620     } else {
00621         bestDiff = diff;
00622     }
00623 
00624     return bestDiff;
00625 }
00626 
00627 
00628 /*===========================================================================*
00629  *
00630  * PLocalSearch
00631  *
00632  *      uses local exhaustive search to compute the P-frame vector
00633  *
00634  * RETURNS:     motion vector
00635  *
00636  * SIDE EFFECTS:    none
00637  *
00638  *===========================================================================*/
00639 int32
00640 PLocalSearch(currentBlock, prev, by, bx, motionY, motionX, bestSoFar, searchRange)
00641     LumBlock currentBlock;
00642     MpegFrame *prev;
00643     int by;
00644     int bx;
00645     int *motionY;
00646     int *motionX;
00647     int32 bestSoFar;
00648     int searchRange;
00649 {
00650     register int mx, my;
00651     int32 diff, bestDiff;
00652     int     stepSize;
00653     int     leftMY, leftMX;
00654     int     rightMY, rightMX;
00655     int     distance;
00656     int     tempRightMY, tempRightMX;
00657 
00658     stepSize = (pixelFullSearch ? 2 : 1);
00659 
00660     COMPUTE_MOTION_BOUNDARY(by,bx,stepSize,leftMY,leftMX,rightMY,rightMX);
00661 
00662     /* try old motion vector first */
00663     if ( VALID_MOTION(*motionY, *motionX) ) {
00664         bestDiff = LumMotionError(currentBlock, prev, by, bx, *motionY, *motionX, bestSoFar);
00665 
00666         if ( bestSoFar < bestDiff ) {
00667             bestDiff = bestSoFar;
00668         }
00669     } else {
00670         *motionY = 0;
00671         *motionX = 0;
00672 
00673         bestDiff = bestSoFar;
00674     }
00675 
00676     /* try a spiral pattern */    
00677     for ( distance = stepSize; distance <= searchRange;
00678           distance += stepSize ) {
00679         tempRightMY = rightMY;
00680         if ( distance < tempRightMY ) {
00681             tempRightMY = distance;
00682         }
00683         tempRightMX = rightMX;
00684         if ( distance < tempRightMX ) {
00685             tempRightMX = distance;
00686         }
00687 
00688         /* do top, bottom */
00689         for ( my = -distance; my < tempRightMY;
00690               my += max(tempRightMY+distance-stepSize, stepSize) ) {
00691             if ( my < leftMY ) {
00692                 continue;
00693             }
00694 
00695             for ( mx = -distance; mx < tempRightMX; mx += stepSize ) {
00696                 if ( mx < leftMX ) {
00697                     continue;
00698                 }
00699 
00700                 diff = LumMotionError(currentBlock, prev, by, bx, my, mx, bestDiff);
00701 
00702                 if ( diff < bestDiff ) {
00703                     *motionY = my;
00704                     *motionX = mx;
00705                     bestDiff = diff;
00706                 }
00707             }
00708         }
00709 
00710         /* do left, right */
00711         for ( mx = -distance; mx < tempRightMX;
00712               mx += max(tempRightMX+distance-stepSize, stepSize) ) {
00713             if ( mx < leftMX ) {
00714                 continue;
00715             }
00716 
00717             for ( my = -distance+stepSize; my < tempRightMY-stepSize;
00718                   my += stepSize ) {
00719                 if ( my < leftMY ) {
00720                     continue;
00721                 }
00722 
00723                 diff = LumMotionError(currentBlock, prev, by, bx, my, mx, bestDiff);
00724 
00725                 if ( diff < bestDiff ) {
00726                     *motionY = my;
00727                     *motionX = mx;
00728                     bestDiff = diff;
00729                 }
00730             }
00731         }
00732     }
00733 
00734     return bestDiff;
00735 }
00736 
00737 
00738 /*===========================================================================*
00739  *
00740  * PTwoLevelSearch
00741  *
00742  *      uses two-level search to compute the P-frame vector
00743  *      first does exhaustive full-pixel search, then looks at neighboring
00744  *      half-pixel motion vectors
00745  *
00746  * RETURNS:     motion vector
00747  *
00748  * SIDE EFFECTS:    none
00749  *
00750  *===========================================================================*/
00751 int32
00752 PTwoLevelSearch(currentBlock, prev, by, bx, motionY, motionX, bestSoFar, searchRange)
00753     LumBlock currentBlock;
00754     MpegFrame *prev;
00755     int by;
00756     int bx;
00757     int *motionY;
00758     int *motionX;
00759     int32 bestSoFar;
00760     int searchRange;
00761 {
00762     register int mx, my;
00763     register int   loopInc;
00764     int32 diff, bestDiff;
00765     int     leftMY, leftMX;
00766     int     rightMY, rightMX;
00767     int     distance;
00768     int     tempRightMY, tempRightMX;
00769     int     xOffset, yOffset;
00770 
00771     /* exhaustive full-pixel search first */
00772 
00773     COMPUTE_MOTION_BOUNDARY(by,bx,2,leftMY,leftMX,rightMY,rightMX);
00774 
00775     rightMY--;
00776     rightMX--;
00777 
00778     /* convert vector into full-pixel vector */
00779     if ( *motionY > 0 ) {
00780         if ( ((*motionY) % 2) == 1 ) {
00781             (*motionY)--;
00782         }
00783     } else if ( ((-(*motionY)) % 2) == 1 ) {
00784         (*motionY)++;
00785     }
00786 
00787     if ( *motionX > 0 ) {
00788         if ( ((*motionX) % 2) == 1 ) {
00789             (*motionX)--;
00790         }
00791     } else if ( ((-(*motionX)) % 2) == 1 ) {
00792         (*motionX)++;
00793     }
00794 
00795     /* try old motion vector first */
00796     if ( VALID_MOTION(*motionY, *motionX) ) {
00797         bestDiff = LumMotionError(currentBlock, prev, by, bx, *motionY, *motionX, bestSoFar);
00798 
00799         if ( bestSoFar < bestDiff ) {
00800             bestDiff = bestSoFar;
00801         }
00802     } else {
00803         *motionY = 0;
00804         *motionX = 0;
00805 
00806         bestDiff = bestSoFar;
00807     }
00808 
00809     rightMY++;
00810     rightMX++;
00811 
00812     /* try a spiral pattern */    
00813     for ( distance = 2; distance <= searchRange; distance += 2 ) {
00814         tempRightMY = rightMY;
00815         if ( distance < tempRightMY ) {
00816             tempRightMY = distance;
00817         }
00818         tempRightMX = rightMX;
00819         if ( distance < tempRightMX ) {
00820             tempRightMX = distance;
00821         }
00822 
00823         /* do top, bottom */
00824         loopInc = max(tempRightMY+distance-2, 2);
00825         for ( my = -distance; my < tempRightMY; my += loopInc ) {
00826             if ( my < leftMY ) {
00827                 continue;
00828             }
00829 
00830             for ( mx = -distance; mx < tempRightMX; mx += 2 ) {
00831                 if ( mx < leftMX ) {
00832                     continue;
00833                 }
00834 
00835                 diff = LumMotionError(currentBlock, prev, by, bx, my, mx, bestDiff);
00836 
00837                 if ( diff < bestDiff ) {
00838                     *motionY = my;
00839                     *motionX = mx;
00840                     bestDiff = diff;
00841                 }
00842             }
00843         }
00844 
00845         /* do left, right */
00846         loopInc = max(tempRightMX+distance-2, 2);
00847         for ( mx = -distance; mx < tempRightMX; mx += loopInc ) {
00848             if ( mx < leftMX ) {
00849                 continue;
00850             }
00851 
00852             for ( my = -distance+2; my < tempRightMY-2; my += 2 ) {
00853                 if ( my < leftMY ) {
00854                     continue;
00855                 }
00856 
00857                 diff = LumMotionError(currentBlock, prev, by, bx, my, mx, bestDiff);
00858 
00859                 if ( diff < bestDiff ) {
00860                     *motionY = my;
00861                     *motionX = mx;
00862                     bestDiff = diff;
00863                 }
00864             }
00865         }
00866     }
00867 
00868     /* now look at neighboring half-pixels */
00869     my = *motionY;
00870     mx = *motionX;
00871 
00872     rightMY--;
00873     rightMX--;
00874 
00875     for ( yOffset = -1; yOffset <= 1; yOffset++ ) {
00876         for ( xOffset = -1; xOffset <= 1; xOffset++ ) {
00877             if ( (yOffset == 0) && (xOffset == 0) )
00878                 continue;
00879 
00880             if ( VALID_MOTION(my+yOffset, mx+xOffset) &&
00881                  ((diff = LumMotionError(currentBlock, prev, by, bx,
00882                          my+yOffset, mx+xOffset, bestDiff)) < bestDiff) ) {
00883                 *motionY = my+yOffset;
00884                 *motionX = mx+xOffset;
00885                 bestDiff = diff;
00886             }
00887         }
00888     }
00889 
00890     return bestDiff;
00891 }
00892 
00893 
00894 void
00895 ShowPMVHistogram(fpointer)
00896     FILE *fpointer;
00897 {
00898     register int x, y;
00899     int *columnTotals;
00900     int rowTotal;
00901 
00902     columnTotals = (int *) calloc(2*searchRangeP+3, sizeof(int));
00903 
00904 #ifdef COMPLETE_DISPLAY
00905     fprintf(fpointer, "    ");
00906     for ( y = 0; y < 2*searchRange+3; y++ ) {
00907         fprintf(fpointer, "%3d ", y-searchRangeP-1);
00908     }
00909     fprintf(fpointer, "\n");
00910 #endif
00911 
00912     for ( x = 0; x < 2*searchRangeP+3; x++ ) {
00913 #ifdef COMPLETE_DISPLAY
00914         fprintf(fpointer, "%3d ", x-searchRangeP-1);
00915 #endif
00916         rowTotal = 0;
00917         for ( y = 0; y < 2*searchRangeP+3; y++ ) {
00918             fprintf(fpointer, "%3d ", pmvHistogram[x][y]);
00919             rowTotal += pmvHistogram[x][y];
00920             columnTotals[y] += pmvHistogram[x][y];
00921         }
00922 #ifdef COMPLETE_DISPLAY
00923         fprintf(fpointer, "%4d\n", rowTotal);
00924 #else
00925         fprintf(fpointer, "\n");
00926 #endif
00927     }
00928 
00929 #ifdef COMPLETE_DISPLAY
00930     fprintf(fpointer, "Tot ");
00931     for ( y = 0; y < 2*searchRangeP+3; y++ ) {
00932         fprintf(fpointer, "%3d ", columnTotals[y]);
00933     }
00934 #endif
00935     fprintf(fpointer, "\n");
00936 }
00937 
00938 
00939 void
00940 ShowBBMVHistogram(fpointer)
00941     FILE *fpointer;
00942 {
00943     register int x, y;
00944     int *columnTotals;
00945     int rowTotal;
00946 
00947     fprintf(fpointer, "B-frame Backwards:\n");
00948 
00949     columnTotals = (int *) calloc(2*searchRangeB+3, sizeof(int));
00950 
00951 #ifdef COMPLETE_DISPLAY
00952     fprintf(fpointer, "    ");
00953     for ( y = 0; y < 2*searchRangeB+3; y++ ) {
00954         fprintf(fpointer, "%3d ", y-searchRangeB-1);
00955     }
00956     fprintf(fpointer, "\n");
00957 #endif
00958 
00959     for ( x = 0; x < 2*searchRangeB+3; x++ ) {
00960 #ifdef COMPLETE_DISPLAY
00961         fprintf(fpointer, "%3d ", x-searchRangeB-1);
00962 #endif
00963         rowTotal = 0;
00964         for ( y = 0; y < 2*searchRangeB+3; y++ ) {
00965             fprintf(fpointer, "%3d ", bbmvHistogram[x][y]);
00966             rowTotal += bbmvHistogram[x][y];
00967             columnTotals[y] += bbmvHistogram[x][y];
00968         }
00969 #ifdef COMPLETE_DISPLAY
00970         fprintf(fpointer, "%4d\n", rowTotal);
00971 #else
00972         fprintf(fpointer, "\n");
00973 #endif
00974     }
00975 
00976 #ifdef COMPLETE_DISPLAY
00977     fprintf(fpointer, "Tot ");
00978     for ( y = 0; y < 2*searchRangeB+3; y++ ) {
00979         fprintf(fpointer, "%3d ", columnTotals[y]);
00980     }
00981 #endif
00982     fprintf(fpointer, "\n");
00983 }
00984 
00985 
00986 void
00987 ShowBFMVHistogram(fpointer)
00988     FILE *fpointer;
00989 {
00990     register int x, y;
00991     int *columnTotals;
00992     int rowTotal;
00993 
00994     fprintf(fpointer, "B-frame Forwards:\n");
00995 
00996     columnTotals = (int *) calloc(2*searchRangeB+3, sizeof(int));
00997 
00998 #ifdef COMPLETE_DISPLAY
00999     fprintf(fpointer, "    ");
01000     for ( y = 0; y < 2*searchRangeB+3; y++ ) {
01001         fprintf(fpointer, "%3d ", y-searchRangeB-1);
01002     }
01003     fprintf(fpointer, "\n");
01004 #endif
01005 
01006     for ( x = 0; x < 2*searchRangeB+3; x++ ) {
01007 #ifdef COMPLETE_DISPLAY
01008         fprintf(fpointer, "%3d ", x-searchRangeB-1);
01009 #endif
01010         rowTotal = 0;
01011         for ( y = 0; y < 2*searchRangeB+3; y++ ) {
01012             fprintf(fpointer, "%3d ", bfmvHistogram[x][y]);
01013             rowTotal += bfmvHistogram[x][y];
01014             columnTotals[y] += bfmvHistogram[x][y];
01015         }
01016 #ifdef COMPLETE_DISPLAY
01017         fprintf(fpointer, "%4d\n", rowTotal);
01018 #else
01019         fprintf(fpointer, "\n");
01020 #endif
01021     }
01022 
01023 #ifdef COMPLETE_DISPLAY
01024     fprintf(fpointer, "Tot ");
01025     for ( y = 0; y < 2*searchRangeB+3; y++ ) {
01026         fprintf(fpointer, "%3d ", columnTotals[y]);
01027     }
01028 #endif
01029     fprintf(fpointer, "\n");
01030 }
01031 
01032 
01033 /*=====================*
01034  * INTERNAL PROCEDURES *
01035  *=====================*/
01036 
01037     /* none */
01038