Trial of New Interpolation Methods

[anthony]

I have added as a trial to the current SVN IMv6.7.7-3 some new 'pixel level' interpolation methods.

These are only in IMv6 at this time, and the names for the methods are not final..

• Average16 -- average of 16 pixels around sampling point
• Average9 -- 9 pixels around nearest pixel
• Average -- Average of 4 pixels around sampling point
• NearestAverage -- Select nearest pixel if close, else Average
• NearestBlend -- blend 1, 2 or 4 pixel neighbors

Here is the results of a interpolative enlargement of some small test images. Increase or scroll the window as it is a bit long.


Notes...

• Before this 'Average' was equivelent to 'Average16' above. -- I always though it was as 'Average' above.
• Averaged methods are pixel level interpolative (box or linear) bluring methods.
• The 'Nearest' methods are variations on NearestNeighbor (or just 'Nearest')
• The center image 'NearestNeighbour' is equivelent to a 'scale' and shows the actual location of the pixel.
• Note that 'Average' Averages the area between pixels and as such the corners of the averaged area is located in 'center' of the pixel.
• Average9 does a Nearest Neighbour, and then averages it and its 8 neibhbours, to generate a average. A but like a radius 1 'flat' or averaging convolution of the source pixels.
• NearestAverage is equivelent to a 1/2 sized Nearest Neighbour, overlayed on 'Average'. The odd shaped colors are the averaged color.
• NearestBlend is the same but only averages the actual closest pixels. It is more like a 2-pass or tensor version
  of the NearestAverage.

Are these names acceptable? Any suggestions, before I port this into IMv7?
Remember these are interpolative methods, ment for special types of enlargement.
Should the size of the 'Nearest' be controlable rather than either 0.25 of the real pixel?

Here is the code used to generate the above (IMv6)

Code: Select all

  pixel='' color=''
  for i in   Average16 Average9 Average \
             NearestNeighbor  NearestAverage  NearestBlend  ; do

    pixel="$pixel i_pixel_$i.gif"
    convert xc: -bordercolor black -border 2 \
            -filter point -interpolate $i \
            +distort SRT 32,0 -set comment $i i_pixel_$i.gif

    color="$color i_color_$i.gif"
    convert \( xc:red xc:blue +append \) \
            \( xc:yellow xc:cyan +append \) -append \
            -bordercolor black -border 1 \
            -filter point -interpolate $i \
            +distort SRT 40,0 -set comment $i i_color_$i.gif
  done
  montage -label %c $pixel $color \
          -background silver -tile 6x -geometry +10+10 \
          pixel_interpolations.png
  rm i_*.gif

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

Oh One more interpolative method under trial. NearestBackground.

Code: Select all

  convert \( xc:red xc:blue +append \) \
          \( xc:yellow xc:cyan +append \) -append \
          -bordercolor black -border 1 \
          -filter point -interpolate NearestBackground \
          +distort SRT 5,0 -scale 400% color_NearestBackground.gif

This uses the images 'background color' instead of the 'average' for between pixels. But you will only ever get a single pixel for the 'actual pixel'.

That is samples which are an 'exact match' (well within floating point error). As such you will only see 'exact matches' is you scale the image by an 'odd' size. That is 1,3,5,7,9 etc. That is for scale 9, the image is enlarged 9 times, And you get one real pixel, plus 8 background color rows and columns between them.

This may be very useful, or may not. Ideas, thoughts, comments?

On idea is for a 'control variable' the controls how close to the 'real pixel', should be regarded as 'near', from 'near zero' as in this case, to 0.25 for the previous 'Nearest' interpolations.

[NicolasRobidoux]

I think that for consistency you should use Average4.

[NicolasRobidoux]

There is a connection between some of these and enlarging by an exact ratio with the "align centers" geometry convention without cropping at the "corner centers" as is usually done with bilinear, and then applying nearest neighbour.
I would guess that someone will find them useful. If not in the "raw" version, by combining some of them.

[NicolasRobidoux]

Although it's cute, I would be surprised if NearestAverage is found to be useful, except for effects. But I'm often wrong in such predictions.

[NicolasRobidoux]

NearestBlend could also be called NearestBilinear, because it's equivalent to enlarging by a factor of 2 with the align centers image geometry convention (doing what makes sense past the usual boundary) and then using nearest neighbour on the result.
There is a connection with interpolatory face split subdivision schemes, but this connection does not give a good name in the current context (I think).

[NicolasRobidoux]

Sooner or later someone will ask whether you can add a slider that determines the "size" of the nearest patch for NearestBackground: 0 = exact match. 1 = regular nearest neighbour. This would also help getting reasonable results, less affected by round off, when enlarging using non-integer ratios.
So maybe you should just add this now?

[anthony]

I think that for consistency you should use Average4.

Yes, Average4, Average3 and Average2, With 'Average' an alias for Average2 -- how does that sound?

Note before this change and still in IMv7 'Average' is actually an Average of 16 neighbours. Which when I explored I found far too over powering.
Thus the addition of the others.

Although it's cute, I would be surprised if NearestAverage is found to be useful, except for effects. But I'm often wrong in such predictions.

