avfilter/f_loop: make sure duration of frame is never zero
[ffmpeg.git] / 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 }