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