ON IMPROVING THE COLLISION PROPERTY OF ROBUST HASHING BASED ON
PROJECTIONSRegunathan Radhakrishnan, Wenyu Jiang and Claus Bauer
Dolby Laboratories Inc, 100 Potrero Ave San Francisco CA 94103
ABSTRACTIn this paper, we study the collision property of one of therobust hash functions proposed in [1]. This method was originally proposed for robust hash generation from blocks ofimage data and is based on projection of image block dataon pseudo-random matrices. We show that collision performance of this robust hash function is not optimal when used
to extract hash bits from a moment invariants feature matrix
for video ﬁngerprinting. We identify that the collision performance of this hash extraction method could be improved if
the pseudo-random matrices are selected carefully. We propose two methods that use an ofﬂine training set to improvethe collision property. Both of the methods attempt to selectthe matrices that minimize cross-correlation among the projected features. The ﬁrst method uses an iterative procedure
to select the matrices that satisfy a cross-correlation threshold. The second method used Singular Value Decomposition(SVD) of the feature covariance matrix and hence the crosscorrelation of the projected values is zero. We show the improved collision performance of both these methods on thesame dataset. Also, we interpret the projection matrices obtained through the SVD procedure and show that they captureappearance and motion information from the moment invariants feature matrix.
Index Terms— Robust Visual Hash, Scalable Fingerprinting
1. INTRODUCTION
A Media ﬁngerprint extraction method generally has the following two steps: (i)Robust Feature Extraction (ii)Robust
Hash Extraction. The ﬁrst step ensures that features thatare representative of underlying perceptual content and also
invariant under various processing operations, are extracted.
The second step ensures that such features are converted into
signature bits in a robust fashion i.e small changes in feature values do not result in drastic changes in extracted hashbits i.e for every (x ∼ y), H(x) ∼ H(y) with very highprobability. (Here ∼ denotes similarity). This requirement
disqualiﬁes the use of normal cryptographic hash functions toconvert the feature values into signature bits. The second step
also serves to provide a compact representation of the features so that these signature bits can be stored and searched
efﬁciently. Another property that is important for this robust

978-1-4244-4291-1/09/$25.00 ©2009 IEEE862

hash extraction step is the collision property. A robust hashfunction is said to have good collision property if for every(x = y), H(x) = H(y) with very high probability.
Consider a content identiﬁcation application with a large
database of media ﬁngerprints. Any media ﬁngerprint that is
extracted from query media is compared against this databaseof media ﬁngerprints during identiﬁcation. As the size of
database in terms of number of hours of media increases, it
is desirable that the uniqueness of ﬁngerprint codewords is
not reduced. The uniqueness property of the ﬁngerprint codewords would make the ﬁngerprint database scale to a larger
number of hours. Instead if certain ﬁngerprint codewords
are more likely to occur than others, then as the databasesize grows the uniqueness reduces. This results in morecomputations to perform the matching. To see this, let us
consider a hash-table based searching method for matching
the query ﬁngerprints against the ﬁngerprints in the database.
The database is indexed using the individual ﬁngerprint codewords. Each ﬁngerprint codeword in the hash table links to
the location in a ﬁngerprint ﬁle/media where that ﬁngerprint
codeword is present. The number of links per ﬁngerprintindex in the hash table will be referred 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 look-ups and pick the best match interms of smallest distance from the query ﬁngerprint. Thus,
the ﬁngerprints that have a small number of average collisions per ﬁngerprint codeword will result in shorter search
duration. Such ﬁngerprints are scalable for searching througha larger database of ﬁngerprints than ﬁngerprints for which
the average number of collisions is higher.
In this paper, we study the collision property of one of
the robust hash functions proposed in [1]. This method was
originally proposed for robust hash generation from blocksof image data and is based on projection of image data on
pseudo-random matrices. We had used this hash bit extraction procedure for extracting hash bits from robust featuresfor video ﬁngerprinting in [2]. We ﬁrst show that the collision performance is not optimal if the pseudo-random matrices are not selected carefully. We propose two methods thatuse an ofﬂine training set to improve the collision propertyof this robust hash extraction method. Both of the methods
attempt to select the matrices that de-correlate the projected

