Content-based Video Signatures based on
Projections of Difference Images
Regunathan Radhakrishnan and Claus Bauer
Dolby Laboratories Inc
100 Potrero Ave, San Francisco, CA
Email: {regu.r,cb}@dolby.com
Abstract— We propose a novel video signature extraction
method based on projections of difference images between
consecutive video frames. The difference images are projected
onto random basis vectors to create a low dimensional bitstream
representation of the active content (moving regions) between twovideo frames. A sequence of these signatures serves to identify theunderlying video content in a robust manner. Our experimental
results show that the proposed video signature is robust to mostcommon signal processing operations on video content such ascompression, resolution scaling, brightness scaling.

I. I NTRODUCTION
The goal of content-based video signature extraction is toobtain a compact bitstream representation of the underlying
video content that is robust to various signal processing
operations. Past work on video signature extraction can bebroadly classiﬁed under two approaches. The ﬁrst approach
derives signatures from a subset of frames selected from thevideo sequence either by shot detection followed by key frame
extraction[2] or by random sampling[3]. One of the maindrawbacks with this approach is that the extracted signatures
cannot identify a portion of the video clip that is shorter
than the original shot. The method requires the same subset
of frames to be selected from a video shot for signature
extraction. The second approach is to apply robust image
hashing techniques such as [4],[5] to individual video frames.
Since this method extracts ﬁngerprints from individual video
frames it can identify smaller sequences of video than theﬁrst method can. Our proposed scheme follows the second approach. However, unlike prior approaches, our method works
with difference images. The use of difference images leads toa derivation of ﬁngerprint bits from active moving regions of
the video frame alone. This, in turn, translates to a smaller
video ﬁngerprint length for our proposed method than forprevious methods which try to capture all the informationin an individual video frame. A coarse representation of thedifference image of consecutive video frames is used to extract
signature bits. We use the robust visual hash proposed in[1] to create a low dimensional bitstream representation of
the difference images in the video sequence. The extracted
signature serves as an identiﬁer for the underlying video
content and is invariant to most signal processing operations.
II. P ROPOSED V IDEO S IGNATURE E XTRACTION
The proposed signature extraction consists of the following
two steps: (i) Video feature extraction (ii) Computation of thesignature bits from extracted features.

1-4244-1274-9/07/$25.00 ©2007 IEEE

341

A. Video Feature Extraction
The goal of the video feature extraction block is to obtaina set of robust features that are invariant to certain signal
processing operations on the video. In this section, we describe
a set of such robust features extracted from a coarse representation of the absolute values of intensity differences between
consecutive frames. This set of features is chosen such thatthey survive a variety of processing of the video, including
compression, color space conversion, intensity adjustment,
addition of computer generated graphic objects and format
conversions.
Figure 1 illustrates the proposed video feature extraction
approach. An absolute difference image is computed between
adjacent video frames (frame(n) and frame(n+1)). This step
ensures that we only extract signature bits based on active
moving regions between video frames. We veriﬁed that theamount of motion between two adjacent frames can be as small
as in a talking head sequence and still our method can identify
the sequence. It will, however, fail if the video sequence is of astatic graphic image and there is no activity. The next step is todownsample and crop the absolute difference image. This step
ensures that the extracted features are invariant to interlaced
and progressive video formats and addition of graphics andletterboxes on the corners of the individual frames. Then, thecropped absolute difference image is tiled horizontally andvertically. Finally, the intensities of the absolute difference
image within each tile are summed up to obtain a coarse absolute difference image. Let us represent the cropped absolutedifference image by Δ. We obtain a coarse representation (Qv) of Δ by averaging pixel intensities in image blocks of size
Wx × Wy such that K × Wx = 120 and L × Wy = 160 . Qv
is of size (K × L)

Qv (k, l) =1
Wx ∗ Wy

kW
x

lWy


Δ(i, j)i=(k−1)Wx j=(l−1)Wy

k = 1, 2...K; l = 1, 2...L
Here i and j represent the indices for the horizontal andvertical dimensions for the absolute difference image Δ. k
and l represent the indices of the sub-blocks of the absolutedifference image Δ. This coarse representation (Qv ) helps us

MMSP 2007

Fig. 1.

was processed in a variety of ways to simulate the processing
in modern broadcasting and post production facilities. We
considered the following processing operations: Brightness
modiﬁcation by 10%, Median noise reduction, Addition of
random ﬁlm grain type noise, MPEG compression and decompression at 2,4,8 and 12Mbps, Down conversion from HD to
SD, Logo and Graphic insertions. Overall, we created 432 test
cases from the original 36 one-minute video sequences.

