Page 1 of 16

proper scaling of the Jinc filter for EWA use

Posted: 2011-10-14T08:04:36-07:00
by NicolasRobidoux
I'm (still) thinking about how to improve EWA filtering. I don't find any of the available filters completely satisfactory yet.

There are two issues that I'd like to understand better w.r.t. the Jinc filter, and which I can't settle with a quick and dirty literature search:

1) What is the best "blur", that is, if what should the scaling of the Jinc filter be. Unlike for the sinc function, for which obviously one wants the cardinal function to have a zero at every image grid location, the issue of scaling of the JInc function is not completely clear, given that it is impossible to align more than one of its zeros with the pixel grid. More or less, it's been assumed by everyone that the starting point is blur=1, and indeed this works pretty well, although it's pretty blurry. But I'm really not sure it's right.

2) What is the best windowing function? It's been assumed (e.g. Gustafsson's Interactive Image Warping) that just like Lanczos is Sinc-windowed Sinc, the right thing to do is to window Jinc with itself. One consequence is that the EWA Lanczos kernel decays very fast away from its center, which prevents the use of small blur because you need to give it some spread to prevent "nearest neighbour type" behavior. For example, it would appear to me that Jinc would be better windowed with J_0, although my argument for this is really wishy washy.

Questions:

A)

Does anybody know right off the bat what the frequency response cutoff of the standard Jinc filter, that is, J_1(pi r)/r, is?

I don't see in the easily found literature a statement telling me whether it's 1 or 2/sqrt(2) = sqrt(2)---either value would make sense. (The frequency response plot in Gustafsson is not produced so it's easy to read. It looks like sqrt(2) to me, and the text before figure 5 of his Masters thesis suggests it probably is. However, he uses J_1(2 pi r)/r, which is different than what is apparently in resize.c.)

P.S.: The answer is here: http://books.google.ca/books?id=w3BpSIx ... ff&f=false. I'm also getting my hands on Pratt's book, which is references in the resize.c code.

P.S. II The last inequality on page 96 of Pratt's book makes it clear that the critical w_0 is sqrt(2) pi. Resize.c uses pi (one times pi, if you will, instead of sqrt(2) times pi). So, my hunch was right that the currently used default Jinc is almost certainly needlessly blurry, statement which should not surprise too many people. When I have time, I'll look at the windowing issue.

B)

It would appear to me that the cutoff frequency of the unwindowed Jinc filter should be adjusted (with blur) so it is 2/sqrt(2) if it's not already. The reason is that this is the highest frequency that can be found in an image (it is obtained by alternating black and white diagonals). So, if the answer to A) is 1 instead of sqrt(2), this gives some motivation to making the blur smaller, which should lead to a less blurry scheme.

C)

However, making the blur smaller with Jinc-windowed Jinc leads to jaggies galore. So: Does anybody know anything solid about what the windowing function should be? I'm hoping that the "right" windowing will help with aliasing if blur is set to 1/sqrt(2), and with blurriness otherwise.

When I have time (not for a while), I'll do a more in-depth literature search. And I may start experimenting.

Re: proper scaling of the Jinc filter for EWA use

Posted: 2011-10-14T10:06:01-07:00
by fmw42
Pratt's book has very little -- just the formula and a sentence or two (at least in my 1978 edition).

This might be of interest:

The fourier transform of the jinc is a circle (circular rect). So it has a sharp cutoff frequency.

http://muti.lbl.gov/145b/errata_lecture5.pdf

http://see.stanford.edu/materials/lsoftaee261/chap8.pdf

http://books.google.com/books?id=d8FMlH ... on&f=false (questionable relevance)

http://www.phys.unsw.edu.au/opto/AdvOptics/UNIT5.PDF (questionable relevance)

http://books.google.com/books?id=ow5xs_ ... on&f=false

http://people.csail.mit.edu/halordain/2 ... t%20IV.pdf

http://people.ccmr.cornell.edu/~davidm/ ... rms-2D.pdf

http://www.google.com/url?q=http://www. ... gTmaGJjNug

Re: proper scaling of the Jinc filter for EWA use

Posted: 2011-11-10T17:20:25-07:00
by NicolasRobidoux
Now, here's a funny coincidence:

