Backprojected Lanczos? [Archive]

View Full Version : Backprojected Lanczos?

morsa

15th September 2005, 10:39

This is my question? Is it worth it?
I've been hearing about backprojection since a long time.
I saw some examples here and they look great!!

http://www.general-cathexis.com/interpolation.html

On anycase can someone point me to available easy to understand explanations/descriptions of how it works ?
(I've tried Google but haven't found much)
Thank you guys as always.

mg262

15th September 2005, 11:05

See http://www.interpolatethis.com/phpBB2/viewtopic.php?p=826&sid=a0d2aee739e5245d1e7c7d42b3e2a5d2

The basic idea is that you find the high-resolution clip which is most likely to yield the "original" clip when downsampled.

Where the forward process is linear -- which includes bilinear, bicubic,lanczos, the reverse process (back projection) can be done pretty quickly; the maths is at the end of this post, http://forum.doom9.org/showthread.php?p=604415#post604415, although at the time I wrote that I didn't realise that the method had a name.

morsa

15th September 2005, 11:11

Bad Boy!!! ;)

You pointed me just to where I came from :devil:

Now seriously:
Thanks for the math.. Anyway It wasn't quite useful (for me)

mg262

15th September 2005, 12:23

Ummm... I'm not quite sure what you're looking for. The link I gave has an English description (though I did just find it using Google) of the process, which you've obviously seen, so it's not that -- are you looking for a clearer description or more technical details?

In general, the process seems to involve repeatedly guessing upsampled pictures, downsampling them, and eventually picking the upsampled picture that came closest to the "original" when downsampled. In the linear case, it is possible to short-circuit the guessing process by using maths.

I'm sorry if this isn't being very helpful... but I'm not quite sure what you're looking for?

Edit: I don't like that comparison because there are already artefacts (specifically haloing) in the source picture.

morsa

15th September 2005, 23:20

Exactly.I'm looking for the "real" explanation of the procedures involved on doing it.
Just to give you an idea.A couple of months ago, I was trying to understand how Hadamard transfrom was being used inside H264.
After getting like 10 different books explaining the inners of it, and downloading several papers describing Hadamard uses and looking inside the code of X264 and several other codecs (ranging from 1971 till this day) I finally put all the pieces together and got the final thing.
I coded a compresor using Hadamard in a completely different way to the one used inside H264.And that is in some part because some of the things applyed inside H264 weren't explained anywhere.It seems you just need to have a big background on codec programming to have that little "Know How" that nobody wants to describe in a book ;) .

Now I'm trying to gather the info about this new topic, but problem is I can't seem to find the right one.
Am I clearer now?

morsa

15th September 2005, 23:29

In general, the process seems to involve repeatedly guessing upsampled pictures, downsampling them, and eventually picking the upsampled picture that came closest to the "original" when downsampled. In the linear case, it is possible to short-circuit the guessing process by using maths.

"repeatedly guessing upsampled pictures "

How is that achieved? using several diferent interpolations to different sizes or what?

"downsampling them "

What method? Just binning or what?

" picking the upsampled picture that came closest to the "original" when downsampled "

means just a comparison pixel by pixel???

I think now you have a better idea of what I am looking for.
I just hope some more people here could get interested about this.
Thank you as always

mg262

15th September 2005, 23:55

I'm afraid I can't help very much, but here are a few things:

Suppose you're using back-projected Lanczos to upsample from 100x100 to 400x400. Then all of your guesses will be of size 400x400, and to evaluate how good they are, you will downsample them to 100x100 using Lanczos.

Closeness to the original is probably measured using the sum of the squares of the differences of the pixels.

That leaves unanswered the big question, namely how do you come up with the guesses? Whatever method you use, I think it would still be called back-projection, so arguably it's an implementation detail... but that's just avoiding the question. Remember that it's an iteration... so you're not guessing out of the blue, just improving your guess. (The first guess is relatively easy... just use any normal upsampling method.) What you're trying to do is find a minimum in a very high dimensional space, and that's a problem that's both hard and well studied... there's a whole chapter in Numerical Recipes discussing finding minima in various dimensions.

I will try and say some more about this tomorrow when I am more awake!

mg262

19th September 2005, 18:43

And now I can't remember what I was going to say... well, if it is any use, I can spell out the maths for the linear case I mentioned as carefully as possible -- although it will need some understanding of vectors, matrices and calculus to make sense. [Although if you're messing with frequency space transforms, you probably understand all of those pretty well.] Shout if you want it.

For the iterative case, again assuming some maths, I think the basic idea would be that if you make a small enough perturbation to a guess, the change to the quantity you are trying to minimise would be a linear function of the perturbation. So you can repeatedly perturb the guess by adjusting each pixel separately, obtain the direction of maximal change and take a small step in that direction. Then repeat. [This is surely not the only method... just to give you an idea.]

morsa

21st September 2005, 02:14

Great thanks.Anyway if you can provide me with a short list of several different papers or books describing it I would be more than happy.
(in anycase if you can get the idea of this idiom I would say "happier than a two-tailed dog" :D )

MfA

21st September 2005, 13:06

A little googling found this (http://contentdm.lib.byu.edu/ETD/image/etd976.pdf). They call it sensor model constraints, but it is really the same thing as you are talking about AFAICS.

BTW as suggested in the above paper it is quite easy to use sensor model constraints with "Image Magnification Using Level-Set Reconstruction" (which Tritical already implemented, sans constraints). Of course that is more like a hill-climbing approach, so it can get stuck in local minima. Using random perturbation of pixels with something like a simulated annealing approach is going to be way way slow though.

A couple google searches which seem to have some decent, if voluminous, results you might want to spit through :
(resizing OR upsampling) iterative (psf OR sensor-model)
iterative-back-projection (upsampling OR interpolation OR resizing)

Guest

21st September 2005, 14:00

Nice find, Mfa! Thanks for digging that up and posting it. It's very interesting. The whole process is impractical for video, but the sharpening step may possibly be useful.

Didée

21st September 2005, 15:43

We've been told that there is no need for any advanced sharpening techniques. Remember I put some examples here (http://www.neuron2.net/board/viewtopic.php?p=6119#6119) (which, in fact, made use of some more simple, still rather similar (http://home.arcor.de/dhanselmann/_stuff/SeeSaw_(unfinished).png) ideas to what is described in abovelinked PDF).

But then, Ivo clearly demonstrated (http://www.neuron2.net/board/viewtopic.php?p=6120#6120) that all we need is unsharp masking. <g>

mg262

21st September 2005, 16:46

Cf. http://www.neuron2.net/board/viewtopic.php?t=638

@morsa,
most of what I have is scribbled on scraps of paper on my desk, so I don't have references. For general minimisation see Numerical Recipes [in C/C++/etc.] by Press et al. For the linear case try searching for "least-squares'' derivation.

tedkunich

23rd September 2005, 07:59