On Improving Robustness of Video Fingerprints based on
Projections of Features
Regunathan Radhakrishnan

Claus Bauer

100 Potrero Ave
Dolby Laboratories Inc
San Francisco
California, USA

100 Potrero Ave
Dolby Laboratories Inc
San Francisco
California, USA

regu.r@dolby.com

cb@dolby.com

ABSTRACT

Keywords

In this paper, we study two methods to improve the robustness property of projection based hashing methods. For thisclass of hashing methods, a feature matrix is projected onto
a set of projection matrices. Then, the projected values arecompared to a threshold to derive the hash bits. In our previous work [4], we showed that the collision characteristicsof these methods can be optimized by a careful selection of
the projection matrices. The projection matrices were obtained using a Singular Value Decomposition (SVD) on aset of features from a training data set that minimized thecross-correlation between projected values. However, theseprojection matrices did not consider the eﬀect of content
modiﬁcations on the projected values.
In this paper, we study two methods to create projection
matrices that take into account the noise on projected values due to content modiﬁcations. The ﬁrst method derives
the projection matrices based on maximization of a generalized Rayleigh quotient. The second method derives the
projection matrices based on an eigenvector analysis of thediﬀerence between the signal and the noise correlation matrices. Based on experimental results, we show that theﬁrst method improves the robustness of the projected values while showing poor collision characteristics. The second method improves the robustness of the projected values
while maintaining good collision characteristics.

SVD, Moment Invariants, Rayleigh Quotient

1. INTRODUCTION
A Media ﬁngerprint extraction method generally consistsof the two subsequent steps a) Robust Feature Extraction
and b) Robust Hash Extraction. The ﬁrst step ensures thatthe extracted features are representative of the underlying
perceptual content. The second step ensures that these features are converted into signature bits in a robust fashioni.e small changes in feature values do not result in drasticchanges in extracted hash bits i.e for every x ∼ y there isH(x) ∼ H(y) with very high probability. This requirement
disqualiﬁes the use of normal cryptographic hash functions
for the conversion of the feature values into signature bits.
The second step also serves to provide a compact representation of the features so that the signature bits can be stored
and searched eﬃciently. Another property that is important
for this robust hash extraction step is the collision property.
A robust hash function is said to have a good collision property if for every (x = y), H(x) = H(y) with a very highprobability.
We consider a content identiﬁcation application with alarge database of media ﬁngerprints. Any media ﬁngerprintthat is extracted from a query media object is comparedagainst this database of media ﬁngerprints during the identiﬁcation process. As the size of the database, i.e., the number of ﬁngerprints in the database in terms of number ofhours of media increases, it is desirable that the uniquenessof the ﬁngerprint codewords is preserved. The uniquenessproperty of the ﬁngerprint codewords guarantees that theﬁngerprint database scales to a large number of ﬁngerprints.
Instead, if certain ﬁngerprint codewords are more likely tooccur than others, then the uniqueness property vanishes
as the database size grows. This leads to a computationally more expensive ﬁngerprint matching algorithm. To see
this, we consider a hash-table based searching method formatching the query ﬁngerprints against the ﬁngerprints inthe database. The database is indexed using the individual ﬁngerprint codewords. Each ﬁngerprint codeword in thehash table points to any location in any ﬁngerprint in the
database where that ﬁngerprint codeword is present. The
number of links per ﬁngerprint index in the hash table will bereferred to as number of collisions. If a ﬁngerprint codeword
is unique, one can quickly ﬁnd its match in the database.
As the uniqueness reduces, one has to perform more lookups and pick the best match in terms of smallest hamming

Categories and Subject Descriptors
H.3 [Information Storage and Retrieval]: Content Analysis and Indexing

General Terms
Video Fingerprinting, Singular Value Decomposition, RayleighQuotient, Perceptual Hashing

Permission to make digital or hard copies of all or part of this work forpersonal or classroom use is granted without fee provided that copies are
not made or distributed for profit or commercial advantage and that copies
bear this notice and the full citation on the first page. To copy otherwise, torepublish, to post on servers or to redistribute to lists, requires prior specificpermission and/or a fee.
LS-MMRM’09, October 23, 2009, Beijing, China.
Copyright 2009 ACM 978-1-60558-756-1/09/10 ...$10.00.

