BiCubic Interpolation does not match any known filter!

[anthony]

While looking at interpolation methods. I can't seem to work out exactly what bi-cubic is!

Especially as it seems to generate a very very strong 'negative' halo (deep first lobe).

test image (magnified) -- from IM examples resize pages

Code: Select all

convert xc: -bordercolor gray15 -border 2x0 pixel.gif
convert pixel.gif -scale 150 pixel_mag.gif

This is a magnification of the image using a bicubic interpolation (using IMv7 - see IM Examples, see interpolation for IMv6 methods - same results though)

Code: Select all

magick pixel.gif -interpolate BiCubic -interpolative-resize 150 pixel_bicubic.png
im_profile pixel_bicubic.png pixel_bicubic_profile.png

On the other hand these are the result for a Catrom filter.

Code: Select all

convert pixel.gif -filter catrom -resize 150 pixel_catrom.png
im_profile pixel_catrom.png pixel_catrom_profile.png

As you can see the bicubic profile has a VERY deep first lobe. Far too deep for catrom. And it does not show a disjoint look that you would get for a lagrange filter. In fact NO filter I know of is anywhere as deep as catrom!

It looks to me that bicubic is currently broken!!!! And probably has been for a long time!

[fmw42]

Check and make sure that Catrom and Keys Cubic Convolution are really the same and the latter not Bicubic

see
http://en.wikipedia.org/wiki/Bicubic_interpolation

http://www.google.com/url?sa=t&rct=j&q= ... 9DDbPZ0uRg

http://www.paulinternet.nl/?page=bicubic

[NicolasRobidoux]

Anthony:

Could you tell me where the source code is for -interpolate and -interpolative-resize? Is it in resize.c? Approximate line number? (As you know, I live with IM 7 svn these days.)

-----

(Sorry if my lecture is tedious: I am tired, hence a lousy teacher.)

Part 1:

Part of the confusion, I think, is that bicubic generally refers to a family of explicitly 2D scheme which involves specifying cross derivative (note that I am not impressed with the Wikipedia discussion, even though it is literally correct). However, some bicubic schemes (for example Catmull-Rom and Hermite) are actually tensor methods as well, that is, you can get the exact same scheme through a fairly trivial tensor (what you call "orthogonal") implementation of a 1D method. To make things even more confusing, when the basis functions are associated with a partition of unity (basis functions that sum to 1 everywhere) you can also get the exact same result by filtering or by multiplying the basis functions by coefficients. This is the case, for example, with Catmull-Rom and Hermite.

That is to say: There is more than one way to get the same thing. You can't go: Different procedure/formula -> Bad.

The 2D impulse response, however, tells the whole story when the method is linear. (Which is the case with almost everything implemented in IM.)

Part 2:

One of the drawbacks of bicubic referring to a family of schemes is that ... there is more than one!

I don't know which bicubic IM wants to get. (Well, of course I know you want Catmull-Rom.)

Personally, I don't care about any bicubic other than Catmull-Rom (I don't even care much about Hermite, which turns out to be a bicubic scheme when used in a tensor fashion, whether filtering or multiplying coefficients by basis functions, but this may be idiotic mathematical bias). (Warning: The term "Hermite" is used to denote quite different things in the literature. One could describe what IM does as Hermite bicubic with vanishing first and cross-derivatives, and Catmull-Rom can be described as an Hermite bicubic with different derivative choices.)

So, which bicubic (other than the above two) do you want? Do you want any other one? You would not hear me complain if you went "Vaguely defined troublemaker scheme -> Bye!"

(Reader: If you have a strong opinion about this, it is time to set me straight!)

Part 3:

Other confusion: Bicubic, if one comes from bilinear, suggests a tensor scheme built from a 1D piecewise cubic method. Although some bicubic schemes (as understood, e.g., by the Wikipedia entry) can be constructed this way (Catmull-Rom, Hermite, ...), not all of them can. On the other hand, any tensor of a linear piecewise cubic 1D scheme with the breaks at the right place can be expressed as a bicubic. Which brings me back to: What is it that you want? Zoom history preservation? To have a scheme with a name that resembles a well-known Photoshop scheme? ???

-----

I'll double check the above when I'm more awake.

P.S. In the above, I assume that you are not downsampling.

[anthony]

Anthony:

Could you tell me where the source code is for -interpolate and -interpolative-resize? Is it in resize.c? Approximate line number? (As you know, I live with IM 7 svn these days.)

