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