FFmpeg
motion_estimation.c
Go to the documentation of this file.
1 /**
2  * Copyright (c) 2016 Davinder Singh (DSM_) <ds.mudhar<@gmail.com>
3  *
4  * This file is part of FFmpeg.
5  *
6  * FFmpeg is free software; you can redistribute it and/or
7  * modify it under the terms of the GNU Lesser General Public
8  * License as published by the Free Software Foundation; either
9  * version 2.1 of the License, or (at your option) any later version.
10  *
11  * FFmpeg is distributed in the hope that it will be useful,
12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14  * Lesser General Public License for more details.
15  *
16  * You should have received a copy of the GNU Lesser General Public
17  * License along with FFmpeg; if not, write to the Free Software
18  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
19  */
20 
21 #include "libavutil/common.h"
22 #include "motion_estimation.h"
23 
24 static const int8_t sqr1[8][2] = {{ 0,-1}, { 0, 1}, {-1, 0}, { 1, 0}, {-1,-1}, {-1, 1}, { 1,-1}, { 1, 1}};
25 static const int8_t dia1[4][2] = {{-1, 0}, { 0,-1}, { 1, 0}, { 0, 1}};
26 static const int8_t dia2[8][2] = {{-2, 0}, {-1,-1}, { 0,-2}, { 1,-1}, { 2, 0}, { 1, 1}, { 0, 2}, {-1, 1}};
27 static const int8_t hex2[6][2] = {{-2, 0}, {-1,-2}, {-1, 2}, { 1,-2}, { 1, 2}, { 2, 0}};
28 static const int8_t hex4[16][2] = {{-4,-2}, {-4,-1}, {-4, 0}, {-4, 1}, {-4, 2},
29  { 4,-2}, { 4,-1}, { 4, 0}, { 4, 1}, { 4, 2},
30  {-2, 3}, { 0, 4}, { 2, 3}, {-2,-3}, { 0,-4}, { 2,-3}};
31 
32 #define COST_MV(x, y)\
33 do {\
34  cost = me_ctx->get_cost(me_ctx, x_mb, y_mb, x, y);\
35  if (cost < cost_min) {\
36  cost_min = cost;\
37  mv[0] = x;\
38  mv[1] = y;\
39  }\
40 } while(0)
41 
42 #define COST_P_MV(x, y)\
43 if (x >= x_min && x <= x_max && y >= y_min && y <= y_max)\
44  COST_MV(x, y);
45 
46 void ff_me_init_context(AVMotionEstContext *me_ctx, int mb_size, int search_param,
47  int width, int height, int x_min, int x_max, int y_min, int y_max)
48 {
49  me_ctx->width = width;
50  me_ctx->height = height;
51  me_ctx->mb_size = mb_size;
52  me_ctx->search_param = search_param;
53  me_ctx->get_cost = &ff_me_cmp_sad;
54  me_ctx->x_min = x_min;
55  me_ctx->x_max = x_max;
56  me_ctx->y_min = y_min;
57  me_ctx->y_max = y_max;
58 }
59 
60 uint64_t ff_me_cmp_sad(AVMotionEstContext *me_ctx, int x_mb, int y_mb, int x_mv, int y_mv)
61 {
62  const int linesize = me_ctx->linesize;
63  uint8_t *data_ref = me_ctx->data_ref;
64  uint8_t *data_cur = me_ctx->data_cur;
65  uint64_t sad = 0;
66  int i, j;
67 
68  data_ref += y_mv * linesize;
69  data_cur += y_mb * linesize;
70 
71  for (j = 0; j < me_ctx->mb_size; j++)
72  for (i = 0; i < me_ctx->mb_size; i++)
73  sad += FFABS(data_ref[x_mv + i + j * linesize] - data_cur[x_mb + i + j * linesize]);
74 
75  return sad;
76 }
77 
78 uint64_t ff_me_search_esa(AVMotionEstContext *me_ctx, int x_mb, int y_mb, int *mv)
79 {
80  int x, y;
81  int x_min = FFMAX(me_ctx->x_min, x_mb - me_ctx->search_param);
82  int y_min = FFMAX(me_ctx->y_min, y_mb - me_ctx->search_param);
83  int x_max = FFMIN(x_mb + me_ctx->search_param, me_ctx->x_max);
84  int y_max = FFMIN(y_mb + me_ctx->search_param, me_ctx->y_max);
85  uint64_t cost, cost_min;
86 
87  if (!(cost_min = me_ctx->get_cost(me_ctx, x_mb, y_mb, x_mb, y_mb)))
88  return cost_min;
89 
90  for (y = y_min; y <= y_max; y++)
91  for (x = x_min; x <= x_max; x++)
92  COST_MV(x, y);
93 
94  return cost_min;
95 }
96 
97 uint64_t ff_me_search_tss(AVMotionEstContext *me_ctx, int x_mb, int y_mb, int *mv)
98 {
99  int x, y;
100  int x_min = FFMAX(me_ctx->x_min, x_mb - me_ctx->search_param);
101  int y_min = FFMAX(me_ctx->y_min, y_mb - me_ctx->search_param);
102  int x_max = FFMIN(x_mb + me_ctx->search_param, me_ctx->x_max);
103  int y_max = FFMIN(y_mb + me_ctx->search_param, me_ctx->y_max);
104  uint64_t cost, cost_min;
105  int step = ROUNDED_DIV(me_ctx->search_param, 2);
106  int i;
107 
108  mv[0] = x_mb;
109  mv[1] = y_mb;
110 
111  if (!(cost_min = me_ctx->get_cost(me_ctx, x_mb, y_mb, x_mb, y_mb)))
112  return cost_min;
113 
114  do {
115  x = mv[0];
116  y = mv[1];
117 
118  for (i = 0; i < 8; i++)
119  COST_P_MV(x + sqr1[i][0] * step, y + sqr1[i][1] * step);
120 
121  step = step >> 1;
122 
123  } while (step > 0);
124 
125  return cost_min;
126 }
127 
128 uint64_t ff_me_search_tdls(AVMotionEstContext *me_ctx, int x_mb, int y_mb, int *mv)
129 {
130  int x, y;
131  int x_min = FFMAX(me_ctx->x_min, x_mb - me_ctx->search_param);
132  int y_min = FFMAX(me_ctx->y_min, y_mb - me_ctx->search_param);
133  int x_max = FFMIN(x_mb + me_ctx->search_param, me_ctx->x_max);
134  int y_max = FFMIN(y_mb + me_ctx->search_param, me_ctx->y_max);
135  uint64_t cost, cost_min;
136  int step = ROUNDED_DIV(me_ctx->search_param, 2);
137  int i;
138 
139  mv[0] = x_mb;
140  mv[1] = y_mb;
141 
142  if (!(cost_min = me_ctx->get_cost(me_ctx, x_mb, y_mb, x_mb, y_mb)))
143  return cost_min;
144 
145  do {
146  x = mv[0];
147  y = mv[1];
148 
149  for (i = 0; i < 4; i++)
150  COST_P_MV(x + dia1[i][0] * step, y + dia1[i][1] * step);
151 
152  if (x == mv[0] && y == mv[1])
153  step = step >> 1;
154 
155  } while (step > 0);
156 
157  return cost_min;
158 }
159 
160 uint64_t ff_me_search_ntss(AVMotionEstContext *me_ctx, int x_mb, int y_mb, int *mv)
161 {
162  int x, y;
163  int x_min = FFMAX(me_ctx->x_min, x_mb - me_ctx->search_param);
164  int y_min = FFMAX(me_ctx->y_min, y_mb - me_ctx->search_param);
165  int x_max = FFMIN(x_mb + me_ctx->search_param, me_ctx->x_max);
166  int y_max = FFMIN(y_mb + me_ctx->search_param, me_ctx->y_max);
167  uint64_t cost, cost_min;
168  int step = ROUNDED_DIV(me_ctx->search_param, 2);
169  int first_step = 1;
170  int i;
171 
172  mv[0] = x_mb;
173  mv[1] = y_mb;
174 
175  if (!(cost_min = me_ctx->get_cost(me_ctx, x_mb, y_mb, x_mb, y_mb)))
176  return cost_min;
177 
178  do {
179  x = mv[0];
180  y = mv[1];
181 
182  for (i = 0; i < 8; i++)
183  COST_P_MV(x + sqr1[i][0] * step, y + sqr1[i][1] * step);
184 
185  /* addition to TSS in NTSS */
186  if (first_step) {
187 
188  for (i = 0; i < 8; i++)
189  COST_P_MV(x + sqr1[i][0], y + sqr1[i][1]);
190 
191  if (x == mv[0] && y == mv[1])
192  return cost_min;
193 
194  if (FFABS(x - mv[0]) <= 1 && FFABS(y - mv[1]) <= 1) {
195  x = mv[0];
196  y = mv[1];
197 
198  for (i = 0; i < 8; i++)
199  COST_P_MV(x + sqr1[i][0], y + sqr1[i][1]);
200  return cost_min;
201  }
202 
203  first_step = 0;
204  }
205 
206  step = step >> 1;
207 
208  } while (step > 0);
209 
210  return cost_min;
211 }
212 
213 uint64_t ff_me_search_fss(AVMotionEstContext *me_ctx, int x_mb, int y_mb, int *mv)
214 {
215  int x, y;
216  int x_min = FFMAX(me_ctx->x_min, x_mb - me_ctx->search_param);
217  int y_min = FFMAX(me_ctx->y_min, y_mb - me_ctx->search_param);
218  int x_max = FFMIN(x_mb + me_ctx->search_param, me_ctx->x_max);
219  int y_max = FFMIN(y_mb + me_ctx->search_param, me_ctx->y_max);
220  uint64_t cost, cost_min;
221  int step = 2;
222  int i;
223 
224  mv[0] = x_mb;
225  mv[1] = y_mb;
226 
227  if (!(cost_min = me_ctx->get_cost(me_ctx, x_mb, y_mb, x_mb, y_mb)))
228  return cost_min;
229 
230  do {
231  x = mv[0];
232  y = mv[1];
233 
234  for (i = 0; i < 8; i++)
235  COST_P_MV(x + sqr1[i][0] * step, y + sqr1[i][1] * step);
236 
237  if (x == mv[0] && y == mv[1])
238  step = step >> 1;
239 
240  } while (step > 0);
241 
242  return cost_min;
243 }
244 
245 uint64_t ff_me_search_ds(AVMotionEstContext *me_ctx, int x_mb, int y_mb, int *mv)
246 {
247  int x, y;
248  int x_min = FFMAX(me_ctx->x_min, x_mb - me_ctx->search_param);
249  int y_min = FFMAX(me_ctx->y_min, y_mb - me_ctx->search_param);
250  int x_max = FFMIN(x_mb + me_ctx->search_param, me_ctx->x_max);
251  int y_max = FFMIN(y_mb + me_ctx->search_param, me_ctx->y_max);
252  uint64_t cost, cost_min;
253  int i;
254  av_unused int dir_x, dir_y;
255 
256  if (!(cost_min = me_ctx->get_cost(me_ctx, x_mb, y_mb, x_mb, y_mb)))
257  return cost_min;
258 
259  x = x_mb; y = y_mb;
260  dir_x = dir_y = 0;
261 
262  do {
263  x = mv[0];
264  y = mv[1];
265 
266 #if 1
267  for (i = 0; i < 8; i++)
268  COST_P_MV(x + dia2[i][0], y + dia2[i][1]);
269 #else
270  /* this version skips previously examined 3 or 5 locations based on prev origin */
271  if (dir_x <= 0)
272  COST_P_MV(x - 2, y);
273  if (dir_x <= 0 && dir_y <= 0)
274  COST_P_MV(x - 1, y - 1);
275  if (dir_y <= 0)
276  COST_P_MV(x, y - 2);
277  if (dir_x >= 0 && dir_y <= 0)
278  COST_P_MV(x + 1, y - 1);
279  if (dir_x >= 0)
280  COST_P_MV(x + 2, y);
281  if (dir_x >= 0 && dir_y >= 0)
282  COST_P_MV(x + 1, y + 1);
283  if (dir_y >= 0)
284  COST_P_MV(x, y + 2);
285  if (dir_x <= 0 && dir_y >= 0)
286  COST_P_MV(x - 1, y + 1);
287 
288  dir_x = mv[0] - x;
289  dir_y = mv[1] - y;
290 #endif
291 
292  } while (x != mv[0] || y != mv[1]);
293 
294  for (i = 0; i < 4; i++)
295  COST_P_MV(x + dia1[i][0], y + dia1[i][1]);
296 
297  return cost_min;
298 }
299 
300 uint64_t ff_me_search_hexbs(AVMotionEstContext *me_ctx, int x_mb, int y_mb, int *mv)
301 {
302  int x, y;
303  int x_min = FFMAX(me_ctx->x_min, x_mb - me_ctx->search_param);
304  int y_min = FFMAX(me_ctx->y_min, y_mb - me_ctx->search_param);
305  int x_max = FFMIN(x_mb + me_ctx->search_param, me_ctx->x_max);
306  int y_max = FFMIN(y_mb + me_ctx->search_param, me_ctx->y_max);
307  uint64_t cost, cost_min;
308  int i;
309 
310  if (!(cost_min = me_ctx->get_cost(me_ctx, x_mb, y_mb, x_mb, y_mb)))
311  return cost_min;
312 
313  do {
314  x = mv[0];
315  y = mv[1];
316 
317  for (i = 0; i < 6; i++)
318  COST_P_MV(x + hex2[i][0], y + hex2[i][1]);
319 
320  } while (x != mv[0] || y != mv[1]);
321 
322  for (i = 0; i < 4; i++)
323  COST_P_MV(x + dia1[i][0], y + dia1[i][1]);
324 
325  return cost_min;
326 }
327 
328 /* two subsets of predictors are used
329  me->pred_x|y is set to median of current frame's left, top, top-right
330  set 1: me->preds[0] has: (0, 0), left, top, top-right, collocated block in prev frame
331  set 2: me->preds[1] has: accelerator mv, top, left, right, bottom adj mb of prev frame
332 */
333 uint64_t ff_me_search_epzs(AVMotionEstContext *me_ctx, int x_mb, int y_mb, int *mv)
334 {
335  int x, y;
336  int x_min = FFMAX(me_ctx->x_min, x_mb - me_ctx->search_param);
337  int y_min = FFMAX(me_ctx->y_min, y_mb - me_ctx->search_param);
338  int x_max = FFMIN(x_mb + me_ctx->search_param, me_ctx->x_max);
339  int y_max = FFMIN(y_mb + me_ctx->search_param, me_ctx->y_max);
340  uint64_t cost, cost_min;
341  int i;
342 
343  AVMotionEstPredictor *preds = me_ctx->preds;
344 
345  cost_min = UINT64_MAX;
346 
347  COST_P_MV(x_mb + me_ctx->pred_x, y_mb + me_ctx->pred_y);
348 
349  for (i = 0; i < preds[0].nb; i++)
350  COST_P_MV(x_mb + preds[0].mvs[i][0], y_mb + preds[0].mvs[i][1]);
351 
352  for (i = 0; i < preds[1].nb; i++)
353  COST_P_MV(x_mb + preds[1].mvs[i][0], y_mb + preds[1].mvs[i][1]);
354 
355  do {
356  x = mv[0];
357  y = mv[1];
358 
359  for (i = 0; i < 4; i++)
360  COST_P_MV(x + dia1[i][0], y + dia1[i][1]);
361 
362  } while (x != mv[0] || y != mv[1]);
363 
364  return cost_min;
365 }
366 
367 /* required predictor order: median, (0,0), left, top, top-right
368  rules when mb not available:
369  replace left with (0, 0)
370  replace top-right with top-left
371  replace top two with left
372  repeated can be skipped, if no predictors are used, set me_ctx->pred to (0,0)
373 */
374 uint64_t ff_me_search_umh(AVMotionEstContext *me_ctx, int x_mb, int y_mb, int *mv)
375 {
376  int x, y;
377  int x_min = FFMAX(me_ctx->x_min, x_mb - me_ctx->search_param);
378  int y_min = FFMAX(me_ctx->y_min, y_mb - me_ctx->search_param);
379  int x_max = FFMIN(x_mb + me_ctx->search_param, me_ctx->x_max);
380  int y_max = FFMIN(y_mb + me_ctx->search_param, me_ctx->y_max);
381  uint64_t cost, cost_min;
382  int d, i;
383  int end_x, end_y;
384 
385  AVMotionEstPredictor *pred = &me_ctx->preds[0];
386 
387  cost_min = UINT64_MAX;
388 
389  COST_P_MV(x_mb + me_ctx->pred_x, y_mb + me_ctx->pred_y);
390 
391  for (i = 0; i < pred->nb; i++)
392  COST_P_MV(x_mb + pred->mvs[i][0], y_mb + pred->mvs[i][1]);
393 
394  // Unsymmetrical-cross Search
395  x = mv[0];
396  y = mv[1];
397  for (d = 1; d <= me_ctx->search_param; d += 2) {
398  COST_P_MV(x - d, y);
399  COST_P_MV(x + d, y);
400  if (d <= me_ctx->search_param / 2) {
401  COST_P_MV(x, y - d);
402  COST_P_MV(x, y + d);
403  }
404  }
405 
406  // Uneven Multi-Hexagon-Grid Search
407  end_x = FFMIN(mv[0] + 2, x_max);
408  end_y = FFMIN(mv[1] + 2, y_max);
409  for (y = FFMAX(y_min, mv[1] - 2); y <= end_y; y++)
410  for (x = FFMAX(x_min, mv[0] - 2); x <= end_x; x++)
411  COST_P_MV(x, y);
412 
413  x = mv[0];
414  y = mv[1];
415  for (d = 1; d <= me_ctx->search_param / 4; d++)
416  for (i = 1; i < 16; i++)
417  COST_P_MV(x + hex4[i][0] * d, y + hex4[i][1] * d);
418 
419  // Extended Hexagon-based Search
420  do {
421  x = mv[0];
422  y = mv[1];
423 
424  for (i = 0; i < 6; i++)
425  COST_P_MV(x + hex2[i][0], y + hex2[i][1]);
426 
427  } while (x != mv[0] || y != mv[1]);
428 
429  for (i = 0; i < 4; i++)
430  COST_P_MV(x + dia1[i][0], y + dia1[i][1]);
431 
432  return cost_min;
433 }
AVMotionEstPredictor::nb
int nb
Definition: motion_estimation.h:38
AVMotionEstContext::data_ref
uint8_t * data_ref
Definition: motion_estimation.h:42
dia2
static const int8_t dia2[8][2]
Definition: motion_estimation.c:26
AVMotionEstPredictor
Definition: motion_estimation.h:36
ff_me_search_esa
uint64_t ff_me_search_esa(AVMotionEstContext *me_ctx, int x_mb, int y_mb, int *mv)
Definition: motion_estimation.c:78
mv
static const int8_t mv[256][2]
Definition: 4xm.c:80
av_unused
#define av_unused
Definition: attributes.h:131
AVMotionEstContext::data_cur
uint8_t * data_cur
Definition: motion_estimation.h:42
step
trying all byte sequences megabyte in length and selecting the best looking sequence will yield cases to try But a word about which is also called distortion Distortion can be quantified by almost any quality measurement one chooses the sum of squared differences is used but more complex methods that consider psychovisual effects can be used as well It makes no difference in this discussion First step
Definition: rate_distortion.txt:58
FFMAX
#define FFMAX(a, b)
Definition: macros.h:47
AVMotionEstContext::pred_x
int pred_x
median predictor x
Definition: motion_estimation.h:56
ff_me_search_ntss
uint64_t ff_me_search_ntss(AVMotionEstContext *me_ctx, int x_mb, int y_mb, int *mv)
Definition: motion_estimation.c:160
ff_me_search_tss
uint64_t ff_me_search_tss(AVMotionEstContext *me_ctx, int x_mb, int y_mb, int *mv)
Definition: motion_estimation.c:97
hex2
static const int8_t hex2[6][2]
Definition: motion_estimation.c:27
width
#define width
AVMotionEstContext::x_max
int x_max
Definition: motion_estimation.h:52
AVMotionEstContext::x_min
int x_min
Definition: motion_estimation.h:51
COST_MV
#define COST_MV(x, y)
Definition: motion_estimation.c:32
ff_me_search_fss
uint64_t ff_me_search_fss(AVMotionEstContext *me_ctx, int x_mb, int y_mb, int *mv)
Definition: motion_estimation.c:213
AVMotionEstContext
Definition: motion_estimation.h:41
ff_me_search_ds
uint64_t ff_me_search_ds(AVMotionEstContext *me_ctx, int x_mb, int y_mb, int *mv)
Definition: motion_estimation.c:245
FFABS
#define FFABS(a)
Absolute value, Note, INT_MIN / INT64_MIN result in undefined behavior as they are not representable ...
Definition: common.h:64
AVMotionEstContext::search_param
int search_param
Definition: motion_estimation.h:46
ROUNDED_DIV
#define ROUNDED_DIV(a, b)
Definition: common.h:48
motion_estimation.h
ff_me_cmp_sad
uint64_t ff_me_cmp_sad(AVMotionEstContext *me_ctx, int x_mb, int y_mb, int x_mv, int y_mv)
Definition: motion_estimation.c:60
ff_me_search_hexbs
uint64_t ff_me_search_hexbs(AVMotionEstContext *me_ctx, int x_mb, int y_mb, int *mv)
Definition: motion_estimation.c:300
AVMotionEstContext::y_min
int y_min
Definition: motion_estimation.h:53
ff_me_search_epzs
uint64_t ff_me_search_epzs(AVMotionEstContext *me_ctx, int x_mb, int y_mb, int *mv)
Definition: motion_estimation.c:333
height
#define height
i
#define i(width, name, range_min, range_max)
Definition: cbs_h2645.c:269
hex4
static const int8_t hex4[16][2]
Definition: motion_estimation.c:28
common.h
sqr1
static const int8_t sqr1[8][2]
Copyright (c) 2016 Davinder Singh (DSM_) <ds.mudhar<@gmail.com>
Definition: motion_estimation.c:24
FFMIN
#define FFMIN(a, b)
Definition: macros.h:49
AVMotionEstContext::width
int width
Definition: motion_estimation.h:48
ff_me_search_tdls
uint64_t ff_me_search_tdls(AVMotionEstContext *me_ctx, int x_mb, int y_mb, int *mv)
Definition: motion_estimation.c:128
dia1
static const int8_t dia1[4][2]
Definition: motion_estimation.c:25
pred
static const float pred[4]
Definition: siprdata.h:259
AVMotionEstContext::y_max
int y_max
Definition: motion_estimation.h:54
ff_me_init_context
void ff_me_init_context(AVMotionEstContext *me_ctx, int mb_size, int search_param, int width, int height, int x_min, int x_max, int y_min, int y_max)
Definition: motion_estimation.c:46
AVMotionEstContext::pred_y
int pred_y
median predictor y
Definition: motion_estimation.h:57
AVMotionEstContext::linesize
int linesize
Definition: motion_estimation.h:43
d
d
Definition: ffmpeg_filter.c:156
ff_me_search_umh
uint64_t ff_me_search_umh(AVMotionEstContext *me_ctx, int x_mb, int y_mb, int *mv)
Definition: motion_estimation.c:374
AVMotionEstContext::height
int height
Definition: motion_estimation.h:49
COST_P_MV
#define COST_P_MV(x, y)
Definition: motion_estimation.c:42
AVMotionEstContext::preds
AVMotionEstPredictor preds[2]
Definition: motion_estimation.h:58
AVMotionEstContext::get_cost
uint64_t(* get_cost)(struct AVMotionEstContext *me_ctx, int x_mb, int y_mb, int mv_x, int mv_y)
Definition: motion_estimation.h:60
AVMotionEstContext::mb_size
int mb_size
Definition: motion_estimation.h:45
Generated on Tue Feb 28 2023 21:33:51 for FFmpeg by   doxygen 1.8.17