Major Distort Image Improvement! [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.
Post Reply
User avatar
anthony
Posts: 8883
Joined: 2004-05-31T19:27:03-07:00
Authentication code: 8675308
Location: Brisbane, Australia

Major Distort Image Improvement! [CLOSED]

Post by anthony » 2010-09-14T17:35:46-07:00

Distortion Filters now fixed (At least the default Gaussian filter is)
See the large images at the bottom if you just want to see the results!

This is a major improvement in distort image results, but to understand the fix, you need to understand the problem.

This change will be part of IM version 6.6.4-2 releases and later.

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

A number of years ago, I added the Distort Operator to ImageMagick.
To make this filter work I includes EWA filtering (Elliptical Weighted Average) which used a Gaussian filter by default.

However at that time all the research papers and notes on EWA, always concerned itself with images involving distant horizons. That is correctly averaging large numbers of pixels that look very very 'distant' from the user, as generated by Perspective Distortions.
For example see Viewing Distant Horizons
Here is the image from IM examples of this 'typical' test image they used.
Image

The problem with this 'typical' test of EWA, is that it does not really test the filter handling of images with low (near unity) distortions, only the handling of image sampling at high minification.

At the time I endeavoured to get distortion at near unity scaling to work well, and to some extent it did, but the results were always 'over blurry' in my thinking (and to many other people who reported that fact). however I was unable to fix this due to a lack of understanding of filters, and specifically cylindrical filters.

To compensate this blurriness I make EWA distort automatically switch to using 'interpolation' in situations of image magnification, and also a special switch "-filter point" which will turn off EWA filtering, and force the use of interpolation for the whole image (it also increases the speed, and allows the use of super sampling instead of filtering for improved results with near-unity scaled images.

Later I did a lot of research into filters and as a result of this re-designed the filter system used by 'resize'. See Resize Filters, but resize filters are orthogonal filters and that did not seem to match the cylindrical filter used by distort EWA filtering. All attempts to fix EWA filtering resulted in images become worse rather than better :-(

With the on going discussions with Nicolas Robidoux in Cheaper sinc computation for resize.c however has spurred me on to take a fresh look at the EWA filters.

With this I was able to add a new special switch, that allowed me to actually look at the problem properly, rather than making (bad) guesses as to its cause. If you now set "-interpolate filter" you will turn off interpolated lookup for areas of the image that become 'enlarged'. that lets me used huge enlargement tests with the EWA filters, just like I did with resize, as shown in Ringing Resize Artefacts, and again in Gaussian Filter Support Examples.

With that switch and enlargement filter testing I was about to determine that I had two bugs, one of which roughly cancelled out the other. that was why fixing the more obvious bug (blurriness) only resulted in the results becoming worse, rather than better.

Both bugs have now been found and fixed. The resulting improvement are simply amazing.

Here is the results of a 'Rings' Aliasing Test (using perspective to get a range of scaling factors)

Code: Select all

    convert rings_lg_orig.png -chop 1x1 -border 1 \
            -virtual-pixel tile  -distort perspective \
            '0,0 0,200  1000,0 650,200  0,1000 0,700  1000,1000 1000,700' \
            rings_test.png
You can download the rings image from
http://www.imagemagick.org/Usage/img_ph ... g_orig.png
Yes it is a large image.

Image
as you can see it is very blury, with many Moiré (aliasing) effects visible (which should not be present with a gaussian filtered result. However Much more of the detail of the rings are also visible showing that the resulting image is much less blurry than before.

The lowest part of the resulting image uses interpolation rather than EWA filtering, though it is hard to see when one finishes an the other begins.

After the fixes, we now get...
Image
This image shows barely any Moiré (aliasing) effects (as you should get with Gaussian Filtering) but it also shows the sharp change from EWA Gaussian filtering to Bilinear Interpolation in the areas of image enlargement.

If you do not want this sudden change add a "-interpolate filter" switch to turn off the use of interpolation.
Because this change is now highly visible the automatic switching between the two modes may soon be turned off by default. For example in no -interpolate setting is set. -- Comments?

Comments are welcome.
Anthony Thyssen -- Webmaster for ImageMagick Example Pages
https://imagemagick.org/Usage/

User avatar
fmw42
Posts: 25757
Joined: 2007-07-02T17:14:51-07:00
Authentication code: 1152
Location: Sunnyvale, California, USA

Re: Major Distort Image Improvement!

Post by fmw42 » 2010-09-14T18:42:20-07:00

New EWA results are very striking and impressive. But the transition is disturbingly obvious as there appears to be a brightness change.
anthony wrote:if you do not want this sudden change add a "-interpolate filter" switch to turn off the use of interpolation.
Because this change is now highly visible the automatic switching between the two modes may soon be turned off by default. For example in no -interpolate setting is set. -- Comments?
Seems a bit confusing to use -interpolate filter to turn OFF the interpolation! What do you really mean by that?

Perhaps you can clarify what is used during minification and during magnificiation when one adds either -interpolate filter or -filter filter, in relation to when EWA is used.

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

Re: Major Distort Image Improvement!

Post by anthony » 2010-09-14T20:37:28-07:00

fmw42 wrote:Seems a bit confusing to use -interpolate filter to turn OFF the interpolation!
It means 'filter' instead of interpolate. It is like "-filter point" means don't filter (use interpolate).
Perhaps you can clarify what is used during minification and during magnificiation when one adds either -interpolate filter or -filter filter, in relation to when EWA is used.
Any Distorted image will either become larger (magnify) or smaller (minify) -- in general

the original EWA technique did not work with magnified images as the resampling 'ellipse' could very easily 'miss' all the
pixels in the source image producing no result. Interpoaltion on the other hand was really only suitable when used with magnification. As a result BOTH techniques was needed.

however about a year and half ago the Elliptical technique was modified to use a form which allowed it to be used in both areas. In research papers it was able to be used for both reconstruction (magnification) and decimation (minification), but the filters were not behaving as expected, so the automatic switch between interpolation and filtering was left in place.

Gaussian however as you will note is still quite blury -- absolutely no aliasing, but blurry. The next step is to try to get things like Micthell and Lanczos filters working right, but my initial tests show that any negatives in the filter produce a bad result. That is my nest hurdle. At that point we should start getting results that are near equal to that of -resize (I hope).

Slow but Steady wins the race -- Tortoise "Unstable Fables, Tortoise vs Hare"

At least the aliasing problems have gone completely.
Anthony Thyssen -- Webmaster for ImageMagick Example Pages
https://imagemagick.org/Usage/

User avatar
fmw42
Posts: 25757
Joined: 2007-07-02T17:14:51-07:00
Authentication code: 1152
Location: Sunnyvale, California, USA

Re: Major Distort Image Improvement!

Post by fmw42 » 2010-09-14T21:22:06-07:00

fmw42 wrote:Seems a bit confusing to use -interpolate filter to turn OFF the interpolation!
anthony wrote:It means 'filter' instead of interpolate. It is like "-filter point" means don't filter (use interpolate).
This is now even more confusing to me as you are mixing interpolate and filter. To me -filter point, just replaces whatever is going on with a point filter and has nothing to do with interpolation as you use it. -filter is for minification and -interpolation is for magnification. Corrrect?

But let me ask again.

If I use -interpolate value, what happens to EWA and in what area (minification or magnification)?

If I use -filter value, what happens to EWA and in what area (minification or magnification)?


In your transition to magnification right now with the new method, what are you using in place of EWA? Is there a way to transition between different interpolators as one varies the magnificiation, so that the transition is not so obvious?

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

Re: Major Distort Image Improvement!

Post by anthony » 2010-09-14T23:56:34-07:00

fmw42 wrote:If I use -interpolate value, what happens to EWA and in what area (minification or magnification)?
Starting from defaults setting -interpolate {value} will change the interpolation used in magnified areas. However if -filter point is also use. it applies to the whole image.
If I use -filter {value}, what happens to EWA and in what area (minification or magnification)?
If -filter {value} is used it only applies to minification areas. Unless -interpolate filter is used, in which case the EWA filter is used over the whole image (as shown above).

Using BOTH -interpolate filter and -filter point you will get undefined results. Probably junk I have not tried it.


ASIDE: I do plan to add a 'filter' kernel for convolution at some point. That is set up a radial kernel based on the -filter function, and kernel size.
In your transition to magnification right now with the new method, what are you using in place of EWA?
Direct unscaled interpoated lookup. EG point U,V -> color
Is there a way to transition between different interpolators as one varies the magnificiation, so that the transition is not so obvious?
The final plan (when good filters become available) would be to either only interpolate or only EWA filter, according to the users wishes. I really do not want to switch 'techniques' in the middle of an image!

As mentioned the only reason for both was originally EWA could not do magnification, but it now can.
Actually I an not really very happy with the way this EWA actually handles near UNITY scales. Images are actually slightly more blury when very little scaling is applied due to the way it itself switches between the two areas.

I may switch back to the old EWA method, but just but a 'clamp' on the ellipse size so it can't get too small. It is worth a try now that I have filtering working. However I first want to find out why filters containing negatives are not working.
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: Major Distort Image Improvement!

Post by anthony » 2010-09-15T01:06:04-07:00

Okay I have filters with negative weights working... Ended up to be a simple sanity check
that was failing. It thought values generated by negative weights was insane, which at the time I wrote it, I did not understand.

As such adding -filter lanczos -set option:filter:support 2 will now produce a much sharper image (this is a cylindrical version of Lanczos).

The lobes is needed a EWA still has a fixed filter support radius of 2.0 that it inherited from the original use of gaussian.

A -filter mitchell (automatically a support 2 filter) also produces a good image. Actually in some ways it looks a lot better than the Lanczos which is not designed for such as low support as 2.

Langrange filters also now work well! and also by default use a support of 2 for a lagrange order 3 filter.

Actually this seems to produce a better result than the default -interpolate bilinear at that switch point! Which may not be so suprising as it is being used as a cylindrical filter, rather


Still to test....
  • Trial a 'clamped' EWA instead of Paul Heckberts high Quality EWA varient, to try and remove some
    of the excess blurrring at Unity scaling.
  • allow the use of a larger support for better (and slower) lanczos use.
  • Use Mitchell (or something else) as the default filter when unset -- no need for a blurry guassian
  • turn off the current mix interpolate/filter usage.

I am now feeling like distort is finally producing the quality results that it should be producing. Almost their! I am so glad Nicholas joined the discussions to give me the insight I needed.
Anthony Thyssen -- Webmaster for ImageMagick Example Pages
https://imagemagick.org/Usage/

User avatar
fmw42
Posts: 25757
Joined: 2007-07-02T17:14:51-07:00
Authentication code: 1152
Location: Sunnyvale, California, USA

Re: Major Distort Image Improvement!

Post by fmw42 » 2010-09-15T10:12:20-07:00

Anthony wrote:Starting from defaults setting -interpolate {value} will change the interpolation used in magnified areas. However if -filter point is also use. it applies to the whole image.

If -filter {value} is used it only applies to minification areas. Unless -interpolate filter is used, in which case the EWA filter is used over the whole image (as shown above).

Using BOTH -interpolate filter and -filter point you will get undefined results. Probably junk I have not tried it.
All of these special cases still are a bit hard to keep up with. I hope when you get done, perhaps EWA everywhere will be the default. But one needs better ways to express what one wants to use in areas of magnification, minification either individually or simultaneously. For example if I just wanted to use bilinear everywhere.

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

Re: Major Distort Image Improvement!

Post by NicolasRobidoux » 2010-09-15T12:34:27-07:00

Anthony:

I know how to fix the "switching artifacts" issue (it is actually part of the Masters work of one of my students, Adam Turcotte).

Busy with other things now, but make note that Adam and I could help.

Roughly speaking, you "blend" the filtering and the interpolatory scheme with a blending factor which varies continuously depending on how close you are to want to use only one of them.

An alternative is to build a filtering (EWA-type) scheme which works reasonably well in all situations. As you know, I have opinions RE: that as well. If the "interpolatory" type scheme you like is Mitchell, this should not be so hard. If it's Catmull-Rom, it's more tricky.

(Well, I'm a prof: I have opinions about EVERYTHING.)

User avatar
fmw42
Posts: 25757
Joined: 2007-07-02T17:14:51-07:00
Authentication code: 1152
Location: Sunnyvale, California, USA

Re: Major Distort Image Improvement!

Post by fmw42 » 2010-09-15T14:25:30-07:00

Roughly speaking, you "blend" the filtering and the interpolatory scheme with a blending factor which varies continuously depending on how close you are to want to use only one of them.
I suspect Anthony is trying to avoid computing every pixel twice (once for each interpolation method, especially if EWA is involved) and blending as that would generally be slower. But that is the obvious solution.

Fred

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

Re: Major Distort Image Improvement!

Post by anthony » 2010-09-15T17:12:39-07:00

fmw42 wrote:For example if I just wanted to use bilinear everywhere.
Then turn off filtering by using 'point' filtering -filter point.

Note that even resize does not use a filter when the user requests a 'point' filter.
Though it does not call interpolation, rather it just directly uses the nearest neighbour.

Note that filters do include all the unscaled interpolation methods (an more like 'hermite'), and when applied from a 2 pass orthogonal resize they produce the exact same results.

However distort uses the filters in a 1 pass cylindrical method. as such selecting -filter triangle
will generate different results than you would get in a interpolated bilinear. That is the pixels are weighted based on diagonal distances, rather that orthogonal distances.
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: Major Distort Image Improvement!

Post by anthony » 2010-09-15T17:20:55-07:00

fmw42 wrote:
Roughly speaking, you "blend" the filtering and the interpolatory scheme with a blending factor which varies continuously depending on how close you are to want to use only one of them.
I suspect Anthony is trying to avoid computing every pixel twice (once for each interpolation method, especially if EWA is involved) and blending as that would generally be slower. But that is the obvious solution.
That is correct. Though at near unity scales which is where this problem occurs the cost is not prohibitive. I would like to avoid it though.

Last night I tried to adjust the "High Quality EWA" ellipse size to match the current support of the filter being used. It failed. The HQEWA just does not seem to be designed with variable (non-gaussian) filter support in mind.

Tonight I will try to switch back to the original EWA but with a clamped minimum size, which is how -resize handles 'magnification'. That is resize scales the filter when the image is minified, but then uses the filter purely as a orthogonal unscaled interpolator when the image become magnified.
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: Major Distort Image Improvement!

Post by anthony » 2010-09-19T17:12:55-07:00

Update...

First I went back to basics and added debuging to output enough info so I can generate gnuplot maps of the scaling vectors, the derived ellipse, and for a specific 'pixel smapling' the pixels that was being sampled and whether they matched the ellipse or not.

here is an example of a EWA smapling ellipse.
Image
the ellipse as you can see is twice the size of the scaling vectors, and it clearly shows that all the pixels within the ellipse was found, using a parallelogram bounding region for the pixel sampling.

I then started to compare "High Quality EWA" (HQ-EWA which IM has been using for the last few years) against the original EWA, first proposed by Paul Heckbert. HQ-EWA is basically EWA, but with the ellipse expanded by a unit circle to allow it to automatically handle 'reconstruction' or 'magnification' of the source image without needing to 'clamp' the ellipse to prevent it 'missing' source pixels when 'sampling' during image enlargement.

Here is my current results, showing clearly where the two styles work and where they fail...
Image
The top line is HQ-EWA (as IM -distort) is currently using, with the bottom line generated using the exact same command but with EWA ellipse calculations instead of High Quality EWA ellipse handling. All images use a "-interpolate filter" setting to ensure only sampling filters are used and not pixel interpolation.

The first three images on the left is extreme magnification (20X) of a single pixel using lanczos (3 lobe) filter. The left most is using a 2 pass orthogonal "-resize 2000%", with the next two images using "-distort SRT 20,0".

You can see that HQ-EWA which can only use a fixed support setting of 2.0 resulting in the Lanczos (Bessel windowed Bessel) filter being 'clipped' at support=2, whcih would generate 'blocking' artifacts. EWA however can use variable support and as a result shows the full 3 'lobes' of the filter (center, trough, and one more minor 'ringing'). Neither result is to bad.

The next two images, a rotated line using Gaussian filter, clearly shows the main disadvantage of using HQEWA. As it adds a unit circle to the calculated ellipse size at unity scales (no scaling) distortions the ellipse is a 3 unit circle, using a 2 unit filter. The result is a VERY blurry line. This is the 'blury' problem so many users have complained about, especially for things like barrel distortion (photo correction).

From this it may seem that EWA is better that HQ-EWA, but the next two sets show that when 'minification' is used, such as for horizon viewing. EWA fails (still trying to determine why). Basically EWA is currently producing extreme aliasing effects.

This is not clear in the typical 'Infinite Checkerboard' test, as this uses very large (16 pixel) squares, that does not test pixel level aliasing effects of the filters. However there is a very slight aliasing effect visible close to the horizon at the top-right of the bottom EWA image.

However substituting a 45 degree rotated 'Rings' clearly shows major aliasing effects for EWA filtering.

Checking and comparing the generated ellipse size only shows a very minor difference in ellipse size for the problem areas (HQ-EWA adding a unit circle to a already very large ellipse). So I am still searching as to the cause of the aliasing effect in the EWA method.

NOTE: you can not simply switch between EWA and HQ-EWA in the same image as the calculations and handling of the 'filter cache' is different.

As such we are still stuck using HQ-EWA with its 'blurry' results at unity scale distorts :-(

I am uploading the testing "resample.c" into SVN with the switch set to use HQ-EWA, set using a define at the top of the module.

Comments always welcome.
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: Major Distort Image Improvement!

Post by anthony » 2010-11-18T17:25:46-07:00

This has all changed with the new set of improvements, specially the proper implementation of a 'Clamped-EWA' technique, that avoids the near-unity blurriness of Paul Heckbert's HQ-EWA, and the problems of 'missing pixels' when enlarging in straight EWA.

The change has been amazing, and as such this forum discussion is now closed.

As part of this the the auto-switch between -filter and -interpolate is no longer relevant.
You either use -filter FILTER_METHOD (the default),
or -filter point -interpolate INTERPOLATE_METHOD,
for fast unscaled single point lookups. The selection will now always apply to the whole image!
Anthony Thyssen -- Webmaster for ImageMagick Example Pages
https://imagemagick.org/Usage/

Post Reply