GSOC Project-Fast Adaptive Resampler Tailored

Hi Nicolas,

This is my first forum of any kind so please forgive me for any mistake.

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.

Thanks,

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