signal processing Signal processing is an electrical engineering subfield that focuses on analyzing, modifying and synthesizing ''signals'', such as audio signal processing, sound, image processing, images, Scalar potential, potential fields, Seismic tomograph ...

, Lulu

smoothing In statistics and image processing, to smooth a data set is to create an approximating function that attempts to capture important patterns in the data, while leaving out noise or other fine-scale structures/rapid phenomena. In smoothing, the d ...

is a

nonlinear In mathematics and science, a nonlinear system (or a non-linear system) is a system in which the change of the output is not proportional to the change of the input. Nonlinear problems are of interest to engineers, biologists, physicists, mathe ...

mathematical technique for removing impulsive

noise Noise is sound, chiefly unwanted, unintentional, or harmful sound considered unpleasant, loud, or disruptive to mental or hearing faculties. From a physics standpoint, there is no distinction between noise and desired sound, as both are vibrat ...

from a data sequence such as a

time series In mathematics, a time series is a series of data points indexed (or listed or graphed) in time order. Most commonly, a time series is a sequence taken at successive equally spaced points in time. Thus it is a sequence of discrete-time data. ...

. It is a nonlinear equivalent to taking a

moving average In statistics, a moving average (rolling average or running average or moving mean or rolling mean) is a calculation to analyze data points by creating a series of averages of different selections of the full data set. Variations include: #Simpl ...

(or other smoothing technique) of a time series, and is similar to other nonlinear smoothing techniques, such as Tukey or median smoothing. LULU smoothers are compared in detail to median smoothers by Jankowitz and found to be superior in some aspects, particularly in mathematical properties like

idempotence Idempotence (, ) is the property of certain operations in mathematics and computer science whereby they can be applied multiple times without changing the result beyond the initial application. The concept of idempotence arises in a number of pl ...

Properties

Lulu operators have a number of attractive mathematical properties, among them

– meaning that repeated application of the operator yields the same result as a single application – and co-idempotence. An interpretation of idempotence is that: 'Idempotence means that there is no “noise” left in the smoothed data and co-idempotence means that there is no “signal” left in the residual.' When studying smoothers there are four properties that are useful to optimize: # Effectiveness # Consistency # Stability # Efficiency The operators can also be used to decompose a signal into various subcomponents similar to wavelet or Fourier decomposition.

History

Lulu smoothers were discovered by C. H. Rohwer and have been studied for the last 30 years. Their exact and asymptotic distributions have been derived.

Operation

Applying a Lulu smoother consists of repeated applications of the min and max operators over a given subinterval of the data. As with other smoothers, a width or interval must be specified. The Lulu smoothers are composed of repeated applications of the ''L'' (lower) and ''U'' (Upper) operators, which are defined as follows:

L operator

For an L operator of width ''n'' over an infinite sequence of ''x''s (..., ''x''_''j'', ''x''_''j''+1,...), the operation on ''x''_''j'' is calculated as follows: # Firstly we create (''n'' + 1) mini-sequences of length (''n'' + 1) each. Each of these mini-sequences contains the element ''x''_''j''. For example, for width 1, we create 2 mini-sequences of length 2 each. For width 1 these mini sequences are (''x''_''j''−1, ''x''_''j'') and (''x''_''j'', ''x''_''j''+1). For width 2, the mini-sequences are (''x''_''j''−2, ''x''_''j''−1, ''x''_''j''), (''x''_''j''−1, ''x''_''j'', ''x''_''j''+1) and (''x''_''j'', ''x''_''j''+1, ''x''_''j''+2). For width 2, we refer to these mini-sequences as seq₋₁, seq₀ and seq₊₁ # Then we take the minimum of each of the mini sequences. Again for width 2 this gives: (Min(seq₋₁), Min(seq₀), Min(seq₊₁)). This gives us (''n'' + 1) numbers for each point. # Lastly we take the maximum of (the minimums of the mini sequences), or Max(Min(seq₋₁), Min(seq₀), Min(seq₊₁)) and this becomes ''L''(''x''_''j'') Thus for width 2, the ''L'' operator is: : ''L''(''x''_''j'') = Max(Min(seq₋₁), Min(seq₀), Min(seq₊₁))

U Operator

This is identical to the L operator, except that the order of Min and Max is reversed, i.e. for width 2: : ''U''(''x''_''j'') = Min(Max(seq₋₁), Max(seq₀), Max(seq₊₁))

Examples

Examples of the ''U'' and ''L'' operators, as well as combined ''UL'' and ''LU'' operators on a sample data set are shown in the following figures. It can be seen that the results of the ''UL'' and ''LU'' operators can be different. The combined operators are very effective at removing impulsive noise, the only cases where the noise is not removed effectively is where we get multiple noise signals very close together, in which case the filter 'sees' the multiple noises as part of the signal.

References

{{Reflist, refs= {{cite journal , title=Idempotent one-sided approximation of median smoothers , author=Rohwer, CH , journal=Journal of Approximation Theory , volume=58 , number=2 , pages=151–163 , year=1989 , doi=10.1016/0021-9045(89)90017-8 , doi-access=free {{cite journal , title=Projections and separators , author=Rohwer, CH , journal=Quaestiones Mathematicae , volume=22 , number=2 , pages=219–230 , year=1999 , doi=10.1080/16073606.1999.9632077 {{cite book , title=Nonlinear smoothing and multiresolution analysis , author=Rohwer, Carl , volume=150 , year=2005 , publisher=Birkhauser Basel {{cite journal , title=Nonlinear (nonsuperposable) methods for smoothing data , author=Tukey, JW , journal=Cong. Rec. , pages=673 , year=1974 , publisher=EASCON {{cite journal , title=Exact and asymptotic distributions of LULU smoothers , author=Conradie, WJ and de Wet, T. and Jankowitz, M. , journal=Journal of Computational and Applied Mathematics , volume=186 , number=1 , pages=253–267 , year=2006 , doi=10.1016/j.cam.2005.03.073 , bibcode=2006JCoAM.186..253C , doi-access= {{cite thesis , title=Some statistical aspects of LULU smoothers , author=Jankowitz , type=PhD Thesis , year=2007 , publisher=University of Stellenbosch {{cite thesis , title=LULU operators on multidimensional arrays and applications , author=Fabris-Rotelli, Inger Nicolette , type=MSc Thesis , year=2009 , publisher=University of Pretoria Abstract algebra Theoretical computer science Binary operations Statistical signal processing