new idea for detecting cycling rainbow pixels

[blivit]

After reading over the threads about rainbow detection and repair, it looked to me like there was still a problem with correctly detecting which pixels should be repaired in the first place, which was resulting in ghosting effects because pixels were being "repaired" that should not have been. I've been thinking about how to detect rainbow pixels while excluding non-rainbow pixels, and I think I've come up with a good idea for it.

In the rainbow effects I've seen, the rainbow moire-like pattern moves in one direction along an edge at a constant rate. This must mean that each pixel involved in the rainbow artifact must be cyling through the rainbow of colors at a constant rate. So if we detect which pixels are cycling through the rainbow at a constant (or nearly constant) rate over 3 or more frames, then we can tell which pixels are involved in the rainbow artifact. We'll of course ignore pixels that don't have a nearly constant luma over the same temporal window, since those pixels are obviously moving and shouldn't be messed with.

Detecting rainbow cycling seems a little awkward to me in UV space. But if you convert into circular Hue space, it is quite easy. I've got equations for the conversion, and I've messed a good deal with HLS space. The UV rainbow artifacts do bleed a little into the Luminance and Saturation channels of HLS, but most of the artifact winds up in the Hue channel, as you would expect. I've written two different Hue edge detection routines (edge detection in circular space is a bit... odd...), and they work pretty well. Perhaps hue edge detection, along with brightness or luminance edge detection, could be used to further prune away pixels that shouldn't be processed. But I digress, back to detecting color cycling.

Take the target pixel. Either look two frames behind, two frames forward, or one frame to either side in time. Perhaps take whichever window has the smallest change in luma. A 3 frame window will give you two delta hues. A larger window would be even better, but then you risk missing more rainbow pixels. If these deltas are the same, with the same magnitude AND sign, within some fudge factor, and larger than some minimum arc length that you specify, then you can classify them as cycling. I haven't implemented it, but it seems to me like this idea is on the right track. I think a minimum cycle distance is necessary, rather than a target cycle distance, because the amount that a given pixel changes is going to depend on the resolution that the video has been shrunk down to from the original source. It could probably depend on other factors too. We're not going to know ahead of time how large an arc step the color cycling is going to be in any given video until we start trying to apply the de-rainbow filter to it. So if you specify a minimum, and perhaps a maximum arc length, then you have a somewhat safe range of allowable cycle distances that can hopefully work on any video source.

How does this approach sound?

-Eric

[Kurosu]

If you know some C, you could check AntiBlink2's (really basic) source who is based on this exact principle:
U0 is the value of the chroma for a pixel in frame 0
U1 for frame 1
U2 for frame 2
It checks if abs(U0-U1) and abs(U2-U1) are higher than a threshold, then discards those for which luma variation may indicate motion. It then do the average on 2/4 frames (both are possible, if you do better check)

The rainbow effect is indeed more present on bright parts (as subtitles, light reflections), but also affects darker parts, because the rainbows are somewhat related to the luminance variation (too late for me to post the links from doom9 about this - a problem of Y and UV analog signals aliasing).

You're right about the fact that more variation values would give better candidate (either 2 from AntiBlink2 or a map accumulating evidences for Guava Comb). Unfortunately, you need very static parts to do a good filtering. But that also happens in parts in motion, and that can't be filtered by calculating the temporal average, as it's moving. At some point, the idea of tackling the problem at the source led to the idea of filtering in the Fourier domain (filtering the luma carrier frequency from the UV spectre). But that is very computational, without evidence of good results, and... too much time needed

[blivit]

Antiblink doesn't sound like *quite* the same principle, but then again, I haven't read about it as much as I should have. From your description, it sounds like it just checks for large amounts of chroma motion over time. Taking the abs(delta U) and thresholding it just tags pixels that have large amounts of chroma motion. So it tags pixels that could be part of regular scene motion, not necessarily rainbow artifacts, and thus the ghosting issues happen. By working in hue space, you can add the extra constraints that they A) change by roughly the same amount along the hue circle each frame, and B) they change in the same direction in each frame. The cycling is only going one direction around the hue circle, or at least it looks that way to me. Requiring the change to be both roughly equal and the same direction should discard a very large number of pixels that are part of regular chroma motion. It would hopefully get rid of many of the chroma ghosting problems, since it would hopefully only detect the true rainbow pixels and not pixels involved in large amounts of regular motion.

