GCC Code Coverage Report
Directory: ../../../ffmpeg/ Exec Total Coverage
File: src/libavfilter/motion_estimation.c Lines: 29 202 14.4 %
Date: 2020-09-25 23:16:12 Branches: 43 370 11.6 %

Line Branch Exec Source
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
2
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
2
    me_ctx->width = width;
49
2
    me_ctx->height = height;
50
2
    me_ctx->mb_size = mb_size;
51
2
    me_ctx->search_param = search_param;
52
2
    me_ctx->get_cost = &ff_me_cmp_sad;
53
2
    me_ctx->x_min = x_min;
54
2
    me_ctx->x_max = x_max;
55
2
    me_ctx->y_min = y_min;
56
2
    me_ctx->y_max = y_max;
57
2
}
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
1200
uint64_t ff_me_search_epzs(AVMotionEstContext *me_ctx, int x_mb, int y_mb, int *mv)
333
{
334
    int x, y;
335
1200
    int x_min = FFMAX(me_ctx->x_min, x_mb - me_ctx->search_param);
336
1200
    int y_min = FFMAX(me_ctx->y_min, y_mb - me_ctx->search_param);
337
1200
    int x_max = FFMIN(x_mb + me_ctx->search_param, me_ctx->x_max);
338
1200
    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
1200
    AVMotionEstPredictor *preds = me_ctx->preds;
343
344
1200
    cost_min = UINT64_MAX;
345
346


1200
    COST_P_MV(x_mb + me_ctx->pred_x, y_mb + me_ctx->pred_y);
347
348
6924
    for (i = 0; i < preds[0].nb; i++)
349


5724
        COST_P_MV(x_mb + preds[0].mvs[i][0], y_mb + preds[0].mvs[i][1]);
350
351
6920
    for (i = 0; i < preds[1].nb; i++)
352


5720
        COST_P_MV(x_mb + preds[1].mvs[i][0], y_mb + preds[1].mvs[i][1]);
353
354
    do {
355
2888
        x = mv[0];
356
2888
        y = mv[1];
357
358
14440
        for (i = 0; i < 4; i++)
359


11552
            COST_P_MV(x + dia1[i][0], y + dia1[i][1]);
360
361

2888
    } while (x != mv[0] || y != mv[1]);
362
363
1200
    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
}