2
$\begingroup$

I am reading about edge detection and I read that 2nd order detectors are more susceptible to noise. Is there a mathematical proof to this ?

$\endgroup$
3
$\begingroup$

Suppose that the noise is a random vector $X$ with normal zero-mean components of variance $\sigma_i$, mutually independent, then for the linear combination (the $g_i$ being for instance coefficients of a FIR filter): $$ Y = \sum_i g_i X_i\,,$$ the variance of $Y$ will be: $$ V(Y) =\sum_i g_i^2 \sigma_i^2\,, $$ which boils down to $$\|g\|_2^2 \sigma_2^2\,$$ for a classical stationnary Gaussian noise.

Now start from $g^1=[1,-1]$, and assume you built higher order derivative by self-convolution, for instance $$g^2=g^1 \ast g^1 = [1 ,-2 ,1],$$ $$g^3 = g^1 \ast g^1 \ast g^1 =[1,-3,3,1] ,$$ etc.

You easily get that the coefficients of $g^n$ are $$g^n_k=(-1)^k \binom{n}{k}\,.$$

Hence $\|g^n\|_2^2 = \sum_k \binom{n}{k} ^2 = \binom{2n}{n}$ (a famous identity). For $n=1$, the amplification is $2$, for $n=2$ it will be $6$, and $20$ for the third derivative.

So the noise amplification roughly grows with the derivative order (based on Stirling's formula) as $$\frac{4^n}{\sqrt{\pi n}}\,.$$

So all in all, noise power tends to explode with derivatives.

This does not happen at order $0$, if you consider that traditional low-pass filters having positive coefficients have finite sum, often equal to $1$. Hence, for those $\|g\|_2 \le \|g\|_1=1$. For instance, if one takes standard smoothing "discrete Gaussian" filters of order $m$ with coefficients $$b^m_k=\frac{ \binom{m}{k}}{2^m}\,,$$ then their $\ell_2$ squared norm is: $$\frac{\binom{2m}{m}}{4^m}$$ and one sees that the $4^m$ term cancels in the asymptotics, and you get that, when $m$ grows: $$\|h^m\|_2^2 \approx\frac{1}{\sqrt{\pi m}}\,,$$ and thus tend to reduce the noise power.

Finally, this is not the whole story, since we have not talked about edges, which traditionally are wide-band, and especially hard to detect in high frequencies. A study in the Fourier domains may lead to others aspects, that exceed my time today, but is addressed in @Olli Niemitalo's answer.

$\endgroup$
  • $\begingroup$ @Olli Niemitalo I meant asymptotics on the $\infty$ side, as derivative order grow, based on Stirling's approximations. I should mention that $\endgroup$ – Laurent Duval Apr 27 '16 at 7:00
  • $\begingroup$ @Olli Niemitalo What a great question! I have added details, hoping I did not make mistakes. I never thought abot that before, I will reuse that in lectures :) $\endgroup$ – Laurent Duval Apr 27 '16 at 7:27
3
$\begingroup$

If you assume the Edge Detection is SNR driven operation, one could find a Mathematical justification for this.

First, the variance of Additive White Noise with Variance $ {\sigma}_{n}^{2} $ at the output of a Linear System given by $ g $ is $ {\sigma}_{n}^{2} {\left\| g \right\|}_{2}^{2} $.

Let's look on an Image filtered by a derivative approximating filter $ g = \left[ -1, 1 \right] $.
This increase the Noise Variance by a factor of 2.
For 2nd order the filter is $ {g}_{2} = g \ast g = \left[ 1, -2, 1 \right] $ hence the factor is 6 (It comes from the reason the second time we filter the noise is correlated).

Now, the question does the signal (Edge) is amplified by the same factor?
Moreover, on areas where there is no edge, the probability to detect noise as edge increases.
To see intuitively, just operate 1st order method on the gradient of the image and see how much False edges you have now.

