Ideas for New Concepts for Video Compression

[3NC0D3_Y0_A$$]

Ok (this may be a bit noobish), So we know various video codec standards have different 'concepts' to encode video and reduce bitrate whilst maintaining quality to the human eye. I realize that a lot of video codec development is down to improving the efficiency or 'eloquance' of these video compression techniques and the languages they are written in.

The H.264 video codec standard has the following compression techniques:

CAVLC/CABAC, Loop/Deblocking Filter, Variable Block Sizes/Macroblock Partitions, Multiple Reference Frames, Weighted Prediction, Rate Distortion Optimisation (RDO).

What other video compression 'concepts' or techniques can you think of?

Its unlikely that anyone is generating a new video compression standard anytime soon, but it still would be interesting to see what ideas people can come up with.

Just for starters:
Perhaps encoding the edges of a still object into an equation for a shape (that outlines it) and also the inside of the shape if the colour is uniform. (this would be useful for distance objects in still shots)

[nm]

Its unlikely that anyone is generating a new video compression standard anytime soon, but it still would be interesting to see what ideas people can come up with.
New open standards are ratified quite often and some companies have their own closed "standards". As an example of an upcoming open (and royalty-free) standard, Dirac Pro is being standardized as SMPTE VC-2.

If you're interested in new techniques and innovations, I'd suggest checking out the abstracts of video compression research papers from the last five years or so.

[Inventive Software]

The only standard they could realistically go into is Snow, which has yet to be given a final specification.

[nm]

The only standard they could realistically go into is Snow, which has yet to be given a final specification.
Who could go? SMPTE? I seriously doubt Michael Niedermayer or other FFmpeg developers would ever consider going through such a standardization process for Snow. RFC maybe.

[3NC0D3_Y0_A$$]

Who could go? SMPTE? I seriously doubt Michael Niedermayer or other FFmpeg developers would ever consider going through such a standardization process for Snow.

Snow? can you explain what this means please?

[nm]

It's a wavelet codec in FFmpeg/libavcodec, written by Michael Niedermayer. See: http://en.wikipedia.org/wiki/Snow_(codec)

[3NC0D3_Y0_A$$]

It's a wavelet codec in FFmpeg/libavcodec, written by Michael Niedermayer. See: http://en.wikipedia.org/wiki/Snow_(codec)

cheers.

[Inventive Software]

ffmpeg's website has a notice that says a specification will be written up for Snow eventually, if there is enough interest. Until then, it's basically a free-for-all based on current code. I think it has CABAC and OBMC and inloop deblocking. Basically borrowing ideas from other codecs, and developing new techniques to make a usable codec to attack H.264 is I think Snow's final aim, but at the moment, speed is less than desirable.

[IgorC]

CAVLC/CABAC, Loop/Deblocking Filter, Variable Block Sizes/Macroblock Partitions, Multiple Reference Frames, Weighted Prediction, Rate Distortion Optimisation (RDO).

Don't worry. Guys are already preparing H.265.


I'm not a professional of video compression but afaik central concept of lossy compression is transform (between temporal to (complex) frequency domains ) like DCT.


There is no proof that wavelet transform is better than (M)DCT.
Jpeg2000 (wavelet) is worse than intra H.264 based on DCT.


afaik it is planned that 2008 will be last year of changing reference source of H.264, new profiles etc... And there will be first papers about H.265 in 2009.

[Dark Shikari]

There is no proof that wavelet transform is better than (M)DCT.But unlike DCT, it can be used in combination with OBMC to avoid blocking altogether.
Jpeg2000 (wavelet) is worse than intra H.264 based on DCT.That's basically because its intra prediction is FIR instead of IIR.

[MfA]

OBMC is not completely blocking free.

I think the improvements which can be gained by OBMC and wavelet coding in the end are only slight. IMO motion coding is the lowest hanging fruit for big improvements at the moment, motion motion compensation and per pixel lossy coding of the motion field.

[Dark Shikari]

OBMC is not completely blocking free.

I think the improvements which can be gained by OBMC and wavelet coding in the end are only slight.IIRC total residual can be decreased by about 25% using OBMC.

[Manao]

Some of the high points that are being considered for inclusion in h265 are :
- 80+ prediction mode just for intra, which greatly increase intra efficiency
- intra frame motion vectors
- free macroblock partitionning for inter : instead of fixed 16x8, 8x16, 8x8... partitions, you can cut a block/macroblock in two by defining a cutting line however you want (not just vertical/horizontal, but any angle too)
- better syntax (for example, better motion vector prediction)

