proper scaling of the Jinc filter for EWA use

Discuss digital image processing techniques and algorithms. We encourage its application to ImageMagick but you can discuss any software solutions here.
Post Reply
imaggie
Posts: 88
Joined: 2011-12-19T04:15:36-07:00
Authentication code: 8675308

Re: proper scaling of the Jinc filter for EWA use

Post by imaggie » 2011-12-20T05:35:03-07:00

PS
the (original) script has a "slow" option that, apart from interpolation errors does that same thing. The result is indistinguishable in reality in the square case to which it is currently restrained.

Code: Select all

    convert -size ${w1}x${h1} xc: -monitor \
      -fx "zz=hypot($fxd*(i-$cx),$fyd*(j-$cy)); (zz<=3)?$jinc1:$jinc2" \
      $tmpF
Hopefully this form would be extended to a more general rect image by using EWA style functions.

It seems all the work has already been done in IM but I just need to see how to hook into it.
8)

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

Re: proper scaling of the Jinc filter for EWA use

Post by NicolasRobidoux » 2011-12-20T09:39:48-07:00

anthony wrote:...
Weather a cylindrical Lanczos (or whatever name it is) should be a Jinc windowed Jinc, OR a Sinc windowed Jinc is the main topic of discussion. My myself do not have the expertise to comment, but am open to the addition and adjustment of 2-d Windowed Jinc Filters, to better improve the results of image distortion, especially for near unity scaled distortions.
...
At this point, it appears that Jinc-windowed Jinc is best.

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

Re: proper scaling of the Jinc filter for EWA use

Post by NicolasRobidoux » 2011-12-20T09:46:40-07:00

imaggie wrote:...
jinc is the FT of the cylinder but the window fn is not specifically related to, say, the FT of the rectangular image array. So there is no 'right' answer there. Single sinc lobe seems a good choice for orthogonal so a rotation of that would seem a good choice for a circularly symmetric fn like jinc.

There is perhaps a temptation to think a jinc - jinc because of some kind of symmetry logic but I don't see any real justification for that idea.
...
I agree. (Although there is something to be said to windowing with something that is directly related to the "ideal" low pass filter. Really wishy-washy, I know.) The only reason my eventual conclusion was that for upsampling or resampling one should use Jinc-windowed Jinc EWA instead of Sinc-windowed Jinc EWA is that it appears that it did better in the "eyeball metric" in a limited collection of enlargement tests. It also appears to lead to less deep halos (by a nudge).

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

Re: proper scaling of the Jinc filter for EWA use

Post by NicolasRobidoux » 2011-12-21T06:08:56-07:00

Apparently, what imaggie needs is to transform a windowed Jinc into a mask (so he/she can apply it in Fourier domain?).

Anybody knows how to do that?

imaggie
Posts: 88
Joined: 2011-12-19T04:15:36-07:00
Authentication code: 8675308

Re: proper scaling of the Jinc filter for EWA use

Post by imaggie » 2011-12-21T09:13:11-07:00

NicolasRobidoux wrote:
imaggie wrote:...
jinc is the FT of the cylinder but the window fn is not specifically related to, say, the FT of the rectangular image array. So there is no 'right' answer there. Single sinc lobe seems a good choice for orthogonal so a rotation of that would seem a good choice for a circularly symmetric fn like jinc.

There is perhaps a temptation to think a jinc - jinc because of some kind of symmetry logic but I don't see any real justification for that idea.
...
I agree. (Although there is something to be said to windowing with something that is directly related to the "ideal" low pass filter. Really wishy-washy, I know.)
To take that line I think it is necessary to define what the second windowing fn is there for. Without defining what it is doing it is impossible to make comments like "ideal".

The base function depends upon the distortion to be removed (in my case) or the frequency filter sought in the case of EWA.

The lobe of whatever gets used as a window is just an envelop function whose function is to deform the truncated (so less than) "ideal" filter so as to remove the artefacts of the truncation or other defects in the process (distortion due to border effects).

the properties that are required of that envelop have , a priori, no relation to the job of the base filter. It is the windowing properties that need to be optimised.

This may include how abrupt the discontinuity is where the window ends. Both sinc and jinc get cropped at a zero-crossing , this implies a discontinuity.

Now if you say it wins by a nose over sinc in a broad set of tests, that sounds like a legitimate empirical approach, however, I think it would be an error to say any similarity to the base filter is a criterion unless you say it's function is to provide a separate frequency filter rather than act as an envelop.