If you scale the JInc zeros "correctly," the fourth one lands at 2.99888431.

This means that the support of Jinc 4 is just a touch smaller than the support of Sinc 3, which suggests that they should "blend" well.

The other thing is that, at first sight, Jinc 2 and Jinc 4 seem to "do the right thing" with the checkerboard mode, at least qualitatively. To be continued...

Re: proper scaling of the Jinc filter for EWA use

Posted: 2011-11-11T10:47:09-07:00
by NicolasRobidoux
Well, this appears to be a case where I can't use the theory to make the application work better:

None of the following give acceptable results (note that the blur = 1/sqrt 2 in all cases):

Code: Select all

convert rose: -define filter:filter=Jinc -define filter:window=Box -define filter:lobes=2 -define filter:blur=.7071067811865475244 -distort Resize 3000% rose_jinc2.png
convert rose: -define filter:filter=Jinc -define filter:window=box -define filter:lobes=3 -define filter:blur=.7071067811865475244 -distort Resize 3000% rose_jinc3.png
convert rose: -define filter:filter=Jinc -define filter:window=box -define filter:lobes=4 -define filter:blur=.7071067811865475244 -distort Resize 3000% rose_jinc4.png
convert rose: -define filter:filter=Jinc -define filter:window=Box -define filter:lobes=8 -define filter:blur=.7071067811865475244 -distort Resize 3000% rose_jinc8.png

convert rose: -define filter:filter=Jinc -define filter:window=Jinc -define filter:lobes=2 -define filter:blur=.7071067811865475244 -distort Resize 3000% rose_l2.png
convert rose: -define filter:filter=Jinc -define filter:window=Jinc -define filter:lobes=3 -define filter:blur=.7071067811865475244 -distort Resize 3000% rose_l3.png
convert rose: -define filter:filter=Jinc -define filter:window=Jinc -define filter:lobes=4 -define filter:blur=.7071067811865475244 -distort Resize 3000% rose_l4.png
convert rose: -define filter:filter=Jinc -define filter:window=Jinc -define filter:lobes=8 -define filter:blur=.7071067811865475244 -distort Resize 3000% rose_l8.png
So, unless I've made a mistake in assembling the various pieces of information, this appears to be a dead end.

Re: proper scaling of the Jinc filter for EWA use

Posted: 2011-11-13T23:13:52-07:00
by anthony
NicolasRobidoux wrote:Now, here's a funny coincidence:

If you scale the JInc zeros "correctly," the fourth one lands at 2.99888431.
Sounds a lot like the another coincidence...
e^pi - pi = 19.999099979

See http://xkcd.com/217/

As for
The other thing is that, at first sight, Jinc 2 and Jinc 4 seem to "do the right thing" with the checkerboard mode, at least qualitatively.
That is not surprising to me, I even mention it in my filter notes for Jinc circular filters.
and specifically for "Distort and Filters in the No-Op case"
http://www.imagemagick.org/Usage/ resize/#jinc

Basically Jinc 2 subtracts immediatally orthogonal neighbour from the immediate diagonal. producing a reasonably good result, generally. Though it blurs 'hash patterns' rather extensively. Something that is not good for small GIF image work which makes heavy use of pixel hash patterns. Jinc 3 subtracts the next lot of orthoginal, generally making it worse, while jinc 4 adds the next set of diagonals again.

That makes Jinc-2 and Jinc-4 are quite good while jinc 3 quite bad. Not certain what happens after that, not much probably because as you say even un-windowed Jinc has a much stronger roll off than Sinc.

Re: proper scaling of the Jinc filter for EWA use

Posted: 2011-11-13T23:36:40-07:00
by anthony
Try this...

No blur... Sinc window verses Box window

Code: Select all

  convert rose: -define filter:filter=Jinc -define filter:window=Sinc -define filter:lobes=4  -distort Resize 100% show:
  convert rose: -define filter:filter=Jinc -define filter:window=Box -define filter:lobes=4 -distort Resize 100% show:
Adding your blur to any of these just makes strong aliasing effects. I don't think you are on the right track!

Re: proper scaling of the Jinc filter for EWA use