[akupenguin]

That's basically because its intra prediction is FIR instead of IIR.
Which is in turn because I have yet to see anyone make IIR intra prediction compatible with wavelets, nor have I thought of a way myself.

@MfA:
Want to run Snow and point out a blocking artifact to me?

@Inventive Software:
Snow doesn't have inloop deblocking because it doesn't need it. OBMC+Wavelet doesn't produce blocking artifacts, so doesn't need to be deblocked.

[Dark Shikari]

Which is in turn because I have yet to see anyone make IIR intra prediction compatible with wavelets, nor have I thought of a way myself.Why is this? Isn't intra prediction entirely spatial, with wavelets merely being a way to encode the residual?

[NerdWithNoLife]

If you're interested in new techniques and innovations, I'd suggest checking out the abstracts of video compression research papers from the last five years or so.
Goodness, did you ever read those papers on DCT, quantization, or compression domain transcoding?

That's a real quick way to feel like an idiot.

[akupenguin]

H.264 spatial intra prediction predicts from the decoded pixels of the neighboring blocks. In any transform with overlapping basis vectors, the neighbors haven't been decoded yet. Plus you need a continuous prediction function if you want to retain the block-free nature.

If you're interested in new techniques and innovations, I'd suggest checking out the abstracts of video compression research papers from the last five years or so.
Don't try this at home, kids. The signal-to-noise ratio in video compression research is really low, so if you don't already have the intuition to cull the BS papers, reading isn't too useful.

[Zarxrax]

Just for starters:
Perhaps encoding the edges of a still object into an equation for a shape (that outlines it) and also the inside of the shape if the colour is uniform. (this would be useful for distance objects in still shots)

This is quite similar to the way flash animation works. I've long thought that something like this could be very effective for anime content, but I have yet to see any sort of proof of concept idea for it. There are some tools out there that have become fairly decent at vectorizing a still image, but I have yet to see anything that can intelligently vectorize a video stream. Perhaps the mathematics behind it is just too complex.

[Inventive Software]

Why is this? Isn't intra prediction entirely spatial, with wavelets merely being a way to encode the residual?

I think the wavelet transform is done before anything else, then OBMC is done on top of that.

[Birdy1]

Is there something like a 3 dimensional wavelet? If so, a scene could be encoded as a 3D wavelet, where the z-axis is the time axis.
No search algorithms, no motion vectors, no residual to encode. Memory usage would be huge however.

[Phanton_13]

Is there something like a 3 dimensional wavelet? If so, a scene could be encoded as a 3D wavelet, where the z-axis is the time axis.
No search algorithms, no motion vectors, no residual to encode. Memory usage would be huge however.Yes there are 3D wavelets and even there are 3D DCT, but at the same time this techniques are in a heavy mined patent land.

[akupenguin]

The problem with 3D wavelet is that it sucks. No motion compensation means you have to code all motion as residual, which is much more expensive than mvs.
What you can do is combine motion compensation with a temporal wavelet, i.e. at each wavelet prediction/update step use motion compensated samples from the neighboring frames rather than the original pixels. This is called "MC-lifted wavelet". But it turns out that wide basis vectors like 9/7 aren't very useful, and MC-lifted 5/3 wavelet is very similar in both structure and compression quality to H.264 B-pyramid.

[Manao]

One possibility that is considered for h265 is 3D DCT on consecutive bframes : you compensate the three bframes as usual, but code the residual of all three bframes with a 3D DCT.

It seems promising, but I don't know how it compares to b-pyramids.

[foxyshadis]

Some of the high points that are being considered for inclusion in h265 are :
- 80+ prediction mode just for intra, which greatly increase intra efficiency
- intra frame motion vectors
- free macroblock partitionning for inter : instead of fixed 16x8, 8x16, 8x8... partitions, you can cut a block/macroblock in two by defining a cutting line however you want (not just vertical/horizontal, but any angle too)
- better syntax (for example, better motion vector prediction)

Is there any effort directed toward 16x16 or larger DCT? Or multiscale residual coding (ala jpeg 2000) with DCT or wavelet? Both benefit low-bitrate video (or anime, I suppose) but have little practical use for sharp/noisy high-bitrate, and both would probably be a large speed hit.

Haha, speaking of speed hits, I'd love to see a multiscale intra coder with the scaler based on NNEDI. =p

[MfA]

MC-wavelet's and SVC's claim to fame isn't really performance, but scaleability (which is ultimately useless IMO).

[Manao]

