Story time.

Back in 1999, I was leaving a startup that had been acquired, but I didn't want to stick around. I had been doing in mpeg encoding; this is relevant later.

One of the companies I interviewed with had come up with a new video compression scheme. They were very tight lipped but after signing NDA paperwork, they showed me some short clips they had encoded/decoded via a non-realtime software codec. I was interviewing to create an ASIC version of the algorithm. Even seeing just a minute or two of their codec output, I guessed what they were doing. I suggested that their examples were playing to the strengths of their algorithm and suggested some scenarios that would be more challenging. I also described what I thought they were doing. They neither confirmed nor denied, but they had me come back for a second round.

In the second round I talked with the founders, a husband/wife CEO/CTO (IIRC) team. That is when I learned their plan wasn't to sell ASICs, but they wanted to keep their codec secret and instead create DSL-based cable network using the ASICs for video distribution. I said something like, it sounds like you have invented a better carburetor and instead of selling carburetors you are planning on building a car factory to compete with GM. It was cheeky, and they didn't take it well.

Getting to the point of how this story relates to H.264, their claim was: conventional compression has reached the limit, and so their codec would allow them to do something nobody else can do: send high-def video over DSL lines. I replied: I think compressors will continue to get better, and even if not, higher speed internet service will eventually come to houses and remove the particular threshhold they think only they can cross. Oh, no, they replied, physics dictates the speed bits can be sent on a wire and we are at that limit.

I didn't get (and didn't want) a job offer. The company did get some VC money but folded a few years later, much more efficient codecs were developed by others, and 2 Mbps internet connections were not a limit. I'm sure the actual algorithm (which I describe later at a high level) had a lot of clever math and algorithmic muscle to make it work -- they weren't stupid technically, just stupid from a business sense.

This retelling makes me sound like a smug know-it-all, but it is one of two times in my life where I looked at something and in seconds figured out their secret sauce. There are far more examples where I am an idiot.

What was their algorithm? They never confirmed it, but based on silhouette artifacts, it seemed pretty clear what they were doing. MPEG (like jpeg) works by compressing images in small blocks (8x8, 16x16, and a few others). That limits how much spatial redundancy can be used to compress the image, but it also limits the computational costs of finding that redundancy. Their codec was similar to what Microsoft had proposed for their Talisman graphics architecture in the late 90s.

From what I could tell, they would analyze a sequence of frames and rather than segmenting the image into fixed blocks like mpeg, they would find regions with semi-arbitrary boundaries that were structurally coherent -- eg, if the scene was a tennis match, they could tell that the background was pretty "rigid" -- if a pixel appeared to move (the camera panned) then the nearby pixels were highly likely to make the same spatial transformation. Although each player changed frame to frame, that blob had some kind of correlation in lighting and position. Once identified, they would isolate a given region and compress that image using whatever (probably similar to jpeg). In subsequent frames they'd analyze the affine (or perhaps more general) transformation from a region from one frame to the next, then encode that transformation via a few parameters. That would be the basis of the next frame prediction, and if done well, not many bits need to be sent to fix up the misprediction errors.