59bits are extracted from the feature matrix Q using a robust
hash function. The robust hash function projects the feature matrix (Q) onto L projection matrices Pi , i = 1, 2, ...L.
Then, each projected value is compared with a threshold T h
to obtain L bits bi . If B.Pi < T h, then bi = 0 else bi = 1.
In [4], we proposed a method to obtain these projection
matrices that are optimal in terms of collision performance.
Here, we brieﬂy recall the procedure in the following threesteps.
Step 1: Obtain a training dataset of media content andextract features Q1 , Q2 , ...QM . Here M is the number oftraining instances. The dimension of each feature matrix Qi
is R = G × N .
Step 2: Then, we compute the covariance matrix C f eat(dimension R*R) of the features from the training set
Q1 , Q2 , ...QM as given by

distance from the query ﬁngerprint. Thus, ﬁngerprints witha small number collisions per ﬁngerprint codeword will result in shorter search duration. Databases containing ﬁngerprints with an average low collision number are more scalable
to large database sizes than databases with a high averagecollision number per ﬁngerprint.
In our previous work [4], we studied the collision propertyof one of the robust hash functions proposed in [3]. The robust hash proposed in [3] ﬁrst projects a feature matrix onto
a set of projection matrices. Then, the projected values arecompared to a threshold to generate hash bits. In [4], we
showed that the collision performance of these methods canbe optimized by a careful selection of the projection matrices. Speciﬁcally, the projection matrices were obtained usinga Singular Value Decomposition (SVD) on a set of featuresfrom a training set that minimized the cross-correlation between projected values. However, the projection matrices
did not consider the eﬀect of content modiﬁcations on the
projected values.
In this paper, we study two methods that create projection matrices that take into account the noise introduced bycontent modiﬁcations on these projected values. The ﬁrst
method derives the projection matrices based on the maximization of a generalized Rayleigh quotient and the second
method derives the projection matrices based on an eigenvector analysis of diﬀerence between the signal and the noisecorrelation matrices. Both of these methods were originallyproposed for deriving noise-robust features from audio spectrograms in [1]. Based on experimental results, we showthat the ﬁrst method improves the robustness of the projected values while losing heavily in terms of collision performance. The second method improves the robustness ofthe projected values while showing a poor collision performance. Also, we interpret the projection matrices obtained
through these two methods and compare with those derived
using the SVD procedure in [4].

2.

MC f eat (k, l) =1
(Qi − E(Qk ))(Qil − E(Ql ))M i=1 kMi1
Here E(Qk ) = M
i=1 Qk and k, l = 1, 2...R.
Step 3: Once we have computed the covariance matrixof the features from the training set, we can now computethe eigenvectors of the matrix C f eat that satisfy the relation, V −1 C f eat V = D, using PCA (Principal Components
Analysis). Here the columns of V (dimension R*R) are theeigenvectors of the covariance matrix C f eat and are represented as φ1 , φ2 , ...φR . D is a diagonal matrix with eigenvalues (E1 , E2 ...ER ) as its main diagonal elements and zero
elsewhere.
Now, we transform the input feature vector Q to a L dimensional space by projecting it onto the ﬁrst L eigenvectors φ1 , φ2 , ...φL and obtain H1svd , H2svd , ...HLsvd respectively.
Here Hksvd is the projection of Q onto φk . In [4], we showedthat the ﬁngerprints derived using these projection matrices
have lower average number of collisions than ﬁngerprints derived using random projection matrices.
However, these projection matrices do not consider thenoise on the projected values due to content modiﬁcations(Hisvd ). In the following two subsections we describe two
methods that derive the projection matrices which accountfor this noise.

PROPOSED APPROACHES

