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