ICME 2009

features. The ﬁrst method uses an iterative procedure to selectthe matrices and the second method used Singular Value Decomposition (SVD) of the feature covariance. We show the
improved collision performance of both these methods on thesame dataset. Also, we interpret the projection matrices obtained through the SVD procedure and show that they captureappearance and motion information from the moment invariants feature matrix.
2. PROPOSED METHOD
2.1. Motivation
The ﬁrst step in media ﬁngerprint extraction is to extract robust features from audio and video that are invariant to various processing operations on 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 appearance and motion information fromthe input video. The input video is ﬁrst temporally downsampled to 12 fps. Then, every frame is spatially downsampled
to 120 ∗ 160 (Height × W idth) resolution after letterbox detection and removal. The N columns in the feature matrix Q
correspond to N video frames in a buffer including the current
frame. We use a buffer of 3s (N = 12 × 3) to capture motion
information. The G rows correspond to a set moment invariants extracted from each frame in the buffer. We extract 7
moment invariants from 5 concentric circular regions in eachframe (G = 5×7). Moment invariants are global measures ofan image surface that are invariant to translation, rotation andscaling and were originally proposed for text pattern recognition in [3]. Now, each column of the matrix Q attempts tocapture the appearance of the corresponding frame of video inthe buffer by measuring how the 7 moment invariants changeover the 5 regions. The second step is to extract hash bits fromthe feature matrix Q using a robust hash function.
In [1] proposed one such robust hash bit extraction procedure from blocks of image data. Given an image block B,
the following steps are performed to extract robust hash bits.
Using a secret key K the method generates N random matrices with entries uniformly distributed in the interval [0, 1].
Then, a low-pass ﬁlter is repeatedly applied to each randommatrix to obtain L random smooth patterns. All patterns arethen made DC-free by subtracting the mean from each pattern. Considering the block and the pattern as vectors, theimage block B is projected on each pattern Pi , i = 1, 2, ...Land the projected value is compared with a threshold T h toobtain L bits bi . If B.Pi < T h, then bi = 0 else bi = 1.
We applied this method of robust hash bit extraction forthe moment invariants based feature matrix Q described earlier and studied collision property. We extracted 36 bit ﬁngerprint codewords from a 25 min video clip at 12 fps. Let
us denote this collection of ﬁngerprint codewords using S.
We computed the average number of collisions per ﬁngerprint
codeword for this collection of codewords (S). The average
number of collisions was found to be 3.59. Then, we added863

about 3 hrs of ﬁngerprint codewords extracted from uniquecontent that is not related to this 25 min clip. Again, we compute the average number of collisions per codeword in theset S. Now, the average number of collisions for this dataset
increased to 7.37. Ideally, the average number of collisions
should remain unchanged after the inclusion of ﬁngerprint
codewords from unrelated content. However, it did not remain the same. This means that the collision property (i.e.
for every (x = y), H(x) = H(y) with very high probability)
is not optimal for this hash function. In the following two subsections, we describe the two proposed methods to improves
the collision property of robust hash in [1] by selecting the
projection matrices Pi (i = 1, 2...L) carefully.
2.2. Iterative Procedure for Selecting Random Matrices:iterThis procedure is motivated by the fact that the pseudorandom matrices P1 , P2 , ..PL should capture different aspects of the feature matrix Q through their corresponding
projections H1 , H2 , ...HL . Instead if the information theycapture about the feature matrix Q is correlated, then certain
hash bits would tend to vary together. This means that certain
codewords are more likely than others. The following are thesteps to choose the L pseudo-random matrices:
Step 1: Obtain a training dataset of media content and extract robust features Q1 , Q2 , ...QM . Here M is the number oftraining instances for selecting the pseudo-random matrices.
Step 2: Initialize iteration index j = 1 and a corresponding set of pseudo-random matrices for this iteration
P1,j , P2,j , ...PL,jStep 3: Project each Qi onto P1,j , P2,j , ...PL,j to obtainiii, H2,j, ...HL,j, i = 1, 2...M . We
the projected values H1,jwould like each of pseudo-random matrices to capture different aspects of the feature matrix. Therefore, we should
select a set of pseudo-random matrices whose projectionsiii, H2,j, ...HL,jhave low correlation among themselves.
H1,j
In the following step, we compute the cross-correlation matrix C of the projected values using the training set containing
M instances of the feature matrix Q.
Step 4: The entries of the cross-correlation matrix C are
computed as given below
M1iii=1 (Hk,j − E(Hk,j ))(Hl,j − E(Hl,j ))MjC (k, l) =√√σk,j σl,j1  iHM i=1 k,jM