In the latter case you'd need to say what you intend it to filter, rather than discuss it as a windowing fn.

(BTW imaggie is a him)

imaggie
Posts: 88
Joined: 2011-12-19T04:15:36-07:00
Authentication code: 8675308

Re: proper scaling of the Jinc filter for EWA use

Post by imaggie » 2011-12-21T09:17:17-07:00

NicolasRobidoux wrote:Apparently, what imaggie needs is to transform a windowed Jinc into a mask (so he/she can apply it in Fourier domain?).

Anybody knows how to do that?
Yes , sorry if that was not clear from my earlier post.

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

Re: proper scaling of the Jinc filter for EWA use

Post by NicolasRobidoux » 2011-12-21T09:44:33-07:00

(Sorry: I'm reading all this really quickly.)

If it's a convolution you want, why don't you simply -distort resize the FFT pseudo-image to the exact same dimension, and then backtransform?

(Gotta run.)

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

Re: proper scaling of the Jinc filter for EWA use

Post by anthony » 2011-12-22T19:38:01-07:00

[quote="imaggie"]There is perhaps a temptation to think a jinc - jinc because of some kind of symmetry logic but I don't see any real justification for that idea./quote]

I never saw the logic behind a sinc-sinc (lanczos) for orthogonal filtering either. But it works very well ;-)


However I gather you are simply using the filters as a convolution for removing a focus problem on images, while performing
a no-op distortion of the image. This is quite valid but may not be the best way to go about it.

Fred Wienhaus has looked at some aspects of de-focus, using Jinc kernels and the fast fourier transform.

See FFT division examples...
http://www.imagemagick.org/Usage/fourier/fft_math/

If this is the case let me know, and I'll split this discussion into a new IM forum, Digital Image Processing topic.
Anthony Thyssen -- Webmaster for ImageMagick Example Pages
https://imagemagick.org/Usage/

imaggie
Posts: 88
Joined: 2011-12-19T04:15:36-07:00
Authentication code: 8675308

Re: proper scaling of the Jinc filter for EWA use

Post by imaggie » 2011-12-25T11:26:31-07:00

I can't recall the details but I think Lanczos being a rigorous mathematician did actually have sound theoretical reasons for his choice. My point was that the fact that sinc-sinc works well is not reason to suppose jinc-jinc it necessarily the best way to do for EWA.

I don't understand your use of the term "no-op distortion", if it distorts , it's not a no-op :?

I got drawn into this whole thing by Fred's deblur script, which I was able to improve slightly by adding a window function. (The published script is pure jinc). I'm trying to improve it further.

I thought the parallel between the two applications of this function would mean the same discussion would apply in both cases and it would make sense to discuss this in one place unless it turns into specifics that apply to one but not the other. If you prefer to split I'll mark the other thread as well and follow both.

I was hoping there was a way to exploit what is already available in EWA , with all the lobe , window etc options to create the sinc-jinc or jinc-jinc functions I need to deblur. In particular locating the jinc zero crossings seems non-trivial.

Can you suggest a way to do that , rather than duplicating what you have done for EWA in a stand alone script for deblur?

Thx.

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

Re: proper scaling of the Jinc filter for EWA use

Post by anthony » 2011-12-28T19:52:07-07:00

imaggie wrote:I don't understand your use of the term "no-op distortion", if it distorts , it's not a no-op :?
It basically means going through the full distortion process but without any changes to pixel locations, That is the distortion should be same as not doing any distortion at all. Equivalent to a Unity Affine Translation.

The problem is that ALL Cylindrical Filters fail to generate the exact same pixel colors during this transformation. Instead you always get some slight mixing of the original pixel color with its neighbours. Sometimes a sharpening effect, more often a slight blurring effect.

Most Interpolative filters, and all Windowed Sinc filters in a orthogonal resize, will preserve the pixel colors in a no-op situation.
Many cubic and all Jinc functions do not preserve colors.
I got drawn into this whole thing by Fred's deblur script, which I was able to improve slightly by adding a window function. (The published script is pure jinc). I'm trying to improve it further.
Sounds good. It would be even better once we start creating new FFT based functions, such as multiple and divide of FFT images, while the image data remains in a floating point format for the FFT library (less translations)
I was hoping there was a way to exploit what is already available in EWA , with all the lobe , window etc options to create the sinc-jinc or jinc-jinc functions I need to deblur. In particular locating the jinc zero crossings seems non-trivial.


