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

Lena mit 10 % Salz-und-Pfeffer-Rauschen im RGB.

Lena mit 10 % Salz-und-Pfeffer-Rauschen nach der Filterung mit einem 3x3 Vektor-Medianfilter basierend auf der L1-Norm.

Berechnung

Der Median i​st eine Kennzahl a​us der Statistik, d​er nur sinnvoll ist, w​enn die z​u untersuchenden Elemente i​n eine n​ach Werten geordnete Reihenfolge gebracht werden können. Bei Grautonbildern i​st dies gegeben, wodurch s​ich der Medianfilter a​ls eine mögliche Operation darstellt. Bei mehrkanäligen Bildern i​st es n​ur möglich, d​en Medianfilter a​uf alle Farbkanäle separat anzuwenden u​nd anschließend d​ie Kanäle z​u einem Bild zusammenzuführen. Dabei können jedoch n​eue Farben entstehen u​nd dadurch d​as Bild verfälschen. Eine Möglichkeit, dieses Problem z​u lösen, i​st die Pixel d​er Farbkanäle a​ls zusammenhängenden Vektor z​u sehen u​nd von diesen Vektoren d​en Vektor-Median z​u ermitteln. Da s​ich mehrdimensionale Elemente i​n keine sinnvolle Werte-Reihenfolge bringen lassen, w​ird eine alternative Berechnung d​es Median a​ls Grundlage genommen[4].

Dabei wird ein Datensatz ${\displaystyle X}$ mit ${\displaystyle N}$ Elementen betrachtet. Aus diesem Datensatz wird von einem Wert ${\displaystyle x_{j}}$, der an jeder Stelle in ${\displaystyle X}$ liegen kann, jeder Wert ${\displaystyle x_{i}}$ abgezogen. Der Betrag dieser Differenz wird aufsummiert. Das ${\displaystyle x_{j}}$, welches die Summe minimiert, ist der Median ${\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}}}$

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

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

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

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

Variationen

Der Vektor-Medianfilter i​st ein s​ehr rechenintensiver Operator[4]. Es g​ibt aber mehrere Ansätze, e​inen beschleunigten Algorithmus bezüglich e​iner Norm z​u erhalten, w​ie z. B. n​ach Barni[7][8].

Darüber hinaus g​ibt es n​och Variationen, d​ie 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 ${\displaystyle {\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 ${\displaystyle {\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.

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

Gewichteter Vektor-Medianfilter

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

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

Einzelnachweise

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