BiCubic Interpolation does not match any known filter!

Questions and postings pertaining to the development of ImageMagick, feature enhancements, and ImageMagick internals. ImageMagick source code and algorithms are discussed here. Usage questions which are too arcane for the normal user list should also be posted here.
NicolasRobidoux
Posts: 1944
Joined: 2010-08-28T11:16:00-07:00
Authentication code: 8675308
Location: Montreal, Canada

Re: BiCubic Interpolation does not match any known filter!

Post by NicolasRobidoux »

Jason S wrote:Consider two ways you could process an image:

1. Apply a background color to the image, then resize it.
2. Resize the image, then apply a background color to it.

Do you expect to get the same result in both cases? If you allow the intermediate image to have transparency outside of [0,1], you can get the same result. Otherwise, you won't (assuming the resampling filter takes negative values).
Unless I'm mistaken, you will not get the same result if you use alpha-multiplied RGB within the filter, like IM does. For the two operations to give the same result, you need "linearity".
Jason S
Posts: 103
Joined: 2010-12-14T19:42:12-07:00
Authentication code: 8675308

Re: BiCubic Interpolation does not match any known filter!

Post by Jason S »

NicolasRobidoux wrote:Did you get nonsense results when you used bilinear on the alpha with another filter on the colour channels? My point is to use a "safer" (monotone, tight support...) filter on the alpha.
I don't recall, and I don't have a good example at the moment. It might be that it's only a significant problem if the filters are incompatible in a certain way. Maybe a "small" color filter value can't correspond to a "not small" alpha filter value? Or not; that's just a wild guess.
(Also: You fed alpha multiplied colours into the filter, and "unmultiplied" them after resampling? ...)
Yes.
NicolasRobidoux
Posts: 1944
Joined: 2010-08-28T11:16:00-07:00
Authentication code: 8675308
Location: Montreal, Canada

Re: BiCubic Interpolation does not match any known filter!

Post by NicolasRobidoux »

NicolasRobidoux wrote:Unless I'm mistaken, you will not get the same result if you use alpha-multiplied RGB within the filter, like IM does. For the two operations to give the same result, you need "linearity".
I am mistaken. Let me fix this in my next post.
NicolasRobidoux
Posts: 1944
Joined: 2010-08-28T11:16:00-07:00
Authentication code: 8675308
Location: Montreal, Canada

Re: BiCubic Interpolation does not match any known filter!

Post by NicolasRobidoux »

Resize first then flatten with constant background will only give the same result as flatten first then resize if you use alpha-multiplied RGB in the filter, and you use the same filter for alpha as for RGB (ignoring issues of zero division).
So, assuming that this property is worth fighting for (and I think it very well may be):
Anthony and Cristy You are vindicated!
Ignore my rubbish about clamping alpha to [0,1] in intermediate computations and using a different filter for alpha VS RGB.
Jason Summers Thanks a million for sending me on the right track.
NicolasRobidoux
Posts: 1944
Joined: 2010-08-28T11:16:00-07:00
Authentication code: 8675308
Location: Montreal, Canada

Re: BiCubic Interpolation does not match any known filter!

Post by NicolasRobidoux »

magick: The following version puts the discontinuity right where it should be, at 0 on the left

Code: Select all

