FFmpeg  4.0
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 }
uint64_t ff_me_search_hexbs(AVMotionEstContext *me_ctx, int x_mb, int y_mb, int *mv)
int pred_y
median predictor y
uint64_t(* get_cost)(struct AVMotionEstContext *me_ctx, int x_mb, int y_mb, int mv_x, int mv_y)
#define COST_P_MV(x, y)
AVMotionEstPredictor preds[2]
#define COST_MV(x, y)
uint64_t ff_me_search_fss(AVMotionEstContext *me_ctx, int x_mb, int y_mb, int *mv)
uint8_t
static const int8_t hex4[16][2]
static const int8_t sqr1[8][2]
Copyright (c) 2016 Davinder Singh (DSM_) <ds.mudhar<.com>
int pred_x
median predictor x
uint64_t ff_me_search_ds(AVMotionEstContext *me_ctx, int x_mb, int y_mb, int *mv)
uint64_t ff_me_search_umh(AVMotionEstContext *me_ctx, int x_mb, int y_mb, int *mv)
#define height
#define ROUNDED_DIV(a, b)
Definition: common.h:56
uint64_t ff_me_search_epzs(AVMotionEstContext *me_ctx, int x_mb, int y_mb, int *mv)
uint16_t width
Definition: gdv.c:47
#define FFMAX(a, b)
Definition: common.h:94
uint64_t ff_me_search_tdls(AVMotionEstContext *me_ctx, int x_mb, int y_mb, int *mv)
static const int8_t dia1[4][2]
#define FFMIN(a, b)
Definition: common.h:96
#define FFABS(a)
Absolute value, Note, INT_MIN / INT64_MIN result in undefined behavior as they are not representable ...
Definition: common.h:72
uint64_t ff_me_search_ntss(AVMotionEstContext *me_ctx, int x_mb, int y_mb, int *mv)
static const int8_t dia2[8][2]
static const int8_t hex2[6][2]
static const float pred[4]
Definition: siprdata.h:259
static const int8_t mv[256][2]
Definition: 4xm.c:77
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)
uint64_t ff_me_cmp_sad(AVMotionEstContext *me_ctx, int x_mb, int y_mb, int x_mv, int y_mv)
uint64_t ff_me_search_esa(AVMotionEstContext *me_ctx, int x_mb, int y_mb, int *mv)
uint64_t ff_me_search_tss(AVMotionEstContext *me_ctx, int x_mb, int y_mb, int *mv)
#define av_unused
Definition: attributes.h:125