FAST AND ACCURATE CONTENT-BASED VIDEO COPY DETECTIONUSING BAG-OF-GLOBAL VISUAL FEATURES
Yusuke Uchida, Koichi Takagi, Shigeyuki Sakazawa
KDDI R&D Laboratories Inc.
2-1-15 Ohara, Fujimino-shi, Saitama, Japan
ABSTRACTIn this paper, we propose a fast, accurate content-based video
copy detection scheme based on bag-of-global visual features, which is characterized by (1) utilizing an efficient
DCT-sign-based feature for fast detection; (2) performing
multiple assignment in the temporal domain, in addition
to the feature and spatial domain to ensure repeatability insegment-level matching; and (3) adopting an inverse document frequency weighting and temporal burstiness-aware
scoring to emphasize distinctive visual words. Despite detection 95 times faster than real-time, the proposed systemachieves a false negative rate of 0.2% against queries that arealtered by non-geometric transformations without any false
positives.
Index Terms— Near-duplicate detection, content-based
copy detection, inverted index, visual words
1. INTRODUCTION
As digital multimedia content, computer, and Internet technologies have become ubiquitous, digital videos have beenused extensively in many applications. Copyright infringement poses a significant issue for one of the applications —online video-sharing services. Because many people upload
video clips to these sites without proper copyright releases,
an automated system that detects copies of copyrighted video
is needed. In recent years, content-based video copy detection (CBCD) technology has attracted considerable researchattention for this purpose. For an automated CBCD system tobe usable, it must have the following properties:◦ Computationally efficient: The system must be sufficiently
efficient because many video clips are uploaded tovideo sharing sites every day.
◦ Robustness (low false negative rate): The video may havebeen subject to editing or degradation, including the addition of captions or patterns, a change of resolution,
compression, and so on. The system should detect eventhese altered videos robustly.
◦ Low false alarms: A system with too many false detections
is annoying and requires ongoing operator intervention
to filter out the false alarms.

To detect video copies, there are mainly two cues: visual
and/or audio information. Although both cues are equally
useful, we focus on visual features in this paper, especially on
global visual features. Instead of trying to handle too severe
alterations such as camcording, we propose an efficient andeffective CBCD system to efficiently filter out the majority of
infringing video clips that have not been altered by geometrictransformations. The proposed system satisfies the requirements described above by (1) utilizing an efficient DCT-signbased feature for fast detection; (2) performing multiple assignment in the temporal domain, in addition to the featureand spatial domain to ensure repeatability in segment-level
matching; and (3) adopting an inverse document frequency
weighting and temporal burstiness-aware scoring to emphasize distinctive visual words (VWs), resulting in suppressing
false positives.
2. RELATED WORK
CBCD schemes based on visual cues are roughly classified
into two categories: one based on global features [1–4] andthe other on local features [5]. Although local feature-based
schemes are robust against even geometric transformations
such as camcording, local feature detection, description, andmatching processes remain highly time consuming [3]. In thispaper, therefore, we focus on global feature-based schemes
for practical use. An ordinal measure (OM) [1] is one of
the major global descriptors, which has proven robust againstchanges in resolution or illumination. In [2], OM is extended
to the spatiotemporal domain to capture temporal information. In [3, 4], OM features from a video clip are summarized
into compact signatures for efficient retrieval. However, it
is difficult for the clip-based methods [3, 4] to detect partial
copies that are embedded in unrelated video clips. In [6], thebag-of-visual words (BoVW) framework [7], which is usually used for local features, is adapted to global features, inwhich multiple global features are extracted from predefined
windows in a keyframe. Multiple assignment in the featuredomain [8] is also performed to ensure repeatability of feature matching. However, multiple assignment in the featureand spatial domain is not the optimal choice in terms of the
tradeoff between repeatability and filtering rate.

3. PROPOSED CBCD SYSTEM

DCT

Zigzag scanAC1, ... , ACvsign(ACi)

Top-v AC coefficients

For simplicity, we explain the indexing and search step only
when there is a single reference video clip. This limitation
is easily overcome by considering reference video identifiers
1 Divied into 2x1, 2x2, 4x2, and 4x4 blocks for ms = 1, 2, 3, and 4.

y
t ...

...

x

qs , w = {1, vw}

Searching stept-th segment

t,w

vw

t,w

...

...

Match

N

...

3.2. Indexing and searching inverted index

Inverted index
1
2

...