Video Feature Extraction

to achieve robustness by allowing for certain variations withina block while preserving the average intensity within a block.
B. Robust Hash
This block takes as input the matrix Qv , and generates
the signature by generating K hash bits. We use a robust
hash function for this purpose as small perturbations in thevideo features caused by signal processing operations suchas compression, ﬁltering etc would not change the hash bits
drastically. The Robust hash function also serves to reducethe bit-rate of the signature stream. Let us represent thedimensions of the matrix Qv by (M × N ). By using a robust
hash, instead of sending (M × N ) values we only send K bits.
A robust hash function is unlike a regular cryptographic hashfunction. A cryptographic hash function changes its output
for every single bit change in the input. However, we would
like our hash output to change slowly with small changes infeatures. This would enable us to allow for certain signal
processing operations on the content which do not change
the content but only slightly disturb the features. We use
one such robust hash function proposed in [1] for generating
the hash bits from the feature matrix, Qv . We generate K
random matrices each with the same dimensions as the matrix,
Qv (M × N ). The matrix entries are uniformly distributed
random variables in [0, 1]. The state of the random number
generator is set based on a key. Let us denote these randommatrices by P1 , P2 , ...PK each of dimension (M × N ). We
compute the mean of matrix Pi and subtract it from eachmatrix element in Pi (i goes from 1 to K). Then, the matrix
Qv is projected onto these K random vectors as shown below:
Hk =

M 
N


Qv (i, j) ∗ Pk (i, j)(1)

i=1 j=1

Here Hk is the projection of the matrix Q onto the random
vector Pk . Using the median of these projections ( Hk , k =1, 2K) as a threshold, we generate K hash bits for the matrix
Qv . We generate a hash bit ’1’ for k th hash bit if the projection
Hk is greater than the threshold. Otherwise, we generate a hashbit of ’0’.
III. E XPERIMENTAL R ESULTS
A. Test Content
The test content used for the performance assessment of
the proposed video signature extraction consisted of 36 oneminute original video clips of a variety of content types invarious formats. The video formats include standard broadcast formats such as Standard Deﬁnition (SD) 480/30i, HighDeﬁnition 1080/30i and 720/60p (HD). Each of the test clips

342

B. Parameter Settings
The signature extraction parameters were empirically selected and set as described below. The size of coarse difference
image was set to be 8 × 9 (K = 8, L = 9). The number ofrandom vectors for the hash was chosen to be 36. This meansfor every pair of frames we create a signature of length 36
bits.
C. Sensitivity of the Proposed Signature
Before we show the robustness of the proposed signature, we ﬁrst illustrate how sensitive the signature is to theunderlying content. Let us assume we perform a MPEG
compression attack on certain content which causes x% of theoriginal signature bits to be ﬂipped. Now, when comparing
the signatures of two different video ﬁles we would like thepercentage of bits that ﬂip to be much larger than x%. Then,
we can say that the proposed signature is sensitive enoughto be used as a content identiﬁer and is robust to MPEG
compression attack. To verify the sensitivity of the proposed
signature, we perform the following for two scenarios. Under
scenario 1, we compare the signatures from two different
video ﬁles (A and B). We compute the histogram of hamming
distances between signature of A and signature of B. Under
scenario 2, we compare the signature of A against the signatureof some modiﬁed version (e.g MPEG Compression) of A. We
compute the histogram of hamming distances between thesignature of A and the signature of modiﬁed A. A robust
signature would have a distribution that is heavily skewed
near hamming distance value of zero under scenario 2. A
signature that is also sensitive to underlying content, should
show minimal overlap between the histograms under scenario
1 and scenario 2. In other words, the BER for comparison
between signatures of A and B should be larger than the
BER for comparison of signatures of A and modiﬁed A.
Figure 2 shows the comparison of histogram of hamming
distances for scenario 1 and MPEG compression (scenario 2)
and it conﬁrms that there is indeed minimum overlap between
the two histograms as we expected. Note that most of thehamming distance values for MPEG compression attack is
below 15 whereas the hamming distance for two different ﬁles
is atleast 15. The overlap is small even for one of the severe
modiﬁcations on content (Rotation by 3o ) as shown in Figure
3.
D. Robustness of proposed video signature
In this section, we present more results to show the robustness of the proposed video signature to various signal processing operations. Towards that end, we ﬁrst extract the signaturefrom the original video content and then compare it against theAttack
MPEG-8Mbps
MPEG-12Mbps

