[vorbis-dev] video compression using textured polygons?

[Lourens Veen]

> Weird, so was I :) and I'm not just saying that to sound
> smart... actually I have evidence saying that I thought about this
> Thursday at 10:05 AM EST, but that's very much besides the point.

You beat me to it then. I was thinking this Friday at 7:30 PM CET, so
you were thinking about it 27 hours and 25 minutes earlier :).
 
> The problem here is of course the encoder. Do you know any algorithms
> that could possibly come close to doing this in anything near
> real-time? That's what discourages me from putting it in the core of a
> video spec (though you could have one polygon filling the entire
> screen and the texture changing, but that would not compress well in
> the proposed scheme).

Well, I haven't done any research on it, so I don't even know any
algorithms that could do it at all. But ofcourse I've been thinking
about it some more. First of all, doing this with triangles instead of
with polygons makes things a bit easier without loss of generality. Then
we'd have to divide the image into triangles. Finding edges should be
possible, by looking at the gradients in the image. However, how to
organise these into triangles? The only algorithm I know of (but again I
haven't done any research on it) that comes anywhere near that is
Delauney triangulation, which makes triangles out of a set of vertices.

Then if we have a bunch of triangles, extract textures and do fractal
compression using those. A spiral search pattern in 3D would do quite
well (in fact the first triangle is very likely to match, if you take
the triangle that is at the same location in the previous frame as the
first one in your search). If there's a match, use it, if not, add this
texture to the search space and store it in the stream.

Another possibility would be to triangulate the triangle into two or
more smaller triangles, and try again (limited ofcourse, so that we
don't get one-pixel triangles) in case no match can be found.
 
> The textures themselves could change, but in relatively predictable
> ways. For example, consider (as Sean Lynch was talking to me about) a
> road with cars passing by. Every time a car moves, a conventional
> video codec would have to retransmit the road underneath. A
> polygon- (or generic object) based codec could realize that the road
> is now mostly the same as it was before the car passed, and just tell
> the player that object "car" moved, and (if it doesn't already know)
> polygon "road"'s texture has changed to <what the road was underneath>

Yeah. Or if the road has a reasonably constant texture it could use a
texture previously gathered from a different piece of road, and paste it
onto a new polygon.
 
> I don't know how MPEG4 works here, but I will say that a simple
> polygon would not cut it in all cases. The encoder will probably not
> be able to handle it, but the codec should provide for entirely
> arbitrary 3d worlds (awesome for recording a quake level to show your
> friends :), though in a way that doesn't overly harm the compressino
> for the rest of the encoder. Same for any other encoder extensions. I
> will be playing with this sort of stuff soon in a prototype
> renderer-based player (encode by hand for a while) and keep you posted
> on how things work out.

Okay, cool. I'm going to have a go at the edge finding and
triangulation.
 
> Encoder issues... the player for this would be absurdly simple on a
> system with 3d accel (or a port of Mesa).

True, but if you can't write an encoder there's not much use to the
codec is there? Unless you manage to get an infinite amount of monkeys
to keep creating random files and wait until something that resembles
the input file close enough rolls out...:)
 
> Always happy to talk to smart people.

Yeah, this mailinglist is good :)

Lourens

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