Multiple assignment is powerful tool to improve repeatabilityof VW-based feature matching by assigning multiple VWs
to a single feature or keyframe [6, 8]. In this paper, multiple assignment is defined to assign multiple VWs to a single,
short segment, not to a keyframe. In this section, multiple
assignments in the feature, spatial, and temporal domain are
introduced. First, both reference and query video clips are
divided into short segments with fixed durations in the temporal domain (0.3 sec in this paper). From each of the segments, fixed number 2mt of frames are subsampled at a uniform interval (multiple assignment in the temporal domain).
Subsequently, these subsampled frames are divided into 2ms
blocks1 (multiple assignment in the spatial domain). Finally,
feature vectors are extracted from these blocks. In this paper, we adopt the DCT-sign-based feature [9] as depicted in
Figure 1; each block is resized into 8x8 pixels, and 2D-DCT
is performed. Top-v AC coefficients in the zigzag scan order
are used as a feature vector. Subsequently, they are quantized into a v-bit binary string by taking the sign of the AC
coefficients. The resulting binary strings of length v define
VWs with a size of N = 2v . Multiple assignment in the feature domain can be performed by toggling the most unreliable
mf -bits [10]. With the multiple assignment in the feature domain, each feature is assigned to 2mf VWs. The reliability ofeach bit is defined by the absolute value of the corresponding
AC coefficient. Finally, t-th reference segment is represented
by Rt = (rt,1 , · · · , rt,w , · · · , rt,W ), where W (= 2ms ) denotes the number of blocks and rt,w denotes a set of VWs
associated with w-th block. We also denote s-th query segment by Qs = (qs,1 , · · · , qs,w , · · · , qs,W ). The parameters
introduced above (mf , ms, mt) have a considerable impact
on the performance of segment-level matching as shown in
Section 4.1.

Fig. 1: Feature extraction procedure.
s-th segment...

3.1. Feature extraction and multiple assignment

v-bit strings
define2v visual words

8x8 thumbnail...

In this section, we describe the proposed content-based video
copy detection scheme based on bag-of-global visual features.
The proposed scheme consists of the following steps: feature extraction, feature quantization, indexing based on an inverted index, and searching via the voting function. It realizes
fast detection by accelerating feature extraction and quantization while achieving high detection accuracy and low false
alarm rate owing to multiple assignment and sophisticatedscoring of VWs.

1 0 0 1 0 1

rt , w = {2, vw, N }t,wIndexing step

Fig. 2: Indexing and searching process using an inverted index structure.

