Why EWA/circular scaling operators?

[hjulenissen]

I do understand that non-separable scaling is a superset of separable scaling, so that non-separable should have the potential to be as good, or better than separable scaling. But what is the benefit of a radially symmetric function vs a "carthesian" (tensor?)? It would seem that the sampling grid allows for more high-frequency information along diagonals than horizontally/vertically, so why use scaling that suppress it?

I am only interested in uniform image resampling, not e.g. rotation. I guess that a rotationally symmetric kernel might be handy in some way if you are to rotate the image.

kind regards
Hjulenissen

[BryantMoore]

The best way to process a two dimensional signal is with a two dimensional function as I understand.

[NicolasRobidoux]

Quick imperfect answer:
1) If you believe that resampling filters should be based on the so-called "ideal low pass filter", namely the one that drops all frequencies above a threshold and keeps all those below a threshold intact, which in 1D gives you the Sinc filter (with infinite extent), then in 2D you want to base your filters on the radial Jinc function.
The main difference between tensor (orthogonal) Sinc and radial Jinc is that Jinc kills the "checkerboard mode" (alternating black and white squares), while the equivalent tensor Sinc filter does not, because the checkerboard mode is at the threshold of the frequency cut off both horizontally and vertically, and a tensor filter treats the two directions independently. This is a consequence of the support of the filter in 2D Fourier space being a disc in the case of Jinc, and a square in the case of tensor Sinc. The checkerboard mode sits at the corners of the square.
This can actually be seen: Tensor filters with negative lobes (those that attempt to mimic tensor Sinc somehow) do not dampen the checkerboard mode enough, and as a consequence diagonal lines and interfaces are enlarged in a fairly jagged way. With EWA filters, diagonal lines are generally smoother.
Another example: If you reduce http://upload.wikimedia.org/wikipedia/c ... rtrait.jpg down to, say, 403x600 with a tensor filter and you zoom into the result, you will see tiny checkerboards in some of the lighter areas of the eyes. If you filter the same image with an equivalently sharp EWA filter, the checkerboards are basically gone. (Advice: Downsample through linear light (RGB or XYZ) otherwise the eyes change colour big time: They turn to "rust".)
2) Resampling filters are not only used to resize. They are also used to warp ("distort"). Although Anthony and I have a pretty good idea of how to extend orthogonal filters so that they can handle general warping elegantly, we do not believe it's been done cleanly before---if you know references or implementations, please let us know---and consequently this would be pushing the state of the art, and could fail, in the sense that the result may not be better than EWA, except when the transformation is a rotation by an angle which is a multiple of 90 degrees. It also would require a fair amount of programming. (Could somebody fund us to do this?)
My understanding is that (clamped) EWA is pretty much the state of the art w.r.t. general warping. Correct me if I'm wrong.
3) They work. IMHO, enlarging with -filter LanczosSharp -distort Resize gives beautifully artifact free results, of a quality unmatched by any -resize filter in the "artifact/sharpness" ratio department. The downfall of the EWA filters, however, is that none of the good ones are interpolatory. But this actually is not the crime some make it to be. For example, the default IM -resize filter is, in most situations, (tensor) Mitchell (which stands for the Mitchell-Netravali Keys cubic), which is not interpolatory either. This filter was chosen, long long ago, by a panel of experts, as being "balanced". IMHO, EWA LanczosSharp is even more balanced. ("Maximally balanced". Oximoron?)
EWA filters don't all work better than tensor ones, although there is one place where they shine: moire reduction when downsampling. Which of course makes complete sense from a frequency response viewpoint: Come on Jean Baptiste Joseph Fourier! Clip these corners.

[hjulenissen]

Thank you for a lenghty reply. I am still sceptical though. Moire (and dither?) seems like image flaws to me that should be be fixed by targeted image processing rather than generating an infinite list of named scaling functions with complicated differences that may fix one or the other image flaw at the cost of some distortion to the desired signal

