Slashdot Mirror
How Stanford Engineers Created a Fictitious Compression For HBO
Tekla Perry (3034735) writes Professor Tsachy Weissman and Ph.D student Vinith Misra came up with (almost) believable compression algorithms for HBO's Silicon Valley. Some constraints -- they had to seem plausible, look good when illustrated on a whiteboard, and work with the punchline, "middle out." Next season the engineers may encourage producers to tackle the challenge of local decodability.
Now they can admit it.
Anyone who knows anything about compression knows that universal lossless compression is impossible to always do, because if such an algorithm existed, you could run it repeatedly on a data source until you were down to a single bit. And uncompresing a single bit that could be literally anything is problematic.
I sort of wish they'd picked some other sort of woo.
Here's the torrent link to Season 1 for anyone who hasn't yet checked out this show.
To me it appears they are professors, programmers and comp sci people in general.
I dunno, mebbe it's me, but I find the Hollywood casting of hackers and geeks somewhat off
Have been in the Valley for decades, having mixed with at least 2.5 generations of geeks / hackers I don't find Hollywood's portrayal of geeks believable
Some 20 years ago when there were some choices of compression software I remember I ran some tests - and found that a utility called "Winace" is the only compression utility that produces a smaller compressed file than the original if compressing .avi, .mov, and .jpg files
All the rest produced larger "compressed" files than the original
Ask CSI. GUI interface using visual basic to track the killer --> http://www.youtube.com/watch?v... Seriously, the average joe that watches TV doesn't care about what algorithm is used, let alone know what an algorithm is.
I watched the show twice and what still isn't clear to me is if the algorithm is universal for all data files or just *media* files (audio, video, pictures, 3D). If it is a universal algorithm then it shouldn't matter if the file is a movie or an application binary executable. But in the show he fretted about being given a 3D movie file. So it is just for media files?
In any case to write "almost believable" is a stretch. I knew from episode one that the algorithm is "totally unbelievable." That is fine because I understand that I have to suspend disbelief. The show was awesome and had some true moments of the trials and tribulations of life in software development. Mike Judge does not disappoint. It makes me wonder at the potential if he and Scott Adams collaborated on technology satire.
Now let's just hope that no aliens listening in to our broadcasting and no far future humans actually believe this and try to recreate the "groundbreaking compression algorithm" the whiz humans of the digital age came up with.
That's another good insight for the wrong article.
How the Unix command line that flashed onscreen in "Tron Legacy" was developed, including rejected alternatives.
JPEG is a lossy compression and it's impossible for an archiving utility using a lossless compression to best that.
Of course it's possible. JPEG encoding has three steps: cosine transform of each block (DCT), then quantization (where the loss happens), then coding. In JPEG, the coding involves a zig-zag order and a Huffman/RLE structure, and this isn't necessarily optimal. A lossless compressor specially tuned for JPEG files could decode the quantized coefficients and losslessly encode them in a more efficient manner, producing a file that saves a few percent compared to the equivalent JPEG bitstream. Then on decompression, it would decode these coefficients and reencode them back into a JPEG file.
Any digital broadcast will include two things that are recognizable as a broadcast. One is a pilot signal, used to communicate the existence of a signal to the receiver. Another is forward error correction, used to reconstruct a signal partially obscured by noise. Analog television included both: the pilot signal was the sync pulses during horizontal and vertical blanking, and the error correction was the presence of a double sideband in the bottom 1 MHz of the video.
I am a PE in California..
one can do engineering in California without a license under the "industrial exemption", and even be called an engineer on your business card.
What you can't do is hang up a shingle and run your own business as Joe Bloggs, Engineer, unless you have a license.
A lot of companies have an HR policy that to be an "engineer" requires a 4 year degree, otherwise you are a "technician". To a certain extent, this is a "exempt" vs "non-exempt" (overtime) distinction. Engineers are exempt from overtime because they are "professional" (having conducted a course of advanced study), Technicians are not.
Tecently, most places treat "fresh out of college" engineers as non-exempt (e.g. get overtime), because the Dept of Labor is looking at other factors: independent work, etc. and the "bar" for advanced study has moved up. Back when the Fair Labor Standards Act was written, a high school diploma and some on the job work was "advanced study".
"Universal lossless compression" doesn't refer to always reducing the file size. It refers to always being lossless, and approaching asymptotically optimal compression levels for any piece of data. Data that is already compressed will generally be slightly expanded by such algorithms (e.g. gzip), so the paradox doesn't factor in. (as a side note, universal compression is actually a pretty big field (cf wikipedia)).
For the video, it's called AVC-Intra. Basically it works like "everything is preserved", but in some extreme scenarios some details are lost.
First of all, some colour is lost because human eye can see levels of gray better, but also pixels are lost when there is a lot of noise on the picture.
Regarding genetics scheme were there is some amount of static information on the decoder and encoder and this partial data can be used to shrink the information transmitted between is already very well known and well investigated by the crypto community but not only.
For example, when there is only text on the screen, the OCR can be performed and the text can be rendered as vector graphics effectively reconstructing original shape picture into much more detail with huge bandwidth savings, like it is done in DejaVu multi-layer compression methods.
This multi-layer compression method would be very good to encode the video, so that if it's news channel, the text is encoded as meta-data while the rest of the picture as standard video. This would be very good as the text could be always rendered as hires even if the background picture is fuzzy.
No you would run the compression and it would not compress. Like when you try to zip a zip file.
Sometimes you don't even need to change the file format - optimization can be applied to already compressed gzip/deflate files (which PNG uses) which can be used to create a more optimal deflate/gzip file. See tools like DeflOpt and defluff (DeflOpt can sometimes make even zopfli encoded files smaller).
ACT has a JPEG recompression test which clearly shows a bunch of compressors making a JPEG smaller. Even better - there's a great paper by the author of packJPG talking about how to compress a JPEG losslessly using the technique teppples described...
He came up with the idea of using lossy compression techniques to compress the original file, then calculating the difference between the approximate reconstruction and the original file and compressing that data; by combining the two pieces, you have a lossless compressor.
This type of approach can work, Misra said, but, in most cases, would not be more efficient than a standard lossless compression algorithm, because coding the error usually isn’t any easier than coding the data.
Well, this is almost how MPEG movie compresion works - and it really does work! MPEG works by partly describing the next picture from the previous using motion vectors. These vectors described how the next picture will look based on movements of small-ish macroblocks on the original picture. Now, if that was the only element of the algorithm movies would look kind of strange (like paper-doll characters being moved about)! So the secret to make it work is to send extra information allowing the client to calculate the final picture. This is done by subracted the predicted picture from the actual next frame. This difference-picture will (if the difference between the two frames was indeed mostly due to movement) be mostly black but it will contain some information due to noise, things that have become visible due to the movement, rotation etc. So MPEG also contains an algorithm that can very efficiently encode this "difference picture". Basically an algorithm that is very efficient for encoding an almost black picture.
So there you have it - MPEG works by applying a very crude, lossy compression (only describing the picture difference in terms of motion vectors) and in addition transmitting the information required to correct the errors and allow reconstruction of the actual frame.
The only part where the comparison breaks down is that MPEG is not lossless. Even when transmitting the difference picture, further compression and reduction takes place (depending on bandwidth) so that the actual frame can not be reconstructed 100%. Still MPEG is evidence that the basic principle of using a crude lossy compressor combined with sending a compensation, works.
http://en.wikipedia.org/wiki/S... "In information theory, Shannon's source coding theorem (or noiseless coding theorem) establishes the limits to possible data compression, and the operational meaning of the Shannon entropy."
Forget streaming the movie. Just send the UPC code for the DVD...
Odd because I'm designing something that I believe to be a new type of compression which directly targets seemingly random streams.
Funny how the world keeps following these little endeavors I partake in.....
The last 4 major things I've done where I intentionally go against the grain and try something new has resulted in a sudden shift to that idea a year later in the industry.
Perhaps I'm either onto something or thinking similarly to others who are breaking new ground. Definitely more motivation to continue forwards.
In 2000 I imported an AWD turbo 4cylinder rally car from overseas due to the lack of them in the USA. I wanted to show how a little 2.0 engine could make well over 600 horsepower and with four wheel drive simply destroy a "drag-racing" V8. In 2003 they finally sell a detuned imported model from Japan. In 2001 the Fast and the Furious comes out and blam, everyone has to have one. Now in 2012+ everyone including non-sports car enthusiasts all want turbo 4 engines.
I start using tricks in OpenGL to use vector coordinates as a shorthand for getting the GPU to do math in 2004-2005. Then in 2007 here comes CUDA and suddenly everyone is doing it.
I disliked the P4 which everyone loved and decided to stick with a dual CPU Tualatin-pin modded board running dual P3s and preferring SMP. I thought dual slower processors were more useful than one faster one as a developer. Everyone else said I was wrong. Fast-forward the Core2 architecture abandoned P4 for P3-based design which also moved into dual processors. Also the X2 came out from AMD and suddenly *everyone* had to have 2 processors.
I decided to focus on crazy fuel economy and bought a 3 cylinder Geo Metro since no one produced a 3 banger since 2001. Now we have the recently released Ecoboost 1.0 3 cylinder turbo from Ford, and the new Mitsubishi Mirage with a 1.2 3cylinder non-turbo.
I gotta say I keep trying to think outside the box and do something fresh and different only to find that society then moves in my direction a year or two later no matter how odd my path was.
Now I'm building a compression algorithm based off of the idea of iteration (and I won't say a thing more) and now some show I haven't even seen is now based entirelly around the idea of building compression algorithms (which has been super un-cool to everyone I've tried to talking to about it for about the past 2 years).
What an odd set of coincidences minimally.