Median filter. Fast median filtering algorithm

Median filtering is a nonlinear signal processing method developed by Tukey. This method is useful in reducing noise in an image. One-dimensional median filter is a sliding window covering an odd number of image elements. The center element is replaced by the median of all elements in the window. Median of a discrete sequence for odd N is that element for which there are elements smaller or equal to it in magnitude, and elements greater or equal to it in magnitude.

Let the window contain image elements with levels 80, 90, 200, 110 and 120; in this case, the center element should be replaced with the value 110, which is the median of the ordered sequence 80, 90, 110, 200. If in this example the value 200 is a noise outlier in a monotonically increasing sequence, then median filtering will provide a significant improvement. On the contrary, if the value 200 corresponds to the useful signal pulse (when using wideband sensors), then the processing will lead to a loss of clarity in the reproduced image. Thus, the median filter in some cases provides noise suppression, in others it causes unwanted signal suppression.

Let's consider the impact of the median and averaging (smoothing) filters with a five-element window on the step, sawtooth, pulse and triangle discrete signals(Fig. 4.23). From these diagrams, it is clear that the median filter does not affect step or sawtooth functions, which is usually a desirable property. However, this filter suppresses pulsed signals whose duration is

is less than half the width of the window. The filter also causes the vertex of the triangular function to flatten.

The ability to analyze the effect of the median filter is limited. It can be shown that the median of the product of a constant and a sequence is equal to:

Besides,

However, the median of the sum of two arbitrary sequences is not equal to the sum of their medians:

This inequality can be verified using the sequences 80, 90, 100, 110, 120 and 80, 90, 100, 90, 80 as an example.

Various strategies are possible for applying the median filter to suppress noise. One of them recommends starting with a median filter, the window of which covers three elements of the image. If the signal attenuation is insignificant, the filter window is expanded to five elements. This continues until median filtering begins to do more harm than good.

Another possibility is to perform cascaded median filtering of the signal using a fixed or variable window width. In general

Typically, those areas that remain unchanged after a single filter treatment do not change after repeated treatment. Regions where the duration of the pulse signals is less than half the window width will be subject to changes after each processing cycle.

The concept of a median filter can easily be generalized to two dimensions by using a two-dimensional window of the desired shape, such as rectangular or close to circular. Obviously, a two-dimensional median filter with a window of size provides more effective noise reduction than successively applied horizontal and vertical one-dimensional median filters with a window of size. 2D processing, however, results in more significant signal attenuation.

The median filter implements a nonlinear noise reduction procedure. The median filter is a window W sliding across the image field, covering an odd number of samples. The central reference is replaced by the median of all image elements included in the window. The median of a discrete sequence x1, x2, ..., xL for odd L is an element for which there are (L ? 1)/2 elements smaller or equal to it in value, and (L ? 1)/2 elements larger or equal in size. In other words, the median is the average member of the series resulting from ordering the original sequence.

For example, med(20, 10, 3, 7, 7) = 7.

We define a two-dimensional median filter with a window W as follows:

The median filter is used to suppress additive and impulse noise in the image. Characteristic feature The median filter is to preserve brightness differences (contours). The median filter is especially effective in the case of impulse noise. Shown is the effect of the smoothing and median filters with a three-element window on the brightness gradient noisy with additive noise for a one-dimensional signal.

As for impulse noise, a median filter with a 3 x 3 window completely suppresses single outliers on a uniform background, as well as groups of two, three and four impulse outliers. In general, to suppress a group of impulse noise, the window size must be at least twice as large more sizes interference groups.

Among median filters with a 3x3 window, the following are the most common:

The coordinates of the presented masks indicate how many times the corresponding pixel is included in the ordered sequence described above.

One of the effective ways to eliminate impulse noise in an image is to use a median filter.

For each pixel in some of its surroundings (window), the median value is searched and assigned to this pixel. Defining a median value: If an array of pixels is sorted by their value, the median will be the middle element of that array. The window size must therefore be odd for this middle element to exist.

