ViewVC Help
View File | Revision Log | Show Annotations | View Changeset | Root Listing
root/freemol/trunk/src/mpeg_encode/src/psearch.c
Revision: 22
Committed: Mon Jul 7 22:16:37 2008 UTC (11 years ago) by wdelano
File size: 24455 byte(s)
Log Message:
initial checkin of mpeg_encode source
Line File contents
1 /*===========================================================================*
2 * psearch.c *
3 * *
4 * Procedures concerned with the P-frame motion search *
5 * *
6 * EXPORTED PROCEDURES: *
7 * SetPixelSearch *
8 * SetPSearchAlg *
9 * SetSearchRange *
10 * MotionSearchPreComputation *
11 * PMotionSearch *
12 * PSearchName *
13 * PSubSampleSearch *
14 * PLogarithmicSearch *
15 * *
16 *===========================================================================*/
17
18 /*
19 * Copyright (c) 1995 The Regents of the University of California.
20 * All rights reserved.
21 *
22 * Permission to use, copy, modify, and distribute this software and its
23 * documentation for any purpose, without fee, and without written agreement is
24 * hereby granted, provided that the above copyright notice and the following
25 * two paragraphs appear in all copies of this software.
26 *
27 * IN NO EVENT SHALL THE UNIVERSITY OF CALIFORNIA BE LIABLE TO ANY PARTY FOR
28 * DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES ARISING OUT
29 * OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN IF THE UNIVERSITY OF
30 * CALIFORNIA HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
31 *
32 * THE UNIVERSITY OF CALIFORNIA SPECIFICALLY DISCLAIMS ANY WARRANTIES,
33 * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY
34 * AND FITNESS FOR A PARTICULAR PURPOSE. THE SOFTWARE PROVIDED HEREUNDER IS
35 * ON AN "AS IS" BASIS, AND THE UNIVERSITY OF CALIFORNIA HAS NO OBLIGATION TO
36 * PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS.
37 */
38
39 /*
40 * $Header: /u/smoot/md/mpeg_encode/RCS/psearch.c,v 1.9 1995/01/19 23:09:12 eyhung Exp $
41 * $Log: psearch.c,v $
42 * Revision 1.9 1995/01/19 23:09:12 eyhung
43 * Changed copyrights
44 *
45 * Revision 1.9 1995/01/19 23:09:12 eyhung
46 * Changed copyrights
47 *
48 * Revision 1.8 1994/12/07 00:40:36 smoot
49 * Added seperate P and B search ranges
50 *
51 * Revision 1.7 1994/11/12 02:09:45 eyhung
52 * full pixel bug
53 * fixed on lines 512 and 563
54 *
55 * Revision 1.6 1994/03/15 00:27:11 keving
56 * nothing
57 *
58 * Revision 1.5 1993/12/22 19:19:01 keving
59 * nothing
60 *
61 * Revision 1.4 1993/07/22 22:23:43 keving
62 * nothing
63 *
64 * Revision 1.3 1993/06/30 20:06:09 keving
65 * nothing
66 *
67 * Revision 1.2 1993/06/03 21:08:08 keving
68 * nothing
69 *
70 * Revision 1.1 1993/03/02 18:27:05 keving
71 * nothing
72 *
73 */
74
75
76 /*==============*
77 * HEADER FILES *
78 *==============*/
79
80 #include "all.h"
81 #include "mtypes.h"
82 #include "frames.h"
83 #include "search.h"
84 #include "prototypes.h"
85 #include "fsize.h"
86 #include "param.h"
87
88
89 /*==================*
90 * STATIC VARIABLES *
91 *==================*/
92
93 /* none */
94
95
96 /*==================*
97 * GLOBAL VARIABLES *
98 *==================*/
99
100 int **pmvHistogram = NULL; /* histogram of P-frame motion vectors */
101 int **bbmvHistogram = NULL; /* histogram of B-frame motion vectors */
102 int **bfmvHistogram = NULL; /* histogram of B-frame motion vectors */
103 int pixelFullSearch;
104 int searchRangeP,searchRangeB;
105 int psearchAlg;
106
107
108 /*===============================*
109 * INTERNAL PROCEDURE prototypes *
110 *===============================*/
111
112
113 /*=====================*
114 * EXPORTED PROCEDURES *
115 *=====================*/
116
117 /*===========================================================================*
118 *
119 * PMotionSearch
120 *
121 * compute the best P-frame motion vector we can
122 *
123 *
124 * RETURNS: TRUE = motion vector valid
125 * FALSE = motion vector invalid; should code I-block
126 *
127 * PRECONDITIONS: The relevant block in 'current' is valid (it has not
128 * been dct'd). Thus, the data in 'current' can be
129 * accesed through y_blocks, cr_blocks, and cb_blocks.
130 * This is not the case for the blocks in 'prev.'
131 * Therefore, references into 'prev' should be done
132 * through the struct items ref_y, ref_cr, ref_cb
133 *
134 * POSTCONDITIONS: current, prev should be unchanged.
135 * Some computation could be saved by requiring
136 * the dct'd difference to be put into current's block
137 * elements here, depending on the search technique.
138 * However, it was decided that it mucks up the code
139 * organization a little, and the saving in computation
140 * would be relatively little (if any).
141 *
142 * NOTES: the search procedure need not check the (0,0) motion vector
143 * the calling procedure has a preference toward (0,0) and it
144 * will check it itself
145 *
146 * SIDE EFFECTS: none
147 *
148 *===========================================================================*/
149 boolean
150 PMotionSearch(currentBlock, prev, by, bx, motionY, motionX)
151 LumBlock currentBlock;
152 MpegFrame *prev;
153 int by;
154 int bx;
155 int *motionY;
156 int *motionX;
157 {
158 /* CALL SEARCH PROCEDURE */
159
160 switch(psearchAlg) {
161 case PSEARCH_SUBSAMPLE:
162 PSubSampleSearch(currentBlock, prev, by, bx, motionY, motionX, searchRangeP);
163 break;
164 case PSEARCH_EXHAUSTIVE:
165 PLocalSearch(currentBlock, prev, by, bx, motionY, motionX,
166 0x7fffffff, searchRangeP);
167 break;
168 case PSEARCH_LOGARITHMIC:
169 PLogarithmicSearch(currentBlock, prev, by, bx, motionY, motionX, searchRangeP);
170 break;
171 case PSEARCH_TWOLEVEL:
172 PTwoLevelSearch(currentBlock, prev, by, bx, motionY, motionX,
173 0x7fffffff, searchRangeP);
174 break;
175 default:
176 fprintf(stderr, "ILLEGAL PSEARCH ALG: %d\n", psearchAlg);
177 exit(1);
178 }
179
180 return TRUE;
181 }
182
183
184 /*===========================================================================*
185 *
186 * SetPixelSearch
187 *
188 * set the pixel search type (half or full)
189 *
190 * RETURNS: nothing
191 *
192 * SIDE EFFECTS: pixelFullSearch
193 *
194 *===========================================================================*/
195 void
196 SetPixelSearch(searchType)
197 char *searchType;
198 {
199 if ( (strcmp(searchType, "FULL") == 0 ) || ( strcmp(searchType, "WHOLE") == 0 )) {
200 pixelFullSearch = TRUE;
201 } else if ( strcmp(searchType, "HALF") == 0 ) {
202 pixelFullSearch = FALSE;
203 } else {
204 fprintf(stderr, "ERROR: Invalid pixel search type: %s\n",
205 searchType);
206 exit(1);
207 }
208 }
209
210
211 /*===========================================================================*
212 *
213 * SetPSearchAlg
214 *
215 * set the P-search algorithm
216 *
217 * RETURNS: nothing
218 *
219 * SIDE EFFECTS: psearchAlg
220 *
221 *===========================================================================*/
222 void
223 SetPSearchAlg(alg)
224 char *alg;
225 {
226 if ( strcmp(alg, "EXHAUSTIVE") == 0 ) {
227 psearchAlg = PSEARCH_EXHAUSTIVE;
228 } else if (strcmp(alg, "SUBSAMPLE") == 0 ) {
229 psearchAlg = PSEARCH_SUBSAMPLE;
230 } else if ( strcmp(alg, "LOGARITHMIC") == 0 ) {
231 psearchAlg = PSEARCH_LOGARITHMIC;
232 } else if ( strcmp(alg, "TWOLEVEL") == 0 ) {
233 psearchAlg = PSEARCH_TWOLEVEL;
234 } else {
235 fprintf(stderr, "ERROR: Invalid psearch algorithm: %s\n", alg);
236 exit(1);
237 }
238 }
239
240
241 /*===========================================================================*
242 *
243 * PSearchName
244 *
245 * returns a string containing the name of the search algorithm
246 *
247 * RETURNS: pointer to the string
248 *
249 * SIDE EFFECTS: none
250 *
251 *===========================================================================*/
252 char *
253 PSearchName()
254 {
255 switch(psearchAlg) {
256 case PSEARCH_EXHAUSTIVE:
257 return "EXHAUSTIVE";
258 case PSEARCH_SUBSAMPLE:
259 return "SUBSAMPLE";
260 case PSEARCH_LOGARITHMIC:
261 return "LOGARITHMIC";
262 case PSEARCH_TWOLEVEL:
263 return "TWOLEVEL";
264 default:
265 exit(1);
266 break;
267 }
268 }
269
270
271 /*===========================================================================*
272 *
273 * SetSearchRange
274 *
275 * sets the range of the search to the given number of pixels
276 *
277 * RETURNS: nothing
278 *
279 * SIDE EFFECTS: searchRange*, fCode
280 *
281 *===========================================================================*/
282 void
283 SetSearchRange(pixelsP,pixelsB)
284 int pixelsP,pixelsB;
285 {
286 register int index;
287
288 searchRangeP = 2*pixelsP; /* +/- 'pixels' pixels */
289 searchRangeB = 2*pixelsB;
290 searchRangeB = 2*pixelsB;
291
292 if ( computeMVHist ) {
293 int max_search;
294 max_search=(searchRangeP>searchRangeB) ?
295 ((searchRangeP>searchRangeB)?searchRangeP:searchRangeB)
296 : ((searchRangeB>searchRangeB)?searchRangeB:searchRangeB);
297
298 pmvHistogram = (int **) malloc((2*searchRangeP+3)*sizeof(int *));
299 bbmvHistogram = (int **) malloc((2*searchRangeB+3)*sizeof(int *));
300 bfmvHistogram = (int **) malloc((2*searchRangeB+3)*sizeof(int *));
301 for ( index = 0; index < 2*max_search+3; index++ ) {
302 pmvHistogram[index] = (int *) calloc(2*searchRangeP+3, sizeof(int));
303 bbmvHistogram[index] = (int *) calloc(2*searchRangeB+3, sizeof(int));
304 bfmvHistogram[index] = (int *) calloc(2*searchRangeB+3, sizeof(int));
305 }
306 }
307 }
308
309
310 /*===========================================================================*
311 *
312 * USER-MODIFIABLE
313 *
314 * MotionSearchPreComputation
315 *
316 * do whatever you want here; this is called once per frame, directly
317 * after reading
318 *
319 * RETURNS: whatever
320 *
321 * SIDE EFFECTS: whatever
322 *
323 *===========================================================================*/
324 void
325 MotionSearchPreComputation(frame)
326 MpegFrame *frame;
327 {
328 /* do nothing */
329 }
330
331
332 /*===========================================================================*
333 *
334 * PSubSampleSearch
335 *
336 * uses the subsampling algorithm to compute the P-frame vector
337 *
338 * RETURNS: motion vector
339 *
340 * SIDE EFFECTS: none
341 *
342 * REFERENCE: Liu and Zaccarin: New Fast Algorithms for the Estimation
343 * of Block Motion Vectors, IEEE Transactions on Circuits
344 * and Systems for Video Technology, Vol. 3, No. 2, 1993.
345 *
346 *===========================================================================*/
347 int32
348 PSubSampleSearch(currentBlock, prev, by, bx, motionY, motionX, searchRange)
349 LumBlock currentBlock;
350 MpegFrame *prev;
351 int by;
352 int bx;
353 int *motionY;
354 int *motionX;
355 int searchRange;
356 {
357 register int mx, my;
358 int32 diff, bestBestDiff;
359 int stepSize;
360 register int x;
361 int bestMY[4], bestMX[4], bestDiff[4];
362 int leftMY, leftMX;
363 int rightMY, rightMX;
364
365 stepSize = (pixelFullSearch ? 2 : 1);
366
367 COMPUTE_MOTION_BOUNDARY(by,bx,stepSize,leftMY,leftMX,rightMY,rightMX);
368
369 if ( searchRange < rightMY ) {
370 rightMY = searchRange;
371 }
372
373 if ( searchRange < rightMX ) {
374 rightMX = searchRange;
375 }
376
377 for ( x = 0; x < 4; x++ ) {
378 bestMY[x] = 0;
379 bestMX[x] = 0;
380 bestDiff[x] = 0x7fffffff;
381 }
382
383 /* do A pattern */
384 for ( my = -searchRange; my < rightMY; my += 2*stepSize ) {
385 if ( my < leftMY ) {
386 continue;
387 }
388
389 for ( mx = -searchRange; mx < rightMX; mx += 2*stepSize ) {
390 if ( mx < leftMX ) {
391 continue;
392 }
393
394 diff = LumMotionErrorA(currentBlock, prev, by, bx, my, mx, bestDiff[0]);
395
396 if ( diff < bestDiff[0] ) {
397 bestMY[0] = my;
398 bestMX[0] = mx;
399 bestDiff[0] = diff;
400 }
401 }
402 }
403
404 /* do B pattern */
405 for ( my = stepSize-searchRange; my < rightMY; my += 2*stepSize ) {
406 if ( my < leftMY ) {
407 continue;
408 }
409
410 for ( mx = -searchRange; mx < rightMX; mx += 2*stepSize ) {
411 if ( mx < leftMX ) {
412 continue;
413 }
414
415 diff = LumMotionErrorB(currentBlock, prev, by, bx, my, mx, bestDiff[1]);
416
417 if ( diff < bestDiff[1] ) {
418 bestMY[1] = my;
419 bestMX[1] = mx;
420 bestDiff[1] = diff;
421 }
422 }
423 }
424
425 /* do C pattern */
426 for ( my = stepSize-searchRange; my < rightMY; my += 2*stepSize ) {
427 if ( my < leftMY ) {
428 continue;
429 }
430
431 for ( mx = stepSize-searchRange; mx < rightMX; mx += 2*stepSize ) {
432 if ( mx < leftMX ) {
433 continue;
434 }
435
436 diff = LumMotionErrorC(currentBlock, prev, by, bx, my, mx, bestDiff[2]);
437
438 if ( diff < bestDiff[2] ) {
439 bestMY[2] = my;
440 bestMX[2] = mx;
441 bestDiff[2] = diff;
442 }
443 }
444 }
445
446 /* do D pattern */
447 for ( my = -searchRange; my < rightMY; my += 2*stepSize ) {
448 if ( my < leftMY ) {
449 continue;
450 }
451
452 for ( mx = stepSize-searchRange; mx < rightMX; mx += 2*stepSize ) {
453 if ( mx < leftMX ) {
454 continue;
455 }
456
457 diff = LumMotionErrorD(currentBlock, prev, by, bx, my, mx, bestDiff[3]);
458
459 if ( diff < bestDiff[3] ) {
460 bestMY[3] = my;
461 bestMX[3] = mx;
462 bestDiff[3] = diff;
463 }
464 }
465 }
466
467 /* first check old motion */
468 if ( (*motionY >= leftMY) && (*motionY < rightMY) &&
469 (*motionX >= leftMX) && (*motionX < rightMX) ) {
470 bestBestDiff = LumMotionError(currentBlock, prev, by, bx, *motionY, *motionX, 0x7fffffff);
471 } else {
472 bestBestDiff = 0x7fffffff;
473 }
474
475 /* look at Error of 4 different motion vectors */
476 for ( x = 0; x < 4; x++ ) {
477 bestDiff[x] = LumMotionError(currentBlock, prev, by, bx,
478 bestMY[x], bestMX[x], bestBestDiff);
479
480 if ( bestDiff[x] < bestBestDiff ) {
481 bestBestDiff = bestDiff[x];
482 *motionY = bestMY[x];
483 *motionX = bestMX[x];
484 }
485 }
486
487 return bestBestDiff;
488 }
489
490
491 /*===========================================================================*
492 *
493 * PLogarithmicSearch
494 *
495 * uses logarithmic search to compute the P-frame vector
496 *
497 * RETURNS: motion vector
498 *
499 * SIDE EFFECTS: none
500 *
501 * REFERENCE: MPEG-I specification, pages 32-33
502 *
503 *===========================================================================*/
504 int32
505 PLogarithmicSearch(currentBlock, prev, by, bx, motionY, motionX, searchRange)
506 LumBlock currentBlock;
507 MpegFrame *prev;
508 int by;
509 int bx;
510 int *motionY;
511 int *motionX;
512 int searchRange;
513 {
514 register int mx, my;
515 int32 diff, bestDiff;
516 int stepSize;
517 int leftMY, leftMX;
518 int rightMY, rightMX;
519 int tempRightMY, tempRightMX;
520 int spacing;
521 int centerX, centerY;
522 int newCenterX, newCenterY;
523
524 stepSize = (pixelFullSearch ? 2 : 1);
525
526 COMPUTE_MOTION_BOUNDARY(by,bx,stepSize,leftMY,leftMX,rightMY,rightMX);
527
528 bestDiff = 0x7fffffff;
529
530 /* grid spacing */
531 if ( stepSize == 2 ) { /* make sure spacing is even */
532 spacing = (searchRange+1)/2;
533 if ( (spacing % 2) != 0 ) {
534 spacing--;
535 }
536 } else {
537 spacing = (searchRange+1)/2;
538 }
539 centerX = 0;
540 centerY = 0;
541
542 while ( spacing >= stepSize ) {
543 newCenterY = centerY;
544 newCenterX = centerX;
545
546 tempRightMY = rightMY;
547 if ( centerY+spacing+1 < tempRightMY ) {
548 tempRightMY = centerY+spacing+1;
549 }
550 tempRightMX = rightMX;
551 if ( centerX+spacing+1 < tempRightMX ) {
552 tempRightMX = centerX+spacing+1;
553 }
554
555 for ( my = centerY-spacing; my < tempRightMY; my += spacing ) {
556 if ( my < leftMY ) {
557 continue;
558 }
559
560 for ( mx = centerX-spacing; mx < tempRightMX; mx += spacing ) {
561 if ( mx < leftMX ) {
562 continue;
563 }
564
565 diff = LumMotionError(currentBlock, prev, by, bx, my, mx, bestDiff);
566
567 if ( diff < bestDiff ) {
568 newCenterY = my;
569 newCenterX = mx;
570
571 bestDiff = diff;
572 }
573 }
574 }
575
576 centerY = newCenterY;
577 centerX = newCenterX;
578
579 if ( stepSize == 2 ) { /* make sure spacing is even */
580 if ( spacing == 2 ) {
581 spacing = 0;
582 } else {
583 spacing = (spacing+1)/2;
584 if ( (spacing % 2) != 0 ) {
585 spacing--;
586 }
587 }
588 } else {
589 if ( spacing == 1 ) {
590 spacing = 0;
591 } else {
592 spacing = (spacing+1)/2;
593 }
594 }
595 }
596
597 /* check old motion -- see if it's better */
598 if ( (*motionY >= leftMY) && (*motionY < rightMY) &&
599 (*motionX >= leftMX) && (*motionX < rightMX) ) {
600 diff = LumMotionError(currentBlock, prev, by, bx, *motionY, *motionX, bestDiff);
601 } else {
602 diff = 0x7fffffff;
603 }
604
605 if ( bestDiff < diff ) {
606 *motionY = centerY;
607 *motionX = centerX;
608 } else {
609 bestDiff = diff;
610 }
611
612 return bestDiff;
613 }
614
615
616 /*===========================================================================*
617 *
618 * PLocalSearch
619 *
620 * uses local exhaustive search to compute the P-frame vector
621 *
622 * RETURNS: motion vector
623 *
624 * SIDE EFFECTS: none
625 *
626 *===========================================================================*/
627 int32
628 PLocalSearch(currentBlock, prev, by, bx, motionY, motionX, bestSoFar, searchRange)
629 LumBlock currentBlock;
630 MpegFrame *prev;
631 int by;
632 int bx;
633 int *motionY;
634 int *motionX;
635 int32 bestSoFar;
636 int searchRange;
637 {
638 register int mx, my;
639 int32 diff, bestDiff;
640 int stepSize;
641 int leftMY, leftMX;
642 int rightMY, rightMX;
643 int distance;
644 int tempRightMY, tempRightMX;
645
646 stepSize = (pixelFullSearch ? 2 : 1);
647
648 COMPUTE_MOTION_BOUNDARY(by,bx,stepSize,leftMY,leftMX,rightMY,rightMX);
649
650 /* try old motion vector first */
651 if ( VALID_MOTION(*motionY, *motionX) ) {
652 bestDiff = LumMotionError(currentBlock, prev, by, bx, *motionY, *motionX, bestSoFar);
653
654 if ( bestSoFar < bestDiff ) {
655 bestDiff = bestSoFar;
656 }
657 } else {
658 *motionY = 0;
659 *motionX = 0;
660
661 bestDiff = bestSoFar;
662 }
663
664 /* try a spiral pattern */
665 for ( distance = stepSize; distance <= searchRange;
666 distance += stepSize ) {
667 tempRightMY = rightMY;
668 if ( distance < tempRightMY ) {
669 tempRightMY = distance;
670 }
671 tempRightMX = rightMX;
672 if ( distance < tempRightMX ) {
673 tempRightMX = distance;
674 }
675
676 /* do top, bottom */
677 for ( my = -distance; my < tempRightMY;
678 my += max(tempRightMY+distance-stepSize, stepSize) ) {
679 if ( my < leftMY ) {
680 continue;
681 }
682
683 for ( mx = -distance; mx < tempRightMX; mx += stepSize ) {
684 if ( mx < leftMX ) {
685 continue;
686 }
687
688 diff = LumMotionError(currentBlock, prev, by, bx, my, mx, bestDiff);
689
690 if ( diff < bestDiff ) {
691 *motionY = my;
692 *motionX = mx;
693 bestDiff = diff;
694 }
695 }
696 }
697
698 /* do left, right */
699 for ( mx = -distance; mx < tempRightMX;
700 mx += max(tempRightMX+distance-stepSize, stepSize) ) {
701 if ( mx < leftMX ) {
702 continue;
703 }
704
705 for ( my = -distance+stepSize; my < tempRightMY-stepSize;
706 my += stepSize ) {
707 if ( my < leftMY ) {
708 continue;
709 }
710
711 diff = LumMotionError(currentBlock, prev, by, bx, my, mx, bestDiff);
712
713 if ( diff < bestDiff ) {
714 *motionY = my;
715 *motionX = mx;
716 bestDiff = diff;
717 }
718 }
719 }
720 }
721
722 return bestDiff;
723 }
724
725
726 /*===========================================================================*
727 *
728 * PTwoLevelSearch
729 *
730 * uses two-level search to compute the P-frame vector
731 * first does exhaustive full-pixel search, then looks at neighboring
732 * half-pixel motion vectors
733 *
734 * RETURNS: motion vector
735 *
736 * SIDE EFFECTS: none
737 *
738 *===========================================================================*/
739 int32
740 PTwoLevelSearch(currentBlock, prev, by, bx, motionY, motionX, bestSoFar, searchRange)
741 LumBlock currentBlock;
742 MpegFrame *prev;
743 int by;
744 int bx;
745 int *motionY;
746 int *motionX;
747 int32 bestSoFar;
748 int searchRange;
749 {
750 register int mx, my;
751 register int loopInc;
752 int32 diff, bestDiff;
753 int leftMY, leftMX;
754 int rightMY, rightMX;
755 int distance;
756 int tempRightMY, tempRightMX;
757 int xOffset, yOffset;
758
759 /* exhaustive full-pixel search first */
760
761 COMPUTE_MOTION_BOUNDARY(by,bx,2,leftMY,leftMX,rightMY,rightMX);
762
763 rightMY--;
764 rightMX--;
765
766 /* convert vector into full-pixel vector */
767 if ( *motionY > 0 ) {
768 if ( ((*motionY) % 2) == 1 ) {
769 (*motionY)--;
770 }
771 } else if ( ((-(*motionY)) % 2) == 1 ) {
772 (*motionY)++;
773 }
774
775 if ( *motionX > 0 ) {
776 if ( ((*motionX) % 2) == 1 ) {
777 (*motionX)--;
778 }
779 } else if ( ((-(*motionX)) % 2) == 1 ) {
780 (*motionX)++;
781 }
782
783 /* try old motion vector first */
784 if ( VALID_MOTION(*motionY, *motionX) ) {
785 bestDiff = LumMotionError(currentBlock, prev, by, bx, *motionY, *motionX, bestSoFar);
786
787 if ( bestSoFar < bestDiff ) {
788 bestDiff = bestSoFar;
789 }
790 } else {
791 *motionY = 0;
792 *motionX = 0;
793
794 bestDiff = bestSoFar;
795 }
796
797 rightMY++;
798 rightMX++;
799
800 /* try a spiral pattern */
801 for ( distance = 2; distance <= searchRange; distance += 2 ) {
802 tempRightMY = rightMY;
803 if ( distance < tempRightMY ) {
804 tempRightMY = distance;
805 }
806 tempRightMX = rightMX;
807 if ( distance < tempRightMX ) {
808 tempRightMX = distance;
809 }
810
811 /* do top, bottom */
812 loopInc = max(tempRightMY+distance-2, 2);
813 for ( my = -distance; my < tempRightMY; my += loopInc ) {
814 if ( my < leftMY ) {
815 continue;
816 }
817
818 for ( mx = -distance; mx < tempRightMX; mx += 2 ) {
819 if ( mx < leftMX ) {
820 continue;
821 }
822
823 diff = LumMotionError(currentBlock, prev, by, bx, my, mx, bestDiff);
824
825 if ( diff < bestDiff ) {
826 *motionY = my;
827 *motionX = mx;
828 bestDiff = diff;
829 }
830 }
831 }
832
833 /* do left, right */
834 loopInc = max(tempRightMX+distance-2, 2);
835 for ( mx = -distance; mx < tempRightMX; mx += loopInc ) {
836 if ( mx < leftMX ) {
837 continue;
838 }
839
840 for ( my = -distance+2; my < tempRightMY-2; my += 2 ) {
841 if ( my < leftMY ) {
842 continue;
843 }
844
845 diff = LumMotionError(currentBlock, prev, by, bx, my, mx, bestDiff);
846
847 if ( diff < bestDiff ) {
848 *motionY = my;
849 *motionX = mx;
850 bestDiff = diff;
851 }
852 }
853 }
854 }
855
856 /* now look at neighboring half-pixels */
857 my = *motionY;
858 mx = *motionX;
859
860 rightMY--;
861 rightMX--;
862
863 for ( yOffset = -1; yOffset <= 1; yOffset++ ) {
864 for ( xOffset = -1; xOffset <= 1; xOffset++ ) {
865 if ( (yOffset == 0) && (xOffset == 0) )
866 continue;
867
868 if ( VALID_MOTION(my+yOffset, mx+xOffset) &&
869 ((diff = LumMotionError(currentBlock, prev, by, bx,
870 my+yOffset, mx+xOffset, bestDiff)) < bestDiff) ) {
871 *motionY = my+yOffset;
872 *motionX = mx+xOffset;
873 bestDiff = diff;
874 }
875 }
876 }
877
878 return bestDiff;
879 }
880
881
882 void
883 ShowPMVHistogram(fpointer)
884 FILE *fpointer;
885 {
886 register int x, y;
887 int *columnTotals;
888 int rowTotal;
889
890 columnTotals = (int *) calloc(2*searchRangeP+3, sizeof(int));
891
892 #ifdef COMPLETE_DISPLAY
893 fprintf(fpointer, " ");
894 for ( y = 0; y < 2*searchRange+3; y++ ) {
895 fprintf(fpointer, "%3d ", y-searchRangeP-1);
896 }
897 fprintf(fpointer, "\n");
898 #endif
899
900 for ( x = 0; x < 2*searchRangeP+3; x++ ) {
901 #ifdef COMPLETE_DISPLAY
902 fprintf(fpointer, "%3d ", x-searchRangeP-1);
903 #endif
904 rowTotal = 0;
905 for ( y = 0; y < 2*searchRangeP+3; y++ ) {
906 fprintf(fpointer, "%3d ", pmvHistogram[x][y]);
907 rowTotal += pmvHistogram[x][y];
908 columnTotals[y] += pmvHistogram[x][y];
909 }
910 #ifdef COMPLETE_DISPLAY
911 fprintf(fpointer, "%4d\n", rowTotal);
912 #else
913 fprintf(fpointer, "\n");
914 #endif
915 }
916
917 #ifdef COMPLETE_DISPLAY
918 fprintf(fpointer, "Tot ");
919 for ( y = 0; y < 2*searchRangeP+3; y++ ) {
920 fprintf(fpointer, "%3d ", columnTotals[y]);
921 }
922 #endif
923 fprintf(fpointer, "\n");
924 }
925
926
927 void
928 ShowBBMVHistogram(fpointer)
929 FILE *fpointer;
930 {
931 register int x, y;
932 int *columnTotals;
933 int rowTotal;
934
935 fprintf(fpointer, "B-frame Backwards:\n");
936
937 columnTotals = (int *) calloc(2*searchRangeB+3, sizeof(int));
938
939 #ifdef COMPLETE_DISPLAY
940 fprintf(fpointer, " ");
941 for ( y = 0; y < 2*searchRangeB+3; y++ ) {
942 fprintf(fpointer, "%3d ", y-searchRangeB-1);
943 }
944 fprintf(fpointer, "\n");
945 #endif
946
947 for ( x = 0; x < 2*searchRangeB+3; x++ ) {
948 #ifdef COMPLETE_DISPLAY
949 fprintf(fpointer, "%3d ", x-searchRangeB-1);
950 #endif
951 rowTotal = 0;
952 for ( y = 0; y < 2*searchRangeB+3; y++ ) {
953 fprintf(fpointer, "%3d ", bbmvHistogram[x][y]);
954 rowTotal += bbmvHistogram[x][y];
955 columnTotals[y] += bbmvHistogram[x][y];
956 }
957 #ifdef COMPLETE_DISPLAY
958 fprintf(fpointer, "%4d\n", rowTotal);
959 #else
960 fprintf(fpointer, "\n");
961 #endif
962 }
963
964 #ifdef COMPLETE_DISPLAY
965 fprintf(fpointer, "Tot ");
966 for ( y = 0; y < 2*searchRangeB+3; y++ ) {
967 fprintf(fpointer, "%3d ", columnTotals[y]);
968 }
969 #endif
970 fprintf(fpointer, "\n");
971 }
972
973
974 void
975 ShowBFMVHistogram(fpointer)
976 FILE *fpointer;
977 {
978 register int x, y;
979 int *columnTotals;
980 int rowTotal;
981
982 fprintf(fpointer, "B-frame Forwards:\n");
983
984 columnTotals = (int *) calloc(2*searchRangeB+3, sizeof(int));
985
986 #ifdef COMPLETE_DISPLAY
987 fprintf(fpointer, " ");
988 for ( y = 0; y < 2*searchRangeB+3; y++ ) {
989 fprintf(fpointer, "%3d ", y-searchRangeB-1);
990 }
991 fprintf(fpointer, "\n");
992 #endif
993
994 for ( x = 0; x < 2*searchRangeB+3; x++ ) {
995 #ifdef COMPLETE_DISPLAY
996 fprintf(fpointer, "%3d ", x-searchRangeB-1);
997 #endif
998 rowTotal = 0;
999 for ( y = 0; y < 2*searchRangeB+3; y++ ) {
1000 fprintf(fpointer, "%3d ", bfmvHistogram[x][y]);
1001 rowTotal += bfmvHistogram[x][y];
1002 columnTotals[y] += bfmvHistogram[x][y];
1003 }
1004 #ifdef COMPLETE_DISPLAY
1005 fprintf(fpointer, "%4d\n", rowTotal);
1006 #else
1007 fprintf(fpointer, "\n");
1008 #endif
1009 }
1010
1011 #ifdef COMPLETE_DISPLAY
1012 fprintf(fpointer, "Tot ");
1013 for ( y = 0; y < 2*searchRangeB+3; y++ ) {
1014 fprintf(fpointer, "%3d ", columnTotals[y]);
1015 }
1016 #endif
1017 fprintf(fpointer, "\n");
1018 }
1019
1020
1021 /*=====================*
1022 * INTERNAL PROCEDURES *
1023 *=====================*/
1024
1025 /* none */