$\endgroup$
  • $\begingroup$ Hi thanks for the reply. So if I were tweak your example by using the central differencing operator [ -1 0 1] and the 2nd order derivative [ 1 -2 1]. Then if I convolve with the central differencing operator I would get f'(x) = f(x+1) - f(x-1) + n(x+1) + n(x-1). Convolving with the 2nd order derivative yields f''(x) = n(x+1) + 2n(x) + n(x-1) + f(....) ? Is that why the noise variance goes up a factor of 4 ? n(x) is the noise present. $\endgroup$ – RuiQi Apr 26 '16 at 10:06
  • $\begingroup$ @Drazick I am very bad at answering today, yet, if the filter is $g$, for a independent normal random noise, I would have said that the factor would be $\|g\|^2_2$, hence $2$ and $6$ for $[1, 0, -1]$ and $[1 ,2 ,1]$. Where is my mistake? $\endgroup$ – Laurent Duval Apr 26 '16 at 14:08
  • $\begingroup$ Ah sorry yes I meant to write 6 for [1, 2, 1] since the center is 2 and hence the variance of 2n(x) would be 4. $\endgroup$ – RuiQi Apr 26 '16 at 15:05
  • $\begingroup$ @Olli Niemitalo Very good, diversity! $\endgroup$ – Laurent Duval Apr 27 '16 at 13:54
  • 1
    $\begingroup$ @LaurentDuval, I meant the factor is 2 for this filter. Your general answer is right of course. I did a mistake on the 2nd. Will fix. $\endgroup$ – Royi Apr 28 '16 at 8:11
2
$\begingroup$

Let's assume that the signal has a white (flat) power spectrum $|X(\omega)|^2$ of unity power $P_0$:

$$|X(\omega)|^2 = c$$ $$P_0 = \int_{-\pi}^\pi |X(\omega)|^2 d\omega = 1$$ $$\Rightarrow c = \frac{1}{2\pi}$$

The Fourier transform of the "differentiation" filter $g = \left[1, -1\right]$ is:

$$G(\omega) = 1-e^{i\omega}$$

The signal power after filtering $n$ times will be:

$$P_n = \int_{-\pi}^\pi |X(\omega)|^2|G(\omega)|^{2n} d\omega = \int_{-\pi}^\pi \frac{1}{2\pi}\left|1-e^{i\omega}\right|^{2n} d\omega$$ $$= 2^{2n + 1}\frac{\left(\frac{1}{2}(2n + 1)\right)!}{n!\sqrt{\pi}(2n + 1)}$$ $$\Rightarrow P_0 = 1, P_1 = 2, P_2 = 6, P_3 = 20, P_4 = 70\tag{1}$$

This is for a flat power spectrum all the way to the Nyquist frequency ($\pi$). We won't see those large gains if the signal is low-pass with a band-limit below the Nyquist frequency, for example at half the Nyquist frequency:

$$P_n = \int_{-\pi/2}^{\pi/2} \frac{1}{\pi}\left|1-e^{i\omega}\right|^{2n} d\omega$$ $$\Rightarrow P_0 = 1, P_1 \approx 0.73, P_2 \approx 0.91, P_3 \approx 1.33, P_4 \approx 2.09$$

For the higher orders of differentiation, if there was any white noise in the data, it would follow (1) and blow up in comparison to a signal that is low-pass with the lower band-limit, giving a hopelessly low signal-to-noise ratio. The situation will be similar for any signal that doesn't utilize the spectrum all the way up to the Nyquist frequency.

True edges are not low-pass, however, but have a -6 dB / octave decaying spectrum. After the first differentiation, a normalized edge signal $[\dots, 1, 1, 1, 1, 0, 0, 0, \dots]$.looks like an impulse: $[\dots, 0, 0, 0, 1, 0, 0, 0, \dots]$. Based on (1), the second filtering multiplies the noise power by a factor of 3 while the edge signal becomes $[\dots, 0, 0, 0, 1, -1, 0, 0, \dots]$, doubling its sum of squares power and not affecting its peak value. We can conclude that in the presence of white noise, compared to the first order edge detector the second order edge detector suffers from a $10 \log_{10}\left(\frac{3}{2}\right) \text{ dB} \approx 1.76 \text{ dB}$ worse sum of squares and $10 \log_{10}\left(3\right) \text{ dB} \approx 4.77 \text{ dB}$ worse peak to sum of squares signal-to-noise ratio.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.