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