Interpolative Lookup is actually performed in the "pixel.c" module.
Interpolative Resize (-interpolative-resize is not the final name) is in "resize.c".

In IMv6 it is identical to "Adaptive Resize" except that only uses 'mesh' interpolation. In Imv7 Adaptive Resize is just a
call to Interpolative Resize, but with 'mesh' as the interpolation method. This is why it could probably be 'backported' easily into IMv6, though it is a new operator.

The current operator -interpolative-resize will probably be part of a merger of all 'non-standard' resize operations into
a -resize-special {method}. This will make the finding of documentation on different resizes, and selection of different resize methods a lot easier for new users. Currently the options are spread out and hard to find.

The old resize options will have a 'warning and redirection' added (much like some already re-directed). This is scheduled for Beta development, when most new operations and re-development of old options will happen.

[anthony]

I'll double check the above when I'm more awake.

P.S. In the above, I assume that you are not downsampling.

Upsampling from a 5 pixel image! It generates reasonably accurate facsimile of the filter graph.

I am basically just trying to understand what is implemented, and if it is 'good' or needs to be changed. From the depth of the filter the latter apears to be the case, but I don't want to change it for changes sake.

As their are so many variants, is it any wonder people get confused! I mean in the earily days on IMv6 'Spline' was used as bicubic. Yes it is a cubic function, be one that is way to blurry to be 'typically' used or represent a 'bicubic' interpolation, which is why it was replaced.

So perhaps i should leave 'bicubic' as it is... a undefined tensor cubic interpolation.
and just add catrom and hermite (as a smooth triangle filter) as other interpolations.


I also not that other interpolations should also be made available, but perhaps I should return to this again, after I finish IMv7 Global Percent Escapes. (probably IMv7 Beta devlopment).

[NicolasRobidoux]

...In the above, I assume that you are not downsampling.

