ROBUST VIDEO FINGERPRINTS BASED ON SUBSPACE EMBEDDING
Regunathan Radhakrishnan and Claus Bauer
100 Potrero Ave, San Francisco CA 94103
regu.r@dolby.com, cb@dolby.com
ABSTRACT
We present a novel video ﬁngerprinting method based on subspace embedding. The proposed method is particularly robust
against frame-rate conversion attacks and geometric attacks
among other attacks including compression and spatial scaling. Using a sliding window, we extract ﬁngerprints from agroup of subsequent video frames. For the generation of theﬁngerprints, we ﬁrst calculate the basis vectors of a coarse
representation of this group of frames using a Singular Value
Decomposition (SVD). Then, we project the coarse representation of the video frames onto a subset of the basis vectors.
Thus, we obtain a subspace representation of the input video
frames. Finally, we extract the ﬁngerprint bits by projecting a temporal average of these representations onto pseudorandom basis vectors. Since the subspace is estimated fromthe input video data itself, any global attack on video such as
rotation would result in a corresponding change in estimatedbasis vectors thereby preserving the subspace representation.
We present experimental results on 250hrs of video to show
the robustness and sensitivity of the proposed signature extraction method.
Index Terms— Singular Value Decomposition, Robust
Video Fingerprints, Geometric attacks
1. INTRODUCTION
Robust ﬁngerprinting methods create a compact bitstream
representation of the underlying content so as to enable content identiﬁcation applications. The extracted ﬁngerprints
should remain similar even after the original content has been
modiﬁed by common signal processing operations.Geometricattacks and frame rate conversion attacks are the most challenging of all the modiﬁcations that a video ﬁngerprint
method should be robust against.
Past work on geometric attacks for image ﬁngerprinting
is mostly based on a transform that is invariant to geometricattacks. In [1], Swaminathan et al propose a image hash thatis based on a discrete polar Fourier Transform. The method
derives features invariant to geometric attacks based on thefact that the magnitude of Fourier coefﬁcients is independentof translation and - when expressed in polar coordinates - thecoefﬁcients are shifted if the underlying image is rotated. In

1-4244-1484-9/08/$25.00 ©2008 IEEE2245

Fig. 1. Region used for ﬁngerprint extraction[2],[3], an image hash algorithm was proposed based on theproperties of the Radon transform. In [2], Principal Components Analysis (PCA) is used to extract features from Radontransform coefﬁcients. In [3], the Radon transform is combined with a an autocorrelation step and 2 dimensional FFT.
The ﬁngerprints are extracted based on the sign of local energy differences between the coefﬁcients. In [4], the authors
propose an image hashing method resilient to image rotation
based on matrix invariants derived from the Singular Value
Decomposition (SVD) of pseudo-random tiles in the image.
In [5], a mesh based image hashing method is proposed. The
robustness of this method relies on the robust detection ofHarris corners to form the mesh. Aforementioned geometricattack invariant image hash methods could be applied to individual decoded video frames as well. However, for resilienceagainst frame rate conversion attacks it is desirable to create
ﬁngerprints from group of video frames rather than from individual video frames. Further, the application of these methods
to the creation of video ﬁngerprints would not be practical dueto the high complexity of the aforementioned methods.
In this paper, we propose a novel video ﬁngerprint extraction method based on subspace embedding. Using a sliding window, we extract ﬁngerprints from a group of subsequent video frames. For the generation of the ﬁngerprints,
we ﬁrst calculate the basis vectors of a coarse representation

ICASSP 2008• We divide the video in intervals of length Tint and associate a ﬁngerprint with each time interval. Tint is derived from the smallest frame rate conversion that wewould like the ﬁngerprint be robust against. For example, if the original video is at 30 fps and we would
like the ﬁngerprint to be robust for frame rate conversion down to 12fps, then we extract ﬁngerprints every
1of a second.
Tint = 12• For each time interval Tint (see Figure 2), we select agroup of frames around the time interval with a combined length of Tchunk > Tint . We refer to this groupof frames as (F1 , F2 , .., FN ). Here N = TchunkTint .

