FFmpeg coverage

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