The ﬁrst step in a media ﬁngerprint extraction process isthe derivation of robust features from the video content thatare invariant to various processing operations of the content.
Let us represent the extracted robust features by a matrix
Q. For all the experiments in this paper, Q is a matrix with
G × N elements that attempts to capture the appearance
and motion information from the input video. The input
video is ﬁrst temporally downsampled to 12 fps. A letterbox detector detects eventual black bars on the sides of thepicture and removes them. Then, every frame is spatiallydownsampled to 120∗160 (Height×W idth) resolution. The
N columns in the feature matrix Q correspond to N video
frames in a buﬀer including the current frame. We use abuﬀer of 3s (N = 12 × 3) to capture motion information.
The G rows correspond to a set of moment invariants extracted from each frame in the buﬀer. We extract 7 moment
invariants from 5 concentric circular regions in each frame(G = 5 × 7). Moment invariants are global measures of animage surface that are invariant to translation, rotation andscaling and were originally proposed for text pattern recognition in [2]. Now, each column of the matrix Q attempts
to capture the appearance of the corresponding frame of thevideo in the buﬀer by measuring how the 7 moment invariants change over the 5 regions. In the second step, hash

2.1 Noise Robust Projection Matrices basedon Rayleigh Quotient
Consider the case where the original video is modiﬁed bycompression, cropping and/or rotation. These operations
add noise to the extracted feature vector. The noisy featurematrix is denoted as Q. Let the projections obtained byprojecting Q onto L projection matrices be represented as
H1 , H2 , ...HL . Then, the noise on ith projected value is Zi =Hi − Hi . Here Hi is the projection of original feature matrix
Q onto the ith projection matrix.
Step 1: Obtain a training dataset of media content andextract features Q1 , Q2 , ...QM . Here M is the number oftraining instances. The dimension of each feature matrix
Qi be R = G × N . We also create modiﬁed versions ofcontent and compute the corresponding modiﬁed features
Q1 , Q2 , ...QM .
Step 2: We compute the noise in the feature vectors forthe training set W 1 , W 2 , ...W M . Here W = Q − Q and W
is of the same dimension as Q.

  

 

60





Step 3: We compute the covariance matrix C f eat (dimension R*R) of the features from the training set
Q1 , Q2 , ...QM as given by:original feature vector. The projection matrices that minimize this reconstruction error can be found as eigenvectorsof C f eat − C noise . We select the ﬁrst L signiﬁcant eigenvectors of this diﬀerence between signal and noise covariance matrices ,φs−n, φs−n, ...φs−n, as our projection matri1
2
L
ces. We can now transform any input feature vector Q toa L dimensional space by projecting it onto the projection
matrices φs−n
, φs−n, ...φs−n
to obtain H1s−n , H2s−n , ...HLs−n12L
respectively. Here Hks−n is the projection of Q onto φs−n.
kM

C f eat (k, l) =1
(Qi − E(Qk ))(Qil − E(Ql ))M i=1 kMi1
Here E(Qk ) = M
i=1 Qk and k, l = 1, 2...R. We refer
f eat
to C
as the signal covariance matrix.
Step 4: We compute the noise covariance matrix C noise(dimension R*R) of the noise in the features from the training set
W 1 , W 2 , ...W M as given by

3. EXPERIMENTAL RESULTS

M

C noise (k, l) =1
(Wki − E(Wk ))(Wli − E(Wl ))
M i=1



M
i
1
Here E(Wk ) = M
i=1 Wk and k, l = 1, 2...R. We refernoise
as the noise covariance matrix.
to C
Step 5: Given the signal covariance matrix (C f eat ) andthe noise covariance matrix (C noise ),the generalized RayleighpC f eat p
quotient is given by pC
noise p and can be maximized by solving the following generalized eigenvalue problem:

C f eat p = rq C noise p
Here, p is a generalized eigenvector. rq is the corresponding generalized eigenvalue also denoted as the Rayleigh quotient. The most signiﬁcant generalized eigenvector p obtained as a solution to this eigenvalue problem maximizes
the generalized Rayleigh quotient. Maximizing Rayleighquotient ensures that the projected values have a higher
variance along the signal direction while having a small variance along the noise direction thereby improving the signal to noise ratio of the projected values. We select the
L most signiﬁcant generalized eigenvectors of this solution
rq
rq
,φrq
1 , φ2 , ...φL , as our projection matrices. We can now
transform any input feature vector Q to a L dimensionalrq
rq
space by projecting it onto the projection matrices φrq
1 , φ2 , ...φL
rq
rq
rq
rq
to obtain H1 , H2 , ...HL , respectively. Here Hk is the projection of Q onto φrqk .

