Compressing video files; algorithm idea

[garreh]

Hi All

Developers, let me know what you think of this new idea for a compression algorithm, whether it would work, complications, etc.

Video files are compressed using codecs. Let's say we are using XviD as an example. Different frames point information that has changed between those frames, to save the amount of data needed in the file. So a "map" is created to describe what information has changed. This map is local to that file only. Now what if the same idea was applied to multiple files in a predefined directory, and have a single mapping file that can be used as almost like a lookup.

The downside to this is, of course, if the mapping file is deleted then all files that point to it will become corrupt. A workaround would be to copy over the data from the mapped upon deletion of a file that would become corrupt.

Another downside is let's say a series of Red Dwarf is encoded at different bitrates. The intro remains the same for the same season, but yet it won't be the same information bit for bit simply because it's encoded at different bitrates. The workaround would be to analyse each frame of all the different video files to be compressed, compare how different they are, and decide whether certain frames can be described as one with little to no difference in human perception.

This theory has a lot of caveats and I'm not sure of the technicalities of it, whether it could be incorporated into the codec, or even if the whole concept would save that much data. But it just seems that there is a lot of duplicated data from video file to video file, and simply pointing to this information would save much data. This is particularly true among files that are of the same TV series, where the intro and outro are the same, same kind of scenes, and so forth.

This idea is sort of related to an article I read a few years ago by some professor of a university. I'm sorry I can't quite remember the details, but the general idea remained the same. The concept was to speed up P2P and Torrent by finding duplicate pieces of a file from other files from different sources. So for example, your downloading Battlestar Galactica and some piece in that file is exactly the same as something found in a download of a Windows XP Hot Fix file. Of course, with Microsoft's very fast servers, it would dramatically improve the download speed.

What are your thoughts?

[Firon]

Won't work.

[hermanm]

From a visual perspective, there is a lot of repeated information (opening credits & ending credits), but on a data level, the opening credits from one video file will not match the opening credits from another video file.

Companies like YouTube use video recognition technology to get a score on copyright material that distribution companies send them to semi-automate takedowns. Airports and casinos also use video recognition to flag individuals they want to scrutinize. This requires an immense amount of processing power to compute fast. It also requires a human being to make the final call.

> Of course, with Microsoft's very fast servers, it would

> dramatically improve the download speed.

Essentially, everything is either a 0 or a 1. So, we have all the data we need to view a movie. Its just how those 0s and 1s gets assembled. How do you detect if a piece is a duplicate or not? What piece size do you compare? Who keeps this information? In theory, it sounds nice, but actually making it a usable system doesn't sound practical nor doable right now. I suggest you use a program like HJSplit and chop some movie files into 4 kB chunks. Run SHA1 on all of them. See if you can find any pieces that match up within the movie file or files on your hard drive.

[garreh]

The problem with splitting the file into chunks and running SHA-1 on them is simply knowing where is the best place to split?

Splitting one byte ahead will produce radically different results of the hashed pieces. To overcome this, an edit-distance algorithm, such as Levenshtein, would find out how much data it takes to transpose one hash into another. From this information you could work out the best place to split the data, and hash that.

Your correct, there is the problem of who keeps this data? A huge database of hashed pieces value, their exact location, etc, is simply impractical right now. However, the concept I'm explaining is local to the user's hard drive. The other example of speeding up P2P is only really practical if, for example, the huge network Ares could incorporate this into their protocol.