What is an "edgelet"?

[trbarry]

Silly question, and I probably just made up the word.

But it seems video is essentially made of a combination of edges, textures, and gradients. And textures and gradients seem to be handled just fine by normal DCT, sums of various cosines.

But edges are different. Because of the way real world objects move around these edges would tend to be the boundaries where we should stop doing one thing and start doing something else.

Now I don't pretend to understand wavelets but I was wondering if there was any similar well behaved mathematical transform that just happened to be very good at expressing edges, sharp transitions.

Does anyone know if such a mathematical beast exists?

- Tom

[Birdy1]

How about splines? A spline is just a line, but when you say one side of the line is this color and the other side is that color, then you have an edge.

[akupenguin]

Yes, there exist other sets of basis functions that attempt to address this issue: ridgelets, bandlets, wedgelets, ...
AFAIK, while there are some nice theoretical results, none have been made into a viable compression format yet.

Also, all codecs I know of so far have separated motion from residual transform, but that doesn't have to be the case. I can imagine a variant of mesh-based motion compensation that takes into account edges in the image.

[Joe Fenton]

I've read papers on edge-based scaling - where filters are applied to edges after scaling an image up to avoid blurring the edges. It uses info in the DCT space to determine if an edge exists and what direction it is.

It always seemed to me that an interesting experiment would be to modify a DCT based codec so that it used the DCT space info to look for edges and to change the quantizer values a little on the fly based on whether an edge were present in an MB. Raise the quantizer if no edge, and lower the quantizer if an edge is present.

I have no idea how feasible that is, but I keep meaning to look into it more one of these days.

[trbarry]

Yes, there exist other sets of basis functions that attempt to address this issue: ridgelets, bandlets, wedgelets, ...

akupenguin -

Thanks. I'll look for things under those names.

- Tom

[trbarry]

I think I'm looking for something like sort of like a wavelet but reflected upside down after the center point. So the tails are at 2 different levels and maybe with a smooth accelerating rise in the center.

Sigmoid (or inverse)? Hyperbolic tangent? It seems I remember a couple curves shaped like that.

- Tom

[akupenguin]

Disclaimer: I haven't tried to make a wedgelet compressor either. But I have used wavelets in the context of Snow, JPEG2k, and various image/video filters.

like this?
http://mathworld.wolfram.com/s1img2355.gif http://mathworld.wolfram.com/himg4170.gif
The problem in practice is how to (a) generalize it to 2D, (b) make it multi-resolution, and (c) deal with the overcomplete set of basis function you get from combining it with wavelets.

1D wavelets do reasonably well at representing point discontinuities. There's a bit of ringing, but you still only need a few non-zero coefficients for reasonable distortion. But the normal way of making 2-D wavelets is as a tensor product of 1-D wavelets, which is really bad at diagonal edges.

You can't just scale down Tanh to represent finer details, because it still extends infinitely in both directions. If you segment the image into discrete blocks and transform them independently, that produces blocking artifacts. And a deblocking filter would be equivalent to fading out the function at the edges. So I would propose to skip that step and just use a basis function more like this: (drawn freehand, no particular equation in mind)
http://img59.exs.cx/img59/5216/wedge36qn.png
which would then be allowed to rotate (in discrete inrements). Disadvantage: slower, because it can't be separated into two 1-D filters.

[Manao]

I don't know exactly the definition of bandelets / ridgelets & co, but there is a firm which is using them : have a look here (http://www.letitwave.fr/). And, for once, the results claimed by the firm aren't faked.

[d'Oursse]

The firm is just using bandlets (more pricesely a modification of them)

trbarry: look at here: http://www.sam.math.ethz.ch/news/conferences/archive/zss04

i have participated to these conferences and talked with the authors. They are eagerly waiting for people to write good code for their starlets (*-lets), especially E. Candes and R. Baraniuk. Don't hesitate to mail them for more informations.

bandlets, wedgelets and curvelets are good wavelet basis to track the edges in a image.

If you want the talk of E. Lepennec (which is not on the web site of ETHZ), i could send it to you.

[trbarry]

I don't know exactly the definition of bandelets / ridgelets & co, but there is a firm which is using them : have a look here. And, for once, the results claimed by the firm aren't faked.

Cool. If you look at their Technology page it looks like they do have a means of finding edges and breaking out objects.

- Tom

[scharfis_brain]

hm... but what about the bottom corners of those sample pictures?
they are far more blurred than the other image areas.

so they seem to use a focus...

[akupenguin]

Yup. While the results are impressive, it looks like part of their compression gain for mugshots is adaptive quantization favoring the center of the picture.

[d'Oursse]

Sharfis: the aim of LetItWave is to provide a compression algorithm that is adapted to compression of faces. So they have modified the usual algorithm to take into account an image that displays a face (the hair are at the top of the image, below the hair, there are the eyes, then the nose, etc...)

That's why the boundary of the compressed image is not accurate (they don't care about the boundary of the image and they preserve some bytes there to use them for the face)

their aim is to put these compressed faces in *very* small amount of memory

[LordRPI]

Originally posted by akupenguin
Yup. While the results are impressive, it looks like part of their compression gain for mugshots is adaptive quantization favoring the center of the picture.

Clever. But I guess the big picture if it works in the context of what their aiming for, then it's *ok* - but still needs to be pointed out it isn't the end-all in the big picture.

[trbarry]

Yup. While the results are impressive, it looks like part of their compression gain for mugshots is adaptive quantization favoring the center of the picture.

It may actually be the resolution and not the quants. I've experimented and I think posted here of using the WarpedResize function of my SimpleResize filter to warp the image such that there is more detail towards the center where the action is. Then during display unwarp it back to linear.

The way the filter is written WarpedResize is busted for YV12 (okay for YUY2) and there is currently still no exact inverse for the warping but I really do intend to fix that someday (really, I promise ;) ) since the idea seems to work. It's especially useful for the safe area of very wide screen movies. But of course a PITA to display.

Anyway, maybe they are doing something like that since it would be fine for portraits.

- Tom

[akupenguin]

With multiscale transforms like *-lets, adaptive quantization is equivalent to adaptive resolution.

[trbarry]

I hadn't really grasped that but, like I said, I really don't understand wavelets and the like yet.

Would there be any advantage in combining wavelets and arbitrarily steep sigmoid curves just to be able to use blocks in wavelets, to handle the block boundaries better?

But maybe I had better go study these things a bit more before I really betray my ignorance here.

- Tom

[scharfis_brain]

IMO image warping could hurt video compressibility on panning scenes, cause the AR isn't homogeneous anymore...
(no more equal vectors (direction, length)
moved macroblocks aren't fitting...)

[trbarry]

IMO image warping could hurt video compressibility on panning scenes, cause the AR isn't homogeneous anymore...

Good point, though the amount of warp I was playing with would vary by only a small amount from block to block. Even there you could probably adjust for it in motion comp functions if the codec was designed for it. For that matter, similar sorts of warping occur with foreshortening as people rotate, turn their head, etc. Somebody's probably already worked that out somehow.

- Tom

[MfA]

With a multiscale transform (or even jpeg) you can adapt the amount of detail coded inside a given region very smoothly, if you have good entropy coding you can do all that with smart quantization as aku said.

[akupenguin]

Originally posted by trbarry
For that matter, similar sorts of warping occur with foreshortening as people rotate, turn their head, etc. Somebody's probably already worked that out somehow. Yep, it's called "mesh based motion compensation". But then you're talking about temporal prediction, not variable resolution.