[vorbis-dev] More Ogg Video discussion

[Jelle Foks]

Kenneth Arnold wrote:
> 
> On Thu, Sep 14, 2000 at 02:30:17PM +0200, Jelle Foks wrote:
> > See my in-line comments.
> 
> Ditto.
>
> > Kenneth Arnold wrote:
> > >
> > > Smack my curiosity, but I encoded some songs in Vorbis mode 2 and tried
> > > to be able to distinguish the difference between that and the uncompressed
> > > WAVs. (*smacks self*) but here's what I noted:
> > >
> > > It's actually kind of hard to tell the difference :) (and I consider myself
> > > to have a decent set of ears, though not anywhere near the best)
> > >
> > > I got my accuracy to about 90%, but I couldn't figure out what it was. Finally
> > > I figured out that it was some of the high-range in a few spots that hit with
> > > less -- brillience is the word that comes to mind -- than the uncompressed.
> > > Yeah this is 128k so what should I really expect, and compressed against
> > > uncompressed so almost no fault at all found here, but could the psycoacoustic
> > > model be tuned any? Maybe if somebody could assemble a "test kit" that a
> > > lot of people could use and try to tune the model to what they thought
> > > sounded best, then the results could be averaged? Or do we have it on higher
> > > authority that the psycoacoustics are the best they could be? (I am reminded
> > > of Linus Torvalds' announcement for 2.4.0-test2 on l-k back when I was
> > > subscribed.)
> > >
> > > Wow. Not bad.
> > >
> > > Now gotta try against MP3. Dang, does that mean I have to grab notlame or
> > > bladeenc? Darn... I didn't even install them when I reinstalled last,
> > > because it seems that I have my audio compression needs taken care of.
> > >
> > > Back to developer mode:
> > >
> > > Thanks, Ralph, for the Ogg todo sent a while ago. I've only now got to really
> > > studying it and looking at what to do. Looks like video is it. So a couple
> > > questions for the list:
> > >
> > > 1. Where's the Tarkin source anyway?
> > >
> > > 2. I am aware that Tarkin uses wavelets. MPEG uses object detection and
> > > motion estimation. What other methods are out there? Does anybody know
> > > of any new, cool methods for compressing video? Or, failing that, does
> > > anybody know [of] anyone who does?
> > >
> > > 3. I have looked over the MPEG document Marshall said to look over a while
> > > ago (about varying levels of detail). I think that's a good idea (in fact
> > > that was a goal even before I read that). See what you all think about my
> > > personal codec wishlist (from a starting-from-scratch viewpoint, even though
> > > it probably won't work out that easily):
> > >
> > > * Three levels: packet, frame, and field. Packet holds all the stuff that
> > >   should naturally go together and is otherwise worthless when split up.
> > >   (I'm thinking streaming here). Field is collection of packets that
> > >   describes part of a frame. It may pull information from a lot of sources,
> > >   e.g., raw image data, data from frames earlier / later (with an arbitrarily
> > >   adjustable window), "scratch" area, whatever. It should have the capability
> > >   to embody vector graphics, arbitrary transforms, effects, etc. even if the
> > >   encoder can't pick them out from a source video (if it could, that'd be
> > >   great, but that gets very compex). Maybe field == packet; I need to think
> > >   some more about that. But by "part of a frame", I mean a level of detail
> > >   as opposed to a region (although region might be useful also). Object
> > >   descriptions are hierarchical in importance by nature; the codec should
> > >   take advantage of this. Coding should be done residually, i.e., take as
> > >   much information about the frame as can be embodied relatively simply, and
> > >   repeat with what's left over. The amount of complexity per independent
> > >   block should be adjustable over a wide range. Each block iteration
> > >   (hierarchical level) could be assigned a priority, and when streaming, the
> > >   transport could choose to only send the blocks above priority x. Different
> > >   methods could be used to formulate these blocks, possibly even different
> > >   methods for different blocks describing the same area. This would allow
> > >   motion estimation to be used for entire objects, and e.g. wavelets for
> > >   details about the object. The definitions and implementations of the
> > >   residue and coding areas are left for later, to allow for more than
> > >   enough flexibility (I hope).
> > > * Every frame should be able to reference back to frames before it, i.e.,
> > >   no MPEG's I frames (except maybe at the beginning of the stream).
> >
> > If there are too many dependencies upon 'previous data', such as what
> > happens when you send/store I-type image data only very occasionally,
> > then you will have very slow or difficult seeking, channel zapping, etc.
> 
> This is why such things should be adjustable through a wide range.

True.

> Depending on the quality of the algorithm and tuning that can be done,
> the default should behave much like conventional streaming. But leave
> in the design the ability to incorporate more diff data, as is suited
> for the specific application (e.g., with a DVD, you can read data off
> pretty fast and get back to a far-away I-type frame without much delay,
> but an NLE setup could reprocess the data (the format should be structured
> to make this easy) so that almost every frame is I-type).

Getting back to the last I-type frame is not enough if you have
differential frames following it that can be reference frames themselves
(P-type). In that case, seeking to a random point in the video stream
requires seeking to the previous I-type frame plus decoding of all
P-type differential frames after that until the desired seek
destination.

But of course, in some applications, such seeks may be acceptable. I
agree that for some applications, a couple of seconds delay when seeking
may not be a problem for the user.

Even if you want maximum compression with best quality without caring
about seeking time or transmission errors, there is an optimal balance
for using I-frames, P-frames, and B-frames. Just sending as few as
possible I-frames (many bits) and as much as possible B-frames (few
bits) doesn't result in the best compression.

When B-type frames are used, the seeking problem disappears, but you get
stuck with more difference entropy with the reference frames because the
reference images were taken too long ago and don't resemble the current
images anymore. If you wait long enough, then each B-type frame contains
the entropy for two images, one to cancel out the reference image, and
one to encode the new image (in which case it's often better to use
I-type macroblocks in the B-type frame). That's why they're using P-type
frames. The problem of cumulative errors in P-type frames is handled by
requiring regular transmission of I-type image data (does not have to be
an entire frame, as long as each macroblock is transmitted as I-type at
least once every 230 or something frames). If supported by the decoder,
and with a well implemented encoder, the effect of cumulative errors can
also be removed (in the more recent standards) by having the the encoder
define which approximation it is using for the IDCT for the reference
frame reconstruction, so that the decoder can optionally use exactly the
same method. The cost of that is that the decoders must support every
possible IDCT approximation (there are a lot), and/or limiting the
encoders and decoders to one 'golden standard IDCT approximation', which
limits the degrees of freedom for cost-effective (hardware)
implementations.

> >
> > >   Okay,
> > >   so maybe there should be I-frames, but use them more carefully.
> >
> > If 3d transforms are used, then there is not much need for something
> > like a I/P/B-type frame concept, because you're looking at muti-frame
> > data coefficients in the transformed domain. Here, the depth in time of
> > the 3d transform is similar to the 'I-frame frequency' in 2d-transform
> > coding.
> 
> Yup. But unless I've missed some very important development, no algorithm
> is yet perfect. A 3D transform may (hypothetically here) not be able to
> capture some specific sort of data as well as an I/P (and maybe B). 

I could be wrong of course but I believe the largest reason why 3D
transforms haven't been used often yet is cost and coding delay. A 3d
transform requires both the encoder and decoder to have sufficient RAM
for all decompressed frames in the 3d transform block (maybe not in the
decoder if some sort of progressive reverse transform is possible, which
I expect to always be at the cost of additional computations), and
possibly buffering of the transform coefficients because of the need of
coefficient re-ordering for efficient entropy coding. All this buffered
data costs money in hardware, and results in delay in the transmission
path. If you have to process N frames before you can finish the N-frame
3d transform, then I think you'll have to do magic to get your
encoder+decoder delay below (or even at) N frames (because the last
transmitted bit may contain data about the first frame in the block).

The decorrelating effect of a well chosen transform has already proven
to beat predictive coding in the two spatial dimensions, so why not in
time? The main question that remains is: Can we afford the RAM and can
we live with the latency or find a magic trick to reduce it?

> Perhaps
> the best thing to do would be to allow for those sorts of "legacy"-type
> codes, but optimize the encoder for whatever works better most of the time.
> Or better, loosen the I/P concept to not just raw video data, but perhaps
> parameters for the 3d transforms or the left-over data after doing the
> 3D transforms, or various other metadata, whatever can be thought of.

Agreed, at the 3d-block boundaries, there may still be some correlation
between the 3d transform blocks that could be reduced with some form of
prediction. I guess that all depends on the chosen 3d block size, and
the duration of the scenes (how long do image object properties remain
intact/predicatble?).

> Intersperce a brief general note here: You all likely know a lot more than
> me about how video compression works. But if we're going to get a DVD on a
> ZIP disk (MPEG-4 has conveniently upped the ante ;), it is obviously necessary
> to try something new, perhaps seemingly stupid, or totally random. 

"Hey, people will never fly, Mr Wright, go tell that to your brother."
;-))

