Digital signal processing. Median filter. Median filtering

Currently, digital signal processing methods are widely used in television, radio engineering, communication systems, control and monitoring. One of the most common operations during such processing is digital filtering signals.

Median filtering was proposed by Tukey as a tool for smoothing time series found in economic research, and later it became widely used in processing images, speech signals, etc. Median filtering is carried out by moving a certain aperture along a sequence of discrete samples and replacing the value in the center of the aperture with the median of the initial readings inside the aperture.

Rice. 1

The essence of median filtering with a three-sample window is illustrated in Fig. 1, where “1” is an opaque plate with three holes A, B and C; 2 - tape with readings applied on it and placed in increments equal to the distance between the holes. The tape is pulled discretely one step at a time. Three readings are simultaneously observed in the holes, from which the middle one is selected. Not the arithmetic mean, not the reading in the middle hole, but the average of three ordered readings. Thus, by arranging the readings shown in Fig. 1, we have values ​​24, 27, 29, that is, the average is the count of 27 in hole A.

In general median sequences y1, y2, ... , ym (m - odd) is the average member of the series, obtained after ordering the sequence in increasing order. For even m, the median is defined as the arithmetic mean of the two middle terms. Other definitions can be found in the literature, but they differ little from each other, and in the vast majority of cases they take m to be odd.

Although the structure of a one-dimensional digital median filter with a three-sample window is known, it is considered here as engineering design example digital device with a simple and easily understandable operating algorithm, performed using combinational nodes described in previous articles of the educational cycle.

IN digital system the functions of holes A, B and C (Fig. 1) are performed by three registers A, B and C (Fig. 2). Register A is the data register of a device operating under conditions of strong industrial noise, for example, a temperature-to-digital converter. All these registers have unified system synchronization, which ensures that data is written to register A, the contents of register A are loaded into register B, and the contents of register B are loaded into register C. Before the filtering procedure begins, all registers are reset. The beginning of the procedure is the moment the first count appears in register A. So, for example, if the input sequence has the form 22, 29, 24, 27, 31, 40, 28, 32, 29,... (22 is the first count), then In the first cycle we will have the following sample values: A = 22, B = 0, C = 0, which means that the average sample is 0. In the second cycle we will have A = 29, B = 22, C = 0, which means that the average count is 22, etc. So, the output sequence will look like: 0, 22, 24, 27, 27, 31, 31, 32, 29,... .

Rice. 2

It's obvious that median filter with a three-count window, it delays the output sequence by one clock cycle relative to the input.

In addition to the indicated registers, the hardware implementation of such a filter must include an n-bit multiplexer MS 4->1, which will use only three information input(n is the number of binary digits of a digital count), and three digital comparators that provide comparison of each count with each, which can be considered as a replacement for the ordering procedure. This allows you to reduce hardware costs and time to calculate the median. Recall that ordering requires comparison and permutation of samples.

Let us note first of all that there is no need to take into account the relations of equality of samples, since if two or three samples are equal, any of them can be considered as the average. Let us choose the relations A > B, A > C, B > C, denoting the corresponding signals from the outputs of three digital comparators by the variables x2, x1 and x0. Let us assume that if the specified relationships are satisfied, then the corresponding output signals of the comparators take the value “1”; if they are not satisfied, then - “0”. So, the task of designing our filter comes down to identifying the structure of the combinational circuit (CC) that implements the address variables a1 and a0 of the MS 4->1 multiplexer, which ensures automatic transmission of the average count of the three received at its information inputs.

Let's draw up a table that shows: Set number - the decimal equivalent of a binary set of three variables x2, x1 and x0; a comment is a conditional histogram of three readings A, B and C, qualitatively corresponding to the situation reflected by one of eight sets of variables x2, x1 and x0; the “average count” column indicates the average count identified from the corresponding histogram. So, in the first line we have the set x2x1x0 = 000, from which it follows that A< B, A < C, B < C. Эта ситуация качественно показана в столбце “комментарий”, из которого следует, что в in this case the average is count B. Since in Fig. 2nd count B arrives at input D1 MS 4->1, then in this line we indicate the values ​​a1 = 0, a0 = 1 (the first option for encoding address variables in the table). When typing x2x1x0 = 001 we have situation A< B, A < C, B >C, which is reflected by the corresponding histogram, and from the latter it follows that the average reading in this case is the reading C. Accordingly, we set a1 = 1, a0 = 0.

