Gamma-aware, dithered colorspace conversion and resizing

[madshi]

Let me just say that if you are preserving aspect ratios exactly, then you won't have ellipses: only disks.

If you don't reduce in any of the two directions (for example, if you are enlarging in both directions, or keeping one dimension the same and enlarging in the other), you will get disks, not ellipses.

But if your resize ratio is slightly different horizontally and vertically, and you are downsampling in at least one direction, then you'll get ellipses aligned with the axes instead of disks.

More wishy washy: Your image may have sampled the world on a uniform grid, but the world is not laid out on a uniform grid. Some of the artifacts one gets with common samplers are a consequence of being enslaved to Descartes. Using rotationally invariant samplers takes off these shackles.
Ok, makes sense.

Personally, I'm not much of a math/science guy. I usually understand things best by looking at code. Do you happen to have a Jinc EWA implementation which is as simple and short as possible? Ideally only targetted at up/downscaling (not for rotations or anything else), optimized for easy understanding instead of speed? That would go a long way helping me understand the basic principle of how Jinc EWA differs from convential linear resamplers.

If you find something that works, overall, better with natural images, let me know.
I've found that ICBI (which I've modded to not ring) produces better results than simple linear Lanczos. But NNEDI3 seems to be even better. See here:

original: http://img69.imageshack.us/img69/6127/z3hs1n8ns1t.png
spline36: http://bengal.missouri.edu/~kes25c/castle_spline36.png
NNEDI3: http://bengal.missouri.edu/~kes25c/castle_abs.png

[PhrostByte]

Personally, I'm not much of a math/science guy. I usually understand things best by looking at code. Do you happen to have a Jinc EWA implementation which is as simple and short as possible? Ideally only targetted at up/downscaling (not for rotations or anything else), optimized for easy understanding instead of speed? That would go a long way helping me understand the basic principle of how Jinc EWA differs from convential linear resamplers.

I'm the same way! I'd love to see some simple code for it so I can try it out here.

I did notice some of this stuff while digging through ImageMagick's code, but didn't understand what it was doing so I left it alone. Overall ImageMagick has a far more interesting resampling system.

[NicolasRobidoux]

...
I've found that ICBI (which I've modded to not ring) produces better results than simple linear Lanczos. But NNEDI3 seems to be even better.
...

The *NEDI* people have done great work, and I consider their methods my only "real" competition in the quality department (if you forgive the boast contained in this statement).

(I still need to do a more careful comparison. Waiting for sabbatical or unemployment so I can get some work done.)

[madshi]

I'm the same way!
Yeah, we programmers are weird. We prefer code over plain English explanations... :)

The *NEDI* people have done great work, and I consider their methods my only "real" competition in the quality department (if you forgive the boast contained in this statement).
FWIW, NNEDI3 is not related to NEDI in any way. I don't like most of the NEDI variations much, personally, because they have loads of weird directional artifacts. NNEDI3 is a completely different solution, based on a trained neural network. As far as I can see: NEDI < ICBI < NNEDI3. But I guess this is OT here.

[NicolasRobidoux]

...
Do you happen to have a Jinc EWA implementation which is as simple and short as possible? Ideally only targetted at up/downscaling (not for rotations or anything else), optimized for easy understanding instead of speed? That would go a long way helping me understand the basic principle of how Jinc EWA differs from convential linear resamplers.
...

Unfortunately this is not something I will be able to put time into for a few months. At this point, your best bet is the (not yet fully optimized) ImageMagick code found here:

http://trac.imagemagick.org/browser/ImageMagick/trunk/magick/distort.c

http://trac.imagemagick.org/browser/ImageMagick/trunk/magick/resample.c

http://trac.imagemagick.org/browser/ImageMagick/trunk/magick/resize.c

[NicolasRobidoux]

...
FWIW, NNEDI3 is not related to NEDI in any way. I don't like most of the NEDI variations much, personally, because they have loads of weird directional artifacts.
...

Thank you anyway for the info.

I had not done a careful comparison, but iNEDI seemed to work pretty well with my limited testing.

[madshi]

Unfortunately this is not something I will be able to put time into for a few months. At this point, your best bet is the (not yet fully optimized) ImageMagick code
Thanks, will have a look when I find some time.