Best way is probably to generate a radial gradient, then convert that (linear to sinc/jinc) using a -function of some kind. I believe it was added but I have not studied it. (To many other things)
Can you suggest a way to do that , rather than duplicating what you have done for EWA in a stand alone script for deblur?
Can't think of a good method at this time.
The big problem is that images only store a interger from 0 to 2^16-1 (for IM Q16) and Jinc has negatives. You would need HDRI or some type of offset, to do it properly.

One thing I could do is map Resampling filters to Convolve/Morphology Kernels! But those kernels are floating point arrays, not images. I have been wanting to generate a kernel to image built-in. At this time thier is only an external kernel to image function.

http://www.imagemagick.org/Usage/morpho ... rnel2image
Anthony Thyssen -- Webmaster for ImageMagick Example Pages
https://imagemagick.org/Usage/

imaggie
Posts: 88
Joined: 2011-12-19T04:15:36-07:00
Authentication code: 8675308

Re: proper scaling of the Jinc filter for EWA use

Post by imaggie » 2011-12-29T01:16:31-07:00

As a result of some testing using windowed jinc on deblur it appears that there is not one "best" choice , indeed windowing is not always advantageous.

As I said elsewhere I think some more thought needs to go into why the window is there and what it is supposed to achieve rather than subjective empirical testing on a perhaps rather ill-defined group of test images.

My understanding of windowing from my work on using Lanczos for bidirectional scaling interpolation in GIMP is that the aim is to prevent a sharp truncation of the filter function at the end of the kernel window. Such an abrupt change at an arbitrary point in the function can be detrimental, so one objective is to ensure the function is tapered to zero before the edge of the kernel window. When the convolution is done by TD multiplication rather than FFT, the kernel is typically quite small and this is important.

Another choice made by Lanczos was to make the window cut-off (outside first lobe) coincide with a zero point in the base function. While this seems like a nice idea I have not looked into the mathematical justification for this choice. I bow to Lanczos' far superior rigour and intellect and assume he based this choice on sound reasoning.

I experimented with L4 in that context but the ringing on block graphics became far too pronounced. This brings in the second reason for windowing: in deviating from the idea form of the base function a distortion is introduced , this results is a slight softening blur. This will typically reduce the extent to which the ringing is visible. It does this by reducing the higher frequencies that are necessary for a sharp step function in the frequency domain: the ideal step filter that is the original aim.

In reducing sharpness of the filter transition the overshoot and subsequent ringing in FD that causes ghosting in the image is reduced.

I suspect there is another cause of ringing but the gentle softening , while being technical a degradation, often produces a better compromise result. There is a clear trade off here. The optimum method will almost certainly depend upon the subject material: an photo, even a portrait, will accept ringing better than block graphic art or lettering.

In experimenting with adding a window fn to Fred's cameradeblur I initially scaled a sinc lobe at 3x the jinc (not knowing the proper location of the jinc zero at 3.2383). On the classic "camerman" greyscale test image with an artificial 15px defocus blur this gave a small but worthwhile improvement.

Code: Select all

cameraman.png: PNG image data, 256 x 256, 8-bit grayscale, non-interlaced
On another image, a scan from a traditional negative film image, (ie true defocus blur) I found the best deblur result from pure jinc without a window. ( 36 px deblur ). Though the script is still producing such pronounced ringing that it is of little use for aesthetic images.

Code: Select all

cygale.png: PNG image data, 524 x 524, 8-bit/color RGBA, non-interlaced
The ensuing filter in the latter case has six jinc rings filling about half the filter window, the seventh is barely visible. In this case it appears that distorting the idea function with a window is detrimental since the jinc is fully expressed within the window (thought you need to look damn close to see any difference).

I expect this will mean that in the case of EWA the choice will depend on the scaling factor which determines the proportions of the ensuing jinc filter. Maybe some evaluation of the amount of power in the outer rings and the signal power of the difference between windowed and unwindowed over the fitler dimensions would allow an objective criterion for whether to apply a window.

Since it is the central lobe that does most of the work, the outer rings being progressively finer corrections, I would favour sinc over jinc as window fn. The jinc having a much faster decay envelop will probably degrade the essential central lobe more than sinc. I would suggest that the broader sinc lobe would generally be less destructive (in the sense of blurring the result) than a jinc window.

Of course there will be some test cases where this blurring may give a more pleasing result by, for example, softening staircasing on near horizontal lines. So some care needs to be taken in the choice of test image and the appreciation given to such features.

imaggie
Posts: 88
Joined: 2011-12-19T04:15:36-07:00
Authentication code: 8675308

Re: proper scaling of the Jinc filter for EWA use