Table

The set x2x1x0 = 010 will never appear on the outputs of digital comparators, since it corresponds to the impossible situation A< B, A >C, B< C, поэтому в соответствующей строке таблицы адресные переменные а1 и а0 обозначены крестиком как безразличные значения. Аналогично заполняются все строки таблицы. Рассматривая а1 и а0 как функции алгебры логики от переменных x2, x1 и x0 и используя для их минимизации карты Карно (рис. 3) , получаем

a1 = x1 E x0 (1)
a0 = x2 E x0 or x2 E x0. (2)

Let's try to eliminate the inverter needed to implement x2 or x0 in formula (2). To do this, we recode the address variables a1 and a0, assuming that sample A is supplied to input D1, and B to input D0 MS 4®1 (second option in the table). In Fig. Figure 4 shows Karnaugh maps for the second option for encoding the address variables a1 and a0, from which it follows:

a1 = x1 E x0 (3)
a0 = x2 E x1.
(4)

Rice. 3	Rice. 4

Obviously, the second coding option is preferable. So, the combinational circuit (CC), the structure of which we have defined, consists of two elements “sum mod2”.

Let us verify the validity of the above remark that there is no need to take into account equality relations. Consider the following situations:

• A = B, A > C, in this case x2x1x0 = 011, average count A;
• A = B, A< C, в этом случае x2x1x0 = 000, средний отсчёт В;
• A = C, A > B, in this case x2x1x0 = 100, average count A;
• A = C, A< B, в этом случае x2x1x0 = 001, средний отсчёт C;
• B = C, A > B, in this case x2x1x0 = 110, average count C;
• B = C, A< B, в этом случае x2x1x0 = 000, средний отсчёт B;
• A = B = C, in this case x2x1x0 = 000, average count B.

If “greater than or equal” relations are used at the outputs of digital comparators, then we will have:

• A = B, A > C, in this case x2x1x0 = 111, average count B;
• A = B, A< C, в этом случае x2x1x0 = 100, средний отсчёт А;
• A = C, A > B, in this case x2x1x0 = 110, average count C;
• A = C, A< B, в этом случае x2x1x0 = 011, средний отсчёт А;
• B = C, A > B, in this case x2x1x0 = 111, average count B;
• B = C, A< B, в этом случае x2x1x0 = 001, средний отсчёт С;
• A = B = C, in this case x2x1x0 = 111, average count B.

The analysis carried out confirms that when designing the structure of a combinational CS circuit, any combination of the relations “greater”, “greater than or equal to”, “less than”, “less than or equal to” can be used at the outputs of digital comparators.

Literature

1. Tukey J.W. Exploratory Data Analysis (Addison - Wesley, Reading, Mass., 1971).
2. Fast algorithms in digital image processing / T.S. Huang, J.-O. Eklund, G.J. Nussbaumer et al.; Ed. T.S. Huanga: Transl. from English - M.: Radio and communications. - 1984. -224 p.
3. A device for finding the median of three numbers. A.S. No. 1575168.
4. Vorobiev N.V. Multiplexers // Chip News. - 1998. - No. 11-12. - pp. 38–41.
5. Vorobiev N.V. Multiplexer as a multifunctional node // Chip News. - 1999. - No. 2. - P. 36–41.
6. Vorobiev N.V. Digital comparators // Chip News. - 1999. - No. 5. - P. 8–14.
7. Vorobiev N.V. Digital comparators (continued) // Chip News. - 1999. - No. 7. - P. 35–38.
8. Vorobiev N.V. Minimization of logic algebra functions // Chip News. - 1997. - No. 9-10. - P. 54–60.
9. Pratt W. Digital processing images: Per. from English - M.: Mir. - 1982. - Book. 2. - 480 s. (Book 1. - 312 pp.).