Posted: 2011-11-14T05:23:15-07:00
by NicolasRobidoux
anthony wrote:...
The other thing is that, at first sight, Jinc 2 and Jinc 4 seem to "do the right thing" with the checkerboard mode, at least qualitatively.
That is not surprising to me, I even mention it in my filter notes for Jinc circular filters.
and specifically for "Distort and Filters in the No-Op case"
http://www.imagemagick.org/Usage/resize/#jinc
Now that you mention it, I remember reading about this a while ago. Plagiarism is the sincerest form of flattery...

Re: proper scaling of the Jinc filter for EWA use

Posted: 2011-11-14T07:30:48-07:00
by NicolasRobidoux
Let's see if I can improve my "conjecture batting average."

There is starting to be a good amount of evidence that (when not downsampling) with EWA there is cross-over of "good things in the orthogonal case" to "good things in the EWA case."

(Through Anthony's writings, it appears that this dawned on him way before me.)
  • The "right" scaling of the Jinc function corresponds to the maximum "orthogonal" frequency (this thread); and
  • The Keys filters (characterized by minimizing the affine data reconstruction when used as orthogonal interpolators) are best w.r.t. the same criterion when used as EWA filter kernels (http://imagemagick.org/discourse-server ... 22&t=19823).
Given this surprising correspondence, it would appear to make sense that windowing functions that work well orthogonally (hello Sinc!) would work well with EWA.

When I have a minute, I'll check.

Re: proper scaling of the Jinc filter for EWA use

Posted: 2011-11-14T19:17:21-07:00
by NicolasRobidoux
Interesting: There appears to be little difference between windowing with the first lobe of the Jinc function and the first lobe of the Sinc function:

Code: Select all

convert rose: -define filter:window=Sinc -define filter:lobes=3 -filter Jinc -distort Resize 3000% rose_JincSinc3.png
convert rose: -filter Lanczos -distort Resize 3000% rose_Lanczos.png
(Distort Lanczos is Jinc-windowed Jinc 3.)

Now, I'd love to figure an excellent scheme which would consist of combining Jinc and Sinc because then I'd call it the "ginseng filter." I'll have a go when I have time.

Re: proper scaling of the Jinc filter for EWA use

Posted: 2011-11-14T22:11:31-07:00
by anthony
My own view of windowing (windowed Sinc) is that as long as you scale the curve to zero, and don't clip it at a non-zero point, you will generally get a reasonable result.

You seem to get fairly good results for a 'bartlett' filter (with a triangular or linear windowing method), vs a welsh (parabolic), vs, Hamming/Hamming (Sin curve) vs Blackman, or even Parezen (Cubic). The only reason Lanczos (first lobe of Sinc as a windowing function) seems to have been settled upon is that it seems to be logical.

I have read papers, and see frequency response curves, but it all seem, guess work with little concerte evidence as to the best way of windowing a Sinc function.

Now in EWA Jinc windowed Jinc seems a natural extension. But it may as well have been a Sinc Windowed Jinc, or Blackman windowed Jinc, for all the differences I have seen in the results. I get better results using the specialised sharpened or Robidoux filters than I do for a direct Windowed Jinc.

Aside: if you use a 'Blackman' filter, or any other 'windowing filter' with EWA, you will actually get a Jinc filter with an appropriate Blackman windowing function. Blackman has a extremely sharp roll off, compared to any other windowing function. For A Sinc windowing function you will need to be more explicit as shown in examples above ;-)

Re: proper scaling of the Jinc filter for EWA use

Posted: 2011-11-15T05:59:13-07:00
by NicolasRobidoux
anthony wrote:... For A Sinc windowing function you will need to be more explicit as shown in examples above ;-)
Just to make sure: Did I did something wrong?

Re: proper scaling of the Jinc filter for EWA use

Posted: 2011-11-15T06:29:53-07:00
by NicolasRobidoux
Anthony: Did I read right that you find results quite good with Bartlett-windowed Sinc?

Better, more or less, than the other ones?