0.45
Two different video files
MPEG Compression

0.4

B463950445898

C
84438
84672

D
0.15260.1462

0.35

TABLE I

0.3

ROBUSTNESS OF P ROPOSED V IDEO S IGNATURE FOR MPEGC OMPRESSION ATTACK ON H IGH -D EFINITION SOURCES ; B:BC,
N um.BitErrors; C: N um.F rames; D:BER = (SigSize∗C)
SigSize = 36

0.25
0.2
0.15
0.1
0.05
0
−5

0

5

10

15

20

25

30

35

AttackMPEG-2Mbps
MPEG-4Mbps

40

Fig. 2. Comparison between histograms for scenario 1 and scenario 2 (MPEG
Compression)

C
31170
31329

D
0.15570.1420TABLE IIROBUSTNESS OF P ROPOSED V IDEO S IGNATURE FOR MPEGC OMPRESSION ATTACK ON SD SOURCES ;0.45
Two different video files
Rotate 3 degrees

0.4

B
174744160204

0.35
0.3

0.2
0.15
0.1
0.05
0
−5

0

5

10

15

20

25

30

35

40

Fig. 3.
Comparison between histograms for scenario 1 and scenario2(Rotation by 3o )signature extracted from processed (attacked) video content
using a hamming distance measure. Then, we compare theBER (Bit Error Rate) between signatures of original content
and its modiﬁed content with the BER between signatures of
two different video ﬁles. In the previous section, we showedthat on an average 15 out of 36 bits ﬂip, when comparing
signatures of two different video ﬁles. This means that the
average BER for this case is 41%. In the remainder of thissection, we will compare this BER of 41% to the BER caused
by various attacks to illustrate the robustness of the signature.
1) MPEG Video Compression: Tables I and II summarize
the performance of the video signature for MPEG compression
attack on HD sources and SD sources respectively. Note that
MPEG compression at 8Mbps causes a BER of 15% whichis smaller than the BER of 41%. Therefore, we can conclude
that the proposed signature is robust to MPEG compression
attack. The higher the bitrate used for compression the closer
the compressed video is to the original. Consequently, fewer
number of bits in the signature ﬂip.
Figure 4 illustrates the effect of increasing the MPEGcompression bitrate from 500kbps to 4Mbps on the robustnessof the signature for a SD source video.
2) Brightness scaling: Table III shows that the proposed
signature is robust to brightness scaling by +/-10% as the
maximum BER for this case (11.44%) is far less than the BER
of 41%. Since the signature extraction is based on difference
images, uniform scaling of the brightness across frames in343

video doesn’t affect the signature bits as much as MPEG
compression does. Also, note that brightness scaling by 10% causes slightly more number of bits to ﬂip as some of
the frames can turn out completely black after the intensity
adjustment.
3) Down-Conversion and Up-Conversion: We perform thefollowing attacks on HD content that occurs in practice. HD
content is in 16:9 aspect ratio and when it is to be displayedon standard deﬁnition TV screen with 4:3 aspect ratio one of
the following three is usually done:• The 16:9 content is horizontally cropped to ﬁt 4:3 aspectratio. We refer to this down conversion as hcrop in TableIV.
• A letterbox is added to 16:9 content to ﬁt 4:3 aspect ratio.
There is no horizontal cropping or vertical stretching. We
refer to this type of down conversion as Letterbox1 inTable IV.
• A letterbox of smaller size than in the case of Letterbox1

0.22

0.21

0.2

BER

0.25

0.19

0.18

0.17

0.16
0.5

Fig. 4.

1

1.5

2
2.5
3
MPEG Compression in Mbps

3.5

4MPEG-Compression Vs Bit Error Rate of the signature

Attack
Brightness Up 10%
Brightness Down 10%

B567689593478C
144233
144091D
0.10930.1144

Attacknoise1noise2noise3noise4

TABLE IIIROBUSTNESS OF P ROPOSED V IDEO S IGNATURE FOR B RIGHTNESSS CALING ;AttackLetterbox1
Letterbox2
hcrop

B
482668441208437200

C
84546
84396
84693

B
5568
6820
9610
12184

C
3996
3996
3996
3996

D
0.03870.04740.06680.0846

PSNR(dB)
44.49
38.5
34.62
32.4

