Second even bigger improvement for Distorts [CLOSED]

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.
Locked
User avatar
anthony
Posts: 8882
Joined: 2004-05-31T19:27:03-07:00
Authentication code: 8675308
Location: Brisbane, Australia

Second even bigger improvement for Distorts [CLOSED]

Post by anthony » 2010-09-27T18:51:08-07:00

IM v6.6.4-8

With major help from Professor Nicolas Robidoux and his [strikeout]PHD[/strikeout] Masters student Chantal Racette, I have been finally able to replace the "High Quality EWA" resampling method that IM has been using since it was first developed with a "Clamped EWA" resampling method.

This is a major improvement for Distorting images, especially those images that are not being resized (scaled) to any great extent. The "HQ-EWA" method generally make very very 'fuzzy' images. The new method is no where near as 'fuzzy' producing much clearer results.

Here are some examples..
Image old HQ-EWA method Image new Clamped-EWA method.

Extreme distortions such as 'Viewing Distant Horizons' are not effected to any great extent, though a 'rings' aliasing test showed much improved results.

Text distortion will especially show great improvements with much sharper and clearer distorted text images. Such as the "Around the World" Arc Ring Tests For example...
Image old HQ-EWA method Image new Clamped-EWA

The technique also allows us to make better use of non-Gaussian Image filters when distorting images, allowing us to generate even sharper image results. It is in this area where distortion work continues.

Also as part of the change Distort no long automatically switches between EWA resampling for minification and Interpolated resampling for magnification. As such the -interpolate filter switch introduced in the last 'improvement' is now discontinued. On the other hand the older -filter point will still switch from the use of EWA resampling to Interpolated Resampling.

ASIDE: A bug was also discovered in the original code that HQ-EWA was 'hidding' in its fuzziness. This bug caused sever aliasing in my previous attempts to convert a less fuzzy Clamped EWA, but only appears in very specific cases.
Anthony Thyssen -- Webmaster for ImageMagick Example Pages
https://imagemagick.org/Usage/

User avatar
anthony
Posts: 8882
Joined: 2004-05-31T19:27:03-07:00
Authentication code: 8675308
Location: Brisbane, Australia

Re: Second even bigger improvement for Distorts

Post by anthony » 2010-09-27T22:55:39-07:00

Addendum...
The default filter for Distort is currently set to Lanczos (Cylindrical version - Bessel-Bessel).

This is NOT the final filter choice for Distorts, but just an interim one that produces a reasonable result in a 'no-op distort' case (where the image is still filtered so does become slightly more blurry).

Other possibilities include
  • Mitchell which is close to the current Lanczos-Jinc function,
  • a Lanczos based on a x^2 lookup,
  • a Cubic function that has zero points at 1.0 and 1.414 (sqrt(2)),
    matching orthogonal and diagonal pixels at 'unity' scaling,
    so as to make a good interpolation filter.
  • Lagrange filter
  • something else
It seems that very little research into 'cylindrical filters' is available. So if you know of some work in this areas, please let me know.

Nicholas and I am keen to try out various cylindrical filter weighting schemes to try and improve this even further.

For those interested I re-discovered one of the few research papers that was actually involved with cylindrical filters (it was filed in my bookmarks for image distortions rather than as re-sampling filters).
http://www.gson.org/thesis/warping-thesis.pdf

ASIDE: Fred Weinhaus original gave me the reference to the paper but I filed it with regards to its localized circular distortion methods, and not for its involvement in EWA resampling. Because of this I could not find it as a paper on EWA resampling, when I wanted it again. A heavy Google search allowed me to re-discover it, and from their where I had filed the original reference.