foxyshadis : if I'm not mistaken, 16x16 DCT is being considered too.

As for SVC, it stands better chances than previous attempts at scalability (Mpeg2/4 FGS), because IPTV can profit from it. That it has better chances of being actually used doesn't mean of course it'll be effectively used in the end.

[akupenguin]

MC-wavelet's and SVC's claim to fame isn't really performance, but scaleability (which is ultimately useless IMO).
MC-wavelet gives you temporal scalability, and does it no better than B-pyramid. In fact, pyramid might be better; normal framerates are too low for a temporal lowpass to look good, so you're better off just dropping frames than using a wavelet subband.

[benwaggoner]

MC-wavelet's and SVC's claim to fame isn't really performance, but scaleability (which is ultimately useless IMO).
Why do you say that?

My customer are constantly asking about scalability. It's really hard to stream content reliably and in high quality over the public internet without it. Bandwidth, between users and even mid-session for longer content, is just too variable.

Move Networks has had tremendous success with abc.com and other sites by delivering practical scalability, even though it isn't using any kind of intraband or layered compression.

The real question is if we can do a "FGS" style scalability that doesn't cause such a cumulative reduction in compression efficiency that it's easier to just encode independant bands and switch between them (whcih is what all the real-world systems have used up to now, like Intelligent Streaming and SureStream).

[moogie]

Probably not very new or un-obvious... but i have been playing around with the idea of non-block based compression. i.e. pixel based.

I am currently using "least squares" to generate a equation which approximates the colour of a pixel per frame.

This means that there is an equation for each pixel.

Each pixel can(and probably will) have multiple equations which will be used sequentially. When a pixel is unable to be modelled within certain error bounds then the next equation is used. (the number of frames to use each equation is recorded in the bit stream).

Bit savings can be achieved when multiple frames (per pixel) can be modeled per equation. The actual frames necessary for compression to occur can vary as I can reduce the accuracy of the constants for the equation. i.e. instead of a 32 bit float per constant... 24 bits.

for example

Assuming an 8 bit grey scale video

i have 20 frames of a pixel which can be modeled with given error bounds using an equation consiting of 3 terms (or order 2)... lets say -1230 * x ^ 2 + 0.3315 x - 88

Further analysis has determined that the equation's terms can be encoded in 16 bits without going beyond the error bounds.

thus
8 bits for the equations frame length
+ 2 bits to record how many bytes per equation term.
+ 16 x 3 for the equation.

gives 26 bits for 20 frames. uncompressed it would be 20 x 8 = 160 bits


That example was a little contrived but from my experiments it does compress resaonably well. I doubt that it will have any where near the compression of modern codecs but as my first attempt at a lossy video codec i dont think it is too bad :P

My next step is to encode a colour video using this scheme.

some other possible enhancement ideas:

-previous frame pixel matching (similar to block matching)
-allow equations with different number of terms per video

a nice benefit of this system is that the decoding of the video should be quite fast.

[MfA]

The real question is if we can do a "FGS" style scalability that doesn't cause such a cumulative reduction in compression efficiency that it's easier to just encode independant bands and switch between them (whcih is what all the real-world systems have used up to now, like Intelligent Streaming and SureStream).
Even if you could avoid the reduction in compression efficiency, what are the advantages? A little saving's in storage? Storage is extremely cheap. There has to be a real advantage to bother with scaleable codecs in the first place, not just a lack of disadvantages.

[akupenguin]

a nice benefit of this system is that the decoding of the video should be quite fast.
Are you sure? If each pixel depends on the previous, then you can't use SIMD. So even if you reduce the number of theoretical arithmetic operations compared to MC+DCT, it may still be slower than a block-based codec.

[Manao]

The real question is if we can do a "FGS" style scalability that doesn't cause such a cumulative reduction in compression efficiency that it's easier to just encode independant bands and switch between them (whcih is what all the real-world systems have used up to now, like Intelligent Streaming and SureStream).SVC claims to be as efficient as AVC, while being scalable (I don't know whether scalable here encompass FGS, or if it's something more coarse).
Even if you could avoid the reduction in compression efficiency, what are the advantages?Bandwidth. And generate x streams at difference x bitrates requires x AVC encoders, while only one SVC encoder.

If I take my example, my ISP is providing some TV channels at both low bitrates (1.5mbits h264) and high bitrates (3mbit mpeg2). The purpose is to increase the number of people being able to watch videos. With SVC, they could also maximize the quality each individual receive (because a user has a max bitrate ranging from 1mbit to 22mbit, depending on the lossyness of its connection), and they could do it with only one encoder per channel.