What I wanted to communicate with this is that some of my statements, namely that you can get the same exact result for some method by filtering or by doing a procedure which most people will describe as interpolating, and which is equivalent to multiplying, for example, basis functions by pixel values, are only applicable if you don't downsample. The equivalence breaks down if you locally "reduce size in any direction".
I'm pretty sure you know this already, but in confusing times dotting i's twice is often a good thing. (This is a very very very bad joke: http://en.wikipedia.org/wiki/Diaeresis_%28diacritic%29.)
P.S. It is possible to preserve the equivalence if you don't enlarge the filter support when downsampling. See below.

[NicolasRobidoux]

Anthony:

I don't know the big picture and the details of -interpolate and -interpolate-resize, but I want to make a "big picture comment" here.

Are you sure that you need to add more interpolative methods, or add interpolate-resize? (Except for possibly very few "special case" methods.)

The reason why I am asking is that by and large they are redundant in some sense.

General assumption (which actually is directly applicable to most of what people want to do):
The "interpolate" procedure is equivalent to taking the sum of the basis functions times the pixel values, and the basis functions have the usual symmetries of a uniform grid. (Although this is not explicit in the bicubic Wikipedia for example, for all reasonable choices of derivatives it can be reframed so that it satisfies this condition. The discussion of how/why is not something I have time for right now, and I don't think it's useful.)

Technical condition
Your basis functions (with coefficient 1) sum to a constant everywhere (except possibly past the "boundary").

(Not directly checked: Based on how I would implement these methods without making my life hard. But I'm pretty sure that) This is true of: Triangle, Catrom, Hermite, Lagrange, Quadratic, Box, Point and I actually believe that it's true for all Keys splines (would need to check, but I'm pretty sure). This is not true for windowed Sinc methods unless you refactor them BIG time.

Consequence
When not reducing size, "interpolating" gives the exact same result (within roundoff) as "filtering". If reducing size, the two give the same result IF you don't rescale the filter extent as is normally done when downsampling. (Roughly, this is equivalent to having blur=ratio when doing -resize (ratio*100)%.)

Practical consequence Just add an option to resize that allows one to nail the "window size resizing factor" at exactly 1 (the value it has when enlarging) and you should get "everything" you want as far as resize goes.

-----

Now, maybe what you're after is the ability to do this, or something like this, with distort type operations, which you can't get through the above -resize mod.

Wild and a bit shaky idea
It would appear to me that the most efficient solution is to implement the clean extension of orthogonal methods to arbitrary warps we discussed privately (the novel modification of EWA, which would have a very similar code structure to distort, just slightly different math and Sinc would remain Sinc). Then, you get a method which behaves exactly like resize, for every filter with large enough extent (almost all of them, even Triangle), when resizing, but which adapts to warps, whether they downsample in one or both directions, or not. And using the "don't resize the filter extent" trick I suggested above, you'd get exactly the interpolate behavior when resizing down. What you would not get is the exact same answer as a reasonable implementation of interpolate when doing warps with a rotation component, but I'm not sure that the answer would not be as good. On the other hand, you'd get "everything" in one fell swoop: cloning distort and changing something like 200 lines of code not counting API mods.

Warning: I have not even computed the needed math formulas for this. But I'm pretty sure I can in a reasonable amount of time ... that I don't have now.

[NicolasRobidoux]

Anthony: I visually compared the plot you give for the Catmull-Rom cardinal basis function with the one given in Figure 16.3 p.120 of the Masters thesis of my student Chantal Racette, computed independently. They look the same to me. http://arxiv.org/abs/1204.4734
And the preliminary results of my other student Adam Turcotte suggest that there is nothing wrong with Catmull-Rom in ImageMagick (well, through -resize). What you could do is enlarge with the interpolate Catmull-Rom and the -resize Catmull-Rom and see if you get the same result. You should (if alignment/abyss/... correspond).

-----

And yes, the "bicubic" you show along it, whatever it is, does have a very deep overshoot.

[NicolasRobidoux]

Anthony: I'm looking at pixel.c Line 4174 SVN-7995.
Let's assume I understand what's going on. Then:
Whatever this bicubic is, it's junk. (In addition, the code is not structured maximally efficiently, but this is another story.)
Reason: Any good bicubic should interpolate an affine function by returning the affine function. If it does not do that, it's is not exact on linears (as this property is usually called) and very few such schemes are worth keeping.
So, let's see what happens with the following affine function: z(x,y) = x. (Hardly gets any simpler than that.)
Within the for (i=0; i<4; i++) loop, u[0] = (1)-(-1) = 2, u[1] = (-1)-2 = -3, u[2] = 2 and u[3] = 1 (with the right x_offset).
The fact that u[0], the coefficient of dx^3 in v, is not zero, tells us right away that it's broken.
Let's complete the computation to make it clear. v = 2*dx^3 + -3*dx^2 + 2*dx + 1 for every i.
Consequently (moving past the for loop):
u[0]=0, u[1]=0, u[2]=0, u[3] = 2*dx^3 + -3*dx^2 + 2*dx + 1 which is not equal to dx + 1, the result we should get if this was a scheme exact on linears.

-----

I would guess that if you enlarge a linear gradient a lot you'll see it oscillate.

-----

Assuming that I did not make a mistake, how do you want to fix this? Again, this depends on the choice of bicubic you want to implement. Catmull-Rom? Hermite? Unless you move into nonlinear schemes (you don't want to) these are the only two bicubics (in the sense of Wikipedia) I would recommend. But I've not looked around to see if there were reasonable alternatives. (Note that Hermite is NOT exact on linears. But it does not overshoot, and it's smooth at the small scale as well as pretty "tight", and for these reasons it appears that you forgave it.)

[fmw42]

I really have no idea what the bicubic filter/interpolation is. Perhaps some cardinal spline.

You can call me old fashion (and a nit-picker), but I am not sure why Catmull-Rom get so much credit for the 2D image interpolation rather than Keys. I am assuming the two are equivalent. It is clear that Catmull-Rom published curve splining techniques in 1974, but I do not know of any references to its use for filter/interpolation prior to the 1981 paper of Keys for his cubic convolution. Correct me if I am wrong.

Back in my day, for image processing, we had just nearest neighbor, bilinear and keys cubic convolution both for downsampling and upsampling (minify/magnify).

see references in
http://en.wikipedia.org/wiki/Cubic_Hermite_spline
http://en.wikipedia.org/wiki/Bicubic_interpolation

Don't get me wrong. I think all the work you guys have done to advance the state of the art is fantastic.

[NicolasRobidoux]

For better or worse everybody calls it Catmull-Rom now. When in Rome...
To me, "Catmull-Rom" is simply tensor Hermite interpolation with derivatives set by centered differences. There has to be some Frenchman or Russian or ??? who had this figured out a long long long time ago. If I was the gambling type or sufficiently drunk, I'd put my money on the 19th Century.

[NicolasRobidoux]

Anthony: Lots of "bicubic" code got copied around between apps. Maybe you can track down a similar piece of code in another software package, and find out what went wrong?

[anthony]

Anthony:

I don't know the big picture and the details of -interpolate and -interpolate-resize, but I want to make a "big picture comment" here.

The reason why I am asking is that by and large they are redundant in some sense.

I agree that in the "Big Picture" Interpolation is not greatly important. Though for some things where scaled lookup is not available, such as FX equations, CLUT color replacement, and Displacement/Distortion Mapping, Interpolation is what is used.

Also when I was re-designing resize filters, the interpolations was something I ignored for the time being. just as I previously initially ignored resize filter handling when first adding Distortions and EWA resampling. It has been bugging me that I never completed the task by looking at Interpolative filters.

Consequence
When not reducing size, "interpolating" gives the exact same result (within roundoff) as "filtering"....

Practical consequence Just add an option to resize that allows one to nail the "window size resizing factor" at exactly 1 (the value it has when enlarging) and you should get "everything" you want as far as resize goes.

Note quite. A few interpolations are 'blurring'. Spline and Average for example.
More importantly they do so in very predictable ways. Perfect blends for example.

Also some do apply 'non-tensor' interpolation. Mesh for example divides the inter-pixel area into two flat triangles.
Though at this time no 'cylindrical interpolation' exists, that is also possible.

Interpolation is not typically used for resizing, or down sampling. It is typically used for near unity, and upsampling only,
but also when scaling is very difficult to calculate (displacement maps, and Shepard's Distortion)

More important it is used as 'fast lookup' by specific image processing operations, such as when super sampling.

You yourself benefited by the expanded 'methods' provided for resampling filters, This is the same type of expansion but for unscaled interpolation. Right now it is more an 'exploration' of possibilities.

[NicolasRobidoux]

...
Not quite. A few interpolations are 'blurring'. Spline and Average for example.
More importantly they do so in very predictable ways. Perfect blends for example.

What I meant is that an "interpolatory" set up (implicitly equivalent to sum the pixel values times the basis functions) set up will give the same result as a "filtering" set up. If your basis functions introduce blur in one set up, they'll introduce blur in the other, and conversely an "interpolatory" filtering method will remain interpolatory if programmed as a -intermpolate or -interpolate-resize method. The key point is that they'll give the same result (if you set things up with the corresondence in mind, and maybe even if not). Which is why I suggested going ahead with a novel approach that extends orthogonal filters to any situation that EWA can handle, and also suggested a simple way of making both EWA and the new method behave like a -interpolate method.

I am not saying that my proposal is necessarily "right". But I felt that you should be aware that you may be spending a considerable amount of effort adding features that only add something in unusual situations. Which, of course, is a good enough reason to do it.

[anthony]

I really have no idea what the bicubic filter/interpolation is. Perhaps some cardinal spline.

You can call me old fashion (and a nit-picker), but I am not sure why Catmull-Rom get so much credit for the 2D image interpolation rather than Keys. I am assuming the two are equivalent. It is clear that Catmull-Rom published curve splining techniques in 1974, but I do not know of any references to its use for filter/interpolation prior to the 1981 paper of Keys for his cubic convolution. Correct me if I am wrong.

A Key's Cubic is a family of filters, as are Cardinals. 'The' keys cubic is the Catmull-Rom filter.

Found the matching cubic function for the one implemented. It is an extreme Cardinal bi-cubic filter.
Good guess, Fred!

Code: Select all

convert pixel.gif -filter catrom -define filter:c=1 -define filter:b=0 -resize 150 miff:- |
    im_profile -  pixel_cardinal_profile.png

Nicholas yes it is not 'linear' preserving as it is not a Keys filter (fred that is a properity of linear filters)

This Extreme Cardinal interpolator, is not I believe a good choice.

And yes I think Catrom and Hermite as being the better cubic interpolators. Catrom should be 'standard' cubic.

Hermite is basically a smooth interpolation function for 'sharp color changes'. Basically is like 'bilinear' but flat at the actual pixel center, rather than producing a sharp 'ridge' between pixel centers.


The way out of this 'morass' is now clear (at least to me)..

• rename the current 'bi-cubic' as 'cardinal' (much as the older 'bicubic' became 'spline')
• add 'hermite' and 'catrom'
• make 'bicubic' an alias for 'catrom' (not the original 'cardinal')
• never use 'bicubic' as a interpolation in documentation (except as a historical footnote)

ASIDE: a similar thing could be said for 'Cubic' filter, renaming it 'Spline'. But keeping 'Cubic' as a base filter name (by default referring to 'Spline' for backward compatibility, that is only used for generating filters using expert functions. Much like the FastSinc filter function.