I had not done a careful comparison, but iNEDI seemed to work pretty well with my limited testing.
ICBI was created by the same guys who created iNEDI. ICBI is newer than iNEDI and as far as I can see, it's faster and has better image quality. But NNEDI3 seems to be even better than ICBI, judging from a quick comparison.

[NicolasRobidoux]

...
ICBI was created by the same guys who created iNEDI.
...

Oops! I indeed meant ICBI, not iNEDI.

[markanini]

Install a recent version of ImageMagick and try any resizing task (up/down/mix and match) with "convert -filter lanczossharp -distort resize".
Just tried this on a half dozen photographic images. Smooth yet detailed, very nice. On one problematic image with combined aliasing/ringing/moire I modified the command line to use the filter with your name and got a result that got me a (subjectively) better detail-to-artifacts ratio than anything I could get out of Avisynth.

[madshi]

@markanini, can you upload your "problematic image" and the result you got with ImageMagick?

[NicolasRobidoux]

...
On one problematic image with combined aliasing/ringing/moire
...
When moire is a concern, it should surprise no-one that "convert -filter lanczos -distort resize" is a safer
bet than "convert -filter lanczossharp -distort resize". (The results are generally almost the same, however, so this substitution may not make much difference.)

And yes, "convert -filter robidoux -distort resize" or "convert -distort resize" (since robidoux is the default---not my decision) is an OK scheme. Robidoux is kind of the Mitchell-Netravali of the Clamped EWA world. I don't particularly like it, but many people find it to be "balanced." Also: Robidoux is just about as cheap a Clamped EWA scheme can be.

I'm not being falsely modest here: I strongly believe that "distort lanczossharp" and "distort lanczos" are better all around schemes.