[akupenguin]

And generate x streams at difference x bitrates requires x AVC encoders, while only one SVC encoder.
But one SVC encoder is slower than one AVC encoder. At the very least, you have to run macroblock mode decision (with a limited number of mdoes), dct, and miscellaneous bookkeeping at each layer, plus some motion refinement at each change in spatial resolution. Most of motion estimation can be shared between layers, but that's true of multiple AVC encoders too, if they want to take advantage of it. The only speed difference guaranteed by the change in bitstream format is less time spent in CABAC.

[moogie]

Are you sure? If each pixel depends on the previous, then you can't use SIMD. So even if you reduce the number of theoretical arithmetic operations compared to MC+DCT, it may still be slower than a block-based codec.

true, i should have qualified that statement :)

At the moment the algorthim does not depend on the previous when decoding... the act of decoding is as simple as inputing the current frame count into each pixel's current equation.. e.g. at frame 10 with the equation -2.5 * x^2 + 43 * x + 33, the pixel value would be -2.5 * 10^2 + 43 * 10 + 33 = 213. And at frame 11 the value will be 203.5

[akupenguin]

So you use no spatial prediction at all, and a temporal transform with basis vectors 1, t, t^2, etc. In that case, everything I dissed about 3D wavelet still applies, except that you don't get the benefits of spatial wavelet either.

[moogie]

That was just an example. the optimum number of terms in the equation might be more or less than this example for a given sequence of frames.

I am not familiar with 3-d wavelets so i cannot comment on that but will read up on them.

Yes, at the moment only temporal information is predicted... It is only early days for this video compression algorithm. I have only been developing this idea for a couple of days!

It should be easy to modify the algorithm such that it predicts differences instead of the actual pixel value. This would allow some form of spatial prediction to be utilised as well.

[benwaggoner]

But one SVC encoder is slower than one AVC encoder. At the very least, you have to run macroblock mode decision (with a limited number of mdoes), dct, and miscellaneous bookkeeping at each layer, plus some motion refinement at each change in spatial resolution. Most of motion estimation can be shared between layers, but that's true of multiple AVC encoders too, if they want to take advantage of it. The only speed difference guaranteed by the change in bitstream format is less time spent in CABAC.
Beyond encoding seperate streams, layered video lets you proritize deliver of base streams hgher, so that you can deliver those in advance.

Imagine you're doing SVC with four layers for a real-time VOD playback.

You burst ahead the base layer 60 seconds, the second layer 30 seconds, the third 15, and the fourth 10. If the user gets a change in banwidth and can only receive the base layer, that's buffered ahead the most, so they don't have any "buffering" message for stream switching. Also, if they're only getting say the bottom two layers and they get more bandwidth, they just need to start pulling down layer 3, and can keep what they've already cached.

Traditional stream-switching is painful, since often by the time you know you need to switch, you don't have enough time to get enough of the new stream to avoid a disruption in playback.

I'd love to see this be workable in practice.

[Birdy1]

Another idea:
Macroblocks are translated (geometric operation) from one frame to the other using a motion vector.
There are a lot more geometric operations you can do to a macro block, like rotate, scale, skew, warp, change brightness. This way you can get a better match from frame to frame, resulting is less residual.

[Dark Shikari]

Another idea:
Macroblocks are translated (geometric operation) from one frame to the other using a motion vector.
There are a lot more geometric operations you can do to a macro block, like rotate, scale, skew, warp, change brightness. This way you can get a better match from frame to frame, resulting is less residual.Already been done. Nokia MVC (a failed proposal codec for the H.264 standard) used an affine (linear) transformation, which thus would have allowed skewing. Changing of brightness can also sort of be done with existing H.264 through weighted prediction.

Rotate is problematic because it can't really be SIMD'd, so its a lot slower. Same problem with generic non-linear warping.

[MfA]

Rotate is problematic because it can't really be SIMD'd, so its a lot slower.
Modern budget video cards could do it without breaking a sweat (even with the interpolation inside the shader to make it work exactly as intended).

[akupenguin]

And you prefer the latency of sending a task to the video card and back for each macroblock? Or you plan to implement only DXVA/equivalent, with no software decoder at all? "Sorry, you don't have a GeForce 8xxx, you can't play this video."

[MfA]

And you prefer the latency of sending a task to the video card and back for each macroblock?
Prefer it over what? (Of course you would not want to do this stuff at that kind of granularity, only send parameters for entire slices/frames and read back the same.)