2.2 Noise Robust Projection Matrices basedon Difference between Signal and Noise
Covariance Matrices
In this method, we compute the signal covariance matrix (C f eat ) and the noise covariance matrix (C noise ) froma training dataset as explained in steps 1-4 in the previous
subsection. Instead of maximizing the Rayleigh quotient toobtain the projection matrices, here we compute projection
matrices that minimize the following mean squared reconstruction error.
M

 

i=1



(Qi − Qi )2 

Here Qi = (Qi .p)p. Recall that Qi is the noisy feature
extracted from modiﬁed content. Then, Qi is a projectionof the noisy feature Qi along the direction p. By minimizing the reconstruction error in the equation above, we attempt to ﬁnd projection matrices (p) such that the transformed noisy feature vector is as close as possible to the61

In this section, we present experimental results on collision performance and robustness of three methods for selecting the projection matrices. The ﬁrst method is proposedin [4]. It is based on a SVD of the signal covariance matrix(C f eat) computed from a training set. The L projection matrices obtained in this manner are denoted to as φ1 , φ2 , ...φL .
The other two methods considered in this paper are methods that take into account the noise introduced by content
modiﬁcations to derive the projection matrices. The second
method obtains projection matrices based on maximizationof Rayleigh quotient. The projection matrices obtained usrq
rq
ing this method are denoted as φrq
1 , φ2 , ...φL . The third
method obtains projection matrices based on the SVD ofdiﬀerence between the signal and the noise covariance matrix. The projection matrices obtained using this method
are denoted as φs−n
, φs−n, ...φs−n. The feature matrix Q
1
2
Lfor all experiments in this paper is a matrix of dimensions
35×36 (G×N ) where 36 corresponds to a 3s buﬀer of frames
at 12fps and 35 corresponds to the 7 moment invariants computed from 5 concentric circular regions of each frame in the
buﬀer.

3.1 Collision analysis
First, we extract 22 bit ﬁngerprint codewords (L = 22)
from a 25 min video clip using three sets of projection mas−ntrices: (i) φi (svd), (ii) φrq(s-n). In all threei (rq),(iii) φicases, for the selection of the projection matrices, we used
the same oﬄine training set of 94 hrs of content to computeboth the signal covariance matrix (C f eat ) and the noise covariance matrix (C noise ). In the case of (i), the noise covariance matrix doesn’t play a role in the selection of projection matrices. This method can be considered as a baseline
method. Let us denote the collection of ﬁngerprint codewords extracted from the 25 min clip using projection matrices from (i) as S svd . We also let those extracted using
projection matrices from (ii) be denoted as S rq and those
extracted using projection matrices from (iii) be denoted as
S s−n . Then, we compute the average number of collisions
for the ﬁngerprint codewords in each of the three sets namely
S svd ,S rq and S s−n .
In order to study the collision performance of these threesets, we ﬁrst add ﬁngerprint codewords extracted from uniquecontent (content that is unrelated to the 25 min clip) to the
database. Then, we compute the average number of collisions as we increase the number of ﬁngerprint codewordsof unrelated content from 1 hr to upto 3hrs. Ideally, there
should be no change in the average of number of collisions
as we add unrelated content to the database.
Table 1 illustrates the collision performance for the threesets of projection matrices.The average of number of collisions for S svd increases from 5.437 to 5.541 (see column C)
as we add ﬁngerprint codewords 3.37hrs of unrelated con-

3.3 Discussion

Table 1: Collision Performance A: Number of fingerprint codewords; B: Number of hours in DB; C:
Avg. num of collisions for φi ; D: Avg. num of collis−nsions for φrq;
i ; E: Avg. num of collisions for φiA
B
C(svd) D(rq) E(s-n)
20705 0.479
5.437
7.483
4.372
145813 3.375
5.541
43.114
4.49