E(Hk,j ) =1  i(H − E(Hk,j ))2
M i=1 k,jM

σk,j =

Here C j (k, l) represents the cross correlation coefﬁcient
between the projected values Hk,j and Hl,j for j th set ofpseudo-random matrices and k, l, n = 1, 2...L. E(Hk,j ))and σk,j represent the mean and variance of Hk,j estimatedUnlike the iterative procedure in the previous section, we
obtain the φ1 , φ2 , ...φL by directly computing the eigenvectors of the feature covariance matrix, C f eat . φ1 , φ2 , ...φL are
pairwise orthogonal i.e (< φi .φj >= 0 i = j) whereas Pi .Pj
need not to identically equal to 0 for i = j. Also, the elementsof Pi are uniformly distributed between random numbers between -0.5 and 0.5 whereas the elements of φi are obtainedin a data-driven fashion and are not drawn from a speciﬁc
distribution. In the case of the projections obtained from projecting Q onto φ1 , φ2 , ...φL (H1svd , H2svd , ...HLsvd ), there isan inherent order of signiﬁcant projections that corresponds
to the signiﬁcance of the basis functions (φ1 more signiﬁcant than φ2 , φ2 more signiﬁcant than phi3 ...so on). Thismeans that one could derive varying number of ﬁngerprint
bits from each of the projections H1svd , H2svd , ...HLsvd . Obviously, one would like to derive more number of bits from
H1svd than from HLsvd . In the case of projections obtained
2.3. SVD based Selection of Projection Matrices:svd
from projecting Q onto P1 , P2 , ..PL , there is no speciﬁc order
In the previous subsection, we described an iterative proceof signiﬁcance and therefore we usually derive equal number
dure to design the L pseudo-random matrices P1 , P2 , ..PL .
These pseudo-random matrices ensure that the cross-correlation of bits from each of the projected values H1 , H2 , ...HL .
coefﬁcient between any two projected values (C(k, l)) is
3. EXPERIMENTAL RESULTS
smaller than a chosen threshold (say 0.2). Here C(k, l) represents the cross-correlation between Hk (projection of Q onto
In this section, we present experimental results on collision
Pk ) and Hl (projection of Q onto Pl ). In this section, we
performance of the iterative procedure as well as the SVD
describe a method that designs L matrices φ1 , φ2 , ...φL suchbased procedure for selecting the projection matrices. The
that the cross-correlation between any two projected values
feature matrix Q for all experiments in this paper is a matrix(C svd (k, l)) is equal to zero. Here C svd (k, l) represents theof dimensions 35 × 36 (G × N ) where 36 corresponds to across-correlation between Hksvd (projection of Q onto φk ) and3s
buffer of frames at 12fps and 35 corresponds to the 7 moHlsvd (projection of Q onto φl ). The matrices φ1 , φ2 , ...φLment invariants computed from 5 concentric circular regions
are the eigenvectors of the covariance matrix of the featureof each frame in the buffer. First, we extract 22 bit ﬁngerprint
values from the training set.
codewords (L = 22) from a 25 min video clip using three sets
Step 1: Obtain a training dataset of media content andof projection matrices: (i) pseudo-random matrices (no-opt)
extract robust features Q1 , Q2 , ...QM . Here M is the number(ii) pseudo-random matrices selected using the iterative proof training instances. Let the dimension of each feature matrix
cedure (iter)(iii) projection matrices selected using the SVD
Qi be R = G × N .
procedure (svd). For selecting the projection matrices in case
Step 2: Then, we compute the covariance matrix C f eatof (ii) and (iii), we used the same ofﬂine training set of 3 hrs(dimension R*R) of the features from the training
setof content. In the case of (i), the pseudo-random matrices areM1i
Q1 , Q2 , ...QM as given by C f eat (k, l) = M
not selected carefully using either procedure proposed in thisi=1 (Qk −M
1i
E(Qk ))(Qil − E(Ql )). Here E(Qk ) = M
paper and this method acts as a baseline method. In the casei=1 Qk andk, l = 1, 2...R.
of (ii), the pseudo-random matrices were selected ensuringthat the cross-correlation between the projected values is alStep 3: Once we compute the covariance matrix of theways less than 0.2. Let us denote the collection of ﬁngerprintfeatures from the training set, we compute the eigenvectors
codewords extracted from the 25 min clip using projectionof the matrix C f eat that satisfy the relation, V −1 C f eat V =matrices from (i) as S no−opt . And let those extracted using
D, using PCA (Principal Components Analysis). Here theprojection matrices from (ii) be denoted as S iter and thosecolumns of V (dimension R*R) are the eigenvectors of the
f eat
extracted using projection matrices from (iii) be denoted as
and are represented as φ1 , φ2 , ...φR .
covariance matrix C
S svd . Then, we compute the average number of collisions
D is a diagonal matrix with eigenvalues (E1 , E2 ...ER ) as its
for the ﬁngerprint codewords in each of the three sets namely
main diagonal elements and zero elsewhere.
S no−opt ,S iter and S svd .
Thus, we can now transform any input feature vector
In order to study the collision performance of these
Q to a L dimensional space by projecting it onto the ﬁrst
three sets, ﬁrst, we add ﬁngerprint codewords extracted fromL eigenvectors φ1 , φ2 , ...φL to obtain H1svd , H2svd , HLsvd
respectively. Here Hksvd is the projection of Q onto φk .
unique content (content that is unrelated to the 25 min clip) to
the database. Then, we compute the average number of colliNow the cross-correlation between any two projected values
sions as we increase the number of ﬁngerprint codewords of(C svd (k, l)) is guaranteed to be equal to zero.
from this training set. Note that the cross-correlation matrix
is a matrix of dimension L × L whose main diagonal elements are equal to the value 1.0. Once we have computed
the cross-correlation matrix in this manner, we select pseudorandom matrices for which the cross-correlation of projections with other pseudo-random matrices is smaller than achosen threshold.
Step 5: After we have selected random matrices that meet
our criteria, we replace the matrices that did not meet our criteria with new ones and proceed with the next iteration.
Step 6: We continue the iterations until we ﬁnd all L
pseudo-random matrices that capture different aspects of thefeature matrix. The cross-correlation matrix after the last iteration would have all terms less than the chosen threshold (say0.2) except for the main diagonal elements.

