downsampling with grid_sample doesn't match interpolate

[fmassa]

I'm taking this discussion from #20785 (comment) as it is unrelated to grid_sample not being aligned.

---

There is also another point that I'd like to make about grid_sample, which is that even after we make this change to make it aligned, it won't match 1:1 with interpolate in some cases.

Indeed, if we use grid_sample to downsample an image using bilinear interpolation, it will always take the 4 closest pixels that correspond to the neighbors in the image space. This means that for large downsampling factors, this will make the bilinear interpolation look almost like a nearest neighbor interpolation.

Here is where this is defined

pytorch/aten/src/ATen/native/cuda/GridSampler.cu

Lines 181 to 186 in 90182a7

	int ix_ne = ix_nw + 1;
	int iy_ne = iy_nw;
	int ix_sw = ix_nw;
	int iy_sw = iy_nw + 1;
	int ix_se = ix_nw + 1;
	int iy_se = iy_nw + 1;

We might potentially want to replace the +1 with the corresponding image offset after a lookup in the coordinates of the next elements in the grid, to have smoother interpolation. But I haven't thought about it throughly, and we might be overfitting to a particular case. In particular, I don't know how what I proposed just above would behave with grids having holes.

---

Comment from @bnehoran from #20785 (comment) :

I am not sure I understand how what you are suggesting would work for a more general grid.
First of all, if I understand what you are suggesting, you are proposing to allow grid_sample to also do the job of upsampling and/or downsampling tensors, right?
Just to avoid confusion, as you mention, this is different than the point made in this issue, which is more about using the two functionalities in conjunction with one another (that is, using grid_sample on a tensor that has been upsampled or downsampled using interpolate), but incidentally, it seems that these changes should also cover the case of using gird_sample to upsample/downsample, for the most part.

I agree that calling grid_sample on a tensor using an identity grid of larger size than the tensor should have the same effect as upsampling it using interpolate with bi/tri/linear modes, and I think these changes should do that. Similarly, attempting to downsample a tensor by using grid_sample with an identity grid that is smaller than the tensor, would bi/tri/linearly interpolate between the nearest whole pixels (note: rather than average pooling over the nearby area), which I believe should also be equivalent to the bi/tri/linear modes of interpolate. I think this equivalence is what you meant to point out, right?
The nearest modes should similarly become equivalent.

There would just be no equivalent to the area mode of interpolate. However, it's not immediately clear to me how such a mode should really behave for grid_sample. If the identity grid is evenly spaced, then it is all well, since the rectangular areas that each grid pixel covers are well defined. However, as soon as the grid starts deviating significantly from the identity (for example, in an extreme case, suppose that multiple grid points land on the same location of the sampled tensor), how do you then define the "area" covered by each grid point?
Maybe there does exist some way to define it that is both natural and consistent, but at the very least, it seems non-trivial.

cc @fmassa @vfdev-5

[bnehoran]

If I understand correctly, @andreaskoepf is suggesting at #24870 (comment) that a better downsampling grid_sample result could be achieved by filtering the image in different ways before sampling.

This could be one way to tackle the problem. Depending on the filtering method, it won't necessarily be equivalent to average pooling (the area mode of interpolate), but it could potentially give some nice results for grids that simultaneously warp and downsample.

[bnehoran]

If I may slightly rephrase the point of this issue, I think what we want to achieve is to add a mode to grid_sample (or possibly more than one) that incorporates a wider receptive field / window whenever the grid that's passed in is either smaller than the sampled image, or similarly when the sampled grid points just occur much farther apart, such that there are several image pixels between neighboring grid points.

As it is currently in such cases, those image pixels in between are just not used in the interpolation, and therefore do not factor into the output.
From what I can tell, there seem to be two different directions from which it might be desired to include/consider every input image pixel in computing the output.

1. The first involves the visual effects of downsampling, in which merely keeping one out of every so many pixels and dropping the rest often does not produce a visually appealing result, and produces several artifacts.
   I think @andreaskoepf could pitch in here with some more insight.

2. The second involves the effect on the gradient in the backwards pass. Any input pixels that do not factor into the sampling result are unfortunately given zero gradient in the backwards pass, and so they do not get any update in training. Likewise, the gradient for the grid points only depends on the immediate neighborhood, and so any high frequencies in the sampled image tend to cause an exceedingly noisy gradient, making it harder to learn.

In certain cases, there could be some methods that simultaneously do better at producing a visually appealing result and producing a useful and less noisy gradient for training, but it's very likely that there exists some sort of tradeoff between the two.

Note that if designed and implemented properly, this should allow grid_sample to subsume some of the interpolate method’s functionality for downsampling, by just using an identity grid of smaller size. Even so, I wouldn’t necessarily recommend using grid_sample in place of interpolate, since it would probably be much less performant and require generating an identity affine grid.
But it would certainly help to expand on the capabilities of interpolate and grid_sample by allowing for a combined warp-downsample, which is very much not the same as downsample and then warp.

[bnehoran]

Method Proposal: Expanding the definition of average pooling to irregular grids

One way to address this when only downsampling is needed (and no warping), is of course by average pooling (the area mode of interpolate).
When warp-downsampling, however, this is complicated by the irregularness of the grids that can be passed into grid_sample, so one question is whether we can expand the definition of average pooling to apply to an irregular sampling grid, and I think with some effort, we can.

The most natural definition seems to be just to say that the region sampled by a grid point is defined to be the set of image pixels for which that grid point is the nearest grid point.

This is a well defined notion, and it naturally reduces to the standard average pooling in the case of a regular grid.
The question is whether there is an efficient way to implement this: to determine which grid point is nearest to each image pixel, and then which image pixels should factor into the average for each grid point. I'm sure there is. It just requires some discussion.

---

N.B. Although the simple definition described above is probably sufficient for an initial implementation, there are some varieties and/or choices to potentially consider futher:

• The simple way I described above considers everything in whole pixel units, which can only be assigned to one grid point or another. The downside of this is that the gradient for the grid will then always be 0. So another way to look at it is to consider this definition for points within pixels as well (that is, points other than pixel centers), so that pixels areas can be divided up among regions belonging to different grid points. The average over these pixels would then be weighted by the fraction of each pixel that belongs to the grid point's region.
  Unfortunately, unlike the simple whole-pixel case, I imagine that this might be much more difficult to implement efficiently and cleanly.
• Another factor to consider is what should happen when the grid doubles over itself (that is, for example, if grid points that would normally be further to the right have moved over leftward and past grid points that would normally be to their left). One way would be to just say whichever grid point is closest is closest, period. But this would mean that sampling with a subset of the grid could be different than sampling with the full grid and then cropping it to that subset.
  Another way that addresses this inconsistency is to only consider the 3x3 grid neighborhood of each grid point when dividing up pixels (by which I mean the surrounding 3x3 chunk sectioned out of the grid tensor). Any pixel that is closer to a grid point than to the 8 other grid points that make up its 3x3 neighborhood is assigned to that grid point, and then you average as before.

[gchanan]

@bnehoran: assigning you because @soumith says you are working on it, but no time pressure to complete it. Let me know if that isn't accurate.

[bnehoran]

@gchanan I am not actively working on this.
What I discussed with Soumith was that I've started working on #36107 and #36108.
They were previously list items in #24870, so I've now expanded them into their own GitHub issues to make it easier to keep track and discuss.
If you want to assign those issues to me, that would be awesome (I unfortunately don't have sufficient privileges to do so myself).