Of course, all this is based on the assumption that the artifacts in U/V space really do move at a constant rate around the hue circle.... Even if they don't move at a constant rate, they hopefully do only move in one direction. Either constraint would be helpful. I'll try to find some time to code up some tests to see if any of this is really true. But it won't be for a few weeks, probably. Too busy with other stuff I just thought I'd throw the idea out in the mean time and see if anyone could run with it.

[mf]

Seems last night was pretty productive, I came up with 3 ideas while trying to fall asleep.
Here's one of them:
If chroma rainbows are caused by luma/chroma interleaving (for NTSC to be backwards-compatible with greyscale TVs), then chroma rainbows are directly caused by interference of the luma channel. This would mean that you can use luma info in finding out where chroma rainbows appear. So my idea is to take the luma blur mask that smart smoothers would use, invert it, and use it on the chroma plane (which means that areas where high detail is in luma will be blurred in chroma), to perform a temporal and spatial smooth. Because of the nature of the detail mask (effictiveness of which proven by smart smoothers), in theory, all detail would be retained.


What do you think ?

[Kurosu]

Alas, the aliasing doesn't happen in the spatial domain, but in the frequency domain. Luma information gets mixed with chroma information before being converted to spatial data. High frequencies of the luma signal can't be distinguished from chroma signal frequencies.

In fact, detecting rainbow isn't the bigger problem. It's rather having as little as possible false candidates, and besides, have sufficient stability to do the temporal smoothing. This is the last point that discouraged me from continuing, as it means only stationnary scenes can be cleaned correctly.

Edges produce rainbow artifact, but I believe it's in such a way it would be hard to directly use it. I'm not an expert anyway, and if it leads to a succesfull algorithm, I would love it.

@blivit
Aside from the above problem, something seems problematic to me:

If these deltas are the same, with the same magnitude AND sign, within some fudge factor

It also does this in YUV colorspace, but the magnitude isn't constant (can vary by as much as 30%), even for stationnary scenes. So I wonder if it will work better in HSL than in YUV colorspace.

[mf]

Look at the images on the following page:

http://www.doki.ca/filters/

Where does the rainbowing appear ? In high detail levels. I think a proper detail mask can easily fix this.

[Kurosu]

What I meant: for sure, the rainbows will always be located near edges, but not all edges have rainbows near them. What you actually want to do is not to filter chroma around every edge, but chroma near egdes that looks like rainbow.

The first 'generation' of AntiBlink (even more poorly written than the 2nd) first tried to build a edge mask, but this was too simple a proof of rainbows for the strength of the temporal averaging used. But for those kind of source, temporal averaging (smoothing is too preservative) is the best bet at eliminating the rainbows. AFAIK, that's also what does GuavaComb. Unfortunately it produces ghosting, if the motion pruning isn't effective enough.

Spatial smoothing is also effective, but not as much (see how strong it has to be to bring any result). It can be however seen as a possible post-processing (as did AntiBlink first generation).

[mf]

So far, throwing away all dignity, this has worked fine:

Convolution3D(1, 0, 255, 0, 20, 50, 0)
deen("a3d",1,0,10)
MergeChroma(MSmooth())

[Kurosu]

*speechless for a minute*

well, maybe the chroma-only smoothing on pixels found as having rainbow could be a solution, after all... Like a 5x5/7x7 kernel or so. But still not by only using edge mask.

[EDIT]
grammar error and first comment not meant to be harmful in any way.

[blivit]

Originally posted by Kurosu
@blivit
Aside from the above problem, something seems problematic to me:

It also does this in YUV colorspace, but the magnitude isn't constant (can vary by as much as 30%), even for stationnary scenes. So I wonder if it will work better in HSL than in YUV colorspace.