Post by imaggie » 2011-12-29T05:16:15-07:00

Can't think of a good method at this time.
The big problem is that images only store a interger from 0 to 2^16-1 (for IM Q16) and Jinc has negatives. You would need HDRI or some type of offset, to do it properly.

One thing I could do is map Resampling filters to Convolve/Morphology Kernels! But those kernels are floating point arrays, not images. I have been wanting to generate a kernel to image built-in. At this time thier is only an external kernel to image function.
Thanks. I am able to do what I need by just scaling sinc/jinc window to the base jinc so no immediate problem.

It would be a plus in terms of execution, I imagine, (and duplication of effort) if I could exploit the code that is already there for EWA. So that would be a motivation for the sort of thing you suggest.

regards.

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

Re: proper scaling of the Jinc filter for EWA use

Post by NicolasRobidoux » 2011-12-29T06:27:07-07:00

anthony wrote:
imaggie wrote:I don't understand your use of the term "no-op distortion", if it distorts , it's not a no-op :?
It basically means going through the full distortion process but without any changes to pixel locations, That is the distortion should be same as not doing any distortion at all. Equivalent to a Unity Affine Translation...
Another way of understanding no-op: Resize and Distort compute pixel values at the (usually new) locations determined by a geometrical transformation. "no-op" is short for "the new pixel locations are exactly the old ones", that is, the geometrical transformation is the identity. This is equivalent to using the resize or distort operation as a filter (like the usual Gaussian blur or unsharp mask), that is, as an "in-place" operation.
anthony wrote:...The problem is that ALL Cylindrical Filters fail to generate the exact same pixel colors during this transformation. Instead you always get some slight mixing of the original pixel color with its neighbours. Sometimes a sharpening effect, more often a slight blurring effect...
Actually, there are cylindrical filters which give the identity under no-op: Point, Triangle and Hermite. But they suck: aliasing hell unless downsampling a lot, in which case Triangle is probably the better of the lot.

Better ones (still not great) are discussed in this thread: http://imagemagick.org/discourse-server ... 22&t=20007.

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

Re: proper scaling of the Jinc filter for EWA use

Post by NicolasRobidoux » 2011-12-29T09:02:29-07:00

As I mentioned several times, there are several mathematical criterions that can be used with the same qualitative feature in mind. Horizontal/vertical feature preservation, for example.

I revisited the computation of the LanczosSharp blur, using the "minimize the worst possible change, under no-op, in the pixel values of a vertical (or horizontal) line with constant pixel values" criterion. What this has to do is to keep (under no-op) a vertical or horizontal line "intact" irregardless of its surroundings. For example, this is the blur that will keep "frames" put around an image as untouched by no-op EWA distort as possible, given that the image content is arbitrary.

I now believe that this is the best criterion as far as preserving vertical and horizontal features go.

It turns out that the optimization value is one that I suggested before (but computed more precisely this time), and that it is even closer to 1 than the current one:

The new LanczosSharp blur this gives is 0.9891028367558475.

The currently implemented blur is 0.9812505644269356.

That is, the blur with this "better" criterion is even closer to 1 than the current value.

This again points toward ditching the LanczosSharp and Lanczos2Sharp methods (and adding RobidouxSharp). (Although when I get around to programming Jinc-windowed Jinc EWA for GEGL and VIPS I'll use 0.9891028367558475.)

The Axiom code that computes this value:

Code: Select all

)cl a

digits 100

R1 := 3.831705970207512315614435886308160766564545274287801928762298989918839309519011470214112874757423127

r1 := R1 / %pi

R3 := 10.17346813506272207718571177677584406981951250019168555611465006811578704378288387382891893264510929

r3 := R3 / %pi

jinc x == besselJ(1,%pi*x)/x

wind x == besselJ(1,x*(R1/r3))/x

l x == if (x<r3) then ( wind(x) * jinc(x) ) else 0.

f r == [ r, sqrt(1.+1)*r, 2*r, sqrt(1.+4)*r, sqrt(4.+4)*r, 3*r, sqrt(9.+1.)*r, sqrt(9.+4)*r, 4*r, sqrt(16.+1)*r, sqrt(9.+9)*r, sqrt(16.+4)*r, 5*r ]

z := l 1.e-128