It was just something that was sort of 'on the way' toward doing NearestBackground.

[NicolasRobidoux]

...
Yes, Average4, Average3 and Average2, With 'Average' an alias for Average2 -- how does that sound?

At the top you had Average16 and Average9. You mean Average16, Average9 and Average4, with Average standing for Average4?

[NicolasRobidoux]

I persist in thinking that NearestAverage will not be useful for anything.

[anthony]

...
Yes, Average4, Average3 and Average2, With 'Average' an alias for Average2 -- how does that sound?

At the top you had Average16 and Average9. You mean Average16, Average9 and Average4, with Average standing for Average4?

Sorry I thought you meant call Average16 (average of 16 neighbors) Average4. But you mean call them Average16, Average9, and Average4, with 'Average' as a shortcut for Average4.

I persist in thinking that NearestAverage will not be useful for anything.

Probably not. But I thought it less confusing that 'NearestBlend', and a good 'step' to explainging NearestBlend

NearestBlend could also be called NearestBilinear, because it's equivalent to enlarging by a factor of 2 with the align centers image geometry convention (doing what makes sense past the usual boundary) and then using nearest neighbour on the result.
There is a connection with interpolatory face split subdivision schemes, but this connection does not give a good name in the current context (I think).

Note that it is not 'NearestBilinear' as that implied the area between the 'Nearest pixel spot' is a Bilinear or Triangular filter gradient. It isn't.

It is basically equivalent to NearestAverage, but with the area between any two 'nearest spots' a average of those nearest spots (a 2 color average).

The 'interpolatory face split subdivision schemes' is probably a closer description but only a 'level 1 split'. But I didn't know what to call it. It was not a 'fixed' average, so I decided to use 'Blend' as meaning 'average' but not quite in the same way.

A Better name is needed.


I could add NearestBilinear. In fact I could make 'Nearest...whatever...' a special case of ANY interpolation, but with a 'pixel spot' at the center of real source pixel. I could make that spot user definable size! from default 0.25, to near-zero (for NearestBackground).


I specifically wanted to add NearestBackground as a way of telling EWA to use the background color for the 'fallback' if it 'missed all pixels', or had 'zero filter weights'. That is something you should find useful.

Idea...

I think I will do it that way! Remove all 'nearest' (except the original 'NearestNeighbour', and perhaps 'NearestBlend' as it is a little different.) but add a user setting to enable and set the size of a 'nearest pixel spot' for all interpolation methods.

That way ALL interpolations can have a 'nearest spots' added to the results.

What do you think?

Sooner or later someone will ask whether you can add a slider that determines the "size" of the nearest patch for NearestBackground: 0 = exact match. 1 = regular nearest neighbour. This would also help getting reasonable results, less affected by round off, when enlarging using non-integer ratios.
So maybe you should just add this now?

It seems you had the same thought I did when I was adding them and setting that 0.25! (or MagickEpsilon (typically about 1e-10) for nearest Background)

[NicolasRobidoux]

Note that it is not 'NearestBilinear' as that implied the area between the 'Nearest pixel spot' is a Bilinear or Triangular filter gradient. It isn't They are just the average of the nearest 2 or 4 neighbours.

I understood. If this name does not make obvious sense to you, it means it's a bad name.

[anthony]

There is a connection with interpolatory face split subdivision schemes

Do you have a referance? Preferably with a good diagram or text description, rather than pure mathematics. I'm a programmer not a mathematician!

[NicolasRobidoux]

I'm sleep deprived (3 year old's night time shenanigans), but I don't like your Idea.
I think that the most useful stuff is Average16, Average9, Average(4), NearestBlend, and having an option with NearestBackground that adjusts the "width" of the "foreground" neareast neighbour pixel from 0 (+epsilon) (perfect match) to 1 (same as standard nearest neighbour).
This covers everything that I expect to be useful. So, if I was the Very Grumpy Master of the Universe, I'd go with that, and no more. And if I was to drop one more thing, I'd drop NearestBackground altogether.

[NicolasRobidoux]

There is a connection with interpolatory face split subdivision schemes

Do you have a referance? Preferably with a good diagram or text description, rather than pure mathematics. I'm a programmer not a mathematician!

Thinking about it more, I actually think that this connection is not particularly useful. You still want the reference? (Need to dig into my archives.) Even with the best reference I can think of, I don't think the connection will be that obvious, which is why I actually think a pass may be better. (I looked for something making it "obvious" on the web, and did not find anything.)

[anthony]

If I was to drop one more thing, I'd drop NearestBackground altogether.

Actually that was the thing I specifically wanted to add!! For two reasons...

As an alternative way of making Grids of Pixels
http://www.imagemagick.org/Usage/transform/#gridding

And as a method of reporting 'Bad Resampling' in EWA, where you set interpolation to some 'background' and background to a color not present in the image (such as "red") so you can see the pixels that 'went bad'. For which you added an extra 'filter weight check' test.

An example can be seen when using "too small a support"... See expert (owl) note...
http://www.imagemagick.org/Usage/resize ... terpolated