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;
 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         if (mi_ctx->b_width < 2 || mi_ctx->b_height < 2) {
 367             av_log(inlink->dst, AV_LOG_ERROR, "Height or width < %d\n",
 368                    2 * mi_ctx->mb_size);
 369             return AVERROR(EINVAL);
 370         }
 371         ff_me_init_context(me_ctx, mi_ctx->mb_size, mi_ctx->search_param,
 372                            width, height, 0, (mi_ctx->b_width - 1) << mi_ctx->log2_mb_size,
 373                            0, (mi_ctx->b_height - 1) << mi_ctx->log2_mb_size);
 374
 375         if (mi_ctx->me_mode == ME_MODE_BIDIR)
 376             me_ctx->get_cost = &get_sad_ob;
 377         else if (mi_ctx->me_mode == ME_MODE_BILAT)
 378             me_ctx->get_cost = &get_sbad_ob;
 379
 380         mi_ctx->pixel_mvs = av_mallocz_array(width * height, sizeof(PixelMVS));
 381         mi_ctx->pixel_weights = av_mallocz_array(width * height, sizeof(PixelWeights));
 382         mi_ctx->pixel_refs = av_mallocz_array(width * height, sizeof(PixelRefs));
 383         if (!mi_ctx->pixel_mvs || !mi_ctx->pixel_weights || !mi_ctx->pixel_refs)
 384             return AVERROR(ENOMEM);
 385
 386         if (mi_ctx->me_mode == ME_MODE_BILAT)
 387             if (!(mi_ctx->int_blocks = av_mallocz_array(mi_ctx->b_count, sizeof(Block))))
 388                 return AVERROR(ENOMEM);
 389
 390         if (mi_ctx->me_method == AV_ME_METHOD_EPZS) {
 391             for (i = 0; i < 3; i++) {
 392                 mi_ctx->mv_table[i] = av_mallocz_array(mi_ctx->b_count, sizeof(*mi_ctx->mv_table[0]));
 393                 if (!mi_ctx->mv_table[i])
 394                     return AVERROR(ENOMEM);
 395             }
 396         }
 397     }
 398
 399     if (mi_ctx->scd_method == SCD_METHOD_FDIFF) {
 400         mi_ctx->sad = ff_scene_sad_get_fn(mi_ctx->bitdepth == 8 ? 8 : 16);
 401         if (!mi_ctx->sad)
 402             return AVERROR(EINVAL);
 403     }
 404
 405     return 0;
 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(AVFilterContext *ctx)
 827 {
 828     MIContext *mi_ctx = ctx->priv;
 829     AVFilterLink *input = ctx->inputs[0];
 830     uint8_t *p1 = mi_ctx->frames[1].avf->data[0];
 831     ptrdiff_t linesize1 = mi_ctx->frames[1].avf->linesize[0];
 832     uint8_t *p2 = mi_ctx->frames[2].avf->data[0];
 833     ptrdiff_t linesize2 = mi_ctx->frames[2].avf->linesize[0];
 834
 835     if (mi_ctx->scd_method == SCD_METHOD_FDIFF) {
 836         double ret = 0, mafd, diff;
 837         uint64_t sad;
 838         mi_ctx->sad(p1, linesize1, p2, linesize2, input->w, input->h, &sad);
 839         emms_c();
 840         mafd = (double) sad * 100.0 / (input->h * input->w) / (1 << mi_ctx->bitdepth);
 841         diff = fabs(mafd - mi_ctx->prev_mafd);
 842         ret  = av_clipf(FFMIN(mafd, diff), 0, 100.0);
 843         mi_ctx->prev_mafd = mafd;
 844
 845         return ret >= mi_ctx->scd_threshold;
 846     }
 847
 848     return 0;
 849 }
 850
 851 #define ADD_PIXELS(b_weight, mv_x, mv_y)\
 852     do {\
 853         if (!b_weight || pixel_refs->nb + 1 >= NB_PIXEL_MVS)\
 854             continue;\
 855         pixel_refs->refs[pixel_refs->nb] = 1;\
 856         pixel_weights->weights[pixel_refs->nb] = b_weight * (ALPHA_MAX - alpha);\
 857         pixel_mvs->mvs[pixel_refs->nb][0] = av_clip((mv_x * alpha) / ALPHA_MAX, x_min, x_max);\
 858         pixel_mvs->mvs[pixel_refs->nb][1] = av_clip((mv_y * alpha) / ALPHA_MAX, y_min, y_max);\
 859         pixel_refs->nb++;\
 860         pixel_refs->refs[pixel_refs->nb] = 2;\
 861         pixel_weights->weights[pixel_refs->nb] = b_weight * alpha;\
 862         pixel_mvs->mvs[pixel_refs->nb][0] = av_clip(-mv_x * (ALPHA_MAX - alpha) / ALPHA_MAX, x_min, x_max);\
 863         pixel_mvs->mvs[pixel_refs->nb][1] = av_clip(-mv_y * (ALPHA_MAX - alpha) / ALPHA_MAX, y_min, y_max);\
 864         pixel_refs->nb++;\
 865     } while(0)
 866
 867 static void bidirectional_obmc(MIContext *mi_ctx, int alpha)
 868 {
 869     int x, y;
 870     int width = mi_ctx->frames[0].avf->width;
 871     int height = mi_ctx->frames[0].avf->height;
 872     int mb_y, mb_x, dir;
 873
 874     for (y = 0; y < height; y++)
 875         for (x = 0; x < width; x++)
 876             mi_ctx->pixel_refs[x + y * width].nb = 0;
 877
 878     for (dir = 0; dir < 2; dir++)
 879         for (mb_y = 0; mb_y < mi_ctx->b_height; mb_y++)
 880             for (mb_x = 0; mb_x < mi_ctx->b_width; mb_x++) {
 881                 int a = dir ? alpha : (ALPHA_MAX - alpha);
 882                 int mv_x = mi_ctx->frames[2 - dir].blocks[mb_x + mb_y * mi_ctx->b_width].mvs[dir][0];
 883                 int mv_y = mi_ctx->frames[2 - dir].blocks[mb_x + mb_y * mi_ctx->b_width].mvs[dir][1];
 884                 int start_x, start_y;
 885                 int startc_x, startc_y, endc_x, endc_y;
 886
 887                 start_x = (mb_x << mi_ctx->log2_mb_size) - mi_ctx->mb_size / 2 + mv_x * a / ALPHA_MAX;
 888                 start_y = (mb_y << mi_ctx->log2_mb_size) - mi_ctx->mb_size / 2 + mv_y * a / ALPHA_MAX;
 889
 890                 startc_x = av_clip(start_x, 0, width - 1);
 891                 startc_y = av_clip(start_y, 0, height - 1);
 892                 endc_x = av_clip(start_x + (2 << mi_ctx->log2_mb_size), 0, width - 1);
 893                 endc_y = av_clip(start_y + (2 << mi_ctx->log2_mb_size), 0, height - 1);
 894
 895                 if (dir) {
 896                     mv_x = -mv_x;
 897                     mv_y = -mv_y;
 898                 }
 899
 900                 for (y = startc_y; y < endc_y; y++) {
 901                     int y_min = -y;
 902                     int y_max = height - y - 1;
 903                     for (x = startc_x; x < endc_x; x++) {
 904                         int x_min = -x;
 905                         int x_max = width - x - 1;
 906                         int obmc_weight = obmc_tab_linear[4 - mi_ctx->log2_mb_size][(x - start_x) + ((y - start_y) << (mi_ctx->log2_mb_size + 1))];
 907                         PixelMVS *pixel_mvs = &mi_ctx->pixel_mvs[x + y * width];
 908                         PixelWeights *pixel_weights = &mi_ctx->pixel_weights[x + y * width];
 909                         PixelRefs *pixel_refs = &mi_ctx->pixel_refs[x + y * width];
 910
 911                         ADD_PIXELS(obmc_weight, mv_x, mv_y);
 912                     }
 913                 }
 914             }
 915 }
 916
 917 static void set_frame_data(MIContext *mi_ctx, int alpha, AVFrame *avf_out)
 918 {
 919     int x, y, plane;
 920
 921     for (plane = 0; plane < mi_ctx->nb_planes; plane++) {
 922         int width = avf_out->width;
 923         int height = avf_out->height;
 924         int chroma = plane == 1 || plane == 2;
 925
 926         for (y = 0; y < height; y++)
 927             for (x = 0; x < width; x++) {
 928                 int x_mv, y_mv;
 929                 int weight_sum = 0;
 930                 int i, val = 0;
 931                 PixelMVS *pixel_mvs = &mi_ctx->pixel_mvs[x + y * avf_out->width];
 932                 PixelWeights *pixel_weights = &mi_ctx->pixel_weights[x + y * avf_out->width];
 933                 PixelRefs *pixel_refs = &mi_ctx->pixel_refs[x + y * avf_out->width];
 934
 935                 for (i = 0; i < pixel_refs->nb; i++)
 936                     weight_sum += pixel_weights->weights[i];
 937
 938                 if (!weight_sum || !pixel_refs->nb) {
 939                     pixel_weights->weights[0] = ALPHA_MAX - alpha;
 940                     pixel_refs->refs[0] = 1;
 941                     pixel_mvs->mvs[0][0] = 0;
 942                     pixel_mvs->mvs[0][1] = 0;
 943                     pixel_weights->weights[1] = alpha;
 944                     pixel_refs->refs[1] = 2;
 945                     pixel_mvs->mvs[1][0] = 0;
 946                     pixel_mvs->mvs[1][1] = 0;
 947                     pixel_refs->nb = 2;
 948
 949                     weight_sum = ALPHA_MAX;
 950                 }
 951
 952                 for (i = 0; i < pixel_refs->nb; i++) {
 953                     Frame *frame = &mi_ctx->frames[pixel_refs->refs[i]];
 954                     if (chroma) {
 955                         x_mv = (x >> mi_ctx->log2_chroma_w) + pixel_mvs->mvs[i][0] / (1 << mi_ctx->log2_chroma_w);
 956                         y_mv = (y >> mi_ctx->log2_chroma_h) + pixel_mvs->mvs[i][1] / (1 << mi_ctx->log2_chroma_h);
 957                     } else {
 958                         x_mv = x + pixel_mvs->mvs[i][0];
 959                         y_mv = y + pixel_mvs->mvs[i][1];
 960                     }
 961
 962                     val += pixel_weights->weights[i] * frame->avf->data[plane][x_mv + y_mv * frame->avf->linesize[plane]];
 963                 }
 964
 965                 val = ROUNDED_DIV(val, weight_sum);
 966
 967                 if (chroma)
 968                     avf_out->data[plane][(x >> mi_ctx->log2_chroma_w) + (y >> mi_ctx->log2_chroma_h) * avf_out->linesize[plane]] = val;
 969                 else
 970                     avf_out->data[plane][x + y * avf_out->linesize[plane]] = val;
 971             }
 972     }
 973 }
 974
 975 static void var_size_bmc(MIContext *mi_ctx, Block *block, int x_mb, int y_mb, int n, int alpha)
 976 {
 977     int sb_x, sb_y;
 978     int width = mi_ctx->frames[0].avf->width;
 979     int height = mi_ctx->frames[0].avf->height;
 980
 981     for (sb_y = 0; sb_y < 2; sb_y++)
 982         for (sb_x = 0; sb_x < 2; sb_x++) {
 983             Block *sb = &block->subs[sb_x + sb_y * 2];
 984
 985             if (sb->sb)
 986                 var_size_bmc(mi_ctx, sb, x_mb + (sb_x << (n - 1)), y_mb + (sb_y << (n - 1)), n - 1, alpha);
 987             else {
 988                 int x, y;
 989                 int mv_x = sb->mvs[0][0] * 2;
 990                 int mv_y = sb->mvs[0][1] * 2;
 991
 992                 int start_x = x_mb + (sb_x << (n - 1));
 993                 int start_y = y_mb + (sb_y << (n - 1));
 994                 int end_x = start_x + (1 << (n - 1));
 995                 int end_y = start_y + (1 << (n - 1));
 996
 997                 for (y = start_y; y < end_y; y++)  {
 998                     int y_min = -y;
 999                     int y_max = height - y - 1;
1000                     for (x = start_x; x < end_x; x++) {
1001                         int x_min = -x;
1002                         int x_max = width - x - 1;
1003                         PixelMVS *pixel_mvs = &mi_ctx->pixel_mvs[x + y * width];
1004                         PixelWeights *pixel_weights = &mi_ctx->pixel_weights[x + y * width];
1005                         PixelRefs *pixel_refs = &mi_ctx->pixel_refs[x + y * width];
1006
1007                         ADD_PIXELS(PX_WEIGHT_MAX, mv_x, mv_y);
1008                     }
1009                 }
1010             }
1011         }
1012 }
1013
1014 static void bilateral_obmc(MIContext *mi_ctx, Block *block, int mb_x, int mb_y, int alpha)
1015 {
1016     int x, y;
1017     int width = mi_ctx->frames[0].avf->width;
1018     int height = mi_ctx->frames[0].avf->height;
1019
1020     Block *nb;
1021     int nb_x, nb_y;
1022     uint64_t sbads[9];
1023
1024     int mv_x = block->mvs[0][0] * 2;
1025     int mv_y = block->mvs[0][1] * 2;
1026     int start_x, start_y;
1027     int startc_x, startc_y, endc_x, endc_y;
1028
1029     if (mi_ctx->mc_mode == MC_MODE_AOBMC)
1030         for (nb_y = FFMAX(0, mb_y - 1); nb_y < FFMIN(mb_y + 2, mi_ctx->b_height); nb_y++)
1031             for (nb_x = FFMAX(0, mb_x - 1); nb_x < FFMIN(mb_x + 2, mi_ctx->b_width); nb_x++) {
1032                 int x_nb = nb_x << mi_ctx->log2_mb_size;
1033                 int y_nb = nb_y << mi_ctx->log2_mb_size;
1034
1035                 if (nb_x - mb_x || nb_y - mb_y)
1036                     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]);
1037             }
1038
1039     start_x = (mb_x << mi_ctx->log2_mb_size) - mi_ctx->mb_size / 2;
1040     start_y = (mb_y << mi_ctx->log2_mb_size) - mi_ctx->mb_size / 2;
1041
1042     startc_x = av_clip(start_x, 0, width - 1);
1043     startc_y = av_clip(start_y, 0, height - 1);
1044     endc_x = av_clip(start_x + (2 << mi_ctx->log2_mb_size), 0, width - 1);
1045     endc_y = av_clip(start_y + (2 << mi_ctx->log2_mb_size), 0, height - 1);
1046
1047     for (y = startc_y; y < endc_y; y++) {
1048         int y_min = -y;
1049         int y_max = height - y - 1;
1050         for (x = startc_x; x < endc_x; x++) {
1051             int x_min = -x;
1052             int x_max = width - x - 1;
1053             int obmc_weight = obmc_tab_linear[4 - mi_ctx->log2_mb_size][(x - start_x) + ((y - start_y) << (mi_ctx->log2_mb_size + 1))];
1054             PixelMVS *pixel_mvs = &mi_ctx->pixel_mvs[x + y * width];
1055             PixelWeights *pixel_weights = &mi_ctx->pixel_weights[x + y * width];
1056             PixelRefs *pixel_refs = &mi_ctx->pixel_refs[x + y * width];
1057
1058             if (mi_ctx->mc_mode == MC_MODE_AOBMC) {
1059                 nb_x = (((x - start_x) >> (mi_ctx->log2_mb_size - 1)) * 2 - 3) / 2;
1060                 nb_y = (((y - start_y) >> (mi_ctx->log2_mb_size - 1)) * 2 - 3) / 2;
1061
1062                 if (nb_x || nb_y) {
1063                     uint64_t sbad = sbads[nb_x + 1 + (nb_y + 1) * 3];
1064                     nb = &mi_ctx->int_blocks[mb_x + nb_x + (mb_y + nb_y) * mi_ctx->b_width];
1065
1066                     if (sbad && sbad != UINT64_MAX && nb->sbad != UINT64_MAX) {
1067                         int phi = av_clip(ALPHA_MAX * nb->sbad / sbad, 0, ALPHA_MAX);
1068                         obmc_weight = obmc_weight * phi / ALPHA_MAX;
1069                     }
1070                 }
1071             }
1072
1073             ADD_PIXELS(obmc_weight, mv_x, mv_y);
1074         }
1075     }
1076 }
1077
1078 static void interpolate(AVFilterLink *inlink, AVFrame *avf_out)
1079 {
1080     AVFilterContext *ctx = inlink->dst;
1081     AVFilterLink *outlink = ctx->outputs[0];
1082     MIContext *mi_ctx = ctx->priv;
1083     int x, y;
1084     int plane, alpha;
1085     int64_t pts;
1086
1087     pts = av_rescale(avf_out->pts, (int64_t) ALPHA_MAX * outlink->time_base.num * inlink->time_base.den,
1088                                    (int64_t)             outlink->time_base.den * inlink->time_base.num);
1089
1090     alpha = (pts - mi_ctx->frames[1].avf->pts * ALPHA_MAX) / (mi_ctx->frames[2].avf->pts - mi_ctx->frames[1].avf->pts);
1091     alpha = av_clip(alpha, 0, ALPHA_MAX);
1092
1093     if (alpha == 0 || alpha == ALPHA_MAX) {
1094         av_frame_copy(avf_out, alpha ? mi_ctx->frames[2].avf : mi_ctx->frames[1].avf);
1095         return;
1096     }
1097
1098     if (mi_ctx->scene_changed) {
1099         av_log(ctx, AV_LOG_DEBUG, "scene changed, input pts %"PRId64"\n", mi_ctx->frames[1].avf->pts);
1100         /* duplicate frame */
1101         av_frame_copy(avf_out, alpha > ALPHA_MAX / 2 ? mi_ctx->frames[2].avf : mi_ctx->frames[1].avf);
1102         return;
1103     }
1104
1105     switch(mi_ctx->mi_mode) {
1106         case MI_MODE_DUP:
1107             av_frame_copy(avf_out, alpha > ALPHA_MAX / 2 ? mi_ctx->frames[2].avf : mi_ctx->frames[1].avf);
1108
1109             break;
1110         case MI_MODE_BLEND:
1111             for (plane = 0; plane < mi_ctx->nb_planes; plane++) {
1112                 int width = avf_out->width;
1113                 int height = avf_out->height;
1114
1115                 if (plane == 1 || plane == 2) {
1116                     width = AV_CEIL_RSHIFT(width, mi_ctx->log2_chroma_w);
1117                     height = AV_CEIL_RSHIFT(height, mi_ctx->log2_chroma_h);
1118                 }
1119
1120                 for (y = 0; y < height; y++) {
1121                     for (x = 0; x < width; x++) {
1122                         avf_out->data[plane][x + y * avf_out->linesize[plane]] =
1123                             (alpha  * mi_ctx->frames[2].avf->data[plane][x + y * mi_ctx->frames[2].avf->linesize[plane]] +
1124                              (ALPHA_MAX - alpha) * mi_ctx->frames[1].avf->data[plane][x + y * mi_ctx->frames[1].avf->linesize[plane]] + 512) >> 10;
1125                     }
1126                 }
1127             }
1128
1129             break;
1130         case MI_MODE_MCI:
1131             if (mi_ctx->me_mode == ME_MODE_BIDIR) {
1132                 bidirectional_obmc(mi_ctx, alpha);
1133                 set_frame_data(mi_ctx, alpha, avf_out);
1134
1135             } else if (mi_ctx->me_mode == ME_MODE_BILAT) {
1136                 int mb_x, mb_y;
1137                 Block *block;
1138
1139                 for (y = 0; y < mi_ctx->frames[0].avf->height; y++)
1140                     for (x = 0; x < mi_ctx->frames[0].avf->width; x++)
1141                         mi_ctx->pixel_refs[x + y * mi_ctx->frames[0].avf->width].nb = 0;
1142
1143                 for (mb_y = 0; mb_y < mi_ctx->b_height; mb_y++)
1144                     for (mb_x = 0; mb_x < mi_ctx->b_width; mb_x++) {
1145                         block = &mi_ctx->int_blocks[mb_x + mb_y * mi_ctx->b_width];
1146
1147                         if (block->sb)
1148                             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);
1149
1150                         bilateral_obmc(mi_ctx, block, mb_x, mb_y, alpha);
1151
1152                     }
1153
1154                 set_frame_data(mi_ctx, alpha, avf_out);
1155             }
1156
1157             break;
1158     }
1159 }
1160
1161 static int filter_frame(AVFilterLink *inlink, AVFrame *avf_in)
1162 {
1163     AVFilterContext *ctx = inlink->dst;
1164     AVFilterLink *outlink = ctx->outputs[0];
1165     MIContext *mi_ctx = ctx->priv;
1166     int ret;
1167
1168     if (avf_in->pts == AV_NOPTS_VALUE) {
1169         ret = ff_filter_frame(ctx->outputs[0], avf_in);
1170         return ret;
1171     }
1172
1173     if (!mi_ctx->frames[NB_FRAMES - 1].avf || avf_in->pts < mi_ctx->frames[NB_FRAMES - 1].avf->pts) {
1174         av_log(ctx, AV_LOG_VERBOSE, "Initializing out pts from input pts %"PRId64"\n", avf_in->pts);
1175         mi_ctx->out_pts = av_rescale_q(avf_in->pts, inlink->time_base, outlink->time_base);
1176     }
1177
1178     if (!mi_ctx->frames[NB_FRAMES - 1].avf)
1179         if (ret = inject_frame(inlink, av_frame_clone(avf_in)))
1180             return ret;
1181
1182     if (ret = inject_frame(inlink, avf_in))
1183         return ret;
1184
1185     if (!mi_ctx->frames[0].avf)
1186         return 0;
1187
1188     mi_ctx->scene_changed = detect_scene_change(ctx);
1189
1190     for (;;) {
1191         AVFrame *avf_out;
1192
1193         if (av_compare_ts(mi_ctx->out_pts, outlink->time_base, mi_ctx->frames[2].avf->pts, inlink->time_base) > 0)
1194             break;
1195
1196         if (!(avf_out = ff_get_video_buffer(ctx->outputs[0], inlink->w, inlink->h)))
1197             return AVERROR(ENOMEM);
1198
1199         av_frame_copy_props(avf_out, mi_ctx->frames[NB_FRAMES - 1].avf);
1200         avf_out->pts = mi_ctx->out_pts++;
1201
1202         interpolate(inlink, avf_out);
1203
1204         if ((ret = ff_filter_frame(ctx->outputs[0], avf_out)) < 0)
1205             return ret;
1206     }
1207
1208     return 0;
1209 }
1210
1211 static av_cold void free_blocks(Block *block, int sb)
1212 {
1213     if (block->subs)
1214         free_blocks(block->subs, 1);
1215     if (sb)
1216         av_freep(&block);
1217 }
1218
1219 static av_cold void uninit(AVFilterContext *ctx)
1220 {
1221     MIContext *mi_ctx = ctx->priv;
1222     int i, m;
1223
1224     av_freep(&mi_ctx->pixel_mvs);
1225     av_freep(&mi_ctx->pixel_weights);
1226     av_freep(&mi_ctx->pixel_refs);
1227     if (mi_ctx->int_blocks)
1228         for (m = 0; m < mi_ctx->b_count; m++)
1229             free_blocks(&mi_ctx->int_blocks[m], 0);
1230     av_freep(&mi_ctx->int_blocks);
1231
1232     for (i = 0; i < NB_FRAMES; i++) {
1233         Frame *frame = &mi_ctx->frames[i];
1234         av_freep(&frame->blocks);
1235         av_frame_free(&frame->avf);
1236     }
1237
1238     for (i = 0; i < 3; i++)
1239         av_freep(&mi_ctx->mv_table[i]);
1240 }
1241
1242 static const AVFilterPad minterpolate_inputs[] = {
1243     {
1244         .name          = "default",
1245         .type          = AVMEDIA_TYPE_VIDEO,
1246         .filter_frame  = filter_frame,
1247         .config_props  = config_input,
1248     },
1249     { NULL }
1250 };
1251
1252 static const AVFilterPad minterpolate_outputs[] = {
1253     {
1254         .name          = "default",
1255         .type          = AVMEDIA_TYPE_VIDEO,
1256         .config_props  = config_output,
1257     },
1258     { NULL }
1259 };
1260
1261 const AVFilter ff_vf_minterpolate = {
1262     .name          = "minterpolate",
1263     .description   = NULL_IF_CONFIG_SMALL("Frame rate conversion using Motion Interpolation."),
1264     .priv_size     = sizeof(MIContext),
1265     .priv_class    = &minterpolate_class,
1266     .uninit        = uninit,
1267     .query_formats = query_formats,
1268     .inputs        = minterpolate_inputs,
1269     .outputs       = minterpolate_outputs,
1270 };