You may be especially interested in the graph on page 35, of the final support size that results at different (prefilter) scales, and which shows why HQ-EWA is so much more blurry, than a the ideal "Clamped-EWA" technique (the 'proposed method in the graph) would produce.
Anthony Thyssen -- Webmaster for ImageMagick Example Pages
https://imagemagick.org/Usage/

NicolasRobidoux
Posts: 1944
Joined: 2010-08-28T11:16:00-07:00
Authentication code: 8675308
Location: Montreal, Canada

Re: Second even bigger improvement for Distorts

Post by NicolasRobidoux » 2010-09-28T06:18:35-07:00

Chantal Racette would like to point out that she is "only" a Masters student.

User avatar
anthony
Posts: 8882
Joined: 2004-05-31T19:27:03-07:00
Authentication code: 8675308
Location: Brisbane, Australia

Re: Second even bigger improvement for Distorts

Post by anthony » 2010-09-28T20:22:34-07:00

Update.

The new resampling method is so good, that it was generating a better and sharper result for Barrel Distortions than the result obtained by turning it off and using the default bilinear interpolation!!!!

See http://www.imagemagick.org/Usage/distorts/#barrel

You can compare results by comparing the OLD interpolated result

Code: Select all

  convert barrel_distorted.jpg -virtual-pixel black -filter point \
          -distort Barrel "0.0 0.0 -0.075 1.1"       barrel_interpolate.jpg
with the NEW EWA resamping filtered result

Code: Select all

  convert barrel_distorted.jpg -virtual-pixel black \
          -distort Barrel "0.0 0.0 -0.075 1.1"       barrel_ewa.jpg
Actually the result seemed to be slightly better than the published result from Hemut's website. Though that could be just a result of JPEG artifacts, as his web site version may be a low JPEG quality.

Of course it is not a sharp as using -filter point -interpolate NearestNeighbor which is what Hemut was using. But that can produce some severe aliasing effects!!!
Anthony Thyssen -- Webmaster for ImageMagick Example Pages
https://imagemagick.org/Usage/

User avatar
anthony
Posts: 8882
Joined: 2004-05-31T19:27:03-07:00
Authentication code: 8675308
Location: Brisbane, Australia

Re: Second even bigger improvement for Distorts

Post by anthony » 2010-10-12T22:31:08-07:00

fwm42 wrote:Is EWA now resolved for the time being?
Yes it has. and things have settled.

The second improvement announcement was the switch from the HQ-EWA technique (very blurry for almost no distort cases) to a Lower bound Clamped EWA.

As Clamped-EWA now works and works in a way that is equivalent to normal orthogonal resizing, different filters than a blurry Gaussian could now be used.

After lengthly discussions with Nicholas Robidoux, Professor of Mathematics at Laurentian University, the default filter has switched from Gaussian to a 'Mitchell-like' Robidoux filter, which was mathematically designed to have a minimal-blur for a minimal-distort case.

Cylindrical Interpolative methods such as Triangle, or the Hermite filter, or even a Gaussian filter with a "-define filter:blur=0.5" can also be used. Though any interpolation method will produce some aliasing effects in areas of high minification (image shrinking).
Could you add some more notes or clarification on your page about -distorts and EWA? For example:

1) I am confused about the use of -filter. Does that now change from using EWA to some -resize filter or does it change the Gaussian to something else such as cylindrical lanczos or spline or whatever within EWA
-filter changes the filter being used for either Resize or for Distort.

"-filter Point" turns of the use of filters in both as well, though for resize it only falls back to a nearest neighbour interpolation where in distort it will fall back to the -interpolate setting.

Up until these changes to distort, changing the -filter setting did not really do anything due to the extreme blurriness of the technique being used, especial in a 'no distort' case. It was something that I found annoying for years. The only solution for it however requires heavy use of trigonometric functions, which I was lothed to implement. Major thanks goes to Nicholas for working out a matrix solution (Singular decomposition) to the problem. After all, I am not really a mathematician.

Now the default distort output is very sharp, with only a minimal amount of blur for a 'no distort' case, and changing the filter and the various filter expert options can produce a marked change in results, allowing for the direct generation of very high quality distortions.

The Distort notes detail this in IM Examples, Distort Operator, EWA Resampling and Filters which was re-written about a week ago. People are always welcome to submit additions, changes or spelling corrections to any IM examples. I may not respond quickly or use them as given, but they are always welcome.

Also see the new Cylindrical Filters pages.
2) What is the current filter used by EWA as default? Is it cylindrical lanczos, Gaussian or the spline approx?
As of IM v6.6.5-0 it is the Robidoux Filter which happens to be almost identical to the Mitchell filter used for resize.

Both are Cubic 'Keys' filters, with almost the same 'C' (keys alpha) value.

The only difference between them is that Mitchell was chosen using social engineering to find an acceptable filter that works well for orthogonal 2-pass image resizing.

Robidoux however was specifically designed to act like a 2-lobe cylindrical Lanczos filter (Lanczos2D) that was sharpened to remove the detrimental effects windowing has on the Jinc function, and generate only minimal blurring for edges in a no-distort case.

