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