So it would seem from the frequency response plots + your description of the practical advantages that awindowed approximation to the jinc response (circular) can be fairly well approximated by a 2-d diagonal notch filter (deep null at diagonal frequencies of sqrt(2) in series with a regular windowed sinc (orthogonal) type scaling. This might not be computationally efficient but at least the various aspects of todays scaling would be more "modular" to the advanced user. Of course, the two functions could be wrapped into one apparent function for those ththat prefer todays interface.

I come from a 1-d signal processing background. My instinct is to maximize the information that can be recorded/reconstructed error-free. For 1-d that is the (physically unrealizable, but often reasonably approximated) sinc. A tensored extension into 2-d would seem to allow 4*r*r/(pi*r*r) more perfectly reconstructable 2-d bandwidth than the corresponding "jinc". If images were really captured with an optical jinc function, then another jinc function might be optimal in reconstruction/resampling. If the capture function was a tensored sinc, then that might be the optimal reconstruction/resampling function. As is well known, neither function is realizable in a camera, display or printer. So perhaps any image scaling will be part image restoration, part pre-filtering compensating for display limitations, and part purely mathematical resampling?

Kind regards
H

[NicolasRobidoux]

The frequency content supported by a uniform grid may not be isotropic, but the frequency content of "nature" is not supported by a uniform grid.

[hjulenissen]

The frequency content supported by a uniform grid may not be isotropic, but the frequency content of "nature" is not supported by a uniform grid.

I dont follow you on that one. We cant know what the frequency content of "nature" (any given scene) will be before hand. What we do know is that the sampling theoreme allows us to sample and recreate a "bandlimited" version of that scene.

If the scene is "smooth" then it can in principle be sampled and recreated with exactly zero loss. For digital audio, the digital signal path can be approximated as a lowpass-filter (excluding quantization error). If camera->display could be approximated as a 2-d spatial lowpass filter would it be better to have a circular filter of radius r than a rectanguøar filter of sides 2r? Knowing that reliably reconstructable signal components are thrown away?

[NicolasRobidoux]

...My instinct is to maximize the information that can be recorded/reconstructed error-free...

Let's start with enlarging.
If your goal is to maximize the information that can be reconstructed error free, simply enlarge with nearest neighbour (convert {input} -filter Point -resize {width}x{height} {output}). It is then trivial to reconstruct the original image with 100% accuracy (even if the enlargement is not by an exact integer ratio). All you have to do is embed the original width and height in the medadata.
No approximation of the infinite support Sinc filter. No boundary effects. No clipped over- and undershoots.
Just perfect.

[NicolasRobidoux]

Just to make sure it's clear:
You can eliminate half of the "infinite list" from consideration by never using -distort Resize.
If you stick to -resize, you only ever use tensor filters. Never EWA. When resizing, EWA is only obtained with -distort Resize (or, at least, with some variant of the distort command).
-----
Now, in case you are enclined to try methods from the remaining infinite list, you can do raw or windowed tensor Sinc filtering with up to 8 lobes which, when enlarging, gives you a 16x16=256 taps filter.
http://www.imagemagick.org/Usage/resize/#filter_lobes
It would seem to me that this could be the main component of a reasonable approximation of what I understand you would find "ideal".
In order to minimize clipping artifacts, esp. when enlarging, please use an HDRI version of ImageMagick, even if your input and output images are only 8bpc.

[NicolasRobidoux]

@Hjulenissen:
I actually am not interested in theoretical discussions about this. So, I'll stop egging you on.
If someone else wants to discuss "in principle" pros and cons of various approaches with you, I'll watch and see if I learn something that helps me program something useful.
But I'll stay out of it (as much as I can stay out of things ).
NNTR
P.S. In case this is where some of your comments originated: I do realize that http://www.imagemagick.org/Usage/resize/#nicolas is a bit of a mess, that it contains what one may call "unfinished experimental methods", and that not absolutely every bit of advice has been quadruple checked for worst case scenario robustness as well as bang for the buck (or bang for the complication). With Anthony Thyssen's help, I'm working on making it better. And I am performing some of the triple checking as fast as I can.
Hopefully, it will be more solid in a week or three.
This being said, I think that it always will contain somewhat unconventional advice. I truly do believe that some of these "unusual methods" are actually better than standard ones. But I may be wrong. Or someone else may come up with something even better.
Cheers.

[hjulenissen]

...My instinct is to maximize the information that can be recorded/reconstructed error-free...

Let's start with enlarging.
If your goal is to maximize the information that can be reconstructed error free, simply enlarge with nearest neighbour (convert {input} -filter Point -resize {width}x{height} {output}). It is then trivial to reconstruct the original image with 100% accuracy (even if the enlargement is not by an exact integer ratio). All you have to do is embed the original width and height in the medadata.
No approximation of the infinite support Sinc filter. No boundary effects. No clipped over- and undershoots.
Just perfect.

Sure, any invertible function does not reduce the amount of information, provided that the necessary info to do the inversion is transmitted as side-info. That was not where I was getting at, though.

Referring to Figure 4 and Figure 5 of Gustafssons thesis. Are these the ideal (unrealizable) end-to-end function for the camera->display system? If so, one would assume that the sampling theorem would guarantee that e.g. an idealized 640x480 camera connected to an idealized 1024x768 (or 320x240) display would approach the _analog_ lowpass function (corresponding to the minimum of those two resolutions) suggested by the figures, if a corresponding resampler using a similar prototype function was used. Lots of ifs there.... Given all of that, would it still be preferreable to "throw away" some analog bandwidth on a circular rather than square passband? This is the core of the (granted theoretical) question that puzzle me.

I actually am not interested in theoretical discussions about this. So, I'll stop egging you on.
If someone else wants to discuss "in principle" pros and cons of various approaches with you, I'll watch and see if I learn something that helps me program something useful.
But I'll stay out of it (as much as I can stay out of things ).

Fair enough. I take it that the reason why circular prototype functions are used in IM is not a fundamental, provable, truth such as the one supporting the Shannon-Nyquist sampling theoreme, but rather an empirical observation that it "just seems to look better"? That is a very good reason to choose one algorithm over another in a piece of software, but does little to ease my curiosity

Ah, well, at some time I might be able to read and comprehend one of M. Unsers papers touching this topic:
http://bigwww.epfl.ch/publications/

-h

[anthony]

I do understand that non-separable scaling is a superset of separable scaling, so that non-separable should have the potential to be as good, or better than separable scaling. But what is the benefit of a radially symmetric function vs a "carthesian" (tensor?)? It would seem that the sampling grid allows for more high-frequency information along diagonals than horizontally/vertically, so why use scaling that suppress it?

I am only interested in uniform image resampling, not e.g. rotation. I guess that a rotationally symmetric kernel might be handy in some way if you are to rotate the image.

kind regards
Hjulenissen

Short answer... Speed.

It is a lot faster to resize images in two passes using 1-d filters, than to resize in 1 -pass using 2-D filters.
It can in fact be an order of magnitude faster.

This is also why Blur's are implemented using 2-pass 1-dimensional Gaussian, than 1-pass 2-dimensional Gaussian convolutions. But the Gaussian Filters/Kernels are separable. Most filters are not.

That is it in a nut shell -- speed.

Additional factor... Easer to Implement, and less likely to get wrong

Distort's EWA implementation was plagued by bluriness at low distortions, due to a 'sign' bug, and appropriate 'clamping' of the ellipse size (very little good implementation documentation is out there).

But then Tensor resizing can still be tricky, and in fact a lot of web browsers do have it wrong, or have a very lazy implementation. See How web browsers resize images for someone trying to figure out how browsers implemented their image resizing function.



Details of EWA, from an implementation point of view...

EWA (any -distort method by default) resampling is a 2-dimentional (cylindrical filtered), single pass distortion, resize is just a special case of image distortion (scaling - perhaps with a translation if wanted).

The -distort Resize method is specialized further using a special hack to make the filters completely ignore any effect from 'virtual pixels' (pixels that surround or extend the image proper). This is only to do with the handling of 'edge' effects, but it allows -distort resize and -resize to be compared directly, as alternate techniques. It also takes 'resize geometry' arguments, rather than the normal 'list of floating-point numbers', that distort expects.

If embedding a distorted image into another image, the default -distort results, using 'transparent virtual pixels' and appropriate sub-pixel 'translation' should be used as part of the image distortion (scaling), before the image is incorporated into the larger background image.

[hjulenissen]

Short answer... Speed.

It is a lot faster to resize images in two passes using 1-d filters, than to resize in 1 -pass using 2-D filters.
It can in fact be an order of magnitude faster.

This is also why Blur's are implemented using 2-pass 1-dimensional Gaussian, than 1-pass 2-dimensional Gaussian convolutions. But the Gaussian Filters/Kernels are separable. Most filters are not.

That is it in a nut shell -- speed.

Additional factor... Easer to Implement, and less likely to get wrong

I was asking why circular analytical functions shold be preferred over separable ones. You arguments all seems to support that separable functions are to be preferred?

If quality is the only concern (calculation speed, implementation complexity etc is of no concern), then why should I want a resampler that filters out diagonal information that can in fact be relilably reconstructed? I am not claiming to know the answer, I am just puzzled by this.

-h

[fmw42]

Anti-aliasing quality can be better with EWA (elliptical/circular) filters, especially if not a simple constant scaling. See perspective transformations at http://www.imagemagick.org/Usage/distorts/#horizon. The elliptical filters can do a better job of "averaging" pixels over a spread out region. The tensor filters are limited to small rectangular regions about a given pixel.

Tests have shown that even in simple scaling, some of the circular (EWA) filters perform better at reducing haloing and moire artifacts than do the tensor (rectangular) ones, because these artifacts are not always along orthogonal x,y lines. They can be at angles or along curves. I cannot give you a mathematical reason. These tests grew out of attempts to improve the EWA (elliptically weighted average) that started with a simple gaussian profile. That goes back to the early days of texture mapping as proposed by Paul Heckbert. But by using other windowing functions besides the Gaussian, it was found that better results could be had for the perspective and other non-constant scaling distortions. After than, it was generalized to try similar concepts with circular filters and circular windowing functions or tensor filters windowed by circular filters. The results below are comments about those tests.

See the comments at http://www.imagemagick.org/Usage/filter/nicolas/ which shows rankings of various tensor and EWA resampling methods for simple scaling.

However, I would suggest that there is no one best filter for every type of image. But IM gives you the flexibility to have some expert advice and be able to try different types of filters on any given image type. Some images may work better with traditional tensor (orthogonal) resampling. Other images seem to be noticeably better with circular resampling or combinations of the two. Artifact reduction may often be improved by using the sigmoidal concept as well whether tensor or circular filters are used.

Anthony and Nicolas feel free to add to or correct anything that I have said above.

[NicolasRobidoux]

Not an answer to your question, but gives you an idea of what I think about: http://forum.doom9.org/showthread.php?p ... ost1595678.
I consider theory to be a tool to understand and formulate better approaches. No more and no less.
The pudding always is king.

[hjulenissen]

I consider theory to be a tool to understand and formulate better approaches. No more and no less.
The pudding always is king.

If you want to make pudding, only the pudding matters, not the fancy theories used to make it. I guess that I dont see the same conflict between practice and theory that some people do.

A good theory should describe well (and compactly) what we can observe today, and predict well what we may observe tomorrow. It should be an instrument to condense the (often) noisy and sparse empirical tests into a small, comprehensible rule. I'd suggest that the main problem with "theories" or "theoretics" in informal settings such as this discussion forum is not that the theories are fundamentally wrong or inaccurate, but that they are used in the wrong context, without all of the conditions under which the theory was suggested and tested.

A good argument against the use of Shannon-Nyquist sampling theory for images might be that the camera and the display are far from perfect sinc-type A/D and D/A devices. So should the scaler try to "repair" the sub-optimal images, and "prefilter" the assumed deficiencies of a computer monitor? It might do so, and empirical testing might suggest that the end-result is somewhat better images. But there are some caveats. What kind of image sources? What kind of computer displays? Perhaps the chosen algorithm is great for LCD displays but worse than regular resampling for a DLP projector or laser printers?

kind regards
h