[God Radio]

But what if thanks to increased cpu power you can?

We use prediction to drop frames and enable compression.

The problem is that the more compression and prediction requires more and more cpu power, hence X264 and H264 usage is very cpu hungry versus mpeg-2.

So we can get even more compression by doing a prediction of two frames(two seconds) instead of a single frame representing a second.

But.

To enable this level of error prediction means the cpu usage is going to want an 8 core cpu like the PS3 and maybe even twice that.( if we go with five to ten second predictions)

As far as I know we can get better compression, better error correction/detection/prediction but its at the cost of better and better hardware.

I know nothing therefore please feel free to correct me on this.

[akupenguin]

So what would you do to two frames that would compress them better than predicting one at a time? There certainly are areas that would benefit from increases in processing power allowing more complex algorithms (e.g. OBMC, arbitrary motion shapes, non-translational MC), but higher order temporal prediction isn't one of them. As far as I know, temporal transforms are not limited by processing power, but rather by the fact that no one has yet come up with an idea fundamentally better than P/B frames.

[God Radio]

One frame gets a regular X264 or H264 job task.

The second frame gets turned into a wireframe.(eventually the whole movie gets the wireframe for transmission).

This cuts the required bandwith by 1/2.

The fun part is turning that wireframe back into a regular scene since it does take considerable cpu power to do so.(i.e. game CGI when running off the in game engine instead of pre-rendred).

I expect someone sooner or later to try this with either a cartoon or anime to cut bandwith cost when distributing programing.

With better cpu power available there is no real reason to not be able to turn an entire cartoon, anime and sooner or later CGI movies like Apple-Seed into wire frames to be de-compressed and skinned(rendered) at the destination point.

Since most movies these days begin life as wireframes before final ok to be rendered into the final product that we see.

It sounds doable to me but then I barely know what end to point the movie camera at when we are filming.

[MfA]

You are still just doing motion compensation, if compensating every second frame with it works well compensating every frame with it works even better.

[God Radio]

Think of it like building a house where you predict where the next line of bricks is going but you still have to set a flag position for every line of bricks, every door, window, etc.

The simple way is just have the entire blueprint with no set position flags needed.

The wireframe is the blueprint.
The render is the final product working from the wireframe.
The color palette is just a tiny data stream that tells the render engine what colors go where the same as sending a multicolor fax where you only send the color positions and color pallette as a tiny data stream.

Pre-rendered data( even compressed) uses a huge amount of space versus on the fly renders.

The downside is that the more complex or realistic the render the more cpu power is required.

So we make do with prediction but soon we will begin to try the on the fly render for at least some cartoons.

Have to go.

Thanks for the interesting conversation.

[nm]

Your idea sounds like Machinima (http://en.wikipedia.org/wiki/Machinima), which allows the scenes to be rendered at the viewer's computer, although large-scale distribution is usually done with video files. If the game/video engine and the data files are distributed instead of the resulting video file, complex scenes may still require quite large amounts of texture data. On the other hand, output pixel resolution is only limited by the viewer's equipment and the game-based medium allows varying levels of viewer interaction.

[akupenguin]

One frame gets a regular X264 or H264 job task.
The second frame gets turned into a wireframe.(eventually the whole movie gets the wireframe for transmission).
This cuts the required bandwith by 1/2.
Even assuming you can extract the models and textures entirely from the remaining frames with no sideband data, and even assuming motion can be perfectly interpolated, that still only cuts the bitrate by about 20%, because you cut B-frames and keep I/P-frames. So this line of extrapolation doesn't go anywhere. Lets try from the other end:
How much space does it take to store the models, textures, and motion of a modern 3D CGI movie? Well, that wouldn't be very helpful either, as those probably don't involve any compression, and are designed to render at very high resolution. How much space does it take to store the models, textures, and motion of a modern 3D CGI movie, if models are subsampled and textures lossily compressed until the resulting movie is similar precision to a decent 1080p h264? Furthermore, there's a large difference between taking an existing movie and compressing it, vs designing the movie with compression in mind a la .kkrieger

[Leak]

Your idea sounds like Machinima (http://en.wikipedia.org/wiki/Machinima), which allows the scenes to be rendered at the viewer's computer, although large-scale distribution is usually done with video files.
Made me think more of demos, actually - but Debris (http://www.pouet.net/prod.php?which=30244) would probably still take the cake at 177kB download vs. 197MB hi-res video... :D

np: Battles - Atlas (Mirrored)