Thank you Aurélien, that is a great answer.
I think I will try to incorporate this in the weight computation of non
local means to use only "non noisy" pixels in the computations of the
weights, in addition to trying to use this as a (parametric?) mask.
rawfiner
Le samedi 21 juillet 2018, Aurélien Pierre a
écrit :
> The TV is the norm (L1, L2, or something else) of the gradient along the
> dimensions. Here, we have TV = || du/dx ; du/dy||. The discretized gradient
> of a function u along a direction x is a simple forward or backward finite
> difference such as du/dx = [u(i) - u(i-1)] / [x(i) - x(i-1)] (backward) or
> du/dx = [u(i +1) - u(i)] / [x(i+1) - x(i)] (forward).
>
> For contiguous pixels on main directions, the distance between 2 pixels is
> x(i) - x(i-1) = 1 (I don't divide explicitely by 1 in the code though), on
> diagonals it's = sqrt(2) (result of Pythagore's theorem). Hence the
> division by sqrt(2).
>
> Now, imagine a 2D problem where we have an inconsistent pixel in a smooth
> sub-area of a picture with 0 all around:
>
> [0 ; 0 ; 0]
> [0 ; 1 ; 0]
> [0 ; 0 ; 0]
>
> That is the matrix of a 2D Dirac delta function (impulse). Computing the
> TV L1 in forward difference leads to :
>
> ([0.0 ; 0.5 ; 0.0]
> [0.5 ; 1.0 ; 0.0]
> [0.0 ; 0.0 ; 0.0])*2
>
> Doing the same backwards leads to :
>
> ([0.0 ; 0.0 ; 0.0]
> [0.0 ; 1.0 ; 0.5]
> [0.0 ; 0.5 ; 0.0])*2
>
> So what happens is in both cases, the immediate neighbours of the noisy
> pixel are detected as somewhat noisy as well because of the first order
> discretization, but they are not noise. That's a limit of the discrete
> computation. Also the derivative of a Dirac delta function is supposed to
> be an even function, obviously that property is broken here. If you compute
> the L2 norm of these arrays, you get 1.22. A delta function should have a
> L2 norm = 1. Actually, the best approximation of the TV of the delta
> function would be the original delta function itself.
>
> If we average the both TV norms, we get :
>
> ([0.00 ; 0.25 ; 0.00]
> [0.25 ; 1.00 ; 0.25]
> [0.00 ; 0.25 ; 0.00])*4
>
> So, now, we have an error on more neighbours, but smaller in magnitude and
> the TV map is now even. Also, the L2 norm of the array is now 1.12, which
> is closer to 1. So we have a better approximation of the delta derivative.
>
> With that in mind, on the 8 neighbours variant, we also compute the TV L1
> norms (average of backward and forward) on diagonals, meaning :
>
> ([0.25 ; 0.00 ; 0.25]
> [0.00 ; 1.00 ; 0.00]
> [0.25 ; 0.00 ; 0.25])*4/sqrt(2)
>
> And… you are right, there is a problem of normalization because we should
> divide by 4*(1 + 1/sqrt(2)) instead of 4. Then, our TV L1 map will be :
>
> [0.1036 ; 0.1464 ; 0.1036]
> [0.1464 ; 1. ; 0.1464]
> [0.1036 ; 0.1464 ; 0.1036]
>
> That's an even better approximation to the Dirac delta. Now, the L2 norm
> is 1.06. And now that I see it, that could lead to a separable kernel to
> compute the TV L1 with two 1D convolutions…
>
> I didn't plan on going full math here, but, here we are…
>
> I will correct my code soon.
>
> 16/07/2018 à 01:51, rawfiner a écrit :
>
> I went through Aurélien's study again
> I wonder why the result of TV is divided by 4 (in case of 8 neighbors, "
> out[i, j, k] /= 4.")
>
> I guess it is kind of a normalisation.
> But as we divided the differences along diagonals by sqrt(2), the maximum
> achievable (supposing the values of the image are in [0,1], thus taking a
> difference of 1 along each direction) are:
> sqrt(1 + 1) + sqrt(1 + 1) + sqrt(1/2+1/2) + sqrt(1/2+1/2) = 2*sqrt(2) + 2
> in case of L2 norm
> 2 + 2 + 2*1/sqrt(2) + 2*1/sqrt(2) = 4 + 2*sqrt(2) in case of L1 norm
>
> So why this 4 and not a 4.83 and a 6.83 for L2 norm and L1 norm
> respectively?
> Or is it just a division by the number of directions? (if so, why are the
> diagonals difference divided by sqrt(2)?)
>
> Thanks!
>
> rawfiner
>
>
> 2018-07-02 21:34 GMT+02:00 rawfiner :
>
> Thank you for all these explanations!
> Seems promising to me.
>
> Cheers,
>
> rawfiner
>
> 2018-07-01 21:26 GMT+02:00 Aurélien Pierre :
>
> You're welcome ;-)
>
> That's true : the multiplication is equivalent to an "AND" operation, the
> resulting mask has non-zero values where both TV AND Laplacian masks has
> non-zero values, which - from my tests - is where the real noise is.
>
> That is because TV alone is too sensitive : when the image is noisy, it
> works fine, but whenever the image is clean or barely noisy, it detect
> edges as well, thus false-positive in the case of noise detection.
>
> The TV × Laplacian is a safety jacket that allows the TV to work as
> expected on noisy images (see the example) but will protect sharp edges on
> clean images (on the example, the masks barely grabs a few pixels in the
> in-focus area).
>
> I have found that the only way we could overcome the oversensibility of
> the TV alone is by setting a window (like a band-pass filter) instead of a
> threshold (high-pass filter) because,