The median can also be determined by the formula:

where W is the set of pixels among which the median is sought, and fi is the brightness values ​​of these pixels.

For color images, a vector median filter (VMF) is used:

where Fi are the pixel values ​​in 3D color space and d is an arbitrary metric (e.g. Euclidean).

However, in its pure form, the median filter blurs small details, the size of which is less than the size of the window for searching for the median, and therefore is practically not used in practice.

Digital signals processing

Topic 16. Median filters

Who is unaware of the ever-present discrepancy between what a person seeks and what he finds?

Nicollo Machiavelli. Italian politician, historian. 1469-1527

When dealing with orientation towards the middle, be doubly careful. Socialism also laid claim to an average paradise for everyone, but what it ended up with was a wretched barracks.

Ernst Trubov. Ural geophysicist. XX century

Introduction.

1. Median filtering of one-dimensional signals. Filtration principle. One-dimensional filters. Suppression of statistical noise. Pulse and point noise. Difference plus noise. Covariance functions. Conversion of noise statistics. Frequency properties of the filter. Types of median filters. Advantages of median filters. Disadvantages of median filters.

2. Median filtering of images. Noise in images. Two-dimensional filters. Adaptive two-dimensional filters. Filters based on ranking statistics.

Introduction

Median filters are often used in practice as a means of preprocessing digital data. A specific feature of filters is a clearly expressed selectivity in relation to array elements, which are a non-monotonic component of the sequence of numbers within the window (aperture) of the filter, and stand out sharply against the background of neighboring samples. At the same time, the median filter does not affect the monotonic component of the sequence, leaving it unchanged. Thanks to this feature, median filters with an optimally selected aperture can, for example, preserve sharp object boundaries without distortion, effectively suppressing uncorrelated or weakly correlated noise and small-sized details. This property allows you to use median filtering to eliminate anomalous values ​​in data arrays, reduce outliers and impulse noise. A characteristic feature of the median filter is its nonlinearity. In many cases, the use of a median filter is more effective than linear filters, since linear processing procedures are optimal when the noise distribution is uniform or Gaussian, which in real signals this may not be the case. In cases where the differences in signal values ​​are large compared to the dispersion of additive white noise, the median filter gives a lower mean square error compared to optimal linear filters. The median filter is especially effective when cleaning signals from impulse noise when processing images, acoustic signals, transmitting code signals, etc. However, detailed studies of the properties of median filters as a means of filtering signals of various types are quite rare.

16.1. Median filtering of one-dimensional signals.

Filtration principle. Medians have long been used and studied in statistics as an alternative to arithmetic means of samples in estimating sample means. The median of a number sequence x 1, x 2, ..., x n for odd n is the average member of the series resulting from ordering this sequence in ascending (or descending) order. For even n, the median is usually defined as the arithmetic mean of the two middle samples of the ordered sequence.

The median filter is a window filter that sequentially moves through the signal array, and at each step returns one of the elements that fell into the window (aperture) of the filter. The output signal y k of a sliding median filter with a width of 2n+1 for the current sample k is generated from the input time series ..., x k -1 , x k , x k +1 , ... in accordance with the formula:

y k = med(x k - n , x k - n +1 ,…, x k -1 , x k , x k +1 ,…, x k + n -1 , x k + n), (16.1.1)

where med(x 1, …, x m, …, x 2n+1) = x n+1, x m are elements of the variation series, i.e. ranked in ascending order of x m values: x 1 = min(x 1 , x 2 ,…, x 2n+1) ≤ x (2) ≤ x (3) ≤ … ≤ x 2n+1 = max(x 1 , x 2 ,…, x 2n+1).

Thus, median filtering replaces the sample values ​​at the center of the aperture with the median value of the original samples inside the filter aperture. In practice, to simplify data processing algorithms, the filter aperture is usually set with an odd number of samples, which will be accepted in further consideration without additional explanation.

