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