FFmpeg
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Groups Pages
signature_lookup.c
Go to the documentation of this file.
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  */
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  */
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  */
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];
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 
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 ||
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 
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 
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 }
uint8_t l1distlut[243 *242/2]
Definition: signature.h:141
static unsigned int union_word(const uint8_t *first, const uint8_t *second)
#define NULL
Definition: coverity.c:32
double meandist
Definition: signature.h:91
const char const char void * val
Definition: avisynth_c.h:771
static MatchingInfo * get_matching_parameters(AVFilterContext *ctx, SignatureContext *sc, FineSignature *first, FineSignature *second)
compares framesignatures and sorts out signatures with a l1 distance above a given threshold...
static int find_next_coarsecandidate(SignatureContext *sc, CoarseSignature *secondstart, CoarseSignature **first, CoarseSignature **second, int start)
step through the coarsesignatures as long as a good candidate is found
const char * b
Definition: vf_curves.c:113
struct FineSignature * next
Definition: signature.h:73
#define COARSE_SIZE
Definition: signature.h:39
#define STATUS_NULL
uint32_t index
Definition: signature.h:76
#define HOUGH_MAX_OFFSET
#define DIR_PREV
uint8_t confidence
Definition: signature.h:77
static int get_jaccarddist(SignatureContext *sc, CoarseSignature *first, CoarseSignature *second)
calculates the jaccard distance and evaluates a pair of coarse signatures as good ...
uint8_t
#define av_malloc(s)
#define f(width, name)
Definition: cbs_vp9.c:255
struct FineSignature * first
Definition: signature.h:84
static void fill_l1distlut(uint8_t lut[])
ptrdiff_t size
Definition: opengl_enc.c:101
#define av_log(a,...)
#define DIR_NEXT
#define STATUS_END_REACHED
#define AV_LOG_DEBUG
Stuff which is only useful for libav* developers.
Definition: log.h:197
int av_log_get_level(void)
Get the current log level.
Definition: log.c:380
static const uint8_t offset[127][2]
Definition: vf_spp.c:92
GLsizei count
Definition: opengl_enc.c:109
#define FFMAX(a, b)
Definition: common.h:94
static MatchingInfo lookup_signatures(AVFilterContext *ctx, SignatureContext *sc, StreamContext *first, StreamContext *second, int mode)
#define MAX_FRAMERATE
int matchframes
Definition: signature.h:95
struct FineSignature * second
Definition: signature.h:98
static void sll_free(MatchingInfo *sll)
AVFormatContext * ctx
Definition: movenc.c:48
MPEG-7 video signature calculation and lookup filter.
#define FFABS(a)
Absolute value, Note, INT_MIN / INT64_MIN result in undefined behavior as they are not representable ...
Definition: common.h:72
#define s(width, name)
Definition: cbs_vp9.c:257
static MatchingInfo evaluate_parameters(AVFilterContext *ctx, SignatureContext *sc, MatchingInfo *infos, MatchingInfo bestmatch, int mode)
static unsigned int intersection_word(const uint8_t *first, const uint8_t *second)
static unsigned int get_l1dist(AVFilterContext *ctx, SignatureContext *sc, const uint8_t *first, const uint8_t *second)
#define DIR_NEXT_END
#define STATUS_BEGIN_REACHED
static int iterate_frame(double frr, FineSignature **a, FineSignature **b, int fcount, int *bcount, int dir)
struct CoarseSignature * next
Definition: signature.h:86
CoarseSignature * coarsesiglist
Definition: signature.h:114
struct FineSignature * first
Definition: signature.h:97
int
#define DIR_PREV_END
#define SIGELEM_SIZE
Definition: signature.h:37
static double c[64]
struct FineSignature * prev
Definition: signature.h:74
uint8_t data[5][31]
Definition: signature.h:83
An instance of a filter.
Definition: avfilter.h:338
#define av_freep(p)
void INT64 start
Definition: avisynth_c.h:690
#define AV_LOG_FATAL
Something went wrong and recovery is not possible.
Definition: log.h:170
#define av_malloc_array(a, b)
mode
Use these values in ebur128_init (or'ed).
Definition: ebur128.h:83
double framerateratio
Definition: signature.h:92
struct MatchingInfo * next
Definition: signature.h:99
uint8_t framesig[SIGELEM_SIZE/5]
Definition: signature.h:79
static uint8_t tmp[11]
Definition: aes_ctr.c:26