14
$\begingroup$

In image processing, what does it mean when a filter is called non-linear?

Does it mean the equation of the filter contains derivatives and if it didn't, it would have been called linear?

$\endgroup$
23
$\begingroup$

A filter F is called "linear", iff for any scalars $c_1$, $c_2$ and any images $I_1$ and $I_2$:

$F\left(c_1\cdot I_1+c_2\cdot I_2\right)=c_1\cdot F\left(I_1\right)+c_2\cdot F\left(I_2\right)$

This includes:

  • Derivatives
  • Integrals
  • Fourier transform
  • Z-Transform
  • Geometric transformations (rotate, translate, scale, warp)
  • Convolution and Correlation
  • the composition of any tuple of linear filters (i.e. applying some linear filter to the output of another linear filter $F(G(I))$)
  • the sum of the result of any two linear filters (i.e. the output of one filter, added pixel by pixel to the output of another filter $F(I) + G(I)$)

and many others.

Examples of non-linear filters are:

  • the square, absolute, square root, exp or logarithm of the result of any linear filter
  • the product of the result of any two linear filters (i.e. the output of one filter, multiplied pixel by pixel with the output of another filter $F(I)\cdot G(I)$)
  • morphological filters
  • median filter
$\endgroup$
  • $\begingroup$ Good list. The concept of linear system theory also applies more generally to signals with other than two dimensions, and is a pretty fundamental topic in many areas of engineering. $\endgroup$ – Jason R Apr 24 '12 at 12:47
  • 1
    $\begingroup$ Good list, but I am a little concerned about the phrase "product of any two linear filters" being misinterpreted by beginners. The cascade of two linear filters (connect the output of the first to the input of the second) results in a linear filter, and since the transfer functions are multiplied, a newbie might well think that the filter whose transfer function is the product $H_1(z)H_2(z)$ or $H_1(f)H_2(f)$ of the transfer functions is what is meant by product of two linear filters, and this filter is nonlinear even though its two components are linear filters. $\endgroup$ – Dilip Sarwate Apr 24 '12 at 14:06
  • $\begingroup$ @DilipSarwate: Good point. I've added composition to the list and clarified what I meant by "product of two filters". $\endgroup$ – Niki Estner Apr 24 '12 at 14:55
  • $\begingroup$ @nikie Excellent list. You might also list Image Segmentation (since I see that it exists as a technique in its own right) as another non-linear method. (Equivalent to thresh-holding in the 1-D sense). $\endgroup$ – Spacey Apr 24 '12 at 15:32
  • $\begingroup$ @nikie I do not believe that translation is a linear operation. $\endgroup$ – Spacey May 16 '12 at 5:30
1
$\begingroup$

Let us say that you have two filters, one linear and one non linear (for filtering out some noise corrupted images). i.e you have some bad pixels with really high or low values that look sort of 'the odd one out' in a small rectangular region on an image.

Now, a linear filter (like 'average') works like this:

  1. Place a window over element
  2. Take an average — sum up elements and divide the sum by the number of elements.

You will notice that if you expand the area of the filter window you will stretch it over more elements (i.e more elements make up the average automatically contributing to the filtered pixel value).

On the other hand for a non-linear filter such as the median (which replaces the pixel to be filtered with the median value inside the square window), increasing the window does not necessarily bring a contribution to the median of the window and hence does not result in a direct impact on the filtered pixel.

Here is a numerical example : say you have a i,j (i.e. 3x3 window) with the anchor (center pixel in the middle at position (2,2) and the values are (brightness level) 40, 60, 80, 89, 90, 100, 101, 105, 185. you will notice that the median is 90 so the anchor pixel will become 90. now lets say you increase the window size and you add more values to those nine, namely to have a 5x5 window. There is a chance that even after that the median would still be 90. So a change in input does not necessarily give a proportional change in the output, hence the non-linearity.

$\endgroup$
  • $\begingroup$ -1. I would agree that Median is non-linear filter. However, your explanation is not acceptable. $\endgroup$ – Dipan Mehta May 4 '12 at 12:31
0
$\begingroup$

This reminds me: many years ago (15?), I read in a non-academic but quite kwnown magazine for developers (cof,cofdr,cof,cofdobbs...) an explanation about LPC=Linear Predictive Coding... It gave as an example the prediction of signal $x[t+1]$ based on the values of $x[t]$ and $x[t-1]$ and explained that for a typical (smooth) signal that could be done by drawing a straight line that passed through those two given values... and because of that the prediction was called 'linear'. I couldn't believe my eyes.

Of course, that 'linearity' has nothing to do with a filter being linear. Suppose that I want to predict the value of a signal using three previous values, and I decide to fit them via a second-degree polynomial, and extrapolate. The extrapolation then would fit a parabola, but my filter would still be a linear filter, because the extrapolated value is a linear combination of the input.

$\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.