Fig. 2. Video Fingerprint Extraction based on SVDof this group of frames using a Singular Value Decomposition (SVD). Then, we project the coarse representation of thevideo frames onto a subset of the basis vectors. Thus, weobtain a subspace representation of the input video frames.
Finally, we extract the ﬁngerprint bits by projecting a temporal average of these representations onto pseudo-random basisvectors. Then, we extract ﬁngerprint bits by projecting a temporal average of these representations onto pseudo-randombasis vectors. Since the subspace is estimated from the input video data itself, any global attack on video such as rotation would result in a corresponding change in estimated basis
vectors thereby preserving the subspace representation. Since
performing SVD for each time step is computationally intensive, we update the SVD basis for the next time step using anincremental SVD update procedure proposed in [6].

2. PROPOSED METHOD
Figure 2 illustrates the steps in the proposed method forvideo ﬁngerprint extraction. The ﬁrst two steps in the proposed method ensure resilience against frame rate conversion
attacks by ﬁrst downsampling the input video to a reference
frame rate (say 12fps) and then by extracting ﬁngerprints
by summarizing information from a group of frames rather
than from individual frames. Also, extracting ﬁngerprints
at a reference rate (12fps) makes comparing ﬁngerprints oftwo videos at different frame rates easier than resorting todynamic programming for comparing signature sequences ofdifferent lengths as in [7].

2246

• Then, for every frame Fi we perform the following twosteps to ensure resilience against addition of graphics
and logos along the boundaries of video frames andcropping during rotation attacks. First, we downsample the image to a reference 120 × 160 resolution andcrop out a circular region for ﬁngerprint extraction asshown in Figure 1. This ensures that input images arein a common subspace of dimension 120 × 160. Fromeach image Fi , only region A is used for signature generation. This circular region is the only region of theimage that would survive all rotations of the input image. Region C is excluded as rotation would cause pixels in those regions to go out of the viewing area. Region B is excluded so as to allow for text overlay in thebottom one tenth of the original picture and to allow forplacement of logo or graphics around the corners. We
denote this cropped out image as Fic . Second, we obtain a coarse representation (Qi ) of Fic by dividing Fic
into M1 ∗ M2 blocks and averaging the intensity withineach block as given below:Qi (k, l) =1Wx ∗ Wy

kW
xlWy


Fic (m, n)m=(k−1)Wx n=(l−1)Wy

k = 1, 2...M1 ; l = 1, 2...M2
Here ’m’ and ’n’ represent the indices for the horizontal
and vertical dimensions for the image Fic and Fic (m, n)
is the intensity at that location. ’k’ and ’l’ represent theindices of the coarse image Qi . Wx ∗ Wy is the numberof pixels in each of the blocks that are averaged to get
one element Qi (k, l).
• Qi computed in the previous step is sensitive to geometric attacks and hence cannot be directly used forextracting ﬁngerprint bits. For instance, if the originalvideo is rotated, the values of Qi (k, l) will change. Inorder to obtain a representation of Qi that is invariant
to geometric attacks, we represent Qi in a subspace
using basis vectors that are estimated from the sequence (Q1 , Q2 , .., QN ) itself. For instance, in caseof a rotation, this ensures that the basis vectors are−→• In the previous step, by computing Qsi we have obtained a representation for Qi which is invariant togeometric attacks. In this step, we compute the tem−→poral average of the new coordinates (Qsi ). This step
ensures that extracted features are not dependent onvalues from individual frames but are derived from agroup of frames thereby providing robustness against
frame rate conversion. The temporal average G of(Qs1 , Qs2 , ...QsN ), is computed as shown below

