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