Abstract:

Current web video search results rely exclusively on text keywords or user-supplied tags. A search on typical popular video often returns many duplicate and near-duplicate videos in the top results. This paper outlines ways to cluster and filter out the near-duplicate video using a hierarchical approach. Initial triage is performed using fast signatures derived from color histograms. Only when a video cannot be clearly classified as novel or near-duplicate using global signatures, we apply a more expensive local feature based near-duplicate detection which provides very accurate duplicate analysis through more costly computation. The results of 24 queries in a data set of 12,790 videos retrieved from Google, Yahoo! and YouTube show that this hierarchical approach can dramatically reduce redundant video displayed to the user in the top result set, at relatively small computational cost.

Figures:

Figure 1: Search results from different video search engines for the query “The lion sleeps tonight” demonstrate that there are a large number of near-duplicate videos in the topmost results..

Figure 2. Keyframe sequence of near-duplicate videos with different variations (each row corresponds to one video). (a) is the standard version (b) brightness and resolution change (c) frame rate change (d) adding overlay text, borders and content modification at the end (e, f) content modification at beginning and end (g) longer version with borders (h) resolution differences

Figure 3. Two videos of complex scene query “White and Nerdy” with complex transformations (only the first ten keyframes are displayed): logo insertion, geometric and photometric variations (lighting change, black border), and keyframes added/removed

Near-Duplicate Web Videos

1. Formatting differences

  • lEncoding format: flv, wmv, avi, mpg, mp4, ram …
  • lFrame rate: 15fps, 25fps, 29.97fps …
  • lBit rate: 529kbps, 819kbps …
  • lFrame resolution: 174x144, 320x240, 240x320 …

2. Content differences

  • lPhotometric variations: color / lighting change.
  • lEditing: logo insertion, adding borders around frames, superposition of overlay text.
  • lContent modification: adding unrelated frames with different content
  • lVersions: same content in different lengths for different releases.

Hierarchical Framework

  • Global Signature with Color Histograms
  • Pairwise Keyframe Comparison with Matching of Local Features

Application

  • Novelty Re-Ranking
  • Near-Duplicate Video Retrieval

Reference:

  • Xiao Wu, Alexander G. Hauptmann and Chong-Wah Ngo
    Practical Elimination of Near-Duplicates from Web Video Search
    ACM International Conference on Multimedia (ACM MM’07), Augsburg, Germany, Sep. 2007 (oral).
    Full Text: [PDF, 3.79M]