On Sat, Jan 24, 2009 at 2:48 PM, jungle wrote:

Has anyone ever done any work implementing advanced interpolation schemes (NEDI or ICBI)? They provide much better results than the spatially invariant schemes present in GIMP.

AFAIK no.

I would probably be able to code up something, but I wouldn't be able to guarantee that it would be very efficient. Of course, these more complicated methods are much slower.

ICBI matlab GPL source is available. I should be able to port it to c++. What do y'all think?

NEDI looks amazing, and ICBI even more amazing; I could certainly put them to good use rather than my current rather slow/limited vectorization-based scaling system.
Keep in mind:
a) You should investigate implementing this interpolation method for GEGL rather than GIMP, as in the fairly near future these kinds of transformations in GIMP will be implemented through use of GEGL. b) If you want it included with the baseline GEGL distribution, it would need to be written not in C++ but in C. If you don't, then you can probably code it in C++ fine.

David

On Sat, Jan 24, 2009 at 11:47 PM, David Gowers wrote:

On Sat, Jan 24, 2009 at 2:48 PM, jungle wrote:

Has anyone ever done any work implementing advanced interpolation schemes (NEDI or ICBI)? They provide much better results than the spatially invariant schemes present in GIMP.

AFAIK no.

I would probably be able to code up something, but I wouldn't be able to guarantee that it would be very efficient. Of course, these more complicated methods are much slower.

ICBI matlab GPL source is available. I should be able to port it to c++. What do y'all think?

NEDI looks amazing, and ICBI even more amazing; I could certainly put them to good use rather than my current rather slow/limited vectorization-based scaling system.
Keep in mind:
a) You should investigate implementing this interpolation method for GEGL rather than GIMP, as in the fairly near future these kinds of transformations in GIMP will be implemented through use of GEGL. b) If you want it included with the baseline GEGL distribution, it would need to be written not in C++ but in C. If you don't, then you can probably code it in C++ fine.

To clarify -- this is because both GEGL and GIMP are written in C.

David

2009/1/24 David Gowers :

a) You should investigate implementing this interpolation method for GEGL rather than GIMP, as in the fairly near future these kinds of transformations in GIMP will be implemented through use of GEGL.

My understanding is that this will not be possible in GEGL as things stand, since GEGL does not give interpolators the local slopes. In other words, a GEGL interpolator is just asked for the value at (double x, double y), it can't find out how closely spaced the surrounding sample points are.

No doubt this could be added or changed. I think other interpolator authors have been asking for this feature as well.

John

John, David and Bill:

jcupitt@gmail.com writes: > 2009/1/24 David Gowers :
> > a) You should investigate implementing this interpolation method for > > GEGL rather than GIMP, as in the fairly near future these kinds of > > transformations in GIMP will be implemented through use of GEGL. >
> My understanding is that this will not be possible in GEGL as things > stand, since GEGL does not give interpolators the local slopes. In > other words, a GEGL interpolator is just asked for the value at > (double x, double y), it can't find out how closely spaced the > surrounding sample points are.
>
> No doubt this could be added or changed. I think other interpolator > authors have been asking for this feature as well. >
> John
>

Bill:

There are already two fast nonlinear resamplers implemented in GEGL:

YAFR (gegl-sampler-yafr.c)

and

Nohalo-sharp (gegl-sampler-sharp.c).

Both are a little slower than gegl-sampler-linear, but faster than gegl-sampler-bicubic. See the (informal) benchmarks at

http://bugzilla.gnome.org/show_bug.cgi?id=566717

Code wise, you may want to have a look at the following:

http://svn.gnome.org/viewvc/gegl/trunk/gegl/buffer/gegl-sampler-sharp.c?revision=2881&view=markup

This is the lowest quality/fastest version of a scheme which, at higher quality levels, should compete advantageously will NEDI in the good looks department.

Nohalo-sharp is (literally as we speak!) also being implemented in vips, and on the GPU (with DirectX).

A not yet implemented variant of the scheme, Nohalo-Smooth, will look smoother (duh!).

YAFR (Yet Another Fast Resampler) is likely to be made obsolete by the higher level nohalos.

See:

http://svn.gnome.org/viewvc/gegl/trunk/gegl/buffer/gegl-sampler-yafr.c?view=markup

------

I'd love manpower (GSoC?) to implement Nohalo-Smooth and/or either Nohalo at higher quality levels.

(Just a wish.)

Nicolas Robidoux Laurentian University/Universite Laurentienne

Hello Bill:

At some point it may a good idea to move this discussion off the list, but at this point I'll hope that those without interest in these issues are just skipping this email.

----------------------------------------------------------------------

