Hello Rahul:

i m a student and interested in gsoc project:Fast Adaptive Resampler Tailored For Transformations Which Mostly Downsample

I have read the requirements properly for this project which also includes jacobian transformation,box filtering algorithm and bilinear resampling.But i am having some problem in relating all these in one algorithm. Please guide me.Also I would like to know the status of this project progress.

The >>programming<< for this project has not started. "No progress" is consequently a fair description.

This would be a brand new way of doing downsampling, so I can't point you to "one algorithm."

Computing jacobian information (for an arbitrary point transformation) approximately using finite differences is probably too ambitious. My current opinion is that this method should only be used when the point transformation "communicates" this information to the sampler. This probably means that a point transformation (e.g., scale, rotate) needs to have this info part of its implementation as an object. I'll need opinions from people who know better at some point.

You need to understand exact area methods, and in particular, exact area box filtering (basically, you understand images as being a piecewise constant surface, with the pieces determined by the set of points which are closer to a pixel center than any other pixel center, and you (approximately) integrate this surface over an area associated with the new pixel centers (determined by the point transformation).

References which may help understand what is going on are

@TechReport{Dodgson, author = {N. A. Dodgson},
title = {Image resampling}, institution = {University of Cambridge Computer Lab.}, year = 1992,
number = {UCAM--CL--TR--261}, address = {15 JJ Thomson Avenue, Cambridge CB3 0FD, UK}, month = {Aug.}
}

and

@inproceedings{DBLP:conf/iciar/RobidouxTGT08, author = {Nicolas Robidoux and
Adam Turcotte and
Minglun Gong and
Annie Tousignant},
title = {Fast Exact Area Image Upsampling with Natural Biquadratic Histosplines},
pages = {85-96},
ee = {http://dx.doi.org/10.1007/978-3-540-69812-8_9}, bibsource = {DBLP, http://dblp.uni-trier.de}, crossref = {DBLP:conf/iciar/2008} }

Also, a student and I programmed a C filter (for 8-bit ppm/pgm) which does exact area box filtering in the very simple case of pure image resizing. If you're still interested, we'll put this on the web.

The proposed method is none of the above. More precisely, it is a composite method: It "fits" a new fast but accurate downsampling method (related to box filtering) and bilinear together so that Frankenstein is flexible and "smoothly varying."

Note: French is my mother tongue. If you are more comfortable in French, you can communicate with me---not this list---in French. Obviously, English is fine too.

Best of luck,

Nicolas Robidoux Universite Laurentienne

On Mar 10, 2009, at 8:56 AM, Nicolas Robidoux wrote:

Hello Rahul:

i m a student and interested in gsoc project:Fast Adaptive Resampler Tailored For Transformations Which Mostly Downsample

I have read the requirements properly for this project which also includes jacobian transformation,box filtering algorithm and bilinear resampling.But i am having some problem in relating all these in one algorithm. Please guide me.Also I would like to know the status of this project progress.

The >>programming<< for this project has not started. "No progress" is consequently a fair description.

Computing jacobian information (for an arbitrary point transformation) approximately using finite differences is probably too ambitious. My current opinion is that this method should only be used when the point transformation "communicates" this information to the sampler. ...

Numerical Jacobian calculation is not so bad in terms of coding effort --
you can use the method I implemented for PDL::Transform (available as part
of the PDL package for Perl, or at pdl.perl.org), and it's straightforward
to code. The PDL::Transform resampling code switches its sampling technique
based on user input; Jacobian based spatially variable filters are used where artifact avoidance is most important. It might make a nice starting
point for you to look at.

On the other hand, you will need to think a bit about the "Fast" part, which
the PDL Jacobian-driven sampling is not -- mostly because of the need to supply input and output filtering. I did that by padding the singular values
of the Jacobian to approximate the effect of convolving one-pixel-wide input
and output filter kernels with the calculated sampling kernel. That requires
subjecting a matrix to singular value decomposition for every pixel - there
is almost certainly a faster way to do it. For linear transformations (where
the Jacobian is constant) the method is much faster.

Dodgson is a great reference (in Nicolas' email). You might also like to
read Ken Turkowski's nice overview of resampling theory: http://www.worldserver.com/turk/computergraphics/ResamplingFilters.pdf

My own paper on the subject (in the context of image resampling for scientific
applications) is here:
http://adsabs.harvard.edu/abs/2004SoPh..219....3D

You need to understand exact area methods, and in particular, exact area box filtering (basically, you understand images as being a piecewise constant surface, with the pieces determined by the set of points which are closer to a pixel center than any other pixel center, and you (approximately) integrate this surface over an area associated with the new pixel centers (determined by the point transformation).

References which may help understand what is going on are

@TechReport{Dodgson, author = {N. A. Dodgson},
title = {Image resampling},
institution = {University of Cambridge Computer Lab.}, year = 1992,
number = {UCAM--CL--TR--261}, address = {15 JJ Thomson Avenue, Cambridge CB3 0FD, UK}, month = {Aug.}
}

and

@inproceedings{DBLP:conf/iciar/RobidouxTGT08, author = {Nicolas Robidoux and
Adam Turcotte and
Minglun Gong and
Annie Tousignant},
title = {Fast Exact Area Image Upsampling with Natural Biquadratic
Histosplines},
pages = {85-96},
ee = {http://dx.doi.org/10.1007/978-3-540-69812-8_9}, bibsource = {DBLP, http://dblp.uni-trier.de}, crossref = {DBLP:conf/iciar/2008}
}

Also, a student and I programmed a C filter (for 8-bit ppm/pgm) which does exact area box filtering in the very simple case of pure image resizing. If you're still interested, we'll put this on the web.

The proposed method is none of the above. More precisely, it is a composite method: It "fits" a new fast but accurate downsampling method (related to box filtering) and bilinear together so that Frankenstein is flexible and "smoothly varying."

Note: French is my mother tongue. If you are more comfortable in French, you can communicate with me---not this list---in French. Obviously, English is fine too.

Best of luck,

Nicolas Robidoux Universite Laurentienne

Hello Craig:

Numerical Jacobian calculation is not so bad in terms of coding effort

The issue is that, if I understand correctly, GEGL's current "pure" demand-driven structure means that resamplers have no information whatsoever about what other nearby locations are being resampled, and consequently there would need to be major changes to make this info available for arbitrary transformations (with, most likely, serious speed impact). Once you have it, sure, computing approximate Jacobian matrices is no big deal (provided you make sure that you stay from singularity).

Hence my pragmatic choice to reserve the use of the "novel" (not so sure anymore that it's really new) method for tasks for which the jacobian is easy to compute and pass on. (This is the: "ask people who know better" part.)

Does this make sense to you?

Nicolas Robidoux Universite Laurentienne

Hello Rahul:

Indeed, the GSoC I suggested can be roughly described as implementing a poor man's version of the scheme Craig describes in

http://adsabs.harvard.edu/abs/2004SoPh..219....3D

Replace circles/ellipses by parallelograms/rectangles, and notice that "padding" the singular values of the Jacobian to 1 is more or less equivalent to exact area box filtering with sides no less than the input image's inter-pixel distance, and one gets more or less the same thing.

This being said, what I have in mind in way simpler than what Craig implemented. But if you understand Craig's paper, you probably understand what I want to do.

Nicolas Robidoux Universite Laurentienne

This being said, what I have in mind in way simpler than what Craig implemented. But if you understand Craig's paper, you probably understand what I want to do.

Actually, if I took the time to completely understand Craig's paper, I probably would understand what I want to do.

;-)

Nicolas Robidoux Laurentian University

Rahul:

exact area box filtering with sides no less than the input image's inter-pixel distance

This was a bit terse:

Exact area box filtering with a square box with diameter equal to the inter-pixel distance is exactly bilinear interpolation. So, it's only when the sides are larger than the scheme is not bilinear.

nicolas

Rahul:

I just replied to the list instead of including you in the CC.

If you want to read the whole discussion, go there:

http://www.mail-archive.com/gimp-developer@lists.xcf.berkeley.edu/

nicolas