Vorbis dev - Jan 2001 - Video compression, edge detection, and gcc warnings

<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
http://home.student.utwente.nl/l.e.veen/out.jpg.

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
follows:

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.

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

> 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?
rint(). Not in every compiler though (I think).

Segher

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

On Wed, Jan 10, 2001 at 08:28:07PM +0100, Lourens Veen
wrote:
> 
> 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.
Anyone doing edge detection based compression work would be advised to
read some papers by James Elder:

Elder, J.H. Are edges incomplete?,
      International Journal of Computer Vision. Nov 1999

J.H. Elder, S.W. Zucker,  Local Scale Control for Edge Detection and Blur
Estimation, 
     IEEE Transactions on Pattern Analysis and Machine Intelligence,
     vol. 20, no. 7, pp. 699-716, 1998.

Elder's publication page can be reached at:

http://elderlab.yorku.ca/~elder/publications.html

Some crude explorations of the ideas presented in these papers can be
found at the following link:
  
http://www.stanford.edu/class/ee368b/Projects/cnetzer/

In particular, Elder and Zucker have some good multi-scale edge detection
algorithms.  They then reconstruct from the edges using PDE methods, but
the edge detection may also be useful for reconstruction with facets


-- 
Chad Netzer
cnetzer@stanford.edu

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

.. just a thought.. how about detecting edges for each channel ? ie. detect
edges for red, green, blue, and possibly alpha, seperately ?

Gerry
- again babbling wildly about stuff i know little or nothing about

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