[SOLVED] Double check w/ resize/distort: positive weight sum

Discuss digital image processing techniques and algorithms. We encourage its application to ImageMagick but you can discuss any software solutions here.
Locked
NicolasRobidoux
Posts: 1944
Joined: 2010-08-28T11:16:00-07:00
Authentication code: 8675308
Location: Montreal, Canada

[SOLVED] Double check w/ resize/distort: positive weight sum

Post by NicolasRobidoux »

For each filter, is there some resize/distort operation which makes the sum of the weights equal to 0. Generally, this will happen if the sum of the weights is negative somewhere for a nearby operation (unless we just "kiss").

I (we) have been making the assumption that this never happens, but I feel this is important enough that there should be a compile option that checks whether the sum of the weights is <= 0 and that returns an informative message if a sum <= 0 occurs. (Is there such a thing already?) In an ideal world, I'd get an automatic email with details of the operation!

I may be able to tackle this geometrically, but this is a big job given everything that can be done with IM.

I also vaguely remember that Anthony found that this CAN happen if one uses windowed Sincs with EWA.
Last edited by NicolasRobidoux on 2012-05-11T03:47:25-07:00, edited 1 time in total.

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

Re: Double check w/ resize/distort: strictly positive weight

Post by anthony »

That was the one case, and only if you use a specific number of lobes (even number I believe)

Here was My notes...
Sinc makes a BAD cylindrical filter...

It seems that a Sinc Cylindrical Weighting Function (with even support) when applied to an integer grid of sampling points just does not work.

The accumulation of Sinc weightings in such a case simply results in a near zero accumulation of sampling weights. That in creates weighting divisor which is near zero in value (resulting in large positive or negative color values). And these in turn become clipped at either pure black or white colors in the resulting image.

For example in a Sinc of support=2, a sample near the center (the central peak) will generate a weight of about 1.0, But that weight will be offset by the surrounding four diagonals which will have negative weights. that produces a overall weight of near zero and a indeterminate final value for the convolution.


Do not use Sinc as a cylindrical filter function. At least not with an even support radius

convert -size 1x1 xc: -bordercolor '#333' -border 3 \
-filter Sinc -define filter:lobes=4 \
+distort SRT 30,0 show:

Note also that a odd number of Sinc lobes will not cause this aliasing

convert -size 1x1 xc: -bordercolor '#333' -border 3 \
-filter Sinc -define filter:lobes=5 \
+distort SRT 30,0 show:

Another facet is that as a cylindrial filter a Sinc (odd support) will generate a very sharp triangular like central peak, rather that the rounded one you would normally expect, though zero crossings remain at interger intervals.

A Sinc windowed Sinc (Orthogonal Lanczos) filter is not as bad as a raw support clipped Sinc, due to the added weight function reducing the negative influence of diagonals. However it still results in some clipping of the central peak.


For Example

convert -size 1x1 xc: -bordercolor '#333' -border 3 \
-define filter:filter=Sinc -define filter:window=Sinc \
-define filter:support=2 +distort SRT 30,0 show:
Your response (as I noteded it) was...
The theory says that raw, unwindowed, Sinc decays as 1/r (if my memory is
good).

Multiplied by r, this means it does not decay when used radially. Hence the near perfect cancellation.

What my decay argument implies is that if you want something that behaves like a sinc for a large number of lobes in a cylindrical setting, you need to use its square:

Instead of sinc(x) (or sinc(pi x)) use (sinc(pi x))^2.

Lanczos decays as sinc * sinc so like 1/r*1/r = 1/r^2. Even multiplied by r, it decays like 1/r. So: no near cancellation.

In other words, lanczos used rotationally behaves more or less like what you expect sinc to behave like when the number of lobes, and consequently the support, is large.
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: Double check w/ resize/distort: strictly positive weight

Post by NicolasRobidoux »

@Anthony: If we start using "orthogonal" filters in a distorted way, having a "debug" runtime check for non-positive coefficient sums may be a really nice thing to have. We are going to start sampling filters in very unusual configurations, and I smell the possibility of "random disasters" that happen only when some evil distortion creates a "perfect storm".
We saw that this can happen with Sinc used as an EWA filter...

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

Re: Double check w/ resize/distort: strictly positive weight

Post by anthony »

At the end of resampling there is a check for 'no pixels hit'. At which point depending on a compile define it returns a simple 'interpoated lookup', or just a 'red' pixel (for debugging)
This only happens with very small supports.

See expert notes in
http://www.imagemagick.org/Usage/resize ... terpolated

However no check for division by zero (very unlikely if thier was a 'hit'), or negative division.
WARNING there is two divisors. One for just sum(weights) applied to alpha channel and one for sum(alpha*weights) for color channels. That is for 'alpha blending'. It is possible for one and not the other to be negative!

I could add tests for BOTH, and follow the same 'miss' status
PS: I have also been thinking of adding some new 'interpolation' methods (some very strange but would be useful
for this type of 'error' check. -- useful for weird effects like those shown in the previous link! I even have an applied use for it!

The code in IMv6 is...

Code: Select all

  /*
    Result sanity check -- this should NOT happen
  */
  if ( hit == 0 ) {
    /* not enough pixels in resampling, resort to direct interpolation */
#if DEBUG_NO_PIXEL_HIT
    pixel->opacity = pixel->red = pixel->green = pixel->blue = 0;
    pixel->red = QuantumRange; /* show pixels for which EWA fails */
#else
    status=InterpolateMagickPixelPacket(resample_filter->image,
      resample_filter->view,resample_filter->interpolate,u0,v0,pixel,
      resample_filter->exception);
#endif
    return status;
  }

  /*
    Finialize results of resampling
  */
  divisor_m = 1.0/divisor_m;
  pixel->opacity = (MagickRealType) ClampToQuantum(divisor_m*pixel->opacity);
  divisor_c = 1.0/divisor_c;
  pixel->red   = (MagickRealType) ClampToQuantum(divisor_c*pixel->red);
  pixel->green = (MagickRealType) ClampToQuantum(divisor_c*pixel->green);
  pixel->blue  = (MagickRealType) ClampToQuantum(divisor_c*pixel->blue);
  if (pixel->colorspace == CMYKColorspace)
    pixel->index = (MagickRealType) ClampToQuantum(divisor_c*pixel->index);
  return(MagickTrue);
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: Double check w/ resize/distort: strictly positive weight

Post by NicolasRobidoux »

Given, also, what we've been discussing off line, I think we may be very happy to have the two checks in place.
Murphy's law: As our methods become more powerful, and more users do "strange things" with them, if there is any chance of a perfect storm, someone will be hit by it.
Note: Make sure to check for sum of weights <= 0. Reason: If you can get <0 and the filter functions are continuous, you can get = 0 with a different set of parameters. Since we won't have time to explore the infinitely many sets of parameters, we want the net as big as possible. Sum weight = 0 is generically a measure zero set. You need a pretty fine net to catch this fish! So, make the net bigger.

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

Re: Double check w/ resize/distort: strictly positive weight

Post by anthony »

Added. Though you may not see much with the default inteprolation setting.

When I add extra interpolation settings (very low priority) or you use the compile time 'NO_HIT' define you will see if you get 'bad' results.
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: Double check w/ resize/distort: strictly positive weight

Post by NicolasRobidoux »

@Anthony: Thank you.

Locked