FFmpeg coverage


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