FFmpeg coverage


Directory: ../../../ffmpeg/
File: src/libavfilter/signature_lookup.c
Date: 2024-04-19 07:31:02
Exec Total Coverage
Lines: 0 302 0.0%
Functions: 0 11 0.0%
Branches: 0 204 0.0%

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