w32tex
About: TeX Live provides a comprehensive TeX system including all the major TeX-related programs, macro packages, and fonts that are free software. Windows sources.
  Fossies Dox: w32tex-src.tar.xz  ("unofficial" and yet experimental doxygen-generated source code documentation)  

psearch.c
Go to the documentation of this file.
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) 1995 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: /u/smoot/md/mpeg_encode/RCS/psearch.c,v 1.9 1995/01/19 23:09:12 eyhung Exp $
41  * $Log: psearch.c,v $
42  * Revision 1.9 1995/01/19 23:09:12 eyhung
43  * Changed copyrights
44  *
45  * Revision 1.9 1995/01/19 23:09:12 eyhung
46  * Changed copyrights
47  *
48  * Revision 1.8 1994/12/07 00:40:36 smoot
49  * Added seperate P and B search ranges
50  *
51  * Revision 1.7 1994/11/12 02:09:45 eyhung
52  * full pixel bug
53  * fixed on lines 512 and 563
54  *
55  * Revision 1.6 1994/03/15 00:27:11 keving
56  * nothing
57  *
58  * Revision 1.5 1993/12/22 19:19:01 keving
59  * nothing
60  *
61  * Revision 1.4 1993/07/22 22:23:43 keving
62  * nothing
63  *
64  * Revision 1.3 1993/06/30 20:06:09 keving
65  * nothing
66  *
67  * Revision 1.2 1993/06/03 21:08:08 keving
68  * nothing
69  *
70  * Revision 1.1 1993/03/02 18:27:05 keving
71  * nothing
72  *
73  */
74 
75 
76 /*==============*
77  * HEADER FILES *
78  *==============*/
79 
80 #include "all.h"
81 #include "mtypes.h"
82 #include "frames.h"
83 #include "motion_search.h"
84 #include "prototypes.h"
85 #include "fsize.h"
86 #include "param.h"
87 
88 
89 /*==================*
90  * STATIC VARIABLES *
91  *==================*/
92 
93 /* none */
94 
95 
96 /*==================*
97  * GLOBAL VARIABLES *
98  *==================*/
99 
100 int **pmvHistogram = NULL; /* histogram of P-frame motion vectors */
101 int **bbmvHistogram = NULL; /* histogram of B-frame motion vectors */
102 int **bfmvHistogram = NULL; /* histogram of B-frame motion vectors */
106 
107 
108 /*===============================*
109  * INTERNAL PROCEDURE prototypes *
110  *===============================*/
111 
112 
113 /*=====================*
114  * EXPORTED PROCEDURES *
115  *=====================*/
116 
117 /*===========================================================================*
118  *
119  * PMotionSearch
120  *
121  * compute the best P-frame motion vector we can
122  *
123  *
124  * RETURNS: TRUE = motion vector valid
125  * FALSE = motion vector invalid; should code I-block
126  *
127  * PRECONDITIONS: The relevant block in 'current' is valid (it has not
128  * been dct'd). Thus, the data in 'current' can be
129  * accesed through y_blocks, cr_blocks, and cb_blocks.
130  * This is not the case for the blocks in 'prev.'
131  * Therefore, references into 'prev' should be done
132  * through the struct items ref_y, ref_cr, ref_cb
133  *
134  * POSTCONDITIONS: current, prev should be unchanged.
135  * Some computation could be saved by requiring
136  * the dct'd difference to be put into current's block
137  * elements here, depending on the search technique.
138  * However, it was decided that it mucks up the code
139  * organization a little, and the saving in computation
140  * would be relatively little (if any).
141  *
142  * NOTES: the search procedure need not check the (0,0) motion vector
143  * the calling procedure has a preference toward (0,0) and it
144  * will check it itself
145  *
146  * SIDE EFFECTS: none
147  *
148  *===========================================================================*/
149 boolean
150 PMotionSearch(currentBlock, prev, by, bx, motionY, motionX)
151  LumBlock currentBlock;
152  MpegFrame *prev;
153  int by;
154  int bx;
155  int *motionY;
156  int *motionX;
157 {
158  /* CALL SEARCH PROCEDURE */
159 
160  switch(psearchAlg) {
161  case PSEARCH_SUBSAMPLE:
162  PSubSampleSearch(currentBlock, prev, by, bx, motionY, motionX, searchRangeP);
163  break;
164  case PSEARCH_EXHAUSTIVE:
165  PLocalSearch(currentBlock, prev, by, bx, motionY, motionX,
166  0x7fffffff, searchRangeP);
167  break;
168  case PSEARCH_LOGARITHMIC:
169  PLogarithmicSearch(currentBlock, prev, by, bx, motionY, motionX, searchRangeP);
170  break;
171  case PSEARCH_TWOLEVEL:
172  PTwoLevelSearch(currentBlock, prev, by, bx, motionY, motionX,
173  0x7fffffff, searchRangeP);
174  break;
175  default:
176  fprintf(stderr, "ILLEGAL PSEARCH ALG: %d\n", psearchAlg);
177  exit(1);
178  }
179 
180  return TRUE;
181 }
182 
183 
184 /*===========================================================================*
185  *
186  * SetPixelSearch
187  *
188  * set the pixel search type (half or full)
189  *
190  * RETURNS: nothing
191  *
192  * SIDE EFFECTS: pixelFullSearch
193  *
194  *===========================================================================*/
195 void
196 SetPixelSearch(searchType)
197  char *searchType;
198 {
199  if ( (strcmp(searchType, "FULL") == 0 ) || ( strcmp(searchType, "WHOLE") == 0 )) {
201  } else if ( strcmp(searchType, "HALF") == 0 ) {
203  } else {
204  fprintf(stderr, "ERROR: Invalid pixel search type: %s\n",
205  searchType);
206  exit(1);
207  }
208 }
209 
210 
211 /*===========================================================================*
212  *
213  * SetPSearchAlg
214  *
215  * set the P-search algorithm
216  *
217  * RETURNS: nothing
218  *
219  * SIDE EFFECTS: psearchAlg
220  *
221  *===========================================================================*/
222 void
224  char *alg;
225 {
226  if ( strcmp(alg, "EXHAUSTIVE") == 0 ) {
228  } else if (strcmp(alg, "SUBSAMPLE") == 0 ) {
230  } else if ( strcmp(alg, "LOGARITHMIC") == 0 ) {
232  } else if ( strcmp(alg, "TWOLEVEL") == 0 ) {
234  } else {
235  fprintf(stderr, "ERROR: Invalid psearch algorithm: %s\n", alg);
236  exit(1);
237  }
238 }
239 
240 
241 /*===========================================================================*
242  *
243  * PSearchName
244  *
245  * returns a string containing the name of the search algorithm
246  *
247  * RETURNS: pointer to the string
248  *
249  * SIDE EFFECTS: none
250  *
251  *===========================================================================*/
252 char *
254 {
255  switch(psearchAlg) {
256  case PSEARCH_EXHAUSTIVE:
257  return "EXHAUSTIVE";
258  case PSEARCH_SUBSAMPLE:
259  return "SUBSAMPLE";
260  case PSEARCH_LOGARITHMIC:
261  return "LOGARITHMIC";
262  case PSEARCH_TWOLEVEL:
263  return "TWOLEVEL";
264  default:
265  exit(1);
266  break;
267  }
268 }
269 
270 
271 /*===========================================================================*
272  *
273  * SetSearchRange
274  *
275  * sets the range of the search to the given number of pixels
276  *
277  * RETURNS: nothing
278  *
279  * SIDE EFFECTS: searchRange*, fCode
280  *
281  *===========================================================================*/
282 void
283 SetSearchRange(pixelsP,pixelsB)
284  int pixelsP,pixelsB;
285 {
286  register int index;
287 
288  searchRangeP = 2*pixelsP; /* +/- 'pixels' pixels */
289  searchRangeB = 2*pixelsB;
290  searchRangeB = 2*pixelsB;
291 
292  if ( computeMVHist ) {
293  int max_search;
294  max_search=(searchRangeP>searchRangeB) ?
297 
298  pmvHistogram = (int **) malloc((2*searchRangeP+3)*sizeof(int *));
299  bbmvHistogram = (int **) malloc((2*searchRangeB+3)*sizeof(int *));
300  bfmvHistogram = (int **) malloc((2*searchRangeB+3)*sizeof(int *));
301  for ( index = 0; index < 2*max_search+3; index++ ) {
302  pmvHistogram[index] = (int *) calloc(2*searchRangeP+3, sizeof(int));
303  bbmvHistogram[index] = (int *) calloc(2*searchRangeB+3, sizeof(int));
304  bfmvHistogram[index] = (int *) calloc(2*searchRangeB+3, sizeof(int));
305  }
306  }
307 }
308 
309 
310 /*===========================================================================*
311  *
312  * USER-MODIFIABLE
313  *
314  * MotionSearchPreComputation
315  *
316  * do whatever you want here; this is called once per frame, directly
317  * after reading
318  *
319  * RETURNS: whatever
320  *
321  * SIDE EFFECTS: whatever
322  *
323  *===========================================================================*/
324 void
326  MpegFrame *frame;
327 {
328  /* do nothing */
329 }
330 
331 
332 /*===========================================================================*
333  *
334  * PSubSampleSearch
335  *
336  * uses the subsampling algorithm to compute the P-frame vector
337  *
338  * RETURNS: motion vector
339  *
340  * SIDE EFFECTS: none
341  *
342  * REFERENCE: Liu and Zaccarin: New Fast Algorithms for the Estimation
343  * of Block Motion Vectors, IEEE Transactions on Circuits
344  * and Systems for Video Technology, Vol. 3, No. 2, 1993.
345  *
346  *===========================================================================*/
347 int32
348 PSubSampleSearch(currentBlock, prev, by, bx, motionY, motionX, searchRange)
349  LumBlock currentBlock;
350  MpegFrame *prev;
351  int by;
352  int bx;
353  int *motionY;
354  int *motionX;
355  int searchRange;
356 {
357  register int mx, my;
358  int32 diff, bestBestDiff;
359  int stepSize;
360  register int x;
361  int bestMY[4], bestMX[4], bestDiff[4];
362  int leftMY, leftMX;
363  int rightMY, rightMX;
364 
365  stepSize = (pixelFullSearch ? 2 : 1);
366 
367  COMPUTE_MOTION_BOUNDARY(by,bx,stepSize,leftMY,leftMX,rightMY,rightMX);
368 
369  if ( searchRange < rightMY ) {
370  rightMY = searchRange;
371  }
372 
373  if ( searchRange < rightMX ) {
374  rightMX = searchRange;
375  }
376 
377  for ( x = 0; x < 4; x++ ) {
378  bestMY[x] = 0;
379  bestMX[x] = 0;
380  bestDiff[x] = 0x7fffffff;
381  }
382 
383  /* do A pattern */
384  for ( my = -searchRange; my < rightMY; my += 2*stepSize ) {
385  if ( my < leftMY ) {
386  continue;
387  }
388 
389  for ( mx = -searchRange; mx < rightMX; mx += 2*stepSize ) {
390  if ( mx < leftMX ) {
391  continue;
392  }
393 
394  diff = LumMotionErrorA(currentBlock, prev, by, bx, my, mx, bestDiff[0]);
395 
396  if ( diff < bestDiff[0] ) {
397  bestMY[0] = my;
398  bestMX[0] = mx;
399  bestDiff[0] = diff;
400  }
401  }
402  }
403 
404  /* do B pattern */
405  for ( my = stepSize-searchRange; my < rightMY; my += 2*stepSize ) {
406  if ( my < leftMY ) {
407  continue;
408  }
409 
410  for ( mx = -searchRange; mx < rightMX; mx += 2*stepSize ) {
411  if ( mx < leftMX ) {
412  continue;
413  }
414 
415  diff = LumMotionErrorB(currentBlock, prev, by, bx, my, mx, bestDiff[1]);
416 
417  if ( diff < bestDiff[1] ) {
418  bestMY[1] = my;
419  bestMX[1] = mx;
420  bestDiff[1] = diff;
421  }
422  }
423  }
424 
425  /* do C pattern */
426  for ( my = stepSize-searchRange; my < rightMY; my += 2*stepSize ) {
427  if ( my < leftMY ) {
428  continue;
429  }
430 
431  for ( mx = stepSize-searchRange; mx < rightMX; mx += 2*stepSize ) {
432  if ( mx < leftMX ) {
433  continue;
434  }
435 
436  diff = LumMotionErrorC(currentBlock, prev, by, bx, my, mx, bestDiff[2]);
437 
438  if ( diff < bestDiff[2] ) {
439  bestMY[2] = my;
440  bestMX[2] = mx;
441  bestDiff[2] = diff;
442  }
443  }
444  }
445 
446  /* do D pattern */
447  for ( my = -searchRange; my < rightMY; my += 2*stepSize ) {
448  if ( my < leftMY ) {
449  continue;
450  }
451 
452  for ( mx = stepSize-searchRange; mx < rightMX; mx += 2*stepSize ) {
453  if ( mx < leftMX ) {
454  continue;
455  }
456 
457  diff = LumMotionErrorD(currentBlock, prev, by, bx, my, mx, bestDiff[3]);
458 
459  if ( diff < bestDiff[3] ) {
460  bestMY[3] = my;
461  bestMX[3] = mx;
462  bestDiff[3] = diff;
463  }
464  }
465  }
466 
467  /* first check old motion */
468  if ( (*motionY >= leftMY) && (*motionY < rightMY) &&
469  (*motionX >= leftMX) && (*motionX < rightMX) ) {
470  bestBestDiff = LumMotionError(currentBlock, prev, by, bx, *motionY, *motionX, 0x7fffffff);
471  } else {
472  bestBestDiff = 0x7fffffff;
473  }
474 
475  /* look at Error of 4 different motion vectors */
476  for ( x = 0; x < 4; x++ ) {
477  bestDiff[x] = LumMotionError(currentBlock, prev, by, bx,
478  bestMY[x], bestMX[x], bestBestDiff);
479 
480  if ( bestDiff[x] < bestBestDiff ) {
481  bestBestDiff = bestDiff[x];
482  *motionY = bestMY[x];
483  *motionX = bestMX[x];
484  }
485  }
486 
487  return bestBestDiff;
488 }
489 
490 
491 /*===========================================================================*
492  *
493  * PLogarithmicSearch
494  *
495  * uses logarithmic search to compute the P-frame vector
496  *
497  * RETURNS: motion vector
498  *
499  * SIDE EFFECTS: none
500  *
501  * REFERENCE: MPEG-I specification, pages 32-33
502  *
503  *===========================================================================*/
504 int32
505 PLogarithmicSearch(currentBlock, prev, by, bx, motionY, motionX, searchRange)
506  LumBlock currentBlock;
507  MpegFrame *prev;
508  int by;
509  int bx;
510  int *motionY;
511  int *motionX;
512  int searchRange;
513 {
514  register int mx, my;
515  int32 diff, bestDiff;
516  int stepSize;
517  int leftMY, leftMX;
518  int rightMY, rightMX;
519  int tempRightMY, tempRightMX;
520  int spacing;
521  int centerX, centerY;
522  int newCenterX, newCenterY;
523 
524  stepSize = (pixelFullSearch ? 2 : 1);
525 
526  COMPUTE_MOTION_BOUNDARY(by,bx,stepSize,leftMY,leftMX,rightMY,rightMX);
527 
528  bestDiff = 0x7fffffff;
529 
530  /* grid spacing */
531  if ( stepSize == 2 ) { /* make sure spacing is even */
532  spacing = (searchRange+1)/2;
533  if ( (spacing % 2) != 0 ) {
534  spacing--;
535  }
536  } else {
537  spacing = (searchRange+1)/2;
538  }
539  centerX = 0;
540  centerY = 0;
541 
542  while ( spacing >= stepSize ) {
543  newCenterY = centerY;
544  newCenterX = centerX;
545 
546  tempRightMY = rightMY;
547  if ( centerY+spacing+1 < tempRightMY ) {
548  tempRightMY = centerY+spacing+1;
549  }
550  tempRightMX = rightMX;
551  if ( centerX+spacing+1 < tempRightMX ) {
552  tempRightMX = centerX+spacing+1;
553  }
554 
555  for ( my = centerY-spacing; my < tempRightMY; my += spacing ) {
556  if ( my < leftMY ) {
557  continue;
558  }
559 
560  for ( mx = centerX-spacing; mx < tempRightMX; mx += spacing ) {
561  if ( mx < leftMX ) {
562  continue;
563  }
564 
565  diff = LumMotionError(currentBlock, prev, by, bx, my, mx, bestDiff);
566 
567  if ( diff < bestDiff ) {
568  newCenterY = my;
569  newCenterX = mx;
570 
571  bestDiff = diff;
572  }
573  }
574  }
575 
576  centerY = newCenterY;
577  centerX = newCenterX;
578 
579  if ( stepSize == 2 ) { /* make sure spacing is even */
580  if ( spacing == 2 ) {
581  spacing = 0;
582  } else {
583  spacing = (spacing+1)/2;
584  if ( (spacing % 2) != 0 ) {
585  spacing--;
586  }
587  }
588  } else {
589  if ( spacing == 1 ) {
590  spacing = 0;
591  } else {
592  spacing = (spacing+1)/2;
593  }
594  }
595  }
596 
597  /* check old motion -- see if it's better */
598  if ( (*motionY >= leftMY) && (*motionY < rightMY) &&
599  (*motionX >= leftMX) && (*motionX < rightMX) ) {
600  diff = LumMotionError(currentBlock, prev, by, bx, *motionY, *motionX, bestDiff);
601  } else {
602  diff = 0x7fffffff;
603  }
604 
605  if ( bestDiff < diff ) {
606  *motionY = centerY;
607  *motionX = centerX;
608  } else {
609  bestDiff = diff;
610  }
611 
612  return bestDiff;
613 }
614 
615 
616 /*===========================================================================*
617  *
618  * PLocalSearch
619  *
620  * uses local exhaustive search to compute the P-frame vector
621  *
622  * RETURNS: motion vector
623  *
624  * SIDE EFFECTS: none
625  *
626  *===========================================================================*/
627 int32
628 PLocalSearch(currentBlock, prev, by, bx, motionY, motionX, bestSoFar, searchRange)
629  LumBlock currentBlock;
630  MpegFrame *prev;
631  int by;
632  int bx;
633  int *motionY;
634  int *motionX;
635  int32 bestSoFar;
636  int searchRange;
637 {
638  register int mx, my;
639  int32 diff, bestDiff;
640  int stepSize;
641  int leftMY, leftMX;
642  int rightMY, rightMX;
643  int distance;
644  int tempRightMY, tempRightMX;
645 
646  stepSize = (pixelFullSearch ? 2 : 1);
647 
648  COMPUTE_MOTION_BOUNDARY(by,bx,stepSize,leftMY,leftMX,rightMY,rightMX);
649 
650  /* try old motion vector first */
651  if ( VALID_MOTION(*motionY, *motionX) ) {
652  bestDiff = LumMotionError(currentBlock, prev, by, bx, *motionY, *motionX, bestSoFar);
653 
654  if ( bestSoFar < bestDiff ) {
655  bestDiff = bestSoFar;
656  }
657  } else {
658  *motionY = 0;
659  *motionX = 0;
660 
661  bestDiff = bestSoFar;
662  }
663 
664  /* try a spiral pattern */
665  for ( distance = stepSize; distance <= searchRange;
666  distance += stepSize ) {
667  tempRightMY = rightMY;
668  if ( distance < tempRightMY ) {
669  tempRightMY = distance;
670  }
671  tempRightMX = rightMX;
672  if ( distance < tempRightMX ) {
673  tempRightMX = distance;
674  }
675 
676  /* do top, bottom */
677  for ( my = -distance; my < tempRightMY;
678  my += max(tempRightMY+distance-stepSize, stepSize) ) {
679  if ( my < leftMY ) {
680  continue;
681  }
682 
683  for ( mx = -distance; mx < tempRightMX; mx += stepSize ) {
684  if ( mx < leftMX ) {
685  continue;
686  }
687 
688  diff = LumMotionError(currentBlock, prev, by, bx, my, mx, bestDiff);
689 
690  if ( diff < bestDiff ) {
691  *motionY = my;
692  *motionX = mx;
693  bestDiff = diff;
694  }
695  }
696  }
697 
698  /* do left, right */
699  for ( mx = -distance; mx < tempRightMX;
700  mx += max(tempRightMX+distance-stepSize, stepSize) ) {
701  if ( mx < leftMX ) {
702  continue;
703  }
704 
705  for ( my = -distance+stepSize; my < tempRightMY-stepSize;
706  my += stepSize ) {
707  if ( my < leftMY ) {
708  continue;
709  }
710 
711  diff = LumMotionError(currentBlock, prev, by, bx, my, mx, bestDiff);
712 
713  if ( diff < bestDiff ) {
714  *motionY = my;
715  *motionX = mx;
716  bestDiff = diff;
717  }
718  }
719  }
720  }
721 
722  return bestDiff;
723 }
724 
725 
726 /*===========================================================================*
727  *
728  * PTwoLevelSearch
729  *
730  * uses two-level search to compute the P-frame vector
731  * first does exhaustive full-pixel search, then looks at neighboring
732  * half-pixel motion vectors
733  *
734  * RETURNS: motion vector
735  *
736  * SIDE EFFECTS: none
737  *
738  *===========================================================================*/
739 int32
740 PTwoLevelSearch(currentBlock, prev, by, bx, motionY, motionX, bestSoFar, searchRange)
741  LumBlock currentBlock;
742  MpegFrame *prev;
743  int by;
744  int bx;
745  int *motionY;
746  int *motionX;
747  int32 bestSoFar;
748  int searchRange;
749 {
750  register int mx, my;
751  register int loopInc;
752  int32 diff, bestDiff;
753  int leftMY, leftMX;
754  int rightMY, rightMX;
755  int distance;
756  int tempRightMY, tempRightMX;
757  int xOffset, yOffset;
758 
759  /* exhaustive full-pixel search first */
760 
761  COMPUTE_MOTION_BOUNDARY(by,bx,2,leftMY,leftMX,rightMY,rightMX);
762 
763  rightMY--;
764  rightMX--;
765 
766  /* convert vector into full-pixel vector */
767  if ( *motionY > 0 ) {
768  if ( ((*motionY) % 2) == 1 ) {
769  (*motionY)--;
770  }
771  } else if ( ((-(*motionY)) % 2) == 1 ) {
772  (*motionY)++;
773  }
774 
775  if ( *motionX > 0 ) {
776  if ( ((*motionX) % 2) == 1 ) {
777  (*motionX)--;
778  }
779  } else if ( ((-(*motionX)) % 2) == 1 ) {
780  (*motionX)++;
781  }
782 
783  /* try old motion vector first */
784  if ( VALID_MOTION(*motionY, *motionX) ) {
785  bestDiff = LumMotionError(currentBlock, prev, by, bx, *motionY, *motionX, bestSoFar);
786 
787  if ( bestSoFar < bestDiff ) {
788  bestDiff = bestSoFar;
789  }
790  } else {
791  *motionY = 0;
792  *motionX = 0;
793 
794  bestDiff = bestSoFar;
795  }
796 
797  rightMY++;
798  rightMX++;
799 
800  /* try a spiral pattern */
801  for ( distance = 2; distance <= searchRange; distance += 2 ) {
802  tempRightMY = rightMY;
803  if ( distance < tempRightMY ) {
804  tempRightMY = distance;
805  }
806  tempRightMX = rightMX;
807  if ( distance < tempRightMX ) {
808  tempRightMX = distance;
809  }
810 
811  /* do top, bottom */
812  loopInc = max(tempRightMY+distance-2, 2);
813  for ( my = -distance; my < tempRightMY; my += loopInc ) {
814  if ( my < leftMY ) {
815  continue;
816  }
817 
818  for ( mx = -distance; mx < tempRightMX; mx += 2 ) {
819  if ( mx < leftMX ) {
820  continue;
821  }
822 
823  diff = LumMotionError(currentBlock, prev, by, bx, my, mx, bestDiff);
824 
825  if ( diff < bestDiff ) {
826  *motionY = my;
827  *motionX = mx;
828  bestDiff = diff;
829  }
830  }
831  }
832 
833  /* do left, right */
834  loopInc = max(tempRightMX+distance-2, 2);
835  for ( mx = -distance; mx < tempRightMX; mx += loopInc ) {
836  if ( mx < leftMX ) {
837  continue;
838  }
839 
840  for ( my = -distance+2; my < tempRightMY-2; my += 2 ) {
841  if ( my < leftMY ) {
842  continue;
843  }
844 
845  diff = LumMotionError(currentBlock, prev, by, bx, my, mx, bestDiff);
846 
847  if ( diff < bestDiff ) {
848  *motionY = my;
849  *motionX = mx;
850  bestDiff = diff;
851  }
852  }
853  }
854  }
855 
856  /* now look at neighboring half-pixels */
857  my = *motionY;
858  mx = *motionX;
859 
860  rightMY--;
861  rightMX--;
862 
863  for ( yOffset = -1; yOffset <= 1; yOffset++ ) {
864  for ( xOffset = -1; xOffset <= 1; xOffset++ ) {
865  if ( (yOffset == 0) && (xOffset == 0) )
866  continue;
867 
868  if ( VALID_MOTION(my+yOffset, mx+xOffset) &&
869  ((diff = LumMotionError(currentBlock, prev, by, bx,
870  my+yOffset, mx+xOffset, bestDiff)) < bestDiff) ) {
871  *motionY = my+yOffset;
872  *motionX = mx+xOffset;
873  bestDiff = diff;
874  }
875  }
876  }
877 
878  return bestDiff;
879 }
880 
881 
882 void
884  FILE *fpointer;
885 {
886  register int x, y;
887  int *columnTotals;
888  int rowTotal;
889 
890  columnTotals = (int *) calloc(2*searchRangeP+3, sizeof(int));
891 
892 #ifdef COMPLETE_DISPLAY
893  fprintf(fpointer, " ");
894  for ( y = 0; y < 2*searchRange+3; y++ ) {
895  fprintf(fpointer, "%3d ", y-searchRangeP-1);
896  }
897  fprintf(fpointer, "\n");
898 #endif
899 
900  for ( x = 0; x < 2*searchRangeP+3; x++ ) {
901 #ifdef COMPLETE_DISPLAY
902  fprintf(fpointer, "%3d ", x-searchRangeP-1);
903 #endif
904  rowTotal = 0;
905  for ( y = 0; y < 2*searchRangeP+3; y++ ) {
906  fprintf(fpointer, "%3d ", pmvHistogram[x][y]);
907  rowTotal += pmvHistogram[x][y];
908  columnTotals[y] += pmvHistogram[x][y];
909  }
910 #ifdef COMPLETE_DISPLAY
911  fprintf(fpointer, "%4d\n", rowTotal);
912 #else
913  fprintf(fpointer, "\n");
914 #endif
915  }
916 
917 #ifdef COMPLETE_DISPLAY
918  fprintf(fpointer, "Tot ");
919  for ( y = 0; y < 2*searchRangeP+3; y++ ) {
920  fprintf(fpointer, "%3d ", columnTotals[y]);
921  }
922 #endif
923  fprintf(fpointer, "\n");
924 }
925 
926 
927 void
929  FILE *fpointer;
930 {
931  register int x, y;
932  int *columnTotals;
933  int rowTotal;
934 
935  fprintf(fpointer, "B-frame Backwards:\n");
936 
937  columnTotals = (int *) calloc(2*searchRangeB+3, sizeof(int));
938 
939 #ifdef COMPLETE_DISPLAY
940  fprintf(fpointer, " ");
941  for ( y = 0; y < 2*searchRangeB+3; y++ ) {
942  fprintf(fpointer, "%3d ", y-searchRangeB-1);
943  }
944  fprintf(fpointer, "\n");
945 #endif
946 
947  for ( x = 0; x < 2*searchRangeB+3; x++ ) {
948 #ifdef COMPLETE_DISPLAY
949  fprintf(fpointer, "%3d ", x-searchRangeB-1);
950 #endif
951  rowTotal = 0;
952  for ( y = 0; y < 2*searchRangeB+3; y++ ) {
953  fprintf(fpointer, "%3d ", bbmvHistogram[x][y]);
954  rowTotal += bbmvHistogram[x][y];
955  columnTotals[y] += bbmvHistogram[x][y];
956  }
957 #ifdef COMPLETE_DISPLAY
958  fprintf(fpointer, "%4d\n", rowTotal);
959 #else
960  fprintf(fpointer, "\n");
961 #endif
962  }
963 
964 #ifdef COMPLETE_DISPLAY
965  fprintf(fpointer, "Tot ");
966  for ( y = 0; y < 2*searchRangeB+3; y++ ) {
967  fprintf(fpointer, "%3d ", columnTotals[y]);
968  }
969 #endif
970  fprintf(fpointer, "\n");
971 }
972 
973 
974 void
976  FILE *fpointer;
977 {
978  register int x, y;
979  int *columnTotals;
980  int rowTotal;
981 
982  fprintf(fpointer, "B-frame Forwards:\n");
983 
984  columnTotals = (int *) calloc(2*searchRangeB+3, sizeof(int));
985 
986 #ifdef COMPLETE_DISPLAY
987  fprintf(fpointer, " ");
988  for ( y = 0; y < 2*searchRangeB+3; y++ ) {
989  fprintf(fpointer, "%3d ", y-searchRangeB-1);
990  }
991  fprintf(fpointer, "\n");
992 #endif
993 
994  for ( x = 0; x < 2*searchRangeB+3; x++ ) {
995 #ifdef COMPLETE_DISPLAY
996  fprintf(fpointer, "%3d ", x-searchRangeB-1);
997 #endif
998  rowTotal = 0;
999  for ( y = 0; y < 2*searchRangeB+3; y++ ) {
1000  fprintf(fpointer, "%3d ", bfmvHistogram[x][y]);
1001  rowTotal += bfmvHistogram[x][y];
1002  columnTotals[y] += bfmvHistogram[x][y];
1003  }
1004 #ifdef COMPLETE_DISPLAY
1005  fprintf(fpointer, "%4d\n", rowTotal);
1006 #else
1007  fprintf(fpointer, "\n");
1008 #endif
1009  }
1010 
1011 #ifdef COMPLETE_DISPLAY
1012  fprintf(fpointer, "Tot ");
1013  for ( y = 0; y < 2*searchRangeB+3; y++ ) {
1014  fprintf(fpointer, "%3d ", columnTotals[y]);
1015  }
1016 #endif
1017  fprintf(fpointer, "\n");
1018 }
1019 
1020 
1021 /*=====================*
1022  * INTERNAL PROCEDURES *
1023  *=====================*/
1024 
1025  /* none */
1026 
int32 LumMotionError(LumBlock currentBlock, MpegFrame *prevFrame, int by, int bx, int my, int mx, int32 bestSoFar)
Definition: block.c:506
static char mx
Definition: bmpfont.h:51
@ FALSE
Definition: dd.h:101
@ TRUE
Definition: dd.h:102
int strcmp()
Definition: coll.cpp:143
int32 LumMotionErrorB(LumBlock current, MpegFrame *prevFrame, int by, int bx, int my, int mx, int32 bestSoFar)
Definition: subsample.c:270
int32 LumMotionErrorA(LumBlock current, MpegFrame *prevFrame, int by, int bx, int my, int mx, int32 bestSoFar)
Definition: subsample.c:93
int32 LumMotionErrorD(LumBlock current, MpegFrame *prevFrame, int by, int bx, int my, int mx, int32 bestSoFar)
Definition: subsample.c:624
int32 LumMotionErrorC(LumBlock current, MpegFrame *prevFrame, int by, int bx, int my, int mx, int32 bestSoFar)
Definition: subsample.c:447
static FIELD_PTR prev
Definition: genind.c:36
#define NULL
Definition: ftobjs.h:61
void exit()
kerning y
Definition: ttdriver.c:212
voidp calloc()
#define fprintf
Definition: mendex.h:64
#define malloc
Definition: alloca.c:91
int distance
Definition: lengths.c:38
long int32
Definition: tiff.h:67
int searchRangeP
Definition: psearch.c:104
void MotionSearchPreComputation(MpegFrame *frame)
Definition: psearch.c:325
int32 PLocalSearch(LumBlock currentBlock, MpegFrame *prev, int by, int bx, int *motionY, int *motionX, int32 bestSoFar, int searchRange)
Definition: psearch.c:628
int psearchAlg
Definition: psearch.c:105
int ** bbmvHistogram
Definition: psearch.c:101
int32 PLogarithmicSearch(LumBlock currentBlock, MpegFrame *prev, int by, int bx, int *motionY, int *motionX, int searchRange)
Definition: psearch.c:505
int ** bfmvHistogram
Definition: psearch.c:102
void ShowBFMVHistogram(FILE *fpointer)
Definition: psearch.c:975
void SetPixelSearch(char *searchType)
Definition: psearch.c:196
int pixelFullSearch
Definition: psearch.c:103
void ShowBBMVHistogram(FILE *fpointer)
Definition: psearch.c:928
void ShowPMVHistogram(FILE *fpointer)
Definition: psearch.c:883
int searchRangeB
Definition: psearch.c:104
boolean PMotionSearch(LumBlock currentBlock, MpegFrame *prev, int by, int bx, int *motionY, int *motionX)
Definition: psearch.c:150
int32 PSubSampleSearch(LumBlock currentBlock, MpegFrame *prev, int by, int bx, int *motionY, int *motionX, int searchRange)
Definition: psearch.c:348
void SetPSearchAlg(char *alg)
Definition: psearch.c:223
int ** pmvHistogram
Definition: psearch.c:100
char * PSearchName()
Definition: psearch.c:253
int32 PTwoLevelSearch(LumBlock currentBlock, MpegFrame *prev, int by, int bx, int *motionY, int *motionX, int32 bestSoFar, int searchRange)
Definition: psearch.c:740
void SetSearchRange(int pixelsP, int pixelsB)
Definition: psearch.c:283
#define PSEARCH_TWOLEVEL
Definition: motion_search.h:67
#define COMPUTE_MOTION_BOUNDARY(by, bx, stepSize, leftMY, leftMX, rightMY, rightMX)
Definition: motion_search.h:78
#define VALID_MOTION(y, x)
Definition: motion_search.h:90
#define PSEARCH_LOGARITHMIC
Definition: motion_search.h:66
#define PSEARCH_SUBSAMPLE
Definition: motion_search.h:64
#define PSEARCH_EXHAUSTIVE
Definition: motion_search.h:65
int32 LumBlock[2 *8][2 *8]
Definition: mtypes.h:101
float x
Definition: cordic.py:15
boolean computeMVHist
Definition: main.c:160
#define max(a, b)
Definition: pbmto4425.c:11
#define index(s, c)
Definition: plain2.h:351
int spacing
Definition: process_score.c:12
Definition: mendex.h:20
#define FILE
Definition: t1stdio.h:34
int diff
Definition: tex4ht.c:3815