git.sesse.net Git - ffmpeg/blob - libavfilter/vf_minterpolate.c

   1 /**
   2  * Copyright (c) 2014-2015 Michael Niedermayer <michaelni@gmx.at>
   3  * Copyright (c) 2016 Davinder Singh (DSM_) <ds.mudhar<@gmail.com>
   4  *
   5  * This file is part of FFmpeg.
   6  *
   7  * FFmpeg is free software; you can redistribute it and/or
   8  * modify it under the terms of the GNU Lesser General Public
   9  * License as published by the Free Software Foundation; either
  10  * version 2.1 of the License, or (at your option) any later version.
  11  *
  12  * FFmpeg is distributed in the hope that it will be useful,
  13  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  15  * Lesser General Public License for more details.
  16  *
  17  * You should have received a copy of the GNU Lesser General Public
  18  * License along with FFmpeg; if not, write to the Free Software
  19  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
  20  */
  21
  22 #include "motion_estimation.h"
  23 #include "libavcodec/mathops.h"
  24 #include "libavutil/avassert.h"
  25 #include "libavutil/common.h"
  26 #include "libavutil/motion_vector.h"
  27 #include "libavutil/opt.h"
  28 #include "libavutil/pixdesc.h"
  29 #include "avfilter.h"
  30 #include "formats.h"
  31 #include "internal.h"
  32 #include "video.h"
  33 #include "scene_sad.h"
  34
  35 #define ME_MODE_BIDIR 0
  36 #define ME_MODE_BILAT 1
  37
  38 #define MC_MODE_OBMC 0
  39 #define MC_MODE_AOBMC 1
  40
  41 #define SCD_METHOD_NONE 0
  42 #define SCD_METHOD_FDIFF 1
  43
  44 #define NB_FRAMES 4
  45 #define NB_PIXEL_MVS 32
  46 #define NB_CLUSTERS 128
  47
  48 #define ALPHA_MAX 1024
  49 #define CLUSTER_THRESHOLD 4
  50 #define PX_WEIGHT_MAX 255
  51 #define COST_PRED_SCALE 64
  52
  53 static const uint8_t obmc_linear32[1024] = {
  54   0,  0,  0,  0,  4,  4,  4,  4,  4,  4,  4,  4,  8,  8,  8,  8,  8,  8,  8,  8,  4,  4,  4,  4,  4,  4,  4,  4,  0,  0,  0,  0,
  55   0,  4,  4,  4,  8,  8,  8, 12, 12, 16, 16, 16, 20, 20, 20, 24, 24, 20, 20, 20, 16, 16, 16, 12, 12,  8,  8,  8,  4,  4,  4,  0,
  56   0,  4,  8,  8, 12, 12, 16, 20, 20, 24, 28, 28, 32, 32, 36, 40, 40, 36, 32, 32, 28, 28, 24, 20, 20, 16, 12, 12,  8,  8,  4,  0,
  57   0,  4,  8, 12, 16, 20, 24, 28, 28, 32, 36, 40, 44, 48, 52, 56, 56, 52, 48, 44, 40, 36, 32, 28, 28, 24, 20, 16, 12,  8,  4,  0,
  58   4,  8, 12, 16, 20, 24, 28, 32, 40, 44, 48, 52, 56, 60, 64, 68, 68, 64, 60, 56, 52, 48, 44, 40, 32, 28, 24, 20, 16, 12,  8,  4,
  59   4,  8, 12, 20, 24, 32, 36, 40, 48, 52, 56, 64, 68, 76, 80, 84, 84, 80, 76, 68, 64, 56, 52, 48, 40, 36, 32, 24, 20, 12,  8,  4,
  60   4,  8, 16, 24, 28, 36, 44, 48, 56, 60, 68, 76, 80, 88, 96,100,100, 96, 88, 80, 76, 68, 60, 56, 48, 44, 36, 28, 24, 16,  8,  4,
  61   4, 12, 20, 28, 32, 40, 48, 56, 64, 72, 80, 88, 92,100,108,116,116,108,100, 92, 88, 80, 72, 64, 56, 48, 40, 32, 28, 20, 12,  4,
  62   4, 12, 20, 28, 40, 48, 56, 64, 72, 80, 88, 96,108,116,124,132,132,124,116,108, 96, 88, 80, 72, 64, 56, 48, 40, 28, 20, 12,  4,
  63   4, 16, 24, 32, 44, 52, 60, 72, 80, 92,100,108,120,128,136,148,148,136,128,120,108,100, 92, 80, 72, 60, 52, 44, 32, 24, 16,  4,
  64   4, 16, 28, 36, 48, 56, 68, 80, 88,100,112,120,132,140,152,164,164,152,140,132,120,112,100, 88, 80, 68, 56, 48, 36, 28, 16,  4,
  65   4, 16, 28, 40, 52, 64, 76, 88, 96,108,120,132,144,156,168,180,180,168,156,144,132,120,108, 96, 88, 76, 64, 52, 40, 28, 16,  4,
  66   8, 20, 32, 44, 56, 68, 80, 92,108,120,132,144,156,168,180,192,192,180,168,156,144,132,120,108, 92, 80, 68, 56, 44, 32, 20,  8,
  67   8, 20, 32, 48, 60, 76, 88,100,116,128,140,156,168,184,196,208,208,196,184,168,156,140,128,116,100, 88, 76, 60, 48, 32, 20,  8,
  68   8, 20, 36, 52, 64, 80, 96,108,124,136,152,168,180,196,212,224,224,212,196,180,168,152,136,124,108, 96, 80, 64, 52, 36, 20,  8,
  69   8, 24, 40, 56, 68, 84,100,116,132,148,164,180,192,208,224,240,240,224,208,192,180,164,148,132,116,100, 84, 68, 56, 40, 24,  8,
  70   8, 24, 40, 56, 68, 84,100,116,132,148,164,180,192,208,224,240,240,224,208,192,180,164,148,132,116,100, 84, 68, 56, 40, 24,  8,
  71   8, 20, 36, 52, 64, 80, 96,108,124,136,152,168,180,196,212,224,224,212,196,180,168,152,136,124,108, 96, 80, 64, 52, 36, 20,  8,
  72   8, 20, 32, 48, 60, 76, 88,100,116,128,140,156,168,184,196,208,208,196,184,168,156,140,128,116,100, 88, 76, 60, 48, 32, 20,  8,
  73   8, 20, 32, 44, 56, 68, 80, 92,108,120,132,144,156,168,180,192,192,180,168,156,144,132,120,108, 92, 80, 68, 56, 44, 32, 20,  8,
  74   4, 16, 28, 40, 52, 64, 76, 88, 96,108,120,132,144,156,168,180,180,168,156,144,132,120,108, 96, 88, 76, 64, 52, 40, 28, 16,  4,
  75   4, 16, 28, 36, 48, 56, 68, 80, 88,100,112,120,132,140,152,164,164,152,140,132,120,112,100, 88, 80, 68, 56, 48, 36, 28, 16,  4,
  76   4, 16, 24, 32, 44, 52, 60, 72, 80, 92,100,108,120,128,136,148,148,136,128,120,108,100, 92, 80, 72, 60, 52, 44, 32, 24, 16,  4,
  77   4, 12, 20, 28, 40, 48, 56, 64, 72, 80, 88, 96,108,116,124,132,132,124,116,108, 96, 88, 80, 72, 64, 56, 48, 40, 28, 20, 12,  4,
  78   4, 12, 20, 28, 32, 40, 48, 56, 64, 72, 80, 88, 92,100,108,116,116,108,100, 92, 88, 80, 72, 64, 56, 48, 40, 32, 28, 20, 12,  4,
  79   4,  8, 16, 24, 28, 36, 44, 48, 56, 60, 68, 76, 80, 88, 96,100,100, 96, 88, 80, 76, 68, 60, 56, 48, 44, 36, 28, 24, 16,  8,  4,
  80   4,  8, 12, 20, 24, 32, 36, 40, 48, 52, 56, 64, 68, 76, 80, 84, 84, 80, 76, 68, 64, 56, 52, 48, 40, 36, 32, 24, 20, 12,  8,  4,
  81   4,  8, 12, 16, 20, 24, 28, 32, 40, 44, 48, 52, 56, 60, 64, 68, 68, 64, 60, 56, 52, 48, 44, 40, 32, 28, 24, 20, 16, 12,  8,  4,
  82   0,  4,  8, 12, 16, 20, 24, 28, 28, 32, 36, 40, 44, 48, 52, 56, 56, 52, 48, 44, 40, 36, 32, 28, 28, 24, 20, 16, 12,  8,  4,  0,
  83   0,  4,  8,  8, 12, 12, 16, 20, 20, 24, 28, 28, 32, 32, 36, 40, 40, 36, 32, 32, 28, 28, 24, 20, 20, 16, 12, 12,  8,  8,  4,  0,
  84   0,  4,  4,  4,  8,  8,  8, 12, 12, 16, 16, 16, 20, 20, 20, 24, 24, 20, 20, 20, 16, 16, 16, 12, 12,  8,  8,  8,  4,  4,  4,  0,
  85   0,  0,  0,  0,  4,  4,  4,  4,  4,  4,  4,  4,  8,  8,  8,  8,  8,  8,  8,  8,  4,  4,  4,  4,  4,  4,  4,  4,  0,  0,  0,  0,
  86 };
  87
  88 static const uint8_t obmc_linear16[256] = {
  89   0,  4,  4,  8,  8, 12, 12, 16, 16, 12, 12,  8,  8,  4,  4,  0,
  90   4,  8, 16, 20, 28, 32, 40, 44, 44, 40, 32, 28, 20, 16,  8,  4,
  91   4, 16, 24, 36, 44, 56, 64, 76, 76, 64, 56, 44, 36, 24, 16,  4,
  92   8, 20, 36, 48, 64, 76, 92,104,104, 92, 76, 64, 48, 36, 20,  8,
  93   8, 28, 44, 64, 80,100,116,136,136,116,100, 80, 64, 44, 28,  8,
  94  12, 32, 56, 76,100,120,144,164,164,144,120,100, 76, 56, 32, 12,
  95  12, 40, 64, 92,116,144,168,196,196,168,144,116, 92, 64, 40, 12,
  96  16, 44, 76,104,136,164,196,224,224,196,164,136,104, 76, 44, 16,
  97  16, 44, 76,104,136,164,196,224,224,196,164,136,104, 76, 44, 16,
  98  12, 40, 64, 92,116,144,168,196,196,168,144,116, 92, 64, 40, 12,
  99  12, 32, 56, 76,100,120,144,164,164,144,120,100, 76, 56, 32, 12,
 100   8, 28, 44, 64, 80,100,116,136,136,116,100, 80, 64, 44, 28,  8,
 101   8, 20, 36, 48, 64, 76, 92,104,104, 92, 76, 64, 48, 36, 20,  8,
 102   4, 16, 24, 36, 44, 56, 64, 76, 76, 64, 56, 44, 36, 24, 16,  4,
 103   4,  8, 16, 20, 28, 32, 40, 44, 44, 40, 32, 28, 20, 16,  8,  4,
 104   0,  4,  4,  8,  8, 12, 12, 16, 16, 12, 12,  8,  8,  4,  4,  0,
 105 };
 106
 107 static const uint8_t obmc_linear8[64] = {
 108   4, 12, 20, 28, 28, 20, 12,  4,
 109  12, 36, 60, 84, 84, 60, 36, 12,
 110  20, 60,100,140,140,100, 60, 20,
 111  28, 84,140,196,196,140, 84, 28,
 112  28, 84,140,196,196,140, 84, 28,
 113  20, 60,100,140,140,100, 60, 20,
 114  12, 36, 60, 84, 84, 60, 36, 12,
 115   4, 12, 20, 28, 28, 20, 12,  4,
 116 };
 117
 118 static const uint8_t obmc_linear4[16] = {
 119  16, 48, 48, 16,
 120  48,144,144, 48,
 121  48,144,144, 48,
 122  16, 48, 48, 16,
 123 };
 124
 125 static const uint8_t * const obmc_tab_linear[4]= {
 126     obmc_linear32, obmc_linear16, obmc_linear8, obmc_linear4
 127 };
 128
 129 enum MIMode {
 130     MI_MODE_DUP         = 0,
 131     MI_MODE_BLEND       = 1,
 132     MI_MODE_MCI         = 2,
 133 };
 134
 135 typedef struct Cluster {
 136     int64_t sum[2];
 137     int nb;
 138 } Cluster;
 139
 140 typedef struct Block {
 141     int16_t mvs[2][2];
 142     int cid;
 143     uint64_t sbad;
 144     int sb;
 145     struct Block *subs;
 146 } Block;
 147
 148 typedef struct PixelMVS {
 149     int16_t mvs[NB_PIXEL_MVS][2];
 150 } PixelMVS;
 151
 152 typedef struct PixelWeights {
 153     uint32_t weights[NB_PIXEL_MVS];
 154 } PixelWeights;
 155
 156 typedef struct PixelRefs {
 157     int8_t refs[NB_PIXEL_MVS];
 158     int nb;
 159 } PixelRefs;
 160
 161 typedef struct Frame {
 162     AVFrame *avf;
 163     Block *blocks;
 164 } Frame;
 165
 166 typedef struct MIContext {
 167     const AVClass *class;
 168     AVMotionEstContext me_ctx;
 169     AVRational frame_rate;
 170     enum MIMode mi_mode;
 171     int mc_mode;
 172     int me_mode;
 173     int me_method;
 174     int mb_size;
 175     int search_param;
 176     int vsbmc;
 177
 178     Frame frames[NB_FRAMES];
 179     Cluster clusters[NB_CLUSTERS];
 180     Block *int_blocks;
 181     PixelMVS *pixel_mvs;
 182     PixelWeights *pixel_weights;
 183     PixelRefs *pixel_refs;
 184     int (*mv_table[3])[2][2];
 185     int64_t out_pts;
 186     int b_width, b_height, b_count;
 187     int log2_mb_size;
 188
 189     int scd_method;
 190     int scene_changed;
 191     ff_scene_sad_fn sad;
 192     double prev_mafd;
 193     double scd_threshold;
 194
 195     int log2_chroma_w;
 196     int log2_chroma_h;
 197     int nb_planes;
 198 } MIContext;
 199
 200 #define OFFSET(x) offsetof(MIContext, x)
 201 #define FLAGS AV_OPT_FLAG_VIDEO_PARAM|AV_OPT_FLAG_FILTERING_PARAM
 202 #define CONST(name, help, val, unit) { name, help, 0, AV_OPT_TYPE_CONST, {.i64=val}, 0, 0, FLAGS, unit }
 203
 204 static const AVOption minterpolate_options[] = {
 205     { "fps", "output's frame rate", OFFSET(frame_rate), AV_OPT_TYPE_VIDEO_RATE, {.str = "60"}, 0, INT_MAX, FLAGS },
 206     { "mi_mode", "motion interpolation mode", OFFSET(mi_mode), AV_OPT_TYPE_INT, {.i64 = MI_MODE_MCI}, MI_MODE_DUP, MI_MODE_MCI, FLAGS, "mi_mode" },
 207         CONST("dup",    "duplicate frames",                     MI_MODE_DUP,            "mi_mode"),
 208         CONST("blend",  "blend frames",                         MI_MODE_BLEND,          "mi_mode"),
 209         CONST("mci",    "motion compensated interpolation",     MI_MODE_MCI,            "mi_mode"),
 210     { "mc_mode", "motion compensation mode", OFFSET(mc_mode), AV_OPT_TYPE_INT, {.i64 = MC_MODE_OBMC}, MC_MODE_OBMC, MC_MODE_AOBMC, FLAGS, "mc_mode" },
 211         CONST("obmc",   "overlapped block motion compensation", MC_MODE_OBMC,           "mc_mode"),
 212         CONST("aobmc",  "adaptive overlapped block motion compensation", MC_MODE_AOBMC, "mc_mode"),
 213     { "me_mode", "motion estimation mode", OFFSET(me_mode), AV_OPT_TYPE_INT, {.i64 = ME_MODE_BILAT}, ME_MODE_BIDIR, ME_MODE_BILAT, FLAGS, "me_mode" },
 214         CONST("bidir",  "bidirectional motion estimation",      ME_MODE_BIDIR,          "me_mode"),
 215         CONST("bilat",  "bilateral motion estimation",          ME_MODE_BILAT,          "me_mode"),
 216     { "me", "motion estimation method", OFFSET(me_method), AV_OPT_TYPE_INT, {.i64 = AV_ME_METHOD_EPZS}, AV_ME_METHOD_ESA, AV_ME_METHOD_UMH, FLAGS, "me" },
 217         CONST("esa",    "exhaustive search",                    AV_ME_METHOD_ESA,       "me"),
 218         CONST("tss",    "three step search",                    AV_ME_METHOD_TSS,       "me"),
 219         CONST("tdls",   "two dimensional logarithmic search",   AV_ME_METHOD_TDLS,      "me"),
 220         CONST("ntss",   "new three step search",                AV_ME_METHOD_NTSS,      "me"),
 221         CONST("fss",    "four step search",                     AV_ME_METHOD_FSS,       "me"),
 222         CONST("ds",     "diamond search",                       AV_ME_METHOD_DS,        "me"),
 223         CONST("hexbs",  "hexagon-based search",                 AV_ME_METHOD_HEXBS,     "me"),
 224         CONST("epzs",   "enhanced predictive zonal search",     AV_ME_METHOD_EPZS,      "me"),
 225         CONST("umh",    "uneven multi-hexagon search",          AV_ME_METHOD_UMH,       "me"),
 226     { "mb_size", "macroblock size", OFFSET(mb_size), AV_OPT_TYPE_INT, {.i64 = 16}, 4, 16, FLAGS },
 227     { "search_param", "search parameter", OFFSET(search_param), AV_OPT_TYPE_INT, {.i64 = 32}, 4, INT_MAX, FLAGS },
 228     { "vsbmc", "variable-size block motion compensation", OFFSET(vsbmc), AV_OPT_TYPE_INT, {.i64 = 0}, 0, 1, FLAGS },
 229     { "scd", "scene change detection method", OFFSET(scd_method), AV_OPT_TYPE_INT, {.i64 = SCD_METHOD_FDIFF}, SCD_METHOD_NONE, SCD_METHOD_FDIFF, FLAGS, "scene" },
 230         CONST("none",   "disable detection",                    SCD_METHOD_NONE,        "scene"),
 231         CONST("fdiff",  "frame difference",                     SCD_METHOD_FDIFF,       "scene"),
 232     { "scd_threshold", "scene change threshold", OFFSET(scd_threshold), AV_OPT_TYPE_DOUBLE, {.dbl = 5.0}, 0, 100.0, FLAGS },
 233     { NULL }
 234 };
 235
 236 AVFILTER_DEFINE_CLASS(minterpolate);
 237
 238 static int query_formats(AVFilterContext *ctx)
 239 {
 240     static const enum AVPixelFormat pix_fmts[] = {
 241         AV_PIX_FMT_YUV410P, AV_PIX_FMT_YUV411P,
 242         AV_PIX_FMT_YUV420P, AV_PIX_FMT_YUV422P,
 243         AV_PIX_FMT_YUV440P, AV_PIX_FMT_YUV444P,
 244         AV_PIX_FMT_YUVJ444P, AV_PIX_FMT_YUVJ440P,
 245         AV_PIX_FMT_YUVJ422P, AV_PIX_FMT_YUVJ420P,
 246         AV_PIX_FMT_YUVJ411P,
 247         AV_PIX_FMT_YUVA420P, AV_PIX_FMT_YUVA422P, AV_PIX_FMT_YUVA444P,
 248         AV_PIX_FMT_GRAY8,
 249         AV_PIX_FMT_NONE
 250     };
 251
 252     AVFilterFormats *fmts_list = ff_make_format_list(pix_fmts);
 253     if (!fmts_list)
 254         return AVERROR(ENOMEM);
 255     return ff_set_common_formats(ctx, fmts_list);
 256 }
 257
 258 static uint64_t get_sbad(AVMotionEstContext *me_ctx, int x, int y, int x_mv, int y_mv)
 259 {
 260     uint8_t *data_cur = me_ctx->data_cur;
 261     uint8_t *data_next = me_ctx->data_ref;
 262     int linesize = me_ctx->linesize;
 263     int mv_x1 = x_mv - x;
 264     int mv_y1 = y_mv - y;
 265     int mv_x, mv_y, i, j;
 266     uint64_t sbad = 0;
 267
 268     x = av_clip(x, me_ctx->x_min, me_ctx->x_max);
 269     y = av_clip(y, me_ctx->y_min, me_ctx->y_max);
 270     mv_x = av_clip(x_mv - x, -FFMIN(x - me_ctx->x_min, me_ctx->x_max - x), FFMIN(x - me_ctx->x_min, me_ctx->x_max - x));
 271     mv_y = av_clip(y_mv - y, -FFMIN(y - me_ctx->y_min, me_ctx->y_max - y), FFMIN(y - me_ctx->y_min, me_ctx->y_max - y));
 272
 273     data_cur += (y + mv_y) * linesize;
 274     data_next += (y - mv_y) * linesize;
 275
 276     for (j = 0; j < me_ctx->mb_size; j++)
 277         for (i = 0; i < me_ctx->mb_size; i++)
 278             sbad += FFABS(data_cur[x + mv_x + i + j * linesize] - data_next[x - mv_x + i + j * linesize]);
 279
 280     return sbad + (FFABS(mv_x1 - me_ctx->pred_x) + FFABS(mv_y1 - me_ctx->pred_y)) * COST_PRED_SCALE;
 281 }
 282
 283 static uint64_t get_sbad_ob(AVMotionEstContext *me_ctx, int x, int y, int x_mv, int y_mv)
 284 {
 285     uint8_t *data_cur = me_ctx->data_cur;
 286     uint8_t *data_next = me_ctx->data_ref;
 287     int linesize = me_ctx->linesize;
 288     int x_min = me_ctx->x_min + me_ctx->mb_size / 2;
 289     int x_max = me_ctx->x_max - me_ctx->mb_size / 2;
 290     int y_min = me_ctx->y_min + me_ctx->mb_size / 2;
 291     int y_max = me_ctx->y_max - me_ctx->mb_size / 2;
 292     int mv_x1 = x_mv - x;
 293     int mv_y1 = y_mv - y;
 294     int mv_x, mv_y, i, j;
 295     uint64_t sbad = 0;
 296
 297     x = av_clip(x, x_min, x_max);
 298     y = av_clip(y, y_min, y_max);
 299     mv_x = av_clip(x_mv - x, -FFMIN(x - x_min, x_max - x), FFMIN(x - x_min, x_max - x));
 300     mv_y = av_clip(y_mv - y, -FFMIN(y - y_min, y_max - y), FFMIN(y - y_min, y_max - y));
 301
 302     for (j = -me_ctx->mb_size / 2; j < me_ctx->mb_size * 3 / 2; j++)
 303         for (i = -me_ctx->mb_size / 2; i < me_ctx->mb_size * 3 / 2; i++)
 304             sbad += FFABS(data_cur[x + mv_x + i + (y + mv_y + j) * linesize] - data_next[x - mv_x + i + (y - mv_y + j) * linesize]);
 305
 306     return sbad + (FFABS(mv_x1 - me_ctx->pred_x) + FFABS(mv_y1 - me_ctx->pred_y)) * COST_PRED_SCALE;
 307 }
 308
 309 static uint64_t get_sad_ob(AVMotionEstContext *me_ctx, int x, int y, int x_mv, int y_mv)
 310 {
 311     uint8_t *data_ref = me_ctx->data_ref;
 312     uint8_t *data_cur = me_ctx->data_cur;
 313     int linesize = me_ctx->linesize;
 314     int x_min = me_ctx->x_min + me_ctx->mb_size / 2;
 315     int x_max = me_ctx->x_max - me_ctx->mb_size / 2;
 316     int y_min = me_ctx->y_min + me_ctx->mb_size / 2;
 317     int y_max = me_ctx->y_max - me_ctx->mb_size / 2;
 318     int mv_x = x_mv - x;
 319     int mv_y = y_mv - y;
 320     int i, j;
 321     uint64_t sad = 0;
 322
 323     x = av_clip(x, x_min, x_max);
 324     y = av_clip(y, y_min, y_max);
 325     x_mv = av_clip(x_mv, x_min, x_max);
 326     y_mv = av_clip(y_mv, y_min, y_max);
 327
 328     for (j = -me_ctx->mb_size / 2; j < me_ctx->mb_size * 3 / 2; j++)
 329         for (i = -me_ctx->mb_size / 2; i < me_ctx->mb_size * 3 / 2; i++)
 330             sad += FFABS(data_ref[x_mv + i + (y_mv + j) * linesize] - data_cur[x + i + (y + j) * linesize]);
 331
 332     return sad + (FFABS(mv_x - me_ctx->pred_x) + FFABS(mv_y - me_ctx->pred_y)) * COST_PRED_SCALE;
 333 }
 334
 335 static int config_input(AVFilterLink *inlink)
 336 {
 337     MIContext *mi_ctx = inlink->dst->priv;
 338     AVMotionEstContext *me_ctx = &mi_ctx->me_ctx;
 339     const AVPixFmtDescriptor *desc = av_pix_fmt_desc_get(inlink->format);
 340     const int height = inlink->h;
 341     const int width  = inlink->w;
 342     int i, ret = 0;
 343
 344     mi_ctx->log2_chroma_h = desc->log2_chroma_h;
 345     mi_ctx->log2_chroma_w = desc->log2_chroma_w;
 346
 347     mi_ctx->nb_planes = av_pix_fmt_count_planes(inlink->format);
 348
 349     mi_ctx->log2_mb_size = av_ceil_log2_c(mi_ctx->mb_size);
 350     mi_ctx->mb_size = 1 << mi_ctx->log2_mb_size;
 351
 352     mi_ctx->b_width  = width >> mi_ctx->log2_mb_size;
 353     mi_ctx->b_height = height >> mi_ctx->log2_mb_size;
 354     mi_ctx->b_count = mi_ctx->b_width * mi_ctx->b_height;
 355
 356     for (i = 0; i < NB_FRAMES; i++) {
 357         Frame *frame = &mi_ctx->frames[i];
 358         frame->blocks = av_mallocz_array(mi_ctx->b_count, sizeof(Block));
 359         if (!frame->blocks)
 360             return AVERROR(ENOMEM);
 361     }
 362
 363     if (mi_ctx->mi_mode == MI_MODE_MCI) {
 364         mi_ctx->pixel_mvs = av_mallocz_array(width * height, sizeof(PixelMVS));
 365         mi_ctx->pixel_weights = av_mallocz_array(width * height, sizeof(PixelWeights));
 366         mi_ctx->pixel_refs = av_mallocz_array(width * height, sizeof(PixelRefs));
 367         if (!mi_ctx->pixel_mvs || !mi_ctx->pixel_weights || !mi_ctx->pixel_refs) {
 368             ret = AVERROR(ENOMEM);
 369             goto fail;
 370         }
 371
 372         if (mi_ctx->me_mode == ME_MODE_BILAT)
 373             if (!(mi_ctx->int_blocks = av_mallocz_array(mi_ctx->b_count, sizeof(Block))))
 374                 return AVERROR(ENOMEM);
 375
 376         if (mi_ctx->me_method == AV_ME_METHOD_EPZS) {
 377             for (i = 0; i < 3; i++) {
 378                 mi_ctx->mv_table[i] = av_mallocz_array(mi_ctx->b_count, sizeof(*mi_ctx->mv_table[0]));
 379                 if (!mi_ctx->mv_table[i])
 380                     return AVERROR(ENOMEM);
 381             }
 382         }
 383     }
 384
 385     if (mi_ctx->scd_method == SCD_METHOD_FDIFF) {
 386         mi_ctx->sad = ff_scene_sad_get_fn(8);
 387         if (!mi_ctx->sad)
 388             return AVERROR(EINVAL);
 389     }
 390
 391     ff_me_init_context(me_ctx, mi_ctx->mb_size, mi_ctx->search_param, width, height, 0, (mi_ctx->b_width - 1) << mi_ctx->log2_mb_size, 0, (mi_ctx->b_height - 1) << mi_ctx->log2_mb_size);
 392
 393     if (mi_ctx->me_mode == ME_MODE_BIDIR)
 394         me_ctx->get_cost = &get_sad_ob;
 395     else if (mi_ctx->me_mode == ME_MODE_BILAT)
 396         me_ctx->get_cost = &get_sbad_ob;
 397
 398     return 0;
 399 fail:
 400     for (i = 0; i < NB_FRAMES; i++)
 401         av_freep(&mi_ctx->frames[i].blocks);
 402     av_freep(&mi_ctx->pixel_mvs);
 403     av_freep(&mi_ctx->pixel_weights);
 404     av_freep(&mi_ctx->pixel_refs);
 405     return ret;
 406 }
 407
 408 static int config_output(AVFilterLink *outlink)
 409 {
 410     MIContext *mi_ctx = outlink->src->priv;
 411
 412     outlink->frame_rate = mi_ctx->frame_rate;
 413     outlink->time_base  = av_inv_q(mi_ctx->frame_rate);
 414
 415     return 0;
 416 }
 417
 418 #define ADD_PRED(preds, px, py)\
 419     do {\
 420         preds.mvs[preds.nb][0] = px;\
 421         preds.mvs[preds.nb][1] = py;\
 422         preds.nb++;\
 423     } while(0)
 424
 425 static void search_mv(MIContext *mi_ctx, Block *blocks, int mb_x, int mb_y, int dir)
 426 {
 427     AVMotionEstContext *me_ctx = &mi_ctx->me_ctx;
 428     AVMotionEstPredictor *preds = me_ctx->preds;
 429     Block *block = &blocks[mb_x + mb_y * mi_ctx->b_width];
 430
 431     const int x_mb = mb_x << mi_ctx->log2_mb_size;
 432     const int y_mb = mb_y << mi_ctx->log2_mb_size;
 433     const int mb_i = mb_x + mb_y * mi_ctx->b_width;
 434     int mv[2] = {x_mb, y_mb};
 435
 436     switch (mi_ctx->me_method) {
 437         case AV_ME_METHOD_ESA:
 438             ff_me_search_esa(me_ctx, x_mb, y_mb, mv);
 439             break;
 440         case AV_ME_METHOD_TSS:
 441             ff_me_search_tss(me_ctx, x_mb, y_mb, mv);
 442             break;
 443         case AV_ME_METHOD_TDLS:
 444             ff_me_search_tdls(me_ctx, x_mb, y_mb, mv);
 445             break;
 446         case AV_ME_METHOD_NTSS:
 447             ff_me_search_ntss(me_ctx, x_mb, y_mb, mv);
 448             break;
 449         case AV_ME_METHOD_FSS:
 450             ff_me_search_fss(me_ctx, x_mb, y_mb, mv);
 451             break;
 452         case AV_ME_METHOD_DS:
 453             ff_me_search_ds(me_ctx, x_mb, y_mb, mv);
 454             break;
 455         case AV_ME_METHOD_HEXBS:
 456             ff_me_search_hexbs(me_ctx, x_mb, y_mb, mv);
 457             break;
 458         case AV_ME_METHOD_EPZS:
 459
 460             preds[0].nb = 0;
 461             preds[1].nb = 0;
 462
 463             ADD_PRED(preds[0], 0, 0);
 464
 465             //left mb in current frame
 466             if (mb_x > 0)
 467                 ADD_PRED(preds[0], mi_ctx->mv_table[0][mb_i - 1][dir][0], mi_ctx->mv_table[0][mb_i - 1][dir][1]);
 468
 469             //top mb in current frame
 470             if (mb_y > 0)
 471                 ADD_PRED(preds[0], mi_ctx->mv_table[0][mb_i - mi_ctx->b_width][dir][0], mi_ctx->mv_table[0][mb_i - mi_ctx->b_width][dir][1]);
 472
 473             //top-right mb in current frame
 474             if (mb_y > 0 && mb_x + 1 < mi_ctx->b_width)
 475                 ADD_PRED(preds[0], mi_ctx->mv_table[0][mb_i - mi_ctx->b_width + 1][dir][0], mi_ctx->mv_table[0][mb_i - mi_ctx->b_width + 1][dir][1]);
 476
 477             //median predictor
 478             if (preds[0].nb == 4) {
 479                 me_ctx->pred_x = mid_pred(preds[0].mvs[1][0], preds[0].mvs[2][0], preds[0].mvs[3][0]);
 480                 me_ctx->pred_y = mid_pred(preds[0].mvs[1][1], preds[0].mvs[2][1], preds[0].mvs[3][1]);
 481             } else if (preds[0].nb == 3) {
 482                 me_ctx->pred_x = mid_pred(0, preds[0].mvs[1][0], preds[0].mvs[2][0]);
 483                 me_ctx->pred_y = mid_pred(0, preds[0].mvs[1][1], preds[0].mvs[2][1]);
 484             } else if (preds[0].nb == 2) {
 485                 me_ctx->pred_x = preds[0].mvs[1][0];
 486                 me_ctx->pred_y = preds[0].mvs[1][1];
 487             } else {
 488                 me_ctx->pred_x = 0;
 489                 me_ctx->pred_y = 0;
 490             }
 491
 492             //collocated mb in prev frame
 493             ADD_PRED(preds[0], mi_ctx->mv_table[1][mb_i][dir][0], mi_ctx->mv_table[1][mb_i][dir][1]);
 494
 495             //accelerator motion vector of collocated block in prev frame
 496             ADD_PRED(preds[1], mi_ctx->mv_table[1][mb_i][dir][0] + (mi_ctx->mv_table[1][mb_i][dir][0] - mi_ctx->mv_table[2][mb_i][dir][0]),
 497                                mi_ctx->mv_table[1][mb_i][dir][1] + (mi_ctx->mv_table[1][mb_i][dir][1] - mi_ctx->mv_table[2][mb_i][dir][1]));
 498
 499             //left mb in prev frame
 500             if (mb_x > 0)
 501                 ADD_PRED(preds[1], mi_ctx->mv_table[1][mb_i - 1][dir][0], mi_ctx->mv_table[1][mb_i - 1][dir][1]);
 502
 503             //top mb in prev frame
 504             if (mb_y > 0)
 505                 ADD_PRED(preds[1], mi_ctx->mv_table[1][mb_i - mi_ctx->b_width][dir][0], mi_ctx->mv_table[1][mb_i - mi_ctx->b_width][dir][1]);
 506
 507             //right mb in prev frame
 508             if (mb_x + 1 < mi_ctx->b_width)
 509                 ADD_PRED(preds[1], mi_ctx->mv_table[1][mb_i + 1][dir][0], mi_ctx->mv_table[1][mb_i + 1][dir][1]);
 510
 511             //bottom mb in prev frame
 512             if (mb_y + 1 < mi_ctx->b_height)
 513                 ADD_PRED(preds[1], mi_ctx->mv_table[1][mb_i + mi_ctx->b_width][dir][0], mi_ctx->mv_table[1][mb_i + mi_ctx->b_width][dir][1]);
 514
 515             ff_me_search_epzs(me_ctx, x_mb, y_mb, mv);
 516
 517             mi_ctx->mv_table[0][mb_i][dir][0] = mv[0] - x_mb;
 518             mi_ctx->mv_table[0][mb_i][dir][1] = mv[1] - y_mb;
 519
 520             break;
 521         case AV_ME_METHOD_UMH:
 522
 523             preds[0].nb = 0;
 524
 525             ADD_PRED(preds[0], 0, 0);
 526
 527             //left mb in current frame
 528             if (mb_x > 0)
 529                 ADD_PRED(preds[0], blocks[mb_i - 1].mvs[dir][0], blocks[mb_i - 1].mvs[dir][1]);
 530
 531             if (mb_y > 0) {
 532                 //top mb in current frame
 533                 ADD_PRED(preds[0], blocks[mb_i - mi_ctx->b_width].mvs[dir][0], blocks[mb_i - mi_ctx->b_width].mvs[dir][1]);
 534
 535                 //top-right mb in current frame
 536                 if (mb_x + 1 < mi_ctx->b_width)
 537                     ADD_PRED(preds[0], blocks[mb_i - mi_ctx->b_width + 1].mvs[dir][0], blocks[mb_i - mi_ctx->b_width + 1].mvs[dir][1]);
 538                 //top-left mb in current frame
 539                 else if (mb_x > 0)
 540                     ADD_PRED(preds[0], blocks[mb_i - mi_ctx->b_width - 1].mvs[dir][0], blocks[mb_i - mi_ctx->b_width - 1].mvs[dir][1]);
 541             }
 542
 543             //median predictor
 544             if (preds[0].nb == 4) {
 545                 me_ctx->pred_x = mid_pred(preds[0].mvs[1][0], preds[0].mvs[2][0], preds[0].mvs[3][0]);
 546                 me_ctx->pred_y = mid_pred(preds[0].mvs[1][1], preds[0].mvs[2][1], preds[0].mvs[3][1]);
 547             } else if (preds[0].nb == 3) {
 548                 me_ctx->pred_x = mid_pred(0, preds[0].mvs[1][0], preds[0].mvs[2][0]);
 549                 me_ctx->pred_y = mid_pred(0, preds[0].mvs[1][1], preds[0].mvs[2][1]);
 550             } else if (preds[0].nb == 2) {
 551                 me_ctx->pred_x = preds[0].mvs[1][0];
 552                 me_ctx->pred_y = preds[0].mvs[1][1];
 553             } else {
 554                 me_ctx->pred_x = 0;
 555                 me_ctx->pred_y = 0;
 556             }
 557
 558             ff_me_search_umh(me_ctx, x_mb, y_mb, mv);
 559
 560             break;
 561     }
 562
 563     block->mvs[dir][0] = mv[0] - x_mb;
 564     block->mvs[dir][1] = mv[1] - y_mb;
 565 }
 566
 567 static void bilateral_me(MIContext *mi_ctx)
 568 {
 569     Block *block;
 570     int mb_x, mb_y;
 571
 572     for (mb_y = 0; mb_y < mi_ctx->b_height; mb_y++)
 573         for (mb_x = 0; mb_x < mi_ctx->b_width; mb_x++) {
 574             block = &mi_ctx->int_blocks[mb_x + mb_y * mi_ctx->b_width];
 575
 576             block->cid = 0;
 577             block->sb = 0;
 578
 579             block->mvs[0][0] = 0;
 580             block->mvs[0][1] = 0;
 581         }
 582
 583     for (mb_y = 0; mb_y < mi_ctx->b_height; mb_y++)
 584         for (mb_x = 0; mb_x < mi_ctx->b_width; mb_x++)
 585             search_mv(mi_ctx, mi_ctx->int_blocks, mb_x, mb_y, 0);
 586 }
 587
 588 static int var_size_bme(MIContext *mi_ctx, Block *block, int x_mb, int y_mb, int n)
 589 {
 590     AVMotionEstContext *me_ctx = &mi_ctx->me_ctx;
 591     uint64_t cost_sb, cost_old;
 592     int mb_size = me_ctx->mb_size;
 593     int search_param = me_ctx->search_param;
 594     int mv_x, mv_y;
 595     int x, y;
 596     int ret;
 597
 598     me_ctx->mb_size = 1 << n;
 599     cost_old = me_ctx->get_cost(me_ctx, x_mb, y_mb, x_mb + block->mvs[0][0], y_mb + block->mvs[0][1]);
 600     me_ctx->mb_size = mb_size;
 601
 602     if (!cost_old) {
 603         block->sb = 0;
 604         return 0;
 605     }
 606
 607     if (!block->subs) {
 608         block->subs = av_mallocz_array(4, sizeof(Block));
 609         if (!block->subs)
 610             return AVERROR(ENOMEM);
 611     }
 612
 613     block->sb = 1;
 614
 615     for (y = 0; y < 2; y++)
 616         for (x = 0; x < 2; x++) {
 617             Block *sb = &block->subs[x + y * 2];
 618             int mv[2] = {x_mb + block->mvs[0][0], y_mb + block->mvs[0][1]};
 619
 620             me_ctx->mb_size = 1 << (n - 1);
 621             me_ctx->search_param = 2;
 622             me_ctx->pred_x = block->mvs[0][0];
 623             me_ctx->pred_y = block->mvs[0][1];
 624
 625             cost_sb = ff_me_search_ds(&mi_ctx->me_ctx, x_mb + block->mvs[0][0], y_mb + block->mvs[0][1], mv);
 626             mv_x = mv[0] - x_mb;
 627             mv_y = mv[1] - y_mb;
 628
 629             me_ctx->mb_size = mb_size;
 630             me_ctx->search_param = search_param;
 631
 632             if (cost_sb < cost_old / 4) {
 633                 sb->mvs[0][0] = mv_x;
 634                 sb->mvs[0][1] = mv_y;
 635
 636                 if (n > 1) {
 637                     if (ret = var_size_bme(mi_ctx, sb, x_mb + (x << (n - 1)), y_mb + (y << (n - 1)), n - 1))
 638                         return ret;
 639                 } else
 640                     sb->sb = 0;
 641             } else {
 642                 block->sb = 0;
 643                 return 0;
 644             }
 645         }
 646
 647     return 0;
 648 }
 649
 650 static int cluster_mvs(MIContext *mi_ctx)
 651 {
 652     int changed, c, c_max = 0;
 653     int mb_x, mb_y, x, y;
 654     int mv_x, mv_y, avg_x, avg_y, dx, dy;
 655     int d, ret;
 656     Block *block;
 657     Cluster *cluster, *cluster_new;
 658
 659     do {
 660         changed = 0;
 661         for (mb_y = 0; mb_y < mi_ctx->b_height; mb_y++)
 662             for (mb_x = 0; mb_x < mi_ctx->b_width; mb_x++) {
 663                 block = &mi_ctx->int_blocks[mb_x + mb_y * mi_ctx->b_width];
 664                 c = block->cid;
 665                 cluster = &mi_ctx->clusters[c];
 666                 mv_x = block->mvs[0][0];
 667                 mv_y = block->mvs[0][1];
 668
 669                 if (cluster->nb < 2)
 670                     continue;
 671
 672                 avg_x = cluster->sum[0] / cluster->nb;
 673                 avg_y = cluster->sum[1] / cluster->nb;
 674                 dx = avg_x - mv_x;
 675                 dy = avg_y - mv_y;
 676
 677                 if (FFABS(dx) > CLUSTER_THRESHOLD || FFABS(dy) > CLUSTER_THRESHOLD) {
 678
 679                     for (d = 1; d < 5; d++)
 680                         for (y = FFMAX(mb_y - d, 0); y < FFMIN(mb_y + d + 1, mi_ctx->b_height); y++)
 681                             for (x = FFMAX(mb_x - d, 0); x < FFMIN(mb_x + d + 1, mi_ctx->b_width); x++) {
 682                                 Block *nb = &mi_ctx->int_blocks[x + y * mi_ctx->b_width];
 683                                 if (nb->cid > block->cid) {
 684                                     if (nb->cid < c || c == block->cid)
 685                                         c = nb->cid;
 686                                 }
 687                             }
 688
 689                     if (c == block->cid)
 690                         c = c_max + 1;
 691
 692                     if (c >= NB_CLUSTERS) {
 693                         continue;
 694                     }
 695
 696                     cluster_new = &mi_ctx->clusters[c];
 697                     cluster_new->sum[0] += mv_x;
 698                     cluster_new->sum[1] += mv_y;
 699                     cluster->sum[0] -= mv_x;
 700                     cluster->sum[1] -= mv_y;
 701                     cluster_new->nb++;
 702                     cluster->nb--;
 703
 704                     c_max = FFMAX(c_max, c);
 705                     block->cid = c;
 706
 707                     changed = 1;
 708                 }
 709             }
 710     } while (changed);
 711
 712     /* find boundaries */
 713     for (mb_y = 0; mb_y < mi_ctx->b_height; mb_y++)
 714         for (mb_x = 0; mb_x < mi_ctx->b_width; mb_x++) {
 715             block = &mi_ctx->int_blocks[mb_x + mb_y * mi_ctx->b_width];
 716             for (y = FFMAX(mb_y - 1, 0); y < FFMIN(mb_y + 2, mi_ctx->b_height); y++)
 717                 for (x = FFMAX(mb_x - 1, 0); x < FFMIN(mb_x + 2, mi_ctx->b_width); x++) {
 718                     dx = x - mb_x;
 719                     dy = y - mb_y;
 720
 721                     if ((x - mb_x) && (y - mb_y) || !dx && !dy)
 722                         continue;
 723
 724                     if (!mb_x || !mb_y || mb_x == mi_ctx->b_width - 1 || mb_y == mi_ctx->b_height - 1)
 725                         continue;
 726
 727                     if (block->cid != mi_ctx->int_blocks[x + y * mi_ctx->b_width].cid) {
 728                         if (!dx && block->cid == mi_ctx->int_blocks[x + (mb_y - dy) * mi_ctx->b_width].cid ||
 729                             !dy && block->cid == mi_ctx->int_blocks[(mb_x - dx) + y * mi_ctx->b_width].cid) {
 730                             if (ret = var_size_bme(mi_ctx, block, mb_x << mi_ctx->log2_mb_size, mb_y << mi_ctx->log2_mb_size, mi_ctx->log2_mb_size))
 731                                 return ret;
 732                         }
 733                     }
 734                 }
 735         }
 736
 737     return 0;
 738 }
 739
 740 static int inject_frame(AVFilterLink *inlink, AVFrame *avf_in)
 741 {
 742     AVFilterContext *ctx = inlink->dst;
 743     MIContext *mi_ctx = ctx->priv;
 744     Frame frame_tmp;
 745     int mb_x, mb_y, dir;
 746
 747     av_frame_free(&mi_ctx->frames[0].avf);
 748     frame_tmp = mi_ctx->frames[0];
 749     memmove(&mi_ctx->frames[0], &mi_ctx->frames[1], sizeof(mi_ctx->frames[0]) * (NB_FRAMES - 1));
 750     mi_ctx->frames[NB_FRAMES - 1] = frame_tmp;
 751     mi_ctx->frames[NB_FRAMES - 1].avf = avf_in;
 752
 753     if (mi_ctx->mi_mode == MI_MODE_MCI) {
 754
 755         if (mi_ctx->me_method == AV_ME_METHOD_EPZS) {
 756             mi_ctx->mv_table[2] = memcpy(mi_ctx->mv_table[2], mi_ctx->mv_table[1], sizeof(*mi_ctx->mv_table[1]) * mi_ctx->b_count);
 757             mi_ctx->mv_table[1] = memcpy(mi_ctx->mv_table[1], mi_ctx->mv_table[0], sizeof(*mi_ctx->mv_table[0]) * mi_ctx->b_count);
 758         }
 759
 760         if (mi_ctx->me_mode == ME_MODE_BIDIR) {
 761
 762             if (mi_ctx->frames[1].avf) {
 763                 for (dir = 0; dir < 2; dir++) {
 764                     mi_ctx->me_ctx.linesize = mi_ctx->frames[2].avf->linesize[0];
 765                     mi_ctx->me_ctx.data_cur = mi_ctx->frames[2].avf->data[0];
 766                     mi_ctx->me_ctx.data_ref = mi_ctx->frames[dir ? 3 : 1].avf->data[0];
 767
 768                     for (mb_y = 0; mb_y < mi_ctx->b_height; mb_y++)
 769                         for (mb_x = 0; mb_x < mi_ctx->b_width; mb_x++)
 770                             search_mv(mi_ctx, mi_ctx->frames[2].blocks, mb_x, mb_y, dir);
 771                 }
 772             }
 773
 774         } else if (mi_ctx->me_mode == ME_MODE_BILAT) {
 775             Block *block;
 776             int i, ret;
 777
 778             if (!mi_ctx->frames[0].avf)
 779                 return 0;
 780
 781             mi_ctx->me_ctx.linesize = mi_ctx->frames[0].avf->linesize[0];
 782             mi_ctx->me_ctx.data_cur = mi_ctx->frames[1].avf->data[0];
 783             mi_ctx->me_ctx.data_ref = mi_ctx->frames[2].avf->data[0];
 784
 785             bilateral_me(mi_ctx);
 786
 787             if (mi_ctx->mc_mode == MC_MODE_AOBMC) {
 788
 789                 for (mb_y = 0; mb_y < mi_ctx->b_height; mb_y++)
 790                     for (mb_x = 0; mb_x < mi_ctx->b_width; mb_x++) {
 791                         int x_mb = mb_x << mi_ctx->log2_mb_size;
 792                         int y_mb = mb_y << mi_ctx->log2_mb_size;
 793                         block = &mi_ctx->int_blocks[mb_x + mb_y * mi_ctx->b_width];
 794
 795                         block->sbad = get_sbad(&mi_ctx->me_ctx, x_mb, y_mb, x_mb + block->mvs[0][0], y_mb + block->mvs[0][1]);
 796                     }
 797             }
 798
 799             if (mi_ctx->vsbmc) {
 800
 801                 for (i = 0; i < NB_CLUSTERS; i++) {
 802                     mi_ctx->clusters[i].sum[0] = 0;
 803                     mi_ctx->clusters[i].sum[1] = 0;
 804                     mi_ctx->clusters[i].nb = 0;
 805                 }
 806
 807                 for (mb_y = 0; mb_y < mi_ctx->b_height; mb_y++)
 808                     for (mb_x = 0; mb_x < mi_ctx->b_width; mb_x++) {
 809                         block = &mi_ctx->int_blocks[mb_x + mb_y * mi_ctx->b_width];
 810
 811                         mi_ctx->clusters[0].sum[0] += block->mvs[0][0];
 812                         mi_ctx->clusters[0].sum[1] += block->mvs[0][1];
 813                     }
 814
 815                 mi_ctx->clusters[0].nb = mi_ctx->b_count;
 816
 817                 if (ret = cluster_mvs(mi_ctx))
 818                     return ret;
 819             }
 820         }
 821     }
 822
 823     return 0;
 824 }
 825
 826 static int detect_scene_change(MIContext *mi_ctx)
 827 {
 828     AVMotionEstContext *me_ctx = &mi_ctx->me_ctx;
 829     uint8_t *p1 = mi_ctx->frames[1].avf->data[0];
 830     ptrdiff_t linesize1 = mi_ctx->frames[1].avf->linesize[0];
 831     uint8_t *p2 = mi_ctx->frames[2].avf->data[0];
 832     ptrdiff_t linesize2 = mi_ctx->frames[2].avf->linesize[0];
 833
 834     if (mi_ctx->scd_method == SCD_METHOD_FDIFF) {
 835         double ret = 0, mafd = HUGE_VAL, diff;
 836         uint64_t sad;
 837         AVDictionaryEntry *e_mafd = NULL;
 838         char *tail = NULL;
 839
 840         e_mafd = av_dict_get(mi_ctx->frames[2].avf->metadata, "lavfi.scd.mafd", NULL, AV_DICT_MATCH_CASE);
 841         if (e_mafd)
 842             mafd = strtod(e_mafd->value, &tail);
 843         if (*tail || mafd == HUGE_VAL) {
 844             mi_ctx->sad(p1, linesize1, p2, linesize2, me_ctx->width, me_ctx->height, &sad);
 845             emms_c();
 846             mafd = (double) sad / (me_ctx->height * me_ctx->width * 3);
 847         }
 848         diff = fabs(mafd - mi_ctx->prev_mafd);
 849         ret  = av_clipf(FFMIN(mafd, diff), 0, 100.0);
 850         mi_ctx->prev_mafd = mafd;
 851
 852         return ret >= mi_ctx->scd_threshold;
 853     }
 854
 855     return 0;
 856 }
 857
 858 #define ADD_PIXELS(b_weight, mv_x, mv_y)\
 859     do {\
 860         if (!b_weight || pixel_refs->nb + 1 >= NB_PIXEL_MVS)\
 861             continue;\
 862         pixel_refs->refs[pixel_refs->nb] = 1;\
 863         pixel_weights->weights[pixel_refs->nb] = b_weight * (ALPHA_MAX - alpha);\
 864         pixel_mvs->mvs[pixel_refs->nb][0] = av_clip((mv_x * alpha) / ALPHA_MAX, x_min, x_max);\
 865         pixel_mvs->mvs[pixel_refs->nb][1] = av_clip((mv_y * alpha) / ALPHA_MAX, y_min, y_max);\
 866         pixel_refs->nb++;\
 867         pixel_refs->refs[pixel_refs->nb] = 2;\
 868         pixel_weights->weights[pixel_refs->nb] = b_weight * alpha;\
 869         pixel_mvs->mvs[pixel_refs->nb][0] = av_clip(-mv_x * (ALPHA_MAX - alpha) / ALPHA_MAX, x_min, x_max);\
 870         pixel_mvs->mvs[pixel_refs->nb][1] = av_clip(-mv_y * (ALPHA_MAX - alpha) / ALPHA_MAX, y_min, y_max);\
 871         pixel_refs->nb++;\
 872     } while(0)
 873
 874 static void bidirectional_obmc(MIContext *mi_ctx, int alpha)
 875 {
 876     int x, y;
 877     int width = mi_ctx->frames[0].avf->width;
 878     int height = mi_ctx->frames[0].avf->height;
 879     int mb_y, mb_x, dir;
 880
 881     for (y = 0; y < height; y++)
 882         for (x = 0; x < width; x++)
 883             mi_ctx->pixel_refs[x + y * width].nb = 0;
 884
 885     for (dir = 0; dir < 2; dir++)
 886         for (mb_y = 0; mb_y < mi_ctx->b_height; mb_y++)
 887             for (mb_x = 0; mb_x < mi_ctx->b_width; mb_x++) {
 888                 int a = dir ? alpha : (ALPHA_MAX - alpha);
 889                 int mv_x = mi_ctx->frames[2 - dir].blocks[mb_x + mb_y * mi_ctx->b_width].mvs[dir][0];
 890                 int mv_y = mi_ctx->frames[2 - dir].blocks[mb_x + mb_y * mi_ctx->b_width].mvs[dir][1];
 891                 int start_x, start_y;
 892                 int startc_x, startc_y, endc_x, endc_y;
 893
 894                 start_x = (mb_x << mi_ctx->log2_mb_size) - mi_ctx->mb_size / 2 + mv_x * a / ALPHA_MAX;
 895                 start_y = (mb_y << mi_ctx->log2_mb_size) - mi_ctx->mb_size / 2 + mv_y * a / ALPHA_MAX;
 896
 897                 startc_x = av_clip(start_x, 0, width - 1);
 898                 startc_y = av_clip(start_y, 0, height - 1);
 899                 endc_x = av_clip(start_x + (2 << mi_ctx->log2_mb_size), 0, width - 1);
 900                 endc_y = av_clip(start_y + (2 << mi_ctx->log2_mb_size), 0, height - 1);
 901
 902                 if (dir) {
 903                     mv_x = -mv_x;
 904                     mv_y = -mv_y;
 905                 }
 906
 907                 for (y = startc_y; y < endc_y; y++) {
 908                     int y_min = -y;
 909                     int y_max = height - y - 1;
 910                     for (x = startc_x; x < endc_x; x++) {
 911                         int x_min = -x;
 912                         int x_max = width - x - 1;
 913                         int obmc_weight = obmc_tab_linear[4 - mi_ctx->log2_mb_size][(x - start_x) + ((y - start_y) << (mi_ctx->log2_mb_size + 1))];
 914                         PixelMVS *pixel_mvs = &mi_ctx->pixel_mvs[x + y * width];
 915                         PixelWeights *pixel_weights = &mi_ctx->pixel_weights[x + y * width];
 916                         PixelRefs *pixel_refs = &mi_ctx->pixel_refs[x + y * width];
 917
 918                         ADD_PIXELS(obmc_weight, mv_x, mv_y);
 919                     }
 920                 }
 921             }
 922 }
 923
 924 static void set_frame_data(MIContext *mi_ctx, int alpha, AVFrame *avf_out)
 925 {
 926     int x, y, plane;
 927
 928     for (plane = 0; plane < mi_ctx->nb_planes; plane++) {
 929         int width = avf_out->width;
 930         int height = avf_out->height;
 931         int chroma = plane == 1 || plane == 2;
 932
 933         for (y = 0; y < height; y++)
 934             for (x = 0; x < width; x++) {
 935                 int x_mv, y_mv;
 936                 int weight_sum = 0;
 937                 int i, val = 0;
 938                 PixelMVS *pixel_mvs = &mi_ctx->pixel_mvs[x + y * avf_out->width];
 939                 PixelWeights *pixel_weights = &mi_ctx->pixel_weights[x + y * avf_out->width];
 940                 PixelRefs *pixel_refs = &mi_ctx->pixel_refs[x + y * avf_out->width];
 941
 942                 for (i = 0; i < pixel_refs->nb; i++)
 943                     weight_sum += pixel_weights->weights[i];
 944
 945                 if (!weight_sum || !pixel_refs->nb) {
 946                     pixel_weights->weights[0] = ALPHA_MAX - alpha;
 947                     pixel_refs->refs[0] = 1;
 948                     pixel_mvs->mvs[0][0] = 0;
 949                     pixel_mvs->mvs[0][1] = 0;
 950                     pixel_weights->weights[1] = alpha;
 951                     pixel_refs->refs[1] = 2;
 952                     pixel_mvs->mvs[1][0] = 0;
 953                     pixel_mvs->mvs[1][1] = 0;
 954                     pixel_refs->nb = 2;
 955
 956                     weight_sum = ALPHA_MAX;
 957                 }
 958
 959                 for (i = 0; i < pixel_refs->nb; i++) {
 960                     Frame *frame = &mi_ctx->frames[pixel_refs->refs[i]];
 961                     if (chroma) {
 962                         x_mv = (x >> mi_ctx->log2_chroma_w) + pixel_mvs->mvs[i][0] / (1 << mi_ctx->log2_chroma_w);
 963                         y_mv = (y >> mi_ctx->log2_chroma_h) + pixel_mvs->mvs[i][1] / (1 << mi_ctx->log2_chroma_h);
 964                     } else {
 965                         x_mv = x + pixel_mvs->mvs[i][0];
 966                         y_mv = y + pixel_mvs->mvs[i][1];
 967                     }
 968
 969                     val += pixel_weights->weights[i] * frame->avf->data[plane][x_mv + y_mv * frame->avf->linesize[plane]];
 970                 }
 971
 972                 val = ROUNDED_DIV(val, weight_sum);
 973
 974                 if (chroma)
 975                     avf_out->data[plane][(x >> mi_ctx->log2_chroma_w) + (y >> mi_ctx->log2_chroma_h) * avf_out->linesize[plane]] = val;
 976                 else
 977                     avf_out->data[plane][x + y * avf_out->linesize[plane]] = val;
 978             }
 979     }
 980 }
 981
 982 static void var_size_bmc(MIContext *mi_ctx, Block *block, int x_mb, int y_mb, int n, int alpha)
 983 {
 984     int sb_x, sb_y;
 985     int width = mi_ctx->frames[0].avf->width;
 986     int height = mi_ctx->frames[0].avf->height;
 987
 988     for (sb_y = 0; sb_y < 2; sb_y++)
 989         for (sb_x = 0; sb_x < 2; sb_x++) {
 990             Block *sb = &block->subs[sb_x + sb_y * 2];
 991
 992             if (sb->sb)
 993                 var_size_bmc(mi_ctx, sb, x_mb + (sb_x << (n - 1)), y_mb + (sb_y << (n - 1)), n - 1, alpha);
 994             else {
 995                 int x, y;
 996                 int mv_x = sb->mvs[0][0] * 2;
 997                 int mv_y = sb->mvs[0][1] * 2;
 998
 999                 int start_x = x_mb + (sb_x << (n - 1));
1000                 int start_y = y_mb + (sb_y << (n - 1));
1001                 int end_x = start_x + (1 << (n - 1));
1002                 int end_y = start_y + (1 << (n - 1));
1003
1004                 for (y = start_y; y < end_y; y++)  {
1005                     int y_min = -y;
1006                     int y_max = height - y - 1;
1007                     for (x = start_x; x < end_x; x++) {
1008                         int x_min = -x;
1009                         int x_max = width - x - 1;
1010                         PixelMVS *pixel_mvs = &mi_ctx->pixel_mvs[x + y * width];
1011                         PixelWeights *pixel_weights = &mi_ctx->pixel_weights[x + y * width];
1012                         PixelRefs *pixel_refs = &mi_ctx->pixel_refs[x + y * width];
1013
1014                         ADD_PIXELS(PX_WEIGHT_MAX, mv_x, mv_y);
1015                     }
1016                 }
1017             }
1018         }
1019 }
1020
1021 static void bilateral_obmc(MIContext *mi_ctx, Block *block, int mb_x, int mb_y, int alpha)
1022 {
1023     int x, y;
1024     int width = mi_ctx->frames[0].avf->width;
1025     int height = mi_ctx->frames[0].avf->height;
1026
1027     Block *nb;
1028     int nb_x, nb_y;
1029     uint64_t sbads[9];
1030
1031     int mv_x = block->mvs[0][0] * 2;
1032     int mv_y = block->mvs[0][1] * 2;
1033     int start_x, start_y;
1034     int startc_x, startc_y, endc_x, endc_y;
1035
1036     if (mi_ctx->mc_mode == MC_MODE_AOBMC)
1037         for (nb_y = FFMAX(0, mb_y - 1); nb_y < FFMIN(mb_y + 2, mi_ctx->b_height); nb_y++)
1038             for (nb_x = FFMAX(0, mb_x - 1); nb_x < FFMIN(mb_x + 2, mi_ctx->b_width); nb_x++) {
1039                 int x_nb = nb_x << mi_ctx->log2_mb_size;
1040                 int y_nb = nb_y << mi_ctx->log2_mb_size;
1041
1042                 if (nb_x - mb_x || nb_y - mb_y)
1043                     sbads[nb_x - mb_x + 1 + (nb_y - mb_y + 1) * 3] = get_sbad(&mi_ctx->me_ctx, x_nb, y_nb, x_nb + block->mvs[0][0], y_nb + block->mvs[0][1]);
1044             }
1045
1046     start_x = (mb_x << mi_ctx->log2_mb_size) - mi_ctx->mb_size / 2;
1047     start_y = (mb_y << mi_ctx->log2_mb_size) - mi_ctx->mb_size / 2;
1048
1049     startc_x = av_clip(start_x, 0, width - 1);
1050     startc_y = av_clip(start_y, 0, height - 1);
1051     endc_x = av_clip(start_x + (2 << mi_ctx->log2_mb_size), 0, width - 1);
1052     endc_y = av_clip(start_y + (2 << mi_ctx->log2_mb_size), 0, height - 1);
1053
1054     for (y = startc_y; y < endc_y; y++) {
1055         int y_min = -y;
1056         int y_max = height - y - 1;
1057         for (x = startc_x; x < endc_x; x++) {
1058             int x_min = -x;
1059             int x_max = width - x - 1;
1060             int obmc_weight = obmc_tab_linear[4 - mi_ctx->log2_mb_size][(x - start_x) + ((y - start_y) << (mi_ctx->log2_mb_size + 1))];
1061             PixelMVS *pixel_mvs = &mi_ctx->pixel_mvs[x + y * width];
1062             PixelWeights *pixel_weights = &mi_ctx->pixel_weights[x + y * width];
1063             PixelRefs *pixel_refs = &mi_ctx->pixel_refs[x + y * width];
1064
1065             if (mi_ctx->mc_mode == MC_MODE_AOBMC) {
1066                 nb_x = (((x - start_x) >> (mi_ctx->log2_mb_size - 1)) * 2 - 3) / 2;
1067                 nb_y = (((y - start_y) >> (mi_ctx->log2_mb_size - 1)) * 2 - 3) / 2;
1068
1069                 if (nb_x || nb_y) {
1070                     uint64_t sbad = sbads[nb_x + 1 + (nb_y + 1) * 3];
1071                     nb = &mi_ctx->int_blocks[mb_x + nb_x + (mb_y + nb_y) * mi_ctx->b_width];
1072
1073                     if (sbad && sbad != UINT64_MAX && nb->sbad != UINT64_MAX) {
1074                         int phi = av_clip(ALPHA_MAX * nb->sbad / sbad, 0, ALPHA_MAX);
1075                         obmc_weight = obmc_weight * phi / ALPHA_MAX;
1076                     }
1077                 }
1078             }
1079
1080             ADD_PIXELS(obmc_weight, mv_x, mv_y);
1081         }
1082     }
1083 }
1084
1085 static void interpolate(AVFilterLink *inlink, AVFrame *avf_out)
1086 {
1087     AVFilterContext *ctx = inlink->dst;
1088     AVFilterLink *outlink = ctx->outputs[0];
1089     MIContext *mi_ctx = ctx->priv;
1090     int x, y;
1091     int plane, alpha;
1092     int64_t pts;
1093
1094     pts = av_rescale(avf_out->pts, (int64_t) ALPHA_MAX * outlink->time_base.num * inlink->time_base.den,
1095                                    (int64_t)             outlink->time_base.den * inlink->time_base.num);
1096
1097     alpha = (pts - mi_ctx->frames[1].avf->pts * ALPHA_MAX) / (mi_ctx->frames[2].avf->pts - mi_ctx->frames[1].avf->pts);
1098     alpha = av_clip(alpha, 0, ALPHA_MAX);
1099
1100     if (alpha == 0 || alpha == ALPHA_MAX) {
1101         av_frame_copy(avf_out, alpha ? mi_ctx->frames[2].avf : mi_ctx->frames[1].avf);
1102         return;
1103     }
1104
1105     if (mi_ctx->scene_changed) {
1106         /* duplicate frame */
1107         av_frame_copy(avf_out, alpha > ALPHA_MAX / 2 ? mi_ctx->frames[2].avf : mi_ctx->frames[1].avf);
1108         return;
1109     }
1110
1111     switch(mi_ctx->mi_mode) {
1112         case MI_MODE_DUP:
1113             av_frame_copy(avf_out, alpha > ALPHA_MAX / 2 ? mi_ctx->frames[2].avf : mi_ctx->frames[1].avf);
1114
1115             break;
1116         case MI_MODE_BLEND:
1117             for (plane = 0; plane < mi_ctx->nb_planes; plane++) {
1118                 int width = avf_out->width;
1119                 int height = avf_out->height;
1120
1121                 if (plane == 1 || plane == 2) {
1122                     width = AV_CEIL_RSHIFT(width, mi_ctx->log2_chroma_w);
1123                     height = AV_CEIL_RSHIFT(height, mi_ctx->log2_chroma_h);
1124                 }
1125
1126                 for (y = 0; y < height; y++) {
1127                     for (x = 0; x < width; x++) {
1128                         avf_out->data[plane][x + y * avf_out->linesize[plane]] =
1129                             (alpha  * mi_ctx->frames[2].avf->data[plane][x + y * mi_ctx->frames[2].avf->linesize[plane]] +
1130                              (ALPHA_MAX - alpha) * mi_ctx->frames[1].avf->data[plane][x + y * mi_ctx->frames[1].avf->linesize[plane]] + 512) >> 10;
1131                     }
1132                 }
1133             }
1134
1135             break;
1136         case MI_MODE_MCI:
1137             if (mi_ctx->me_mode == ME_MODE_BIDIR) {
1138                 bidirectional_obmc(mi_ctx, alpha);
1139                 set_frame_data(mi_ctx, alpha, avf_out);
1140
1141             } else if (mi_ctx->me_mode == ME_MODE_BILAT) {
1142                 int mb_x, mb_y;
1143                 Block *block;
1144
1145                 for (y = 0; y < mi_ctx->frames[0].avf->height; y++)
1146                     for (x = 0; x < mi_ctx->frames[0].avf->width; x++)
1147                         mi_ctx->pixel_refs[x + y * mi_ctx->frames[0].avf->width].nb = 0;
1148
1149                 for (mb_y = 0; mb_y < mi_ctx->b_height; mb_y++)
1150                     for (mb_x = 0; mb_x < mi_ctx->b_width; mb_x++) {
1151                         block = &mi_ctx->int_blocks[mb_x + mb_y * mi_ctx->b_width];
1152
1153                         if (block->sb)
1154                             var_size_bmc(mi_ctx, block, mb_x << mi_ctx->log2_mb_size, mb_y << mi_ctx->log2_mb_size, mi_ctx->log2_mb_size, alpha);
1155
1156                         bilateral_obmc(mi_ctx, block, mb_x, mb_y, alpha);
1157
1158                     }
1159
1160                 set_frame_data(mi_ctx, alpha, avf_out);
1161             }
1162
1163             break;
1164     }
1165 }
1166
1167 static int filter_frame(AVFilterLink *inlink, AVFrame *avf_in)
1168 {
1169     AVFilterContext *ctx = inlink->dst;
1170     AVFilterLink *outlink = ctx->outputs[0];
1171     MIContext *mi_ctx = ctx->priv;
1172     int ret;
1173
1174     if (avf_in->pts == AV_NOPTS_VALUE) {
1175         ret = ff_filter_frame(ctx->outputs[0], avf_in);
1176         return ret;
1177     }
1178
1179     if (!mi_ctx->frames[NB_FRAMES - 1].avf || avf_in->pts < mi_ctx->frames[NB_FRAMES - 1].avf->pts) {
1180         av_log(ctx, AV_LOG_VERBOSE, "Initializing out pts from input pts %"PRId64"\n", avf_in->pts);
1181         mi_ctx->out_pts = av_rescale_q(avf_in->pts, inlink->time_base, outlink->time_base);
1182     }
1183
1184     if (!mi_ctx->frames[NB_FRAMES - 1].avf)
1185         if (ret = inject_frame(inlink, av_frame_clone(avf_in)))
1186             return ret;
1187
1188     if (ret = inject_frame(inlink, avf_in))
1189         return ret;
1190
1191     if (!mi_ctx->frames[0].avf)
1192         return 0;
1193
1194     mi_ctx->scene_changed = detect_scene_change(mi_ctx);
1195
1196     for (;;) {
1197         AVFrame *avf_out;
1198
1199         if (av_compare_ts(mi_ctx->out_pts, outlink->time_base, mi_ctx->frames[2].avf->pts, inlink->time_base) > 0)
1200             break;
1201
1202         if (!(avf_out = ff_get_video_buffer(ctx->outputs[0], inlink->w, inlink->h)))
1203             return AVERROR(ENOMEM);
1204
1205         av_frame_copy_props(avf_out, mi_ctx->frames[NB_FRAMES - 1].avf);
1206         avf_out->pts = mi_ctx->out_pts++;
1207
1208         interpolate(inlink, avf_out);
1209
1210         if ((ret = ff_filter_frame(ctx->outputs[0], avf_out)) < 0)
1211             return ret;
1212     }
1213
1214     return 0;
1215 }
1216
1217 static av_cold void free_blocks(Block *block, int sb)
1218 {
1219     if (block->subs)
1220         free_blocks(block->subs, 1);
1221     if (sb)
1222         av_freep(&block);
1223 }
1224
1225 static av_cold void uninit(AVFilterContext *ctx)
1226 {
1227     MIContext *mi_ctx = ctx->priv;
1228     int i, m;
1229
1230     av_freep(&mi_ctx->pixel_mvs);
1231     av_freep(&mi_ctx->pixel_weights);
1232     av_freep(&mi_ctx->pixel_refs);
1233     if (mi_ctx->int_blocks)
1234         for (m = 0; m < mi_ctx->b_count; m++)
1235             free_blocks(&mi_ctx->int_blocks[m], 0);
1236     av_freep(&mi_ctx->int_blocks);
1237
1238     for (i = 0; i < NB_FRAMES; i++) {
1239         Frame *frame = &mi_ctx->frames[i];
1240         av_freep(&frame->blocks);
1241         av_frame_free(&frame->avf);
1242     }
1243
1244     for (i = 0; i < 3; i++)
1245         av_freep(&mi_ctx->mv_table[i]);
1246 }
1247
1248 static const AVFilterPad minterpolate_inputs[] = {
1249     {
1250         .name          = "default",
1251         .type          = AVMEDIA_TYPE_VIDEO,
1252         .filter_frame  = filter_frame,
1253         .config_props  = config_input,
1254     },
1255     { NULL }
1256 };
1257
1258 static const AVFilterPad minterpolate_outputs[] = {
1259     {
1260         .name          = "default",
1261         .type          = AVMEDIA_TYPE_VIDEO,
1262         .config_props  = config_output,
1263     },
1264     { NULL }
1265 };
1266
1267 AVFilter ff_vf_minterpolate = {
1268     .name          = "minterpolate",
1269     .description   = NULL_IF_CONFIG_SMALL("Frame rate conversion using Motion Interpolation."),
1270     .priv_size     = sizeof(MIContext),
1271     .priv_class    = &minterpolate_class,
1272     .uninit        = uninit,
1273     .query_formats = query_formats,
1274     .inputs        = minterpolate_inputs,
1275     .outputs       = minterpolate_outputs,
1276 };