But there's still room for some sceptisicm and not unwise to look at
what is currently percieved as the limit of what is possible, right?

According to Shannon, "Mr Information", we only need to encode the
information (entropy), and how much real information does a feature film
or television program really have? I'd say 50,000 pages of text
(=100mbyte?) may actually be enough to describe two hours of video in
detail (how long is the movie script?). The question is how, and how
long does the decoder need to reconstruct the pixels, and how much are
the encoder and decoder going to cost?

> But
> whatever results should have as much flexibility and power as possible, such
> that you can just throw in an encoder on the default settings and it'll work
> and maybe adapt on its own, but that you can endlessly tweak it so it is
> optimized for the specific use. It would be cooler that way ;)

Agreed.

> Go ahead, argue with me. You're likely right, but that's something I'll
> have to deal with later.

I'm not saying you're wrong, I'm just trying to shed some light on
issues you may be overlooking.

> >
> > the I-P-B frame types are a direct result of the current 2d transform
> > coding methods using predicive coding in the time domain. Back in the
> > old days, image compression method even did predictive coding in the
> > pixel domain, but when they stepped over towards transform coding, then
> > there was no need to keep doing that. The only place where prediction
> > remains is on the boundaries of the transforms: in 8x8 DCT coding (MPEG,
> > JPEG, H.26x), this is at the DC DCT coefficients plus in the time
> > domain.  In NxMxQ 3d-wavelet coding, prediction will only help at the
> > edges of the pixels and the group of frames that are transformed as a
> > whole.
> >
> > >   Possibly
> > >   a lossless compression could be made from them...
> >
> > Lossless compression can be made from any compression method where the
> > residual entropy is sufficiently low. Lossless compression doesn't
> > require I-frames.
> 
> Wrong thought connection. That's why I normally don't write after 10:00 PM.
> 
> >
> > >   but back to the main
> > >   issue here: a typical viewer will be watching the video for at least 100
> > >   megabits before [s]he even starts to worry about quality as opposed to
> > >   content.
> >
> > Unless the viewer is receiving the stream over a 56k POTS modem or
> > similar. Even on 512kbit ADSL that is still more than 3 minutes.
> 
> Bad number. Maybe the point was (can't remember exactly) to allow
> adjustment to whatever situation the streamer encounters. Yes, 512kbit ADSL
> should be able to get whatever quality it can, but a 15-20 Mb DTV should
> also should be able to get what it needs.  In that case, 100 Mb is 5-7 sec.,
> still off, but until the viewer has made the decision to keep watching a
> program, the video doesn't need to look perfect. If [s]he takes a long time
> in deciding, the quality should be improving anyway.
> 
> Clearer explanation: when viewer first starts receiving a stream, quality
> doesn't really matter; the video could just show rough, blocky object outlines
> for a couple of frames until it gets more data; 

As a sort of fade-in effect? sounds good.

> as the viewer becomes more
> preceptive to the details of the video, the quality should be improving at
> about the same rate as more of the dependent I-type data is sent, but spread
> out over potentially up to even 2 sec. worth of data before it is noticed.
> Better than waiting for the I-frame (MPEG context) to display anything.

I doubt whether that can be done efficiently. The redundant transmission
of I-type data may not be able to keep up with reference frame changes
when P-type frames are used. So, either refrain from using P-frames as
well, accepting the B-type frame problems of gradually increasing
difference entropy, or increase the bit-rate of the redundant data. I
wonder whether the breakeven point here is anywhere better than simply
increasing the I-frame frequency. The latter at least is a lot less
complex (I mean implementation complexity here).

> Try again: the player should be smart enough to display something useful with
> only the diff data, however this gets used. The codec system should be
> structured so that this is easy. I suppose a real purpose for this will become
> more evident with further development.

Use scalable bitstreams where the base layer (of lower resolution, image
quality, and frame rate) has a high frequency of I-type frames and give
the enhancement layers the much lower frequency of I-type frames. That
seems to me the obvious way to do get that effect.

> >
> > >   So I-frames can be very sparse.
> >
> > I'de hate to be able to seek only to 3-minute or more intervals or wait
> > up to three minutes after each seek because the decoder needs to
> > reconstruct sufficient 'history'. Also I'd hate to be able to zap
> > through channels at only one channel per three minutes.
> 
> Maybe, but would you really complain that much if the video wasn't
> _perfect_ for 3 minutes, as an optional tradeoff for the ability to get
> better quality after that wait than without it?

Sometimes I would, sometimes I wouldn't. When looking at a good movie, I
won't be seeking much anyway, but when fast-forwarding through boring
scenes of a recorder television program, I'd like to keep the high
quality. Then again, for fast-forwarding is easier to fix that problem
than for seeking. When channel surfing, I'll probably accept a lower
quality, as long as I quickly get sound and enough image to recognize
what they're broadcasting.

Yes this is of course subjective, and application dependent, so the best
way to deal with it is to keep it a flexible parameter, so that the
application or user can make the tradeoff.

> > >   The tradeoff is more redundancy in the diff frames.
> >
> > Not completely. In your proposal all difference frames are changing the
> > reference frames, because each decompressed difference frame can be a
> > reference frame. In that case you have the problem of accumulated
> > errors. Especially in transform coding, where various implementations of
> > decoders may not be bit-true equal (due to various decoding
> > environments: processors, hardware (read: differences in rounding,
> > optimizations, efficiency and available data types)). After each
> > difference frame that is used as reference frame, the reference
> > available decoder deviates a bit more from the reference available in
> > the encoder, resulting in increased differences in the reconstructed
> > images.
> 
> Consider my proposal to be missing in some major areas. As for errors, that's
> where both the redundancy and the adjustment come in. If the situation is
> more prone to errors, you first ask whether or not you really want to be
> working with video in that situation in the first place, and then you tell
> the encoder to increase the data redundancy, such that the errored data
> eventually gets replaced by correct data. 

I did not mean about transmission errors here, I meant that the IDCT (or
IWT) transform in the decoder can be implemented in different ways that
each give slightly different results. Two different implementations may
have the same precision (calculated as MSE with the full precision
(slow) IDCT), but different exact output. If you use fixed-point, which
is cheapest in hardware, then changing the order or structure of the
calculations, then you get different quantization (roundoff errors).
Also, when the algorithm calls for specific functions, such as the
logarithm, then it's very expensive to use full precision logarithms
(costs many computational iterations to calculate), so it's very nice to
be able to use an approximation function for the logarithm, of which
many variations are possible as well, each of the resulting in slightly
different results. Some hardware may also do fixed-point rounding a bit
different that other hardware (see for example "MAD", Rob Leslie's
fixed-point implementation of MPEG1/2 audio decoding for various
fixed-point platforms).

> Perhaps the decoder could employ
> a trust system, whereby it would track how many lossy processing steps it
> has gone through and if unicast, ask the server to send the data again, or
> in multicast, wait for new data, which could itself need processing before
> it becomes useful, so compare trust values to know which to use and which
> to throw away.

I think it's best up to the encoder to keep track of error accumulation.
In unicast applications you can use a negotiation sequency to see if the
encoder and decoder have matching implementations, or at least find the
implementations with the best match. Then, the encoder will know when
the cumulative errors become too large. In a broadcast situation, the
encoder has to assume the worst match within spec, or some viewer with
an full spec decoder may still be stuck with a bad video quality.

In a multicast situation, it may be possible to use scalable bitstreams
here as well, where each receiver subscribes to the base layer, plus the
enhancement layer that best matches its decoder implementation plus
bandwidth budget. Of course, this means that the encoder needs to encode
the video with multiple implementation variants. In one-to-many
transmission situations, the encoder cost is less of an issue anyway.

> > >   Each diff frame should transmit the diff, plus some
> > >   data that the viewer should know if it's been watching since the last
> > >   I-frame.
> > >   This would allow streaming to be able to take advantage of scene
> > >   similarity without worrying too much about the consequences of lost data.
> > >   Possibly the redundant data could have a temporal component attached also,
> > >   so when the video is saved to disk after streaming, it could be moved to
> > >   the proper place where it should have been first introduced and then
> > >   removed as much as possible to keep redundancy to a minimum on a fixed
> > >   medium (key point: the stream is not the compressed video. They work together
> > >   but both can be modified to hold the same or similar data in a more optimal
> > >   manner). Another key point: there's a lot you can tune here (amount of
> > >   redundant data transmitted, frequency of I-frames, etc.). More flexibilty.
> > > * VBR of course. But since streaming often works best when bitrate is constant
> > >   (TCP windows, if streaming over TCP), allow the redundant data to be filled
> > >   in whenever the data size is otherwise small.
> >
> > If the bitstream can occasionally have a higher bit-rate than the
> > transmission medium, this results in latency (due to buffering).
> >
> > Dropping frames is not a good solution here, because that is nothing
> > more than very bluntly reducing the VBR ceiling, which can better be
> > done inside the coding algorithm.
> 
> In almost all cases, the streamer should have knowledge of the approximate
> bit-rate ceiling for the medium, at least on average. Even a multicast
> streamer could put out different streams for differently connected viewers

