avfilter/avf_concat: check ff_insert_pad() for failure
[ffmpeg.git] / libavfilter / motion_estimation.c
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 }