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())

:D

[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 :D.

[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! :D

[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! :D

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 :D. 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 :D.

[neuron2]

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 ? :confused:

[neuron2]

@blivit

I have no idea what you are talking about, nor could I make any sense of your earlier posts. What distinction are you drawing? Something about the linearity, or what? Luminance is by definition "decoupled" from chrominance.

[blivit]

Originally posted by neuron2
@blivit

I have no idea what you are talking about, nor could I make any sense of your earlier posts. What distinction are you drawing? Something about the linearity, or what? Luminance is by definition "decoupled" from chrominance.

First, let me start with equations for calculating L and Y from RGB:

/* Luminance */
y = 0.299*r + 0.587*g + 0.114*b;

/* Lightness */
rgbmax = r;
if (g > rgbmax) rgbmax = g;
if (b > rgbmax) rgbmax = b;
rgbmin = r;
if (g < rgbmin) rgbmin = g;
if (b < rgbmin) rgbmin = b;
l = (rgbmax + rgbmin) * 0.5;

From Alan Robert's "Colour Equations FAQ", he says the following: "European TV (PAL and SECAM coded) uses Y'U'V' components. Y' is similar to perceived luminance, U' and V' carry the colour information and some luminance information".

Luminance weights R, G, and B, based on how bright humans perceive each color to be. Green is brighter than red, and blue is the darkest. This is why night vision scopes show things in green, we see the greatest amount of brightness variation in green. For greyscale TV, it makes sense to weight like this. But when you use luminance in image processing, you start running into some difficulties. As Alan Roberts said, U and V both carry some brightness information as well. This is why I say that brightness is not "completely decoupled" from chroma. Some of the brightness information is in the chroma. Let's take a simple test case example. Take the 3 primary colors, R, G, B, and the secondaries in between them, yellow, cyan, and magenta. Set them all at full value. Now take the luminance, divide by two, and see what they look like on the screen. I would like for them to all be at half value, but they aren't. If you use L, lightness, instead of Y, halfing the brightness does just what I'd want it to do, halves the visual brightness of the pixels on screen. L does not have any brightness information that has bled into the color component. It is all in L, and thus I say it is "completely decoupled".

For another example of how L and Y differ, look at chroma rainbow artifacts. In YUV space, there is no fluctuation in Y, all the Moire patterns show up in U and V. If you take the video and convert it into HLS, you'll see that hue and saturation both show the rainbow artifacts as you might expect. But if you look at L, it has them too. This is because U and V do have some component of the brightness in them, and thus changes to U and V will also be seen in the brightness.

Luminance is great for creating greyscale images from color, since it is similar to how we perceive the relative brightness of the colors. But if you want to adjust the brightness of color pixels, lightness is the only way to do it correctly. This is why fades done in HLS space look so much better than fades done with Y. This is also why fade detection works so much better in HLS space than YUV space, since the changes in L really are the changes in the brightness of the pixels, whereas the changes in Y aren't (since, again, some of the brightness is in the chroma).

Now that I've elaborated on all this, do my earlier posts make a little more sense? I was assuming some familiarity with the differences between L and Y. I can see how things wouldn't make much sense if you weren't familiar with how they differ :)

[mf]

Actually, grayscaling from lightness might be better, if your theory is true. Red surfaces usually become a dark grey in greyscale, and they "light up" when you put the chroma back. Somehow that "lighting up" shouldn't happen I think.

[blivit]

Originally posted by mf
Actually, grayscaling from lightness might be better, if your theory is true. Red surfaces usually become a dark grey in greyscale, and they "light up" when you put the chroma back. Somehow that "lighting up" shouldn't happen I think.

Reds are a darker grey than greens because of the relative weightings of the colors in the Y calculation. The human eye is less sensitive to red light than to green, so for red and green light sources of equal intensity (HLS is also called HSI, I for intensity), the red will appear to be darker than the green. Y tries to take this into account. I don't know how someone who can not see color would see green vs. red, but I don't think it is unreasonable to treat greyscale this way. If you were to look at objects in a dark room, where you can't really see much color, I think that Y would better capture how the objects appear to the human eye than L. Y is used in TV so that black and white TVs can simply show the Y channel and get good looking greyscale images.

The red "brightens up" when you add the chroma in because the chroma contains part of the true brighness information. If you used L for greyscale, reds and greens of equal intensities would have equal L values. I think I actually prefer the "look" of Y greyscale to L greyscale. And all image processing programs I have ever seen or used do greyscale with the Y weightings, not with L values. I think that Y is probably more visually pleasing than L for greyscale.

[neuron2]

Now that I've elaborated on all this, do my earlier posts make a little more sense? I was assuming some familiarity with the differences between L and Y. I can see how things wouldn't make much sense if you weren't familiar with how they differ. I am well familiar with the differences between the spaces and their definitions. I just disagree with all of your conclusions and interpretations. But since I do not have time to argue it, I will withdraw from this discussion.

[High Speed Dubb]

blivit,

The “detect the cycle” idea is a good description of the way Guava Comb works. Like Kurosu said, the (temporal) wavelength is 8 fields for PAL, 4 for NTSC. There's also a spatial wavelength of 4 scanlines (PAL), and 2 for NTSC.

mf,

Yeah, using luma edge detection to increase the sensitivity of the filter would be a good idea. Guava doesn’t do that.

[neuron2]

Taking mf's idea a bit further. You can see that the artifacts are strong on edges close to 45 degree diagonals and absent on edges near horizontal or vertical. So perhaps the discrimination could be improved by making the edge detector maximally sensitive to such edges and insensitive to the other edges.

[High Speed Dubb]

You can see that the artifacts are strong on edges close to 45 degree diagonals and absent on edges near horizontal or vertical

That depends on the way the luma and chroma were separated. For simpler separation techniques (from a notch filter, such as on the Bt8x8 cards), the artifacts are strongest near vertical edges. With medium quality separation (a two line comb filter), horizontal and diagonal edges should show the most artifacts. With higher quality separation (a three line comb filter), just diagonal boundaries, thin horizontal lines, and high detail areas would tend to have artifacts.

[neuron2]

Good point. How silly of me.

[High Speed Dubb]

;) Well, unless you’ve recently been reading up on color separation algorithms, it’s a pretty obscure bit of trivia.

[neuron2]

Well I have been. :(

Maybe you know this. I was looking at the Sony Wega 32" at Best Buy and it had horrible dot crawl compared to other brands. They were all showing the same picture so I could compare on the same material.

The Wega is supposed to have a fancy comb filter. Why then is it so manifestly poor?

Finally, why do the dots crawl? Don't just tell me that things change with the frame rate, because I don't see why.

Thank you.

[High Speed Dubb]

A friend of mine has a 32" Wega. It has a reasonably good three line comb filter. (It's comparable with the comb filter in my Philips SAA 7whatnot card.) But you may have been looking at a different TV.

Also, you do have to be careful when comparing comb filters, since each kind has its own unique artifacts. If you choose just the wrong picture to compare, even a very high quality comb filter can look worse than no comb filter at all. But the vast majority of the time, the comb filter (even a poor one) will improve things. (In particular -- Horizontal lines in computer graphics look awful with 3 line comb filters. And only a 3D comb filter can help in areas with a lot of fine detail. But most of the time a comb filter will both cut down on artifacts and substantially improve the horizontal resolution.)

Another possible problem with Sonys (and some other tubes) is that they're pretty sharp. That can make any mistakes in the picture stand out more.

Finally, why do the dots crawl?
It's an optical illusion -- They don't really crawl.

The crosstalk produces a checkerboard pattern. Every frame, the phase of the color carrier signal is reversed. On "odd" frames, the black squares of the checkerboard are darkened, while on "even" frames, the red squares of the checkerboard are darkened. The alternation of the checkboard is usually perceived as motion, but it's really just flipping back and forth.

[neuron2]

All is clear now. Thank you taking the time to educate us on this interesting subject.

Now I'm curious about how adding lines with color information of opposite phase amounts to a filter with a series of evenly spaced notches in the frequency domain. :) Naively, I might have thought to implement a comb filter by making a series of notch filters at appropriate frequencies.