Hello all:

This question will make clear that I don't understand c++.

Suppose that, in the code for, say, gegl/gegl/buffer/gegl-sampler-cubic.c, I want to use information about the bounding box of the input data.

More precisely:

I (believe that) I already know that the relevant pixel values start at indices 0,0. Requested values to the left and above those are created by the (currently 0,0,0,0) abyss policy. Which is to say that 0 and 0 are the smallest "x" and "y" for which I have "real" data.

What I want to know is the width and height (in pixels) the area with "valid" pixel values.

This is almost the same as:

I want to know the lowest positive indices at which the abyss policy kicks in.

Which is almost the same as:

What is the index of the rightmost/lowest pixel with "real" data associated to it.

------

Once I have this info, I can finish the yafr code.

With thanks,

Nicolas Robidoux Laurentian University/Universite Laurentienne

Hello Øyvind:

Thank you for the quick response.

I wrote:

I (believe that) I already know that the relevant pixel values start at indices 0,0. Requested values to the left and above those are created by the (currently 0,0,0,0) abyss policy. Which is to say that 0 and 0 are the smallest "x" and "y" for which I have "real" data.

You replied:

Not true, the valid pixel values can be in any rectangular sub region of the buffer, negative values should also be supported. GeglBuffer supports dynamically growing (will be useful for GIMP having auto-growing layers when painting.)

I'll clean up the YAFR code this weekend, and submit a patch for gegl-sampler-yafr which makes accessible, through an otherwise inactive #define, a version of the code which carefully implements the boundary conditions making the assumption that valid pixels start at 0,0. (Obviously, this inactive version is not to be used by non-developers).

When not toggled, the code will use the default abyss policy, without implementing careful boundary conditions (in this respect, it will act like, say, gegl-sampler-cubic).

I'll briefly discuss the "toggle careful boundary conditions" version:

When used to, say, rotate the default image which shows up when typing gegl in a terminal, it reasonably seamlessly fills in values to the left and top (prior to rotation) of the unrotated image. With the "extent of valid pixel" info, I could make it do this all around.

The treatment of the boundary is equivalent to having a bilinear abyss policy, plus a correction to handle "far values."

Let me first describe the bilinear abyss policy, assuming that the abyss starts at -1 and extends to the left/top, and ignoring the fact that one needs to have an abyss policy at the bottom and right. Suppose that the stencil needs values which are to the left of 0. Find the two closest image pixels which are on the same horizontal line (if there are any; otherwise, it does not matter what values are used, because they will be overwritten in the vertical pass; this is not quite how it's really done but I don't want to be too long). On an horizontal line, bilinear extrapolation boils down to linear extrapolation. So, get the abyss value by linear extrapolation. Formula-wise, if the indices of the missing pixel are [i][j], this gives:

abyss_pixel[i][j] = pixel[i][0] + ( pixel[i][0] - pixel[i][1] ) * i;

This being done, we can now fix the abyss which is above the image, using:

abyss_pixel[i][j] = pixel[0][j] + ( pixel[0][j] - pixel[1][j] ) * j;

Although this may not immediately obvious, this computes properly the abyss_values which are in the "top left wedge," because bilinear extrapolation can be performed by a sequence of two linear extrapolations along an horizontal/vertical pair of lines, provided that the proper tile is loaded at the get go (the "proper" tile is easily computed, as explained below). Consequently, it does not matter if I fix left first, then fix top, or vice versa.

This abyss policy has a very attractive property:

If an (interior) scheme is exact on bilinear data---as are bilinear, all the cubic samplers, lanczos, YAFR and, for example, gaussian blur---meaning that if the data corresponds to a bilinear function, then the operation recovers the values of the bilinear function (in the case of gaussian blur it means that the blur operator is the identity, which should be for bilinear data), then extending the scheme using this abyss policy makes the "exact on bilinears" property hold everywhere, not only far enough in the interior of the image.

One consequence of this is that as the scheme traverses the boundary, the "seam" is fairly "smooth." The other is that "second order accuracy" is preserved without having to implement careful boundary conditions. You may think of this abyss policy as a second order improvement of the first order approach used, for example, by ImageMagick (programmed slightly differently than as described here): Fill the abyss with zeros, but normalize the coefficients having to do with non-zero values so they sum to 1. This last approach preserves the property of being exact on constants (as opposed to bilinear).

(I'll actually do a lit search when I have a minute and see if the bilinear abyss trick is published. If not, I'll write an article.)

I would be more than happy to help in implementing this abyss policy in Gegl (but the abyss code is quite complicated, so I'm not sure I'd want to do it completely alone).

This abyss policy has a very unattractive property:

If the abyss pixel abyss_pixel[i][j] which is to be computed is far from the boundary, then bilinear extrapolation amplifies noise in boundary values by a factor which is basically i*j. I programmed yet another version of the scheme, and this manifests itself as "smooth streaks" which "radiate" from the rotated image. If anyone asks me for the version of that code, I'll gladly oblige.

This problem can be fixed as follows:

When the sampler---not the abyss policy---is asked for a value outside of the convex hull of the non-abyss pixels, return the computed sampled value which corresponds to the closest point of the convex hull.

This sounds complicated, so I'll explain:

Consider the currently used approach (from gegl-sampler-linear.c). x and y are the coordinates of the requested sample.

...

dx = (gint) x; dy = (gint) y;

...

sampler_bptr = gegl_sampler_get_ptr (self, dx, dy);

...

Suppose that x and y are such that x0, so that the requested sampled value is outside of the "image."

Instead of using x and y directly, use this:

...

local_x = x < (gfloat) 0. ? (gfloat) 0. : x; local_y = y < (gfloat) 0. ? (gfloat) 0. : y;

dx = (gint) local_x; dy = (gint) local_y;

...

sampler_bptr = gegl_sampler_get_ptr (self, dx, dy);

...

(This is the "proper" tile. See above.)

As a side effect, abyss values are now only only computed for stencils relevant to coordinates which are in the convex hull of the input pixel positions.

-----

In order to know these "closest points of the convex hull," one must know the positions. This is why I think that it would be nice if the extent of the "valid pixel rectangles" was passed as an object to samplers.

But this "replace far positions by the closest positions for which the sampler interpolates" trick could also be implemented in the calling function.

If you've made it here, thanks: this was long.

Again, I'm willing to help with abyss policy business, but given my limited c++ I would appreciate some assistance.

Nicolas Robidoux Laurentian University/Universite Laurentienne.

Hello all:

I'd also be happy to help implement a "smear" (a.k.a. nearest neighbour) abyss policy, which preserves the property of being exact on constants (as the "truncate the stencil and normalize to unit sum does as well, although I think that going through an abyss policy is more elegant and faster).

In the case of YAFR for example, it would ensure that the transition through the boundary is continuously differentiable, without being as complicated as the bilinear abyss policy and without the need for "stick outside points to the boundary" to look good far from the valid pixels.

Nicolas Robidoux
Laurentian University/Universite Laurentienne