FAST AND ROBUST CONTENT-BASED COPY DETECTION BASED ON QUADRANT OF
LUMINANCE CENTROID AND ADAPTIVE FEATURE COMPARISON
Yusuke Uchida, Masayuki Hashimoto, Ryoichi Kawada
KDDI R&D Laboratories Inc.
2-1-15 Ohara, Fujimino-shi, Saitama, Japan
ABSTRACTThis paper proposes a fast and robust content-based copy detection scheme. Our proposal consists of a new compact feature, efficient keyframe selection and adaptive mask-based
feature comparison. Firstly, a block-level luminance centroid
is binarized into a 32-bit quadrant feature for fast and robustfeature comparison. Subsequently, a new keyframe selection method is adopted to enhance pairwise independence between unrelated video segments in addition to choosing stable
keyframes. Finally, a block-level mask-based feature comparison method is introduced to compare only stable features.
Experimental results show our scheme improves recall by 0.1
at the same precision 0.9 and the processing speed in featurecomparison of the proposed scheme is about twice as fast asthat of conventional schemes.
Index Terms— video fingerprinting, content-based copy
detection, near-duplicate detection, luminance centroid
1. INTRODUCTION
With the advancement of both computer and Internet technology, digital multimedia content is being used more widely inmany applications. Video sharing services, one such application, have become very popular and have attracted a great dealof attention. One big problem with these video sharing services, however, is copyright infringement. As many people
upload infringing video clips to video sharing sites without
proper authorization, an automated means of detecting suchclips is needed. In recent years, Content-Based Copy Detection (CBCD) technology, more generally referred to as digital
fingerprinting, has attracted considerable research attention
for this purpose. In an automated inspection system based on
CBCD, content holders register copyrighted content with theoperators of video sharing sites in advance. The operators extract features from the copyrighted content and store them in a
database. When a user uploads a video clip, features are also
extracted from the uploaded video clip in the same way andthe database is searched for a match. If there is matching content in the database, the uploaded content is considered to bea copy of copyrighted content and filtered out or some otheraction is taken according to the content holder’s intentions.
Considering a CBCD system in practical terms, robustness

and computational efficiency are vital because many video
clips are uploaded to video sharing sites every day and these
uploaded video clips are subject to various kinds of transformations such as compression, contrast changes, etc. In thispaper, we focus on improving detection accuracy and speedin CBCD for efficient copyright protection.
2. RELATED WORKS
To date, many algorithms have been developed in the CBCD
area. CBCD schemes can be roughly classified into two categories: one based on global features [1–4] and the other on
local features [5]. Although one state-of-the-art scheme basedon local features has achieved high accuracy and an efficient
database search [5] in terms of content-based image retrieval,local feature detection and description [6] processes remain
highly time-consuming (in the order of a few seconds perframe on an ordinary PC). In this paper, therefore, we focus
on schemes based on global features for practical use. An
ordinal measure (OM) [1, 2], one of the major global descriptors, has proven robust against changes in resolution or illumination. Recently, it has been revealed that gradient based
features [3, 4] achieve good robustness and pairwise independence. Among them, the block-wise orientation of luminancecentroid (OLC) is shown to have optimum performance [4].
3. PROPOSED APPROACH
The most significant problem of the aforementioned conventional schemes based on global features is the fact that thedetection accuracy deteriorates when a copied video clip has
been distorted, particularly by geometric transformations. In
this paper, we overcome this problem via the following three
approaches:◦ Binarizing frame features into 32-bit signatures and comparing them in terms of Hamming distance, which prevents the disparity between a copied video clip and its
original video segment from becoming excessive due todistortion.
◦ Selecting stable and distinctive keyframes in order to accomplish both robustness and pairwise independence.
◦ Filtering out the features that are sensitive to distortion,
which improves accuracy, especially in recall.

…

1,0 … 1,1Bi

( x ic , y ic )Frame samplingQuery
q1 q2 q3 q4 q5 q6

Feature extraction( x im , y im )

… 0,0

… B16

Key-frame selection

Distance…

B1

q1 q2 q3 q4 q5 q6…

q1 q2 q3 q4 q5 q6

Keyframes…

Feature vectors…

Query video

Partitioning each frame
Calculate
into 4x4 blocks
Luminance centroid

Distance

Binarization

Fig. 2: Feature extraction in the proposed scheme.

Feature comparison… rt rt+1 rt+2 rt+3 rt+4 rt+5 rt+6 rt+7 …
Reference segment
at offset t
Sequential search

offset t

Detectthoffset t

Non-maxima suppression
and thresholding

Fig. 1: Framework of the proposed scheme.

