1 /*===========================================================================*
2 * bsearch.c *
3 * *
4 * Procedures concerned with the B-frame motion search *
5 * *
6 * EXPORTED PROCEDURES: *
7 * SetBSearchAlg *
8 * BMotionSearch *
9 * BSearchName *
10 * *
11 *===========================================================================*/
12
13 /*
14 * Copyright (c) 1995 The Regents of the University of California.
15 * All rights reserved.
16 *
17 * Permission to use, copy, modify, and distribute this software and its
18 * documentation for any purpose, without fee, and without written agreement is
19 * hereby granted, provided that the above copyright notice and the following
20 * two paragraphs appear in all copies of this software.
21 *
22 * IN NO EVENT SHALL THE UNIVERSITY OF CALIFORNIA BE LIABLE TO ANY PARTY FOR
23 * DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES ARISING OUT
24 * OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN IF THE UNIVERSITY OF
25 * CALIFORNIA HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
26 *
27 * THE UNIVERSITY OF CALIFORNIA SPECIFICALLY DISCLAIMS ANY WARRANTIES,
28 * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY
29 * AND FITNESS FOR A PARTICULAR PURPOSE. THE SOFTWARE PROVIDED HEREUNDER IS
30 * ON AN "AS IS" BASIS, AND THE UNIVERSITY OF CALIFORNIA HAS NO OBLIGATION TO
31 * PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS.
32 */
33
34 /*
35 * $Header: /n/picasso/project/mpeg/mpeg_dist/mpeg_encode/RCS/bsearch.c,v 1.10 1995/08/07 21:49:01 smoot Exp $
36 * $Log: bsearch.c,v $
37 * Revision 1.10 1995/08/07 21:49:01 smoot
38 * fixed bug in initial-B-frame searches
39 *
40 * Revision 1.9 1995/06/26 21:36:07 smoot
41 * added new ordering constraints
42 * (B frames which are backward P's at the start of a sequence)
43 *
44 * Revision 1.8 1995/03/27 19:17:43 smoot
45 * killed useless type error messge (int32 defiend as int)
46 *
47 * Revision 1.7 1995/01/19 23:07:20 eyhung
48 * Changed copyrights
49 *
50 * Revision 1.6 1994/12/07 00:40:36 smoot
51 * Added seperate P and B search ranges
52 *
53 * Revision 1.5 1994/03/15 00:27:11 keving
54 * nothing
55 *
56 * Revision 1.4 1993/12/22 19:19:01 keving
57 * nothing
58 *
59 * Revision 1.3 1993/07/22 22:23:43 keving
60 * nothing
61 *
62 * Revision 1.2 1993/06/30 20:06:09 keving
63 * nothing
64 *
65 * Revision 1.1 1993/06/03 21:08:08 keving
66 * nothing
67 *
68 * Revision 1.1 1993/03/02 18:27:05 keving
69 * nothing
70 *
71 */
72
73
74 /*==============*
75 * HEADER FILES *
76 *==============*/
77 #include <string.h>
78 #include "all.h"
79 #include "mtypes.h"
80 #include "frames.h"
81 #include "search.h"
82 #include "fsize.h"
83
84
85 /*==================*
86 * STATIC VARIABLES *
87 *==================*/
88
89 static int bsearchAlg;
90
91
92 /*===============================*
93 * INTERNAL PROCEDURE prototypes *
94 *===============================*/
95
96 static int32 FindBestMatch _ANSI_ARGS_((LumBlock block, LumBlock currentBlock, MpegFrame *prev,
97 int by, int bx, int *motionY, int *motionX, int32 bestSoFar, int searchRange));
98 static int BMotionSearchSimple _ANSI_ARGS_((LumBlock currentBlock, MpegFrame *prev,
99 MpegFrame *next, int by, int bx, int *fmy, int *fmx,
100 int *bmy, int *bmx, int oldMode));
101 static int BMotionSearchCross2 _ANSI_ARGS_((LumBlock currentBlock, MpegFrame *prev,
102 MpegFrame *next, int by, int bx, int *fmy, int *fmx,
103 int *bmy, int *bmx, int oldMode));
104 static int BMotionSearchExhaust _ANSI_ARGS_((LumBlock currentBlock, MpegFrame *prev,
105 MpegFrame *next, int by, int bx, int *fmy, int *fmx,
106 int *bmy, int *bmx, int oldMode));
107 static void BMotionSearchNoInterp _ANSI_ARGS_((LumBlock currentBlock, MpegFrame *prev,
108 MpegFrame *next, int by, int bx,
109 int *fmy, int *fmx, int32 *forwardErr,
110 int *bmy, int *bmx, int32 *backErr,
111 boolean backNeeded));
112 static int32 FindBestMatchExhaust _ANSI_ARGS_((LumBlock block, LumBlock currentBlock, MpegFrame *prev,
113 int by, int bx, int *motionY, int *motionX,
114 int32 bestSoFar, int searchRange));
115 static int32 FindBestMatchTwoLevel _ANSI_ARGS_((LumBlock block, LumBlock currentBlock, MpegFrame *prev,
116 int by, int bx, int *motionY, int *motionX,
117 int32 bestSoFar, int searchRange));
118 static int32 FindBestMatchLogarithmic _ANSI_ARGS_((LumBlock block, LumBlock currentBlock, MpegFrame *prev,
119 int by, int bx, int *motionY, int *motionX,
120 int32 bestSoFar, int searchRange));
121 static int32 FindBestMatchSubSample _ANSI_ARGS_((LumBlock block, LumBlock currentBlock, MpegFrame *prev,
122 int by, int bx, int *motionY, int *motionX,
123 int32 bestSoFar, int searchRange));
124
125
126 /*=====================*
127 * EXPORTED PROCEDURES *
128 *=====================*/
129
130 /*===========================*
131 * INITIALIZATION PROCEDURES *
132 *===========================*/
133
134
135 /*===========================================================================*
136 *
137 * SetBSearchAlg
138 *
139 * set the B-search algorithm
140 *
141 * RETURNS: nothing
142 *
143 * SIDE EFFECTS: bsearchAlg modified
144 *
145 *===========================================================================*/
146 void
SetBSearchAlg(char * alg)147 SetBSearchAlg(char *alg)
148 {
149 if ( strcmp(alg, "SIMPLE") == 0 ) {
150 bsearchAlg = BSEARCH_SIMPLE;
151 } else if ( strcmp(alg, "CROSS2") == 0 ) {
152 bsearchAlg = BSEARCH_CROSS2;
153 } else if ( strcmp(alg, "EXHAUSTIVE") == 0 ) {
154 bsearchAlg = BSEARCH_EXHAUSTIVE;
155 } else {
156 throw "Illegal bsearch algorithm";
157 }
158 }
159
160
161 /*===========================================================================*
162 *
163 * BSearchName
164 *
165 * return the text of the B-search algorithm
166 *
167 * RETURNS: a pointer to the string
168 *
169 * SIDE EFFECTS: none
170 *
171 *===========================================================================*/
172 char *
BSearchName()173 BSearchName()
174 {
175 switch(bsearchAlg) {
176 case BSEARCH_SIMPLE:
177 return (char*)"SIMPLE";
178 case BSEARCH_CROSS2:
179 return (char*)"CROSS2";
180 case BSEARCH_EXHAUSTIVE:
181 return (char*)"EXHAUSTIVE";
182 default:
183 throw "Error in BSearchName";
184 break;
185 }
186 }
187
188
189 /*===========================================================================*
190 *
191 * BMotionSearch
192 *
193 * search for the best B-frame motion vectors
194 *
195 * RETURNS: MOTION_FORWARD forward motion should be used
196 * MOTION_BACKWARD backward motion should be used
197 * MOTION_INTERPOLATE both should be used and interpolated
198 *
199 * OUTPUTS: *fmx, *fmy = TWICE the forward motion vector
200 * *bmx, *bmy = TWICE the backward motion vector
201 *
202 * SIDE EFFECTS: none
203 *
204 * PRECONDITIONS: The relevant block in 'current' is valid (it has not
205 * been dct'd). Thus, the data in 'current' can be
206 * accesed through y_blocks, cr_blocks, and cb_blocks.
207 * This is not the case for the blocks in 'prev' and
208 * 'next.' Therefore, references into 'prev' and 'next'
209 * should be done
210 * through the struct items ref_y, ref_cr, ref_cb
211 *
212 * POSTCONDITIONS: current, prev, next should be unchanged.
213 * Some computation could be saved by requiring
214 * the dct'd difference to be put into current's block
215 * elements here, depending on the search technique.
216 * However, it was decided that it mucks up the code
217 * organization a little, and the saving in computation
218 * would be relatively little (if any).
219 *
220 * NOTES: the search procedure MAY return (0,0) motion vectors
221 *
222 *===========================================================================*/
223 int
BMotionSearch(LumBlock currentBlock,MpegFrame * prev,MpegFrame * next,int by,int bx,int * fmy,int * fmx,int * bmy,int * bmx,int oldMode)224 BMotionSearch(LumBlock currentBlock,
225 MpegFrame *prev,
226 MpegFrame *next,
227 int by,
228 int bx,
229 int *fmy,
230 int *fmx,
231 int *bmy,
232 int *bmx,
233 int oldMode)
234 {
235 /* If we are an initial B frame, no possibility of forward motion */
236 if (prev == (MpegFrame *) NULL) {
237 PMotionSearch(currentBlock, next, by, bx, bmy, bmx);
238 return MOTION_BACKWARD;
239 }
240
241 /* otherwise simply call the appropriate algorithm, based on user preference */
242
243 switch(bsearchAlg) {
244 case BSEARCH_SIMPLE:
245 return BMotionSearchSimple(currentBlock, prev, next, by, bx, fmy,
246 fmx, bmy, bmx, oldMode);
247 break;
248 case BSEARCH_CROSS2:
249 return BMotionSearchCross2(currentBlock, prev, next, by, bx, fmy,
250 fmx, bmy, bmx, oldMode);
251 break;
252 case BSEARCH_EXHAUSTIVE:
253 return BMotionSearchExhaust(currentBlock, prev, next, by, bx, fmy,
254 fmx, bmy, bmx, oldMode);
255 break;
256 default:
257 throw "Illegal B-frame motion search algorithm";
258 }
259 }
260
261
262 /*===========================================================================*
263 *
264 * BMotionSearchSimple
265 *
266 * does a simple search for B-frame motion vectors
267 * see BMotionSearch for generic description
268 *
269 * DESCRIPTION:
270 * 1) find best backward and forward vectors
271 * 2) compute interpolated error using those two vectors
272 * 3) return the best of the three choices
273 *
274 *===========================================================================*/
275 static int
BMotionSearchSimple(LumBlock currentBlock,MpegFrame * prev,MpegFrame * next,int by,int bx,int * fmy,int * fmx,int * bmy,int * bmx,int oldMode)276 BMotionSearchSimple(LumBlock currentBlock,
277 MpegFrame *prev,
278 MpegFrame *next,
279 int by,
280 int bx,
281 int *fmy,
282 int *fmx,
283 int *bmy,
284 int *bmx,
285 int oldMode)
286 {
287 int32 forwardErr, backErr, interpErr;
288 LumBlock interpBlock;
289 int32 bestSoFar;
290
291 /* STEP 1 */
292 BMotionSearchNoInterp(currentBlock, prev, next, by, bx, fmy, fmx,
293 &forwardErr, bmy, bmx, &backErr, TRUE);
294
295 /* STEP 2 */
296
297 ComputeBMotionLumBlock(prev, next, by, bx, MOTION_INTERPOLATE,
298 *fmy, *fmx, *bmy, *bmx, interpBlock);
299 bestSoFar = min(backErr, forwardErr);
300 interpErr = LumBlockMAD(currentBlock, interpBlock, bestSoFar);
301
302 /* STEP 3 */
303
304 if ( interpErr <= forwardErr ) {
305 if ( interpErr <= backErr ) {
306 return MOTION_INTERPOLATE;
307 }
308 else
309 return MOTION_BACKWARD;
310 } else if ( forwardErr <= backErr ) {
311 return MOTION_FORWARD;
312 } else {
313 return MOTION_BACKWARD;
314 }
315 }
316
317
318 /*===========================================================================*
319 *
320 * BMotionSearchCross2
321 *
322 * does a cross-2 search for B-frame motion vectors
323 * see BMotionSearch for generic description
324 *
325 * DESCRIPTION:
326 * 1) find best backward and forward vectors
327 * 2) find best matching interpolating vectors
328 * 3) return the best of the 4 choices
329 *
330 *===========================================================================*/
331 static int
BMotionSearchCross2(LumBlock currentBlock,MpegFrame * prev,MpegFrame * next,int by,int bx,int * fmy,int * fmx,int * bmy,int * bmx,int oldMode)332 BMotionSearchCross2(LumBlock currentBlock,
333 MpegFrame *prev,
334 MpegFrame *next,
335 int by,
336 int bx,
337 int *fmy,
338 int *fmx,
339 int *bmy,
340 int *bmx,
341 int oldMode)
342 {
343 LumBlock forwardBlock, backBlock;
344 int32 forwardErr, backErr, interpErr;
345 int newfmy, newfmx, newbmy, newbmx;
346 int32 interpErr2;
347 int32 bestErr;
348
349 /* STEP 1 */
350
351 BMotionSearchNoInterp(currentBlock, prev, next, by, bx, fmy, fmx,
352 &forwardErr, bmy, bmx, &backErr, TRUE);
353
354 bestErr = min(forwardErr, backErr);
355
356 /* STEP 2 */
357 ComputeBMotionLumBlock(prev, next, by, bx, MOTION_FORWARD,
358 *fmy, *fmx, 0, 0, forwardBlock);
359 ComputeBMotionLumBlock(prev, next, by, bx, MOTION_BACKWARD,
360 0, 0, *bmy, *bmx, backBlock);
361
362 /* try a cross-search; total of 4 local searches */
363 newbmy = *bmy; newbmx = *bmx;
364 newfmy = *fmy; newfmx = *fmx;
365
366 interpErr = FindBestMatch(forwardBlock, currentBlock, next, by, bx,
367 &newbmy, &newbmx, bestErr, searchRangeB);
368 bestErr = min(bestErr, interpErr);
369 interpErr2 = FindBestMatch(backBlock, currentBlock, prev, by, bx,
370 &newfmy, &newfmx, bestErr, searchRangeB);
371
372 /* STEP 3 */
373
374 if ( interpErr <= interpErr2 ) {
375 newfmy = *fmy;
376 newfmx = *fmx;
377 }
378 else
379 {
380 newbmy = *bmy;
381 newbmx = *bmx;
382 interpErr = interpErr2;
383 }
384
385 if ( interpErr <= forwardErr ) {
386 if ( interpErr <= backErr ) {
387 *fmy = newfmy;
388 *fmx = newfmx;
389 *bmy = newbmy;
390 *bmx = newbmx;
391
392 return MOTION_INTERPOLATE;
393 }
394 else
395 return MOTION_BACKWARD;
396 } else if ( forwardErr <= backErr ) {
397 return MOTION_FORWARD;
398 } else {
399 return MOTION_BACKWARD;
400 }
401 }
402
403
404 /*===========================================================================*
405 *
406 * BMotionSearchExhaust
407 *
408 * does an exhaustive search for B-frame motion vectors
409 * see BMotionSearch for generic description
410 *
411 * DESCRIPTION:
412 * 1) find best backward and forward vectors
413 * 2) use exhaustive search to find best interpolating vectors
414 * 3) return the best of the 3 choices
415 *
416 *===========================================================================*/
417 static int
BMotionSearchExhaust(LumBlock currentBlock,MpegFrame * prev,MpegFrame * next,int by,int bx,int * fmy,int * fmx,int * bmy,int * bmx,int oldMode)418 BMotionSearchExhaust(LumBlock currentBlock,
419 MpegFrame *prev,
420 MpegFrame *next,
421 int by,
422 int bx,
423 int *fmy,
424 int *fmx,
425 int *bmy,
426 int *bmx,
427 int oldMode)
428 {
429 register int mx, my;
430 int32 diff, bestDiff;
431 int stepSize;
432 LumBlock forwardBlock;
433 int32 forwardErr, backErr;
434 int newbmy, newbmx;
435 int leftMY, leftMX;
436 int rightMY, rightMX;
437 boolean result;
438
439 /* STEP 1 */
440
441 BMotionSearchNoInterp(currentBlock, prev, next, by, bx, fmy, fmx,
442 &forwardErr, bmy, bmx, &backErr, FALSE);
443
444 if ( forwardErr <= backErr ) {
445 bestDiff = forwardErr;
446 result = MOTION_FORWARD;
447 }
448 else
449 {
450 bestDiff = backErr;
451 result = MOTION_BACKWARD;
452 }
453
454 /* STEP 2 */
455
456 stepSize = (pixelFullSearch ? 2 : 1);
457
458 COMPUTE_MOTION_BOUNDARY(by,bx,stepSize,leftMY,leftMX,rightMY,rightMX);
459
460 if ( searchRangeB < rightMY ) {
461 rightMY = searchRangeB;
462 }
463 if ( searchRangeB < rightMX ) {
464 rightMX = searchRangeB;
465 }
466
467 for ( my = -searchRangeB; my < rightMY; my += stepSize ) {
468 if ( my < leftMY ) {
469 continue;
470 }
471
472 for ( mx = -searchRangeB; mx < rightMX; mx += stepSize ) {
473 if ( mx < leftMX ) {
474 continue;
475 }
476
477 ComputeBMotionLumBlock(prev, next, by, bx, MOTION_FORWARD,
478 my, mx, 0, 0, forwardBlock);
479
480 newbmy = my; newbmx = mx;
481
482 diff = FindBestMatch(forwardBlock, currentBlock, next, by, bx,
483 &newbmy, &newbmx, bestDiff, searchRangeB);
484
485 if ( diff < bestDiff ) {
486 *fmy = my;
487 *fmx = mx;
488 *bmy = newbmy;
489 *bmx = newbmx;
490 bestDiff = diff;
491 result = MOTION_INTERPOLATE;
492 }
493 }
494 }
495
496 return result;
497 }
498
499
500 /*===========================================================================*
501 *
502 * FindBestMatch
503 *
504 * given a motion-compensated block in one direction, tries to find
505 * the best motion vector in the opposite direction to match it
506 *
507 * RETURNS: the best vector (*motionY, *motionX), and the corresponding
508 * error is returned if it is better than bestSoFar. If not,
509 * then a number greater than bestSoFar is returned and
510 * (*motionY, *motionX) has no meaning.
511 *
512 * SIDE EFFECTS: none
513 *
514 *===========================================================================*/
515 static int32
FindBestMatch(LumBlock block,LumBlock currentBlock,MpegFrame * prev,int by,int bx,int * motionY,int * motionX,int32 bestSoFar,int searchRange)516 FindBestMatch(LumBlock block,
517 LumBlock currentBlock,
518 MpegFrame *prev,
519 int by,
520 int bx,
521 int *motionY,
522 int *motionX,
523 int32 bestSoFar,
524 int searchRange)
525 {
526 int32 result;
527
528 switch(psearchAlg) {
529 case PSEARCH_SUBSAMPLE:
530 result = FindBestMatchSubSample(block, currentBlock, prev, by, bx,
531 motionY, motionX, bestSoFar, searchRange);
532 break;
533 case PSEARCH_EXHAUSTIVE:
534 result = FindBestMatchExhaust(block, currentBlock, prev, by, bx,
535 motionY, motionX, bestSoFar, searchRange);
536 break;
537 case PSEARCH_LOGARITHMIC:
538 result = FindBestMatchLogarithmic(block, currentBlock, prev, by, bx,
539 motionY, motionX, bestSoFar, searchRange);
540 break;
541 case PSEARCH_TWOLEVEL:
542 result = FindBestMatchTwoLevel(block, currentBlock, prev, by, bx,
543 motionY, motionX, bestSoFar, searchRange);
544 break;
545 default:
546 throw "Illegal P-search alg";
547 }
548
549 return result;
550 }
551
552
553 /*===========================================================================*
554 *
555 * FindBestMatchExhaust
556 *
557 * tries to find matching motion vector
558 * see FindBestMatch for generic description
559 *
560 * DESCRIPTION: uses an exhaustive search
561 *
562 *===========================================================================*/
563 static int32
FindBestMatchExhaust(LumBlock block,LumBlock currentBlock,MpegFrame * prev,int by,int bx,int * motionY,int * motionX,int32 bestSoFar,int searchRange)564 FindBestMatchExhaust(LumBlock block,
565 LumBlock currentBlock,
566 MpegFrame *prev,
567 int by,
568 int bx,
569 int *motionY,
570 int *motionX,
571 int32 bestSoFar,
572 int searchRange)
573 {
574 register int mx, my;
575 int32 diff, bestDiff;
576 int stepSize;
577 int leftMY, leftMX;
578 int rightMY, rightMX;
579 int distance;
580 int tempRightMY, tempRightMX;
581 boolean changed = FALSE;
582
583 stepSize = (pixelFullSearch ? 2 : 1);
584
585 COMPUTE_MOTION_BOUNDARY(by,bx,stepSize,leftMY,leftMX,rightMY,rightMX);
586
587 /* try old motion vector first */
588 if ( VALID_MOTION(*motionY, *motionX) ) {
589 bestDiff = LumAddMotionError(currentBlock, block, prev, by, bx,
590 *motionY, *motionX, bestSoFar);
591
592 if ( bestSoFar < bestDiff ) {
593 bestDiff = bestSoFar;
594 }
595 }
596 else
597 {
598 *motionY = 0;
599 *motionX = 0;
600
601 bestDiff = bestSoFar;
602 }
603
604 /* maybe should try spiral pattern centered around prev motion vector? */
605
606
607 /* try a spiral pattern */
608 for ( distance = stepSize; distance <= searchRange; distance += stepSize ) {
609 tempRightMY = rightMY;
610 if ( distance < tempRightMY ) {
611 tempRightMY = distance;
612 }
613 tempRightMX = rightMX;
614 if ( distance < tempRightMX ) {
615 tempRightMX = distance;
616 }
617
618 /* do top, bottom */
619 for ( my = -distance; my < tempRightMY;
620 my += max(tempRightMY+distance-stepSize, stepSize) ) {
621 if ( my < leftMY ) {
622 continue;
623 }
624
625 for ( mx = -distance; mx < tempRightMX; mx += stepSize ) {
626 if ( mx < leftMX ) {
627 continue;
628 }
629
630 diff = LumAddMotionError(currentBlock, block, prev, by, bx,
631 my, mx, bestDiff);
632
633 if ( diff < bestDiff ) {
634 *motionY = my;
635 *motionX = mx;
636 bestDiff = diff;
637 }
638 }
639 }
640
641 /* do left, right */
642 for ( mx = -distance; mx < tempRightMX; mx += max(tempRightMX+distance-stepSize, stepSize) ) {
643 if ( mx < leftMX ) {
644 continue;
645 }
646
647 for ( my = -distance+stepSize; my < tempRightMY-stepSize; my += stepSize ) {
648 if ( my < leftMY ) {
649 continue;
650 }
651
652 diff = LumAddMotionError(currentBlock, block, prev, by, bx,
653 my, mx, bestDiff);
654
655 if ( diff < bestDiff ) {
656 *motionY = my;
657 *motionX = mx;
658 bestDiff = diff;
659 changed = TRUE;
660 }
661 }
662 }
663 }
664
665 if ( ! changed ) {
666 bestDiff++;
667 }
668
669 return bestDiff;
670 }
671
672
673 /*===========================================================================*
674 *
675 * FindBestMatchTwoLevel
676 *
677 * tries to find matching motion vector
678 * see FindBestMatch for generic description
679 *
680 * DESCRIPTION: uses an exhaustive full-pixel search, then looks at
681 * neighboring half-pixels
682 *
683 *===========================================================================*/
684 static int32
FindBestMatchTwoLevel(LumBlock block,LumBlock currentBlock,MpegFrame * prev,int by,int bx,int * motionY,int * motionX,int32 bestSoFar,int searchRange)685 FindBestMatchTwoLevel(LumBlock block,
686 LumBlock currentBlock,
687 MpegFrame *prev,
688 int by,
689 int bx,
690 int *motionY,
691 int *motionX,
692 int32 bestSoFar,
693 int searchRange)
694 {
695 register int mx, my;
696 int32 diff, bestDiff;
697 int leftMY, leftMX;
698 int rightMY, rightMX;
699 int distance;
700 int tempRightMY, tempRightMX;
701 boolean changed = FALSE;
702 int yOffset, xOffset;
703
704 /* exhaustive full-pixel search first */
705
706 COMPUTE_MOTION_BOUNDARY(by,bx,2,leftMY,leftMX,rightMY,rightMX);
707
708 rightMY--;
709 rightMX--;
710
711 /* convert vector into full-pixel vector */
712 if ( *motionY > 0 ) {
713 if ( ((*motionY) % 2) == 1 ) {
714 (*motionY)--;
715 }
716 } else if ( ((-(*motionY)) % 2) == 1 ) {
717 (*motionY)++;
718 }
719
720 if ( *motionX > 0 ) {
721 if ( ((*motionX) % 2) == 1 ) {
722 (*motionX)--;
723 }
724 } else if ( ((-(*motionX)) % 2) == 1 ) {
725 (*motionX)++;
726 }
727
728 /* try old motion vector first */
729 if ( VALID_MOTION(*motionY, *motionX) ) {
730 bestDiff = LumAddMotionError(currentBlock, block, prev, by, bx,
731 *motionY, *motionX, bestSoFar);
732
733 if ( bestSoFar < bestDiff ) {
734 bestDiff = bestSoFar;
735 }
736 }
737 else
738 {
739 *motionY = 0;
740 *motionX = 0;
741
742 bestDiff = bestSoFar;
743 }
744
745 rightMY++;
746 rightMX++;
747
748 /* maybe should try spiral pattern centered around prev motion vector? */
749
750
751 /* try a spiral pattern */
752 for ( distance = 2; distance <= searchRange; distance += 2 ) {
753 tempRightMY = rightMY;
754 if ( distance < tempRightMY ) {
755 tempRightMY = distance;
756 }
757 tempRightMX = rightMX;
758 if ( distance < tempRightMX ) {
759 tempRightMX = distance;
760 }
761
762 /* do top, bottom */
763 for ( my = -distance; my < tempRightMY;
764 my += max(tempRightMY+distance-2, 2) ) {
765 if ( my < leftMY ) {
766 continue;
767 }
768
769 for ( mx = -distance; mx < tempRightMX; mx += 2 ) {
770 if ( mx < leftMX ) {
771 continue;
772 }
773
774 diff = LumAddMotionError(currentBlock, block, prev, by, bx,
775 my, mx, bestDiff);
776
777 if ( diff < bestDiff ) {
778 *motionY = my;
779 *motionX = mx;
780 bestDiff = diff;
781 }
782 }
783 }
784
785 /* do left, right */
786 for ( mx = -distance; mx < tempRightMX; mx += max(tempRightMX+distance-2, 2) ) {
787 if ( mx < leftMX ) {
788 continue;
789 }
790
791 for ( my = -distance+2; my < tempRightMY-2; my += 2 ) {
792 if ( my < leftMY ) {
793 continue;
794 }
795
796 diff = LumAddMotionError(currentBlock, block, prev, by, bx,
797 my, mx, bestDiff);
798
799 if ( diff < bestDiff ) {
800 *motionY = my;
801 *motionX = mx;
802 bestDiff = diff;
803 changed = TRUE;
804 }
805 }
806 }
807 }
808
809 /* now look at neighboring half-pixels */
810 my = *motionY;
811 mx = *motionX;
812
813 rightMY--;
814 rightMX--;
815
816 for ( yOffset = -1; yOffset <= 1; yOffset++ ) {
817 for ( xOffset = -1; xOffset <= 1; xOffset++ ) {
818 if ( (yOffset == 0) && (xOffset == 0) )
819 continue;
820
821 if ( VALID_MOTION(my+yOffset, mx+xOffset) &&
822 ((diff = LumAddMotionError(currentBlock, block, prev, by, bx,
823 my+yOffset, mx+xOffset, bestDiff)) < bestDiff) ) {
824 *motionY = my+yOffset;
825 *motionX = mx+xOffset;
826 bestDiff = diff;
827 changed = TRUE;
828 }
829 }
830 }
831
832 if ( ! changed ) {
833 bestDiff++;
834 }
835
836 return bestDiff;
837 }
838
839
840 /*===========================================================================*
841 *
842 * FindBestMatchLogarithmic
843 *
844 * tries to find matching motion vector
845 * see FindBestMatch for generic description
846 *
847 * DESCRIPTION: uses a logarithmic search
848 *
849 *===========================================================================*/
850 static int32
FindBestMatchLogarithmic(LumBlock block,LumBlock currentBlock,MpegFrame * prev,int by,int bx,int * motionY,int * motionX,int32 bestSoFar,int searchRange)851 FindBestMatchLogarithmic(LumBlock block,
852 LumBlock currentBlock,
853 MpegFrame *prev,
854 int by,
855 int bx,
856 int *motionY,
857 int *motionX,
858 int32 bestSoFar,
859 int searchRange)
860 {
861 register int mx, my;
862 int32 diff, bestDiff;
863 int stepSize;
864 int leftMY, leftMX;
865 int rightMY, rightMX;
866 int tempRightMY, tempRightMX;
867 int spacing;
868 int centerX, centerY;
869 int newCenterX, newCenterY;
870
871 stepSize = (pixelFullSearch ? 2 : 1);
872
873 COMPUTE_MOTION_BOUNDARY(by,bx,stepSize,leftMY,leftMX,rightMY,rightMX);
874
875 bestDiff = 0x7fffffff;
876
877 /* grid spacing */
878 if ( stepSize == 2 ) { /* make sure spacing is even */
879 spacing = (searchRange+1)/2;
880 if ( (spacing % 2) != 0 ) {
881 spacing++;
882 }
883 }
884 else
885 spacing = (searchRange+1)/2;
886 centerX = 0;
887 centerY = 0;
888
889 while ( spacing >= stepSize ) {
890 newCenterY = centerY;
891 newCenterX = centerX;
892
893 tempRightMY = rightMY;
894 if ( centerY+spacing+1 < tempRightMY ) {
895 tempRightMY = centerY+spacing+1;
896 }
897 tempRightMX = rightMX;
898 if ( centerX+spacing+1 < tempRightMX ) {
899 tempRightMX = centerX+spacing+1;
900 }
901
902 for ( my = centerY-spacing; my < tempRightMY; my += spacing ) {
903 if ( my < leftMY ) {
904 continue;
905 }
906
907 for ( mx = centerX-spacing; mx < tempRightMX; mx += spacing ) {
908 if ( mx < leftMX ) {
909 continue;
910 }
911
912 diff = LumAddMotionError(currentBlock, block, prev, by, bx,
913 my, mx, bestDiff);
914
915 if ( diff < bestDiff ) {
916 newCenterY = my;
917 newCenterX = mx;
918
919 bestDiff = diff;
920 }
921 }
922 }
923
924 centerY = newCenterY;
925 centerX = newCenterX;
926
927 if ( stepSize == 2 ) { /* make sure spacing is even */
928 if ( spacing == 2 ) {
929 spacing = 0;
930 }
931 else
932 {
933 spacing = (spacing+1)/2;
934 if ( (spacing % 2) != 0 ) {
935 spacing++;
936 }
937 }
938 }
939 else
940 {
941 if ( spacing == 1 ) {
942 spacing = 0;
943 }
944 else
945 spacing = (spacing+1)/2;
946 }
947 }
948
949 /* check old motion -- see if it's better */
950 if ( (*motionY >= leftMY) && (*motionY < rightMY) &&
951 (*motionX >= leftMX) && (*motionX < rightMX) ) {
952 diff = LumAddMotionError(currentBlock, block, prev, by, bx, *motionY, *motionX, bestDiff);
953 } else {
954 diff = 0x7fffffff;
955 }
956
957 if ( bestDiff < diff ) {
958 *motionY = centerY;
959 *motionX = centerX;
960 }
961 else
962 bestDiff = diff;
963
964 return bestDiff;
965 }
966
967
968 /*===========================================================================*
969 *
970 * FindBestMatchSubSample
971 *
972 * tries to find matching motion vector
973 * see FindBestMatch for generic description
974 *
975 * DESCRIPTION: should use subsampling method, but too lazy to write all
976 * the code for it (so instead just calls FindBestMatchExhaust)
977 *
978 *===========================================================================*/
979 static int32
FindBestMatchSubSample(LumBlock block,LumBlock currentBlock,MpegFrame * prev,int by,int bx,int * motionY,int * motionX,int32 bestSoFar,int searchRange)980 FindBestMatchSubSample(LumBlock block,
981 LumBlock currentBlock,
982 MpegFrame *prev,
983 int by,
984 int bx,
985 int *motionY,
986 int *motionX,
987 int32 bestSoFar,
988 int searchRange)
989 {
990 /* too lazy to write the code for this... */
991
992 return FindBestMatchExhaust(block, currentBlock, prev,
993 by, bx, motionY, motionX, bestSoFar, searchRange);
994 }
995
996
997 /*===========================================================================*
998 *
999 * BMotionSearchNoInterp
1000 *
1001 * finds the best backward and forward motion vectors
1002 * if backNeeded == FALSE, then won't find best backward vector if it
1003 * is worse than the best forward vector
1004 *
1005 * RETURNS: (*fmy,*fmx) and associated error *forwardErr
1006 * (*bmy,*bmx) and associated error *backErr
1007 *
1008 * SIDE EFFECTS: none
1009 *
1010 *===========================================================================*/
1011 static void
BMotionSearchNoInterp(LumBlock currentBlock,MpegFrame * prev,MpegFrame * next,int by,int bx,int * fmy,int * fmx,int32 * forwardErr,int * bmy,int * bmx,int32 * backErr,boolean backNeeded)1012 BMotionSearchNoInterp(LumBlock currentBlock,
1013 MpegFrame *prev,
1014 MpegFrame *next,
1015 int by,
1016 int bx,
1017 int *fmy,
1018 int *fmx,
1019 int32 *forwardErr,
1020 int *bmy,
1021 int *bmx,
1022 int32 *backErr,
1023 boolean backNeeded)
1024 {
1025 /* CALL SEARCH PROCEDURE */
1026 switch(psearchAlg) {
1027 case PSEARCH_SUBSAMPLE:
1028 *forwardErr = PSubSampleSearch(currentBlock, prev, by, bx,
1029 fmy, fmx, searchRangeB);
1030 *backErr = PSubSampleSearch(currentBlock, next, by, bx,
1031 bmy, bmx, searchRangeB);
1032 break;
1033 case PSEARCH_EXHAUSTIVE:
1034 *forwardErr = PLocalSearch(currentBlock, prev, by, bx, fmy, fmx,
1035 0x7fffffff, searchRangeB);
1036 if ( backNeeded ) {
1037 *backErr = PLocalSearch(currentBlock, next, by, bx, bmy, bmx,
1038 0x7fffffff, searchRangeB);
1039 } else {
1040 *backErr = PLocalSearch(currentBlock, next, by, bx, bmy, bmx,
1041 *forwardErr, searchRangeB);
1042 }
1043 break;
1044 case PSEARCH_LOGARITHMIC:
1045 *forwardErr = PLogarithmicSearch(currentBlock, prev, by, bx,
1046 fmy, fmx, searchRangeB);
1047 *backErr = PLogarithmicSearch(currentBlock, next, by, bx,
1048 bmy, bmx, searchRangeB);
1049 break;
1050 case PSEARCH_TWOLEVEL:
1051 *forwardErr = PTwoLevelSearch(currentBlock, prev, by, bx, fmy, fmx,
1052 0x7fffffff, searchRangeB);
1053 if ( backNeeded ) {
1054 *backErr = PTwoLevelSearch(currentBlock, next, by, bx, bmy, bmx,
1055 0x7fffffff, searchRangeB);
1056 } else {
1057 *backErr = PTwoLevelSearch(currentBlock, next, by, bx, bmy, bmx,
1058 *forwardErr, searchRangeB);
1059 }
1060 break;
1061 default:
1062 throw "Illegal PSEARCH ALG";
1063 break;
1064 }
1065 }
1066
1067
1068
1069 /*===========================================================================*
1070 * *
1071 * UNUSED PROCEDURES *
1072 * *
1073 * The following procedures are all unused by the encoder *
1074 * *
1075 * They are listed here for your convenience. You might want to use *
1076 * them if you experiment with different search techniques *
1077 * *
1078 *===========================================================================*/
1079
1080 #ifdef UNUSED_PROCEDURES
1081
1082 /*===========================================================================*
1083 *
1084 * ValidBMotion
1085 *
1086 * decides if the given B-frame motion is valid
1087 *
1088 * RETURNS: TRUE if the motion is valid, FALSE otherwise
1089 *
1090 * SIDE EFFECTS: none
1091 *
1092 *===========================================================================*/
1093 boolean
ValidBMotion(int by,int bx,int mode,int fmy,int fmx,int bmy,int bmx)1094 ValidBMotion(int by,
1095 int bx,
1096 int mode,
1097 int fmy,
1098 int fmx,
1099 int bmy,
1100 int bmx)
1101 {
1102 if ( mode != MOTION_BACKWARD ) {
1103 /* check forward motion for bounds */
1104 if ( (by*DCTSIZE+(fmy-1)/2 < 0) || ((by+2)*DCTSIZE+(fmy+1)/2-1 >= Fsize_y) ) {
1105 return FALSE;
1106 }
1107 if ( (bx*DCTSIZE+(fmx-1)/2 < 0) || ((bx+2)*DCTSIZE+(fmx+1)/2-1 >= Fsize_x) ) {
1108 return FALSE;
1109 }
1110 }
1111
1112 if ( mode != MOTION_FORWARD ) {
1113 /* check backward motion for bounds */
1114 if ( (by*DCTSIZE+(bmy-1)/2 < 0) || ((by+2)*DCTSIZE+(bmy+1)/2-1 >= Fsize_y) ) {
1115 return FALSE;
1116 }
1117 if ( (bx*DCTSIZE+(bmx-1)/2 < 0) || ((bx+2)*DCTSIZE+(bmx+1)/2-1 >= Fsize_x) ) {
1118 return FALSE;
1119 }
1120 }
1121
1122 return TRUE;
1123 }
1124
1125
1126 #endif /* UNUSED_PROCEDURES */
1127