Near-Duplicate Video Detection

What is VSC - Video Similarity Check?

VSC is a powerful video matching software tool for near-duplicate video detection within large databases. It is designed mainly for linux workstations, to process a huge amount of videos very fast, using as few resources as possible. After building an indexed database (containing several 10,000 hours of video footage), small video sequences can be tested against this database within a couple of seconds.
These test videos can vary in size, aspect ratio, codec, compression strength and much more, and will still be found. So VSC can be used as a duplicate finder or near-duplicate detector to clean your database from unnecessary video copies and clones, or to recognize video copyright infringement, for example.

What does "similarity" and "near-duplicate" mean?

Detection of exact copies of a video is a trivial task. But even if the video is only transcoded, let's say from MPEG-2 (DVD) codec to H.264 (widely-used efficient videocompression), so that it is very difficult for a human to notice any difference between them, you need already a good software algorithm to identify this as a duplicate. And because it is not an exact copy/duplicate (byte by byte video clone) it is called a "near-duplicate". If the video is just a part of the original and slightly changed in coloring and modified with black borders and logos for example, a human still recognizes this as a near-duplicate, but computers have a hard time to "see" this similarity.

The "Similarity" in VSC stands for a wide range of near-duplicates, which means "copied and possibly slightly modified parts from an original". So VSC does not detect semantic similar video scenes, but copied parts of an original video within your database.
The first row in the image above shows some modifications, but we still consider it as a duplicate. The right image shows some compression artefacts, has a lower resolution, black borders on top and bottom and a logo inserted at the top right corner. But we still notice, that this is a modified version of the left image, a near-duplicate. The second row shows us a very similar image, but there is no way getting the right image out of the left one with some simple image modifications. It is still some kind of elephant, made of some Lego like bricks, but it is a complete different scene and not even the "same" elephant, so we do not consider this as a copy or a near-duplicate.

What imageprocessing / videomatching techniques can be used for near-duplicate video recognition?

Before discussing suitable algorithms, let`s think about what we expect from a software capable to find near-duplicate videos:

1. To detect a near-duplicate video, a single test video has to be compared against a large video database. This means that techniques which compare video versus video directly are not suitable - they need too much time.
2. A short test video sequence should be detected as a copy or near-duplicate if it is part of a larger database video. If there is a long test video, and we want to find out if there are any subsequences already in the database, this kind of duplicate search should work too.
3. The software should recognize only real near-duplicate videos and not semantic similar videos. We want to find video copies and not videos with just the same subject. On the other hand, these duplicate or near-duplicate videos are often modified in size, length, compression and include/exclude borders, banners and logos.
4. Video databases can be very large and contain several 100 TB of video material. So the used algorithms should be very efficient in terms of speed and resources.

So what does this mean for the algorithmic requirements:

1. General video or image features (descriptions, patterns) have to be defined which are able to describe a specific videopart. These features are added to a database and linked with the corresponding video. Afterwards, if we want to check a new video, we just have to extract the defined features from this video and look in our database to which known video they link. If it is a unique new video, there will be no matches at all.
2. A video can be considered as a sequence of images. To detect any subsequence (videopart) we have to choose features which describe very small sequences, maybe as small as single images.
3. To find robust features, which are insensitive to resolution, noise, compression artefacts, logos and so on, will be the most challenging part.
4. The chosen features have not only to be robust, but also CPU and memory "friendly". To combine these (maybe contradictory) properties and to exactly know what computers are good in and which kind of algorithms should be avoided, will be crucial. So extreme robust and fast algorithms will be the secret to success.

What algorithms does VSC use?

VSC uses a close to single image registration technique combined with time correlated evaluation. The implemented perceptual hashing algorithm is the fastest of its kind. But the key to success is the interaction of feature robustness and the "perceptual" part of the algorithm. And to make sure VSC is the fastest out there, SSE (Streaming SIMD Extensions) and multicore support are a matter of course.

Latest version: VSC 1.4 [March, 2015]

• Processing speed indexing: ~20 GB/h ¹ (per 3 GHz core)
• Processing speed testing: ~20 GB/h ¹ (per 3 GHz core)
• Resources: ~1 GB RAM per 1 TB database videos ² (workstation parallelization for databases > 100 TB)
• Unaffected by³: codec, framerate, compression strength, artefacts
• Unaffected by³: color balance, brightness shift, noise, blurring
• Unaffected by³: resolution, aspect ratio, black borders, logos
• Adaptive multi server/client solution and online scalable parallelization^New
• Video clips from below 20s^New to several hours
• Multicore and multi server support^New
• SSE, SSE2, SSE3, SSSE3, SSE4, AVX support^New
• Support for newest FFmpeg 2.5 and libav 11.2^New
• Sensitivity: ~96% ⁴
• False positive rate: ~2ppm ⁴

¹FullHD (1920x1080, 25p, MPEG-4 (FFmpeg) Codec, AVI-Container): ~15h videos per hour
  HD720 (1280x720, 25p, MPEG-4 (FFmpeg) Codec, AVI-Container): ~30h videos per hour
  HD720 (1280x720, 25p, H.264 /AVC Codec, MP4-Container): ~10h videos per hour
  VGA (640x480, 25 fps, MPEG2 Codec, MPG-Container): ~60h videos per hour
²~0.5MB RAM / hour database video footage
³ Moderate real life variations
⁴ Tested with video clip lengths of 5 minutes in average

VSC is the ideal tool for operators of tube sites, video search engines, video libraries or similar, to handle large video databases or to fight with state of the art methods against video copyright infringement. If very large video databases have to be processed, accuracy, speed and scalability are the crucial factors for a near-duplicate video detection software. So if extreme processing power and highest accuracy is needed, VSC is the way to go!
VSC is distributed via per year license (single server and all inclusive variants - please ask for pricing and special offers).

In 2012, the Internet Commerce Security Laboratory (ICSL) at the University of Ballarat undertook a large scale test of video duplication detection technologies under a private contract. The report itself cannot be made public, however we can acknowledge that the algoxdream VSC system was, by far, the best method that we tested. We compared VSC with other software solutions for the task of matching videos under modification, and found most other solutions had a poor accuracy. In contrast, VSC was able to handle most forms of modification that we were able to generate. During our testing phase, we were able to identify some modifications, such as mirroring, that VSC was unable to identify, but was able to with a different configuration. This configuration only slightly increased the false positive rate. Even with this configuration, VSC was still the best solution. While the system was not able to handle very short videos of less than two minutes, we were unable to find a solution that does. In addition, the support provided by algoxdream was fantastic and prompt.

We wholly recommend this product for the purposes of detecting duplicate videos under manipulation above competitor products.

This was an independent evaluation of a set of products. For our testing, algoxdream provided access to a testing server for no cost. We have not received any reimbursement for this recommendation, nor have any private or professional dealings with algoxdream previously, or expectations to have in the future.

Dr. Robert Layton
www.icsl.com.au