or by handling many video clips as a single, long video clip.
In the indexing step, for each segment of reference video, thesegment and block identifiers (t, w) are stored in the vw -thlist of an inverted index for all vw ∈ rt,w . In the search step,
segment-level matching is efficiently performed by inverted
index lookups. Two segments are matched if and only if theyshare the same VW(s) in at least one block. The function
m(Qs , Rt ) judges whether a query segment Qs is matchedwith a reference segment Rt :{∩1 if ∃ w s.t. qs,w rt,w ̸= ∅m(Qs , Rt ) =(1)
0 otherwise.
The indexing/searching process is summarized in Figure 2.
3.3. Offset-level integration
Segment-level matching results obtained by inverted index
lookups are integrated into offset-level results using a voting framework [6, 11]. Every matched segment pair (Qs , Rt )votes for the bin B[t−s] corresponding to the offset t−s ina 1-D Hough space. In voting, since our scheme is basedon the BoVW framework, the inverse document frequency(IDF) weighting [7] can be applicable to emphasize distinctive VWs. Though the IDF scoring has been used only for local features, experimental results in Section 4 show that it also
works well for global features. Performing non-maxima suppression and thresholding to the voting table after voting, we
obtain a set of offset hypotheses. Each hypothesis indicatesthe offset between copied segments in the query and reference
clips. Each offset has segment-level matching results associated with the offset represented by a set of tuples (s, vw , w).
After sorting the tuples according to a query segment identifier s, they are divided into groups to localize the copied segments. A sequence of the tuples are divided if successive twotuples (s, vw , w) and (s′ , vw ′ , w′ ) satisfy s′ −s>th. Finally,
the scores of the segmented tuples are calculated by summingup the IDF weights of VWs appearing in the tuples. Temporal
burstiness-aware (TBA) scoring [6] is also adopted, in which
individual VWs contribute to the score only once even if a
VW is shared in consecutive query and reference segments.
The beginning and ending timestamps of copied segments arecalculated from min and max of s in the tuples.

4. EXPERIMENTAL EVALUATION◦ Detection accuracy: Normalized detection cost rate (NDCR)
measures the tradeoff between the cost of false negatives and false positives, and is defined by a weighted
mean of the two errors.
◦ Localization accuracy: The accuracy of localization ismeasured by the F-measure, which is the harmonicmean of the precision and recall of the detected copy
location relative to the true video segment.
◦ Efficiency: Efficiency is evaluated by the mean processing
time per query.
The following experiments were performed on a machinewith a Core i7 970 CPU and 24 GB of main memory.
4.1. Tradeoffs between repeatability and filtering rate
First, to confirm the effectiveness of multiple assigmentin the temporal domain, we introduce two measurements
to evaluate multiple assignment: repeatability (RP ) and1 − filteringrate (FR). RP represents the probability thata query frame is matched with the groundtruth reference
segment. Larger RP tends to result in low false-negative
rates in detection. FR represents the rate of the number ofmatched reference frames against the number of all reference
segments N . Smaller FR tends to result in low false-positive
rates. There is a tradeoff between RP and FR: a larger FR
results in a larger RP in general. Similar discussions in terms
of approximate nearest neighbor search are found in [12].
Table 1: Query transformations.
T2
T3
T4
T5
T6

T8

T10

Picture in picture
Insertions of pattern
Strong re-encoding
Change in gamma
Decrease in quality (combinations of 3 transformations from blur, gamma, frame dropping, contrast, compression, ratio, and noise)
Post production (combinations of 3 transformations from crop, shift, contrast, caption, flip, insertion of pattern, and picture in picture)
Combinations of 5 transformations from T2-T8

2 http://www-nlpir.nist.gov/projects/tv2009/
Evaluation-cbcd-v1.3.htm(0,4,0)−3

1 − filtering rate

In this section, our CBCD system is evaluated using the
TRECVID 2009 dataset. We chose the 2009 dataset rather
than the most recent 2010 dataset because all queries in the
more recent dataset have both video and audio, precluding
evaluation of video-only queries. The 2009 dataset includes
838 reference videos (about 400 hours in total) and 1,407
query videos. Each query has been edited by the seventransformations listed in Table 1, including both photometric transformations and geometric transformations. In theframework of the TRECVID CBCD task, a CBCD system ischaracterized by three key performance measures2 :

−2

10

10

(3,2,0)(0,2,3)(4,0,0)−4(0,0,3)

10(0,0,0)Feature domain only
Spatial domain only
Temporal domain only

−5

10

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1

Repeatability

Fig. 3: The tradeoff between repeatability and filtering rate under
different multiple assignment settings. From upper left to lower
right, the tradeoff improves.

RP and FR are defined using Equation 1 as∑S
RP = S1 s=1 m(Qs , Rgt(s) ),
(2)
∑S ∑T
1
FR = ST s=1 t=1 m(Qs , Rt ),(3)
where gt(s) denotes the identifier of the ground truth segment
associated with s-th query segment.
We exhaustively evaluate multiple assignments using a
subset of the reference videos and simulated queries thathave been randomly extracted from the reference videos andaltered by a random transformation chosen from contrast
change (±50%), gamma change (±50%), and strong compression. Figure 3 shows the performance of the combinationof multiple assignments parameterized by (mf , ms, mt). Abbreviating mf + ms + mt to m, at most 2m VWs are assigned
to a single segment in the multiple assignment process explained in Section 3.1. Because the memory requirement
increases as m increases, we set the constraint m ≤ 5 here.
It is found that multiple assignment in the temporal domain
is most effective, and multiple assignment in the feature andspatial domain follows. This is mainly because multiple assignment in the feature and spatial domain always increases
the number of assigned VWs at a constant rate, while thenumber of assigned VWs adaptively changes according toscenes in the multiple assignment in the temporal domain
because repeated VWs in a segment are ignored. In noisy or
dynamic scenes, a larger number of VWs is assigned to thesegment, while multiple assignment in the temporal domain
does nothing in a static scene.
4.2. Detection accuracy
The proposed systems are evaluated in terms of detection accuracy. Table 2 shows the resulting NDCR measures of the
proposed systems for different video transformations. Base1and Base2 represent the proposed system with multiple assignment defined by the parameter (3, 2, 0) and (0, 2, 3), respectively. These parameters are chosen to maximize repeatability among parameters w/o and w/ multiple assignment in
the temporal domain. The system performing multiple as-Table 2: NDCR scores for different systems and transformations(lower is better).
Base1
Base2
+IDF
+TBA
[5]
[6]-1
[6]-2

T2
1.000
1.000
1.000
1.000
0.672
0.134
0.239

T3
0.291
0.201
0.052
0.007
0.224
0.067
0.007

T4
0.425
0.246
0.112
0.000
0.381
0.045
0.060

T5
0.448
0.276
0.142
0.000
0.239
0.082
0.022

T6
0.418
0.075
0.007
0.000
0.284
0.433
0.022

T8
0.963
0.933
0.910
0.843
0.269
0.567
0.231

T10
0.993
0.985
0.910
0.821
0.515
0.470
0.269

Table 3: Localization accuracy (F-measure, higher is better).
Prop.
[5]
[6]-1
[6]-2

T2
0.000
0.64
0.937
0.960

T3
0.977
0.89
0.938
0.952

T4
0.967
0.84
0.936
0.949

T5
0.961
0.92
0.940
0.961

T6
0.976
0.83
0.939
0.946

T8
0.883
0.88
0.936
0.957

T10
0.847
0.82
0.941
0.956

signment in the temporal domain (Base2) achieved better
NDCR value by improving the tradeoff between repeatability and filtering rate, as discussed in Section 4.1. We canalso see that adopting IDF weighting (+IDF) and TBA scoring (+TBA) drastically improves detection accuracy. The full
proposed system (+TBA) achieves an NDCR score of 0.002
on average in transformations T3 to T6, which corresponds toa false negative rate of 0.2% (one false negative against 536
positive examples) without any false positives.
In Table 2, the proposed system is also compared to thesystem that had achieved the best performance in TRECVID’09
CBCD task [5] and one of the state-of-the-art systems [6].
[6]-1 and [6]-2 represent a system based on global features and a system based on both local and global featuresdescribed in [6], respectively. The full proposed system outperforms conventional systems in transformations T3 to T6.
As the other transformations include geometric alterations,
it is inherently difficult for global features to handle thesetransformations. Some preprocessing, such as picture in picture detection [6] or letter box detection [3], can alleviate theproblems.
4.3. Evaluations based on other criteria
Table 3 shows the localization accuracy of our system andthe systems described in [5] (estimated from the literature)and [6]. It is shown that our schemes have also achieved
good performance on segment localization criterion in transformations T3 to T6 compared to conventional schemes, owing to the high repeatability in segment-level matching. Table 4 shows the processing time required for each step in the
proposed system: decoding a query video clip, resizing query
frames, feature extraction and quantization, and voting. It isshown that the most time-consuming processes are voting anddecoding. In other words, the search process is as fast as decoding in our system. The system requires only 0.94 seconds
to process a query video clip with a duration of 90 seconds on
Table 4: Processing time required in the proposed system [sec].
Decode0.420

Resize0.023

Feature0.007

Voting
0.488

Total
0.938

average, which is about 95 times faster than real-time, owing
to fast feature extraction and quantization. The system in theliterature [5] reported a much longer processing time of over
200 seconds, which is mainly because their system is basedon local features. The system in the literature [6] requires
around 15 and 121 seconds in global feature-based system
and in local and global feature-based system, respectively.
5. CONCLUSION
In this paper, we proposed an efficient and effective CBCD
system. The proposed system achieved a false negative rateof 0.2% against queries that were altered by non-geometrictransformations without any false positives. As the proposed system is lightweight (95 times faster than real-time),
it can be efficiently combined with other systems, such as
local feature-based or audio feature-based systems, which arecomplementary to global feature-based systems.
6. REFERENCES[1] X. Hua, X. Chen, and H. Zhang, “Robust video signature
based on ordinal measure,” in Proc. of ICIP, 2004, pp. 685–
688.
[2] C. Kim and C. Vasudev, “Spatiotemporal sequence matchingfor efficient video copy detection,” IEEE Trans. on CSVT, vol.
15, no. 1, pp. 127–132, 2005.
[3] S. Paisitkriangkrai, T. Mei, J. Zhang, and X. S. Hua, “Scalable
clip-based near-duplicate video detection with ordinal measure,” in Proc. of CIVR, 2010, pp. 121–128.
[4] L. Shang, L Yang, F. Wang, K. P. Chan, and X. S. Hua, “Realtime large scale near-duplicate web video retrieval,” in Proc.
of MM, 2010, pp. 531–540.
[5] Z. Liu, T. Liu, and B. Shahraray, “At&t research at trecvid
2009 content-based copy detection,” in Proc. of TRECVID,
2009.
[6] Y. Uchida, M. Agrawal, and S. Sakazawa, “Accurate contentbased video copy detection with efficient feature indexing,” inProc. of ICMR, 2011.
[7] J. Sivic and A. Zissermane, “Video google: A text retrieval
approach to object matching in videos,” in Proc. of ICCV,2003, pp. 1470–1477.
[8] J. Philbin, O. Chum, M. Isard, J. Sivic, and A. Zisserman,“Lost in quantization: Improving particular object retrieval inlarge scale image databases,” in Proc. of CVPR, 2008, pp. 1–8.
[9] J. Barr, B. Bradley, and B. T. Hannigan, “Using digital watermarks with image signatures to mitigate the threat of the copy
attack,” in Proc. of ICASSP, 2003, pp. 69–72.
[10] J. Haitsma and T. Kalker, “A highly robust audio fingerprinting
system,” in Proc. of ISMIR, 2002, pp. 107–115.
[11] J. Law-To, L. Chen, A. Joly, and I. Laptev, “Video copy detection: a comparative study,” in Proc. of CIVR, 2007, pp.
371–378.
[12] L. Paulevé, H. Jégou, and L. Amsaleg, “Locality sensitive
hashing: A comparison of hash function types and querying
mechanisms,” Pattern Recognition Letters, vol. 31, no. 11,2010.