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

   1 /*
   2  * Copyright (c) 2017 Gerion Entrup
   3  *
   4  * This file is part of FFmpeg.
   5  *
   6  * FFmpeg is free software; you can redistribute it and/or modify
   7  * it under the terms of the GNU General Public License as published by
   8  * the Free Software Foundation; either version 2 of the License, or
   9  * (at your option) any later version.
  10  *
  11  * FFmpeg is distributed in the hope that it will be useful,
  12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14  * GNU General Public License for more details.
  15  *
  16  * You should have received a copy of the GNU General Public License along
  17  * with FFmpeg; if not, write to the Free Software Foundation, Inc.,
  18  * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
  19  */
  20
  21 /**
  22  * @file
  23  * MPEG-7 video signature calculation and lookup filter
  24  */
  25
  26 #include "signature.h"
  27
  28 #define HOUGH_MAX_OFFSET 90
  29 #define MAX_FRAMERATE 60
  30
  31 #define DIR_PREV 0
  32 #define DIR_NEXT 1
  33 #define DIR_PREV_END 2
  34 #define DIR_NEXT_END 3
  35
  36 #define STATUS_NULL 0
  37 #define STATUS_END_REACHED 1
  38 #define STATUS_BEGIN_REACHED 2
  39
  40 static void fill_l1distlut(uint8_t lut[])
  41 {
  42     int i, j, tmp_i, tmp_j,count;
  43     uint8_t dist;
  44
  45     for (i = 0, count = 0; i < 242; i++) {
  46         for (j = i + 1; j < 243; j++, count++) {
  47             /* ternary distance between i and j */
  48             dist = 0;
  49             tmp_i = i; tmp_j = j;
  50             do {
  51                 dist += FFABS((tmp_j % 3) - (tmp_i % 3));
  52                 tmp_j /= 3;
  53                 tmp_i /= 3;
  54             } while (tmp_i > 0 || tmp_j > 0);
  55             lut[count] = dist;
  56         }
  57     }
  58 }
  59
  60 static unsigned int intersection_word(const uint8_t *first, const uint8_t *second)
  61 {
  62     unsigned int val=0,i;
  63     for (i = 0; i < 28; i += 4) {
  64         val += av_popcount( (first[i]   & second[i]  ) << 24 |
  65                             (first[i+1] & second[i+1]) << 16 |
  66                             (first[i+2] & second[i+2]) << 8  |
  67                             (first[i+3] & second[i+3]) );
  68     }
  69     val += av_popcount( (first[28] & second[28]) << 16 |
  70                         (first[29] & second[29]) << 8  |
  71                         (first[30] & second[30]) );
  72     return val;
  73 }
  74
  75 static unsigned int union_word(const uint8_t *first, const uint8_t *second)
  76 {
  77     unsigned int val=0,i;
  78     for (i = 0; i < 28; i += 4) {
  79         val += av_popcount( (first[i]   | second[i]  ) << 24 |
  80                             (first[i+1] | second[i+1]) << 16 |
  81                             (first[i+2] | second[i+2]) << 8  |
  82                             (first[i+3] | second[i+3]) );
  83     }
  84     val += av_popcount( (first[28] | second[28]) << 16 |
  85                         (first[29] | second[29]) << 8  |
  86                         (first[30] | second[30]) );
  87     return val;
  88 }
  89
  90 static unsigned int get_l1dist(AVFilterContext *ctx, SignatureContext *sc, const uint8_t *first, const uint8_t *second)
  91 {
  92     unsigned int i;
  93     unsigned int dist = 0;
  94     uint8_t f, s;
  95
  96     for (i = 0; i < SIGELEM_SIZE/5; i++) {
  97         if (first[i] != second[i]) {
  98             f = first[i];
  99             s = second[i];
 100             if (f > s) {
 101                 /* little variation of gauss sum formula */
 102                 dist += sc->l1distlut[243*242/2 - (243-s)*(242-s)/2 + f - s - 1];
 103             } else {
 104                 dist += sc->l1distlut[243*242/2 - (243-f)*(242-f)/2 + s - f - 1];
 105             }
 106         }
 107     }
 108     return dist;
 109 }
 110
 111 /**
 112  * calculates the jaccard distance and evaluates a pair of coarse signatures as good
 113  * @return 0 if pair is bad, 1 otherwise
 114  */
 115 static int get_jaccarddist(SignatureContext *sc, CoarseSignature *first, CoarseSignature *second)
 116 {
 117     int jaccarddist, i, composdist = 0, cwthcount = 0;
 118     for (i = 0; i < 5; i++) {
 119         if ((jaccarddist = intersection_word(first->data[i], second->data[i])) > 0) {
 120             jaccarddist /= union_word(first->data[i], second->data[i]);
 121         }
 122         if (jaccarddist >= sc->thworddist) {
 123             if (++cwthcount > 2) {
 124                 /* more than half (5/2) of distances are too wide */
 125                 return 0;
 126             }
 127         }
 128         composdist += jaccarddist;
 129         if (composdist > sc->thcomposdist) {
 130             return 0;
 131         }
 132     }
 133     return 1;
 134 }
 135
 136 /**
 137  * step through the coarsesignatures as long as a good candidate is found
 138  * @return 0 if no candidate is found, 1 otherwise
 139  */
 140 static int find_next_coarsecandidate(SignatureContext *sc, CoarseSignature *secondstart, CoarseSignature **first, CoarseSignature **second, int start)
 141 {
 142     /* go one coarsesignature foreword */
 143     if (!start) {
 144         if ((*second)->next) {
 145             *second = (*second)->next;
 146         } else if ((*first)->next) {
 147             *second = secondstart;
 148             *first = (*first)->next;
 149         } else {
 150             return 0;
 151         }
 152     }
 153
 154     while (1) {
 155         if (get_jaccarddist(sc, *first, *second))
 156             return 1;
 157
 158         /* next signature */
 159         if ((*second)->next) {
 160             *second = (*second)->next;
 161         } else if ((*first)->next) {
 162             *second = secondstart;
 163             *first = (*first)->next;
 164         } else {
 165             return 0;
 166         }
 167     }
 168 }
 169
 170 /**
 171  * compares framesignatures and sorts out signatures with a l1 distance above a given threshold.
 172  * Then tries to find out offset and differences between framerates with a hough transformation
 173  */
 174 static MatchingInfo* get_matching_parameters(AVFilterContext *ctx, SignatureContext *sc, FineSignature *first, FineSignature *second)
 175 {
 176     FineSignature *f, *s;
 177     size_t i, j, k, l, hmax = 0, score;
 178     int framerate, offset, l1dist;
 179     double m;
 180     MatchingInfo *cands = NULL, *c = NULL;
 181
 182     struct {
 183         uint8_t size;
 184         unsigned int dist;
 185         FineSignature *a;
 186         uint8_t b_pos[COARSE_SIZE];
 187         FineSignature *b[COARSE_SIZE];
 188     } pairs[COARSE_SIZE];
 189
 190     typedef struct hspace_elem {
 191         int dist;
 192         size_t score;
 193         FineSignature *a;
 194         FineSignature *b;
 195     } hspace_elem;
 196
 197     /* houghspace */
 198     hspace_elem** hspace = av_malloc_array(MAX_FRAMERATE, sizeof(hspace_elem *));
 199
 200     /* initialize houghspace */
 201     for (i = 0; i < MAX_FRAMERATE; i++) {
 202         hspace[i] = av_malloc_array(2 * HOUGH_MAX_OFFSET + 1, sizeof(hspace_elem));
 203         for (j = 0; j < HOUGH_MAX_OFFSET; j++) {
 204             hspace[i][j].score = 0;
 205             hspace[i][j].dist = 99999;
 206         }
 207     }
 208
 209     /* l1 distances */
 210     for (i = 0, f = first; i < COARSE_SIZE && f->next; i++, f = f->next) {
 211         pairs[i].size = 0;
 212         pairs[i].dist = 99999;
 213         pairs[i].a = f;
 214         for (j = 0, s = second; j < COARSE_SIZE && s->next; j++, s = s->next) {
 215             /* l1 distance of finesignature */
 216             l1dist = get_l1dist(ctx, sc, f->framesig, s->framesig);
 217             if (l1dist < sc->thl1) {
 218                 if (l1dist < pairs[i].dist) {
 219                     pairs[i].size = 1;
 220                     pairs[i].dist = l1dist;
 221                     pairs[i].b_pos[0] = j;
 222                     pairs[i].b[0] = s;
 223                 } else if (l1dist == pairs[i].dist) {
 224                     pairs[i].b[pairs[i].size] = s;
 225                     pairs[i].b_pos[pairs[i].size] = j;
 226                     pairs[i].size++;
 227                 }
 228             }
 229         }
 230     }
 231     /* last incomplete coarsesignature */
 232     if (f->next == NULL) {
 233         for (; i < COARSE_SIZE; i++) {
 234             pairs[i].size = 0;
 235             pairs[i].dist = 99999;
 236         }
 237     }
 238
 239     /* hough transformation */
 240     for (i = 0; i < COARSE_SIZE; i++) {
 241         for (j = 0; j < pairs[i].size; j++) {
 242             for (k = i + 1; k < COARSE_SIZE; k++) {
 243                 for (l = 0; l < pairs[k].size; l++) {
 244                     if (pairs[i].b[j] != pairs[k].b[l]) {
 245                         /* linear regression */
 246                         m = (pairs[k].b_pos[l]-pairs[i].b_pos[j]) / (k-i); /* good value between 0.0 - 2.0 */
 247                         framerate = (int) m*30 + 0.5; /* round up to 0 - 60 */
 248                         if (framerate>0 && framerate <= MAX_FRAMERATE) {
 249                             offset = pairs[i].b_pos[j] - ((int) m*i + 0.5); /* only second part has to be rounded up */
 250                             if (offset > -HOUGH_MAX_OFFSET && offset < HOUGH_MAX_OFFSET) {
 251                                 if (pairs[i].dist < pairs[k].dist) {
 252                                     if (pairs[i].dist < hspace[framerate-1][offset+HOUGH_MAX_OFFSET].dist) {
 253                                         hspace[framerate-1][offset+HOUGH_MAX_OFFSET].dist = pairs[i].dist;
 254                                         hspace[framerate-1][offset+HOUGH_MAX_OFFSET].a = pairs[i].a;
 255                                         hspace[framerate-1][offset+HOUGH_MAX_OFFSET].b = pairs[i].b[j];
 256                                     }
 257                                 } else {
 258                                     if (pairs[k].dist < hspace[framerate-1][offset+HOUGH_MAX_OFFSET].dist) {
 259                                         hspace[framerate-1][offset+HOUGH_MAX_OFFSET].dist = pairs[k].dist;
 260                                         hspace[framerate-1][offset+HOUGH_MAX_OFFSET].a = pairs[k].a;
 261                                         hspace[framerate-1][offset+HOUGH_MAX_OFFSET].b = pairs[k].b[l];
 262                                     }
 263                                 }
 264
 265                                 score = hspace[framerate-1][offset+HOUGH_MAX_OFFSET].score + 1;
 266                                 if (score > hmax )
 267                                     hmax = score;
 268                                 hspace[framerate-1][offset+HOUGH_MAX_OFFSET].score = score;
 269                             }
 270                         }
 271                     }
 272                 }
 273             }
 274         }
 275     }
 276
 277     if (hmax > 0) {
 278         hmax = (int) (0.7*hmax);
 279         for (i = 0; i < MAX_FRAMERATE; i++) {
 280             for (j = 0; j < HOUGH_MAX_OFFSET; j++) {
 281                 if (hmax < hspace[i][j].score) {
 282                     if (c == NULL) {
 283                         c = av_malloc(sizeof(MatchingInfo));
 284                         if (!c)
 285                             av_log(ctx, AV_LOG_FATAL, "Could not allocate memory");
 286                         cands = c;
 287                     } else {
 288                         c->next = av_malloc(sizeof(MatchingInfo));
 289                         if (!c->next)
 290                             av_log(ctx, AV_LOG_FATAL, "Could not allocate memory");
 291                         c = c->next;
 292                     }
 293                     c->framerateratio = (i+1.0) / 30;
 294                     c->score = hspace[i][j].score;
 295                     c->offset = j-90;
 296                     c->first = hspace[i][j].a;
 297                     c->second = hspace[i][j].b;
 298                     c->next = NULL;
 299
 300                     /* not used */
 301                     c->meandist = 0;
 302                     c->matchframes = 0;
 303                     c->whole = 0;
 304                 }
 305             }
 306         }
 307     }
 308     for (i = 0; i < MAX_FRAMERATE; i++) {
 309         av_freep(&hspace[i]);
 310     }
 311     av_freep(&hspace);
 312     return cands;
 313 }
 314
 315 static int iterate_frame(double frr, FineSignature **a, FineSignature **b, int fcount, int *bcount, int dir)
 316 {
 317     int step;
 318
 319     /* between 1 and 2, because frr is between 1 and 2 */
 320     step = ((int) 0.5 + fcount     * frr) /* current frame */
 321           -((int) 0.5 + (fcount-1) * frr);/* last frame */
 322
 323     if (dir == DIR_NEXT) {
 324         if (frr >= 1.0) {
 325             if ((*a)->next) {
 326                 *a = (*a)->next;
 327             } else {
 328                 return DIR_NEXT_END;
 329             }
 330
 331             if (step == 1) {
 332                 if ((*b)->next) {
 333                     *b = (*b)->next;
 334                     (*bcount)++;
 335                 } else {
 336                     return DIR_NEXT_END;
 337                 }
 338             } else {
 339                 if ((*b)->next && (*b)->next->next) {
 340                     *b = (*b)->next->next;
 341                     (*bcount)++;
 342                 } else {
 343                     return DIR_NEXT_END;
 344                 }
 345             }
 346         } else {
 347             if ((*b)->next) {
 348                 *b = (*b)->next;
 349                 (*bcount)++;
 350             } else {
 351                 return DIR_NEXT_END;
 352             }
 353
 354             if (step == 1) {
 355                 if ((*a)->next) {
 356                     *a = (*a)->next;
 357                 } else {
 358                     return DIR_NEXT_END;
 359                 }
 360             } else {
 361                 if ((*a)->next && (*a)->next->next) {
 362                     *a = (*a)->next->next;
 363                 } else {
 364                     return DIR_NEXT_END;
 365                 }
 366             }
 367         }
 368         return DIR_NEXT;
 369     } else {
 370         if (frr >= 1.0) {
 371             if ((*a)->prev) {
 372                 *a = (*a)->prev;
 373             } else {
 374                 return DIR_PREV_END;
 375             }
 376
 377             if (step == 1) {
 378                 if ((*b)->prev) {
 379                     *b = (*b)->prev;
 380                     (*bcount)++;
 381                 } else {
 382                     return DIR_PREV_END;
 383                 }
 384             } else {
 385                 if ((*b)->prev && (*b)->prev->prev) {
 386                     *b = (*b)->prev->prev;
 387                     (*bcount)++;
 388                 } else {
 389                     return DIR_PREV_END;
 390                 }
 391             }
 392         } else {
 393             if ((*b)->prev) {
 394                 *b = (*b)->prev;
 395                 (*bcount)++;
 396             } else {
 397                 return DIR_PREV_END;
 398             }
 399
 400             if (step == 1) {
 401                 if ((*a)->prev) {
 402                     *a = (*a)->prev;
 403                 } else {
 404                     return DIR_PREV_END;
 405                 }
 406             } else {
 407                 if ((*a)->prev && (*a)->prev->prev) {
 408                     *a = (*a)->prev->prev;
 409                 } else {
 410                     return DIR_PREV_END;
 411                 }
 412             }
 413         }
 414         return DIR_PREV;
 415     }
 416 }
 417
 418 static MatchingInfo evaluate_parameters(AVFilterContext *ctx, SignatureContext *sc, MatchingInfo *infos, MatchingInfo bestmatch, int mode)
 419 {
 420     int dist, distsum = 0, bcount = 1, dir = DIR_NEXT;
 421     int fcount = 0, goodfcount = 0, gooda = 0, goodb = 0;
 422     double meandist, minmeandist = bestmatch.meandist;
 423     int tolerancecount = 0;
 424     FineSignature *a, *b, *aprev, *bprev;
 425     int status = STATUS_NULL;
 426
 427     for (; infos != NULL; infos = infos->next) {
 428         a = infos->first;
 429         b = infos->second;
 430         while (1) {
 431             dist = get_l1dist(ctx, sc, a->framesig, b->framesig);
 432
 433             if (dist > sc->thl1) {
 434                 if (a->confidence >= 1 || b->confidence >= 1) {
 435                     /* bad frame (because high different information) */
 436                     tolerancecount++;
 437                 }
 438
 439                 if (tolerancecount > 2) {
 440                     a = aprev;
 441                     b = bprev;
 442                     if (dir == DIR_NEXT) {
 443                         /* turn around */
 444                         a = infos->first;
 445                         b = infos->second;
 446                         dir = DIR_PREV;
 447                     } else {
 448                         break;
 449                     }
 450                 }
 451             } else {
 452                 /* good frame */
 453                 distsum += dist;
 454                 goodfcount++;
 455                 tolerancecount=0;
 456
 457                 aprev = a;
 458                 bprev = b;
 459
 460                 if (a->confidence < 1) gooda++;
 461                 if (b->confidence < 1) goodb++;
 462             }
 463
 464             fcount++;
 465
 466             dir = iterate_frame(infos->framerateratio, &a, &b, fcount, &bcount, dir);
 467             if (dir == DIR_NEXT_END) {
 468                 status = STATUS_END_REACHED;
 469                 a = infos->first;
 470                 b = infos->second;
 471                 dir = iterate_frame(infos->framerateratio, &a, &b, fcount, &bcount, DIR_PREV);
 472             }
 473
 474             if (dir == DIR_PREV_END) {
 475                 status |= STATUS_BEGIN_REACHED;
 476                 break;
 477             }
 478
 479             if (sc->thdi != 0 && bcount >= sc->thdi) {
 480                 break; /* enough frames found */
 481             }
 482         }
 483
 484         if (bcount < sc->thdi)
 485             continue; /* matching sequence is too short */
 486         if ((double) goodfcount / (double) fcount < sc->thit)
 487             continue;
 488         if ((double) goodfcount*0.5 < FFMAX(gooda, goodb))
 489             continue;
 490
 491         meandist = (double) goodfcount / (double) distsum;
 492
 493         if (meandist < minmeandist ||
 494                 status == STATUS_END_REACHED | STATUS_BEGIN_REACHED ||
 495                 mode == MODE_FAST){
 496             minmeandist = meandist;
 497             /* bestcandidate in this iteration */
 498             bestmatch.meandist = meandist;
 499             bestmatch.matchframes = bcount;
 500             bestmatch.framerateratio = infos->framerateratio;
 501             bestmatch.score = infos->score;
 502             bestmatch.offset = infos->offset;
 503             bestmatch.first = infos->first;
 504             bestmatch.second = infos->second;
 505             bestmatch.whole = 0; /* will be set to true later */
 506             bestmatch.next = NULL;
 507         }
 508
 509         /* whole sequence is automatically best match */
 510         if (status == (STATUS_END_REACHED | STATUS_BEGIN_REACHED)) {
 511             bestmatch.whole = 1;
 512             break;
 513         }
 514
 515         /* first matching sequence is enough, finding the best one is not necessary */
 516         if (mode == MODE_FAST) {
 517             break;
 518         }
 519     }
 520     return bestmatch;
 521 }
 522
 523 static void sll_free(MatchingInfo *sll)
 524 {
 525     void *tmp;
 526     while (sll) {
 527         tmp = sll;
 528         sll = sll->next;
 529         av_freep(&tmp);
 530     }
 531 }
 532
 533 static MatchingInfo lookup_signatures(AVFilterContext *ctx, SignatureContext *sc, StreamContext *first, StreamContext *second, int mode)
 534 {
 535     CoarseSignature *cs, *cs2;
 536     MatchingInfo *infos;
 537     MatchingInfo bestmatch;
 538     MatchingInfo *i;
 539
 540     cs = first->coarsesiglist;
 541     cs2 = second->coarsesiglist;
 542
 543     /* score of bestmatch is 0, if no match is found */
 544     bestmatch.score = 0;
 545     bestmatch.meandist = 99999;
 546     bestmatch.whole = 0;
 547
 548     fill_l1distlut(sc->l1distlut);
 549
 550     /* stage 1: coarsesignature matching */
 551     if (find_next_coarsecandidate(sc, second->coarsesiglist, &cs, &cs2, 1) == 0)
 552         return bestmatch; /* no candidate found */
 553     do {
 554         av_log(ctx, AV_LOG_DEBUG, "Stage 1: got coarsesignature pair. "
 555                "indices of first frame: %"PRIu32" and %"PRIu32"\n",
 556                cs->first->index, cs2->first->index);
 557         /* stage 2: l1-distance and hough-transform */
 558         av_log(ctx, AV_LOG_DEBUG, "Stage 2: calculate matching parameters\n");
 559         infos = get_matching_parameters(ctx, sc, cs->first, cs2->first);
 560         if (av_log_get_level() == AV_LOG_DEBUG) {
 561             for (i = infos; i != NULL; i = i->next) {
 562                 av_log(ctx, AV_LOG_DEBUG, "Stage 2: matching pair at %"PRIu32" and %"PRIu32", "
 563                        "ratio %f, offset %d\n", i->first->index, i->second->index,
 564                        i->framerateratio, i->offset);
 565             }
 566         }
 567         /* stage 3: evaluation */
 568         av_log(ctx, AV_LOG_DEBUG, "Stage 3: evaluate\n");
 569         if (infos) {
 570             bestmatch = evaluate_parameters(ctx, sc, infos, bestmatch, mode);
 571             av_log(ctx, AV_LOG_DEBUG, "Stage 3: best matching pair at %"PRIu32" and %"PRIu32", "
 572                    "ratio %f, offset %d, score %d, %d frames matching\n",
 573                    bestmatch.first->index, bestmatch.second->index,
 574                    bestmatch.framerateratio, bestmatch.offset, bestmatch.score, bestmatch.matchframes);
 575             sll_free(infos);
 576         }
 577     } while (find_next_coarsecandidate(sc, second->coarsesiglist, &cs, &cs2, 0) && !bestmatch.whole);
 578     return bestmatch;
 579
 580 }