One-dimensional filters. Median filtering is implemented as a procedure for local processing of samples in a sliding window, which includes a certain number of signal samples. For each window position, the samples selected in it are ranked in ascending or descending order of values. The average report in the ranked list is called the median of the group of reports under consideration. This sample replaces the central sample in the window for the signal being processed. Because of this, the median filter is one of the non- linear filters, which replaces anomalous points and outliers with a median value, regardless of their amplitude values, and is stable by definition, capable of canceling even infinitely large samples.

The median filtering algorithm has a pronounced selectivity to array elements with a non-monotonic component of the sequence of numbers within the aperture and most effectively excludes from the signals single outliers, negative and positive, that fall on the edges of the ranked list. Taking into account the ranking in the list, median filters suppress noise and interference well, the length of which is less than half the window. A stable point is a sequence (in the one-dimensional case) or an array (in the two-dimensional case) that does not change during median filtering. In the one-dimensional case, the stable points of median filters are “locally monotonic” sequences, which the median filter leaves unchanged. The exception is some periodic binary sequences.

Thanks to this feature, median filters with an optimally selected aperture can preserve sharp object boundaries without distortion, suppressing uncorrelated and weakly correlated noise and small-sized details. Under similar conditions, algorithms linear filtration inevitably “blurs” sharp boundaries and contours of objects. In Fig. 16.1.1 shows an example of processing a signal with impulse noise by median and triangular filters with the same window sizes N=3. The advantage of the median filter is obvious.

The end values ​​of the signals are usually taken as the initial and final filtering conditions, or the median is found only for those points that fit within the aperture limits.

Statistical noise suppression median filters, due to their nonlinearity, are usually considered only at a qualitative level. It is also impossible to clearly distinguish between the influence of median filters on signal and noise.

If the values ​​of the elements of a sequence of numbers (x i ) in the filter aperture are independent identically distributed (IID) random variables with an average value m

then the mathematical expectation is M(z) = 0 and, therefore, M(x)=m.

Let F(x) and f(x)=F"(x) denote the distribution and probability density functions of values ​​x. According to probability theory, the distribution y = med(x 1, ..., x n) for large n is approximately normal N(m t,  n), where m t is the theoretical median, determined from the condition F(m t) = 0.5, and the distribution dispersion:

 n 2 = 1/(n 4f 2 (m t)). (16.1.2)

The results presented are valid for both one-dimensional and two-dimensional filtering, if n is chosen equal to the number of points in the filter aperture. If f(x) is symmetric with respect to m, then the distribution of medians will also be symmetric with respect to m and, thus, the formula is valid:

M(med(x 1, ..., x n)) = M(x i) = m.

If the random variables x are NOR and are uniformly distributed on the segment , then the exact value of the median dispersion can be found using the formula:

 n 2 = 1/(4(n+2)) = 3 x /(n+2).

