On Donnerstag, 7. April 2016 00:35:25 CEST Michael Niedermayer wrote:
> On Wed, Mar 30, 2016 at 11:02:36PM +0200, Gerion Entrup wrote:
> > On Mittwoch, 30. März 2016 22:57:47 CEST Gerion Entrup wrote:
> > > Add improved patch.
> >
> > Rebased to master.
> >
>
> > Changelog | 1
> > configure | 1
> > doc/filters.texi | 70 +++
> > libavfilter/Makefile | 1
> > libavfilter/allfilters.c | 1
> > libavfilter/signature.h | 554 ++++++++++++++++++++++++++++++
> > libavfilter/signature_lookup.c | 550 ++++++++++++++++++++++++++++++
> > libavfilter/version.h | 4
> > libavfilter/vf_signature.c | 741
> > +++++++++++++++++++++++++++++++++++++++++
> > 9 files changed, 1921 insertions(+), 2 deletions(-)
> > 9192f27ded45c607996b4e266b6746f807c9a7fd
> > 0001-add-signature-filter-for-MPEG7-video-signature.patch
> > From 9646ed6f0cf78356cf2914a60705c98d8f21fe8a Mon Sep 17 00:00:00 2001
> > From: Gerion Entrup <gerion.ent...@flump.de>
> > Date: Sun, 20 Mar 2016 11:10:31 +0100
> > Subject: [PATCH] add signature filter for MPEG7 video signature
> >
> > This filter does not implement all features of MPEG7. Missing features:
> > - compression of signature files
> > - work only on (cropped) parts of the video
> > ---
> > Changelog | 1 +
> > configure | 1 +
> > doc/filters.texi | 70 ++++
> > libavfilter/Makefile | 1 +
> > libavfilter/allfilters.c | 1 +
> > libavfilter/signature.h | 554 ++++++++++++++++++++++++++++++
> > libavfilter/signature_lookup.c | 550 ++++++++++++++++++++++++++++++
> > libavfilter/version.h | 4 +-
> > libavfilter/vf_signature.c | 741
> > +++++++++++++++++++++++++++++++++++++++++
> > 9 files changed, 1921 insertions(+), 2 deletions(-)
> > create mode 100644 libavfilter/signature.h
> > create mode 100644 libavfilter/signature_lookup.c
> > create mode 100644 libavfilter/vf_signature.c
> >
> > diff --git a/Changelog b/Changelog
> > index 7b0187d..8a2b7fd 100644
> > --- a/Changelog
> > +++ b/Changelog
> > @@ -18,6 +18,7 @@ version <next>:
> > - coreimage filter (GPU based image filtering on OSX)
> > - libdcadec removed
> > - bitstream filter for extracting DTS core
> > +- MPEG-7 Video Signature filter
> >
> > version 3.0:
> > - Common Encryption (CENC) MP4 encoding and decoding support
> > diff --git a/configure b/configure
> > index e550547..fe29827 100755
> > --- a/configure
> > +++ b/configure
> > @@ -2979,6 +2979,7 @@ showspectrum_filter_deps="avcodec"
> > showspectrum_filter_select="fft"
> > showspectrumpic_filter_deps="avcodec"
> > showspectrumpic_filter_select="fft"
> > +signature_filter_deps="gpl avcodec avformat"
> > smartblur_filter_deps="gpl swscale"
> > sofalizer_filter_deps="netcdf avcodec"
> > sofalizer_filter_select="fft"
> > diff --git a/doc/filters.texi b/doc/filters.texi
> > index 5d6cf52..a95f5a7 100644
> > --- a/doc/filters.texi
> > +++ b/doc/filters.texi
> > @@ -11559,6 +11559,76 @@ saturation maximum:
> > %@{metadata:lavfi.signalstats.SATMAX@}
> > @end example
> > @end itemize
> >
> > +@anchor{signature}
> > +@section signature
> > +
> > +Calculates the MPEG-7 Video Signature. The filter could handle more than
> > one
> > +input. In this case the matching between the inputs could be calculated.
> > The
> > +filter passthrough the first input. The output is written in XML.
> > +
> > +It accepts the following options:
> > +
> > +@table @option
> > +@item mode
>
> > +Enable the calculation of the matching. The option value must be 0 (to
> > disable
> > +or 1 (to enable). Optionally you can set the mode to 2. Then the detection
> > ends,
> > +if the first matching sequence it reached. This should be slightly faster.
> > +Per default the detection is disabled.
>
> these shuld probably support named identifers not (only) 0/1/2
done
>
>
> > +
> > +@item nb_inputs
> > +Set the number of inputs. The option value must be a non negative interger.
> > +Default value is 1.
> > +
> > +@item filename
> > +Set the path to witch the output is written. If there is more than one
> > input,
> > +the path must be a prototype, i.e. must contain %d or %0nd (where n is a
> > positive
> > +integer), that will be replaced with the input number. If no filename is
> > +specified, no output will be written. This is the default.
> > +
>
> > +@item xml
> > +Choose the output format. If set to 1 the filter will write XML, if set to > > 0
> > +the filter will write binary output. The default is 0.
>
> format=xml/bin/whatever
> seems better as its more extensible
done
>
>
> > +
> > +@item th_d
> > +Set threshold to detect one word as similar. The option value must be an
> > integer
> > +greater than zero. The default value is 9000.
> > +
> > +@item th_dc
> > +Set threshold to detect all words as similar. The option value must be an
> > integer
> > +greater than zero. The default value is 60000.
> > +
> > +@item th_xh
> > +Set threshold to detect frames as similar. The option value must be an
> > integer
> > +greater than zero. The default value is 116.
> > +
> > +@item th_di
> > +Set the minimum length of a sequence in frames to recognize it as matching
> > +sequence. The option value must be a non negative integer value.
> > +The default value is 0.
> > +
> > +@item th_it
> > +Set the minimum relation, that matching frames to all frames must have.
> > +The option value must be a double value between 0 and 1. The default value
> > is 0.5.
> > +@end table
> > +
> > +@subsection Examples
> > +
> > +@itemize
> > +@item
> > +To calculate the signature of an input video and store it in signature.xml:
> > +@example
> > +ffmpeg -i input.mkv -vf signature=filename=signature.xml -map 0:v -c
> > rawvideo -f null -
> > +@end example
>
> the output seems to differ between 32 an 64bit x86
> this would make any regression testing rather difficult
> why is there a difference ? can this be avoided or would that result in
> some disadvantage ?
This is due to this line:
sum -= ((double) blocksum)/(blocksize * denum);
sum was a double. It seems the difference leads to different results in 32 and
64 bit
(the 5 decimal place). I have reworked the filter part so it does not use
double at all.
This also leads in some fewer divisions, but the numbers get really big. The
relevant
parts use int63_t.
If the videos gets really big, the numbers could overflow. Can I restrict this
someway?
An upper bound could be find with:
255 * BLOCK_LCM * (width/32+1)^2 * (height/32+1)^2 < 2^63
I tested it with 4K (UHD) input. This does not give any problems, but it is
near the limit.
(As a note: Especially 4K is a certain amount under the limit, because the
width 3840 is
dividable by 32, so the square in the above formula could be deleted)
The filter should generate the same signatures as in 64 bit before, now with 32
and 64 bit.
>
>
> [...]
>
> > +static unsigned int intersection_word(uint8_t *first, uint8_t *second)
> > +{
> > + unsigned int val=0,i;
> > + for(i=0; i < 28; i+=4){
> > + val += av_popcount( (first[i] & second[i] ) << 24 |
> > + (first[i+1] & second[i+1]) << 16 |
> > + (first[i+2] & second[i+2]) << 8 |
> > + (first[i+3] & second[i+3]) );
>
> see AV_RN32() and similar functions
> (make sure that if you pick one that requires alignment that alignment
> is provided)
If I get it right, the 4 8-bit numbers are concatenated to 32 bit (AV_RN32),
then again
split into 16 bit (put_bits32) and finally written in 8 bit pieces into the
stream (put_bits).
I've changed the code, that is uses put_bits(..., 8, ...) directly (definitely
simplifies the code,
don't know whether it changes the performance).
>
>
> > + }
> > + val += av_popcount( (first[28] & second[28]) << 16 |
> > + (first[29] & second[29]) << 8 |
> > + (first[30] & second[30]) );
> > + return val;
> > +}
> > +
>
> > +static unsigned int union_word(uint8_t *first, uint8_t *second)
>
> unchanged pointer arguments could be marked as const
done
>
>
> [...]
>
> > +static MatchingInfo* get_matching_parameters(AVFilterContext *ctx,
> > SignatureContext *sc, FineSignature *first, FineSignature *second)
> > +{
> > + FineSignature *f,*s;
> > + size_t i, j, k, l, hmax = 0, score;
> > + int framerate, offset, l1dist;
> > + double m;
> > + MatchingInfo *cands = NULL, *c = NULL;
> > +
> > + struct {
> > + uint8_t size;
> > + unsigned int dist;
> > + FineSignature *a;
> > + uint8_t b_pos[COURSE_SIZE];
> > + FineSignature *b[COURSE_SIZE];
> > + } pairs[COURSE_SIZE];
> > +
> > + struct {
> > + int dist;
> > + size_t score;
> > + FineSignature *a;
> > + FineSignature *b;
> > + } hspace[MAX_FRAMERATE][2*HOUGH_MAX_OFFSET+1]; /* houghspace */
>
> stack space is not unlimited, some platforms have rather little
> i dont know if above is too large but it might be
This is 60*(2*90+1) = 11K. This is taken from the reference code, althought the
lookup itself
is not standardized. Nevertheless I don't see an easy way to reduce this.
The houghspace represents a matrix. Theoretically it could be possible to use a
list
instead of a matrix, but this would lead to clearly more complicated code.
If you find it better I can allocate the space in the heap. Maybe this solves
the problem.
>
>
> > +
> > +
> > + /* l1 distances */
> > + for(i = 0, f = first; i < COURSE_SIZE && f->next; i++, f = f->next){
> > + pairs[i].size = 0;
> > + pairs[i].dist = 99999;
> > + pairs[i].a = f;
> > + for(j = 0, s = second; j < COURSE_SIZE && s->next; j++, s =
> > s->next){
> > + /* l1 distance of finesignature */
> > + l1dist = get_l1dist(ctx, sc, f->framesig, s->framesig);
> > + if(l1dist < sc->thl1){
> > + if(l1dist < pairs[i].dist){
> > + pairs[i].size = 1;
> > + pairs[i].dist = l1dist;
> > + pairs[i].b_pos[0] = j;
> > + pairs[i].b[0] = s;
> > + } else if(l1dist == pairs[i].dist){
> > + pairs[i].b[pairs[i].size] = s;
> > + pairs[i].b_pos[pairs[i].size] = j;
> > + pairs[i].size++;
> > + }
> > + }
> > + }
> > + }
> > + /* last incomplete coursesignature */
> > + if(f->next == NULL){
> > + for(; i < COURSE_SIZE; i++){
> > + pairs[i].size = 0;
> > + pairs[i].dist = 99999;
> > + }
> > + }
> > +
> > + /* initialize houghspace */
> > + for(i = 0; i < MAX_FRAMERATE; i++){
> > + for(j = 0; j < HOUGH_MAX_OFFSET; j++){
> > + hspace[i][j].score = 0;
> > + hspace[i][j].dist = 99999;
> > + }
> > + }
> > +
> > + /* hough transformation */
> > + for(i = 0; i < COURSE_SIZE; i++){
> > + for(j = 0; j < pairs[i].size; j++){
> > + for(k = i+1; k < COURSE_SIZE; k++){
> > + for(l = 0; l < pairs[k].size; l++){
> > + if(pairs[i].b[j] != pairs[k].b[l]){
> > + /* linear regression */
> > + m = (pairs[k].b_pos[l]-pairs[i].b_pos[j]) / (k-i);
> > /* good value between 0.0 - 2.0 */
> > + framerate = (int) m*30 + 0.5; /* round up to 0 -
> > 60 */
> > + if(framerate>0 && framerate <= MAX_FRAMERATE){
> > + offset = pairs[i].b_pos[j] - ((int) m*i +
> > 0.5); /* only second part has to be rounded up */
> > + if(offset > -HOUGH_MAX_OFFSET && offset <
> > HOUGH_MAX_OFFSET){
> > + if(pairs[i].dist < pairs[k].dist){
> > + if(pairs[i].dist <
> > hspace[framerate-1][offset+HOUGH_MAX_OFFSET].dist){
> > +
> > hspace[framerate-1][offset+HOUGH_MAX_OFFSET].dist = pairs[i].dist;
> > +
> > hspace[framerate-1][offset+HOUGH_MAX_OFFSET].a = pairs[i].a;
> > +
> > hspace[framerate-1][offset+HOUGH_MAX_OFFSET].b = pairs[i].b[j];
> > + }
> > + } else {
> > + if(pairs[k].dist <
> > hspace[framerate-1][offset+HOUGH_MAX_OFFSET].dist){
> > +
> > hspace[framerate-1][offset+HOUGH_MAX_OFFSET].dist = pairs[k].dist;
> > +
> > hspace[framerate-1][offset+HOUGH_MAX_OFFSET].a = pairs[k].a;
> > +
> > hspace[framerate-1][offset+HOUGH_MAX_OFFSET].b = pairs[k].b[l];
> > + }
> > + }
> > +
> > + score =
> > hspace[framerate-1][offset+HOUGH_MAX_OFFSET].score + 1;
> > + if(score > hmax)
> > + hmax = score;
> > +
> > hspace[framerate-1][offset+HOUGH_MAX_OFFSET].score = score;
> > + }
> > + }
> > + }
> > + }
> > + }
> > + }
> > + }
> > +
> > + if(hmax > 0){
> > + hmax = (int) (0.7*hmax);
> > + for(i = 0; i < MAX_FRAMERATE; i++){
> > + for(j = 0; j < HOUGH_MAX_OFFSET; j++){
> > + if(hmax < hspace[i][j].score){
> > + if(c == NULL){
> > + c = av_malloc(sizeof(MatchingInfo));
> > + if (!c)
> > + av_log(ctx, AV_LOG_FATAL, "Could not allocate
> > memory");
> > + cands = c;
> > + } else {
> > + c->next = av_malloc(sizeof(MatchingInfo));
> > + if (!c->next)
> > + av_log(ctx, AV_LOG_FATAL, "Could not allocate
> > memory");
> > + c = c->next;
> > + }
> > + c->framerateratio = (i+1.0) / 30;
> > + c->score = hspace[i][j].score;
> > + c->offset = j-90;
> > + c->first = hspace[i][j].a;
> > + c->second = hspace[i][j].b;
> > + c->next = NULL;
> > +
> > + /* not used */
> > + c->meandist = 0;
> > + c->matchframes = 0;
> > + c->whole = 0;
> > + }
> > + }
> > + }
> > + }
> > + return cands;
> > +}
> > +
>
> [...]
> > +static int filter_frame(AVFilterLink *inlink, AVFrame *picref)
> > +{
> > + AVFilterContext *ctx = inlink->dst;
> > + SignatureContext *sic = ctx->priv;
> > + StreamContext *sc = &(sic->streamcontexts[FF_INLINK_IDX(inlink)]);
> > + FineSignature* fs;
> > +
> > + static const uint8_t pot3[5] = { 3*3*3*3, 3*3*3, 3*3, 3, 1 };
> > + /* indexes of words : 210,217,219,274,334 44,175,233,270,273
> > 57,70,103,237,269 100,285,295,337,354 101,102,111,275,296
> > + s2usw = sorted to unsorted wordvec: 44 is at index 5, 57 at index 10...
> > + */
> > + static const unsigned int wordvec[25] =
> > {44,57,70,100,101,102,103,111,175,210,217,219,233,237,269,270,273,274,275,285,295,296,334,337,354};
> > + static const uint8_t s2usw[25] = { 5,10,11, 15, 20, 21, 12, 22, 6,
> > 0, 1, 2, 7, 13, 14, 8, 9, 3, 23, 16, 17, 24, 4, 18, 19};
> > +
> > + uint8_t wordt2b[5] = { 0, 0, 0, 0, 0 }; /* word ternary to binary */
> > + uint64_t intpic[32][32];
> > + uint64_t rowcount;
> > + uint8_t *p = picref->data[0];
> > + int inti, intj;
> > + int *intjlut;
> > +
> > + double conflist[DIFFELEM_SIZE];
> > + int f = 0, g = 0, w = 0;
> > + int dh1 = 1, dh2 = 1, dw1 = 1, dw2 = 1, denum, a, b;
> > + int i,j,k,ternary;
> > + uint64_t blocksum;
> > + int blocksize;
> > + double th; /* threshold */
> > + double sum;
> > +
> > + /* initialize fs */
> > + if(sc->curfinesig){
> > + fs = av_mallocz(sizeof(FineSignature));
> > + if (!fs)
> > + return AVERROR(ENOMEM);
> > + sc->curfinesig->next = fs;
> > + fs->prev = sc->curfinesig;
> > + sc->curfinesig = fs;
> > + }else{
> > + fs = sc->curfinesig = sc->finesiglist;
> > + sc->curcoursesig1->first = fs;
> > + }
> > +
> > + fs->pts = picref->pts;
> > + fs->index = sc->lastindex++;
> > +
> > + memset(intpic, 0, sizeof(uint64_t)*32*32);
> > + intjlut = av_malloc(inlink->w * sizeof(int));
> > + if (!intjlut)
> > + return AVERROR(ENOMEM);
> > + for (i=0; i < inlink->w; i++){
> > + intjlut[i] = (i<<5)/inlink->w;
> > + }
> > +
> > + for (i=0; i < inlink->h; i++){
> > + inti = (i<<5)/inlink->h;
> > + for (j=0; j< inlink->w; j++){
> > + intj = intjlut[j];
> > + intpic[inti][intj] += p[j];
> > + }
> > + p += picref->linesize[0];
> > + }
> > + av_free(intjlut);
>
> av_freep() is safer as use of freed memor becomes harder and more
> noticable
I don't get the function completely. Could you explain a little? Problem is
that I can use
it exactly there. Replacing other occurences of av_free results in a segfault.
>
>
> > +
> > + /* The following calculate a summed area table (intpic) and brings the
> > numbers
> > + * in intpic to to the same denuminator.
> > + * So you only have to handle the numinator in the following sections.
> > + */
> > + dh1 = inlink->h/32;
> > + if (inlink->h%32)
> > + dh2 = dh1 + 1;
> > + dw1 = inlink->w/32;
> > + if (inlink->w%32)
> > + dw2 = dw1 + 1;
> > + denum = dh1 * dh2 * dw1 * dw2;
> > +
> > + for (i=0; i<32; i++){
> > + rowcount = 0;
> > + a = 1;
> > + if (dh2 > 1) {
> > + a = ((inlink->h*(i+1))%32 == 0) ? (inlink->h*(i+1))/32 - 1 :
> > (inlink->h*(i+1))/32;
> > + a -= ((inlink->h*i)%32 == 0) ? (inlink->h*i)/32 - 1 :
> > (inlink->h*i)/32;
> > + a = (a == dh1)? dh2 : dh1;
> > + }
> > + for (j=0; j<32; j++){
> > + b = 1;
> > + if (dw2 > 1) {
> > + b = ((inlink->w*(j+1))%32 == 0) ? (inlink->w*(j+1))/32 - 1
> > : (inlink->w*(j+1))/32;
> > + b -= ((inlink->w*j)%32 == 0) ? (inlink->w*j)/32 - 1 :
> > (inlink->w*j)/32;
> > + b = (b == dw1)? dw2 : dw1;
> > + }
> > + rowcount += intpic[i][j] *= a * b;
> > + if(i>0){
> > + intpic[i][j] = intpic[i-1][j] + rowcount;
> > + } else {
> > + intpic[i][j] = rowcount;
> > + }
> > + }
> > + }
> > +
> > + for (i=0; i< ELEMENT_COUNT; i++){
> > + const ElemCat* elemcat = elements[i];
>
> > + double* elemsignature = av_malloc(sizeof(double) *
> > elemcat->elem_count);
> > + double* sortsignature = av_malloc(sizeof(double) *
> > elemcat->elem_count);
>
> av_malloc_array()
done
>
> > + if (!elemsignature || !sortsignature)
> > + return AVERROR(ENOMEM);
>
> memleak
hopefully fixed
from my previous mails:
> BTW is division by 2 optimized out or it is better to use >> 1 ?
> - The timebase of the testfiles is 90000. In the binary output unfortunately
> there
> is only place for a 16 bit number, so this don't fit. Currently the code
> simply crop
> remaining bits. Is there a better solution (devide with some number etc)?
Would be nice, if you could comment.
Then I added a few TODOs in the code, was about parts I don't know. Would be
nice,
if you comment there, too.
I attached the new (complete) patch, the diff to the last time and the updated
check script.
Gerion
>From 9646ed6f0cf78356cf2914a60705c98d8f21fe8a Mon Sep 17 00:00:00 2001
From: Gerion Entrup <gerion.ent...@flump.de>
Date: Sun, 20 Mar 2016 11:10:31 +0100
Subject: [PATCH] add signature filter for MPEG7 video signature
This filter does not implement all features of MPEG7. Missing features:
- compression of signature files
- work only on (cropped) parts of the video
---
Changelog | 1 +
configure | 1 +
doc/filters.texi | 70 ++++
libavfilter/Makefile | 1 +
libavfilter/allfilters.c | 1 +
libavfilter/signature.h | 554 ++++++++++++++++++++++++++++++
libavfilter/signature_lookup.c | 550 ++++++++++++++++++++++++++++++
libavfilter/version.h | 4 +-
libavfilter/vf_signature.c | 741 +++++++++++++++++++++++++++++++++++++++++
9 files changed, 1921 insertions(+), 2 deletions(-)
create mode 100644 libavfilter/signature.h
create mode 100644 libavfilter/signature_lookup.c
create mode 100644 libavfilter/vf_signature.c
diff --git a/Changelog b/Changelog
index 7b0187d..8a2b7fd 100644
--- a/Changelog
+++ b/Changelog
@@ -18,6 +18,7 @@ version <next>:
- coreimage filter (GPU based image filtering on OSX)
- libdcadec removed
- bitstream filter for extracting DTS core
+- MPEG-7 Video Signature filter
version 3.0:
- Common Encryption (CENC) MP4 encoding and decoding support
diff --git a/configure b/configure
index e550547..fe29827 100755
--- a/configure
+++ b/configure
@@ -2979,6 +2979,7 @@ showspectrum_filter_deps="avcodec"
showspectrum_filter_select="fft"
showspectrumpic_filter_deps="avcodec"
showspectrumpic_filter_select="fft"
+signature_filter_deps="gpl avcodec avformat"
smartblur_filter_deps="gpl swscale"
sofalizer_filter_deps="netcdf avcodec"
sofalizer_filter_select="fft"
diff --git a/doc/filters.texi b/doc/filters.texi
index 5d6cf52..a95f5a7 100644
--- a/doc/filters.texi
+++ b/doc/filters.texi
@@ -11559,6 +11559,76 @@ saturation maximum: %@{metadata:lavfi.signalstats.SATMAX@}
@end example
@end itemize
+@anchor{signature}
+@section signature
+
+Calculates the MPEG-7 Video Signature. The filter could handle more than one
+input. In this case the matching between the inputs could be calculated. The
+filter passthrough the first input. The output is written in XML.
+
+It accepts the following options:
+
+@table @option
+@item mode
+Enable the calculation of the matching. The option value must be 0 (to disable
+or 1 (to enable). Optionally you can set the mode to 2. Then the detection ends,
+if the first matching sequence it reached. This should be slightly faster.
+Per default the detection is disabled.
+
+@item nb_inputs
+Set the number of inputs. The option value must be a non negative interger.
+Default value is 1.
+
+@item filename
+Set the path to witch the output is written. If there is more than one input,
+the path must be a prototype, i.e. must contain %d or %0nd (where n is a positive
+integer), that will be replaced with the input number. If no filename is
+specified, no output will be written. This is the default.
+
+@item xml
+Choose the output format. If set to 1 the filter will write XML, if set to 0
+the filter will write binary output. The default is 0.
+
+@item th_d
+Set threshold to detect one word as similar. The option value must be an integer
+greater than zero. The default value is 9000.
+
+@item th_dc
+Set threshold to detect all words as similar. The option value must be an integer
+greater than zero. The default value is 60000.
+
+@item th_xh
+Set threshold to detect frames as similar. The option value must be an integer
+greater than zero. The default value is 116.
+
+@item th_di
+Set the minimum length of a sequence in frames to recognize it as matching
+sequence. The option value must be a non negative integer value.
+The default value is 0.
+
+@item th_it
+Set the minimum relation, that matching frames to all frames must have.
+The option value must be a double value between 0 and 1. The default value is 0.5.
+@end table
+
+@subsection Examples
+
+@itemize
+@item
+To calculate the signature of an input video and store it in signature.xml:
+@example
+ffmpeg -i input.mkv -vf signature=filename=signature.xml -map 0:v -c rawvideo -f null -
+@end example
+
+@item
+To detect whether two videos matches and store the signatures in
+signature0.xml and signature1.xml:
+@example
+ffmpeg -i input1.mkv -i input2.mkv -filter_complex "[0:0][1:0] signature=nb_inputs=2:detectmode=1signature%d.xml" -map 0:v -map 1:v -c rawvideo -f null -
+@end example
+
+@end itemize
+
@anchor{smartblur}
@section smartblur
diff --git a/libavfilter/Makefile b/libavfilter/Makefile
index b6e1999..9cd0d22 100644
--- a/libavfilter/Makefile
+++ b/libavfilter/Makefile
@@ -246,6 +246,7 @@ OBJS-$(CONFIG_SHOWPALETTE_FILTER) += vf_showpalette.o
OBJS-$(CONFIG_SHUFFLEFRAMES_FILTER) += vf_shuffleframes.o
OBJS-$(CONFIG_SHUFFLEPLANES_FILTER) += vf_shuffleplanes.o
OBJS-$(CONFIG_SIGNALSTATS_FILTER) += vf_signalstats.o
+OBJS-$(CONFIG_SIGNATURE_FILTER) += vf_signature.o
OBJS-$(CONFIG_SMARTBLUR_FILTER) += vf_smartblur.o
OBJS-$(CONFIG_SPLIT_FILTER) += split.o
OBJS-$(CONFIG_SPP_FILTER) += vf_spp.o
diff --git a/libavfilter/allfilters.c b/libavfilter/allfilters.c
index 5c18fd1..2946186 100644
--- a/libavfilter/allfilters.c
+++ b/libavfilter/allfilters.c
@@ -266,6 +266,7 @@ void avfilter_register_all(void)
REGISTER_FILTER(SHUFFLEFRAMES, shuffleframes, vf);
REGISTER_FILTER(SHUFFLEPLANES, shuffleplanes, vf);
REGISTER_FILTER(SIGNALSTATS, signalstats, vf);
+ REGISTER_FILTER(SIGNATURE, signature, vf);
REGISTER_FILTER(SMARTBLUR, smartblur, vf);
REGISTER_FILTER(SPLIT, split, vf);
REGISTER_FILTER(SPP, spp, vf);
diff --git a/libavfilter/signature.h b/libavfilter/signature.h
new file mode 100644
index 0000000..a22cab3
--- /dev/null
+++ b/libavfilter/signature.h
@@ -0,0 +1,554 @@
+/*
+ * Copyright (c) 2016 Gerion Entrup
+ *
+ * This file is part of FFmpeg.
+ *
+ * FFmpeg is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version.
+ *
+ * FFmpeg is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License along
+ * with FFmpeg; if not, write to the Free Software Foundation, Inc.,
+ * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
+ */
+
+/**
+ * @file
+ * MPEG-7 video signature calculation and lookup filter
+ */
+
+#ifndef AVFILTER_SIGNATURE_H
+#define AVFILTER_SIGNATURE_H
+
+#include <float.h>
+#include "libavutil/common.h"
+#include "libavutil/opt.h"
+#include "libavutil/timestamp.h"
+#include "avfilter.h"
+#include "internal.h"
+
+#define ELEMENT_COUNT 10
+#define SIGELEM_SIZE 380
+#define DIFFELEM_SIZE 348 /* SIGELEM_SIZE - elem_a1 - elem_a2 */
+#define COURSE_SIZE 90
+
+typedef struct {
+ uint8_t x;
+ uint8_t y;
+} Point;
+
+typedef struct {
+ Point up;
+ Point to;
+} Block;
+
+typedef struct {
+ int av_elem; /* average element category */
+ short left_count; /* count of blocks that will be added together */
+ short block_count; /* count of blocks per element */
+ short elem_count;
+ const Block* blocks;
+} ElemCat;
+
+typedef struct FineSignature{
+ struct FineSignature* next;
+ struct FineSignature* prev;
+ uint64_t pts;
+ uint32_t index; /* needed for xmlexport */
+ uint8_t confidence;
+ uint8_t words[5];
+ uint8_t framesig[SIGELEM_SIZE/5];
+} FineSignature;
+
+typedef struct CourseSignature{
+ uint8_t data[5][31]; /* 5 words with min. 243 bit */
+ struct FineSignature* first; /* associated Finesignatures */
+ struct FineSignature* last;
+ struct CourseSignature* next;
+} CourseSignature;
+
+/* lookup types */
+typedef struct MatchingInfo{
+ double meandist;
+ double framerateratio; /* second/first */
+ int score;
+ int offset;
+ int matchframes; /* number of matching frames */
+ int whole;
+ struct FineSignature* first;
+ struct FineSignature* second;
+ struct MatchingInfo* next;
+} MatchingInfo;
+
+typedef struct {
+ int x_coords[32];
+ int y_coords[32];
+ AVRational time_base;
+ /* needed for xml_export */
+ int w; /* height */
+ int h; /* width */
+
+ FineSignature* finesiglist;
+ FineSignature* curfinesig;
+
+ CourseSignature* coursesiglist;
+ CourseSignature* courseend; /* needed for xml export */
+ /* helpers to store the alternating signatures */
+ CourseSignature* curcoursesig1;
+ CourseSignature* curcoursesig2;
+
+ int coursecount; /* counter from 0 to 89 */
+ int midcourse; /* whether it is a coursesignature beginning from 45 + i * 90 */
+ uint32_t lastindex; /* helper to store amount of frames */
+} StreamContext;
+
+typedef struct {
+ const AVClass *class;
+ int mode;
+ int nb_inputs;
+ char *filename;
+ int xml; /* bool */
+ int thworddist;
+ int thcomposdist;
+ int thl1;
+ int thdi;
+ int thit;
+ uint8_t l1distlut[243*242/2]; /* 243 + 242 + 241 ... */
+ StreamContext* streamcontexts;
+} SignatureContext;
+
+
+static const Block elem_a1_data[] = {
+ {{ 0, 0},{ 7, 7}},
+ {{ 8, 0},{15, 7}},
+ {{ 0, 8},{ 7,15}},
+ {{ 8, 8},{15,15}},
+ {{16, 0},{23, 7}},
+ {{24, 0},{31, 7}},
+ {{16, 8},{23,15}},
+ {{24, 8},{31,15}},
+ {{ 0,16},{ 7,23}},
+ {{ 8,16},{15,23}},
+ {{ 0,24},{ 7,31}},
+ {{ 8,24},{15,31}},
+ {{16,16},{23,23}},
+ {{24,16},{31,23}},
+ {{16,24},{23,31}},
+ {{24,24},{31,31}},
+ {{ 0, 0},{15,15}},
+ {{16, 0},{31,15}},
+ {{ 0,16},{15,31}},
+ {{16,16},{31,31}}
+};
+static const ElemCat elem_a1 = { 1, 1, 1, 20, elem_a1_data };
+
+static const Block elem_a2_data[] = {
+ {{ 2, 2},{ 9, 9}},
+ {{12, 2},{19, 9}},
+ {{22, 2},{29, 9}},
+ {{ 2,12},{ 9,19}},
+ {{12,12},{19,19}},
+ {{22,12},{29,19}},
+ {{ 2,22},{ 9,29}},
+ {{12,22},{19,29}},
+ {{22,22},{29,29}},
+ {{ 9, 9},{22,22}},
+ {{ 6, 6},{25,25}},
+ {{ 3, 3},{28,28}}
+};
+static const ElemCat elem_a2 = { 1, 1, 1, 12, elem_a2_data };
+
+static const Block elem_d1_data[] = {
+ {{ 0, 0},{ 1, 3}},{{ 2, 0},{ 3, 3}},
+ {{ 4, 0},{ 7, 1}},{{ 4, 2},{ 7, 3}},
+ {{ 0, 6},{ 3, 7}},{{ 0, 4},{ 3, 5}},
+ {{ 6, 4},{ 7, 7}},{{ 4, 4},{ 5, 7}},
+ {{ 8, 0},{ 9, 3}},{{10, 0},{11, 3}},
+ {{12, 0},{15, 1}},{{12, 2},{15, 3}},
+ {{ 8, 6},{11, 7}},{{ 8, 4},{11, 5}},
+ {{14, 4},{15, 7}},{{12, 4},{13, 7}},
+ {{ 0, 8},{ 1,11}},{{ 2, 8},{ 3,11}},
+ {{ 4, 8},{ 7, 9}},{{ 4,10},{ 7,11}},
+ {{ 0,14},{ 3,15}},{{ 0,12},{ 3,13}},
+ {{ 6,12},{ 7,15}},{{ 4,12},{ 5,15}},
+ {{ 8, 8},{ 9,11}},{{10, 8},{11,11}},
+ {{12, 8},{15, 9}},{{12,10},{15,11}},
+ {{ 8,14},{11,15}},{{ 8,12},{11,13}},
+ {{14,12},{15,15}},{{12,12},{13,15}},
+ {{16, 0},{19, 1}},{{16, 2},{19, 3}},
+ {{22, 0},{23, 3}},{{20, 0},{21, 3}},
+ {{16, 4},{17, 7}},{{18, 4},{19, 7}},
+ {{20, 6},{23, 7}},{{20, 4},{23, 5}},
+ {{24, 0},{27, 1}},{{24, 2},{27, 3}},
+ {{30, 0},{31, 3}},{{28, 0},{29, 3}},
+ {{24, 4},{25, 7}},{{26, 4},{27, 7}},
+ {{28, 6},{31, 7}},{{28, 4},{31, 5}},
+ {{16, 8},{19, 9}},{{16,10},{19,11}},
+ {{22, 8},{23,11}},{{20, 8},{21,11}},
+ {{16,12},{17,15}},{{18,12},{19,15}},
+ {{20,14},{23,15}},{{20,12},{23,13}},
+ {{24, 8},{27, 9}},{{24,10},{27,11}},
+ {{30, 8},{31,11}},{{28, 8},{29,11}},
+ {{24,12},{25,15}},{{26,12},{27,15}},
+ {{28,14},{31,15}},{{28,12},{31,13}},
+ {{ 0,16},{ 3,17}},{{ 0,18},{ 3,19}},
+ {{ 6,16},{ 7,19}},{{ 4,16},{ 5,19}},
+ {{ 0,20},{ 1,23}},{{ 2,20},{ 3,23}},
+ {{ 4,22},{ 7,23}},{{ 4,20},{ 7,21}},
+ {{ 8,16},{11,17}},{{ 8,18},{11,19}},
+ {{14,16},{15,19}},{{12,16},{13,19}},
+ {{ 8,20},{ 9,23}},{{10,20},{11,23}},
+ {{12,22},{15,23}},{{12,20},{15,21}},
+ {{ 0,24},{ 3,25}},{{ 0,26},{ 3,27}},
+ {{ 6,24},{ 7,27}},{{ 4,24},{ 5,27}},
+ {{ 0,28},{ 1,31}},{{ 2,28},{ 3,31}},
+ {{ 4,30},{ 7,31}},{{ 4,28},{ 7,29}},
+ {{ 8,24},{11,25}},{{ 8,26},{11,27}},
+ {{14,24},{15,27}},{{12,24},{13,27}},
+ {{ 8,28},{ 9,31}},{{10,28},{11,31}},
+ {{12,30},{15,31}},{{12,28},{15,29}},
+ {{16,16},{17,19}},{{18,16},{19,19}},
+ {{20,16},{23,17}},{{20,18},{23,19}},
+ {{16,22},{19,23}},{{16,20},{19,21}},
+ {{22,20},{23,23}},{{20,20},{21,23}},
+ {{24,16},{25,19}},{{26,16},{27,19}},
+ {{28,16},{31,17}},{{28,18},{31,19}},
+ {{24,22},{27,23}},{{24,20},{27,21}},
+ {{30,20},{31,23}},{{28,20},{29,23}},
+ {{16,24},{17,27}},{{18,24},{19,27}},
+ {{20,24},{23,25}},{{20,26},{23,27}},
+ {{16,30},{19,31}},{{16,28},{19,29}},
+ {{22,28},{23,31}},{{20,28},{21,31}},
+ {{24,24},{25,27}},{{26,24},{27,27}},
+ {{28,24},{31,25}},{{28,26},{31,27}},
+ {{24,30},{27,31}},{{24,28},{27,29}},
+ {{30,28},{31,31}},{{28,28},{29,31}},
+ {{ 2, 2},{ 3, 5}},{{ 4, 2},{ 5, 5}},
+ {{ 6, 2},{ 9, 3}},{{ 6, 4},{ 9, 5}},
+ {{ 2, 8},{ 5, 9}},{{ 2, 6},{ 5, 7}},
+ {{ 8, 6},{ 9, 9}},{{ 6, 6},{ 7, 9}},
+ {{12, 2},{13, 5}},{{14, 2},{15, 5}},
+ {{16, 2},{19, 3}},{{16, 4},{19, 5}},
+ {{12, 8},{15, 9}},{{12, 6},{15, 7}},
+ {{18, 6},{19, 9}},{{16, 6},{17, 9}},
+ {{22, 2},{23, 5}},{{24, 2},{25, 5}},
+ {{26, 2},{29, 3}},{{26, 4},{29, 5}},
+ {{22, 8},{25, 9}},{{22, 6},{25, 7}},
+ {{28, 6},{29, 9}},{{26, 6},{27, 9}},
+ {{ 2,12},{ 3,15}},{{ 4,12},{ 5,15}},
+ {{ 6,12},{ 9,13}},{{ 6,14},{ 9,15}},
+ {{ 2,18},{ 5,19}},{{ 2,16},{ 5,17}},
+ {{ 8,16},{ 9,19}},{{ 6,16},{ 7,19}},
+ {{12,12},{15,13}},{{12,14},{15,15}},
+ {{16,12},{19,13}},{{16,14},{19,15}},
+ {{12,18},{15,19}},{{12,16},{15,17}},
+ {{16,18},{19,19}},{{16,16},{19,17}},
+ {{22,12},{23,15}},{{24,12},{25,15}},
+ {{26,12},{29,13}},{{26,14},{29,15}},
+ {{22,18},{25,19}},{{22,16},{25,17}},
+ {{28,16},{29,19}},{{26,16},{27,19}},
+ {{ 2,22},{ 3,25}},{{ 4,22},{ 5,25}},
+ {{ 6,22},{ 9,23}},{{ 6,24},{ 9,25}},
+ {{ 2,28},{ 5,29}},{{ 2,26},{ 5,27}},
+ {{ 8,26},{ 9,29}},{{ 6,26},{ 7,29}},
+ {{12,22},{13,25}},{{14,22},{15,25}},
+ {{16,22},{19,23}},{{16,24},{19,25}},
+ {{12,28},{15,29}},{{12,26},{15,27}},
+ {{18,26},{19,29}},{{16,26},{17,29}},
+ {{22,22},{23,25}},{{24,22},{25,25}},
+ {{26,22},{29,23}},{{26,24},{29,25}},
+ {{22,28},{25,29}},{{22,26},{25,27}},
+ {{28,26},{29,29}},{{26,26},{27,29}},
+ {{ 7, 7},{10, 8}},{{ 7, 9},{10,10}},
+ {{11, 7},{12,10}},{{13, 7},{14,10}},
+ {{ 7,11},{ 8,14}},{{ 9,11},{10,14}},
+ {{11,11},{14,12}},{{11,13},{14,14}},
+ {{17, 7},{20, 8}},{{17, 9},{20,10}},
+ {{21, 7},{22,10}},{{23, 7},{24,10}},
+ {{17,11},{18,14}},{{19,11},{20,14}},
+ {{21,11},{24,12}},{{21,13},{24,14}},
+ {{ 7,17},{10,18}},{{ 7,19},{10,20}},
+ {{11,17},{12,20}},{{13,17},{14,20}},
+ {{ 7,21},{ 8,24}},{{ 9,21},{10,24}},
+ {{11,21},{14,22}},{{11,23},{14,24}},
+ {{17,17},{20,18}},{{17,19},{20,20}},
+ {{21,17},{22,20}},{{23,17},{24,20}},
+ {{17,21},{18,24}},{{19,21},{20,24}},
+ {{21,21},{24,22}},{{21,23},{24,24}}
+};
+static const ElemCat elem_d1 = { 0, 1, 2, 116, elem_d1_data };
+
+static const Block elem_d2_data[] = {
+ {{ 0, 0},{ 3, 3}},{{ 4, 4},{ 7, 7}},{{ 4, 0},{ 7, 3}},{{ 0, 4},{ 3, 7}},
+ {{ 8, 0},{11, 3}},{{12, 4},{15, 7}},{{12, 0},{15, 3}},{{ 8, 4},{11, 7}},
+ {{16, 0},{19, 3}},{{20, 4},{23, 7}},{{20, 0},{23, 3}},{{16, 4},{19, 7}},
+ {{24, 0},{27, 3}},{{28, 4},{31, 7}},{{28, 0},{31, 3}},{{24, 4},{27, 7}},
+ {{ 0, 8},{ 3,11}},{{ 4,12},{ 7,15}},{{ 4, 8},{ 7,11}},{{ 0,12},{ 3,15}},
+ {{ 8, 8},{11,11}},{{12,12},{15,15}},{{12, 8},{15,11}},{{ 8,12},{11,15}},
+ {{16, 8},{19,11}},{{20,12},{23,15}},{{20, 8},{23,11}},{{16,12},{19,15}},
+ {{24, 8},{27,11}},{{28,12},{31,15}},{{28, 8},{31,11}},{{24,12},{27,15}},
+ {{ 0,16},{ 3,19}},{{ 4,20},{ 7,23}},{{ 4,16},{ 7,19}},{{ 0,20},{ 3,23}},
+ {{ 8,16},{11,19}},{{12,20},{15,23}},{{12,16},{15,19}},{{ 8,20},{11,23}},
+ {{16,16},{19,19}},{{20,20},{23,23}},{{20,16},{23,19}},{{16,20},{19,23}},
+ {{24,16},{27,19}},{{28,20},{31,23}},{{28,16},{31,19}},{{24,20},{27,23}},
+ {{ 0,24},{ 3,27}},{{ 4,28},{ 7,31}},{{ 4,24},{ 7,27}},{{ 0,28},{ 3,31}},
+ {{ 8,24},{11,27}},{{12,28},{15,31}},{{12,24},{15,27}},{{ 8,28},{11,31}},
+ {{16,24},{19,27}},{{20,28},{23,31}},{{20,24},{23,27}},{{16,28},{19,31}},
+ {{24,24},{27,27}},{{28,28},{31,31}},{{28,24},{31,27}},{{24,28},{27,31}},
+ {{ 4, 4},{ 7, 7}},{{ 8, 8},{11,11}},{{ 8, 4},{11, 7}},{{ 4, 8},{ 7,11}},
+ {{12, 4},{15, 7}},{{16, 8},{19,11}},{{16, 4},{19, 7}},{{12, 8},{15,11}},
+ {{20, 4},{23, 7}},{{24, 8},{27,11}},{{24, 4},{27, 7}},{{20, 8},{23,11}},
+ {{ 4,12},{ 7,15}},{{ 8,16},{11,19}},{{ 8,12},{11,15}},{{ 4,16},{ 7,19}},
+ {{12,12},{15,15}},{{16,16},{19,19}},{{16,12},{19,15}},{{12,16},{15,19}},
+ {{20,12},{23,15}},{{24,16},{27,19}},{{24,12},{27,15}},{{20,16},{23,19}},
+ {{ 4,20},{ 7,23}},{{ 8,24},{11,27}},{{ 8,20},{11,23}},{{ 4,24},{ 7,27}},
+ {{12,20},{15,23}},{{16,24},{19,27}},{{16,20},{19,23}},{{12,24},{15,27}},
+ {{20,20},{23,23}},{{24,24},{27,27}},{{24,20},{27,23}},{{20,24},{23,27}}
+};
+static const ElemCat elem_d2 = { 0, 2, 4, 25, elem_d2_data };
+
+static const Block elem_d3_data[] = {
+ {{ 1, 1},{10,10}},{{11, 1},{20,10}},
+ {{ 1, 1},{10,10}},{{21, 1},{30,10}},
+ {{ 1, 1},{10,10}},{{ 1,11},{10,20}},
+ {{ 1, 1},{10,10}},{{11,11},{20,20}},
+ {{ 1, 1},{10,10}},{{21,11},{30,20}},
+ {{ 1, 1},{10,10}},{{ 1,21},{10,30}},
+ {{ 1, 1},{10,10}},{{11,21},{20,30}},
+ {{ 1, 1},{10,10}},{{21,21},{30,30}},
+ {{11, 1},{20,10}},{{21, 1},{30,10}},
+ {{11, 1},{20,10}},{{ 1,11},{10,20}},
+ {{11, 1},{20,10}},{{11,11},{20,20}},
+ {{11, 1},{20,10}},{{21,11},{30,20}},
+ {{11, 1},{20,10}},{{ 1,21},{10,30}},
+ {{11, 1},{20,10}},{{11,21},{20,30}},
+ {{11, 1},{20,10}},{{21,21},{30,30}},
+ {{21, 1},{30,10}},{{ 1,11},{10,20}},
+ {{21, 1},{30,10}},{{11,11},{20,20}},
+ {{21, 1},{30,10}},{{21,11},{30,20}},
+ {{21, 1},{30,10}},{{ 1,21},{10,30}},
+ {{21, 1},{30,10}},{{11,21},{20,30}},
+ {{21, 1},{30,10}},{{21,21},{30,30}},
+ {{ 1,11},{10,20}},{{11,11},{20,20}},
+ {{ 1,11},{10,20}},{{21,11},{30,20}},
+ {{ 1,11},{10,20}},{{ 1,21},{10,30}},
+ {{ 1,11},{10,20}},{{11,21},{20,30}},
+ {{ 1,11},{10,20}},{{21,21},{30,30}},
+ {{11,11},{20,20}},{{21,11},{30,20}},
+ {{11,11},{20,20}},{{ 1,21},{10,30}},
+ {{11,11},{20,20}},{{11,21},{20,30}},
+ {{11,11},{20,20}},{{21,21},{30,30}},
+ {{21,11},{30,20}},{{ 1,21},{10,30}},
+ {{21,11},{30,20}},{{11,21},{20,30}},
+ {{21,11},{30,20}},{{21,21},{30,30}},
+ {{ 1,21},{10,30}},{{11,21},{20,30}},
+ {{ 1,21},{10,30}},{{21,21},{30,30}},
+ {{11,21},{20,30}},{{21,21},{30,30}}
+};
+static const ElemCat elem_d3 = { 0, 1, 2, 36, elem_d3_data };
+
+static const Block elem_d4_data[] = {
+ {{ 7,13},{12,18}},{{19,13},{24,18}},
+ {{13, 7},{18,12}},{{13,19},{18,24}},
+ {{ 7, 7},{12,12}},{{19,19},{24,24}},
+ {{19, 7},{24,12}},{{ 7,19},{12,24}},
+ {{13, 7},{18,12}},{{19,13},{24,18}},
+ {{19,13},{24,18}},{{13,19},{18,24}},
+ {{13,19},{18,24}},{{ 7,13},{12,18}},
+ {{ 7,13},{12,18}},{{13, 7},{18,12}},
+ {{ 7, 7},{12,12}},{{19, 7},{24,12}},
+ {{19, 7},{24,12}},{{19,19},{24,24}},
+ {{19,19},{24,24}},{{ 7,19},{12,24}},
+ {{ 7,19},{12,24}},{{ 7, 7},{12,12}},
+ {{13,13},{18,18}},{{13, 1},{18, 6}},
+ {{13,13},{18,18}},{{25,13},{30,18}},
+ {{13,13},{18,18}},{{13,25},{18,30}},
+ {{13,13},{18,18}},{{ 1,13},{ 6,18}},
+ {{13, 1},{18, 6}},{{13,25},{18,30}},
+ {{ 1,13},{ 6,18}},{{25,13},{30,18}},
+ {{ 7, 1},{12, 6}},{{19, 1},{24, 6}},
+ {{ 7,25},{12,30}},{{19,25},{24,30}},
+ {{ 1, 7},{ 6,12}},{{ 1,19},{ 6,24}},
+ {{25, 7},{30,12}},{{25,19},{30,24}},
+ {{ 7, 1},{12, 6}},{{ 1, 7},{ 6,12}},
+ {{19, 1},{24, 6}},{{25, 7},{30,12}},
+ {{25,19},{30,24}},{{19,25},{24,30}},
+ {{ 1,19},{ 6,24}},{{ 7,25},{12,30}},
+ {{ 1, 1},{ 6, 6}},{{25, 1},{30, 6}},
+ {{25, 1},{30, 6}},{{25,25},{30,30}},
+ {{25,25},{30,30}},{{ 1,25},{ 6,30}},
+ {{ 1,25},{ 6,30}},{{ 1, 1},{ 6, 6}}
+};
+static const ElemCat elem_d4 = { 0, 1, 2, 30, elem_d4_data };
+
+static const Block elem_d5_data[] = {
+ {{ 1, 1},{10, 3}},{{ 1, 4},{ 3, 7}},{{ 8, 4},{10, 7}},{{ 1, 8},{10,10}},{{ 4, 4},{ 7, 7}},
+ {{11, 1},{20, 3}},{{11, 4},{13, 7}},{{18, 4},{20, 7}},{{11, 8},{20,10}},{{14, 4},{17, 7}},
+ {{21, 1},{30, 3}},{{21, 4},{23, 7}},{{28, 4},{30, 7}},{{21, 8},{30,10}},{{24, 4},{27, 7}},
+ {{ 1,11},{10,13}},{{ 1,14},{ 3,17}},{{ 8,14},{10,17}},{{ 1,18},{10,20}},{{ 4,14},{ 7,17}},
+ {{11,11},{20,13}},{{11,14},{13,17}},{{18,14},{20,17}},{{11,18},{20,20}},{{14,14},{17,17}},
+ {{21,11},{30,13}},{{21,14},{23,17}},{{28,14},{30,17}},{{21,18},{30,20}},{{24,14},{27,17}},
+ {{ 1,21},{10,23}},{{ 1,24},{ 3,27}},{{ 8,24},{10,27}},{{ 1,28},{10,30}},{{ 4,24},{ 7,27}},
+ {{11,21},{20,23}},{{11,24},{13,27}},{{18,24},{20,27}},{{11,28},{20,30}},{{14,24},{17,27}},
+ {{21,21},{30,23}},{{21,24},{23,27}},{{28,24},{30,27}},{{21,28},{30,30}},{{24,24},{27,27}},
+ {{ 6, 6},{15, 8}},{{ 6, 9},{ 8,12}},{{13, 9},{15,12}},{{ 6,13},{15,15}},{{ 9, 9},{12,12}},
+ {{16, 6},{25, 8}},{{16, 9},{18,12}},{{23, 9},{25,12}},{{16,13},{25,15}},{{19, 9},{22,12}},
+ {{ 6,16},{15,18}},{{ 6,19},{ 8,22}},{{13,19},{15,22}},{{ 6,23},{15,25}},{{ 9,19},{12,22}},
+ {{16,16},{25,18}},{{16,19},{18,22}},{{23,19},{25,22}},{{16,23},{25,25}},{{19,19},{22,22}},
+ {{ 6, 1},{15, 3}},{{ 6, 4},{ 8, 7}},{{13, 4},{15, 7}},{{ 6, 8},{15,10}},{{ 9, 4},{12, 7}},
+ {{16, 1},{25, 3}},{{16, 4},{18, 7}},{{23, 4},{25, 7}},{{16, 8},{25,10}},{{19, 4},{22, 7}},
+ {{ 1, 6},{10, 8}},{{ 1, 9},{ 3,12}},{{ 8, 9},{10,12}},{{ 1,13},{10,15}},{{ 4, 9},{ 7,12}},
+ {{11, 6},{20, 8}},{{11, 9},{13,12}},{{18, 9},{20,12}},{{11,13},{20,15}},{{14, 9},{17,12}},
+ {{21, 6},{30, 8}},{{21, 9},{23,12}},{{28, 9},{30,12}},{{21,13},{30,15}},{{24, 9},{27,12}},
+ {{ 6,11},{15,13}},{{ 6,14},{ 8,17}},{{13,14},{15,17}},{{ 6,18},{15,20}},{{ 9,14},{12,17}},
+ {{16,11},{25,13}},{{16,14},{18,17}},{{23,14},{25,17}},{{16,18},{25,20}},{{19,14},{22,17}},
+ {{ 1,16},{10,18}},{{ 1,19},{ 3,22}},{{ 8,19},{10,22}},{{ 1,23},{10,25}},{{ 4,19},{ 7,22}},
+ {{11,16},{20,18}},{{11,19},{13,22}},{{18,19},{20,22}},{{11,23},{20,25}},{{14,19},{17,22}},
+ {{21,16},{30,18}},{{21,19},{23,22}},{{28,19},{30,22}},{{21,23},{30,25}},{{24,19},{27,22}},
+ {{ 6,21},{15,23}},{{ 6,24},{ 8,27}},{{13,24},{15,27}},{{ 6,28},{15,30}},{{ 9,24},{12,27}},
+ {{16,21},{25,23}},{{16,24},{18,27}},{{23,24},{25,27}},{{16,28},{25,30}},{{19,24},{22,27}},
+ {{ 2, 2},{14, 6}},{{ 2, 7},{ 6, 9}},{{10, 7},{14, 9}},{{ 2,10},{14,14}},{{ 7, 7},{ 9, 9}},
+ {{ 7, 2},{19, 6}},{{ 7, 7},{11, 9}},{{15, 7},{19, 9}},{{ 7,10},{19,14}},{{12, 7},{14, 9}},
+ {{12, 2},{24, 6}},{{12, 7},{16, 9}},{{20, 7},{24, 9}},{{12,10},{24,14}},{{17, 7},{19, 9}},
+ {{17, 2},{29, 6}},{{17, 7},{21, 9}},{{25, 7},{29, 9}},{{17,10},{29,14}},{{22, 7},{24, 9}},
+ {{ 2, 7},{14,11}},{{ 2,12},{ 6,14}},{{10,12},{14,14}},{{ 2,15},{14,19}},{{ 7,12},{ 9,14}},
+ {{ 7, 7},{19,11}},{{ 7,12},{11,14}},{{15,12},{19,14}},{{ 7,15},{19,19}},{{12,12},{14,14}},
+ {{12, 7},{24,11}},{{12,12},{16,14}},{{20,12},{24,14}},{{12,15},{24,19}},{{17,12},{19,14}},
+ {{17, 7},{29,11}},{{17,12},{21,14}},{{25,12},{29,14}},{{17,15},{29,19}},{{22,12},{24,14}},
+ {{ 2,12},{14,16}},{{ 2,17},{ 6,19}},{{10,17},{14,19}},{{ 2,20},{14,24}},{{ 7,17},{ 9,19}},
+ {{ 7,12},{19,16}},{{ 7,17},{11,19}},{{15,17},{19,19}},{{ 7,20},{19,24}},{{12,17},{14,19}},
+ {{12,12},{24,16}},{{12,17},{16,19}},{{20,17},{24,19}},{{12,20},{24,24}},{{17,17},{19,19}},
+ {{17,12},{29,16}},{{17,17},{21,19}},{{25,17},{29,19}},{{17,20},{29,24}},{{22,17},{24,19}},
+ {{ 2,17},{14,21}},{{ 2,22},{ 6,24}},{{10,22},{14,24}},{{ 2,25},{14,29}},{{ 7,22},{ 9,24}},
+ {{ 7,17},{19,21}},{{ 7,22},{11,24}},{{15,22},{19,24}},{{ 7,25},{19,29}},{{12,22},{14,24}},
+ {{12,17},{24,21}},{{12,22},{16,24}},{{20,22},{24,24}},{{12,25},{24,29}},{{17,22},{19,24}},
+ {{17,17},{29,21}},{{17,22},{21,24}},{{25,22},{29,24}},{{17,25},{29,29}},{{22,22},{24,24}},
+ {{ 8, 3},{13, 4}},{{ 8, 5},{ 9, 6}},{{12, 5},{13, 6}},{{ 8, 7},{13, 8}},{{10, 5},{11, 6}},
+ {{13, 3},{18, 4}},{{13, 5},{14, 6}},{{17, 5},{18, 6}},{{13, 7},{18, 8}},{{15, 5},{16, 6}},
+ {{18, 3},{23, 4}},{{18, 5},{19, 6}},{{22, 5},{23, 6}},{{18, 7},{23, 8}},{{20, 5},{21, 6}},
+ {{ 3, 8},{ 8, 9}},{{ 3,10},{ 4,11}},{{ 7,10},{ 8,11}},{{ 3,12},{ 8,13}},{{ 5,10},{ 6,11}},
+ {{ 8, 8},{13, 9}},{{ 8,10},{ 9,11}},{{12,10},{13,11}},{{ 8,12},{13,13}},{{10,10},{11,11}},
+ {{13, 8},{18, 9}},{{13,10},{14,11}},{{17,10},{18,11}},{{13,12},{18,13}},{{15,10},{16,11}},
+ {{18, 8},{23, 9}},{{18,10},{19,11}},{{22,10},{23,11}},{{18,12},{23,13}},{{20,10},{21,11}},
+ {{23, 8},{28, 9}},{{23,10},{24,11}},{{27,10},{28,11}},{{23,12},{28,13}},{{25,10},{26,11}},
+ {{ 3,13},{ 8,14}},{{ 3,15},{ 4,16}},{{ 7,15},{ 8,16}},{{ 3,17},{ 8,18}},{{ 5,15},{ 6,16}},
+ {{ 8,13},{13,14}},{{ 8,15},{ 9,16}},{{12,15},{13,16}},{{ 8,17},{13,18}},{{10,15},{11,16}},
+ {{13,13},{18,14}},{{13,15},{14,16}},{{17,15},{18,16}},{{13,17},{18,18}},{{15,15},{16,16}},
+ {{18,13},{23,14}},{{18,15},{19,16}},{{22,15},{23,16}},{{18,17},{23,18}},{{20,15},{21,16}},
+ {{23,13},{28,14}},{{23,15},{24,16}},{{27,15},{28,16}},{{23,17},{28,18}},{{25,15},{26,16}},
+ {{ 3,18},{ 8,19}},{{ 3,20},{ 4,21}},{{ 7,20},{ 8,21}},{{ 3,22},{ 8,23}},{{ 5,20},{ 6,21}},
+ {{ 8,18},{13,19}},{{ 8,20},{ 9,21}},{{12,20},{13,21}},{{ 8,22},{13,23}},{{10,20},{11,21}},
+ {{13,18},{18,19}},{{13,20},{14,21}},{{17,20},{18,21}},{{13,22},{18,23}},{{15,20},{16,21}},
+ {{18,18},{23,19}},{{18,20},{19,21}},{{22,20},{23,21}},{{18,22},{23,23}},{{20,20},{21,21}},
+ {{23,18},{28,19}},{{23,20},{24,21}},{{27,20},{28,21}},{{23,22},{28,23}},{{25,20},{26,21}},
+ {{ 8,23},{13,24}},{{ 8,25},{ 9,26}},{{12,25},{13,26}},{{ 8,27},{13,28}},{{10,25},{11,26}},
+ {{13,23},{18,24}},{{13,25},{14,26}},{{17,25},{18,26}},{{13,27},{18,28}},{{15,25},{16,26}},
+ {{18,23},{23,24}},{{18,25},{19,26}},{{22,25},{23,26}},{{18,27},{23,28}},{{20,25},{21,26}}
+};
+static const ElemCat elem_d5 = { 0, 4, 5, 62, elem_d5_data };
+
+static const Block elem_d6_data[] = {
+ {{ 3, 5},{12,10}},{{ 5, 3},{10,12}},
+ {{11, 5},{20,10}},{{13, 3},{18,12}},
+ {{19, 5},{28,10}},{{21, 3},{26,12}},
+ {{ 3,13},{12,18}},{{ 5,11},{10,20}},
+ {{11,13},{20,18}},{{13,11},{18,20}},
+ {{19,13},{28,18}},{{21,11},{26,20}},
+ {{ 3,21},{12,26}},{{ 5,19},{10,28}},
+ {{11,21},{20,26}},{{13,19},{18,28}},
+ {{19,21},{28,26}},{{21,19},{26,28}}
+};
+static const ElemCat elem_d6 = { 0, 1, 2, 9, elem_d6_data };
+
+static const Block elem_d7_data[] = {
+ {{ 0, 4},{ 3, 7}},{{ 8, 4},{11, 7}},{{ 4, 4},{ 7, 7}},
+ {{ 4, 0},{ 7, 3}},{{ 4, 8},{ 7,11}},{{ 4, 4},{ 7, 7}},
+ {{ 5, 4},{ 8, 7}},{{13, 4},{16, 7}},{{ 9, 4},{12, 7}},
+ {{ 9, 0},{12, 3}},{{ 9, 8},{12,11}},{{ 9, 4},{12, 7}},
+ {{10, 4},{13, 7}},{{18, 4},{21, 7}},{{14, 4},{17, 7}},
+ {{14, 0},{17, 3}},{{14, 8},{17,11}},{{14, 4},{17, 7}},
+ {{15, 4},{18, 7}},{{23, 4},{26, 7}},{{19, 4},{22, 7}},
+ {{19, 0},{22, 3}},{{19, 8},{22,11}},{{19, 4},{22, 7}},
+ {{20, 4},{23, 7}},{{28, 4},{31, 7}},{{24, 4},{27, 7}},
+ {{24, 0},{27, 3}},{{24, 8},{27,11}},{{24, 4},{27, 7}},
+ {{ 0, 9},{ 3,12}},{{ 8, 9},{11,12}},{{ 4, 9},{ 7,12}},
+ {{ 4, 5},{ 7, 8}},{{ 4,13},{ 7,16}},{{ 4, 9},{ 7,12}},
+ {{ 5, 9},{ 8,12}},{{13, 9},{16,12}},{{ 9, 9},{12,12}},
+ {{ 9, 5},{12, 8}},{{ 9,13},{12,16}},{{ 9, 9},{12,12}},
+ {{10, 9},{13,12}},{{18, 9},{21,12}},{{14, 9},{17,12}},
+ {{14, 5},{17, 8}},{{14,13},{17,16}},{{14, 9},{17,12}},
+ {{15, 9},{18,12}},{{23, 9},{26,12}},{{19, 9},{22,12}},
+ {{19, 5},{22, 8}},{{19,13},{22,16}},{{19, 9},{22,12}},
+ {{20, 9},{23,12}},{{28, 9},{31,12}},{{24, 9},{27,12}},
+ {{24, 5},{27, 8}},{{24,13},{27,16}},{{24, 9},{27,12}},
+ {{ 0,14},{ 3,17}},{{ 8,14},{11,17}},{{ 4,14},{ 7,17}},
+ {{ 4,10},{ 7,13}},{{ 4,18},{ 7,21}},{{ 4,14},{ 7,17}},
+ {{ 5,14},{ 8,17}},{{13,14},{16,17}},{{ 9,14},{12,17}},
+ {{ 9,10},{12,13}},{{ 9,18},{12,21}},{{ 9,14},{12,17}},
+ {{10,14},{13,17}},{{18,14},{21,17}},{{14,14},{17,17}},
+ {{14,10},{17,13}},{{14,18},{17,21}},{{14,14},{17,17}},
+ {{15,14},{18,17}},{{23,14},{26,17}},{{19,14},{22,17}},
+ {{19,10},{22,13}},{{19,18},{22,21}},{{19,14},{22,17}},
+ {{20,14},{23,17}},{{28,14},{31,17}},{{24,14},{27,17}},
+ {{24,10},{27,13}},{{24,18},{27,21}},{{24,14},{27,17}},
+ {{ 0,19},{ 3,22}},{{ 8,19},{11,22}},{{ 4,19},{ 7,22}},
+ {{ 4,15},{ 7,18}},{{ 4,23},{ 7,26}},{{ 4,19},{ 7,22}},
+ {{ 5,19},{ 8,22}},{{13,19},{16,22}},{{ 9,19},{12,22}},
+ {{ 9,15},{12,18}},{{ 9,23},{12,26}},{{ 9,19},{12,22}},
+ {{10,19},{13,22}},{{18,19},{21,22}},{{14,19},{17,22}},
+ {{14,15},{17,18}},{{14,23},{17,26}},{{14,19},{17,22}},
+ {{15,19},{18,22}},{{23,19},{26,22}},{{19,19},{22,22}},
+ {{19,15},{22,18}},{{19,23},{22,26}},{{19,19},{22,22}},
+ {{20,19},{23,22}},{{28,19},{31,22}},{{24,19},{27,22}},
+ {{24,15},{27,18}},{{24,23},{27,26}},{{24,19},{27,22}},
+ {{ 0,24},{ 3,27}},{{ 8,24},{11,27}},{{ 4,24},{ 7,27}},
+ {{ 4,20},{ 7,23}},{{ 4,28},{ 7,31}},{{ 4,24},{ 7,27}},
+ {{ 5,24},{ 8,27}},{{13,24},{16,27}},{{ 9,24},{12,27}},
+ {{ 9,20},{12,23}},{{ 9,28},{12,31}},{{ 9,24},{12,27}},
+ {{10,24},{13,27}},{{18,24},{21,27}},{{14,24},{17,27}},
+ {{14,20},{17,23}},{{14,28},{17,31}},{{14,24},{17,27}},
+ {{15,24},{18,27}},{{23,24},{26,27}},{{19,24},{22,27}},
+ {{19,20},{22,23}},{{19,28},{22,31}},{{19,24},{22,27}},
+ {{20,24},{23,27}},{{28,24},{31,27}},{{24,24},{27,27}},
+ {{24,20},{27,23}},{{24,28},{27,31}},{{24,24},{27,27}}
+};
+static const ElemCat elem_d7 = { 0, 2, 3, 50, elem_d7_data };
+
+static const Block elem_d8_data[] = {
+ {{ 0, 0},{ 7, 3}},{{ 0, 4},{ 7, 7}},
+ {{ 8, 0},{11, 7}},{{12, 0},{15, 7}},
+ {{ 0, 8},{ 3,15}},{{ 4, 8},{ 7,15}},
+ {{ 8, 8},{15,11}},{{ 8,12},{15,15}},
+ {{16, 0},{19, 7}},{{20, 0},{23, 7}},
+ {{24, 0},{31, 3}},{{24, 4},{31, 7}},
+ {{16, 8},{23,11}},{{16,12},{23,15}},
+ {{24, 8},{27,15}},{{28, 8},{31,15}},
+ {{ 0,16},{ 3,23}},{{ 4,16},{ 7,23}},
+ {{ 8,16},{15,19}},{{ 8,20},{15,23}},
+ {{ 0,24},{ 7,27}},{{ 0,28},{ 7,31}},
+ {{ 8,24},{11,31}},{{12,24},{15,31}},
+ {{16,16},{23,19}},{{16,20},{23,23}},
+ {{24,16},{27,23}},{{28,16},{31,23}},
+ {{16,24},{19,31}},{{20,24},{23,31}},
+ {{24,24},{31,27}},{{24,28},{31,31}},
+ {{ 0, 0},{ 7,15}},{{ 8, 0},{15,15}},
+ {{16, 0},{31, 7}},{{16, 8},{31,15}},
+ {{ 0,16},{15,23}},{{ 0,24},{15,31}},
+ {{16,16},{23,31}},{{24,16},{31,31}}
+};
+static const ElemCat elem_d8 = { 0, 1, 2, 20, elem_d8_data };
+
+static const ElemCat* elements[ELEMENT_COUNT] = { &elem_a1, &elem_a2,
+ &elem_d1, &elem_d2, &elem_d3, &elem_d4,
+ &elem_d5, &elem_d6, &elem_d7, &elem_d8 };
+
+// TODO the lut could be here, with calculation at compile time, but don't know how possible
+//static const int l1distlut[255*256/2];
+
+#endif /* AVFILTER_SIGNATURE_H */
diff --git a/libavfilter/signature_lookup.c b/libavfilter/signature_lookup.c
new file mode 100644
index 0000000..ab3456e
--- /dev/null
+++ b/libavfilter/signature_lookup.c
@@ -0,0 +1,550 @@
+/*
+ * Copyright (c) 2016 Gerion Entrup
+ *
+ * This file is part of FFmpeg.
+ *
+ * FFmpeg is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version.
+ *
+ * FFmpeg is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License along
+ * with FFmpeg; if not, write to the Free Software Foundation, Inc.,
+ * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
+ */
+
+/**
+ * @file
+ * MPEG-7 video signature calculation and lookup filter
+ */
+
+#define HOUGH_MAX_OFFSET 90
+#define MAX_FRAMERATE 60
+
+#define DIR_PREV 0
+#define DIR_NEXT 1
+#define DIR_PREV_END 2
+#define DIR_NEXT_END 3
+
+#define MODE_NORMAL 1
+#define MODE_SPEED 2
+
+#define STATUS_NULL 0
+#define STATUS_END_REACHED 1
+#define STATUS_BEGIN_REACHED 2
+
+static void fill_l1distlut(uint8_t lut[])
+{
+ int i,j,tmp_i,tmp_j,count;
+ uint8_t dist;
+
+ for(i=0, count=0; i<242; i++){
+ for(j=i+1; j<243; j++, count++){
+ /* ternary distance between i and j */
+ dist = 0;
+ tmp_i = i; tmp_j = j;
+ do {
+ dist += FFABS((tmp_j % 3) - (tmp_i % 3));
+ tmp_j /= 3;
+ tmp_i /= 3;
+ } while (tmp_i > 0 || tmp_j > 0);
+ lut[count] = dist;
+ }
+ }
+}
+
+static unsigned int intersection_word(uint8_t *first, uint8_t *second)
+{
+ unsigned int val=0,i;
+ for(i=0; i < 28; i+=4){
+ val += av_popcount( (first[i] & second[i] ) << 24 |
+ (first[i+1] & second[i+1]) << 16 |
+ (first[i+2] & second[i+2]) << 8 |
+ (first[i+3] & second[i+3]) );
+ }
+ val += av_popcount( (first[28] & second[28]) << 16 |
+ (first[29] & second[29]) << 8 |
+ (first[30] & second[30]) );
+ return val;
+}
+
+static unsigned int union_word(uint8_t *first, uint8_t *second)
+{
+ unsigned int val=0,i;
+ for(i=0; i < 28; i+=4){
+ val += av_popcount( (first[i] | second[i] ) << 24 |
+ (first[i+1] | second[i+1]) << 16 |
+ (first[i+2] | second[i+2]) << 8 |
+ (first[i+3] | second[i+3]) );
+ }
+ val += av_popcount( (first[28] | second[28]) << 16 |
+ (first[29] | second[29]) << 8 |
+ (first[30] | second[30]) );
+ return val;
+}
+
+static unsigned int get_l1dist(AVFilterContext *ctx, SignatureContext *sc, uint8_t *first, uint8_t *second)
+{
+ unsigned int i;
+ unsigned int dist = 0;
+ uint8_t f,s;
+
+ for(i=0; i < SIGELEM_SIZE/5; i++){
+ if(first[i] != second[i]){
+ f = first[i];
+ s = second[i];
+ if (f > s){
+ /* little variation of gauss sum formula */
+ dist += sc->l1distlut[243*242/2 - (243-s)*(242-s)/2 + f - s - 1];
+ } else {
+ dist += sc->l1distlut[243*242/2 - (243-f)*(242-f)/2 + s - f - 1];
+ }
+ }
+ }
+ return dist;
+}
+
+static int get_jaccarddist(SignatureContext *sc, CourseSignature *first, CourseSignature *second)
+{
+ int jaccarddist, i, composdist = 0, cwthcount = 0;
+ for(i=0; i<5; i++){
+ if((jaccarddist = intersection_word(first->data[i], second->data[i])) > 0){
+ jaccarddist /= union_word(first->data[i], second->data[i]);
+ }
+ if(jaccarddist >= sc->thworddist){
+ if(++cwthcount > 2){
+ /* more than half (5/2) of distances are too wide */
+ return 0;
+ }
+ }
+ composdist += jaccarddist;
+ if(composdist > sc->thcomposdist){
+ return 0;
+ }
+ }
+ return 1;
+}
+
+
+static int find_next_coursecandidate(SignatureContext *sc, CourseSignature *secondstart, CourseSignature **first, CourseSignature **second, int start)
+{
+ /* go one coursesignature foreword */
+ if(!start){
+ if((*second)->next){
+ *second = (*second)->next;
+ } else if((*first)->next){
+ *second = secondstart;
+ *first = (*first)->next;
+ } else {
+ return 0;
+ }
+ }
+
+ while(1){
+ if(get_jaccarddist(sc, *first, *second))
+ return 1;
+
+ /* next signature */
+ if((*second)->next){
+ *second = (*second)->next;
+ } else if((*first)->next){
+ *second = secondstart;
+ *first = (*first)->next;
+ } else {
+ return 0;
+ }
+ }
+}
+
+static MatchingInfo* get_matching_parameters(AVFilterContext *ctx, SignatureContext *sc, FineSignature *first, FineSignature *second)
+{
+ FineSignature *f,*s;
+ size_t i, j, k, l, hmax = 0, score;
+ int framerate, offset, l1dist;
+ double m;
+ MatchingInfo *cands = NULL, *c = NULL;
+
+ struct {
+ uint8_t size;
+ unsigned int dist;
+ FineSignature *a;
+ uint8_t b_pos[COURSE_SIZE];
+ FineSignature *b[COURSE_SIZE];
+ } pairs[COURSE_SIZE];
+
+ struct {
+ int dist;
+ size_t score;
+ FineSignature *a;
+ FineSignature *b;
+ } hspace[MAX_FRAMERATE][2*HOUGH_MAX_OFFSET+1]; /* houghspace */
+
+
+ /* l1 distances */
+ for(i = 0, f = first; i < COURSE_SIZE && f->next; i++, f = f->next){
+ pairs[i].size = 0;
+ pairs[i].dist = 99999;
+ pairs[i].a = f;
+ for(j = 0, s = second; j < COURSE_SIZE && s->next; j++, s = s->next){
+ /* l1 distance of finesignature */
+ l1dist = get_l1dist(ctx, sc, f->framesig, s->framesig);
+ if(l1dist < sc->thl1){
+ if(l1dist < pairs[i].dist){
+ pairs[i].size = 1;
+ pairs[i].dist = l1dist;
+ pairs[i].b_pos[0] = j;
+ pairs[i].b[0] = s;
+ } else if(l1dist == pairs[i].dist){
+ pairs[i].b[pairs[i].size] = s;
+ pairs[i].b_pos[pairs[i].size] = j;
+ pairs[i].size++;
+ }
+ }
+ }
+ }
+ /* last incomplete coursesignature */
+ if(f->next == NULL){
+ for(; i < COURSE_SIZE; i++){
+ pairs[i].size = 0;
+ pairs[i].dist = 99999;
+ }
+ }
+
+ /* initialize houghspace */
+ for(i = 0; i < MAX_FRAMERATE; i++){
+ for(j = 0; j < HOUGH_MAX_OFFSET; j++){
+ hspace[i][j].score = 0;
+ hspace[i][j].dist = 99999;
+ }
+ }
+
+ /* hough transformation */
+ for(i = 0; i < COURSE_SIZE; i++){
+ for(j = 0; j < pairs[i].size; j++){
+ for(k = i+1; k < COURSE_SIZE; k++){
+ for(l = 0; l < pairs[k].size; l++){
+ if(pairs[i].b[j] != pairs[k].b[l]){
+ /* linear regression */
+ m = (pairs[k].b_pos[l]-pairs[i].b_pos[j]) / (k-i); /* good value between 0.0 - 2.0 */
+ framerate = (int) m*30 + 0.5; /* round up to 0 - 60 */
+ if(framerate>0 && framerate <= MAX_FRAMERATE){
+ offset = pairs[i].b_pos[j] - ((int) m*i + 0.5); /* only second part has to be rounded up */
+ if(offset > -HOUGH_MAX_OFFSET && offset < HOUGH_MAX_OFFSET){
+ if(pairs[i].dist < pairs[k].dist){
+ if(pairs[i].dist < hspace[framerate-1][offset+HOUGH_MAX_OFFSET].dist){
+ hspace[framerate-1][offset+HOUGH_MAX_OFFSET].dist = pairs[i].dist;
+ hspace[framerate-1][offset+HOUGH_MAX_OFFSET].a = pairs[i].a;
+ hspace[framerate-1][offset+HOUGH_MAX_OFFSET].b = pairs[i].b[j];
+ }
+ } else {
+ if(pairs[k].dist < hspace[framerate-1][offset+HOUGH_MAX_OFFSET].dist){
+ hspace[framerate-1][offset+HOUGH_MAX_OFFSET].dist = pairs[k].dist;
+ hspace[framerate-1][offset+HOUGH_MAX_OFFSET].a = pairs[k].a;
+ hspace[framerate-1][offset+HOUGH_MAX_OFFSET].b = pairs[k].b[l];
+ }
+ }
+
+ score = hspace[framerate-1][offset+HOUGH_MAX_OFFSET].score + 1;
+ if(score > hmax)
+ hmax = score;
+ hspace[framerate-1][offset+HOUGH_MAX_OFFSET].score = score;
+ }
+ }
+ }
+ }
+ }
+ }
+ }
+
+ if(hmax > 0){
+ hmax = (int) (0.7*hmax);
+ for(i = 0; i < MAX_FRAMERATE; i++){
+ for(j = 0; j < HOUGH_MAX_OFFSET; j++){
+ if(hmax < hspace[i][j].score){
+ if(c == NULL){
+ c = av_malloc(sizeof(MatchingInfo));
+ if (!c)
+ av_log(ctx, AV_LOG_FATAL, "Could not allocate memory");
+ cands = c;
+ } else {
+ c->next = av_malloc(sizeof(MatchingInfo));
+ if (!c->next)
+ av_log(ctx, AV_LOG_FATAL, "Could not allocate memory");
+ c = c->next;
+ }
+ c->framerateratio = (i+1.0) / 30;
+ c->score = hspace[i][j].score;
+ c->offset = j-90;
+ c->first = hspace[i][j].a;
+ c->second = hspace[i][j].b;
+ c->next = NULL;
+
+ /* not used */
+ c->meandist = 0;
+ c->matchframes = 0;
+ c->whole = 0;
+ }
+ }
+ }
+ }
+ return cands;
+}
+
+static int iterate_frame(double frr, FineSignature **a, FineSignature **b, int fcount, int *bcount, int dir)
+{
+ int step;
+
+ /* between 1 and 2, because frr is between 1 and 2 */
+ step = ((int) 0.5 + fcount * frr) /* current frame */
+ -((int) 0.5 + (fcount-1) * frr);/* last frame */
+
+ if(dir == DIR_NEXT){
+ if(frr >= 1.0){
+ if((*a)->next){
+ *a = (*a)->next;
+ } else {
+ return DIR_NEXT_END;
+ }
+
+ if(step==1){
+ if((*b)->next){
+ *b = (*b)->next;
+ (*bcount)++;
+ } else {
+ return DIR_NEXT_END;
+ }
+ } else {
+ if((*b)->next && (*b)->next->next){
+ *b = (*b)->next->next;
+ (*bcount)++;
+ } else {
+ return DIR_NEXT_END;
+ }
+ }
+ } else {
+ if((*b)->next){
+ *b = (*b)->next;
+ (*bcount)++;
+ } else {
+ return DIR_NEXT_END;
+ }
+
+ if(step==1){
+ if((*a)->next){
+ *a = (*a)->next;
+ } else {
+ return DIR_NEXT_END;
+ }
+ } else {
+ if((*a)->next && (*a)->next->next){
+ *a = (*a)->next->next;
+ } else {
+ return DIR_NEXT_END;
+ }
+ }
+ }
+ return DIR_NEXT;
+ } else {
+ if(frr >= 1.0){
+ if((*a)->prev){
+ *a = (*a)->prev;
+ } else {
+ return DIR_PREV_END;
+ }
+
+ if(step==1){
+ if((*b)->prev){
+ *b = (*b)->prev;
+ (*bcount)++;
+ } else {
+ return DIR_PREV_END;
+ }
+ } else {
+ if((*b)->prev && (*b)->prev->prev){
+ *b = (*b)->prev->prev;
+ (*bcount)++;
+ } else {
+ return DIR_PREV_END;
+ }
+ }
+ } else {
+ if((*b)->prev){
+ *b = (*b)->prev;
+ (*bcount)++;
+ } else {
+ return DIR_PREV_END;
+ }
+
+ if(step==1){
+ if((*a)->prev){
+ *a = (*a)->prev;
+ } else {
+ return DIR_PREV_END;
+ }
+ } else {
+ if((*a)->prev && (*a)->prev->prev){
+ *a = (*a)->prev->prev;
+ } else {
+ return DIR_PREV_END;
+ }
+ }
+ }
+ return DIR_PREV;
+ }
+}
+
+static MatchingInfo evaluate_parameters(AVFilterContext *ctx, SignatureContext *sc, MatchingInfo *infos, MatchingInfo bestmatch, int mode)
+{
+ int dist, distsum = 0, bcount = 1, dir = DIR_NEXT;
+ int fcount = 0, goodfcount = 0, gooda = 0, goodb = 0;
+ double meandist, minmeandist = bestmatch.meandist;
+ int tolerancecount = 0;
+ FineSignature *a,*b, *aprev, *bprev;
+ int status = STATUS_NULL;
+
+ for(; infos != NULL; infos = infos->next){
+ a = infos->first;
+ b = infos->second;
+ while(1){
+ dist = get_l1dist(ctx, sc, a->framesig, b->framesig);
+
+ if(dist > sc->thl1){
+ if(a->confidence >= 1 || b->confidence >= 1){
+ /* bad frame (because high different information) */
+ tolerancecount++;
+ }
+
+ if(tolerancecount > 2){
+ a = aprev;
+ b = bprev;
+ if (dir == DIR_NEXT){
+ /* turn around */
+ a = infos->first;
+ b = infos->second;
+ dir = DIR_PREV;
+ } else {
+ break;
+ }
+ }
+ } else {
+ /* good frame */
+ distsum += dist;
+ goodfcount++;
+ tolerancecount=0;
+
+ aprev = a;
+ bprev = b;
+
+ if(a->confidence < 1) gooda++;
+ if(b->confidence < 1) goodb++;
+ }
+
+ fcount++;
+
+ dir = iterate_frame(infos->framerateratio, &a, &b, fcount, &bcount, dir);
+ if(dir == DIR_NEXT_END){
+ status = STATUS_END_REACHED;
+ a = infos->first;
+ b = infos->second;
+ dir = iterate_frame(infos->framerateratio, &a, &b, fcount, &bcount, DIR_PREV);
+ }
+
+ if(dir == DIR_PREV_END){
+ status |= STATUS_BEGIN_REACHED;
+ break;
+ }
+
+ if(sc->thdi != 0 && bcount >= sc->thdi){
+ break; /* enough frames found */
+ }
+ }
+
+ if(bcount < sc->thdi)
+ continue; /* matching sequence is too short */
+ if((double)goodfcount/(double)fcount < sc->thit)
+ continue;
+ if((double)goodfcount*0.5 < FFMAX(gooda, goodb))
+ continue;
+
+ meandist = (double)goodfcount/(double)distsum;
+
+ if(meandist < minmeandist ||
+ status == STATUS_END_REACHED | STATUS_BEGIN_REACHED ||
+ mode == MODE_SPEED){
+ minmeandist = meandist;
+ /* bestcandidate in this iteration */
+ bestmatch.meandist = meandist;
+ bestmatch.matchframes = bcount;
+ bestmatch.framerateratio = infos->framerateratio;
+ bestmatch.score = infos->score;
+ bestmatch.offset = infos->offset;
+ bestmatch.first = infos->first;
+ bestmatch.second = infos->second;
+ bestmatch.whole = 0; /* will be set to true later */
+ bestmatch.next = NULL;
+ }
+
+ /* whole sequence is automatically best match */
+ if(status == (STATUS_END_REACHED | STATUS_BEGIN_REACHED)){
+ bestmatch.whole = 1;
+ break;
+ }
+
+ /* first matching sequence is enough, finding the best one is not necessary */
+ if(mode == MODE_SPEED){
+ break;
+ }
+ }
+ return bestmatch;
+}
+
+static void sll_free(MatchingInfo *sll)
+{
+ void *tmp;
+ while(sll){
+ tmp = sll;
+ sll = sll->next;
+ av_free(tmp);
+ }
+}
+
+static MatchingInfo lookup_signatures(AVFilterContext *ctx, SignatureContext *sc, StreamContext *first, StreamContext *second, int mode)
+{
+ CourseSignature *cs, *cs2;
+ MatchingInfo *infos;
+ MatchingInfo bestmatch;
+
+ cs = first->coursesiglist;
+ cs2 = second->coursesiglist;
+
+ /* score of bestmatch is 0, if no match is found */
+ bestmatch.score = 0;
+ bestmatch.meandist = 99999;
+ bestmatch.whole = 0;
+
+ fill_l1distlut(sc->l1distlut);
+
+ /* stage 1: course signature matching */
+ av_log(ctx, AV_LOG_DEBUG, "Stage 1: get next coursesignature pair:\n");
+ if(find_next_coursecandidate(sc, second->coursesiglist, &cs, &cs2, 1) == 0)
+ return bestmatch; /* no candidate found */
+ do {
+ /* stage 2: l1-distance and hough-transform */
+ av_log(ctx, AV_LOG_DEBUG, "Stage 2: calculate matching parameters:\n");
+ infos = get_matching_parameters(ctx, sc, cs->first, cs2->first);
+ /* stage 3: evaluation */
+ av_log(ctx, AV_LOG_DEBUG, "Stage 3: evaluate:\n");
+ if(infos){
+ bestmatch = evaluate_parameters(ctx, sc, infos, bestmatch, mode);
+ sll_free(infos);
+ }
+ av_log(ctx, AV_LOG_DEBUG, "Stage 1: get next coursesignature pair:\n");
+ } while(find_next_coursecandidate(sc, second->coursesiglist, &cs, &cs2, 0) && !bestmatch.whole);
+ return bestmatch;
+
+}
diff --git a/libavfilter/version.h b/libavfilter/version.h
index 94c6bdc..0dbb7e5 100644
--- a/libavfilter/version.h
+++ b/libavfilter/version.h
@@ -30,8 +30,8 @@
#include "libavutil/version.h"
#define LIBAVFILTER_VERSION_MAJOR 6
-#define LIBAVFILTER_VERSION_MINOR 40
-#define LIBAVFILTER_VERSION_MICRO 102
+#define LIBAVFILTER_VERSION_MINOR 41
+#define LIBAVFILTER_VERSION_MICRO 100
#define LIBAVFILTER_VERSION_INT AV_VERSION_INT(LIBAVFILTER_VERSION_MAJOR, \
LIBAVFILTER_VERSION_MINOR, \
diff --git a/libavfilter/vf_signature.c b/libavfilter/vf_signature.c
new file mode 100644
index 0000000..1c4d03f
--- /dev/null
+++ b/libavfilter/vf_signature.c
@@ -0,0 +1,741 @@
+/*
+ * Copyright (c) 2016 Gerion Entrup
+ *
+ * This file is part of FFmpeg.
+ *
+ * FFmpeg is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version.
+ *
+ * FFmpeg is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License along
+ * with FFmpeg; if not, write to the Free Software Foundation, Inc.,
+ * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
+ */
+
+/**
+ * @file
+ * MPEG-7 video signature calculation and lookup filter
+ * @see http://epubs.surrey.ac.uk/531590/1/MPEG-7%20Video%20Signature%20Author%27s%20Copy.pdf
+ */
+
+#include <float.h>
+#include "libavutil/opt.h"
+#include "libavutil/avstring.h"
+#include "libavutil/timestamp.h"
+#include "libavformat/avformat.h"
+#include "libavcodec/put_bits.h"
+#include "avfilter.h"
+#include "internal.h"
+#include "signature.h"
+#include "signature_lookup.c"
+
+#define OFFSET(x) offsetof(SignatureContext, x)
+#define FLAGS AV_OPT_FLAG_VIDEO_PARAM
+
+static const AVOption signature_options[] = {
+ { "detectmode", "enable the detectmode, otherwise it will be the analyzemode",
+ OFFSET(mode), AV_OPT_TYPE_INT, {.i64 = 0}, 0, 2, .flags = FLAGS }, \
+ { "nb_inputs", "set number of inputs",
+ OFFSET(nb_inputs), AV_OPT_TYPE_INT, {.i64 = 1}, 1, INT_MAX, .flags = FLAGS }, \
+ { "filename", "set filename for output files",
+ OFFSET(filename), AV_OPT_TYPE_STRING, {.str = ""}, 0, 0, .flags = FLAGS }, \
+ { "xml", "enable XML output instead of binary output",
+ OFFSET(xml), AV_OPT_TYPE_INT, {.i64 = 0}, 0, 1, .flags = FLAGS }, \
+ { "th_d", "set threshold to detect one word as similar",
+ OFFSET(thworddist), AV_OPT_TYPE_INT, {.i64 = 9000}, 1, INT_MAX, .flags = FLAGS }, \
+ { "th_dc", "set threshold to detect all words as similar",
+ OFFSET(thcomposdist), AV_OPT_TYPE_INT, {.i64 = 60000}, 1, INT_MAX, .flags = FLAGS }, \
+ { "th_xh", "set threshold to detect frames as similar",
+ OFFSET(thl1), AV_OPT_TYPE_INT, {.i64 = 116}, 1, INT_MAX, .flags = FLAGS }, \
+ { "th_di", "minimum length of matching sequence in frames",
+ OFFSET(thdi), AV_OPT_TYPE_INT, {.i64 = 0}, 0, INT_MAX, .flags = FLAGS }, \
+ { "th_it", "set threshold for relation of good to all frames",
+ OFFSET(thit), AV_OPT_TYPE_DOUBLE, {.dbl = 0.5},0.0, 1.0, .flags = FLAGS }, \
+ { NULL }
+};
+
+AVFILTER_DEFINE_CLASS(signature);
+
+static int query_formats(AVFilterContext *ctx)
+{
+ static const enum AVPixelFormat pix_fmts[] = {
+ AV_PIX_FMT_GRAY8,
+ AV_PIX_FMT_YUV410P, AV_PIX_FMT_YUV411P,
+ AV_PIX_FMT_YUV420P, AV_PIX_FMT_YUV422P,
+ AV_PIX_FMT_YUV440P, AV_PIX_FMT_YUV444P,
+ AV_PIX_FMT_YUVJ411P, AV_PIX_FMT_YUVJ420P,
+ AV_PIX_FMT_YUVJ422P, AV_PIX_FMT_YUVJ444P,
+ AV_PIX_FMT_YUVJ440P,
+ AV_PIX_FMT_NV12, AV_PIX_FMT_NV21,
+ AV_PIX_FMT_NONE
+ };
+
+ return ff_set_common_formats(ctx, ff_make_format_list(pix_fmts));
+}
+
+static int config_input(AVFilterLink *inlink)
+{
+ AVFilterContext *ctx = inlink->dst;
+ SignatureContext *sic = ctx->priv;
+ StreamContext *sc = &(sic->streamcontexts[FF_INLINK_IDX(inlink)]);
+ int i;
+
+ sc->time_base = inlink->time_base;
+ for(i=0; i<32; i++){
+ sc->x_coords[i] = i * (inlink->w/32);
+ sc->y_coords[i] = i * (inlink->h/32);
+ }
+ sc->w = inlink->w;
+ sc->h = inlink->h;
+ return 0;
+}
+
+static int get_block_size(const Block *b)
+{
+ return (b->to.y - b->up.y + 1) * (b->to.x - b->up.x + 1);
+}
+
+static uint64_t get_block_sum(StreamContext *sc, uint64_t intpic[32][32], const Block *b)
+{
+ uint64_t sum = 0;
+
+ int x0,y0,x1,y1;
+
+ x0 = b->up.x;
+ y0 = b->up.y;
+ x1 = b->to.x;
+ y1 = b->to.y;
+
+ if(x0-1 >= 0 && y0-1 >= 0){
+ sum = intpic[y1][x1] + intpic[y0-1][x0-1] - intpic[y1][x0-1] - intpic[y0-1][x1];
+ }else if(x0-1 >= 0){
+ sum = intpic[y1][x1] - intpic[y1][x0-1];
+ }else if(y0-1 >= 0){
+ sum = intpic[y1][x1] - intpic[y0-1][x1];
+ }else{
+ sum = intpic[y1][x1];
+ }
+ return sum;
+}
+
+static int cmp(const double *a, const double *b)
+{
+ return *a < *b ? -1 : ( *a > *b ? 1 : 0 );
+}
+
+/**
+ * sets the bit at position pos to 1 in data
+ */
+static void set_bit(uint8_t* data, size_t pos)
+{
+ uint8_t mask = 1 << 7-(pos%8);
+ data[pos/8] |= mask;
+}
+
+
+
+static int filter_frame(AVFilterLink *inlink, AVFrame *picref)
+{
+ AVFilterContext *ctx = inlink->dst;
+ SignatureContext *sic = ctx->priv;
+ StreamContext *sc = &(sic->streamcontexts[FF_INLINK_IDX(inlink)]);
+ FineSignature* fs;
+
+ static const uint8_t pot3[5] = { 3*3*3*3, 3*3*3, 3*3, 3, 1 };
+ /* indexes of words : 210,217,219,274,334 44,175,233,270,273 57,70,103,237,269 100,285,295,337,354 101,102,111,275,296
+ s2usw = sorted to unsorted wordvec: 44 is at index 5, 57 at index 10...
+ */
+ static const unsigned int wordvec[25] = {44,57,70,100,101,102,103,111,175,210,217,219,233,237,269,270,273,274,275,285,295,296,334,337,354};
+ static const uint8_t s2usw[25] = { 5,10,11, 15, 20, 21, 12, 22, 6, 0, 1, 2, 7, 13, 14, 8, 9, 3, 23, 16, 17, 24, 4, 18, 19};
+
+ uint8_t wordt2b[5] = { 0, 0, 0, 0, 0 }; /* word ternary to binary */
+ uint64_t intpic[32][32];
+ uint64_t rowcount;
+ uint8_t *p = picref->data[0];
+ int inti, intj;
+ int *intjlut;
+
+ double conflist[DIFFELEM_SIZE];
+ int f = 0, g = 0, w = 0;
+ int dh1 = 1, dh2 = 1, dw1 = 1, dw2 = 1, denum, a, b;
+ int i,j,k,ternary;
+ uint64_t blocksum;
+ int blocksize;
+ double th; /* threshold */
+ double sum;
+
+ /* initialize fs */
+ if(sc->curfinesig){
+ fs = av_mallocz(sizeof(FineSignature));
+ if (!fs)
+ return AVERROR(ENOMEM);
+ sc->curfinesig->next = fs;
+ fs->prev = sc->curfinesig;
+ sc->curfinesig = fs;
+ }else{
+ fs = sc->curfinesig = sc->finesiglist;
+ sc->curcoursesig1->first = fs;
+ }
+
+ fs->pts = picref->pts;
+ fs->index = sc->lastindex++;
+
+ memset(intpic, 0, sizeof(uint64_t)*32*32);
+ intjlut = av_malloc(inlink->w * sizeof(int));
+ if (!intjlut)
+ return AVERROR(ENOMEM);
+ for (i=0; i < inlink->w; i++){
+ intjlut[i] = (i<<5)/inlink->w;
+ }
+
+ for (i=0; i < inlink->h; i++){
+ inti = (i<<5)/inlink->h;
+ for (j=0; j< inlink->w; j++){
+ intj = intjlut[j];
+ intpic[inti][intj] += p[j];
+ }
+ p += picref->linesize[0];
+ }
+ av_free(intjlut);
+
+ /* The following calculate a summed area table (intpic) and brings the numbers
+ * in intpic to to the same denuminator.
+ * So you only have to handle the numinator in the following sections.
+ */
+ dh1 = inlink->h/32;
+ if (inlink->h%32)
+ dh2 = dh1 + 1;
+ dw1 = inlink->w/32;
+ if (inlink->w%32)
+ dw2 = dw1 + 1;
+ denum = dh1 * dh2 * dw1 * dw2;
+
+ for (i=0; i<32; i++){
+ rowcount = 0;
+ a = 1;
+ if (dh2 > 1) {
+ a = ((inlink->h*(i+1))%32 == 0) ? (inlink->h*(i+1))/32 - 1 : (inlink->h*(i+1))/32;
+ a -= ((inlink->h*i)%32 == 0) ? (inlink->h*i)/32 - 1 : (inlink->h*i)/32;
+ a = (a == dh1)? dh2 : dh1;
+ }
+ for (j=0; j<32; j++){
+ b = 1;
+ if (dw2 > 1) {
+ b = ((inlink->w*(j+1))%32 == 0) ? (inlink->w*(j+1))/32 - 1 : (inlink->w*(j+1))/32;
+ b -= ((inlink->w*j)%32 == 0) ? (inlink->w*j)/32 - 1 : (inlink->w*j)/32;
+ b = (b == dw1)? dw2 : dw1;
+ }
+ rowcount += intpic[i][j] *= a * b;
+ if(i>0){
+ intpic[i][j] = intpic[i-1][j] + rowcount;
+ } else {
+ intpic[i][j] = rowcount;
+ }
+ }
+ }
+
+ for (i=0; i< ELEMENT_COUNT; i++){
+ const ElemCat* elemcat = elements[i];
+ double* elemsignature = av_malloc(sizeof(double) * elemcat->elem_count);
+ double* sortsignature = av_malloc(sizeof(double) * elemcat->elem_count);
+ if (!elemsignature || !sortsignature)
+ return AVERROR(ENOMEM);
+ for(j=0; j<elemcat->elem_count; j++) {
+ blocksum = 0;
+ blocksize = 0;
+ for(k=0; k<elemcat->left_count; k++){
+ blocksum += get_block_sum(sc, intpic, &elemcat->blocks[j*elemcat->block_count+k]);
+ blocksize += get_block_size(&elemcat->blocks[j*elemcat->block_count+k]);
+ }
+ sum = ((double) blocksum)/(blocksize * denum);
+ if (elemcat->av_elem){
+ sum -= 128.0;
+ } else {
+ blocksum = 0;
+ blocksize = 0;
+ for(; k< elemcat->block_count; k++){
+ blocksum += get_block_sum(sc, intpic, &elemcat->blocks[j*elemcat->block_count+k]);
+ blocksize += get_block_size(&elemcat->blocks[j*elemcat->block_count+k]);
+ }
+ sum -= ((double) blocksum)/(blocksize * denum);
+ conflist[g++] = FFABS(sum);
+ }
+
+ elemsignature[j] = sum;
+ sortsignature[j] = FFABS(sum);
+ }
+
+ /* get threshold */
+ qsort(sortsignature, elemcat->elem_count, sizeof(double), (void*) cmp);
+ th = sortsignature[(int) (elemcat->elem_count*0.333)];
+
+ /* ternarize */
+ for(j=0; j<elemcat->elem_count; j++) {
+ if (elemsignature[j] < -th){
+ ternary = 0;
+ } else if (elemsignature[j] <= th) {
+ ternary = 1;
+ } else {
+ ternary = 2;
+ }
+ fs->framesig[f/5] += ternary * pot3[f%5];
+
+ if(f==wordvec[w]){
+ fs->words[s2usw[w]/5] += ternary * pot3[wordt2b[s2usw[w]/5]++];
+ if (w < 24)
+ w++;
+ }
+ f++;
+ }
+ av_free(elemsignature);
+ av_free(sortsignature);
+ }
+
+ /* confidence */
+ qsort(conflist, DIFFELEM_SIZE, sizeof(double), (void*) cmp);
+ fs->confidence = FFMIN((int) (conflist[DIFFELEM_SIZE/2] * 8.0), 255);
+
+ /* coursesignature */
+ if(sc->coursecount == 0){
+ if(sc->curcoursesig2){
+ sc->curcoursesig1 = av_mallocz(sizeof(CourseSignature));
+ if (!sc->curcoursesig1)
+ return AVERROR(ENOMEM);
+ sc->curcoursesig1->first = fs;
+ sc->curcoursesig2->next = sc->curcoursesig1;
+ sc->courseend = sc->curcoursesig1;
+ }
+ }
+ if(sc->coursecount == 45){
+ sc->midcourse = 1;
+ sc->curcoursesig2 = av_mallocz(sizeof(CourseSignature));
+ if (!sc->curcoursesig2)
+ return AVERROR(ENOMEM);
+ sc->curcoursesig2->first = fs;
+ sc->curcoursesig1->next = sc->curcoursesig2;
+ sc->courseend = sc->curcoursesig2;
+ }
+ for(i=0; i<5; i++){
+ set_bit(sc->curcoursesig1->data[i], fs->words[i]);
+ }
+ /* assuming the actual frame is the last */
+ sc->curcoursesig1->last = fs;
+ if(sc->midcourse){
+ for(i=0; i<5; i++){
+ set_bit(sc->curcoursesig2->data[i], fs->words[i]);
+ }
+ sc->curcoursesig2->last = fs;
+ }
+
+ sc->coursecount = (sc->coursecount+1)%90;
+
+ /* debug printing finesignature */
+ av_log(ctx, AV_LOG_DEBUG, "confidence: %d\n", fs->confidence);
+
+ av_log(ctx, AV_LOG_DEBUG, "words:");
+ for (i=0; i< 5; i++){
+ av_log(ctx, AV_LOG_DEBUG, " %d:", fs->words[i] );
+ av_log(ctx, AV_LOG_DEBUG, " %d", fs->words[i] / pot3[0] );
+ for (j = 1; j < 5; j++)
+ av_log(ctx, AV_LOG_DEBUG, ",%d", fs->words[i] % pot3[j-1] / pot3[j] );
+ av_log(ctx, AV_LOG_DEBUG, ";");
+ }
+ av_log(ctx, AV_LOG_DEBUG, "\n");
+
+ av_log(ctx, AV_LOG_DEBUG, "framesignature:");
+ for (i=0; i< SIGELEM_SIZE/5; i++){
+ av_log(ctx, AV_LOG_DEBUG, " %d", fs->framesig[i] / pot3[0] );
+ for (j = 1; j < 5; j++)
+ av_log(ctx, AV_LOG_DEBUG, ",%d", fs->framesig[i] % pot3[j-1] / pot3[j] );
+ }
+ av_log(ctx, AV_LOG_DEBUG, "\n");
+
+ if (FF_INLINK_IDX(inlink) == 0)
+ return ff_filter_frame(inlink->dst->outputs[0], picref);
+ return 1;
+}
+
+static int xml_export(AVFilterContext *ctx, StreamContext *sc, char* filename)
+{
+ FineSignature* fs;
+ CourseSignature* cs;
+ int i,j;
+ FILE* f;
+ unsigned int pot3[5] = { 3*3*3*3, 3*3*3, 3*3, 3, 1 };
+
+ f = fopen(filename, "w");
+ if (!f) {
+ av_log(ctx, AV_LOG_ERROR, "cannot open xml file %s\n", filename);
+ return AVERROR(EINVAL);
+ }
+
+ /* header */
+ fprintf(f, "<?xml version='1.0' encoding='ASCII' ?>\n");
+ fprintf(f, "<Mpeg7 xmlns=\"urn:mpeg:mpeg7:schema:2001\" xmlns:xsi=\"http://www.w3.org/2001/XMLSchema-instance\"; xsi:schemaLocation=\"urn:mpeg:mpeg7:schema:2001 schema/Mpeg7-2001.xsd\">\n");
+ fprintf(f, " <DescriptionUnit xsi:type=\"DescriptorCollectionType\">\n");
+ fprintf(f, " <Descriptor xsi:type=\"VideoSignatureType\">\n");
+ fprintf(f, " <VideoSignatureRegion>\n");
+ fprintf(f, " <VideoSignatureSpatialRegion>\n");
+ fprintf(f, " <Pixel>0 0 </Pixel>\n");
+ fprintf(f, " <Pixel>%d %d </Pixel>\n", sc->w - 1, sc->h - 1);
+ fprintf(f, " </VideoSignatureSpatialRegion>\n");
+ fprintf(f, " <StartFrameOfSpatialRegion>0</StartFrameOfSpatialRegion>\n");
+ /* hoping num is 1, other values are vague */
+ fprintf(f, " <MediaTimeUnit>%d</MediaTimeUnit>\n", sc->time_base.den / sc->time_base.num);
+ fprintf(f, " <MediaTimeOfSpatialRegion>\n");
+ fprintf(f, " <StartMediaTimeOfSpatialRegion>0</StartMediaTimeOfSpatialRegion>\n");
+ fprintf(f, " <EndMediaTimeOfSpatialRegion>%" PRIu64 "</EndMediaTimeOfSpatialRegion>\n", sc->courseend->last->pts);
+ fprintf(f, " </MediaTimeOfSpatialRegion>\n");
+
+ /* coursesignatures */
+ for(cs = sc->coursesiglist; cs; cs = cs->next){
+ fprintf(f, " <VSVideoSegment>\n");
+ fprintf(f, " <StartFrameOfSegment>%" PRIu32 "</StartFrameOfSegment>\n", cs->first->index);
+ fprintf(f, " <EndFrameOfSegment>%" PRIu32 "</EndFrameOfSegment>\n", cs->last->index);
+ fprintf(f, " <MediaTimeOfSegment>\n");
+ fprintf(f, " <StartMediaTimeOfSegment>%" PRIu64 "</StartMediaTimeOfSegment>\n", cs->first->pts);
+ fprintf(f, " <EndMediaTimeOfSegment>%" PRIu64 "</EndMediaTimeOfSegment>\n", cs->last->pts);
+ fprintf(f, " </MediaTimeOfSegment>\n");
+ for (i=0; i < 5; i++){
+ fprintf(f, " <BagOfWords>");
+ for (j=0; j < 31; j++){
+ uint8_t n = cs->data[i][j];
+ if (j < 30){
+ fprintf(f, "%d %d %d %d %d %d %d %d ", (n & 0x80) >> 7,
+ (n & 0x40) >> 6,
+ (n & 0x20) >> 5,
+ (n & 0x10) >> 4,
+ (n & 0x08) >> 3,
+ (n & 0x04) >> 2,
+ (n & 0x02) >> 1,
+ (n & 0x01));
+ } else {
+ /* print only 3 bit in last byte */
+ fprintf(f, "%d %d %d ", (n & 0x80) >> 7,
+ (n & 0x40) >> 6,
+ (n & 0x20) >> 5);
+ }
+ }
+ fprintf(f, "</BagOfWords>\n");
+ }
+ fprintf(f, " </VSVideoSegment>\n");
+ }
+
+ /* finesignatures */
+ for(fs = sc->finesiglist; fs; fs = fs->next){
+ fprintf(f, " <VideoFrame>\n");
+ fprintf(f, " <MediaTimeOfFrame>%" PRIu64 "</MediaTimeOfFrame>\n", fs->pts);
+ /* confidence */
+ fprintf(f, " <FrameConfidence>%d</FrameConfidence>\n", fs->confidence);
+ /* words */
+ fprintf(f, " <Word>");
+ for (i=0; i< 5; i++){
+ fprintf(f, "%d ", fs->words[i]);
+ if (i < 4){
+ fprintf(f, " ");
+ }
+ }
+ fprintf(f, "</Word>\n");
+ /* framesignature */
+ fprintf(f, " <FrameSignature>");
+ for (i=0; i< SIGELEM_SIZE/5; i++){
+ if (i>0) {
+ fprintf(f, " ");
+ }
+ fprintf(f, "%d", fs->framesig[i] / pot3[0]);
+ for (j = 1; j < 5; j++)
+ fprintf(f, " %d", fs->framesig[i] % pot3[j-1] / pot3[j] );
+ }
+ fprintf(f, "</FrameSignature>\n");
+ fprintf(f, " </VideoFrame>\n");
+ }
+ fprintf(f, " </VideoSignatureRegion>\n");
+ fprintf(f, " </Descriptor>\n");
+ fprintf(f, " </DescriptionUnit>\n");
+ fprintf(f, "</Mpeg7>\n");
+
+ fclose(f);
+ return 0;
+}
+
+static int binary_export(AVFilterContext *ctx, StreamContext *sc, char* filename)
+{
+ FILE* f;
+ FineSignature* fs;
+ CourseSignature* cs;
+ uint32_t numofsegments = (sc->lastindex + 44)/45;
+ int i,j;
+ PutBitContext buf;
+ /* buffer + header + coursesignatures + finesignature */
+ int len = (512 + 6 * 32 + 3*16 + 2 +
+ numofsegments * (4*32 + 1 + 5*243) +
+ sc->lastindex * (2 + 32 + 6*8 + 608)) / 8;
+ uint8_t* buffer = av_malloc(len * sizeof(uint8_t));
+ if (!buffer)
+ return AVERROR(ENOMEM);
+
+ f = fopen(filename, "wb");
+ if (!f) {
+ av_log(ctx, AV_LOG_ERROR, "cannot open file %s\n", filename);
+ return AVERROR(EINVAL);
+ }
+ init_put_bits(&buf, buffer, len);
+
+ put_bits32(&buf, 1); /* NumOfSpatial Regions, only 1 supported */
+ put_bits(&buf, 1, 1); /* SpatialLocationFlag, always the whole image */
+ put_bits32(&buf, 0); /* PixelX,1 PixelY,1, 0,0 */
+ put_bits(&buf, 16, sc->w-1 & 0xFFFF); /* PixelX,2 */
+ put_bits(&buf, 16, sc->h-1 & 0xFFFF); /* PixelY,2 */
+ put_bits32(&buf, 0); /* StartFrameOfSpatialRegion */
+ put_bits32(&buf, sc->lastindex); /* NumOfFrames */
+ /* hoping num is 1, other values are vague */
+ /* den/num might be greater than 16 bit, so cutting it */
+ put_bits(&buf, 16, 0xFFFF & (sc->time_base.den / sc->time_base.num)); /* MediaTimeUnit */
+ put_bits(&buf, 1, 1); /* MediaTimeFlagOfSpatialRegion */
+ put_bits32(&buf, 0); /* StartMediaTimeOfSpatialRegion */
+ put_bits32(&buf, 0xFFFFFFFF & sc->courseend->last->pts); /* EndMediaTimeOfSpatialRegion */
+ put_bits32(&buf, numofsegments); /* NumOfSegments */
+ /* coursesignatures */
+ for(cs = sc->coursesiglist; cs; cs = cs->next){
+ put_bits32(&buf, cs->first->index); /* StartFrameOfSegment */
+ put_bits32(&buf, cs->last->index); /* EndFrameOfSegment */
+ put_bits(&buf, 1, 1); /* MediaTimeFlagOfSegment */
+ put_bits32(&buf, 0xFFFFFFFF & cs->first->pts); /* StartMediaTimeOfSegment */
+ put_bits32(&buf, 0xFFFFFFFF & cs->last->pts); /* EndMediaTimeOfSegment */
+ for (i=0; i < 5; i++){
+ /* put 243 bits ( = 7 * 32 + 19 = 8 * 28 + 19) into buffer */
+ for (j=0; j < 28; j+=4){
+ put_bits32(&buf, 0xFFFFFFFF & (cs->data[i][j] << 24 |
+ cs->data[i][j+1] << 16 |
+ cs->data[i][j+2] << 8 |
+ cs->data[i][j+3]));
+ }
+ put_bits(&buf, 19, 0x7FFFF & (cs->data[i][28] << 11 |
+ cs->data[i][29] << 3 |
+ cs->data[i][30] >> 5));
+ }
+ }
+ /* finesignatures */
+ put_bits(&buf, 1, 0); /* CompressionFlag, only 0 supported */
+ for(fs = sc->finesiglist; fs; fs = fs->next){
+ put_bits(&buf, 1, 1); /* MediaTimeFlagOfFrame */
+ put_bits32(&buf, 0xFFFFFFFF & fs->pts); /* MediaTimeOfFrame */
+ put_bits(&buf, 8, fs->confidence); /* FrameConfidence */
+ for (i=0; i< 5; i++){
+ put_bits(&buf, 8, fs->words[i]); /* Words */
+ }
+ /* framesignature */
+ for (i=0; i< SIGELEM_SIZE/5; i+=4){
+ put_bits32(&buf, 0xFFFFFFFF & (fs->framesig[i] << 24 |
+ fs->framesig[i+1] << 16 |
+ fs->framesig[i+2] << 8 |
+ fs->framesig[i+3]));
+ }
+ }
+
+ avpriv_align_put_bits(&buf);
+ flush_put_bits(&buf);
+ fwrite(buffer, 1, put_bits_count(&buf)/8, f);
+ fclose(f);
+ av_free(buffer);
+ return 0;
+}
+
+static int export(AVFilterContext *ctx, StreamContext *sc, int input)
+{
+ SignatureContext* sic = ctx->priv;
+ char filename[1024];
+
+ if (sic->nb_inputs > 1) {
+ /* error already handled */
+ av_get_frame_filename(filename, sizeof(filename), sic->filename, input);
+ } else {
+ strcpy(filename, sic->filename);
+ }
+ if (sic->xml) {
+ return xml_export(ctx, sc, filename);
+ } else {
+ return binary_export(ctx, sc, filename);
+ }
+
+}
+
+static int request_frame(AVFilterLink *outlink)
+{
+ AVFilterContext *ctx = outlink->src;
+ SignatureContext *sc = ctx->priv;
+ int i, ret;
+
+ for (i = 0; i < sc->nb_inputs; i++){
+ ret = ff_request_frame(ctx->inputs[i]);
+ if (ret < 0)
+ return ret;
+ }
+ return ret;
+}
+
+static av_cold int init(AVFilterContext *ctx)
+{
+
+ SignatureContext *sic = ctx->priv;
+ StreamContext *sc;
+ int i, ret;
+ char tmp[1024];
+
+ /* check filename before doing anything */
+ if (sic->nb_inputs > 1 && strlen(sic->filename) > 0 && av_get_frame_filename(tmp, sizeof(tmp), sic->filename, 0) == -1){
+ av_log(ctx, AV_LOG_ERROR, "The filename must contain %%d or %%0nd, if you have more than one input.\n");
+ return AVERROR(EINVAL);
+ }
+
+ sic->streamcontexts = av_mallocz(sic->nb_inputs * sizeof(StreamContext));
+ if (!sic->streamcontexts)
+ return AVERROR(ENOMEM);
+
+ for (i = 0; i < sic->nb_inputs; i++) {
+ AVFilterPad pad = {
+ .type = AVMEDIA_TYPE_VIDEO,
+ .name = av_asprintf("in%d", i),
+ .config_props = config_input,
+ .filter_frame = filter_frame,
+ };
+
+ if (!pad.name)
+ return AVERROR(ENOMEM);
+
+ sc = &(sic->streamcontexts[i]);
+
+ sc->lastindex = 0;
+ sc->finesiglist = av_mallocz(sizeof(FineSignature));
+ if (!sc->finesiglist)
+ return AVERROR(ENOMEM);
+ sc->curfinesig = NULL;
+
+ sc->coursesiglist = av_mallocz(sizeof(CourseSignature));
+ if (!sc->coursesiglist)
+ return AVERROR(ENOMEM);
+ sc->curcoursesig1 = sc->coursesiglist;
+ sc->coursecount = 0;
+ sc->midcourse = 0;
+
+ if ((ret = ff_insert_inpad(ctx, i, &pad)) < 0){
+ av_freep(&pad.name);
+ return ret;
+ }
+ }
+
+ return 0;
+}
+
+
+
+static av_cold void uninit(AVFilterContext *ctx)
+{
+ SignatureContext *sic = ctx->priv;
+ StreamContext *sc, *sc2;
+ void* tmp;
+ FineSignature* finsig;
+ CourseSignature* cousig;
+ MatchingInfo match;
+ int i,j;
+
+ /* signature export */
+ if (strlen(sic->filename) > 0) {
+ for (i = 0; i < sic->nb_inputs; i++) {
+ /* if filter frame was called at least once */
+ if ((&(sic->streamcontexts[i]))->curfinesig)
+ export(ctx, &(sic->streamcontexts[i]), i);
+ }
+ }
+
+ /* signature lookup */
+ if(sic->mode){
+ /* iterate over every pair */
+ for (i = 0; i < sic->nb_inputs; i++) {
+ sc = &(sic->streamcontexts[i]);
+ if (sc->curfinesig) {
+ for (j=i+1; j < sic->nb_inputs; j++){
+ sc2 = &(sic->streamcontexts[j]);
+ if (sc2->curfinesig) {
+ match = lookup_signatures(ctx, sic, sc, sc2, sic->mode);
+ if(match.score != 0){
+ av_log(ctx, AV_LOG_INFO, "matching of video %d at %f and %d at %f, %d frames matching\n",
+ i, ((double) match.first->pts * sc->time_base.num) / sc->time_base.den,
+ j, ((double) match.second->pts * sc2->time_base.num) / sc2->time_base.den,
+ match.matchframes);
+ if(match.whole)
+ av_log(ctx, AV_LOG_INFO, "whole video matching\n");
+ } else {
+ av_log(ctx, AV_LOG_INFO, "no matching of video %d and %d\n", i, j);
+ }
+ }
+ }
+ }
+ }
+ }
+
+ /* cleanup */
+ for (i = 0; i < sic->nb_inputs; i++) {
+ sc = &(sic->streamcontexts[i]);
+ finsig = sc->finesiglist;
+ cousig = sc->coursesiglist;
+
+ while(finsig){
+ tmp = finsig;
+ finsig = finsig->next;
+ av_free(tmp);
+ }
+ sc->finesiglist = NULL;
+
+ while(cousig){
+ tmp = cousig;
+ cousig = cousig->next;
+ av_free(tmp);
+ }
+ sc->coursesiglist = NULL;
+ }
+ av_free(sic->streamcontexts);
+}
+
+static int config_output(AVFilterLink *outlink)
+{
+ AVFilterContext *ctx = outlink->src;
+ AVFilterLink *inlink = ctx->inputs[0];
+
+ outlink->time_base = inlink->time_base;
+ outlink->frame_rate = inlink->frame_rate;
+ outlink->sample_aspect_ratio = inlink->sample_aspect_ratio;
+ outlink->w = inlink->w;
+ outlink->h = inlink->h;
+
+ return 0;
+}
+
+static const AVFilterPad signature_outputs[] = {
+ {
+ .name = "default",
+ .type = AVMEDIA_TYPE_VIDEO,
+ .request_frame = request_frame,
+ .config_props = config_output,
+ },
+ { NULL }
+};
+
+AVFilter ff_vf_signature = {
+ .name = "signature",
+ .description = NULL_IF_CONFIG_SMALL("Calculate the MPEG-7 video signature"),
+ .priv_size = sizeof(SignatureContext),
+ .priv_class = &signature_class,
+ .init = init,
+ .uninit = uninit,
+ .query_formats = query_formats,
+ .outputs = signature_outputs,
+ .inputs = NULL,
+ .flags = AVFILTER_FLAG_DYNAMIC_INPUTS,
+};
--
2.7.3
diff --git a/libavfilter/signature.h b/libavfilter/signature.h
index a22cab3..98dba17 100644
--- a/libavfilter/signature.h
+++ b/libavfilter/signature.h
@@ -110,15 +110,18 @@ typedef struct {
typedef struct {
const AVClass *class;
- int mode;
+ /* input parameters */
+ char* mode;
int nb_inputs;
char *filename;
- int xml; /* bool */
+ char* format;
int thworddist;
int thcomposdist;
int thl1;
int thdi;
int thit;
+ /* end input parameters */
+
uint8_t l1distlut[243*242/2]; /* 243 + 242 + 241 ... */
StreamContext* streamcontexts;
} SignatureContext;
diff --git a/libavfilter/signature_lookup.c b/libavfilter/signature_lookup.c
index ab3456e..b43e56b 100644
--- a/libavfilter/signature_lookup.c
+++ b/libavfilter/signature_lookup.c
@@ -31,9 +31,6 @@
#define DIR_PREV_END 2
#define DIR_NEXT_END 3
-#define MODE_NORMAL 1
-#define MODE_SPEED 2
-
#define STATUS_NULL 0
#define STATUS_END_REACHED 1
#define STATUS_BEGIN_REACHED 2
@@ -58,7 +55,7 @@ static void fill_l1distlut(uint8_t lut[])
}
}
-static unsigned int intersection_word(uint8_t *first, uint8_t *second)
+static unsigned int intersection_word(const uint8_t *first, const uint8_t *second)
{
unsigned int val=0,i;
for(i=0; i < 28; i+=4){
@@ -73,7 +70,7 @@ static unsigned int intersection_word(uint8_t *first, uint8_t *second)
return val;
}
-static unsigned int union_word(uint8_t *first, uint8_t *second)
+static unsigned int union_word(const uint8_t *first, const uint8_t *second)
{
unsigned int val=0,i;
for(i=0; i < 28; i+=4){
@@ -88,7 +85,7 @@ static unsigned int union_word(uint8_t *first, uint8_t *second)
return val;
}
-static unsigned int get_l1dist(AVFilterContext *ctx, SignatureContext *sc, uint8_t *first, uint8_t *second)
+static unsigned int get_l1dist(AVFilterContext *ctx, SignatureContext *sc, const uint8_t *first, const uint8_t *second)
{
unsigned int i;
unsigned int dist = 0;
@@ -109,6 +106,10 @@ static unsigned int get_l1dist(AVFilterContext *ctx, SignatureContext *sc, uint8
return dist;
}
+/**
+ * calculates the jaccard distance and evaluate a pair of course signatures as good
+ * @return 0 if pair is bad, 1 otherwise
+ */
static int get_jaccarddist(SignatureContext *sc, CourseSignature *first, CourseSignature *second)
{
int jaccarddist, i, composdist = 0, cwthcount = 0;
@@ -130,7 +131,10 @@ static int get_jaccarddist(SignatureContext *sc, CourseSignature *first, CourseS
return 1;
}
-
+/**
+ * step through the coursesignatures as long as a good candidate is found
+ * @return 0 if no candidate is found, 1 otherwise
+ */
static int find_next_coursecandidate(SignatureContext *sc, CourseSignature *secondstart, CourseSignature **first, CourseSignature **second, int start)
{
/* go one coursesignature foreword */
@@ -161,6 +165,10 @@ static int find_next_coursecandidate(SignatureContext *sc, CourseSignature *seco
}
}
+/**
+ * compares framesignatures and sort out signatures with a l1 distance over a given threshold.
+ * Then tries to find out offset and differences between framerates with a hough transformation
+ */
static MatchingInfo* get_matching_parameters(AVFilterContext *ctx, SignatureContext *sc, FineSignature *first, FineSignature *second)
{
FineSignature *f,*s;
@@ -398,7 +406,7 @@ static int iterate_frame(double frr, FineSignature **a, FineSignature **b, int f
}
}
-static MatchingInfo evaluate_parameters(AVFilterContext *ctx, SignatureContext *sc, MatchingInfo *infos, MatchingInfo bestmatch, int mode)
+static MatchingInfo evaluate_parameters(AVFilterContext *ctx, SignatureContext *sc, MatchingInfo *infos, MatchingInfo bestmatch, const char* mode)
{
int dist, distsum = 0, bcount = 1, dir = DIR_NEXT;
int fcount = 0, goodfcount = 0, gooda = 0, goodb = 0;
@@ -475,7 +483,7 @@ static MatchingInfo evaluate_parameters(AVFilterContext *ctx, SignatureContext *
if(meandist < minmeandist ||
status == STATUS_END_REACHED | STATUS_BEGIN_REACHED ||
- mode == MODE_SPEED){
+ strcmp(mode, "fast") == 0){
minmeandist = meandist;
/* bestcandidate in this iteration */
bestmatch.meandist = meandist;
@@ -496,7 +504,7 @@ static MatchingInfo evaluate_parameters(AVFilterContext *ctx, SignatureContext *
}
/* first matching sequence is enough, finding the best one is not necessary */
- if(mode == MODE_SPEED){
+ if(strcmp(mode, "fast") == 0){
break;
}
}
@@ -509,15 +517,16 @@ static void sll_free(MatchingInfo *sll)
while(sll){
tmp = sll;
sll = sll->next;
- av_free(tmp);
+ av_freep(tmp);
}
}
-static MatchingInfo lookup_signatures(AVFilterContext *ctx, SignatureContext *sc, StreamContext *first, StreamContext *second, int mode)
+static MatchingInfo lookup_signatures(AVFilterContext *ctx, SignatureContext *sc, StreamContext *first, StreamContext *second, const char* mode)
{
CourseSignature *cs, *cs2;
MatchingInfo *infos;
MatchingInfo bestmatch;
+ MatchingInfo *i;
cs = first->coursesiglist;
cs2 = second->coursesiglist;
@@ -530,20 +539,25 @@ static MatchingInfo lookup_signatures(AVFilterContext *ctx, SignatureContext *sc
fill_l1distlut(sc->l1distlut);
/* stage 1: course signature matching */
- av_log(ctx, AV_LOG_DEBUG, "Stage 1: get next coursesignature pair:\n");
if(find_next_coursecandidate(sc, second->coursesiglist, &cs, &cs2, 1) == 0)
return bestmatch; /* no candidate found */
do {
+ av_log(ctx, AV_LOG_DEBUG, "Stage 1: got coursesignature pair. indices of first frame: %d and %d\n", cs->first->index, cs2->first->index);
/* stage 2: l1-distance and hough-transform */
- av_log(ctx, AV_LOG_DEBUG, "Stage 2: calculate matching parameters:\n");
+ av_log(ctx, AV_LOG_DEBUG, "Stage 2: calculate matching parameters\n");
infos = get_matching_parameters(ctx, sc, cs->first, cs2->first);
+ if (av_log_get_level() == AV_LOG_DEBUG){
+ for(i = infos; i != NULL; i = i->next){
+ av_log(ctx, AV_LOG_DEBUG, "Stage 2: matching pair at %d and %d, ratio %f, offset %d\n", i->first->index, i->second->index, i->framerateratio, i->offset);
+ }
+ }
/* stage 3: evaluation */
- av_log(ctx, AV_LOG_DEBUG, "Stage 3: evaluate:\n");
+ av_log(ctx, AV_LOG_DEBUG, "Stage 3: evaluate\n");
if(infos){
bestmatch = evaluate_parameters(ctx, sc, infos, bestmatch, mode);
+ av_log(ctx, AV_LOG_DEBUG, "Stage 3: best matching pair at %d and %d, ratio %f, offset %d, score %d, %d frames matching\n", bestmatch.first->index, bestmatch.second->index, bestmatch.framerateratio, bestmatch.offset, bestmatch.score, bestmatch.matchframes);
sll_free(infos);
}
- av_log(ctx, AV_LOG_DEBUG, "Stage 1: get next coursesignature pair:\n");
} while(find_next_coursecandidate(sc, second->coursesiglist, &cs, &cs2, 0) && !bestmatch.whole);
return bestmatch;
diff --git a/libavfilter/vf_signature.c b/libavfilter/vf_signature.c
index 1c4d03f..5d5b9f5 100644
--- a/libavfilter/vf_signature.c
+++ b/libavfilter/vf_signature.c
@@ -25,11 +25,12 @@
*/
#include <float.h>
+#include "libavcodec/put_bits.h"
+#include "libavformat/avformat.h"
#include "libavutil/opt.h"
#include "libavutil/avstring.h"
+#include "libavutil/intreadwrite.h"
#include "libavutil/timestamp.h"
-#include "libavformat/avformat.h"
-#include "libavcodec/put_bits.h"
#include "avfilter.h"
#include "internal.h"
#include "signature.h"
@@ -37,26 +38,27 @@
#define OFFSET(x) offsetof(SignatureContext, x)
#define FLAGS AV_OPT_FLAG_VIDEO_PARAM
+#define BLOCK_LCM (int64_t) 476985600
static const AVOption signature_options[] = {
- { "detectmode", "enable the detectmode, otherwise it will be the analyzemode",
- OFFSET(mode), AV_OPT_TYPE_INT, {.i64 = 0}, 0, 2, .flags = FLAGS }, \
+ { "detectmode", "set the detectmode, possible values: off (default), full, fast",
+ OFFSET(mode), AV_OPT_TYPE_STRING, {.str = "off"}, 0, 0, .flags = FLAGS }, \
{ "nb_inputs", "set number of inputs",
- OFFSET(nb_inputs), AV_OPT_TYPE_INT, {.i64 = 1}, 1, INT_MAX, .flags = FLAGS }, \
+ OFFSET(nb_inputs), AV_OPT_TYPE_INT, {.i64 = 1}, 1, INT_MAX, .flags = FLAGS }, \
{ "filename", "set filename for output files",
- OFFSET(filename), AV_OPT_TYPE_STRING, {.str = ""}, 0, 0, .flags = FLAGS }, \
- { "xml", "enable XML output instead of binary output",
- OFFSET(xml), AV_OPT_TYPE_INT, {.i64 = 0}, 0, 1, .flags = FLAGS }, \
+ OFFSET(filename), AV_OPT_TYPE_STRING, {.str = ""}, 0, 0, .flags = FLAGS }, \
+ { "format", "set output format, possible values: binary (default), xml",
+ OFFSET(format), AV_OPT_TYPE_STRING, {.str = "binary"}, 0, 1, .flags = FLAGS }, \
{ "th_d", "set threshold to detect one word as similar",
- OFFSET(thworddist), AV_OPT_TYPE_INT, {.i64 = 9000}, 1, INT_MAX, .flags = FLAGS }, \
+ OFFSET(thworddist), AV_OPT_TYPE_INT, {.i64 = 9000}, 1, INT_MAX, .flags = FLAGS }, \
{ "th_dc", "set threshold to detect all words as similar",
- OFFSET(thcomposdist), AV_OPT_TYPE_INT, {.i64 = 60000}, 1, INT_MAX, .flags = FLAGS }, \
+ OFFSET(thcomposdist), AV_OPT_TYPE_INT, {.i64 = 60000}, 1, INT_MAX, .flags = FLAGS }, \
{ "th_xh", "set threshold to detect frames as similar",
- OFFSET(thl1), AV_OPT_TYPE_INT, {.i64 = 116}, 1, INT_MAX, .flags = FLAGS }, \
+ OFFSET(thl1), AV_OPT_TYPE_INT, {.i64 = 116}, 1, INT_MAX, .flags = FLAGS }, \
{ "th_di", "minimum length of matching sequence in frames",
- OFFSET(thdi), AV_OPT_TYPE_INT, {.i64 = 0}, 0, INT_MAX, .flags = FLAGS }, \
+ OFFSET(thdi), AV_OPT_TYPE_INT, {.i64 = 0}, 0, INT_MAX, .flags = FLAGS }, \
{ "th_it", "set threshold for relation of good to all frames",
- OFFSET(thit), AV_OPT_TYPE_DOUBLE, {.dbl = 0.5},0.0, 1.0, .flags = FLAGS }, \
+ OFFSET(thit), AV_OPT_TYPE_DOUBLE, {.dbl = 0.5}, 0.0, 1.0, .flags = FLAGS }, \
{ NULL }
};
@@ -88,6 +90,11 @@ static int config_input(AVFilterLink *inlink)
sc->time_base = inlink->time_base;
for(i=0; i<32; i++){
+ //TODO not used atm, here could be a lot more
+ //is it valid to say, that the width and height for all frames is the same?
+ //if so, a certain amount of calculations in filter_frame can be done here
+ //
+ //pro argument: the output format (xml and binary) only support one width and height
sc->x_coords[i] = i * (inlink->w/32);
sc->y_coords[i] = i * (inlink->h/32);
}
@@ -124,7 +131,7 @@ static uint64_t get_block_sum(StreamContext *sc, uint64_t intpic[32][32], const
return sum;
}
-static int cmp(const double *a, const double *b)
+static int cmp(const uint64_t *a, const uint64_t *b)
{
return *a < *b ? -1 : ( *a > *b ? 1 : 0 );
}
@@ -138,6 +145,47 @@ static void set_bit(uint8_t* data, size_t pos)
data[pos/8] |= mask;
}
+/* TODO this is meant as some kind of lut, I assume the division is made at
+ * compile time. Is it better, to write this with preprocessor?
+ * (Or simply write: return BLOCK_LCM / n;), please comment */
+static int32_t get_multiplier(int32_t n){
+ switch(n){
+ case 4:
+ return BLOCK_LCM / 4;
+ case 8:
+ return BLOCK_LCM / 8;
+ case 9:
+ return BLOCK_LCM / 9;
+ case 16:
+ return BLOCK_LCM / 16;
+ case 32:
+ return BLOCK_LCM / 32;
+ case 36:
+ return BLOCK_LCM / 36;
+ case 60:
+ return BLOCK_LCM / 60;
+ case 64:
+ return BLOCK_LCM / 64;
+ case 84:
+ return BLOCK_LCM / 84;
+ case 100:
+ return BLOCK_LCM / 100;
+ case 128:
+ return BLOCK_LCM / 128;
+ case 160:
+ return BLOCK_LCM / 160;
+ case 196:
+ return BLOCK_LCM / 196;
+ case 256:
+ return BLOCK_LCM / 256;
+ case 400:
+ return BLOCK_LCM / 400;
+ case 676:
+ return BLOCK_LCM / 676;
+ }
+ /* should never reach this point */
+ return BLOCK_LCM / n;
+}
static int filter_frame(AVFilterLink *inlink, AVFrame *picref)
@@ -161,14 +209,14 @@ static int filter_frame(AVFilterLink *inlink, AVFrame *picref)
int inti, intj;
int *intjlut;
- double conflist[DIFFELEM_SIZE];
+ uint64_t conflist[DIFFELEM_SIZE];
int f = 0, g = 0, w = 0;
- int dh1 = 1, dh2 = 1, dw1 = 1, dw2 = 1, denum, a, b;
+ int32_t dh1 = 1, dh2 = 1, dw1 = 1, dw2 = 1, denum, a, b;
int i,j,k,ternary;
uint64_t blocksum;
- int blocksize;
- double th; /* threshold */
- double sum;
+ uint64_t blocksize;
+ int64_t th; /* threshold */
+ int64_t sum;
/* initialize fs */
if(sc->curfinesig){
@@ -187,7 +235,7 @@ static int filter_frame(AVFilterLink *inlink, AVFrame *picref)
fs->index = sc->lastindex++;
memset(intpic, 0, sizeof(uint64_t)*32*32);
- intjlut = av_malloc(inlink->w * sizeof(int));
+ intjlut = av_malloc_array(inlink->w, sizeof(int));
if (!intjlut)
return AVERROR(ENOMEM);
for (i=0; i < inlink->w; i++){
@@ -202,7 +250,7 @@ static int filter_frame(AVFilterLink *inlink, AVFrame *picref)
}
p += picref->linesize[0];
}
- av_free(intjlut);
+ av_freep(intjlut);
/* The following calculate a summed area table (intpic) and brings the numbers
* in intpic to to the same denuminator.
@@ -242,10 +290,16 @@ static int filter_frame(AVFilterLink *inlink, AVFrame *picref)
for (i=0; i< ELEMENT_COUNT; i++){
const ElemCat* elemcat = elements[i];
- double* elemsignature = av_malloc(sizeof(double) * elemcat->elem_count);
- double* sortsignature = av_malloc(sizeof(double) * elemcat->elem_count);
- if (!elemsignature || !sortsignature)
+ int64_t* elemsignature;
+ uint64_t* sortsignature;
+
+ elemsignature = av_malloc_array(elemcat->elem_count, sizeof(int64_t));
+ if (!elemsignature)
+ return AVERROR(ENOMEM);
+ sortsignature = av_malloc_array(elemcat->elem_count, sizeof(uint64_t));
+ if (!sortsignature)
return AVERROR(ENOMEM);
+
for(j=0; j<elemcat->elem_count; j++) {
blocksum = 0;
blocksize = 0;
@@ -253,9 +307,9 @@ static int filter_frame(AVFilterLink *inlink, AVFrame *picref)
blocksum += get_block_sum(sc, intpic, &elemcat->blocks[j*elemcat->block_count+k]);
blocksize += get_block_size(&elemcat->blocks[j*elemcat->block_count+k]);
}
- sum = ((double) blocksum)/(blocksize * denum);
+ sum = blocksum * get_multiplier(blocksize);
if (elemcat->av_elem){
- sum -= 128.0;
+ sum -= 128 * BLOCK_LCM * denum;
} else {
blocksum = 0;
blocksize = 0;
@@ -263,8 +317,8 @@ static int filter_frame(AVFilterLink *inlink, AVFrame *picref)
blocksum += get_block_sum(sc, intpic, &elemcat->blocks[j*elemcat->block_count+k]);
blocksize += get_block_size(&elemcat->blocks[j*elemcat->block_count+k]);
}
- sum -= ((double) blocksum)/(blocksize * denum);
- conflist[g++] = FFABS(sum);
+ sum -= blocksum * get_multiplier(blocksize);
+ conflist[g++] = FFABS(sum * 8 / (BLOCK_LCM * denum));
}
elemsignature[j] = sum;
@@ -272,7 +326,7 @@ static int filter_frame(AVFilterLink *inlink, AVFrame *picref)
}
/* get threshold */
- qsort(sortsignature, elemcat->elem_count, sizeof(double), (void*) cmp);
+ qsort(sortsignature, elemcat->elem_count, sizeof(uint64_t), (void*) cmp);
th = sortsignature[(int) (elemcat->elem_count*0.333)];
/* ternarize */
@@ -298,8 +352,8 @@ static int filter_frame(AVFilterLink *inlink, AVFrame *picref)
}
/* confidence */
- qsort(conflist, DIFFELEM_SIZE, sizeof(double), (void*) cmp);
- fs->confidence = FFMIN((int) (conflist[DIFFELEM_SIZE/2] * 8.0), 255);
+ qsort(conflist, DIFFELEM_SIZE, sizeof(uint64_t), (void*) cmp);
+ fs->confidence = FFMIN(conflist[DIFFELEM_SIZE/2], 255);
/* coursesignature */
if(sc->coursecount == 0){
@@ -336,7 +390,7 @@ static int filter_frame(AVFilterLink *inlink, AVFrame *picref)
sc->coursecount = (sc->coursecount+1)%90;
/* debug printing finesignature */
- av_log(ctx, AV_LOG_DEBUG, "confidence: %d\n", fs->confidence);
+ av_log(ctx, AV_LOG_DEBUG, "input %d, confidence: %d\n", FF_INLINK_IDX(inlink), fs->confidence);
av_log(ctx, AV_LOG_DEBUG, "words:");
for (i=0; i< 5; i++){
@@ -361,7 +415,7 @@ static int filter_frame(AVFilterLink *inlink, AVFrame *picref)
return 1;
}
-static int xml_export(AVFilterContext *ctx, StreamContext *sc, char* filename)
+static int xml_export(AVFilterContext *ctx, StreamContext *sc, const char* filename)
{
FineSignature* fs;
CourseSignature* cs;
@@ -448,9 +502,9 @@ static int xml_export(AVFilterContext *ctx, StreamContext *sc, char* filename)
if (i>0) {
fprintf(f, " ");
}
- fprintf(f, "%d", fs->framesig[i] / pot3[0]);
+ fprintf(f, "%d ", fs->framesig[i] / pot3[0]);
for (j = 1; j < 5; j++)
- fprintf(f, " %d", fs->framesig[i] % pot3[j-1] / pot3[j] );
+ fprintf(f, " %d ", fs->framesig[i] % pot3[j-1] / pot3[j] );
}
fprintf(f, "</FrameSignature>\n");
fprintf(f, " </VideoFrame>\n");
@@ -464,7 +518,7 @@ static int xml_export(AVFilterContext *ctx, StreamContext *sc, char* filename)
return 0;
}
-static int binary_export(AVFilterContext *ctx, StreamContext *sc, char* filename)
+static int binary_export(AVFilterContext *ctx, StreamContext *sc, const char* filename)
{
FILE* f;
FineSignature* fs;
@@ -476,7 +530,7 @@ static int binary_export(AVFilterContext *ctx, StreamContext *sc, char* filename
int len = (512 + 6 * 32 + 3*16 + 2 +
numofsegments * (4*32 + 1 + 5*243) +
sc->lastindex * (2 + 32 + 6*8 + 608)) / 8;
- uint8_t* buffer = av_malloc(len * sizeof(uint8_t));
+ uint8_t* buffer = av_malloc_array(len, sizeof(uint8_t));
if (!buffer)
return AVERROR(ENOMEM);
@@ -510,15 +564,11 @@ static int binary_export(AVFilterContext *ctx, StreamContext *sc, char* filename
put_bits32(&buf, 0xFFFFFFFF & cs->last->pts); /* EndMediaTimeOfSegment */
for (i=0; i < 5; i++){
/* put 243 bits ( = 7 * 32 + 19 = 8 * 28 + 19) into buffer */
- for (j=0; j < 28; j+=4){
- put_bits32(&buf, 0xFFFFFFFF & (cs->data[i][j] << 24 |
- cs->data[i][j+1] << 16 |
- cs->data[i][j+2] << 8 |
- cs->data[i][j+3]));
+ for (j=0; j < 30; j++){
+ //TODO is it faster to use put_bits32 and shift?
+ put_bits(&buf, 8, cs->data[i][j]);
}
- put_bits(&buf, 19, 0x7FFFF & (cs->data[i][28] << 11 |
- cs->data[i][29] << 3 |
- cs->data[i][30] >> 5));
+ put_bits(&buf, 3, cs->data[i][30] >> 5);
}
}
/* finesignatures */
@@ -531,11 +581,8 @@ static int binary_export(AVFilterContext *ctx, StreamContext *sc, char* filename
put_bits(&buf, 8, fs->words[i]); /* Words */
}
/* framesignature */
- for (i=0; i< SIGELEM_SIZE/5; i+=4){
- put_bits32(&buf, 0xFFFFFFFF & (fs->framesig[i] << 24 |
- fs->framesig[i+1] << 16 |
- fs->framesig[i+2] << 8 |
- fs->framesig[i+3]));
+ for (i=0; i< SIGELEM_SIZE/5; i++){
+ put_bits(&buf, 8, fs->framesig[i]);
}
}
@@ -558,7 +605,7 @@ static int export(AVFilterContext *ctx, StreamContext *sc, int input)
} else {
strcpy(filename, sic->filename);
}
- if (sic->xml) {
+ if (strcmp(sic->format, "xml") == 0) {
return xml_export(ctx, sc, filename);
} else {
return binary_export(ctx, sc, filename);
@@ -574,12 +621,27 @@ static int request_frame(AVFilterLink *outlink)
for (i = 0; i < sc->nb_inputs; i++){
ret = ff_request_frame(ctx->inputs[i]);
- if (ret < 0)
+ // TODO handle this in a better way?
+ // Problem is the following:
+ // Assuming two inputs, inputA with 50 frames, inputB with 100 frames
+ // simply returning ret when < 0 would result in not filtering inputB
+ // after 50 frames anymore, not wanted
+ // only returning ret at the end would result in only respecting the error
+ // values of the last input, please comment
+ if (ret < 0 && ret != AVERROR_EOF)
return ret;
}
return ret;
}
+static int check_input_list(const char* input, const char** values, int length){
+ int i, ret = 1;
+ for (i = 0; i < length; i++){
+ ret &= (strcmp(input, values[i]) != 0);
+ }
+ return ret;
+}
+
static av_cold int init(AVFilterContext *ctx)
{
@@ -587,12 +649,8 @@ static av_cold int init(AVFilterContext *ctx)
StreamContext *sc;
int i, ret;
char tmp[1024];
-
- /* check filename before doing anything */
- if (sic->nb_inputs > 1 && strlen(sic->filename) > 0 && av_get_frame_filename(tmp, sizeof(tmp), sic->filename, 0) == -1){
- av_log(ctx, AV_LOG_ERROR, "The filename must contain %%d or %%0nd, if you have more than one input.\n");
- return AVERROR(EINVAL);
- }
+ const char* modes[] = { "off", "full", "fast" };
+ const char* formats[] = { "xml", "binary" };
sic->streamcontexts = av_mallocz(sic->nb_inputs * sizeof(StreamContext));
if (!sic->streamcontexts)
@@ -621,6 +679,7 @@ static av_cold int init(AVFilterContext *ctx)
if (!sc->coursesiglist)
return AVERROR(ENOMEM);
sc->curcoursesig1 = sc->coursesiglist;
+ sc->courseend = sc->coursesiglist;
sc->coursecount = 0;
sc->midcourse = 0;
@@ -630,6 +689,21 @@ static av_cold int init(AVFilterContext *ctx)
}
}
+ /* check filename */
+ if (sic->nb_inputs > 1 && strlen(sic->filename) > 0 && av_get_frame_filename(tmp, sizeof(tmp), sic->filename, 0) == -1){
+ av_log(ctx, AV_LOG_ERROR, "The filename must contain %%d or %%0nd, if you have more than one input.\n");
+ return AVERROR(EINVAL);
+ }
+ /* check mode and format */
+ if (check_input_list(sic->mode, modes, 3)){
+ av_log(ctx, AV_LOG_ERROR, "detectmode must be set to one of the following values: off, full, fast\n");
+ return AVERROR(EINVAL);
+ }
+ if (strlen(sic->filename) > 0 && check_input_list(sic->format, formats, 2)){
+ av_log(ctx, AV_LOG_ERROR, "format must be set to one of the following values: xml, binary\n");
+ return AVERROR(EINVAL);
+ }
+
return 0;
}
@@ -645,6 +719,9 @@ static av_cold void uninit(AVFilterContext *ctx)
MatchingInfo match;
int i,j;
+ //TODO export and especially lookup_signature can have a return value to show some error etc.
+ //How could this be handled in this function?
+
/* signature export */
if (strlen(sic->filename) > 0) {
for (i = 0; i < sic->nb_inputs; i++) {
@@ -655,7 +732,7 @@ static av_cold void uninit(AVFilterContext *ctx)
}
/* signature lookup */
- if(sic->mode){
+ if(strcmp(sic->mode, "off") != 0){
/* iterate over every pair */
for (i = 0; i < sic->nb_inputs; i++) {
sc = &(sic->streamcontexts[i]);
#!/usr/bin/env python3
# This program is free software: you can redistribute it and/or modify
# it under the terms of the GNU General Public License as published by
# the Free Software Foundation, either version 3 of the License, or
# (at your option) any later version.
#
# This program is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
# GNU General Public License for more details.
#
# You should have received a copy of the GNU General Public License
# along with this program. If not, see <http://www.gnu.org/licenses/>
import sys, argparse, os, subprocess
import xml.etree.ElementTree as ET
# BitReader taken from http://rosettacode.org/wiki/Bitwise_IO#Python
class BitReader:
def __init__(self, f):
self.input = f
self.accumulator = 0
self.bcount = 0
self.read = 0
self.counter = 0
self.log = False
def reset_counter(self):
self.counter = 0
def toggle(self):
self.log = not self.log
def readbit(self):
if self.bcount == 0 :
a = self.input.read(1)
if ( len(a) > 0 ):
self.accumulator = ord(a)
self.bcount = 8
self.read = len(a)
rv = ( self.accumulator & ( 1 << (self.bcount-1) ) ) >> (self.bcount-1)
self.bcount -= 1
self.counter += 1
if self.log:
print("b:", self.counter, rv)
return rv
def readbits(self, n):
v = 0
while n > 0:
v = (v << 1) | self.readbit()
n -= 1
return v
def call_ffmpeg(ffmpeg, infile, outfile, mode):
fmode = {'xml': 'format=xml',
'binary': 'format=binary',
'binary_compressed': None}
if fmode[mode] == None:
return
cmd = [ffmpeg, '-i', infile,
'-filter:v', 'signature=filename={}:{}'.format(outfile, fmode[mode]),
'-c', 'rawvideo', '-map', '0:v', '-y', '-f', 'null', '-']
print(' '.join("'{}'".format(x) for x in cmd))
subprocess.call(cmd)
def compare_segment(l1, l2):
assert(len(l1) == len(l2))
assert(len(l1) == 243)
i = 0
for x, y in zip(l1, l2):
if (x != y):
i += 1
return i
def xml_compare_segment(s1, s2):
l1 = [int(i) for i in s1.split()]
l2 = [int(i) for i in s2.split()]
return compare_segment(l1, l2)
def bin_compare_segment(ob, sb):
l1 = []
l2 = []
for i in range(243):
l1.append(ob.readbit())
l2.append(sb.readbit())
return compare_segment(l1, l2)
def compare_framesignature(l1, l2):
assert(len(l1) == len(l2))
assert(len(l1) == 380)
i = 0
for x, y in zip(l1, l2):
i += abs(x-y)
if (i > 15):
error("Error: Framesignatureerrors has to be less than 16. Currently", i)
return i
def xml_compare_framesignature(f1, f2):
l1 = [int(i) for i in f1.split()]
l2 = [int(i) for i in f2.split()]
return compare_framesignature(l1, l2)
def bin_compare_framesignature(ob, sb):
pot3 = ( 3**5, 3**4, 3**3, 3*3, 3, 1 );
l1 = []
l2 = []
for i in range(76):
o = ob.readbits(8)
s = sb.readbits(8)
for j in range(1, 6):
l1.append(o % pot3[j-1] // pot3[j])
l2.append(s % pot3[j-1] // pot3[j])
return compare_framesignature(l1, l2)
def binary_compressed(indir, sample, own):
print("binary_compressed check not implemented")
def get_same_bin(name, ob, sb, n, compare=True, maximum_error=0):
v1 = ob.readbits(n)
v2 = sb.readbits(n)
if compare and abs(v1 - v2) > maximum_error:
if maximum_error > 0:
error("{}: {} should be between {} and {}".format(name, v1, v2-maximum_error, v2+maximum_error))
return min(v1, v2)
else:
error("{}: {} should be {}".format(name, v1, v2))
return v1
def binary(indir, file, own):
max_segment = 0
max_frame = 0
with open(own, 'rb') as of:
with open(os.path.join(indir, '.'.join(file.split('.')[:-1] + ['bin'])), 'rb') as sf:
ob = BitReader(of)
sb = BitReader(sf)
num = get_same_bin("NumOfSpatialRegion", ob, sb, 32)
for i in range(num):
flag = get_same_bin("SpatialLocFlag", ob, sb, 1)
if flag == 1:
for j in range(4):
get_same_bin("PixelXY", ob, sb, 16)
get_same_bin("StartFrameOfSpatialR", ob, sb, 32)
frames = get_same_bin("NumOfFrames", ob, sb, 32)
get_same_bin("MediaTimeUnit", ob, sb, 16, compare=False)
flag = get_same_bin("MediaTimeFlag", ob, sb, 1)
if flag == 1:
get_same_bin("", ob, sb, 32, compare=False)
get_same_bin("", ob, sb, 32, compare=False)
segmentnum = get_same_bin("NumOfSegments", ob, sb, 32)
for j in range(segmentnum):
start = get_same_bin("StartFrameSeg", ob, sb, 32)
get_same_bin("EndFrameSeg", ob, sb, 32)
flag = get_same_bin("MediaTimeFlagSegment", ob, sb, 1)
if flag == 1:
get_same_bin("", ob, sb, 32, compare=False)
get_same_bin("", ob, sb, 32, compare=False)
for k in range(5):
err = bin_compare_segment(ob, sb)
if err > max_segment:
max_segment = err
compression = get_same_bin("CompressionFlag", ob, sb, 1)
assert(compression == 0)
for j in range(frames):
flag = get_same_bin("MediaTimeFlagFrame", ob, sb, 1)
if flag == 1:
get_same_bin("", ob, sb, 32, compare=False)
conf = get_same_bin("confidence", ob, sb, 8, maximum_error=7)
for k in range(5):
get_same_bin("", ob, sb, 8, compare=False)
err = bin_compare_framesignature(ob, sb)
if err > max_frame:
max_frame = err
print("maximum error in coursesignature:", max_segment)
print("maximum error in framesignature:", max_frame)
print("binary is valid")
def xml_compare(e1, e2, subelem, maximum_error=0):
s1 = e1.find(subelem)
s2 = e2.find(subelem)
if maximum_error == 0:
assert(s1.text == s2.text)
return s1.text
else:
assert(abs(int(s1.text) - int(s2.text)) <= maximum_error)
return min(int(s1.text), int(s2.text))
def compare_words(w1, w2):
l1 = [int(i) for i in w1.split()]
l2 = [int(i) for i in w2.split()]
assert(len(l1) == len(l2))
#for x, y in zip(l1, l2):
# assert(x == y)
def xml(indir, file, own):
courseerrors = 0
frameerrors = 0
t = '{urn:mpeg:mpeg7:schema:2001}'
tree1 = ET.parse(own)
root1 = tree1.getroot().find(t+'DescriptionUnit').find(t+'Descriptor').find(t+'VideoSignatureRegion')
tree2 = ET.parse(os.path.join(indir, '.'.join(file.split('.')[:-1] + ['ddl'])))
root2 = tree2.getroot().find(t+'DescriptionUnit').find(t+'Descriptor').find(t+'VideoSignatureRegion')
#VSVideoSegment check
segments1 = root1.findall(t+'VSVideoSegment')
segments2 = root2.findall(t+'VSVideoSegment')
assert(len(segments1) == len(segments2))
for s1, s2 in zip(segments1, segments2):
xml_compare(s1, s2, t+'StartFrameOfSegment')
xml_compare(s1, s2, t+'EndFrameOfSegment')
bow1 = s1.findall(t+'BagOfWords')
bow2 = s2.findall(t+'BagOfWords')
assert(len(bow1) == len(bow2))
for j in range(len(bow1)):
err = xml_compare_segment(bow1[j].text, bow2[j].text)
if err > courseerrors:
courseerrors = err
#VideoFrame check
frame1 = root1.findall(t+'VideoFrame')
frame2 = root2.findall(t+'VideoFrame')
assert(len(frame1) == len(frame1))
for f1, f2 in zip(frame1, frame2):
con = xml_compare(f1, f2, t+'FrameConfidence', maximum_error=7)
compare_words(f1.find(t+'Word').text, f2.find(t+'Word').text)
if con > 4:
fs1 = f1.find(t+'FrameSignature').text
fs2 = f2.find(t+'FrameSignature').text
err = xml_compare_framesignature(fs1, fs2)
if err > frameerrors:
frameerrors = err
print("maximum errors in coursesignature:", courseerrors)
print("maximum errors in frameesignature:", frameerrors)
print("xml is valid")
def error(*args):
print(*args)
sys.exit(1)
def main():
#parse arguments
parser = argparse.ArgumentParser(add_help=True,
description="Check the conformance of a video signature")
parser.add_argument('--ffmpeg', '-f', default="ffmpeg", help="path to the ffmpeg binary")
parser.add_argument('--samples', '-s', default=".", help="path to the directory of sample files")
parser.add_argument('--mode', default=['xml', 'binary'], nargs='*', choices=['binary', 'binary_compressed', 'xml'], help="check against this signatures")
parser.add_argument('--tempdir', default='ffmpeg_output', help="directory, where the ffmpeg signatures are stored")
arg = parser.parse_args(sys.argv[1:])
# TODO add binary_compress once it is ready
videodir = os.path.join(arg.samples, 'Video')
sigdir = os.path.join(arg.samples, 'VideoSignatureDescriptor')
modes = {'binary': (os.path.join(sigdir, 'binary'), binary),
'binary_compressed': (os.path.join(sigdir, 'binary_compressed'), binary_compressed),
'xml': (os.path.join(sigdir, 'ddl'), xml)}
#create tempdir
if not os.path.isdir(arg.tempdir):
if os.path.isfile(arg.tempdir):
error('{} has to be a directory'.format(arg.tempdir))
else:
try:
os.makedirs(arg.tempdir)
except:
error('Error creating {}'.format(arg.tempdir))
for file in os.listdir(videodir):
sample = os.path.join(videodir, file)
for mode in arg.mode:
out = os.path.join(arg.tempdir, file + '.' + mode)
call_ffmpeg(arg.ffmpeg, sample, out, mode)
modes[mode][1](modes[mode][0], file, out)
print('signature extractor passed the test')
if __name__ == '__main__':
main()
_______________________________________________
ffmpeg-devel mailing list
ffmpeg-devel@ffmpeg.org
http://ffmpeg.org/mailman/listinfo/ffmpeg-devel