Recently I had to face the need for software filtering of ADC data. Googling and smoking (various documentation) led me to two technologies: Filter low frequencies(LPF) and Median filter. There is a very detailed article about low-pass filters in the Easyelectronics community, so next we will talk about the median filter.

Disclaimer (excuse): This article is for the most part an almost word-for-word translation of an article from the embeddedgurus website. However, the translator (me) also used the above algorithms in my work and found them useful, and perhaps of interest to this community.

So, any linear filter is designed to pass signals in a given frequency band and attenuate all others as much as possible. Such filters are indispensable if you want to eliminate the influence of all kinds of noise. However, in the real world of embedded systems, a designer may be faced with the fact that these classic filters are virtually useless against short-term high-power surges.

This type of noise usually occurs from some random event, such as an electrostatic discharge, a key fob alarm going off near the device, etc. At the same time input signal may take on a value that is obviously impossible. For example, the ADC received data: 385, 389, 388, 388, 912, 388, 387. Obviously, the value 912 here is false and should be discarded. When using a classic filter, this large number will almost certainly affect the output value greatly. The obvious solution here would be to use a median filter.

True to its name, the median filter passes the average of a set of values. Typically the size of this group is odd to avoid ambiguity in choosing the mean. The main idea is that there is a buffer with several values, from which the median is selected.

Differences between median and arithmetic mean

Let's say there are 19 poor people and one billionaire in one room. Everyone puts money on the table - the poor from their pockets, and the billionaire from his suitcase. Each poor person contributes $5, and the billionaire contributes $1 billion (109). The total is $1,000,000,095. If we divide the money equally among 20 people, we get $50,000,004.75. This will be the arithmetic average of the amount of cash that all 20 people in that room had.

The median in this case will be equal to $5 (half the sum of the tenth and eleventh, the median values ​​of the ranked series). This can be interpreted as follows. Having divided our company into two equal groups of 10 people, we can say that in the first group everyone put no more than $5 on the table, and in the second no less than $5. In general, we can say that the median is how much the average person brought with him. On the contrary, the arithmetic average is an inappropriate characteristic, since it significantly exceeds the amount of cash available to the average person.
ru.wikipedia.org/wiki/Median_ (statistics)

Based on the size of this set, we divide filters into two types:
Dimension = 3
Dimension > 3

Filter size 3

Uint16_t middle_of_3(uint16_t a, uint16_t b, uint16_t c) ( uint16_t middle; if ((a<= b) && (a <= c)) { middle = (b <= c) ? b: c; } else if ((b <= a) && (b <= c)) { middle = (a <= c) ? a: c; } else { middle = (a <= b) ? a: b; } return middle; }

Filter dimension >3