As shown in Fig. 1, the proposed scheme is briefly summarized as follows. 1) The query video is resampled at a fixed
frame rate to deal with frame rate changes. 2) Robust binary features based on block-wise luminance centroid are extracted from every frame of the resampled query video. 3)
Stable and distinctive keyframes are selected. 4) Referenceindices are sequentially searched using a block-level mask,
which enables only distinctive blocks to be compared. 5)
Non-maxima suppression and thresholding are performed todetermine whether the query content is infringing or not. If
so, the offset of the copied segment in reference videos is estimated. In the remainder of this section, feature extraction,
keyframe selection and sequential search procedures are alldetailed.
3.1. Quadrant of the luminance centroid feature
We propose a binary feature based on the quadrant representation of the luminance centroid (QLC) for fast and robust
retrieval. Fig. 2 shows the procedure of the QLC feature.
First, each frame is divided into 4x4 blocks Bi (1 ≤ i ≤ 16),for each of which the coordinate of the luminance centroid(xci , yic ) is then calculated:∑∑(x,y)∈Bi x · I(x, y)(x,y)∈Bi y · I(x, y)ccxi = ∑, yi = ∑,(x,y)∈Bi I(x, y)(x,y)∈Bi I(x, y)(1)
where I(x, y) means the luminance of an image at coordinate(x, y). Subsequently, a 2-bit signature is extracted by comparing the coordinates of the luminance centroid (xci , yic ) andmthe center of the block (xmi , yi ). This extreme quantization
prevents features from being severely changed by distortion.
Integrating these signatures from all blocks, the QLC feature
f is created:f = (x1 , y1 , · · · , x16 , y16 ),(2){{
1 if xci ≥ xm
1 if yic ≥ yimixi =, yi =.
(3)0 else0 elseThis quadrant representation and the mask-based featurecomparison explained in section 3.3 resolve the drawbacksof the OLC feature illustrated in Fig. 3. One drawback is thefact that features θ and π − θ are confusing (on the left in
Fig. 3) because OLC represents the orientation of luminancecentroid by arcsin. This restriction is to enable OLC features
to be compared in Euclid space, while the QLC feature is=≠

Confusion case

Unstable caseFig. 3: Simple illustration of OLC drawbacks.

compared in the Hamming space and can distinguish the centroids illustrated on the left in Fig. 3. The other drawback is
the fact that the OLC feature would change significantly by
distortion, resulting in a significant performance degradation
when the luminance centroid is located near the center ofthe block, e.g., θ changes from π/2 to −π/2 (on the right in
Fig. 3). On the other hand, the QLC feature do not change
significantly due to binary representation. This QLC feature is a very compact signature and requires only 32 bits
per frame, while OM [1] needs 45 bits and OLC 128 bits.
If properly encoded OM is applied, the bit amount can be
reduced to ⌈log2 (9!)⌉ = 19 bits. However, decoding computation is additionally required and the resultant search speed
is degraded.
3.2. Stable and distinctive keyframe selection
Let Q = (q1 , · · · , qN ) denote a feature set extracted froma query video clip where N is the number of frames in thequery video clip after resampling. Because Q includes redundant and noisy frames, M keyframes are selected andonly keyframes are compared in a sequential search for astable and distinctive feature comparison. A keyframe set
K = (k1 , · · · , kM ) is selected by maximizing the following
expression:
maximize(A(K) − αB(K)),
(4)
∑M −1
(5)
A(K) = j=1 ham(qkj , qk(j+1) ),∑M
B(K) = j=1 max(ham(q(kj )−1 , qkj ), ham(qkj , q(kj )+1 )),(6)
where ham(f1 , f2 ) is the Hamming distance between features
f1 and f2 , which is defined as:ham(f1 , f2 ) = bitcount(f1 ⊕ f2 ).
(7)
bitcount(·) counts the number of ’1’ bit, which is efficiently
calculated using a lookup table for every 16 bits. This optimizing problem can be quickly solved by dynamic programming. The term B(K) represents the distance between
keyframes and their neighboring frames. By minimizing this,the keyframes become stable against the time lag between the
copied video clip and the original video. This has an effectsimilar to the keyframe selection method described in [7],where frames are divided into sub-groups and keyframes are
selected for each sub-group for which the distances to any

of the other frames in the sub-group are minimized. Furthermore, in the proposed method, the term A(K) imposesthat consecutive keyframes should be different from eachother, resulting in selecting diverse keyframes and boosting
pairwise independence in the feature comparison.
3.3. Mask-based feature comparison
In this section, we introduce a mask-based feature comparison
method, whereby a comparison of only stable features (bits)
is attempted instead of using the ordinary Hamming distance.
The mask m is created from the coordinates of the luminancecentroids:(8)m = (a∗1 , b∗1 , · · · , a∗16 , b∗16 ),{cm
0 if |xi − xi | ≤ βσx
a∗i =
,
(9)
1 else{0 if |yic − yim | ≤ βσy
∗
bi =
,
(10)
1 elsewhere β is the adjustable parameter determining the mask
strength and σx (σy ) is the standard deviation of xc − xm
(y c − y m ), which is obtained from video clips that differ fromreference videos. Using mask m, the modified Hamming distance between feature f1 and f2 is defined asham∗ (f1 , f2 , m) = bitcount((f1 ⊕ f )2 ∧ m),(11)
where ∧ is an AND operator. In the proposed scheme,
the mask is created from the query feature set Q, whichmeans no additional information is stored in the databaseconcerning the mask-based feature comparison. Let Rt =(rt+1 , · · · , rt+N ) denote a reference feature set at offset t
and M = (m1 , · · · , mN ) denote a mask set created from thequery feature set Q. Subsequently, the distance between Q
and Rt is defined as the sum of the modified Hamming distances over the keyframes with normalization by the numberof bits ’1’ in M:∑∗j∈K ham (qj , rj+t , mj )∑dist(Q, Rt , M, K) =. (12)
j∈K bitcount(mj )Here we simply describe dist(Q, Rt , M, K) as d(t). Aftercalculating d(t) over the reference index, non-maxima suppression with window size w and thresholding with threshold
th is performed for the final results. All offsets t̂ that satisfy
the following expression are regarded as the beginning pointsof the copied segment:d(t̂) ≤ min(d(s), th) (t̂ − w ≤ s ≤ t̂ + w).
(13)
4. EXPERIMENTAL RESULTS
We conducted experiments to evaluate the proposed schemein terms of robustness and computational cost. The experimental environment is described below:◦ Testbed: the following experiments were tested on a machine with a Core 2 Quad 3GHz CPU and 8GB main
memory using Windows XP. All experiments were performed with a single thread.

◦ Reference: 200 hours of video (720x480, 29.97fps) fromvarious movie genres were used as reference videos.
Features were pre-extracted and stored in the main
memory for sequential search.
◦ Query: we created 100 queries of 60 seconds in duration,
which were randomly extracted from reference videos
and edited by particular transformations.
◦ Evaluation criteria: each scheme was evaluated in termsof accuracy (Precision-Recall curve with different
thresholds) and computational cost (average processing
time per query). In this paper, the allowable error of
offset t̂ is set to 2 seconds.
For query generation, the following four transformations wereused:
◦ Cropping: crop each side by 20px.
◦ Contrast: enhance contrast with parameter 1.2.
◦ Rotation: rotate +3 degrees.
◦ Compression: resize to CIF and encode to DivX@256kbps.
4.1. Evaluation of the proposed scheme
In this experiment, each part of the proposed scheme was
evaluated. For this purpose, the following five schemes werecompared:◦ OLC: OLC feature with 4x4 blocks proposed in [4].
◦ QLC: QLC feature proposed in this paper.
◦ QLC+K: QLC combined with the keyframe selection described in section 3.2.
◦ QLC+K2: QLC combined with the keyframe selection described in [7].
◦ QLC+K+M: QLC+K combined with the mask-based feature comparison described in section 3.3.
The parameters used in this experiment were set as: N = 120,
M = 30, α = 2.0, β = 0.2 and w = 10 (α and β were determined by preliminary experiments). Fig. 4 shows the PR
curve of each scheme against each query. The common characteristics independent of the query type are described in
the following. Comparing OLC and QLC, it is confirmedthat the QLC feature improves performance especially interms of recall. This improvement is mainly owing to thebinary feature representation detailed in section 3.1, which
prevents the QLC feature from significant change by distortion. While both keyframe selection methods (QLC+K and
QLC+K2) improve performance compared with QLC, theproposed keyframe selection method is shown to be more
efficient. It mainly contributes to precision because by selecting distinctive frames as keyframes, the distance between
two different video clips increases. The mask-based featurecomparison also improves accuracy, especially in recall. Thisis because by avoiding comparison of unstable bits, the distance between the copied video clip and its original video
content diminishes. It is remarkable that the full proposed

1

0.9

0.9

0.9

0.9

0.8

QLC+K+M
QLC+K2
QLC+K
QLC
OLC

0.7
0.6

0.8

QLC+K+M
QLC+K2
QLC+K
QLC
OLC

0.7
0.6

0.5
0.6

0.7

0.8

0.9

1

0.6

0.9

0.9

0.8

QLC+K+M
QLC+K2
QLC+K
QLC
OLC

0.7
0.6

0.7

0.8

0.9

1

RecallPrecision

Precision

Recall
1

0.6

0.7

0.8

Recall

0.9

1

PROP
OLC+K2
OLC

0.7
0.6
0.5

0.5

0.6

0.7

0.8

0.9

1

0.5

0.6

0.7

0.8

0.9

1

RecallRecall0.8

QLC+K+M
QLC+K2
QLC+K
QLC
OLC

0.7

0.5

0.5

0.7

0.8

Fig. 5: Average PR curve of each scheme against four types of transformations.

0.6

0.5

PROP
OM+K2
OM

0.5
0.5

1

0.8

0.6

0.5

0.5

Precision

1

Precision

1

Precision

Precision

1

0.5

0.6

0.7

0.8

0.9

1

RecallFig. 4: PR curve of each scheme against each query type: Cropping(top-left), Contrast (top-right), Rotation (bottom-left) and Compression (bottom-right).
Table 1: Comparison of the computational cost of each scheme[sec/query].
Feat.
Key.
Mask Feat. comp. Total
OLC
0.146
1.163
1.309
QLC
0.169
0.284
0.453
QLC+K
0.169 0.002
0.284
0.455
QLC+K20.169 0.001
0.284
0.454
QLC+K+M
0.169 0.002 0.001
0.353
0.525

Table 2: Comparison of computational cost among PROP, OM,
OM+K2, OLC and OLC+K2 [sec/query].
Feat.
Key.
Mask Feat. comp. Total
PROP
0.169 0.002 0.001
0.353
0.525
OM
0.025
0.638
0.663
OM+K2
0.025 0.001
0.638
0.664
OLC
0.146
1.163
1.309
OLC+K20.146 0.001
1.163
1.310

Computational costs are compared in Table 2. As shownin the table, though the proposed scheme requires additional
cost in extracting features, it achieves the fastest processing
speed. The proposed scheme is especially fast in feature comparison (about twice as fast as OM), which becomes criticalwhen searching a huge reference database.
5. CONCLUSION

scheme (QLC+K+M) achieves good robustness even against
geometrical transformations (e.g., 0.96 in F-measure against
the rotation query).
Table 1 shows the computational time of each scheme.
The QLC feature also accelerates search speed, even if themask-based comparison is adopted because distance calculation is implemented by bitwise operation and LUT. It is also
shown that the processing overhead of the keyframe selection
and mask generation in the proposed scheme is negligible.

In this paper, we proposed a fast and robust content-based
copy detection scheme based on the quadrant representationof luminance centroid and adaptive mask-based feature comparison for the automatic detection of infringing video clips.
Experimental results show our scheme improves the recall by
0.1 at the same precision of 0.9 and the processing speed infeature comparison of the proposed scheme is about twice as
fast as that of conventional schemes.

4.2. Comparison with conventional schemes[1] X. Hua, X. Chen, and H. Zhang, “Robust video signature basedon ordinal measure,” in Proc. of ICIP, 2004, pp. 685–688.
[2] M. Usman and C. Kim, “Real time video copy detection underthe environments of video degradation and editing,” in Proc. of
ICACT, 2008, pp. 1583–1588.
[3] S. Lee and C. D. Yoo, “Robust video fingerprinting for contentbased video identification,” IEEE Trans. on CSVT, vol. 18, no.
7, pp. 983–988, 2008.
[4] S. Lee and Y. H. Suh, “Video fingerprinting based on orientationof luminance centroid,” in Proc. of ICME, 2009, pp. 1386–1389.
[5] H. Jegou, M. Douze, and C. Schmid, “Hamming embedding
and weak geometric consistency for large scale image search,”
in Proc. of ECCV, 2008, pp. 304–317.
[6] D. G. Lowe, “Distinctive image features from scale-invariant
keypoints,” IJCV, vol. 60, no. 2, pp. 91–110, 2004.
[7] Z. Xu, H. Ling, F. Zou, Z. Lu, P. Li, and T. Wang, “Fast and robust video copy detection scheme using full DCT coefficients,”
in Proc. of ICME, 2009, pp. 434–437.

In this section, the proposed scheme is compared with theconventional schemes described below:◦ PROP: full proposed scheme.
◦ OM: ordinal intensity feature [1] with 3x3 block division.
◦ OM+K2: OM combined with keyframe selection describedin [7] for fair comparison.
◦ OLC: orientation of luminance centroid [1] with 4x4 block
division.
◦ OLC+K2: OLC combined with keyframe selection.
Fig. 5 shows the average PR curves of each scheme for fourtransformations. Although keyframe selection improves theaccuracy of both the OM and OLC schemes, the proposed
scheme still outperforms conventional schemes. Comparing
PROP and OLC+K2 at the same precision of 0.9, the proposed scheme achieved higher performance than OLC+K2 byabout 0.1 in recall.

6. REFERENCES