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