Now that AV2 has officially been released it’s time to remind that these codec advances are not for free. Here it is claimed that AV2 offers about 25% improvements in compression efficiency compared to AV1 with decoding being five times slower (and that’s for an extremely optimised decoder; no idea how much slower encoding is).
Back in the day I proposed to go full AI with the codec design but it was not a fully serious idea, here I’d like to propose something more realistic that would use “AI” hardware that we should have plenty of by now—and with no AVn codecs in mind.
The basic idea is that video compression is being improved mostly by trying more and more different approaches on varying blocks of data that depend on previously coded blocks of data. For modern mainline video codecs the structure is simple: divide frame into, say, 128×128 tiles, split those tiles into e.g. 64×64 blocks, decide whether you want intra or inter prediction there, split those blocks further and try some specific intra/inter coding mode on them, maybe split them further… One of the problems is combinatorial explosion as the number of coding approaches tried correlates with the product of coding alternatives at each stage, so adding just one new method (e.g. previously there was just one 8×8 DCT or 4×4 DCT approximation being employed in all cases, now you can select one out of several transforms let alone the fact that transform size is no longer fixed either) may increase the coding time by tens of percents (of course It Depends™ on the settings, heuristics used and so on but it always increases encoding time, and decoding time may be affected as well)—and now remember that there’s usually at least several new coding tools being added for each new codec iteration. The other problem is data interdependency: you can’t work on a new block before you encoded its neighbours since you may need its data for intra (spatial) prediction.
The answer to that so far was to add more coding tools, better heuristics and hope for Moore’s law to take care of the rest. What I propose is an alternative approach: split encoding into a phase that’s easy to do per block and the second stage that encodes data from the previous stage using context-dependent arithmetic coder or a variation of it. Approximately it’s like coding 8×8 with either intra DCT or DCT of the difference to the previous frame; zeroth stage would calculate those differences (or perform motion compensation), first stage would apply DCT on both intra and inter versions of the blocks, and the final stage will select either version to encode). Of course such scheme is too simple to produce good compression, so here are two methods from the past may come in handy. They did not gain much popularity for being too slow back in the day but are perfect for the modern hardware.
I’m talking about vector quantisation and matching pursuit. To oversimplify it, vector quantisation keeps a codebook of possible image pieces and either selects the most fitting one (like in Cinepak) or constructs image using several entries from its codebook (like mean-removed VQ used in SVQ1, I really should write an encoder for it). Matching pursuit is a similar idea where you construct an image from several pieces in its codebook. To help visualise that idea, look at 8×8 2D DCT bases (here’s a link to Wickedpedia) and think that any 8×8 block can be represented as a sum of some of those bases scaled by a certain number (and the transform itself produces a matrix of those weights for each of the bases—the fewer of them you use the better is compression). Now vector quantisation (one of the varieties) would be having, say, sixteen 8×8 bases and sixteen 4×4 bases for the refinement details (so you code it as one 8×8 base plus four 4×4 base applied as a difference to each quadrant). Matching pursuit means you may have 256 various bases and you select an image as a set of, say, 1-3 of them. It may look excessive at the first glance but it should work better on representing e.g. diagonal and curved lines.
It should be obvious that a scheme employing VQ/MP plus coding of its results offers both scalability and flexibility: as with an ordinary transform you may decide to discard or transmit less important details separately. And the requirement for searching for the best candidate (which made it impractical back in the day) should be no problem for GPUs or TPUs (and with enough parallelism CPUs as well).
So the final scheme should look like this: motion search, VQ or MP for intra and inter blocks, context-dependent coding for indices and motion vectors (and maybe loop filtering). The main challenges here are designing good codebooks for intra blocks and inter differences (which probably just needs collecting a data on encoding a lot of content in different genres and sizes; maybe it makes sense to have several codebook sets for e.g. QCIF, FullHD and UHD content) and devising a scheme for effective compression of the codebook indices (of course they should be coded in a similar manner as generic integer values are coded in H.26x or VPy but maybe they can be predicted as well?). At least both the encoder and the decoder for such format should be much simpler than the state of the art video codecs so more efforts can be dedicated to improving existing few things instead of finding a way to bolt on a new coding tool and then research when actually use it.
P.S. For rather obvious reasons I’m not going to even attempt to design such format. But if somebody wants to do that and name the resulting codec Sleet, Photon2 or Nadd—be my guest.
Bink Video 3.0 format
Bink2 author Fabian Giesen has his own blog, petition him instead.
It has been a long time since I have heard of AI applied to video compression. When I did, it essentially boiled down to using neural networks to perform optimal vector search in a VQ scheme, and that was like 20+ years ago. There are much better opportunities now, and I assume the big boys already leverage the techniques.
I suspect if you asked a modern LLM to compress a video optimally, it would say, “Sure! Here are some FFmpeg command lines you can use…”
…
And how did I never know about that Bink2 author’s blog?
I suspect that like fashion it works in cycles. I still remember virtual reality being a hot new thing in mid-90s (and AI was a hot research topic in 1960s and 1980s apparently). Maybe it’s time to re-discover some forgotten techniques and put them to work again. I don’t think that fractal compression or wavelets would ever be good, but VQ can be optimal and there’s more to it than representing small blocks with two colours and a mask.
As for the blog, I learned about it when somebody shared a link to https://fgiesen.wordpress.com/2013/11/04/bink-2-2-integer-dct-design-part-1/ in the comments to my post about something Bink2.
Mixing vectors from a codebook sounds like KLT, which we’ve talked about on here before. I feel it should be pointed out once again that with KLT it’s possible to have a non-square grid.
Speaking of grids, there’s no reason why we should limit ourselves to splitting blocks along axis-aligned planes. AV1 already has this with its wedge partitioning scheme. But the idea could be applied to macroblock splitting as well.
Another idea worth considering is non-linear prediction. One could for example mix in the squares of surrounding pixels in addition to the usual linear prediction. There are papers demonstrating the surprising effectiveness of such schemes compared to NNs. As a bonus there’s zero AI woo involved.
Mixing vectors from a codebook sounds like any transform at all, it’s just in KLT case the codebook is calculated to have most energy in its first entries and VQ/MP do not necessarily have a codebook of regular structure and with the size 2^N. And of course it’s even easier to adapt them to any kind of grid but people are lazy (and wedge partitioning comes from inherent weakness of rectangular DCT-like transforms to represent diagonals, here it’s significantly less important).
As for non-linear prediction, it sounds suspiciously like overlapped transforms and OBMC. For some reason both never got past H.263 era even if Daala tried to resurrect the former (and wavelet enthusiasts can’t let go of the latter).
Overlapped transforms are still linear, no?
What I’m getting at is that for example intra prediction could have available to it not just the surrounding pixels, but also their values passed through some non-linear function. The encoder could have at its disposal a number of functions and signal to the decoder which functions it chose, along with mixing coefficients for each output sample. Even modest gains in prediction accuracy is likely to pay off.
Overlapped transforms are linear but they work on data outside block boundaries as well, so they still mix surrounding pixels (even if not squared or logarithm of them or whatever).
In general it looks promising indeed but one should still watch that metadata expenses (as you still need to code those functions, modes and coefficients) would not outweigh bit savings for residue coding.
Yes of course, one has to check how many bits coding the extra functions and coefficients costs compared to the savings in residual bits. Luckily this is relatively straightforward. The real issue is that finding an optimal coding is combinatorial. Hill climbing probably works well enough in practice.
In either case I’m looking forward to more original and slightly crazy ideas being incorporated into codec design.
On the topic of things I wish would happen, but know they won’t:
* I wish an x264-like high quality encoder would materialize for EVC (the codec, not the filter), or rather, for a new EVC2 “standard”, with added tools and techniques from all the patents that expired since EVC (v1) came out.
Let’s see how such an encoder would fare against HEVC/VVC and VP9/AV1/AV2 for UHD content, with both enc/dec complexity and quality (not PSNR of course) examined.
And let’s see how much better new codecs can do at above-passable quality 1080p encodes, while requiring nnX or even nnnX the complexity 😉
* I wish, and I was writing this before reading the other comments, I wish Daala development would resume from where it stopped before AOM nuked it. Maybe with a focus on specialized use-cases, like intra-only, archiving (to replace Dirac lol), and perhaps mezzanine too!
Mezzanine in particular doesn’t appear to be a hard space to make inroads in, considering people got relatively excited for APV, despite it being trash.
As for AI, I’m actually starting to have a less disdainful outlook towards it. Considering it’s both “too big to fail” AND “requires a level of deregulation to work”, it may prove to be useful..in ways that perhaps were never intended. And hey, maybe someone knowledgeable and driven will decide to “throw agents” at my first wish, with some good guidance along the way. It would be interesting to see how far they would manage to go.
1) Maybe that’s exactly why there is nobody much working on x264 successor: newer codecs are getting developed for larger resolutions in mind and their encoders also tend to disregard smaller features. So mostly modern UHD content after encoding is good only for producing FullHD downscales.
And while PSNR is the shittiest visual metric of them all (except for all the others we’ve tried) I see two advantages in it: it’s simple and it’s impartial. Even in SSIM there are special weighting coefficients present already, more advanced metrics are all just special weights (with many ways to cheat).
2) To me APV looks more like EVC aka let’s re-make JPEG but with bit-exactness and slightly better compression while not hitting on patented technologies. I suppose it works good enough there (not that I’ve ever tested it). And probably its (whatever moderate) success signals that there’s something other image formats don’t offer.
As for Daala, I rather wish there would be a non-Xiph group doing the development of free and open multimedia formats. What Xiph folks have produced is technically impressive and covered some needs but at the same time they have hard time understanding what others would like to use (e.g. an archival codec from them would probably still depend on global headers, support only Ogg and lack checksums; and it would be next to impossible to have an alternative implementation supporting it). But I suppose there’s little interest in developing video codecs in general, just look how much time went before the initial intent for AV2 and its actual release.
3) I doubt any amount of “AI” will help with your wish as it’s next to impossible to formally specify what you consider good quality beside “I know when I see it”. Which returns us to the question of good metric…
> newer codecs are getting developed for larger resolutions in mind
Actually, that was a part of my half-joke/half-wish. Nue-Codec stakeholders (let’s not pretend the developers themselves are that important) show you “wins” from one codec generation to the next, as an excuse for the complexity tax.
The marketing focuses on both passable-at-best quality, and UHD. For 1080p and high quality, the marketing would not look that convincing if attempted, from the start 😉
But what if the complexity/improvement doesn’t have to come in a full (bloated) package?
EVC claims 30% BD reduction over H264 with less complexity than HEVC. What can a theoretical EVC2 achieve for UHD content, while still having less, or at worst, equivalent complexity to HEVC?
(oversimplification: bigger blocks matching HEVC and later codecs compared to H264, simpler “old” or royalty-free tools otherwise).
This is a half-joke/half-wish because, obviously, the stakeholders are not going to *potentially* threaten invalidating all their “work” and marketing 😉
And that’s where the half-joke/half-wish about AI agents comes in the picture. Because the “theory” is that they can bridge the gap left by the lack of support/resources from said stakeholders.
I think the milestone should be rather “30% BD reduction over H.EVC with less complexity than VVC”. For practical purposes EVC is exactly HEVC lite (i.e. taking it as the base and throwing out all patented bits before discovering there’s more of them left in the standard), so EVC2 should be VVC with some bits thrown out.
For your proposed solution—don’t bet on it. Nothing can replaced a motivated human with taste.