864

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. Figure 1(a) illustrates
the collision performance for the three sets of projection
matrices. The average of number of collisions for S no−opt
increases from 3.59 to 7.37 as we add ﬁngerprint codewords
from 3hrs of unrelated content. On the otherhand, the average
number of collisions for S iter increases from 2.76 to 3.03 forthe same increase in number of ﬁngerprint codewords fromunrelated content. The average number of collisions for S svd
increases from 6.23 to 6.40. The projection matrices obtained
through the SVD procedure have the smallest slope (smallest
increase in average number of collisions for inclusion of anhour of unrelated content) among the three sets of projection
matrices. This is as expected because the SVD procedureensures that the cross-correlation between the projected values is zero. The iterative procedure only ensures that thecross-correlation is always less than 0.2. Figure 1(b) shows
the increase in the average number of collisions for every
additional hour of unrelated content included. The slopes for
S no−opt ,S iter and S svd are 1.5,0.1 and 0.05 respectively.
Inc in Avg num collisions Vs num hrs
1.8
Avg num collision Vs num hrs
7.5

1.6

7

svd

1.4

6.5

1.2

no opt

6
1
5.5
0.8
5
no opt

0.6

4.5

0.4

4

0.2

3
2.5

0

0

0.5

1

1.5

2

(a)