#define STOPPER 0 /* Smaller than any datum */ #define MEDIAN_FILTER_SIZE (13) uint16_t median_filter(uint16_t datum) ( struct pair ( struct pair *point; /* Pointers forming list linked in sorted order */ uint16_t value; /* Values to sort */ ); static struct pair buffer = (0); /* Buffer of nwidth pairs */ static struct pair *datpoint = buffer; /* Pointer into circular buffer of data */ static struct pair small = (NULL, STOPPER ); /* Chain stopper */ static struct pair big = (&small, 0); /* Pointer to head (largest) of linked list.*/ struct pair *successor; /* Pointer to successor of replaced data item */ struct pair *scan; /* Pointer used to scan down the sorted list */ struct pair *scanold; /* Previous value of scan */ struct pair *median; /* Pointer to median */ uint16_t i; ) ( datum = STOPPER + 1; /* No stoppers allowed. */ ) if ((++datpoint - buffer) >= MEDIAN_FILTER_SIZE) ( datpoint = buffer; /* Increment and wrap data in pointer.*/ ) datpoint-> value = datum; /* Copy in new datum */ successor = datpoint->point; /* Save pointer to old value"s successor */ median = /* Median initially to first in chain */ scanold = NULL; /* Scanold initially null. */ scan = /* Points to pointer to first (largest) datum in chain */ /* Handle chain-out of first item in chain as special case */ if (scan->point == datpoint) ( scan->point = successor; ) scanold = scan /* Save this pointer and */ scan = scan->point ; /* step down chain */ /* Loop through the chain, normal loop exit via break.< MEDIAN_FILTER_SIZE; ++i) { /* Handle odd-numbered item in chain */ if (scan->point == datpoint) ( scan->point = successor; /* Chain out the old datum.*/ ) if (scan->value< datum) /* If datum is larger than scanned value,*/ { datpoint->point = scanold->point; /* Chain it in here. */ scanold->point = datpoint; /* Mark it chained in. */ datum = STOPPER; ); /* Step median pointer down chain after doing odd-numbered element */ median = median->point; /* Step median pointer. */ if (scan == &small) ( break; /* Break at end of chain */ ) scanold = scan; /* Save this pointer and */ scan = scan->point; /* step down chain */ /* Handle even-numbered item in chain. */ if (scan->point == datpoint) ( scan->point = successor; ) if (scan->value< datum) { datpoint->point = scanold->point; scanold->point = datpoint; datum = STOPPER; ) if (scan == &small) ( break; ) scanold = scan; scan = scan->point; ) return median->value; )
To use this code, we simply call the function every time a new value appears. It will return the median of the latest MEDIAN_FILTER_SIZE measurements.
This approach requires quite a lot of RAM, because... you have to store both values ​​and pointers. However, it is quite fast (58µs at 40MHz PIC18).

Conclusions

1. Technical specifications

Gaussian noise - ‘gaussian’

Original image.

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),

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.

Pulse and point noise

When recording, processing and exchanging data in modern measuring, computing and information systems, signal flows, in addition to the useful signal s(t-t 0) and fluctuation noise q(t), usually contain pulse flows g(t)= d(t-t k) of various intensity with regular or chaotic structure:

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

Impulse noise refers to the distortion of signals by large pulse surges 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 cleared from statistical noise using frequency filters. For signals distorted by 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-t 0) has an unknown time position t 0 О, and the flow of noise pulses g(t) has the form:

g(t) = e k a k g(t-t k),

where a k is the amplitude of the pulses in the flow, t k is the unknown temporal position of the pulses, e k =1 with probability p k and e k =0 with probability 1-p k . This specification of pulsed noise corresponds to Bernoulli flow.

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 .

Figure 1 shows the results of calculations of the probability of suppression of impulse noise by a median filter. At p<0.5 результаты статистического моделирования процесса показывают хорошее соответствие расчетным значениям. Для интенсивных импульсных шумовых потоков при p>0.5 median filtering becomes less effective, because What occurs is not suppression, but amplification and transformation into a stream of impulses of a different structure (with a random duration).

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

where s is a deterministic signal equal to 0 on one side of the or drop and h on the other, and z is the random values ​​of white noise. Let us assume that random noise values ​​z are distributed according to the normal law N(0, s). First, let's consider one-dimensional filtering and assume that the drop occurs at point i = 1, so that for i £ 0 the value x i is N(0, s), and for i≥1 the value x i is N(h, s ).

In Fig. Figure 2 shows the sequence of values ​​of the mathematical expectation of medians and the moving average near a difference of height h = 5 at 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 RMSE 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.

Wiener filtration

Inverse filtering has low noise immunity because this method does not take into account the noisiness of the observed image. The Wiener filter is much less susceptible to interference and singularities caused by the zeros of the transfer function of the distorting system. during its synthesis, along with the type of PSF, information about the spectral densities of image power and noise is used.

The spectral density of the signal is determined by the relation:

where is the autocorrelation function.

The mutual spectral density of the signal is determined by the relation:

, (14)

where is the cross-correlation function.

When constructing a Wiener filter, the task is to minimize the standard deviation of the processed image from the object:

