[vorbis-dev] Video compression, edge detection, and gcc warnings

Lourens Veen jsr at dds.nl
Wed Jan 10 11:28:07 PST 2001

<WARNING: Long message ahead>

Well, I have actually done something the past 1 1/2 week. I've created a
program that runs several filters over an image to extract edge
information. Currently it loads any uncompressed grayscale TGA file, and
spits out another uncompressed greyscale TGA file that is 255 at places
where there are edges, and 0 where there are not. I managed to get out
quite a lot of noise.

You can find a test image and the result at
http://home.student.utwente.nl/l.e.veen/test4.jpg and

It is very simple:

1) Load the image
2) Rescale to 25% of the original size to filter out noise
3) Run a double (x/y) Sobel filter on the image (a Sobel filter just
calculates the difference between two neighbouring pixel values. I'm not
sure about that, but that's what I'm doing and it looks remarkably
similar to the Sobel filter in Gimp)
4) Make the 10% highest values 1.0, and the rest 0.0
5) Export TGA

I'm still looking for ways to improve this, to also detect smaller edges
(ie with a higher frequency component...most of the time a 1 pixel wide
edge will be missed).

Just before I forget, I also have a Haar wavelet transformer that can
transform arbitrarily sized images. No 3D yet, 2D only, but that can be
added. Other wavelets can be plugged in easily too.

Then out of this resulting image I try to extract edge and vertex
information, which turns out to be rather complicated (read simple in
concept, but I'm not a very good programmer). The current idea is as

1) Do steps as before
2) Find a pixel with value 1.0
3) Get the slope of the edge underneath from the original image
4) Trace ray along the edge, until you meet a pixel that is 0.0
5) Save this edge, and try again from the point you ended up at
6) If you can't go any further, find a new starting point until
everything is done

This doesn't actually work yet, but let's imagine it does, or that we
have another means of extracting triangles from the image. Now want to
compress video. I've so far thought of two ways of doing this, a 2D one
and a 3D one. I'll start with the 2D one.

1) Triangulate first frame
2) Use the same vertex coordinates and attempt to match textures from
the first frame to the second frame. Static objects will match.
3) Leave all the triangles that matched in place, remove the rest and
retriangulate based on the new frame.
4) Rinse and repeat for this frame

This would then be combined with intra- and inter-frame fractal
compression on the triangular textures. Also stored textures could be
wavelet compressed, and this could be combined with the fractal
compression. I reckon this one would be pretty good.

Then the 3D version. 

1) Load in the video as a 3D block of voxels
2) Calculate gradient normals troughout the volume (similar to
calculating the surface normals I do now, with a Sobel filter or perhaps
something more advanced).
3) Triangulate the first slice/frame
4) Using a cross product between the edge in the first slice and the
gradient normal, calculate a second vector to make the edges into
planes. Find their edges by raytracing, like in the 2D version.

Alternatively, use some other algorithm (Marching Cubes springs to mind,
but there are patents surrounding it) to extract planes in the data.

I'm not really sure whether this would work. It doesn't seem very
logical to me for some reason. Also I don't know what we would to with
textures here.

Aside from asking your opinions and ideas on this, I also have a more
practical question, and an Ogg one.

I have a bunch of float-to-int statements in my program, and I
(naturally) get warnings about them. Is there a C or C++ function that
takes a float and returns a rounded int?

And the Ogg question: I'm currently using C++. Is this a problem for
acceptance of the code into Ogg?

Phew, well that was a long post. Hope you're willing to read it all and
start a bit of a discussion. Oh and btw, if you want to see the code
drop a note and I'll put it on the web.


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

More information about the Vorbis-dev mailing list