Vektor-Medianfilter

Der Vektor-Medianfilter ist ein Glättungsfilter, der in der Digitalen Bildverarbeitung für Farbbilder verwendet wird. Beim Vektor-Medianfilter wird jedes Pixel als ein Vektor angesehen, der die Werte aller Farbkanäle an dieser Stelle enthält. Er findet z. B. zur Reduktion von Rauschen in geophysikalischen Daten^[1] oder zur Bildrestauration von Farbbildern Verwendung^[2]. In der Fernsehtechnik wird er zur Reduktion von Cross Luminance und Cross Color verwendet^[3].

Berechnung

Der Median ist eine Kennzahl aus der Statistik, der nur sinnvoll ist, wenn die zu untersuchenden Elemente in eine nach Werten geordnete Reihenfolge gebracht werden können. Bei Grautonbildern ist dies gegeben, wodurch sich der Medianfilter als eine mögliche Operation darstellt. Bei mehrkanäligen Bildern ist es nur möglich, den Medianfilter auf alle Farbkanäle separat anzuwenden und anschließend die Kanäle zu einem Bild zusammenzuführen. Dabei können jedoch neue Farben entstehen und dadurch das Bild verfälschen. Eine Möglichkeit, dieses Problem zu lösen, ist die Pixel der Farbkanäle als zusammenhängenden Vektor zu sehen und von diesen Vektoren den Vektor-Median zu ermitteln. Da sich mehrdimensionale Elemente in keine sinnvolle Werte-Reihenfolge bringen lassen, wird eine alternative Berechnung des Median als Grundlage genommen^[4].

Dabei wird ein Datensatz $X$ mit $N$ Elementen betrachtet. Aus diesem Datensatz wird von einem Wert $x_{j}$ , der an jeder Stelle in $X$ liegen kann, jeder Wert $x_{i}$ abgezogen. Der Betrag dieser Differenz wird aufsummiert. Das $x_{j}$ , welches die Summe minimiert, ist der Median ${\tilde {x}}$ .

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

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

Die erste Formel, nach Burger und Burge^[4], beschreibt die Relation des Median zu den anderen Werten aus dem Datensatz $X$ . Die zweite Formel, nach Vardavoulia und Andreadis^[5], ist die explizite Darstellung des Medians. Dabei muss $N$ ungerade sein, um ein eindeutiges Ergebnis zu erhalten^[6].

Diese Art der Berechnung lässt sich auf mehrdimensionale Fälle verallgemeinern. Der Vektor ${\vec {x}}_{i}$ wird wie bei der Medianberechnung von dem beliebig gewählten Element ${\vec {x}}_{j}$ abgezogen. Im mehrdimensionalen Fall wird die Differenz bezüglich einer p-Norm normiert und über alle $i$ aufsummiert. Der Vektor-Median ${\vec {x}}_{\text{VM}}$ ist dabei dasjenige Element aus $X$ , das die Summe aus normierten Differenzen minimiert.

{\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}}

{\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}}

Die p-te Norm ist dabei ein Parameter, der je nach Anwendung gewählt wird. Am Häufigsten werden von der $L_{p}$ -Norm die Normen $L_{1}$ , $L_{2}$ und $L_{\infty }$ verwendet.

Variationen

Der Vektor-Medianfilter ist ein sehr rechenintensiver Operator^[4]. Es gibt aber mehrere Ansätze, einen beschleunigten Algorithmus bezüglich einer Norm zu erhalten, wie z. B. nach Barni^[7]^[8].

Darüber hinaus gibt es noch Variationen, die für spezielle Aufgabenstellungen sinnvoll sind.

Erweiterter Vektor-Medianfilter

Der Vektor-Median ist per Definition immer ein Wert aus dem Filterbereich. Es ist jedoch möglich, dass er die Summe nicht minimiert. Eine sinnvolle Erweiterung ist der Mittelwertfilter, da er optimal zur Reduktion von weißem Rauschen geeignet ist^[9]. Deswegen wird die Rechnung auch bezüglich des vektoriellen Mittelwertes ${\vec {x}}_{\text{ave}}$ berechnet. Die Rechnung erfolgt mit dem vektoriellen Mittelwert in gleicher Weise wie mit den übrigen Elementen aus dem Datensatz. Der erweiterte Vektor-Median ${\vec {x}}_{\text{EVM}}$ ist dann der vektorielle Mittelwert, wenn die Summe kleiner ist als die des Vektor-Median. Der vektorielle Mittelwert berechnet sich aus der Summe der Vektoren, dividiert durch deren Anzahl.

{\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}}

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

Gewichteter Vektor-Medianfilter

Um die Variabilität zu erhöhen, werden die Werte im Filterbereich mit Gewichten $w_{i}$ belegt, wobei $i$ die Position im Datensatz repräsentiert. Die Berechnung des gewichteten Vektor-Medianfilters ${\vec {x}}_{\text{WVM}}$ erfolgt analog zum gewöhnlichen Vektor-Medianfilter^[10].

{\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}}

Einzelnachweise

↑ Y. Liu, "Noise reduction by vector median filtering", GEOPHYSICS, vol. 78, no. 3, pp. V79-V87, 2013
↑ JIN, Lianghai; LI, Dehua. A switching vector median filter based on the CIELAB color space for color image restoration. Signal Processing, 2007, 87. Jg., Nr. 6, S. 1345–1354.
↑ 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. S. 7
↑ ^a ^b ^c Wilhelm Burger and Mark James Burge. Digitale Bildverarbeitung: Eine algorithmische Einführung mit Java. Springer Vieweg, Berlin, 3 edition, 2015.
↑ Maria I. Vardavoulia, Ioannis Andreadis, and Ph Tsalides. A new vector median filter for colour image processing. Pattern Recognition Letters, 22(6):675–689, 2001.
↑ J. Astola, P. Haavisto, and Y. Neuvo. Vector median filters. Proceedings of the IEEE, 78(4):678–689, Apr 1990.
↑ M. Barni et al.: Fast Vector Median Filter Based on Euclidean Norm Approximation. IEEE Signal processing letters, vol. I , no. 6, june 1994, S. 92–94.
↑ Mauro Barni: A Fast Algorithm for 1-Norm Vector Median Filtering. IEEE Transactions on image processing, vol. 6, no. 10, October 1997, S. 1452–1455.
↑ 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
↑ Laurent Lucat et al: Adaptive and global optimization methods for weighted vector median filters. Signal Processing: Image Communication 17 (2002) 509–524.

[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, 87. Jg., Nr. 6, S. 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. S. 7

[BurgerBurge-4] Wilhelm Burger and Mark James Burge. Digitale Bildverarbeitung: Eine algorithmische Einführung mit Java. Springer Vieweg, Berlin, 3 edition, 2015.

[5] Maria I. Vardavoulia, Ioannis Andreadis, and Ph Tsalides. A new vector median filter for colour 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, S. 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, S. 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.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]