That's where H.26x and MPEG use scalable bitstreams, with a base layer
of low bit-rate and one or more enhancement layers for better video
quality for receivers that can handle the bit-rate.

> (and the alteration should be easy because the data should already be
> split and prioritized, and varying output bitrate should involve little more
> than just cutting the low-priority (i.e., fine detail) data and adding the
> appropriate amount of redundant data, difference coding, etc. that the
> format should also make easy.
> 
> The latency thus needs to be adjustable also. In some situations it matters,
> in many it doesn't. The codec shouldn't be encumbered by dealing with both
> the same way.
> 
> For the dropping frames, that was almost _exactly_ why I had the frame-
> independence idea. That way, no matter how important the data in that frame
> was, future frames should be able to use it anyway. Also, instead of just
> dropping the frame, if the decoder has a buffer of sufficient size (recalling
> Real's prebuffering of even an audio stream over 33.6 connection... horrors!
> but it worked quite well...), the frame could be interpolated from the ones
> before and after, and if the redundant data comes in within the buffer window,
> it could use that to further reconstruct the frame.

Interpolation is not a way to recover lost information, just a method to
occasionally reduce percieved distortion. For example, interpolation
does not work at all on scene change boundaries.

> Hmmm... the idea just popped into my head of a variable _frame_ rate...
> seems interesting to me as an option; what do you think? What could be done
> with it? Removing constraints one at a time... ?

I think both H.26x and MPEG allow for 'dropped frames' as an encoder
decision, which is a rough quantization of variable frame rate, because
the encoder can regulate the frame rate that way. I think it's mostly a
very rough measure to deal with instantaneous bit-rate increases, but it
may of course also be applied as very high compression where two
sequential frames have no difference at all.

Maybe there is a solution in-between, where the encoder can tell the
decoder: "I'm skipping this frame, and if you want to reconstruct it I
suggest predicting the motion yourself if you can and extrapolating" or
"don't try to predict motion here, just repeat the last frame" or "just
extrapolate without motion estimation". Note that skipped-frame
_inter_polation in the decoder introduces another 40ms (1 frame) delay
in the decoder.

> >
> > > * Scratch pad to save previous data. e.g. if scene is switching between two
> > >   talking heads, should save data associated with one when switching to other.
> >
> > AFAIK, MPEG4 solves that by separating object descriptions and image
> > structure. In other words: in MPEG4, not all known and/or previously
> > known objects must be displayed at all times. This allows an encoder to
> > 'keep' some objects across scene switches.
> 
> But how does it deal with picking up the stream in the middle? Need to know
> because I/we need to do better :)