Because if this is the case, despite the fact that Bartlett introduces a derivative discontinuity at the original pixel locations, this suggests that windowing should be done with a partition of unity function, which I would suggest should be the B-spline of extent matching the extent of the function being windowed. (Support 1/2: Box; 1: triangle; 1.5: Quadratic B-spline; 2: Cubic B-spline; 2.5: Quartic B-spline...) P.S. Hmmm! I may have to sit down and think more carefully about what Barlett being a good windowing means.

A good approximation of the above is the normal curve of matching sigma.

Do you have links or at least article names for the better references you have about windowing? (Of course I know about Turkowski.)

Re: proper scaling of the Jinc filter for EWA use

Posted: 2011-11-15T06:34:44-07:00
by NicolasRobidoux
The issue with windowing in image processing is that frequency response only tells the smaller part of the story in this situation, esp. when upsampling.

Re: proper scaling of the Jinc filter for EWA use

Posted: 2011-11-15T08:01:49-07:00
by NicolasRobidoux
Here is one that seems pretty good:

Code: Select all

convert rose: -define filter:filter=Jinc -define filter:window=Sinc -define filter:lobes=3 -define filter:blur=.9264075766146 -distort Resize 3000% rose_JincSinc3support3.png
P.S. Could be argued to be nicer than standard (orthogonal) Lanczos 3.

P.S. 2 The blur is 3/r3, where r3 is the third root of the Jinc function. In other words, the blur was fixed so that the radius of the resulting EWA disc is exactly 3.

Re: proper scaling of the Jinc filter for EWA use

Posted: 2011-11-15T12:33:04-07:00
by NicolasRobidoux
It appears that windowing with Sinc gives a family of schemes which is very different than windowing with Jinc.

If I apply the usual "worst case deviation when the center pixel takes an extreme value" optimization (like I did for RobidouxSharp) I get a blur for the "ginseng" filter (I just can't resist: this name is just too
cute) scheme equal to 1/1.131540185972007785 = 0.883751202473632831, which makes the radius of the corresponding filter smaller than 3 (equal to 2.8618652031208957467, actually).

Now, this value of the "minimal worst deviation blur under no-op" was obtained by very quickly done numerical experiments. I include below the axiom (FLOSS computer algebra system) which produces the "converged" result:

Code: Select all

)cl a

)se fu ca 9

digits 100

r1 := (3.831705970207512315614435886308160766564545274287801928762298989918839309519011470214112874757423127 / %pi)

r3 := (10.17346813506272207718571177677584406981951250019168555611465006811578704378288387382891893264510929 / %pi)

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

-- sinc x == besselJ(1,%pi*x/r3)/x

sinc x == r3*sin(%pi*x/r3)/(%pi*x)

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

plus x == max(l x,0)

minus x == -min(l x, 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 := 2.4674

-- z := (jinc .000000000000000000000001)

z := jinc 1.e-128

gplus(r) == _
  ( _
  4 * _
  ( plus((f(r)).1) _
  + plus((f(r)).2) _
  + plus((f(r)).3) _
  + plus((f(r)).5) _
  + plus((f(r)).6) _
  + plus((f(r)).9) _
  + plus((f(r)).11) _
  + plus((f(r)).13) _
  + 2 * _
  ( plus((f(r)).4) _
  + plus((f(r)).7) _
  + plus((f(r)).8) _
  + plus((f(r)).10) _
  + plus((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) ) ) )

gminus(r) == _
  ( _
  4 * _
  ( minus((f(r)).1) _
  + minus((f(r)).2) _
  + minus((f(r)).3) _
  + minus((f(r)).5) _
  + minus((f(r)).6) _
  + minus((f(r)).9) _
  + minus((f(r)).11) _
  + minus((f(r)).13) _
  + 2 * _
  ( minus((f(r)).4) _
  + minus((f(r)).7) _
  + minus((f(r)).8) _
  + minus((f(r)).10) _
  + minus((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) ) ) )

[ gplus(1+.000000000000000001*i) - gminus(1+.000000000000000001*i) for i in 131540185972007770..131540185972007800 ]
This is definitely an interesting scheme:

Code: Select all

convert rose: -define filter:filter=Jinc -define filter:window=Sinc -define filter:lobes=3 -define filter:blur=.883751202473632831 -distort Resize 3000% rose_ginseng.png