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