AFAIK: with I-type descriptions of the objects.

> >
> > >   Key point is that maybe viewer didn't catch that old data; maybe send it
> > >   before stream starts playing, or put it in the redundant frames. First
> > >   sounds nice if you're not multicasting; second is more suited for
> > >   broadcasting.
> >
> > It's all dependant on the application, many applications won't accept
> > the latency and other problems you get if you trade everything off
> > against maximum compression. The Ogg Video codec should be able to
> > produce the perfect stream for each application, but not every Ogg Video
> > stream has to be perfect for each application. Hence, keep all that
> > parametrizable, and keep as much of the details outside of the standard
> > and codec, let the application decide which parameters tickle it's
> > sweetspot. I think a video stream format is best kept simple: KISS (keep
> > it simple, stupid).
> 
> On the dot; exactly what is first on my mind. But there are certain things
> needed in the codec to allow for maximum parameterization. So the KISS part
> becomes the framework under which you should be able to throw in just about
> anything imaginable that the viewer could sanely deal with. 

Agreed.

> Among those
> things is the varying algorithms by region, residual-based codes,
> backreferences, and all that other sweet stuff. 

Yes, definitely.

> But data should be very
> componentized; seperable as much as possible while not impeding the ability
> to remove redundancy. Maybe wavelet-lets? :)