In the previous subsections, we illustrated the collisionand robustness performance of the projections matrices derived using three methods. We showed that the third method(s−n) has a performance similar to that of the ﬁrst method (svd)in terms of collision and has the best robustness among thethree sets. In otherwords, the third method(s − n)improves
robustness of the ﬁngerprints while maintaining the collision
statistics of the baseline method (svd). In this section, we
further discuss and compare the three diﬀerent types of projection matrices in all three cases. Figure 1 shows the ﬁrst
8 projection matrices obtained through the SVD procedure.
Each of the projection matrices are of the same dimension as
the feature matrix Q (35×36). We recall that the number ofrows correspond to 5 × 7 moment invariants extracted fromeach frame in the buﬀer and the number of columns correspond to the number of frames in the 3s buﬀer (3 × 12).
Projection matrices on the top & bottom left of Figure 1
can be interpreted as those capturing appearance information alone from the feature matrix Q. This is represented by
the fact that the values along the columns of the projection
matrices 1 & 3 are similar for every row. Also, note that thepatterns along rows are repeated 5 times. This is due to thefact that the 7 moment invariants computed from the 5 concentric circular regions are correlated and hence the projection matrix values are also correlated. The other projection
matrices shown in the Figure 1 capture both appearance
and motion information as can be seen from the changing
patterns across the columns (time) for these projection matrices. Similarly, ﬁgure 2 shows the ﬁrst eight projection
matrices obtained using the diﬀerence between the signal
and the noise covariance matrices (φs−n). We note that theilook very similar to φi and hence
projection matrices φs−nitheir collision performance is similar. In contrast to theseprojection matrices, the projection matrices obtained using
maximization of Rayleigh Quotient look very diﬀerent andare not eﬀective in capturing the appearance or motion of
the underlying video content(see Figure 3). Hence, the ﬁngerprints derived using this set of projection matrices don’t
exhibit good collision properties. In contrast, they provide
high robustness against content modiﬁcations.
We can also compare the robustness of the projected values against content modiﬁcations for the projection matrices (φs−nand φi ). We consider the case where the originalivideo is modiﬁed by compression, cropping and/or rotation.
These operations add noise to the extracted feature vector.
Let us represent the noisy feature matrix as Q. Also, let
the projections obtained by projecting Q onto L projection
matrices (φi ’s) be represented as H1 , H2 , ...HL . Then, thenoise of the ith projected value is Zi = Hi − Hi . Here Hi is
the projection of original feature matrix Q onto the ith projection matrix (φi ). Then, we can compute the ratio of thei)signal variance and the noise variance (SN Rsvd = var(H)
var(Zi )as a measure of the robustness of the projections obtainedusing φi . The higher this ratio is, the lower is the ﬁngerprint
BER. Table 3 shows the SN Rsvd for various modiﬁcationsof the original content. We note that the cropping attack
has the lowest SNR while the rotation attack has the highest SNR. Correspondingly, the BER is highest for cropping
attack and in lowest for rotation attacks. (see Table 2).
Similarly, let the projections obtained by projecting Q
onto L projection matrices (φs−n’s) be represented asiTable 2: Robustness Performance ;φi (svd)
φrq
φs−n
i
i
compression 0.0222 0.0306 0.0207
rotation
0.05910.032 0.0534
cropping
0.1854 0.0986 0.1656
bright up
0.0972 0.0395 0.0865
bright down 0.1013 0.0483 0.0895
asp ratio
0.1000 0.0522 0.0926

tent. On the otherhand, the average number of collisions for
S rq increases from 7.483 to 43.114 (see column D) for thesame increase in number of ﬁngerprint codewords from unrelated content. The average number of collisions for S s−n
increases from 4.372 to 4.49 (see column D). We computed
the increase in the average number of collisions for every
additional hour of unrelated content included (referred to as
collision slope) for all three methods from this table. The
collision slopes for S svd ,S rq and S s−n are 0.035,12.30 and
0.04 respectively. This implies that the projection matrices(φs−n) derived using the third method have similar collisioni
performance as that of the base-line method (φi obtainedusing SVD of C f eat ) whereas the collision performance ofthe projection matrices (φrqi ) obtained by the maximizationof the Rayleigh coeﬃcient is inferior to the baseline method
and the third method.

3.2 Robustness analysis
In order to study the robustness of the ﬁngerprints created by the three sets of projection matrices (φi ,φrq
i ,andφs−n), we created modiﬁed versions of the reference conitent. The attacks on the content include both geometric (rotation,cropping,aspect ratio change) and non-geometric attacks (compression, brightness change). Then, we compare
the ﬁngerprints of the original content to those of the attacked content and record the average Bit Error Rate (BER)
for each of the three sets of projection matrices. Table 2
summarizes the robustness performance of the these threesets of projection matrices. Since both φrq
and φs−nareiiderived taking into the noise introduced by content modiﬁcations, they have a lower average BER than the ﬁngerprints
derived using φi . Note that the ﬁngerprints derived using
φrq
have the lowest BER among the three. But the collii
sion performance of this method was the worst among thethree. This implies that φrq
i captures aspects of the featurethat are not sensitive to content and are also most robust
to noise induced by modiﬁcations of the content. The projection matrix φs−n
has a similar collision performance toithat of φi and also improves the robustness against attacks.
For instance, the average BER for cropping attacks has improved from 0.1854 to 0.1656 (almost 2% improvement). For
certain attacks such as compression, the improvement is notsubstantial even with φs−n.
i  



62

rotationbright downbright up
cropping
asp ratio

Table 3: SNR table;
SN Rsvd SN Rs−n SN Rs−n − SN Rsvd
44.492745.64811.155323.1246
23.4984
0.373830.9174
31.56450.64718.95639.26050.304123.342823.80300.4602

10

10

10

10

20

20

20

20

30

30

30

30

10 20 30

10 20 30

10 20 30

10

10

10

20

20

20

20

10

10

10

20

20

20

20

30

30

30

30

10 20 30

10 20 30

1010

10 20 30

10 20 30

10 20 30

10

10

10

10

20

20

20

20

30

30

30

30

10 20 30

10 20 30

10 20 30

10 20 30

Figure 2: First eight projection matrices of φs−n
.
i
30

30
10 20 3030
10 20 3030
10 20 30

10 20 30

Figure 1: First eight projection matrices of φi .
s−n 
s−n


, H2s−n , ...H. Then, the noise of the ith projected
H
1
L
s−n
s−n
s−n

= H
−H
. Here H s−n is the projecvalue is Z

10

10

10

10

tion of the original feature matrix, Q onto the ith projection
matrix (φs−n). Again, we can compute the ratio of signal
i

20

20

20

20

variance and noise variance (SN Rs−n =

30

30

30

30

i

i

i

i

var(His−n )var(Zis−n )) as ameasure of the robustness of the projections obtained using
φs−n. Table 3 (second column) shows the SN Rs−n for varii
ous attacks on original content. Note that SN Rs−n is better
than SN Rsvd for all attacks as shown in the third columnof this table.

4.

10 20 30

CONCLUSIONSIn this paper, we studied two methods to improve the robustness property of projection based hashing methods. The
two methods derive projection matrices taking into accountthe noise on the extracted features due to content modiﬁcations. Both methods use an oﬀ-line training set to estimate asignal covariance matrix and a noise covariance matrix. The
ﬁrst method considered in this paper, derives the projection
matrix by maximizing the Rayleigh Quotient. The second
method derives the projection matrices based on eigenvector
analysis of the diﬀerence between the signal and noise covariance matrices. Both of these methods consider the eﬀect
of noise on extracted feature while deriving the ﬁngerprints

10 20 30

10 20 30

10 20 30

10

10

10

10

20

20

20

20

30

30

30

30

10 20 30

10 20 30

10 20 30

10 20 30

Figure 3: First eight projection matrices of φrqi .

63

5. REFERENCES

which is unlike our previous method proposed in [4]. Basedon experimental results, we showed that the ﬁrst method
improves the robustness of the projected values but resultsin larger number of collisions than in the case of method in[4]. The second method improves the robustness of the projected values while maintaining the collision performance asin [4]. Although the robustness of the ﬁngerprints obtainedby using the second method improves, the amount of improvement is not substantial. Our future work will focus on
further improving robustness while maintaining good collision characteristics.

[1] Burges, C.J.C. Platt, J.C. and Jana, S. Distortion
discriminant analysis for audio ﬁngerprinting. IEEE
Transactions on Speech and Audio Processing, May
2003.
[2] Hu,M.K. Visual pattern recognition by moment
invariants. IRE Trans. Info. Theory, IT-8:179–187,
1962.
[3] J.Fridrich and M.Goljan. Robust hash functions for
digital watermarking. ITCC, 2000.
[4] R.Radhakrishnan and C.Bauer. On improving thecollision property of robust hashing based on
projections. Proc. of ICME, 2009.

64