rotated accordingly thereby preserving the subspace
representation of Qi . Let us represent the basis vectorsthat span the set (Q1 , Q2 , .., QN ) as (B1 , B2 , .., BN ).
Now, let us obtain the coordinates of Qi in the newspace spanned by (B1 , B2 , .., BN ) by projecting Qi
onto each of the basis vectors. Let us represent these−→s,2s,N). Note that Qi
projections as Qsi = (Qs,1i , Qi .., Qi
is a vector of dimension M1 ∗ M2 and is now repre−→
sented by Qsi a vector of dimension N in the new spacespanned by (B1 , B2 , .., BN ). The new representation−→Qsi is invariant to geometric attacks. This is becausethe basis vectors (B1 , B2 , .., BN ) are estimated from
(Q1 , Q2 , .., QN ). Therefore, if the original video isrotated, each Qi is rotated accordingly and so are thebasis vectors obtained from them.

NG(l) =l = 1, 2...NIn order to do so, we select the top L values of G for
the recent R time intervals and store this in a buffer D.
Then, D is a matrix (of size R × L) which summarizes
how the L projections vary over R time intervals.

Now, we describe how we obtain the basis vectors(B1 , B2 , .., BN ) from Q1 , Q2 , .., QN for each time
step. We create a matrix Y in which each column(j) represents a frame Qj . The number of rows is(M1 ∗ M2 ) (same as the number of elements in Qj
and scanned row by row). The dimensions of this matrix are (M1 ∗ M2 ) × N (N << (M1 ∗ M2 )). Therank of matrix Y is utmost N and we obtain the basis vectors (B1 , B2 , .., BN ) using the SVD of Y as
U SV . By deﬁnition of the SVD, the columns of Uthat span the column space of Y are the basis vectors(B1 , B2 , .., BN ).
Here U is of dimension (M1 ∗ M2 ) × N , S is of dimension N ×N and V is of dimension N ×N . S is the diagonal matrix with singular values in the order of decreasing magnitudes. The columns of V form the basis vectors which span the rows of Y. Using the basis vectors(B1 , B2 , .., BN ) obtained through SVD, we obtain thecoordinates of Qi in the new space Qsi = U  Qvi .HereQvi is a vector of dimension (M1 ∗ M2 ) × 1 which is
obtained from the matrix Qi of dimension M1 × M2by scanning the entries of the matrix in row by row toconvert it into a vector.
Performing SVD of Y for each time step is computationally expensive and its time complexity is O(((M1 ∗M2 )2 N ) + (N 2 (M1 ∗ M2 )) + N 3 ) [6]. Recall that
Y is of size (M 1 ∗ M 2) × N and each column of Y
has elements of Qi (i = 1, 2...N ). This means thatfor the next time interval the ﬁrst column of Y getsremoved and a new column is added. Therefore, instead of computing the SVD of Y for the current time
step, we could incrementally update the matrices U,Sand V obtained from the previous time interval. The
incremental procedure in [6] has a time complexity ofO((M1 ∗ M2 )N ∗ N ). Since N (e.g 36) is usually verysmall compare to M1 ∗ M2 (e.g 44*60) this reducescomputationally complexity to a large extent.

1  sQ (l)N i=1 i• Finally, we create K ﬁngerprint bits from the matrix
D by projecting it onto random basis vectors as in [8].
This hash bit extraction method proposed in [8] wasoriginally applied for generating robust hashes fromimages. First, we create the K random basis vectors(P1 , P2 , ...PK ) that have the same dimension as D.
Then, we compute the mean of these random vectors
and subtract them from the respective vectors. Finally,
the matrix D is projected onto this set of K vectors.
The ﬁngerprint bits are then derived by comparing theK projections to a threshold deﬁned as their median.
3. EXPERIMENTAL RESULTS
In this section, we present experimental results on proposed
video ﬁngerprint extraction method to show its robustness
against geometric attacks, frame rate conversion, compression and spatial scaling. We created a video database of 250
hrs and extracted ﬁngerprints for the original, MPEG-2 encoded video. Tchunk , Tint M1 , M2 ,N,K,L,R and the pseudorandom matrices are ﬁngerprint extraction parameters thatneed to be the same for both the original and modiﬁed video.
They were set to be the following: Tchunk = 3s,Tint =1
12 ,M1 = 44, M2 = 60, (dimensions of Qi s),N = 36,R =17, L = 26, (dimensions of the matrix D),K = 36 (thenumber of ﬁngerprint bits per time interval). In a second step,
the content was re-compressed, spatially scaled and rotated.
Apart from these modiﬁcations, we also changed the originalframe rate to 24fps. Then, we derived for the ﬁngerprints forthe modiﬁed video ﬁles. A sequence of 144 ﬁngerprints corresponding to 12s of query video clip was compared with acorresponding 12s in the original video clip using a hamming
distance measure. We record the percentage of ﬁngerprint bitsthat ﬂip (or the Bit Error Rate(BER)) for each comparison.

2247

BER
0.029854
0.03070.028626
0.029325
0.036313
0.020244
0.0429381
cdf of BER (case 1)
cdf of BER (case 2)

0.9
0.8
0.7
0.6
cdf

Attack type
Rotate by 2o & R
Rotate by 3o & R
Rotate by 10o & R
Rotate by 45o & R
Rotate by 45o , R & 30fps to 24fps
SS & R
SS, R & AS

0.5
0.4
0.3

Table 1. Robustness of Proposed Video Fingerprint for various Signal Processing Operations; SS: Spatial scaling, R: Recompressed at 1Mbps, AS: Aspect ratio change from 4:3 to
16:9
Table 1 presents the BER results for several modiﬁcations.
Note that the BER is not a function of the amount of rotation.
Only 3% of bits ﬂip on average for rotation attacks from 2
degrees to 45 degrees. Spatial scaling combined with aspectratio change and recompression causes the BER to go upto
4.29%.
Figure 3 illustrates the sensitivity of the proposed video
ﬁngerprints. We compare the CDFs of BERs for two cases inthis ﬁgure. Case 1 pertains to the scenario when we compare
ﬁngerprints of the original video and against the ﬁngerprintsof the modiﬁed video. The modiﬁcations include compression, spatial scaling, rotation and frame-rate conversion (denoted as comparison between video A and A’ in the ﬁgure).
Case 2 pertains to the scenario when we compare ﬁngerprintsof two different video ﬁles (denoted as comparison between
video A and B in the ﬁgure). For case 1, the probability thatthe BER between ﬁngerprints of video A and A’ ≤ 0.05 isabout 0.96. For case 2, the probability that the BER between
ﬁngerprints of two different videos A and B ≤ 0.05 is about
0.05. This shows that for a chosen BER threshold of 0.05 wewill be able to correctly identify modiﬁed video with probability 0.96 and the probability of declaring a different video
as original (false alarm) is about 0.05.
4. CONCLUSION
We proposed a novel video ﬁngerprint extraction method
based on subspace embedding. A ﬁngerprint is extracted foreach time interval in the video from a group of frames aroundthat time interval. we ﬁrst calculate the basis vectors of acoarse representation of this group of frames using a Singular
Value Decomposition (SVD). Then, we project the coarse
representation of the video frames onto a subset of the basisvectors. Thus, we obtain a subspace representation of the
input video frames. Finally, we extract ﬁngerprint bits byprojecting a temporal average of these representations onto
pseudo-random basis vectors. We use an incremental SVD
update procedure to estimate the SVD basis for each timeinterval in the video. The makes the ﬁngerprint extraction
method run in real-time. Since the video data is represented

2248

0.2
0.1
00

0.1

0.2

0.3

0.4

0.5

BERFig. 3. Comparison of Cumulative Distribution Functions(CDFs) of BER for two cases; case 1: Comparing video Aand A’; case 2: Comparing video A and B
using a set of basis vectors estimated from the input video
data itself, the extracted features are particularly resilient
to geometric attacks. The proposed ﬁngerprint have beenshown to be robust against other attacks as well including
compression, frame-rate conversion, aspect ratio change, spatial scaling. We have shown the robustness and sensitivityof proposed ﬁngerprints based on experiments on a 250hr
database.
5. REFERENCES[1] A.Swaminathan, Y. Mao and Min Wu, “Image hashingresilient to geometric and ﬁltering operations,” Proc. ofMMSP, 2004.
[2] F. Lefbvre, B.Macq and J.D. Legat, “Rash: Radon soft
hash algorithm,” Proc of EUSIPCO, 2002.
[3] J.S.Seo, Jaap Haitsma, T.Kalker and C.D.Yoo, “A robust
image ﬁngerprinting system using the radon transform,”
IEEE Signal Processing Journal: Image Communication,
vol. 19, pp. 325–339, 2004.
[4] S.S.Kozat, R. Venkatesan and M.K.Mihcak, “Robust perceptual image hashing via matrix invariants,” Proc. ofICIP, 2004.
[5] C. Lu, C.Y.Hsu, S.W.Sun and P.C. Chang, “Robust meshbased hashing for copy detection and tracing of images,”
Proc of ICME, 2004.
[6] M.Brand, “Fast low rank modiﬁcations of the thin singular value decomposition,” Linear Algebra and its Applications, vol. 415, pp. 20–30, 2006.
[7] X.S.Hua, X.Chen and H.J.Zhang, “Robust video signature based on oridnal measure,” Proc. of ICIP, 2004.
[8] J.Fridrich and M.Goljan, “Robust hash functions for digital watermarking,” ITCC, 2000.