Re: JPEG press release

This discussion reminds me of the argument between
'gradualism' and 'punctured equilibrium' (I think
that's the phrase??) in the study of evolution and the
creation of species.  I think the truth is that both
things happen: there are gradual changes, which
provide small, incremental, measurable improvements;
and there are (very occasionally) quantum leaps,
changes in paradigm that provide a massive, unexpected
increase in performance on some scale (Andy Grove said
that these sorts of disruptive inventions cause
'inflection points', where opportunities arise to make
decisions with increased risks and rewards).

The art and science of video compression is a good
example of a field where this sort of process is
ongoing.  Generating better compression algorithms is
basically a massive global optimization problem within
the space of all possible codecs.  There are a number
of complex tradeoffs, with nonlinear relationships --
the classic NP problem, where there is no closed-form
solution possible.  The only option is to try things,
and see if they work. 

In general, the things that work today, with minor
variations, are going to be the most fertile ground
for improvements, if you're not looking for a major
leap.  This is essentially a 'local optimization'
within the search space of possible algorithms.  Think
of 'algorithm space' as a density function on a
multi-dimensional space (or an N-dimensional surface
in N+1 dimensions).  Making small changes to our
algorithm is analogous to moving a small distance on
this surface.  To make improvements, we sample a few
points near our present location, determining a
direction in which our slope leads to a 'higher point'
on the hill (ie a better algorithm).  Then we move in
this direction until we see a decrease (or leveling
off) in performance, in which case we reset our
direction.  Eventually, we find a point where every
direction appears to cause a decrease in performance;
we are now on top of a local hill -- a local optimum
in our parameter space (the space of all possible
compression algorithms).  If, on the other hand, we
move to a location relatively far away from our
present hilltop, the overwhelming probability is that
we will end up in a spot at a lower elevation than
where we started, since we presumably started at a
location considerably higher than average. 
Consequently, novel techniques, in their initial form,
are almost always less impressive than the highly
tuned versions of existing techniques.  

Video compression is a perfect example of a search
space where a particular local optimum has been
extensively searched.  There will continue to be
incremental improvements, but inevitably there will
come a point of diminishing returns.  Without
techniques that go further than the pixel/block
paradigm, there is only so much improvement possible. 
The next big leap in this area will come from a more
'semantic' approach to video analysis, including
things like scene description, object segmentation (as
opposed to object recognition, though that may
follow), reverse-3D extrapolation, and so on.  A
possible interim approach might involve motion fields
and 'texture-based' compression, that moves away from
the rigid rectilinear block methods; but it is not
clear that such an algorithm will compete effectively
with existing optimized algorithms, especially
concerning encoder complexity.  From a marketing
perspective, if a new algorithm takes many orders of
magnitude more complexity on compression, it better be
a 3:1 or more improvement over the best existing
methods.  Anything less will simply not be useful
enough to achieve wide adoption.

I'm not sure what the central goal of Tarkin is, or
how it relates to VP3/Theora work; this is a
logistical issue.  In any case, I think there is room
for two independent threads -- one more research
oriented, similar to what Tarkin is already doing, and
another dedicated to practical improvements to the
VP3/Theora codebase.  Obviously, anyone with an
interest can be involved in both groups.  Eventually,
if the research group comes up with something truly
impressive, the VP3 group can take it up as a
potential improvement in future releases.

One thing I can say for sure after many years in this
industry -- any algorithm that is not undergoing
constant improvements is going to be dead in the water
in a relatively short time.

--- Matthias Fleischer
<[email protected]> wrote:
> > But we already have VP3 that basically does that.
> Besides, this 
> > seems hardly satisfying. I'm still all for aiming
> high, and 
> > replacing things in current encoders with similar
> non-patented 
> > algorithms isn't going to give us any substantial
> gains, if at all.
> 
> But that's basically what vorbis did with audio,
> right?
> And if some of MPEGs well known weaknesses can be
> ironed out on the way then that's a win.
> Take for example those blocky MPEG artifacts -
> everybody knows where they come from and how
> they could be avoided - if you chose to get
> incompatible
> to existing MPEG hardware.
> 
> 
> --- >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
> '[email protected]'
> containing only the word 'unsubscribe' in the body. 
> No subject is needed.
> Unsubscribe messages sent to the list will be
ignored/filtered.


__________________________________________________
Do You Yahoo!?
Yahoo! Health - Feel better, live better
http://health.yahoo.com

--- >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 '[email protected]'
containing only the word 'unsubscribe' in the body.  No subject is needed.
Unsubscribe messages sent to the list will be ignored/filtered.