2.5

iter
svd

iter

3.5

3

3.5

1

1.5

2

2.5

3

3.5

4

4

(b)

Fig. 1. (a) Avg. num of collisions vs num hrs of unrelated
content (b)increase in Avg. num of collisions vs num hrs of
unrelated content;
Figure 2 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).
Recall that the number of rows correspond to 5×7 moment invariants extracted from each frame in the buffer and the number of columns correspond to the number of frames in the
3s buffer (3 × 12). Projection matrices 1 & 3 (on the top &bottom left of Figure 2(a)) can be interpreted as those capturing appearance information alone from the feature matrix
Q. This is so because the values along the columns of the
projection matrices 1 & 3 are similar for every row. Also,
note that the patterns along rows are repeated 5 times. Thisis so because the 7 moment invariants computed from the 5concentric circular regions are correlated and hence the projection matrix values are also correlated. The other projection
matrices shown in the Figure 2 capture both appearance andmotion information as can be seen from the changing patterns

865

across the columns (time) for these projection matrices.
basis 1

basis 2

basis 5basis 6

10

10

10

10

20

20

20

20

30

30

30

10

20

30

10

basis 3

20

30

30
10

basis 4

20

30

10

basis 7

10

10

10

10

20

20

20

20

30

30

30

10

20

30

10

20

30

20

30

basis 8

30
10

20

(a)

30

10

20

30

(b)

Fig. 2. (a) Projection matrices 1-4 from SVD procedure (b)Projection matrices 5-8 from SVD procedure;
4. CONCLUSION
In this paper, we have shown that the collision performanceof the robust hash function proposed in [1] is not optimal for
extracting hash bits from moment invariants based video ﬁngerprint extraction. The robust hash function proposed in [1]is based on projection of the features onto a set of pseudorandom matrices. We propose two methods to improve thecollision performance of this robust hash function by carefully selecting a set of projection matrices that minimize thecross-correlation between projected values. Both of the proposed methods design the projection matrices using a training dataset ofﬂine. One method is based on a iterative procedure that selects pseudo-random matrices that satisfy a crosscorrelation threshold. Another method is based on the SVD ofthe feature covariance matrix and hence the cross-correlation
between the projected values is set to zero. We showed thatboth of the proposed methods improved the collision performance when compared to an approach that does not carefully
select the projection matrices. We also interpret the projection matrices obtained through the SVD procedure and showthat they capture appearance and motion information from themoment invariants feature matrix. Also, the SVD based procedure outperformed the iterative procedure both in terms of
average number of collisions and training time to select the
projection matrices.
5. REFERENCES[1] J.Fridrich and M.Goljan, “Robust hash functions for digital watermarking,” ITCC, 2000.
[2] R.Radhakrishnan, W.Jiang and C.Bauer, “A review ofvideo ﬁngerprints invariant to geometric attacks,” to appear in Proc. of SPIE, 2009.
[3] Hu,M.K, “Visual pattern recognition by moment invariants,” IRE Trans. Info. Theory, vol. IT-8, pp. 179–187,
1962.