summaryrefslogtreecommitdiff
path: root/libavfilter/motion_estimation.c (plain)
blob: 0f9ba21784f3a998e75cbfd9f93e17157c1101c1
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
23static const int8_t sqr1[8][2] = {{ 0,-1}, { 0, 1}, {-1, 0}, { 1, 0}, {-1,-1}, {-1, 1}, { 1,-1}, { 1, 1}};
24static const int8_t dia1[4][2] = {{-1, 0}, { 0,-1}, { 1, 0}, { 0, 1}};
25static const int8_t dia2[8][2] = {{-2, 0}, {-1,-1}, { 0,-2}, { 1,-1}, { 2, 0}, { 1, 1}, { 0, 2}, {-1, 1}};
26static const int8_t hex2[6][2] = {{-2, 0}, {-1,-2}, {-1, 2}, { 1,-2}, { 1, 2}, { 2, 0}};
27static 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)\
32do {\
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)\
42if (x >= x_min && x <= x_max && y >= y_min && y <= y_max)\
43 COST_MV(x, y);
44
45void 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
59uint64_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
77uint64_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
96uint64_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
127uint64_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
159uint64_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
212uint64_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
244uint64_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
299uint64_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*/
332uint64_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*/
373uint64_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}
433
generated by cgit at 2024-05-17 06:58:04 (GMT)