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 #include "libavcodec/mathops.h"
23 #include "libavutil/common.h"
24 #include "libavutil/imgutils.h"
25 #include "libavutil/opt.h"
26 #include "libavutil/pixdesc.h"
27 #include "libavutil/motion_vector.h"
28 #include "avfilter.h"
29 #include "formats.h"
30 #include "internal.h"
31 #include "video.h"
32
33 typedef struct MEContext {
34 const AVClass *class;
35 AVMotionEstContext me_ctx;
36 int method; ///< motion estimation method
37
38 int mb_size; ///< macroblock size
39 int search_param; ///< search parameter
40 int b_width, b_height, b_count;
41 int log2_mb_size;
42
43 AVFrame *prev, *cur, *next;
44
45 int (*mv_table[3])[2][2]; ///< motion vectors of current & prev 2 frames
46 } MEContext;
47
48 #define OFFSET(x) offsetof(MEContext, x)
49 #define FLAGS AV_OPT_FLAG_VIDEO_PARAM|AV_OPT_FLAG_FILTERING_PARAM
50 #define CONST(name, help, val, unit) { name, help, 0, AV_OPT_TYPE_CONST, {.i64=val}, 0, 0, FLAGS, unit }
51
52 static const AVOption mestimate_options[] = {
53 { "method", "motion estimation method", OFFSET(method), AV_OPT_TYPE_INT, {.i64 = AV_ME_METHOD_ESA}, AV_ME_METHOD_ESA, AV_ME_METHOD_UMH, FLAGS, "method" },
54 CONST("esa", "exhaustive search", AV_ME_METHOD_ESA, "method"),
55 CONST("tss", "three step search", AV_ME_METHOD_TSS, "method"),
56 CONST("tdls", "two dimensional logarithmic search", AV_ME_METHOD_TDLS, "method"),
57 CONST("ntss", "new three step search", AV_ME_METHOD_NTSS, "method"),
58 CONST("fss", "four step search", AV_ME_METHOD_FSS, "method"),
59 CONST("ds", "diamond search", AV_ME_METHOD_DS, "method"),
60 CONST("hexbs", "hexagon-based search", AV_ME_METHOD_HEXBS, "method"),
61 CONST("epzs", "enhanced predictive zonal search", AV_ME_METHOD_EPZS, "method"),
62 CONST("umh", "uneven multi-hexagon search", AV_ME_METHOD_UMH, "method"),
63 { "mb_size", "macroblock size", OFFSET(mb_size), AV_OPT_TYPE_INT, {.i64 = 16}, 8, INT_MAX, FLAGS },
64 { "search_param", "search parameter", OFFSET(search_param), AV_OPT_TYPE_INT, {.i64 = 7}, 4, INT_MAX, FLAGS },
65 { NULL }
66 };
67
68 AVFILTER_DEFINE_CLASS(mestimate);
69
70 static const enum AVPixelFormat pix_fmts[] = {
71 AV_PIX_FMT_YUV410P, AV_PIX_FMT_YUV411P,
72 AV_PIX_FMT_YUV420P, AV_PIX_FMT_YUV422P,
73 AV_PIX_FMT_YUV440P, AV_PIX_FMT_YUV444P,
74 AV_PIX_FMT_YUVJ444P, AV_PIX_FMT_YUVJ440P,
75 AV_PIX_FMT_YUVJ422P, AV_PIX_FMT_YUVJ420P,
76 AV_PIX_FMT_YUVJ411P,
77 AV_PIX_FMT_YUVA420P, AV_PIX_FMT_YUVA422P, AV_PIX_FMT_YUVA444P,
78 AV_PIX_FMT_GRAY8,
79 AV_PIX_FMT_NONE
80 };
81
config_input(AVFilterLink * inlink)82 static int config_input(AVFilterLink *inlink)
83 {
84 MEContext *s = inlink->dst->priv;
85 int i;
86
87 s->log2_mb_size = av_ceil_log2_c(s->mb_size);
88 s->mb_size = 1 << s->log2_mb_size;
89
90 s->b_width = inlink->w >> s->log2_mb_size;
91 s->b_height = inlink->h >> s->log2_mb_size;
92 s->b_count = s->b_width * s->b_height;
93
94 if (s->b_count == 0)
95 return AVERROR(EINVAL);
96
97 for (i = 0; i < 3; i++) {
98 s->mv_table[i] = av_calloc(s->b_count, sizeof(*s->mv_table[0]));
99 if (!s->mv_table[i])
100 return AVERROR(ENOMEM);
101 }
102
103 ff_me_init_context(&s->me_ctx, s->mb_size, s->search_param, inlink->w, inlink->h, 0, (s->b_width - 1) << s->log2_mb_size, 0, (s->b_height - 1) << s->log2_mb_size);
104
105 return 0;
106 }
107
add_mv_data(AVMotionVector * mv,int mb_size,int x,int y,int x_mv,int y_mv,int dir)108 static void add_mv_data(AVMotionVector *mv, int mb_size,
109 int x, int y, int x_mv, int y_mv, int dir)
110 {
111 mv->w = mb_size;
112 mv->h = mb_size;
113 mv->dst_x = x + (mb_size >> 1);
114 mv->dst_y = y + (mb_size >> 1);
115 mv->src_x = x_mv + (mb_size >> 1);
116 mv->src_y = y_mv + (mb_size >> 1);
117 mv->source = dir ? 1 : -1;
118 mv->flags = 0;
119 }
120
121 #define SEARCH_MV(method)\
122 do {\
123 for (mb_y = 0; mb_y < s->b_height; mb_y++)\
124 for (mb_x = 0; mb_x < s->b_width; mb_x++) {\
125 const int x_mb = mb_x << s->log2_mb_size;\
126 const int y_mb = mb_y << s->log2_mb_size;\
127 int mv[2] = {x_mb, y_mb};\
128 ff_me_search_##method(me_ctx, x_mb, y_mb, mv);\
129 add_mv_data(((AVMotionVector *) sd->data) + mv_count++, me_ctx->mb_size, x_mb, y_mb, mv[0], mv[1], dir);\
130 }\
131 } while (0)
132
133 #define ADD_PRED(preds, px, py)\
134 do {\
135 preds.mvs[preds.nb][0] = px;\
136 preds.mvs[preds.nb][1] = py;\
137 preds.nb++;\
138 } while(0)
139
filter_frame(AVFilterLink * inlink,AVFrame * frame)140 static int filter_frame(AVFilterLink *inlink, AVFrame *frame)
141 {
142 AVFilterContext *ctx = inlink->dst;
143 MEContext *s = ctx->priv;
144 AVMotionEstContext *me_ctx = &s->me_ctx;
145 AVFrameSideData *sd;
146 AVFrame *out;
147 int mb_x, mb_y, dir;
148 int32_t mv_count = 0;
149 int ret;
150
151 if (frame->pts == AV_NOPTS_VALUE) {
152 ret = ff_filter_frame(ctx->outputs[0], frame);
153 return ret;
154 }
155
156 av_frame_free(&s->prev);
157 s->prev = s->cur;
158 s->cur = s->next;
159 s->next = frame;
160
161 s->mv_table[2] = memcpy(s->mv_table[2], s->mv_table[1], sizeof(*s->mv_table[1]) * s->b_count);
162 s->mv_table[1] = memcpy(s->mv_table[1], s->mv_table[0], sizeof(*s->mv_table[0]) * s->b_count);
163
164 if (!s->cur) {
165 s->cur = av_frame_clone(frame);
166 if (!s->cur)
167 return AVERROR(ENOMEM);
168 }
169
170 if (!s->prev)
171 return 0;
172
173 out = av_frame_clone(s->cur);
174 if (!out)
175 return AVERROR(ENOMEM);
176
177 sd = av_frame_new_side_data(out, AV_FRAME_DATA_MOTION_VECTORS, 2 * s->b_count * sizeof(AVMotionVector));
178 if (!sd) {
179 av_frame_free(&out);
180 return AVERROR(ENOMEM);
181 }
182
183 me_ctx->data_cur = s->cur->data[0];
184 me_ctx->linesize = s->cur->linesize[0];
185
186 for (dir = 0; dir < 2; dir++) {
187 me_ctx->data_ref = (dir ? s->next : s->prev)->data[0];
188
189 if (s->method == AV_ME_METHOD_DS)
190 SEARCH_MV(ds);
191 else if (s->method == AV_ME_METHOD_ESA)
192 SEARCH_MV(esa);
193 else if (s->method == AV_ME_METHOD_FSS)
194 SEARCH_MV(fss);
195 else if (s->method == AV_ME_METHOD_NTSS)
196 SEARCH_MV(ntss);
197 else if (s->method == AV_ME_METHOD_TDLS)
198 SEARCH_MV(tdls);
199 else if (s->method == AV_ME_METHOD_TSS)
200 SEARCH_MV(tss);
201 else if (s->method == AV_ME_METHOD_HEXBS)
202 SEARCH_MV(hexbs);
203 else if (s->method == AV_ME_METHOD_UMH) {
204 for (mb_y = 0; mb_y < s->b_height; mb_y++)
205 for (mb_x = 0; mb_x < s->b_width; mb_x++) {
206 const int mb_i = mb_x + mb_y * s->b_width;
207 const int x_mb = mb_x << s->log2_mb_size;
208 const int y_mb = mb_y << s->log2_mb_size;
209 int mv[2] = {x_mb, y_mb};
210
211 AVMotionEstPredictor *preds = me_ctx->preds;
212 preds[0].nb = 0;
213
214 ADD_PRED(preds[0], 0, 0);
215
216 //left mb in current frame
217 if (mb_x > 0)
218 ADD_PRED(preds[0], s->mv_table[0][mb_i - 1][dir][0], s->mv_table[0][mb_i - 1][dir][1]);
219
220 if (mb_y > 0) {
221 //top mb in current frame
222 ADD_PRED(preds[0], s->mv_table[0][mb_i - s->b_width][dir][0], s->mv_table[0][mb_i - s->b_width][dir][1]);
223
224 //top-right mb in current frame
225 if (mb_x + 1 < s->b_width)
226 ADD_PRED(preds[0], s->mv_table[0][mb_i - s->b_width + 1][dir][0], s->mv_table[0][mb_i - s->b_width + 1][dir][1]);
227 //top-left mb in current frame
228 else if (mb_x > 0)
229 ADD_PRED(preds[0], s->mv_table[0][mb_i - s->b_width - 1][dir][0], s->mv_table[0][mb_i - s->b_width - 1][dir][1]);
230 }
231
232 //median predictor
233 if (preds[0].nb == 4) {
234 me_ctx->pred_x = mid_pred(preds[0].mvs[1][0], preds[0].mvs[2][0], preds[0].mvs[3][0]);
235 me_ctx->pred_y = mid_pred(preds[0].mvs[1][1], preds[0].mvs[2][1], preds[0].mvs[3][1]);
236 } else if (preds[0].nb == 3) {
237 me_ctx->pred_x = mid_pred(0, preds[0].mvs[1][0], preds[0].mvs[2][0]);
238 me_ctx->pred_y = mid_pred(0, preds[0].mvs[1][1], preds[0].mvs[2][1]);
239 } else if (preds[0].nb == 2) {
240 me_ctx->pred_x = preds[0].mvs[1][0];
241 me_ctx->pred_y = preds[0].mvs[1][1];
242 } else {
243 me_ctx->pred_x = 0;
244 me_ctx->pred_y = 0;
245 }
246
247 ff_me_search_umh(me_ctx, x_mb, y_mb, mv);
248
249 s->mv_table[0][mb_i][dir][0] = mv[0] - x_mb;
250 s->mv_table[0][mb_i][dir][1] = mv[1] - y_mb;
251 add_mv_data(((AVMotionVector *) sd->data) + mv_count++, me_ctx->mb_size, x_mb, y_mb, mv[0], mv[1], dir);
252 }
253
254 } else if (s->method == AV_ME_METHOD_EPZS) {
255
256 for (mb_y = 0; mb_y < s->b_height; mb_y++)
257 for (mb_x = 0; mb_x < s->b_width; mb_x++) {
258 const int mb_i = mb_x + mb_y * s->b_width;
259 const int x_mb = mb_x << s->log2_mb_size;
260 const int y_mb = mb_y << s->log2_mb_size;
261 int mv[2] = {x_mb, y_mb};
262
263 AVMotionEstPredictor *preds = me_ctx->preds;
264 preds[0].nb = 0;
265 preds[1].nb = 0;
266
267 ADD_PRED(preds[0], 0, 0);
268
269 //left mb in current frame
270 if (mb_x > 0)
271 ADD_PRED(preds[0], s->mv_table[0][mb_i - 1][dir][0], s->mv_table[0][mb_i - 1][dir][1]);
272
273 //top mb in current frame
274 if (mb_y > 0)
275 ADD_PRED(preds[0], s->mv_table[0][mb_i - s->b_width][dir][0], s->mv_table[0][mb_i - s->b_width][dir][1]);
276
277 //top-right mb in current frame
278 if (mb_y > 0 && mb_x + 1 < s->b_width)
279 ADD_PRED(preds[0], s->mv_table[0][mb_i - s->b_width + 1][dir][0], s->mv_table[0][mb_i - s->b_width + 1][dir][1]);
280
281 //median predictor
282 if (preds[0].nb == 4) {
283 me_ctx->pred_x = mid_pred(preds[0].mvs[1][0], preds[0].mvs[2][0], preds[0].mvs[3][0]);
284 me_ctx->pred_y = mid_pred(preds[0].mvs[1][1], preds[0].mvs[2][1], preds[0].mvs[3][1]);
285 } else if (preds[0].nb == 3) {
286 me_ctx->pred_x = mid_pred(0, preds[0].mvs[1][0], preds[0].mvs[2][0]);
287 me_ctx->pred_y = mid_pred(0, preds[0].mvs[1][1], preds[0].mvs[2][1]);
288 } else if (preds[0].nb == 2) {
289 me_ctx->pred_x = preds[0].mvs[1][0];
290 me_ctx->pred_y = preds[0].mvs[1][1];
291 } else {
292 me_ctx->pred_x = 0;
293 me_ctx->pred_y = 0;
294 }
295
296 //collocated mb in prev frame
297 ADD_PRED(preds[0], s->mv_table[1][mb_i][dir][0], s->mv_table[1][mb_i][dir][1]);
298
299 //accelerator motion vector of collocated block in prev frame
300 ADD_PRED(preds[1], s->mv_table[1][mb_i][dir][0] + (s->mv_table[1][mb_i][dir][0] - s->mv_table[2][mb_i][dir][0]),
301 s->mv_table[1][mb_i][dir][1] + (s->mv_table[1][mb_i][dir][1] - s->mv_table[2][mb_i][dir][1]));
302
303 //left mb in prev frame
304 if (mb_x > 0)
305 ADD_PRED(preds[1], s->mv_table[1][mb_i - 1][dir][0], s->mv_table[1][mb_i - 1][dir][1]);
306
307 //top mb in prev frame
308 if (mb_y > 0)
309 ADD_PRED(preds[1], s->mv_table[1][mb_i - s->b_width][dir][0], s->mv_table[1][mb_i - s->b_width][dir][1]);
310
311 //right mb in prev frame
312 if (mb_x + 1 < s->b_width)
313 ADD_PRED(preds[1], s->mv_table[1][mb_i + 1][dir][0], s->mv_table[1][mb_i + 1][dir][1]);
314
315 //bottom mb in prev frame
316 if (mb_y + 1 < s->b_height)
317 ADD_PRED(preds[1], s->mv_table[1][mb_i + s->b_width][dir][0], s->mv_table[1][mb_i + s->b_width][dir][1]);
318
319 ff_me_search_epzs(me_ctx, x_mb, y_mb, mv);
320
321 s->mv_table[0][mb_i][dir][0] = mv[0] - x_mb;
322 s->mv_table[0][mb_i][dir][1] = mv[1] - y_mb;
323 add_mv_data(((AVMotionVector *) sd->data) + mv_count++, s->mb_size, x_mb, y_mb, mv[0], mv[1], dir);
324 }
325 }
326 }
327
328 return ff_filter_frame(ctx->outputs[0], out);
329 }
330
uninit(AVFilterContext * ctx)331 static av_cold void uninit(AVFilterContext *ctx)
332 {
333 MEContext *s = ctx->priv;
334 int i;
335
336 av_frame_free(&s->prev);
337 av_frame_free(&s->cur);
338 av_frame_free(&s->next);
339
340 for (i = 0; i < 3; i++)
341 av_freep(&s->mv_table[i]);
342 }
343
344 static const AVFilterPad mestimate_inputs[] = {
345 {
346 .name = "default",
347 .type = AVMEDIA_TYPE_VIDEO,
348 .filter_frame = filter_frame,
349 .config_props = config_input,
350 },
351 };
352
353 static const AVFilterPad mestimate_outputs[] = {
354 {
355 .name = "default",
356 .type = AVMEDIA_TYPE_VIDEO,
357 },
358 };
359
360 const AVFilter ff_vf_mestimate = {
361 .name = "mestimate",
362 .description = NULL_IF_CONFIG_SMALL("Generate motion vectors."),
363 .priv_size = sizeof(MEContext),
364 .priv_class = &mestimate_class,
365 .uninit = uninit,
366 .flags = AVFILTER_FLAG_METADATA_ONLY,
367 FILTER_INPUTS(mestimate_inputs),
368 FILTER_OUTPUTS(mestimate_outputs),
369 FILTER_PIXFMTS_ARRAY(pix_fmts),
370 };
371