TABLE VROBUSTNESS OF P ROPOSED V IDEO S IGNATURE AGAINST N OISE ;D
0.15850.14520.1433

AttackRotation by 1oRotation by 3o

TABLE IV
ROBUSTNESS OF P ROPOSED V IDEO S IGNATURE FOR D OWN C ONVERSION

B
11300
12146

C
1799
1799

D
0.17440.1875TABLE VI
ROBUSTNESS OF P ROPOSED V IDEO S IGNATURE FOR ROTATION ATTACK ;FROM HD TO SD R ESOLUTION ;is added to 16:9 content to ﬁt 4:3 aspect ratio and there
is also a small amount of horizontal cropping. This down
conversion is a tradeoff between hcrop (more horizontal
cropping) and Letterbox1 (no loss of content). We referto this type of down conversion as Letterbox2 in TableIV.
For the aforementioned down conversion methods, we automatically detect the letter box and extract the smallest image
region common to all of the down conversion methods and usethat for signature extraction. Table IV shows the robustnessof the signature against these down conversion attacks as the
maximum BER is only 15.85% which is less than the BER of41%.
We also converted SD content (4:3 aspect ratio) to HD content (16:9 aspect ratio) to study the robustness of the proposed
signature for up-conversion process. Under this modiﬁcation of
the original signal, 14.25% of the signature bits were in error
when compared with the signature of the original content. Thiserror rate is similar to that for down conversion attacks.
4) Noise: We performed two noise attacks on the originalcontent. In one attack, we employed a denoising algorithm on
the original content and studied its effect on signature bits.
We found that there were as many as 181466 bit errors inthe signatures for a total number of frames equal to 88546
which is 5.69% Bit Error Rate (BER). The denoising attack
has the smallest impact on the signature bits of all attacks wetried. In another attack, we varied amount of noise added tothe original content and studied how the BER increases as afunction of noise level. Table V shows the percentage of bitsthat ﬂip for varying amount of Gaussian noise that is added
to the content and BER is always less than 8.5%. Note that as
PSNR goes down from 44.4dB to 32.4dB the BER increases
from 3.87% to 8.46% as the amount of noise increases.
5) Rotation: We performed two rotation attacks on originalcontent to study how robust the proposed signature is togeometric attacks. Since the signature extraction is based ona coarse representation of an image computed from a grid,
geometric attacks which disturb the location of the features
relative to the ﬁxed grid would cause more bit errors than any

344

other attack. Table VI shows the percentage of bits that ﬂip
for rotation attack and the BER of 18.75% for 3o rotation isstill less than 41%. Note that 1o rotation has fewer bit ﬂips
than 3o rotation. The rotation attack causes most number ofbits to be ﬂipped than any other attack as expected.
IV. C ONCLUSION
We proposed a robust video signature extraction method
based on projections of difference images onto random basis
vectors. The extracted signatures were shown to be robust to
various signal processing operations on video content such
as MPEG compression, Spatial Scaling , Brightness Scaling
etc. It was also shown to be sensitive to underlying content
and hence can be used as a content identiﬁer. However, theproposed signature is not robust to geometric attacks as isshown by the results for the rotation attack. Furthermore, thesignature would not perform as well for frame-rate conversion
attacks. We found that the signature is robust to +/-5% change
in frame rate but for lower frame rates the difference image
between consecutive video frames would not be the same as
it was in the original video (especially so for high motion
sequences). Our future work will focus on improving resilienceto frame rate conversion, rotation and other geometric attacks.
ACKNOWLEDGMENT
The authors would like to thank Kent Terry of Dolby Labs
for all the help with discussions, simulations and content
acquisition.
R EFERENCES[1] J.Fridrich and M.Goljan, “Robust Hash Functions for Digital Watermarking”, Proc. of ITCC, 2000.
[2] H.S. Chang, S. Sull and S.U. Lee, “Efﬁcient video indexing scheme forcontent-based retrieval,” in IEEE Trans. Circuits Syst. Video Technol.,Dec 1999.
[3] S.S. Cheung and A. Zakhor, “Effcient Video Similarity Measurement with
Video Signature”, IEEE Transactions on CSVT,2003.
[4] Kozat, S.S. Venkatesan, R. Mihcak, M.K. , “Robust perceptual image
hashing via matrix invariants”, ICIP 2004.
[5] A.Swaminathan, Y.Mao and Min Wu, “Image Hashing Resilient To
Geometric and Filtering Operations”, MMSP 2004.