Vector median filter

The vector median filter is a smoothing filter that is used in digital image processing for color images. With the vector median filter, each pixel is viewed as a vector that contains the values ​​of all color channels at that point. He finds z. B. to reduce noise in geophysical data or for image restoration of color images. In television technology it is used to reduce cross luminance and cross color .

Lena with 10% salt-and-pepper noise in RGB.

Lena with 10% salt-and-pepper noise after filtering with a 3x3 vector median filter based on the L1 norm.

calculation

The median is a key figure from statistics that only makes sense if the elements to be examined can be sorted according to values. This is the case with gray-tone images, which means that the median filter is a possible operation . In the case of multi-channel images, it is only possible to apply the median filter to all color channels separately and then to merge the channels into one image. However, this can result in new colors and thereby falsify the image. One possibility to solve this problem is to see the pixels of the color channels as a connected vector and to determine the vector median from these vectors. Since multi-dimensional elements cannot be put into a meaningful order of values, an alternative calculation of the median is used as the basis.

A data record with elements is considered. Each value is subtracted from this data record from a value that can be anywhere in. The amount of this difference is added up. That which minimizes the sum is the median . ${\displaystyle X}$ ${\displaystyle N}$ ${\displaystyle x_{j}}$ ${\displaystyle X}$ ${\displaystyle x_{i}}$ ${\displaystyle x_{j}}$ ${\displaystyle {\tilde {x}}}$

${\displaystyle {\begin{aligned}\sum _{i=1}^{N}{|{\tilde {x}}-x_{i}|}\leq \sum _{i=1}^{N}{|x_{j}-x_{i}|}\end{aligned}}}$

${\displaystyle {\begin{aligned}{\tilde {x}}=\arg \min _{x_{j}\in X}\sum _{i=1}^{N}{|x_{j}-x_{i}|}\end{aligned}}}$

The first formula, after Burger and Burge, describes the relation of the median to the other values ​​from the data set . The second formula, after Vardavoulia and Andreadis, is the explicit representation of the median. Must be odd to get a clear result. ${\displaystyle X}$ ${\displaystyle N}$

This type of calculation can be generalized to multi-dimensional cases. As with the median calculation, the vector is subtracted from the arbitrarily selected element . In the multi-dimensional case, the difference is normalized with respect to a p-norm and added up over all . The vector median is that element from which minimizes the sum of normalized differences. ${\displaystyle {\vec {x}}_{i}}$ ${\displaystyle {\vec {x}}_{j}}$ ${\displaystyle i}$ ${\displaystyle {\vec {x}}_{\text{VM}}}$ ${\displaystyle X}$

${\displaystyle {\begin{aligned}\sum _{i=1}^{N}{\|{\vec {x}}_{\text{VM}}-{\vec {x}}_{i}\|_{p}}\leq \sum _{i=1}^{N}{\|{\vec {x}}_{j}-{\vec {x}}_{i}\|_{p}}\end{aligned}}}$

${\displaystyle {\begin{aligned}{\vec {x}}_{\text{VM}}=\arg \min _{{\vec {x}}_{j}\in X}\sum _{i=1}^{N}{\|{\vec {x}}_{j}-{\vec {x}}_{i}\|_{p}}\end{aligned}}}$

The pth standard is a parameter that is selected depending on the application. The norms , and are used most frequently . ${\displaystyle L_{p}}$ ${\displaystyle L_{1}}$ ${\displaystyle L_{2}}$ ${\displaystyle L_{\infty }}$

Variations

The vector median filter is a very computationally intensive operator. But there are several approaches to get an accelerated algorithm with respect to a standard, such as B. to Barni.

There are also variations that are useful for special tasks.

Advanced vector median filter

By definition, the vector median is always a value from the filter range. However, it is possible that he will not minimize the sum. The mean value filter is a useful extension , as it is ideally suited for reducing white noise. That is why the calculation is also calculated with regard to the vectorial mean . The calculation is carried out with the vector mean value in the same way as with the other elements from the data set. The extended vector median is the vector mean if the sum is smaller than that of the vector median. The vector mean value is calculated from the sum of the vectors divided by their number. ${\displaystyle {\vec {x}}_{\text{ave}}}$ ${\displaystyle {\vec {x}}_{\text{EVM}}}$

${\displaystyle {\vec {x}}_{\text{EVM}}={\begin{cases}{\vec {x}}_{\text{ave}}&{\text{für }}\sum _{i=1}^{N}{\|{\vec {x}}_{\text{ave}}-{\vec {x}}_{i}\|}\leq \sum _{i=1}^{N}{\|{\vec {x}}_{\text{VM}}-{\vec {x}}_{i}\|}\\{\vec {x}}_{\text{VM}}&{\text{sonst}}\end{cases}}}$

${\displaystyle {\begin{aligned}{\vec {x}}_{\text{ave}}={\frac {1}{N}}\sum _{i=1}^{N}{\vec {x}}_{i}\end{aligned}}}$

Weighted vector median filter

In order to increase the variability, the values ​​in the filter area are assigned weights , whereby the position in the data set is represented. The weighted vector median filter is calculated in the same way as the conventional vector median filter. ${\displaystyle w_{i}}$ ${\displaystyle i}$ ${\displaystyle {\vec {x}}_{\text{WVM}}}$

${\displaystyle {\begin{aligned}\sum _{i=1}^{N}{w_{i}\|{\vec {x}}_{\text{WVM}}-{\vec {x}}_{i}\|}\leq \sum _{i=1}^{N}{w_{i}\|{\vec {x}}_{j}-{\vec {x}}_{i}\|}\end{aligned}}}$

Individual evidence

1. ^ Y. Liu, "Noise reduction by vector median filtering", GEOPHYSICS, vol. 78, no. 3, pp. V79-V87, 2013
2. ↑ JIN, Lianghai; LI, Dehua. A switching vector median filter based on the CIELAB color space for color image restoration. Signal Processing, 2007, Vol. 87, No. 6, pp. 1345-1354.
3. ↑ Moncef Gabbouj, Edward J. Coyle, and Neal C. Gallagher. An overview of median and stack filtering. Circuits, Systems and Signal Processing, 11 (1): 7-45, 1992. p. 7
4. ↑ ^{a b c} Wilhelm Burger and Mark James Burge. Digital Image Processing: An Algorithmic Introduction Using Java. Springer Vieweg, Berlin, 3 edition, 2015.
5. ↑ Maria I. Vardavoulia, Ioannis Andreadis, and Ph Tsalides. A new vector median filter for color image processing. Pattern Recognition Letters, 22 (6): 675-689, 2001.
6. ↑ J. Astola, P. Haavisto, and Y. Neuvo. Vector median filters. Proceedings of the IEEE, 78 (4): 678-689, Apr 1990.
7. ↑ M. Barni et al .: Fast Vector Median Filter Based on Euclidean Norm Approximation. IEEE Signal processing letters, vol. I, no. 6, june 1994, pp. 92-94.
8. ↑ Mauro Barni: A Fast Algorithm for 1-Norm Vector Median Filtering. IEEE Transactions on image processing, vol. 6, no. 10, October 1997, pp. 1452-1455.
9. ↑ J. Astola, P. Haavisto, P. Heinonen, and Y. Neuvo. Median type filters for color signals. In Circuits and Systems, 1988., IEEE International Symposium on, pages 1753-1756 vol. 2, Jun 1988
10. ↑ Laurent Lucat et al: Adaptive and global optimization methods for weighted vector median filters. Signal Processing: Image Communication 17 (2002) 509-524.