Just be careful that the flexibility may come at a cost: complex
standards take a long time before there are many applications for it,
are error-prone due to differences in interpretation of 'how it was
meant', and may create too much overhead in the bitstream, software code
size, or hardware controller size.

Sometimes trying to change a working algorithm to remove it's
disadvantages may also remove it's advantages. I all Ogg Video people
(we, you, them) should just try it out and see what we can do.

> >
> > > * Assume viewer knows everything about the stream you sent, then either the
> > >   viewer could ask (unicast better again) or the streamer could just resend
> > >   anyway (multicast) the missing data.
> > >
> > > Spewing a lot to myself above, and I really didn't mean to spew that much,
> > > but chew on it and tell me what you think. That's the product of probably
> > > about 15 minutes of mostly continuous thought that is very likely disjointed
> > > and missing some key information still locked somewhere in my head, so don't
> > > take it as written in anything but sand sprinkled in tide pools. It's also
> > > 11:00 PM local time, so I may have gone insane and not known about it.
> > >
> > > The bit of judgement in me that hasn't gone to sleep yet is telling me that
> > > this is a good place to stop.
> > >
> > > Kenneth
> > >
> > > PS - I'm going to really like reading that when I'm more awake. It'll be fun.
> 
> It was -- and I came up with a couple more ideas. Throw as much back as
> you can; discussion is good. And again, don't accept my ideas as solid,
> right, or wrong, but more as (hopefully) a source for inspiration, 

Ditto!

> if any of
> that still exists in this world.

I sure hope so!

> Kenneth

Cya,
Jelle

--- >8 ----
List archives:  http://www.xiph.org/archives/
Ogg project homepage: http://www.xiph.org/ogg/
To unsubscribe from this list, send a message to 'vorbis-dev-request at xiph.org'
containing only the word 'unsubscribe' in the body.  No subject is needed.
Unsubscribe messages sent to the list will be ignored/filtered.