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