(Oh! And Robidoux would make Don Munsil happy: 2-lobe filter (like Catmull-Rom, Mitchell-Netravali and Lanczos 2) constructed with no direct consideration of frequency response (although there is a surprising connection to Jinc Lanczos 2: see http://www.imagemagick.org/Usage/resize/#robidoux).)

[markanini]

@markanini, can you upload your "problematic image" and the result you got with ImageMagick?

Sure:http://imgur.com/a/javFH
Originally a cameraphone image, cropped, NNEDI3 x4 upsized, de-convolution sharpened luminance.

[NicolasRobidoux]

...
NNEDI3 x4 upsized, de-convolution sharpened luminance.
All bets are off with "originals" which actually are sharpened enlargements.

[markanini]

Fair enough, the real original:
http://imgur.com/jE0US

EDIT: Actually it may have been resized and re-compressed. It's from the photographers blog. He didn't keep the original so I can't tell what's been done to it. I played bass guitar in this band while it lasted. Sorry about any confusion.

[NicolasRobidoux]

Mark: Thank you for the precisions.

This would appear to explain the "amazing" performance of the Robidoux filter in this particular instance. (Phew! My bad name is saved.)

[madshi]

Eeeeuw, the "original" looks totally awful. Not a good candidate for comparison, IMHO. Also I'm more interested in upscaling than in downscaling. Thanks, anyway, though!

@PhrostByte, hope you don't mind the off-topic chat.

[markanini]

I just want to add that the image host's layout lets you compare the Clamped EWA Robidoux to your browsers resizing algo. In Chrome I see close to equal amounts of texture in the brickwork and left hand side of the tent yet markedly less artifacting in the Robidoux version when looking at the checkerboard tiles and any hard edges like the speaker stands.

[*.mp4 guy]

Browser interpolation is notoriously terrible. Anything anyone would normally consider using would be better.

[henryho_hk]

Since EWA distort involves much more pixels than normal resizers, may I presume that there is a greater need to "linearize" the image beforehand?

[NicolasRobidoux]

Since EWA distort involves much more pixels than normal resizers, may I presume that there is a greater need to "linearize" the image beforehand?

It should not make much difference.

Also:

EWA Robidoux only requires about 4pi/16 of the input values required by orthogonal bicubic or Lanczos 2 filtering (or interpolation if you are enlarging). Note that 4pi/16 < 1.

EWA Jinc Lanczos 3 and EWA Jinc Lanczos 3 "sharp" require a little more than 9pi/36 of the input values required by orthogonal Lanczos 3 filtering. Again, 9pi/36 < 1.

That is: Generally, EWA resizing methods use less input data than comparable orthogonal resize methods.

(The above estimates are for reducing. They are pretty rough for enlarging. When I have more time, I'll compute the exact ratios when enlarging. But the gist is correct.)

[markanini]

Browser interpolation is notoriously terrible. Anything anyone would normally consider using would be better.

I neglected to mention my browser induced artifacts we're similar to what I got using anything else inside or outside of Avisynth that didn't cause significant blurring. So in this case I found a exception to your resoning, which I agree with in general, in favor of EWA Robidoux. For the first time I can at least view this image at arms length from my screen and not be too annoyed. Not to kiss mr. Robidoux ass, I'd be glad to hear about anything else that might benfit this image, which AFAIK is unlikely unless a better NNEDI3 or better deconvolution sharpening becomes available which is nothing I'll hold my breath for. I'll leave it at that.

[*.mp4 guy]

I should not make much difference.

Also:

EWA Robidoux only requires about 4pi/16 of the input values required by orthogonal bicubic or Lanczos 2 filtering (or interpolation if you are enlarging). Note that 4pi/16 < 1.

EWA Jinc Lanczos 3 and EWA Jinc Lanczos 3 "sharp" require a little more than 9pi/36 of the input values required by orthogonal Lanczos 3 filtering. Again, 9pi/36 < 1.

That is: Generally, EWA resizing methods use less input data than comparable orthogonal resize methods.

(The above estimates are for reducing. They are pretty rough for enlarging. When I have more time, I'll compute the exact ratios when enlarging. But the gist is correct.)
Presumably you are talking about orthogonal linear interpolation as if it was carried out on a two dimensional area, This is not the case, As I believe was mentioned in reference to the superiority of ewa filters.

A 2 lobe orthogonal linear interpolator would typically require 7.5 total input pixel operations per input pixel (IPOPIP's) for a 2:1 downscale, as implemented by a separable filter, whereas it would take 25 IPOPIP's if implemented as a 2 dimensional filter. I cannot see how a viable 2 lobed interpolation kernel could be implemented with less then 7.5 IPOPIP's, though 25 IPOPIP's is an easily bested number.

Its possible I have misunderstood you due to differing conventions, but that's how it hashes out after everything is broken down into convolution operations.

[edit}
I neglected to mention my browser induced artifacts we're similar to what I got using anything else inside or outside of Avisynth that didn't cause significant blurring. For the first time I can at least view this image at arms length from my screen and not be too annoyed. Not to kiss mr. Robidoux ass, I'd be glad to hear about anything else that might benfit this image, which AFAIK is unlikely unless a better NNEDI3 or better deconvolution sharpening becomes available which is nothing I'll hold my breath for. I'll leave it at that. What exactly is your desired use case for this image? are you trying to make it as large as the nnedi3/deconvolution image, or trying to make it as large as the Robidoux downscale? the whole thing doesn't make much sense to me.

[NicolasRobidoux]

There indeed seems to be some misunderstanding going on here.

First, my "I(t) should not make much difference" (yes, there was a typo, a missing "t") was an answer to henryho_hk 's question "Since EWA distort involves much more pixels than normal resizers, may I presume that there is a greater need to "linearize" the image beforehand?", which I understood as concerning the use of linear light.

In this context, I was not counting flops---flop-wise, an EWA method is definitely more expensive than a comparable separable method implemented accordingly---I was counting the raw number of values that are combined to get a single output value.

Let's compare, say, the typical number of pixels "averaged" to get an orthogonal Lanczos 2-lobes or Bicubic (Keys filtering or cubic B-Spline smoothing, say) filtered output value when downsampling by a factor of 2 in both directions, to the number required by Clampled EWA Robidoux of Jinc Lanczos 2.

Note also that I am filtering, not interpolating. If you are doing a 2:1 downscale by interpolating, you are begging for moire and jaggies. Not as much if you filter. So, generally, I don't recommend using interpolation in and by itself when downsampling. (Of course, you could low pass the original with, for example, box filtering, and then interpolate, but this is not what I'm comparing. I'm looking at using exactly one filter to do the downsampling. Please clarify if I am missing something.)

For simplicity, I'll consider an output pixel value located at the average of four nearby input pixel locations ("interlaced," kind of). I could also consider other locations, to get a typical value.

With the orthogonal versions, you are grabbing everything that falls strictly within a (2*4)x(2*4)=8x8 square centered at the output location. This is 64 pixel values.

With the EWA versions, you are grabbing everything that falls within a disk of radius 2*2=4 (actually, EWA Jinc Lanczos 2 extends slightly past radius 2; I'll ignore this for now; I like Robidoux more anyway). A little programming establishes that there are 52 such pixel locations.

Compare this to my earlier estimate:

52/64 = .81

4pi/16 = .79

Pretty close.

(Yes, I understand that I should consider other possible locations for the output pixel and average the counts. I need coffee.)

-----

P.S. It finally dawned on me what IPOPIP count is. I'll do THAT count in a future post.

Presumably you are talking about orthogonal linear interpolation as if it was carried out on a two dimensional area, This is not the case, As I believe was mentioned in reference to the superiority of ewa filters.

A 2 lobe orthogonal linear interpolator would typically require 7.5 total input pixel operations per input pixel (IPOPIP's) for a 2:1 downscale, as implemented by a separable filter, whereas it would take 25 IPOPIP's if implemented as a 2 dimensional filter. I cannot see how a viable 2 lobed interpolation kernel could be implemented with less then 7.5 IPOPIP's, though 25 IPOPIP's is an easily bested number.

Its possible I have misunderstood you due to differing conventions, but that's how it hashes out after everything is broken down into convolution operations.
...

[NicolasRobidoux]

If the question is: "Will an EWA method run as fast for resizing as a comparable separable method?", the answer is "No."

As far as the method I'm promoting (Clamped EWA Jinc lanczossharp, which is not the same as Clamped EWA Robidoux) goes, the filter kernel's support is a disk with radius slightly larger than 3. We are certainly not talking about greased lightning.

[*.mp4 guy]

Note also that I am filtering, not interpolating. If you are doing a 2:1 downscale by interpolating, you are begging for moire and jaggies. Not as much if you filter. So, generally, I don't recommend using interpolation in and by itself when downsampling. (Of course, you could low pass the original with, for example, box filtering, and then interpolate, but this is not what I'm comparing. I'm looking at using exactly one filter to do the downsampling. Please clarify if I am missing something.)(lowpass) Filtering and interpolation are functionally the same in this case, they both are carried with the same operation.

[NicolasRobidoux]

Assuming I understand correctly what IPOPIP is, with the geometry I described in my earlier post, an orthogonal two-lobe filter will require 4 IPOPIP to downsample by a factor of 2 in a data driven implementation exploiting separability, and an EWA two-lobe filter will require 13 in the same context. (A bit shaky on the computation but I think I got the drift.)

[henryho_hk]

I love EWA when processing still photos.... though it may be too luxurious for video processing.

[PhrostByte]

Here's version 7. Mostly optimizations -- significantly faster on my Core 2 Quad, I'm curious to see how it performs versus v6 on a >4 core CPU, and ones with AVX capability. Also includes kernel visualizations (http://svn.int64.org/viewvc/int64/resamplehq/doc/kernels.html).

http://sourceforge.net/projects/int64/files/ResampleHQ/ResampleHQ-v7.zip/download

Changelog:

Multi-core optimizations.
SSE/AVX vertical resampler.
AVX implementations of all conversions.
Optimizations to SSE RGB conversions.
Significant memory use reduction and minor optimizations to dithered RGB output.
Better compatibility with Avisynth built-in resizers.
Add kernel visualization docs.
Remove 64-bit version temporarily.


Going to look at EWA for next version, as well as figure out why 64-bit is crashing Avisynth.

[henryho_hk]

Gamma-aware EWA? Woh!

[NicolasRobidoux]

...
Going to look at EWA for next version, as well as figure out why 64-bit is crashing Avisynth.

FYI

1) The ImageMagick code implementing the best (IMHO) upsampling EWA filter, namely lanczossharp, uses a somewhat slow method of computing the weights. My student Chantal Racette and I will be putting together a faster way of doing this this Summer.

2) There is a very simple EWA implementation (using the teepee, that is, cone filter, which is not very good for upsampling) currently being built into a GEGL method. Its code is sufficiently advanced to be poached. The source code is found here: http://git.gnome.org/browse/gegl/tree/gegl/buffer/gegl-sampler-lohalo.c

Further developments are found in the samplers branch.

You may also contact me directly (or post here) if you have questions.

[henryho_hk]

PhrostByte, I have a suggestion on the kernel visualiization html.

The kernel names are now taking too much vertical space. Can they be arranged in columns like a table?

[NicolasRobidoux]

PhrostByte:

Suggestion if you are going to implement EWA in a "scanline friendly" environment for resizing:

Resize to a nearby or larger resolution which is a power of two (so that the EWA coefficients can be recycled every so many scanlines) and finish with an other scheme (bilinear, even).

[PhrostByte]

FYI

1) The ImageMagick code implementing the best (IMHO) upsampling EWA filter, namely lanczossharp, uses a somewhat slow method of computing the weights. My student Chantal Racette and I will be putting together a faster way of doing this this Summer.

2) There is a very simple EWA implementation (using the teepee, that is, cone filter, which is not very good for upsampling) currently being built into a GEGL method. Its code is sufficiently advanced to be poached. The source code is found here: http://git.gnome.org/browse/gegl/tree/gegl/buffer/gegl-sampler-lohalo.c

Further developments are found in the samplers branch.

You may also contact me directly (or post here) if you have questions.

EWA looks pretty much how I imagined it, just using the basic distance formula to find the sample distance passed to the kernel.

All the Jinc function stuff is completely greek to me, though :)

PhrostByte:

Suggestion if you are going to implement EWA in a "scanline friendly" environment for resizing:

Resize to a nearby or larger resolution which is a power of two (so that the EWA coefficients can be recycled every so many scanlines) and finish with an other scheme (bilinear, even).

I think a significant portion of EWA can be implemented with SIMD, so I should be able to get it pretty fast without sacrificing any quality.

PhrostByte, I have a suggestion on the kernel visualiization html.

The kernel names are now taking too much vertical space. Can they be arranged in columns like a table?

I've been trying to find a better place to put them for a while, to no avail. They should arrange into columns already on Firefox/WebKit.

[NicolasRobidoux]

Clarification RE: something I wrote earlier: ImageMagick does use efficient formulas for the computation of the jinc 1 function. However, current research will lead to even faster approximations of the best radial kernels, most likely within two months or so.

[NicolasRobidoux]

Clarification RE: something I wrote earlier: ImageMagick does use efficient formulas for the computation of the jinc 1 function. However, current research will lead to even faster approximations of the best radial kernels, most likely within two months or so.
... in particular, there will be no need for square roots of the distances: short polynomial expansions will use x^2+y^2 (x is horizontal distance between data point and sampling point, y is vertical distance) directly, and there will be no need to compute jinc1 twice (once for the filter, once for the windowing function).

[PhrostByte]

Version 8. Again, mostly optimizations—overall 2–3x as fast as v7, and in particular resizing RGB is actually slightly faster than Avisynth's gamma-ignorant resizers.

http://sourceforge.net/projects/int64/files/ResampleHQ/ResampleHQ-v8.zip/download

Changelog:

RGB8-specialized gamma corrections—15% faster color conversions.
New gamma correction approximations—200% faster color conversions.
SSE horizontal resampler—25% faster resizing.
Cache optimizations to vertical resampler—10% faster resizing.
Experimental (untested) FMA4 color conversions for AMD Bulldozer.
Reduced memory usage.
Remove automatic multithreading in favor of SetMtMode.
Bug fix: handle very tiny row widths.


64-bit is still not working. I am very puzzled by this—the error "Evaluate: Unrecognized exception!" is happening outside of my code: after AvisynthPluginInit2 finishes successfully and before GetFrame is called. Any devs with 64-bit plugins have some advice?

[henryho_hk]

New version! Woh!

[SubJunk]

Thanks a lot for the update

[henryho_hk]

V8 is giving black screen my computer upsizing 720x480 YV12 source to 1280x720. XP 64bit + Avisynth x86 DLL 2.6.0.2, dated 2011/05/25.

Now I am trying to isolate the test case.

Edit: No more problems with SEt's 2.6 MT 2011.09.13

[killazys]

Question... is resizing/colorspace correction related to the bit depth? As in, Hi10P vs. 8bit? And.. if I'm going to be resizing from 1080p to 720p with no colorspace changes, what's the purpose of "gamma-awareness?" Am I missing something?

[PhrostByte]

Question... is resizing/colorspace correction related to the bit depth? As in, Hi10P vs. 8bit? And.. if I'm going to be resizing from 1080p to 720p with no colorspace changes, what's the purpose of "gamma-awareness?" Am I missing something?

Bit-depth is unrelated to color-space, resizing, or gamma-aware processing. A higher bit depth will allow you to process and store color more accurately -- nothing more. In practice it lets you represent gradients with less banding.

You can think of gamma-aware processing as treating your image as if it were actual light rather than the typical computerized representation of color. It gives you a more visually correct resize. It's not related to color-space, and doesn't matter if you're converting or not. Simply resizing from 1080p->720p is enough to warrant gamma-aware processing.

I'm moving houses so I won't have enough time for a couple days, but if you want a more detailed explanation I can give one then.

Happy scripting!

[jmac698]

One visible effect is that small points of light will look brighter, which is how they should be.

[jmac698]

Oh Phrost,
What is the best resizer to get back the original image again? For example blur(1).resize(width*1.3,height).resize(width/1.3,height) where the first step is to ensure it's low bandwith, the last two steps should have virtually no effect.

[NicolasRobidoux]

REL=: ... if I'm going to be resizing from 1080p to 720p with no colorspace changes, what's the purpose of "gamma-awareness?" Am I missing something?

Many colour spaces do not measure light/colour intensity with units which are "physically relevant." Instead, they use a "ruler" to represent light/colour intensity which has tickmarks at irregular "physical units."

For example, 0 to 5 in sRGB correspond to light intensities which are much closer to each other in "physical terms" than 200-205, in part to make up for the fact that our eyes are more discriminating of slight shade differences between dark colours than slight shade differences between bright ones. So, if you are only going to store 256^3 shades, you should pack more dark shades than light shades, hence the ruler with denser tick marks near zero than elsewhere.

Many people argue that image resampling should be done in so-called "linear light", meaning light in units that are physically, as opposed to perceptually, relevant (or even matched to hardware specs), because the process of resampling then matches more closely what happens in the real world when, roughly, you have a digital camera with much denser, or less dense, sensors.

Gamma-aware resampling converts the image, measured in "nonlinear" units, to one measured in linear ("physical") units, does the resampling using these units, and then converts back to "perceptual" units. This is the most reasonable way of doing things if you believe that resampling should mimic what happens in the "real world".

Clearly, there is less gain in using a skewed ruler when you store images in floating point (say) because there are enough shades everywhere to please even the most discriminating eyes. But the units you use to store light (or other) measurements are, at least in principle, independent of how many bits you use to store them (even though in practice one choice influences the other: you wouldn't use nanometers to measure your child's height).

[jmac698]

The argument is a bit stronger than that, the original viral page I think is this one:
http://www.4p8.com/eric.brasseur/gamma.html

[madshi]

The argument is a bit stronger than that, the original viral page I think is this one:
http://www.4p8.com/eric.brasseur/gamma.html
Yeah, that page does a good job showing the benefits of linear light processing. But you have to be aware that most of the images used on that page include very high pixel-to-pixel contrast patterns (e.g. dithering patterns, or alternating lines etc), which you don't ever see in movie content. With typical movie content the biggest difference between gamma scaling and linear light scaling is that you get more halos when using a resampler with a negative lobe (e.g. Lanczos).

[SEt]

Real world photos definitely scale more correctly with linear light scaling. Difference is not everywhere and often not noticeable on first look, but also it doesn't suffer from severely wrong results from time to time as non-gamma-aware resize does.
On video it's the sharper and more detailed video - the more the difference.

[madshi]

The latest madVR version offers an option to do scaling in linear light. FWIW, so far the majority of users seem to prefer to leave the option off - and that's not due to performance issues.

[SEt]

Implementing linear light scaling is a bit tricky. With dumb reverse_gamma -> usual_scaling -> apply_gamma results often won't be nice.

[madshi]

So what do you suggest instead? Using a non-linear scaling algorithm?