where is the mathematical expectation. By rearranging these expressions, it can be shown that the minimum is achieved when the transfer function is given by the following expression:

Further analysis shows that image restoration, the formation of which is described by the expression, should be carried out using the following OPF of the reconstruction converter:

If there is no noise in the image, then the spectral density of the noise function is 0 and the expression, which is called the Wiener filter, turns into a regular inverse filter.

As the power spectral density of the original image decreases, the transfer function of the Wiener filter tends to zero. For images this is typical at high frequencies.

At frequencies corresponding to the zeros of the transfer function of the forming system, the transfer function of the Wiener filter is also zero. Thus, the problem of singularity of the reconstruction filter is solved.

OPF Wiener filters

Inverse filters

Rice. 3. Examples of filters

Image filtering.

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.

Fig.4

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 Figure 4. With small aperture sizes, contrasting image details are better preserved, but impulse noise is suppressed 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 an image of a difference we mean an image in which the points on one side of a certain line have the 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.

To simplify further consideration, we will limit ourselves to the example of a filter with a square mask of size N × N, with N=3. The sliding filter scans the image samples from left to right and top to bottom, while the input two-dimensional sequence can also be represented as a sequential numerical series of samples (x(n)) from left to right, top to bottom. From this sequence, at each current point, the filter mask extracts the array w(n), as a W-element vector, which in this case contains all the elements from the 3x3 window centered around x(n), and the central element itself, if provided mask type:

w(n) = .

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.

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) = ,

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 8, then the median value is found as the average value of the two central samples of row 9.

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 boundaries, medians will be determined based on a smaller number of points.

Median filtering can also be performed in a recursive version, in which the values ​​above and to the left of the central sample in the mask (in this case x 1 (n)-x 4 (n) in Fig. 9) in row 8 are replaced with those already calculated in previous cycles values ​​y 1 (n)-y 4 (n).

Processing results

Adding noise to the original image

Gaussian Salt & Paper Speckle

Result of processing with the Median filter

MedFilter_Gaussian MedFilter_Salt & Paper MedFilter_Speckle

Result of Wiener filter processing

WinFilter_Gaussian WinFilter_ Salt & Paper WinFilter_ Speckle

The result of calculating the standard deviation of the filtered images from the original.

CONCLUSION

The graph shows that the median filter well suppresses single impulse noise and random noise spikes of samples (CKOSaPeMed) and the graph shows that this is the best method for eliminating this type of noise.

The Wiener filter (CKOSaPeWin), in contrast to the median filter, with an increase in the image noise factor, moved away from the original several times.

Suppression of white and Gaussian noise in the case of the median filter is less effective (CKOGausMed, CKOSpecMed) than that of the Wiener filter (CKOGausWin, CKOSpecWin). Weak efficiency is also observed when filtering fluctuation noise. When increasing the size of the Medial filter window, the image blurs.

References List

1. Digital processing of color images. Shlikht G.Yu. M., EKOM Publishing House, 2007. – 336 p.

2. http://prodav.narod.ru/dsp/index.html

3. Introduction to digital image processing. Yaroslavsky L.P. M.: Sov. radio, 2007. – 312 p.

4. http://matlab.exponenta.ru/

5. Digital image processing in MATLAB. R. Gonzalez, R. Woods, S. Eddins, M.: Tekhnosphere, 2006.

6. http://www.chipinfo.ru/literature/chipnews/199908/29.html

1.Technical specifications......................................................... ........................... 2

2.Analysis of technical specifications.................................................... ....... 3

2.1. Median filter. Median filtering................... 4

2.1.1 Advantages and disadvantages of median filters.................................... 6

2.2 Filtration principle.................................................... ...................... 7

2.3 Statistical noise suppression.................................................... 8

2.4 Pulse and point noise.................................................... ... 9

2.5 Drop plus noise.................................................... ........................... 11

2.6 Wiener filtration.................................................... ........................ 13

2.7. Filtering images................................................... ......... 15

2.7.1 Using adaptive filtering.................................... 17