See Windowed Jinc Cylindrical Filters
http://www.imagemagick.org/Usage/resize/#jinc
3) Can you add one or two examples of using a different expert option to change the filter used by EWA for different types of image.
Working on that (slowly)...

See the new section in IM examples, Cylindrical Filters
http://www.imagemagick.org/Usage/resize ... ylindrical
4) What is now being done when the foreground is magnified and the background is minified?
The automatic switch between EWA filtering, and interpolation has been removed. It is no longer relevant now that Clamped-EWA is in use.

You will either use EWA filtering or unscaled orthogonal Interpolation. Both produce excellent results for magnification (upsampling), though only EWA filters produce good results for minification (shrinking, or down sampling).
5) Can one avoid using EWA and just use one of the normal -filters such as triangle or normal 1d lanczos? If so, how do you do that?
WIthout EWA resampling, you can NOT use a filter. Only a unscaled interpolate looking of a the single sampled point. This will work reasonably well for no or magnification, but will produce serious aliasing effects for string. minification.

You can turn of EWA by using "-filter point". The "-interpolate Bilinear" (triangle filter equivalent) is the default
interpolator.


Alternately you can leave EWA enabled and use the "-filter triangle" Interpolation filter for BOTH magnification and minification. This will however be a 'cylindrical' interpolation rather than a two pass orthogonal interpolate. This will also handle 'minification' much more gracefully than any unscaled interpolate method.

A 1D Lanzcos (Sinc windowed Sinc) is not available as a interpolator. The closest available interpolator is 'Bicubic' which is based on a order-3 (2 lobe) Langrange filter. Lanczos is really ment to be used as a scaled area sampling filter, using either a 2-pass 1-d method (resize), but a 'cylindrical lanczos' (Jinc Windowed Jinc) can be used for a 1 pass 2 dimentional method (distort).

If any rotation is involved any type complex 1D filters do not work very well, they are just not designed for it, and especially not for a distorted 'circle' or elliptical area. If no rotation is involved, then you may as well just Resize the image!

6) Can you change what is used for magnification by -interpolate?
You either use EWA filtering or use interpolation, for the whole image.

Their is no auto-switch, as this tends to create image artifacts at the switch over point, as was seen in both large rings image shown in the first discussion.. Major Distort Image Improvement!
That switch was especially noticable near the bottom of the OLD image http://dl.dropbox.com/u/9500683/rings_fixed.png






ASIDE: Have a look at these two animations.
The first is with The old Rotate operator, The second is generated using the "-distort SRT" with default settings.
Image Image
These are in IM Examples, Image Warping Animations
http://www.imagemagick.org/Usage/warping/#animations

Apart from its overall blurriness, the rotate operators 'jiggle' is especially annoying. It was something that was reported and fixed years and years ago, but seems to have returned for some reason.
Anthony Thyssen -- Webmaster for ImageMagick Example Pages
https://imagemagick.org/Usage/

NicolasRobidoux
Posts: 1944
Joined: 2010-08-28T11:16:00-07:00
Authentication code: 8675308
Location: Montreal, Canada

Re: Second even bigger improvement for Distorts

Post by NicolasRobidoux » 2010-11-14T11:17:36-07:00

I just changed the Lanczos2Sharp parameter value slightly in svn. When doing 'no-op" on a vertical stripes images, you immediately see that I got it just right this time. (It's about a 1% change in the blur value.)

I'm now done tweaking the blur values with the better optimization technique.

User avatar
anthony
Posts: 8882
Joined: 2004-05-31T19:27:03-07:00
Authentication code: 8675308
Location: Brisbane, Australia

Re: Second even bigger improvement for Distorts

Post by anthony » 2010-11-18T17:47:23-07:00

Final notice...

Distort pixel resampling now uses Clamped-EWA.

The default filter for distort is "robidoux" which is essentially a sharpened 2-lobe Jinc-Jinc (cylindrical Lanczos) filter function implemented using a fast Cubic equivalent.

If you are interesting in the on going discussion in resize/distort filters see the topics...
viewtopic.php?f=2&t=17410
and
viewtopic.php?f=2&t=17136
This topic is now closed (locked)
Anthony Thyssen -- Webmaster for ImageMagick Example Pages
https://imagemagick.org/Usage/

Locked