I still don't know exactly how the rainbows behave, but here was my line of thought. If rainbows really do move around the rainbow like I hope they do, then they must be bouncing back and forth in UV space in order to traverse the entire color spectrum. I'm picturing the U level maxing out, then V starting to rise while U falls, or some similar situation. Once either U or V maxes out or hits bottom, and the artifacts start to cycle in the other chroma channel, you've got a discontinuity in your deltas. Once a rainbow has reached the end of a linear chroma spectrum and jumps back to the beginning, that's another big jump in the U and V spaces to get back to the other end of their color range. The advantage of hue is that it is circular. Everything just moves around the circle and you don't have to worry about the start and end of the color space and how to factor in wrapping back around to the beginning. It will also roll both U and V changes into a single channel, at least the color changes themselves (not the brightness and saturation parts of the artifacts). So maybe using hue will lead to more even deltas. Only one way to find out....

[sh0dan]

Just as a side note: You can use UToY() and VToY() to easier see the chroma values.

[Kurosu]

@Blivit

for NTSC, iU/V variation are close to: value+offset then value-offset (ie 2 frames periodicity, except for the 30% error sometimes). Lindsey Dubb has diagnosed it should be 4 for PAL (some phase stuff when going from YIQ to YUV maybe?), but I haven't checked what actually happens (I suspect somthing close to a sine variation).

Not directly related, but I remember having tried (in a foolish attempt to bypass Fourier analysis) to link 'offset' to the edge value, and haven't succeeded in bringing something working. I haven't searched if the colorspace was the cause, or if some tweaking could have lead to more efficient fix.

Is there any program using HSL (not a request for transformation functions, though)

@Sh0dan
Nice! I was still using a plugin called see by marcFD

[mf]

Originally posted by Kurosu
*speechless for a minute*

Like I said, throwing away all dignity .

[blivit]

Originally posted by Kurosu
@Blivit

Is there any program using HSL (not a request for transformation functions, though)

I don't know of any filters that use any channel from HLS space (I don't know why it isn't usually refered to as HSL, when there is a related HSV space). If you are wondering if HLS space has any use at all, I can say from my experiments with fade detection that L works much better than Y for detecting fades. Luma is related to brightness, but isn't quite there. The lightness value in HSL space is a better measure of brightness than luma. All my algorithms for fade detection work with luma, but they work much better with lightness. Something visually half as bright as it was before will have a lightness value half of what it was before, which isn't true for luma.

I've also started looking up articles on denoising, and in recent years, several groups have reported better results using non-linear color spaces (HSV, HLS, CB) than traditional RGB or YUV. Their argument is that these spaces better model the human perception of color, and thus work better, and that the only reason they haven't been explored much until now is that people don't like to work in circular or spherical space for image analysis, since the math gets uglier.

Some interesting papers can be found here:

http://www.math.ucla.edu/~imagers/htmls/rec.html

[mf]

Originally posted by blivit
I don't know of any filters that use any channel from HLS space (I don't know why it isn't usually refered to as HSL, when there is a related HSV space). If you are wondering if HLS space has any use at all, I can say from my experiments with fade detection that L works much better than Y for detecting fades. Luma is related to brightness, but isn't quite there. The lightness value in HSL space is a better measure of brightness than luma. All my algorithms for fade detection work with luma, but they work much better with lightness. Something visually half as bright as it was before will have a lightness value half of what it was before, which isn't true for luma.

Hm, it's not GRB either, right ? Somehow it's just HSL (or HSI, some people refer to Lightness as Intensity, which makes sense in a way). Maybe it's ordered in the way the channels are ordered when you transfer data in HSL, same as with RGB and BGR, where BGR means that Blue is on the other side of a pixel in an LCD screen . Anyway, I don't really get why HSL is used very much either. I love to use it when retouching and creating images, there's nothing like increasing the saturation of a photo a bit . And I've noticed that lightness fades (fading from full to black, keeping saturation intact) look extremely leet. If you don't get what I mean then look at the intro "movie" of Dune II (that old game we all loved to play in the DOS days).
Let's advertise usage of HSL!