If the random variables x are independent, identically distributed with a normal distribution N(m, ), then m t = m. Modified formula for the variance of the median for small odd values ​​of n:

 g    2 /(2n-2+). (16.1.2")

The value of noise dispersion for random variables in a sliding n-window of arithmetic averaging (first-order least squares filter) has the value  2 /n. This means that for normal white noise, with equal values ​​of n windows of the median filter and the moving average filter, the noise variance at the output of the median filter is approximately 57% greater than that of the moving average filter. For the median filter to produce the same variance as the moving average, its aperture must be 57% larger. It should be borne in mind that the distortion of useful signals, especially if they contain jumps and sharp drops, even with a larger aperture of the median filter may be less than that of moving average filters.

The situation changes if the distribution density of random variables differs significantly from normal and has long tails, which are eliminated by the median filter, which provides the optimal and most plausible estimate of the current signal values ​​based on the minimum mean square approximation. Thus, with an exponential (modulo) distribution of noise density

f(x) = (
/ exp(-
|x-m| /)

noise dispersion after the median filter is 50% less than after the moving average filter.

The limiting case of such distributions is impulse noise, random in amplitude and location of occurrence, which is suppressed by median filters with the greatest efficiency.

Pulse and point noise . When registering, processing and exchanging data in modern measuring, computing and information systems signal flows, in addition to the useful signal s(t- 0) and fluctuation noise q(t), as a rule, contain pulse flows g(t)=
(t- k) of varying intensity with a regular or chaotic structure

x(t) = s(t- 0) + g(t) + q(t). (16.1.3)

Impulse noise refers to the distortion of signals by large pulsed spikes of arbitrary polarity and short duration. The cause of the appearance of pulsed flows can be both external pulsed electromagnetic interference and interference, failures and interference in the operation of the systems themselves. The combination of statistically distributed noise and a flow of quasi-deterministic impulses represents a combined interference. A radical method of combating combined interference is the use of noise-resistant codes. However, this leads to a decrease in speed and complexity of data reception and transmission systems. A simple but quite effective alternative method for cleaning signals under such conditions is a two-stage signal processing algorithm x(t), where at the first stage noise pulses are eliminated from the stream x(t), and at the second stage the signal is cleaned frequency filters from statistical noise. For signals distorted by the action of impulse noise, there is no mathematically rigorous formulation and solution of the filtering problem. Only heuristic algorithms are known, the most acceptable of which is the median filtering algorithm.

Let us assume that noise q(t) is a statistical process with zero mathematical expectation, the useful signal s(t- 0) has an unknown time position  0 , and the flow of noise pulses g(t) has the form:

g(t) =  k a k g(t- k), (16.1.4)

where a k is the amplitude of the pulses in the flow,  k is the unknown temporal position of the pulses,  k =1 with probability p k and  k =0 with probability 1-p k . This specification of pulse noise corresponds to Bernoulli flow /44/.

When applying sliding median filtering with a window of N samples (N is odd) to the stream x(t), the median filter completely eliminates single pulses separated from each other by at least half the filter aperture, and suppresses impulse noise if the number of pulses within the aperture does not exceed (N-1)/2. In this case, with p k = p for all interference pulses, the probability of interference suppression can be determined by the expression /3i/:

R(p) =
p m (1-p) N - p . (16.1.5)

If the probability of error is not very high, then median filtering, even with a fairly small aperture, will significantly reduce the number of errors. The efficiency of eliminating noise pulses increases with increasing filter aperture, but at the same time the distortion of the useful signal can also increase.

Difference plus noise. Let's consider filtering edges in the presence of additive white noise, i.e. filtering sequences, or images, with

In Fig. Figure 16.1.4 shows the sequence of values ​​of the mathematical expectation of medians and the moving average near a difference of height h = 5 with n = 3. The values ​​of the moving average follow a slanted line, which indicates that the difference is blurred. The behavior of the mathematical expectation of the median values ​​also indicates some blurring, although much less than for the moving average.

If we use the measure of the root mean square error (RMS), averaged over N points near the drop, and calculate the values ​​of the standard error depending on the values ​​of h, then it is easy to establish that for small values ​​of h<2 СКО для скользящего среднего немного меньше, чем для медианы, но при h>3 The standard deviation of the median is significantly less than the standard deviation of the mean. This result shows that the moving median is significantly better than the moving average for large height differences. Similar results can be obtained for aperture n=5 and for two-dimensional filtering with apertures 3x3 and 5x5. Thus, the mathematical expectations of the median for small h are close to the mathematical expectations for the corresponding averages, but for large h they are asymptotically limited. This is explained by the fact that for large h (say, h>4) the x variables with mean 0 (for this example) will be sharply separated from the x variables with mean h.

The accuracy measure used can only characterize the sharpness across the edge and does not say anything about the smoothness of the filtered image along the edge. Moving averaging produces signals that are smooth along the edge, whereas when processed using a median filter, long edges are slightly jagged.

Covariance functions with white noise at the input. The normalized autocorrelation functions of the output signals of the median and averaging filters are similar to each other. The similarity of the correlation functions is to some extent explained by the relatively high correlation between the median and the mean, which reaches 0.8 for large n.

An approximate formula for the autocovariance function for a sequence subjected to median filtering is given by:

K() =  2 /(n+(/2)-1))
(1-|j|/n) arcsin((j+)). (16.1.6)

The moving median almost does not smooth out processes that behave over large intervals as functions of the form x i = (-1) i y. Indeed, the shape of the input sequence x i = (-1) i y will be left unchanged by the median filter, although for some values ​​of n it will shift by one step. Moving averaging has a great smoothing effect on such a process, since regular fluctuations in x values ​​are completely eliminated. In general, approximate formulas for moving median covariance functions can be expected to be useful only for sequences on which median filters act in the same way as moving averaging. In the case of highly oscillating sequences and sequences of drops, one should not expect much benefit from them.

Conversion of noise statistics. Median filtering is a nonlinear operation on the input process, which, along with eliminating impulse noise, also changes the distribution of statistical noise q(t), which may be undesirable for constructing subsequent filters. Analytical calculation of the conversion of noise statistics is difficult due to the poor development of the corresponding mathematical apparatus.

Rice. 16.1.5. Histograms of noise signals.

Reducing the number of large noise deviations from the average noise value also leads to a change in the noise spectrum and to a certain suppression of its high-frequency components, which are more numerous in the “tails” of noise distributions. This can be seen in Fig. 16.1.7 on the power density spectra of the input and output signals.

Frequency properties of the filter . To describe linear filters, impulse response to a single pulse, a step function, and frequency transfer functions in the main frequency range are used. Since the median filter eliminates single impulses and preserves differences, we can say that the impulse response of the filter is zero, and the response to the step function is equal to 1. As for the frequency response of the filter, due to the nonlinearity of the filter, it cannot be represented as deterministic function of aperture and frequency. To some extent, we can talk about the filter’s response to cosine functions, which also differs significantly for low and high frequencies main frequency range and phase of harmonics in the filter aperture, which can be seen in Fig. 16.1.9.

Rice. 16.1.9.

As the simulation shows, for low frequencies, when the harmonic period is much larger than the filter aperture window, the moving median and moving average have similar characteristics, the transmission coefficient K n of single-tone signals is equal to 1. As the harmonic frequency increases and depending on the phase of the signal in the filter aperture, signal distortion begins at extreme values ​​(underestimation extreme values), and the value of K p begins to decrease. When the aperture value of the median filter becomes commensurate with the signal period, “false” harmonics caused by frequency interference appear in the spectrum of the output signal input signal with its sampling frequency (lower graphs in Figure 16.1.9).

Rice. 16.1.10. Median filtering of multitone signals

The pattern of frequency interference also depends on the phase of the harmonics, which increases the irregularity of the final results and is clearly visible in Fig. 16.1.11 for various random realizations of the harmonic phase. As the filter aperture sizes increase, the irregularity of filter transmission increases.

Rice. 16.1.11.

Weighted Median Filters used if it is desirable to give more weight to the central points. This is achieved by repeating each set of samples in the filter aperture k i times. So, for example, with n=3 and k -1 =k 1 =2, k 0 =3, the weighted median of the input number series is calculated using the formula:

y i = med (x i - 1, x i - 1, x 0, x 0, x 0, x 1, x 1).

Such a stretched sequence also preserves signal drops and, under certain conditions, makes it possible to increase the suppression of statistical noise dispersion in the signal. None of the weighting coefficients k i should be significantly greater than all the others.

Iterative median filters are performed by sequentially repeating median filtering. If the aperture of unit median filtering preserves differences in the signal, then they are preserved when the filter is applied iteratively until the changes in the filtered signal stop, and the final result is significantly different from the iterative application of the moving average, where in the limit a constant numerical sequence is obtained. When using iterative filters, you can change the filter aperture at each iteration step.

Advantages of median filters.

Simple filter structure for both hardware and software implementation.

The filter does not change the step and sawtooth functions.

The filter suppresses single impulse noise and random noise spikes well.

Disadvantages of median filters.

Median filtering is nonlinear, since the median of the sum of two arbitrary sequences is not equal to the sum of their medians, which in some cases can complicate mathematical analysis signals.

The filter causes the vertices of triangular functions to flatten.

White and Gaussian noise suppression is less effective than linear filters. Weak efficiency is also observed when filtering fluctuation noise.

As the filter window size increases, steep signal changes and jumps are blurred.

The disadvantages of the method can be reduced if median filtering is used with an adaptive change in the size of the filter window depending on the dynamics of the signal and the nature of the noise (adaptive median filtering). As a criterion for window size, you can use, for example, the magnitude of the deviation of the values ​​of neighboring samples relative to the central ranked sample /1i/. As this value decreases below a certain threshold, the window size increases.

Noise in images. No registration system provides ideal image quality of the objects under study. Images in the process of being formed by systems (photographic, holographic, television) are usually exposed to various random interference or noise. A fundamental problem in the field of image processing is the effective removal of noise while preserving important image details for subsequent recognition. The complexity of solving this problem depends significantly on the nature of the noise. Unlike deterministic distortions, which are described by functional transformations of the original image, additive, impulse and multiplicative noise models are used to describe random effects.

The most common type of interference is random additive noise, which is statistically independent of the signal. The additive noise model is used when the signal at the output of the system or at some stage of the conversion can be considered as the sum of a useful signal and some random signal. The additive noise model well describes the effect of film grain, fluctuation noise in radio systems, and quantization noise in analog-to-digital converters etc.

Additive Gaussian noise is characterized by adding normally distributed and zero-mean values ​​to each pixel in the image. This noise usually appears during the digital imaging stage. The main information in images is provided by the contours of objects. Classic linear filters can effectively remove statistical noise, but the degree of blurring of small details in the image may exceed acceptable values. To solve this problem, nonlinear methods are used, for example, algorithms based on anisotropic diffusion of Perron and Malik, bilateral and trilateral filters. The essence of such methods is to use local estimates adequate to determine the contour in the image, and smooth such areas to the least extent.

Impulse noise is characterized by the replacement of part of the pixels in the image with values ​​of a fixed or random variable. In the image, such interference appears as isolated dots of contrast. Impulse noise is typical for devices for inputting images from a television camera, systems for transmitting images over radio channels, as well as for digital systems transfer and storage of images. To remove impulse noise, a special class of nonlinear filters based on rank statistics is used. The general idea of ​​such filters is to detect the position of a pulse and replace it with an estimated value, while keeping the remaining pixels of the image unchanged.

Two-dimensional filters. Median filtering of images is most effective if the noise in the image is impulsive in nature and represents a limited set of peak values ​​against a background of zeros. As a result of applying the median filter, sloping areas and sharp changes in brightness values ​​in images do not change. This is a very useful property specifically for images in which contours carry basic information.

When median filtering noisy images, the degree of smoothing of object contours directly depends on the size of the filter aperture and the shape of the mask. Examples of the shape of masks with a minimum aperture are shown in Fig. 16.2.1. Smaller aperture sizes better preserve image contrast details, but reduce impulse noise suppression to a lesser extent. At larger aperture sizes the opposite picture is observed. The optimal choice of the shape of the smoothing aperture depends on the specifics of the problem being solved and the shape of the objects. This is of particular importance for the task of preserving differences (sharp brightness boundaries) in images.

By the image of a difference we mean an image in which the points on one side of a certain line have same value A, and all points on the other side of this line are the value b, b a. If the filter aperture is symmetrical about the origin, then the median filter preserves any difference image. This is done for all apertures with an odd number of samples, i.e. except for apertures (square frames, rings), which do not contain the origin of coordinates. However, square frames and rings will only change the drop slightly.

w(n) = . (16.2.1)

In this case, the value x i corresponds to a left-to-right and top-to-bottom mapping of a 3x3 window into a one-dimensional vector, as shown in Fig. 16.2.2.

The elements of this vector, as for the one-dimensional median filter, can also be ordered in a series in ascending or descending order of their values:

r(n) = , (16.2.2)

the median value y(n) = med(r(n)) is defined, and the center sample of the mask is replaced by the median value. If, according to the type of mask, the central sample is not included in row 16.2.1, then the median value is found as the average value of the two central samples of series 16.2.2.

The above expressions do not explain how to find the output signal near the end and boundary points in the end sequences and images. One simple trick is to find the median of only those points within the image that fall within the aperture. Therefore, for points located near the boundaries, medians will be determined based on a smaller number of points.

In Fig. 16.2.3 shows an example of cleaning a noisy image using the median Chernenko filter /2i/. The area of ​​image noise was 15%; for cleaning, the filter was applied 3 times in succession.

Adaptive two-dimensional filters. The contradiction in the dependence of the degree of noise suppression and signal distortion on the filter aperture is smoothed out to some extent when using filters with a dynamic mask size, adapting the aperture size to the nature of the image. In adaptive filters, large apertures are used in monotonic areas of the processed signal (better noise suppression), and small apertures are used near inhomogeneities, preserving their features, while the size of the sliding filter window is set depending on the distribution of pixel brightness in the filter mask. They are usually based on an analysis of the brightness of the surroundings of the central point of the filter mask.

The simplest algorithms for dynamically changing the aperture of a filter that is symmetrical along both axes usually operate according to a threshold brightness coefficient S threshold = set based on empirical data. At each current mask position in the image, the iterative process starts with the minimum aperture size. The deviation values ​​of the brightness of neighboring pixels A(r, n) falling into a window of size (n x n) relative to the brightness of the central reference A(r) are calculated by the formula:

S n (r) = |A(r,n)/A(r) – 1|. (16.2.3)

The criterion according to which the size of the mask with the central reference r is increased and the next iteration is performed has the form:

max< S порог. (16.2.4)

The maximum mask size (number of iterations) is usually limited. For non-square masks having dimensions (n ​​x m), iterations can be calculated with separate increases in the parameters n and m, as well as changing the shape of the masks during the iteration process.

Filters based on rank statistics . In the last two decades, nonlinear algorithms based on rank statistics have been actively developed in digital image processing to restore images damaged by various noise models. Such algorithms allow you to avoid additional image distortion when removing noise, and also significantly improve the results of filters on images with a high degree of noise.

The essence of rank statistics usually lies in the fact that series 16.2.1 does not include the central sample of the filter mask, and the value m(n) is calculated from series 16.2.2. At N=3 according to Fig. 16.2.2:

m(n) = (x 4 (n)+x 5 (n))/2. (16.2.5)

The output value of the filter, which replaces the central sample, is calculated using the formula:

y(n) =  x(n) + (1-) m(n). (16.2.6)

The value of the confidence coefficient  is associated with a certain relationship with the statistics of samples in the filter window (for example, the total dispersion of samples, the dispersion of differences x(n)-x i (n) or m(n)-x i (n), the dispersion of positive and negative differences x(n )-x i (n) or m(n)-x i (n), etc.). Essentially, the value of the coefficient  should specify the degree of damage to the central sample and, accordingly, the degree of borrowing from the m(n) samples to correct it. The choice of statistical function and the nature of the coefficient  depending on it can be quite diverse and depends both on the size of the filter aperture and on the nature of the images and noise.

Linear spatially invariant (SPI) filters are useful for restoring and enhancing the visual quality of images. They can be used, for example, when implementing Wiener filters to reduce the noise level in images. However, in order to suppress noise and at the same time preserve the contour part of the images, it is necessary to use nonlinear or linear spatially invariant (SPNI) filters. Limitations on the use of LPI filters in image restoration tasks are discussed in.

Many nonlinear and LPNI filters for image restoration are described in. In ch. 5 of the previous volume devoted to linear filters, Kalman LNI filters used for noise suppression during image restoration were described. In ch. Chapters 5 and 6 of this volume discuss a special nonlinear procedure - median filtering. The use of median filters has been found to be effective in suppressing certain types of noise and periodic interference without simultaneously distorting the signal. Such filters have become very popular in image and speech processing.

Because theoretical analysis of the behavior of median filters is very difficult, very few results have been published on this issue. Two chapters of our book contain mainly new results that have not yet been covered in the open literature. In ch. 5 are being considered statistical properties median filters. In particular, various properties of the output signal of the median filter with Gaussian noise or the sum of a step function and Gaussian noise at the input are outlined.

Chapter 6 covers the deterministic properties of median filters. Particularly interesting are the results related to the so-called stable points of median filters. A stable point is a sequence (in the one-dimensional case) or an array (in the two-dimensional case) that does not change during median filtering. In ch. 6 Tian showed that in the one-dimensional case, the stable points of median filters are “locally monotonic” sequences. The exception is some periodic binary sequences. IN lately Gallagher and Weiss were able to eliminate this exception by limiting the length of the sequences.

In ch. 6 briefly describes an effective median filtering algorithm based on histogram modification. The hardware implementation of median filtering in real time based on digital selective circuits is discussed. A method for finding the median, based on the binary representation of image elements in the filter aperture, is proposed in, which compares the hardware implementation of this method, the histogram transformation algorithm and the method of digital selective circuits in complexity and speed. The implementation of median filters on a binary matrix processor is discussed in. A method has been developed for implementing median filters in a pipeline processor operating synchronously with the video signal.

In ch. 5 and 6 present material of a mainly theoretical nature. As a supplement, we present here some experimental results. In Fig. Figure 1.1 shows examples of stable points of median filters. The original image (a) and the results of applying three different median filters six times (b) are given. Further application of filters does not significantly change the results. Thus, the images in Fig. 1.1, b-d are stable points of three median filters.

Median filters are especially useful for combating impulse (point) noise. This fact is illustrated in Fig. 1.2. In Fig. 1.2, a shows the result of transmitting an image 1.1, a over a binary symmetric channel with noise when using pulse code modulation. In this case, impulse noise appears in the image. The use of a median filter makes it possible to suppress most of the noise emissions (Fig. 1.2, b),

(click to view scan)

while linear smoothing turns out to be completely ineffective (Fig. 1.2, c).

Although in ch. 5 and 6 discuss two-dimensional (spatial) filters, it is obvious that three-dimensional median (spatio-temporal) filters can be applied to moving images, such as television, i.e. the filter aperture can be three-dimensional. Median temporal filtering is especially useful for suppressing bursts of noise, including dropped rows. In addition, it preserves motion much better than time averaging (linear smoothing). Several experiments on temporal filtering (including motion-compensated filtering) are described. In one filtering experiment, a sequence of panning frames containing white Gaussian noise and random line dropouts was median filtered and linearly smoothed. The frame rate of the sequence was 30 frames/s, each frame contained approximately 200 lines of 256 elements each with 8 bits/sample. Panning was carried out horizontally at a speed of approximately 5 image elements per frame. The results for one frame are shown in Fig. 1.3: noisy original frame (a), the same frame after linear smoothing (b) and a frame processed with a median filter (c). It should be noted that the median filter gives

Rice. 1.3. (see scan) Temporal filtering of a sequence of panning frames: a - noisy original; b - linear smoothing over three frames; c - median filtering over three frames

much best results in terms of reducing the number of line dropouts and maintaining sharp edges. However, linear smoothing is more effective for suppressing Gaussian noise. The data presented are consistent with the theoretical ones (see Chapters 5 and 6).

Although both median filtering and linear smoothing are used to improve subjective image quality, it is not yet clear whether they contribute to further machine image analysis - pattern recognition or measurements on the image. Extensive studies have been conducted on the effects of linear and median filtering on the performance of edge extraction, shape analysis, and texture analysis. Some results are given in.