2.7.2 Using median filtering.................................... 17

3. MATLAB AUXILIARY FUNCTION DESIGN. 18

3.1. Reading an Image and Making a Copy .................................................... 18

3.2. Adding noise to a copy of the original image.................................... 18

3.3. Processing a noisy copy using a median filter. 18

3.4. Processing a noisy copy using a Wiener filter........ 20

3.5. Calculation of the standard deviation between the filtered image and the original. 21

4. Processing results.................................................... ........................... 23

List of Literature................................................... ........................... 26

1. Technical specifications

Comparison of the effectiveness of median and averaging filters

1. Create a copy of the original image.

2. Add noise to a copy of the original image.

Gaussian noise - ‘gaussian’

Impulse noise - ‘salt&pepper’

Multiplicative noise - ‘speckle’

4. Process one of the noisy copies using a filter.

5. Process another copy using filter 2.

7. Construct graphs of the dependence of the standard deviation of the filtered image on the noise parameter (in the same axes for different filters).

Original image.

2. Analysis of technical specifications

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

Median filter. Median filtering

Currently, digital signal processing methods are widely used in television, radio engineering, communication systems, control and monitoring. One of the most common operations in such processing is digital signal filtering.

Median filtering was proposed by Tukey as a tool for smoothing time series found in economic research, and later it became widely used in processing images, speech signals, etc.

Median filter is a type of digital filter widely used in digital signal and image processing to reduce noise. The median filter is a nonlinear FIR filter.

The sample values ​​inside the filter window are sorted in ascending (descending) order; and the value in the middle of the ordered list is output to the filter. In the case of an even number of samples in the window, the output value of the filter is equal to the average of the two samples in the middle of the ordered list. The window moves along the filtered signal and the calculations are repeated.

Median filtering is an effective procedure for processing signals subject to impulse noise.

Median filtering.

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.

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 considered group of reports. This sample replaces the central sample in the window for the signal being processed. Because of this, the median filter is one of the nonlinear filters that 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.

Median filtering is a nonlinear signal processing method developed by Tukey. This method is useful in reducing noise in an image. The 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 a 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 effect of median and averaging (smoothing) filters with a five-element window on step, sawtooth, pulse and triangular 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 examples.

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.

Median filters are often used in practice as a means of pre-processing digital data. A specific feature and main advantage of such filters is their weak response to samples that stand out sharply from neighboring ones, which makes it possible to use median filtering to eliminate anomalous values ​​in data arrays. A characteristic feature of the median filter is its nonlinearity. In many cases, the use of a median filter turns out to be more effective compared to linear filters, since linear data processing procedures are optimal for a Gaussian noise distribution, which is not always typical for real signals. In cases where the differences in signal values ​​are large compared to the dispersion of Gaussian noise, the median filter gives a lower root mean square error of the output signal relative to the input, non-noisy signal when compared with optimal linear filters.

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. Output signal y k sliding median filter width n for the current reading k formed from the input time series …, x k -1 , x k , x k +1 ,… according to the formula:

y k = Me(x k-(n-1)/2 ,…, x k ,…,x k+(n-1)/2 ) ,

Where Me(x 1 ,…,x n ) = x ((n+1)/2)– elements of the variation series, i.e. ranked in ascending order of values x 1 = min(x 1 ,…, x n ) ≤ x (2) ≤ x (3) ≤ … ≤ x n = max(x 1 ,…, x n ) . The width of the median filter is chosen taking into account the fact that it is capable of suppressing a pulse with a width (n-1)/2 counts, provided that n– odd number.

Thus, 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 position in the ranked list is called the median of the considered group of samples if the number of samples is odd. This sample replaces the central sample in the window for the signal being processed. With an even number of samples, the median is set as the arithmetic mean of the two middle samples. The current signal value is usually taken as the initial and final filtering conditions, or the median is found only for those points that fit within the aperture limits.

Due to their characteristics, 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, linear filtering algorithms inevitably “blur” sharp boundaries and contours of objects.

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 the mathematical analysis of 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 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.