static inline MagickRealType MagickReciprocal(const MagickRealType x)
    {
      MagickRealType signx = (x<(MagickRealType) 0.0 ? (MagickRealType) -1.0 : (MagickRealType) 1.0);
      return((signx*x>MagickEpsilon ? (MagickRealType) 1.0/x : signx*((MagickRealType) 1.0/MagickEpsilon));
    }
User avatar
magick
Site Admin
Posts: 11064
Joined: 2003-05-31T11:32:55-07:00

Re: BiCubic Interpolation does not match any known filter!

Post by magick »

It works! We'll get your patch into ImageMagick-6.7.7-7 Beta by sometime tomorrow. Thanks.
NicolasRobidoux
Posts: 1944
Joined: 2010-08-28T11:16:00-07:00
Authentication code: 8675308
Location: Montreal, Canada

Re: BiCubic Interpolation does not match any known filter!

Post by NicolasRobidoux »

Although the
resize then flatten = flatten then resize when the background has a constant colour
criterion is a convincing reason for preferring the current IM set up, I am not convinced that it should always be used.

I think it's the best choice for IM. But I may not use it with all the methods I program elsewhere, in particular the locally bounded ones (those that never have "overshoots"), like the nonlinear LBB-nohalo method I programmed (and will further develop) for GEGL and VIPS. But then, maybe I'll eventually decide to always use this. I don't really know.
User avatar
anthony
Posts: 8883
Joined: 2004-05-31T19:27:03-07:00
Authentication code: 8675308
Location: Brisbane, Australia

Re: BiCubic Interpolation does not match any known filter!

Post by anthony »

Jason S wrote:ImageWorsener used to have a feature to let you use a different filter for the alpha channel, but I removed it, because it produced nonsense results. I saw no way to prevent it from taking pixels that have no meaningful color, and making them visible.
Very nice page about bi-cubic interpolators, Though you don't specify what interpolator you use - or prefer

For your page..
Before IM v6.3.5-3 it used a blurry Spline.
This was changed to a non-blury 'extreme cardinal' cubic(0,1), at my suggestion.
But I did not test thoroughly enough after that change to notice it was so extreme.
As of the recent IM v6.7.7-6 release (just a couple of days ago) it is now Catmull-Rom cubic(0,1/2)
and with next release IM v6.7.7-7, 'bicubic' as a setting is depreciated (but will work) with 'catrom' the prefered setting to select a bicubic interpolator.

On a similar note (not yet done - but probably today) Resampling filter 'Cubic' will be replaced with 'Spline'.
But again the name 'Cubic' will be retained (and by default mean Spline) so as to refer to selection of a Cubic Filter via expert B,C settings (and reported in "filter:verbose" output)
Anthony Thyssen -- Webmaster for ImageMagick Example Pages
https://imagemagick.org/Usage/
User avatar
anthony
Posts: 8883
Joined: 2004-05-31T19:27:03-07:00
Authentication code: 8675308
Location: Brisbane, Australia

Re: BiCubic Interpolation does not match any known filter!

Post by anthony »

resize then flatten = flatten then resize

You should note that as two different operations is used, this would only work with HDRI (floating point data) versions of IM.

Otherwise the alpha gets 'clamped' anyway because the data is stored into integers between operations, so the former 'resize then flatten' will fail.
Anthony Thyssen -- Webmaster for ImageMagick Example Pages
https://imagemagick.org/Usage/
User avatar
anthony
Posts: 8883
Joined: 2004-05-31T19:27:03-07:00
Authentication code: 8675308
Location: Brisbane, Australia

Re: BiCubic Interpolation does not match any known filter!

Post by anthony »

NicolasRobidoux wrote:magick: The following version puts the discontinuity right where it should be, at 0 on the left

Code: Select all

static inline MagickRealType MagickReciprocal(const MagickRealType x)
    {
      MagickRealType signx = (x<(MagickRealType) 0.0 ? (MagickRealType) -1.0 : (MagickRealType) 1.0);
      return((signx*x>MagickEpsilon ? (MagickRealType) 1.0/x : signx*((MagickRealType) 1.0/MagickEpsilon));
    }
Wouldn't copysign() be better than using signx? It will then leave things to the compiler to work out the best way.

Also there is also a MagickHuge definition, though it is current defined as being much larger than 1/MagickEpsilon
I use it in distort, morphology, and resample (EWA) as limit tests.

PS: its value should be 1/MagickEpsilon but it was made larger, which makes resampling near perspective horizons much-much slower (less early abort) than it should! In otherwords, someone changed it, with detrimental effects in extreme distortions!
Anthony Thyssen -- Webmaster for ImageMagick Example Pages
https://imagemagick.org/Usage/
User avatar
magick
Site Admin
Posts: 11064
Joined: 2003-05-31T11:32:55-07:00

Re: BiCubic Interpolation does not match any known filter!

Post by magick »

Anthony, we'll get a patch in Subverison to define MagickHuge to 1.0/MagickEpsilon.
NicolasRobidoux
Posts: 1944
Joined: 2010-08-28T11:16:00-07:00
Authentication code: 8675308
Location: Montreal, Canada

Re: BiCubic Interpolation does not match any known filter!

Post by NicolasRobidoux »

anthony wrote:Wouldn't copysign() be better than using signx?
I did not use it because TTBOMK copysign is not universally available. Can I assume it is within ImageMagick? It is not used in any .c file of MagickCore, so I figured it is an off-limit function.

Also, there is the issue of MagickRealType possibly being float, and wanting to avoid casts back to float from double (double to float is not as much of an issue), although maybe this is not much of an issue with current compilers/chips. Although this could be fixed with a global macro checking the value of MagickRealType.

(Embarassing anecdote: Laying on the floor next to my sick 3 year old this morning, in my half sleep way before reading your email, I actually dreamed about how great it would have been if copysign and a few similar functions had made it into the original C standard libs... I have very pedestrian alternate reality fantasies.)
Last edited by NicolasRobidoux on 2012-06-07T05:24:31-07:00, edited 3 times in total.
NicolasRobidoux
Posts: 1944
Joined: 2010-08-28T11:16:00-07:00
Authentication code: 8675308
Location: Montreal, Canada

Re: BiCubic Interpolation does not match any known filter!

Post by NicolasRobidoux »

Maybe MagickHuge should be smaller, 1.e-7 for example, and MagickEpsilon should be the reciprocal of MagickHuge, instead of the other way around.
User avatar
magick
Site Admin
Posts: 11064
Joined: 2003-05-31T11:32:55-07:00

Re: BiCubic Interpolation does not match any known filter!

Post by magick »

The copysign() method is C99 so we can't use it, we still support C89 compilers.

We have
  • #define MagickEpsilon ((MagickRealType) 1.0e-16)
    #define MagickHuge ((MagickRealType) 1.0/MagickEpsilon)
What should they be under your proposal?
NicolasRobidoux
Posts: 1944
Joined: 2010-08-28T11:16:00-07:00
Authentication code: 8675308
Location: Montreal, Canada

Re: BiCubic Interpolation does not match any known filter!

Post by NicolasRobidoux »

magick wrote: We have
  • #define MagickEpsilon ((MagickRealType) 1.0e-16)
    #define MagickHuge ((MagickRealType) 1.0/MagickEpsilon)
These are fine. (My reciprocal comment was definitely "out there". Apologies.)
However, if an important use is to limit how much work distort does near horizons and like singularities, something like
  • #define MagickEpsilon ((MagickRealType) 1.0e-7)
    #define MagickHuge ((MagickRealType) 1.0/MagickEpsilon)
may be good. Anthony should be the best judge of this.
Post Reply