[vorbis-dev] More Ogg Video discussion

[Kenneth Arnold]

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.
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).

> 
> >   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). 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.

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. 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 ;)

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

> 
> 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 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.

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.

> 
> >   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?

> >   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. 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.

> >   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
(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.

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... ?

> 
> > * 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 :)

> 
> >   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. Among those
things is the varying algorithms by region, residual-based codes,
backreferences, and all that other sweet stuff. But data should be very
componentized; seperable as much as possible while not impeding the ability
to remove redundancy. Maybe wavelet-lets? :)

> 
> > * 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, if any of
that still exists in this world.

Kenneth

--- >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.