jungle writes: >
> Nicolas Robidoux wrote:
> >
> >
> > There are already two fast nonlinear resamplers implemented in GEGL: > >
> > YAFR (gegl-sampler-yafr.c)
> >
> > and
> >
> > Nohalo-sharp (gegl-sampler-sharp.c). > >
> >
>
> I'm not familiar with those two resamplers. Of course, that's not saying > much, because it's not my area of expertise. I should mention, however, > that I consider NEDI and ICBI interpolators of a different kind than most. >
> First of all, they are very slow compared to bicubic. Speed is not the > goal.
>
> Secondly, they don't provide a value for any point in between given pixels. > Rather, their purpose is to enlarge the image in question by a factor of 2 > (roughly. Actually it's size*2-1). After scaling, the image can be > resampled to any size desired using other methods. Both algorithms copy > known (given) pixel values into a 2x enlarged grid and then fill in the gaps > between pixels using certain assumptions about the statistical values of the > pixels.
>
> The main benefit of both algorithms is the performance around edges. ICBI > is an improvement on NEDI. Edges are much smoother and more natural than > bicubic.
>

This is how nohalo works too, The current (low quality, but highly optimized) gegl-sampler-sharp.c only subdivides once and uses bilinear as "finishing scheme."

Consquently, the gegl-sampler-sharp.c code may provide a good basis for an implementation of "single subdivision" NEDI or ICBI, "one level implementations" which should give good results for resamplings which only involve moderate enlargement/stretching ratios (for nohalo, it's up to about 3-6).

> I explain all this to try to decide if the goal of ICBI is > different than nohalo, and if there would be a reason to try to > code it. Is there a paper I can read on nohalo? Or examples of > results that I could compare to ICBI?

Nohalo-sharp and nohalo-smooth are brand new schemes (we hope: maybe we'll find that they actually are "old"; I have to confess that I don't know as much about them as I should). We are currently writing the first paper about them. But there should be two comparison web sites coming up "soon."

You can also install the current gegl svn trunk and do the testing yourself. I'll include a sample .xml file at the end of this email (adapted from something Øyvind Kolås passed on).

My hunch is that, given the same subdivision level, nohalo will not "straighten" as much as NEDI/ICBI, but will show less "fine scale artifacts" and will run faster---even if programmed with the same programming skill.

This being said, if you would contribute toward the programming effort involved in implementing the "higher level nohalos" (I would guess the main programming issues are basically the same as with implementing the higher subdivisions for NEDI and ICBI) I'd be happy to count you among the co-authors of the appropriate paper(s).

If you just end up programming NEDI/ICBI---but don't touch nohalo---I'd be happy to use your code for our image resizing comparison suite (which should be on the web fairly soon).

Nicolas Robidoux Universite Laurentienne/Laurentian University

Bill:

I forgot the sample xml code to test nohalo-sharp level 1:

<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<

How to use:

Step 1:

Put this in a file (called, say, scale16p4PICTURE.xml) in the directory

YOUR_GEGL_ROOT/docs/gallery/

YOUR_GEGL_ROOT being where you installed the gegl svn trunk.

For example, if you used

svn co http://svn.gnome.org/svn/gegl/trunk/ gegl

then YOUR_GEGL_ROOT is gegl.

Step 2:

Put PICTURE.png in

YOUR_GEGL_ROOT/docs/gallery/data

Step 3:

In YOUR_GEGL_ROOT/docs/gallery/

do

make clean && make

Step 4:

Point your browser to

YOUR_GEGL_ROOT/docs/gallery

(Note: you may want to rm -i *.xml in gallery to remove the xml drivers which don't interest you.)

nicolas

Apologies:

I meant:

Point your browser to

YOUR_GEGL_ROOT/docs/gallery/index.html

Nicolas Robidoux Laurentian University/Universite Laurentienne

Bill:

A quick note about gegl-sampler-sharp (a.k.a. nohalo-bilinear level 1): I just checked, and it does a pretty good job at mild downsampling.

Also:

I am not convinced, far from it actually, that NEDI will do better than nohalo level 1 when the enlargement ratio is moderate (no larger than about 3), and I am pretty confident that higher level nohalos will actually do better across the board. It almost certainly will be much slower.

So: I am not sure it really is worth your while implementing them for GEGL, given that their aims are pretty much the same, and the means are not completely different..

(Warning: I am highly biased: I am the main designer of the nohalo method. I also stand to be corrected: nohalo is still too young for me to really know its character. Note that nohalo-bilinear level 1 used on a CG picture which is "writing like"---as opposed to a photograph of a natural scene---is >>not<< likely to give impressive results.)

Nicolas Robidoux Universite Laurentienne