[blivit]

Originally posted by mf
Maybe it's ordered in the way the channels are ordered when you transfer data in HSL, same as with RGB and BGR, where BGR means that Blue is on the other side of a pixel in an LCD screen .

I seem to remember having an old graphics card that used BGR in hi-color mode (forget if it was 15 or 16 bit). I still use an old DOS program called DISPLAY for many of my image processing and conversion needs (it can even read Amiga HAM!). Way back before there was a VESA driver for it, you had to code your own display drivers for new unsupported chipsets in assembly, based off of other asm code that came with the program. Which is why I seem to remember dealing with swapped RGB/BGR

And I've noticed that lightness fades (fading from full to black, keeping saturation intact) look extremely leet. If you don't get what I mean then look at the intro "movie" of Dune II (that old game we all loved to play in the DOS days).
Let's advertise usage of HSL!

HSL is definately the way to go when dealing with any sort of fade. It is GREAT to have "brightness" totally decoupled from color and saturation. I'd think that an HSL levels filter would be pretty useful, so that you could pump up the saturation, tweak the brightness, and adjust the tint if need be. Maybe I just haven't looked hard enough for one. It would be just like the knobs on older color TV sets. What you say? TVs used to have knobs and dials?

Speaking of older technology, the MCV was definately the most powerful vehicle you could deploy in Dune II. Turreting towards an enemy is a tried and true strategy. You should try the Super Dune II fan hack if you haven't played it. It gives you three new scenarios, with the Fremen, Saurdakar, and Mercenaries. I appologize for getting off topic, but such nostalgia is just too good to pass up.

[mf]

Originally posted by blivit
Speaking of older technology, the MCV was definately the most powerful vehicle you could deploy in Dune II. Turreting towards an enemy is a tried and true strategy. You should try the Super Dune II fan hack if you haven't played it. It gives you three new scenarios, with the Fremen, Saurdakar, and Mercenaries. I appologize for getting off topic, but such nostalgia is just too good to pass up.

Yah, I love MCVs . And I did play SuperDune II I think, at least I have it on HD here, or wait, I think it didn't run. Anyway, it never hurts to go a bit offtopic, especially not with nostalgia. Aaah, the days of Wolf3D and Indy & the Fate of Atlantis .

[Guest]

Originally posted by blivit
I'd think that an HSL levels filter would be pretty useful, so that you could pump up the saturation, tweak the brightness, and adjust the tint if need be. Maybe I just haven't looked hard enough for one. It would be just like the knobs on older color TV sets. What you say? TVs used to have knobs and dials?

I already wrote that filter. It is called Tweak().

[blivit]

Originally posted by neuron2
I already wrote that filter. It is called Tweak().

I guess I didn't look hard enough then

I do have some questions about your algorithm, though. Looking over the code, it looks like instead of using true lightness, you use the Y luminance instead? So instead of hue/saturation/lightness, you're using hue/saturation/luminance? Unless I've misinterpreted your algorithm (which is quite possible), wouldn't this defeat one of the main purposes of working in HLS space to begin with, which is to completely decouple brightness from color (which luminance does not do) and get correct brightness adjustments?

[mf]

Originally posted by blivit
I guess I didn't look hard enough then

I do have some questions about your algorithm, though. Looking over the code, it looks like instead of using true lightness, you use the Y luminance instead? So instead of hue/saturation/lightness, you're using hue/saturation/luminance? Unless I've misinterpreted your algorithm (which is quite possible), wouldn't this defeat one of the main purposes of working in HLS space to begin with, which is to completely decouple brightness from color (which luminance does not do) and get correct brightness adjustments?

Well actually, when seperated, I think that brightness and lightness are 1:1. The only thing you're doing is changing the color channels into hue and saturation, so that you can leave those intact while doing lightness adjustments. Wait a minute, that should be possible in YUV too, then. Am I only confusing myself or am I simply not making sense ?