totheright r == _
  ( _
      l((f(r)).1) _
    + l((f(r)).3) _
    + l((f(r)).6) _
    + l((f(r)).9) _
    + l((f(r)).13) _
    + 2 * _
    ( _
      l((f(r)).2) _
    + l((f(r)).5) _
    + l((f(r)).11) _
    + 2 * _
    (   l((f(r)).4) _
      + l((f(r)).7) _
      + l((f(r)).8) _
      + l((f(r)).10) _
      + l((f(r)).12) _
    ) ) _
  ) _
  / _
  ( _
    z + _
    4 * _
    ( l((f(r)).1) _
    + l((f(r)).2) _
    + l((f(r)).3) _
    + l((f(r)).5) _
    + l((f(r)).6) _
    + l((f(r)).9) _
    + l((f(r)).11) _
    + l((f(r)).13) _
    + 2 * _
    ( l((f(r)).4) _
    + l((f(r)).7) _
    + l((f(r)).8) _
    + l((f(r)).10) _
    + l((f(r)).12) ) ) )

-- To find the one with sum closest to 0 (this is a fully converged result):

[ totheright(1.011017219685562792881111098110700+.000000000000000000000000000000001*i) for i in 0..10 ]

-- The optimal blur
-- (to minimize the worst change in a vertical or horizontal line under no-op):

1/1.011017219685562792881111098110700

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

Re: proper scaling of the Jinc filter for EWA use

Post by NicolasRobidoux » 2011-12-29T10:01:38-07:00

imaggie wrote:As a result of some testing using windowed jinc on deblur it appears that there is not one "best" choice , indeed windowing is not always advantageous.

As I said elsewhere I think some more thought needs to go into why the window is there and what it is supposed to achieve rather than subjective empirical testing on a perhaps rather ill-defined group of test images.

...
I pretty much agree with everything you wrote here. Although I am not sure that "the mathematicians", dead or alive, have as definite answers as you seem to suggest.

One thing that makes things complicated is that, as explained for example in Turkowski, filter characteristics change a lot depending on the geometrical transformation: a filter which may have a better frequency response in the continuum may have a worse one than bilinear when, say, an image is upsampled by a factor of 2. It's not only the image content that matters, but the geometrical transformation that's applied to the image. That is: Content-adaptivity is not enough, transformation-adaptivity is needed too. And who knows what else.

What I figured is that when downsampling a lot, you can pretty much carry continuum arguments to image processing. When upsampling, however, frequency response arguments are much less reliable.

This is why the archetype "next-generation resampler", the still not quite complete sampler lohalo in GEGL, assembles two pieces: A sampler tuned for upsampling is blended with a sampler tuned for downsampling, the blending depending on (approximations of) the singular values of the transformation at the sampling point: http://git.gnome.org/browse/gegl/tree/g ... r-lohalo.c

(I'm not saying I understand everything.)

My plans (for GEGL, VIPS and similar systems; ImageMagick is not quite set up to do this right now):

nohalo: the current GEGL lohalo: blend a nonlinear interpolatory halo-free scheme good for upsampling (LBB-Nohalo) with a linear interpolatory halo-free EWA scheme, only acceptable for downsampling (EWA Triangle).

lohalo: blend a nonlinear interpolatory bicubic scheme with reduced oscillations ROB (Reduced Oscillation Bicubic), an extension of a method discussed in the soon to be filed thesis of my masters student Chantal Racette) with Robidoux or RobidouxSharp, both linear EWA.

mohalo: blend orthogonal Lanczos 3 (linear and interpolatory) for transformations near pure rotations/translations with the "balanced" (maybe maximally sharpened?) EWA Jinc-windowed Jinc 3. (P.S. I am very tempted to use 4 lobes, but will resist the temptation.) P.S. II: Following discussions with GIMP's gg I think I'll actually promote a blend of orthogonal Sinc-windowed Sinc Lanczos 3-lobe (when the singular values of the local transformation are close to 1) with the slightly improved lightly sharpened EWA Jinc-windowed Jinc Lanczos 3-lobe (otherwise).

lopass (better name: smoother? smooth?): Pure EWA LanczosSharp 3 (linear, non-interpolatory). A bit soft, but really nicely antialiased, without jarring halos (@Imaggie: and you clearly have figured out why: indeed windowing with Jinc minimizes both the sharpening and the haloing, compared with Sinc). Not needed anymore because the previous filter is so good.

Whether Oyvind and the gang will let me is another story, but I think so. I can always realign the plans if something is not up to their snuff.

Quick note: It looks like suitably sharpened EWA Jinc-windowed Jinc 4 works surprisingly well with "old skool CG".
Last edited by NicolasRobidoux on 2012-01-02T11:28:28-07:00, edited 7 times in total.

Post Reply