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