Wiederspruchsbeweis

[Architekt]

Ich habe da eine verzwickte Aufgabe:

Gegeben seien 2 Helligkeitsfunktionen auf Bildern: f1 und f2. Sowie med als die Median Funktion.
Zeige dass die Funktion
med[f1(x) + f2(x)] != med[f1(x)] + med[f2(x)]für beliebige Regionen von Pixeln gilt.

Unser Ansatz dazu sieht wie folgt aus:
Sei med die Median Funktion, f1 eine Helligkeitsfunktion, welche das Bild um eine Konstante a heller macht und f2 die inverse Funktion zu f1, die ein Bild um a dunkler macht.
Wir sagen nun, dass die Aussage:

med[f1(x) + f2(x)] != med[f1(x)] + med[f2(x)]

falsch ist.
Somit nehmen wir an das Folgendes gilt:
Annahme:

med[f1(x) + f2(x)] = med[f1(x)] + med[f2(x)]

Gegeben sei x, als ein Grauwert Array der Länge n, welches bereits geordnet ist. Die Operationen f1 und f2 seien als x + a bzw. x - a definiert.
Dann folgt:

med[f1(x) + f2(x)] = med[f1(x)] + med[f2(x)]

nach berechnen der Helligkeitsfunktionen:

med[(x + a) + (x - a)] = med[x+a] + med[x-a]

Da die Addition jedes Wertes in x das doppelte, also 2x, ergibt (a - a löst sich auf):

med[2x] = med[x+a] + med[x-a]
2x[n/2] = x[n/2]+a + x[n/2] -a
2x[n/2]= 2x[n/2]

Wie man sieht bekommen wir da keinen Widerspruch hin. Ist unser Ansatz falsch? Haben wir irgendwo einen Fehler? Oder ist das da komplett falsch?

[Architekt]

Keiner eine Idee?

[Xin]

Keiner eine Idee?

Da f1(x) und f2(x) linear gegenläufig sind und x unverändert stellt sich mir erstmal die Frage nach dem Median... eine Funktion x -> x hat für den Rückgabewertebereich den Wertebereich, der für x reinkommt. Eine Funktion x -> x+c hat für die Rückgabewertebereich x+c.
Offenbar gibt es ja keine Beschränkung. Weiß+a ist offenbar noch weißer, wie Schwarz-a noch schwarzer ist.

Solange es keine Beschränkung gibt, sehe ich keinen Grund, warum der Median hier überhaupt einen Einfluss hat, da dieser vom entsprechenden Bereich abhängt.

Ist der Helligkeitsbereich von 0 bis 255 gegeben, dann ist Schwarz-a immernoch Schwarz. Das entspricht aber nicht der Abbildung x->x-a.
Bei einer unendlich großem Rückgabewertebereich, liegt der Median halt mittig (also 0 versetzt) oder eben -a/2 bzw. +a/2 versetzt, was sich bei einer Addition wieder auf 0 ausgleicht.

Ich sehe hier ohne Beschränkung keinen Einfluss des Medians!?
Oder verläuft die Helligkeit nicht linear?

[Architekt]

Doch die verläuft linear. Hmm, stimmt eig. ohne eine Eingrenzung macht das nicht soviel Sinn, aber wie lässt sich denn dann ein Beweis dazu formulieren? Weil irgendwie sehe ich nicht, wie unsere Annahme bestätigt werden kann. Weil ohne Median steht ja da

f1(x) + f2(x) = f1(x) + f2(x)

und das ist ja ganz offensichtlich wahr. Also führt irgendwie Beweis durch Widerspruch zu keinem Ergebnis.
Könnte man nicht schlicht Rundungsfehler ins Spiel bringen und annehmen, dass der Median von der Addition der beiden Funktionen ein anderes Ergebnis liefert, als die Addition der Mediane der jeweiligen Funktionen f1 und f2?

[Xin]

Doch die verläuft linear. Hmm, stimmt eig. ohne eine Eingrenzung macht das nicht soviel Sinn, aber wie lässt sich denn dann ein Beweis dazu formulieren?

Ich habe Beweise immer gehasst, weil ich Trivialitäten nicht als solche erkenne. Ich bin bei sowas sehr formalistisch. Dafür hatte ich dann über 100% in der Klausur zur logischen Programmierung, weil ich laut Prof übergenau war

Ein Widerspruchbeweis ist ja im Prinzip nix anderes als das Gegenteil als falsch aufzuzeigen.

Das Gegenteil einer Behauptung wäre bei einer Ungleichung die Gleichung.

Code: Alles auswählen

med[f1(x) + f2(x)] = med[f1(x)] + med[f2(x)]

Nun ist die Frage, was kommt eigentlich für med() raus?
Machen wir uns die Sache erstmal einfach: Setzen wir mal a=0, a ist ja konstant, aber bisher nicht festgelegt.

Code: Alles auswählen

med[x+x] = med[x] + med[x]

x muss ja ein Bild sein. Addiert man zwei Helligkeitswerte, die ja auch noch identisch sind, dann ist der Wert doppelt so groß.

Code: Alles auswählen

med[2*x] = med[x] + med[x]

Da das Bild 2*x doppelt so hell ist, wie das Bild x, ist der Median auch doppelt so groß.

Code: Alles auswählen

2m = m+m

Der Widerspruch ist also nicht falsch. Wenn das Gegenteil der Annahme richtig ist, dann muss die Annahme falsch sein.

Mit a wäre es

Code: Alles auswählen

med[x+a+x-a] = med[x+a] + med[x-a]
med[x+x] = med[x+a] + med[x-a]

Wenn jeder Pixel um den Wert a verändert wird, verändert sich auch der Median um a.

Code: Alles auswählen

2*m = m+a + m-a

Auch hier ist die Umkehrung der Annahme wahr, sofern ich keinen Fehler gemacht habe, also die Annahme falsch.

Weil irgendwie sehe ich nicht, wie unsere Annahme bestätigt werden kann. Weil ohne Median steht ja da

f1(x) + f2(x) = f1(x) + f2(x)

und das ist ja ganz offensichtlich wahr. Also führt irgendwie Beweis durch Widerspruch zu keinem Ergebnis.

Naja, der Widerspruch widerspricht der Annahme... wenn wir den Widerspruch als wahr beweisen, bedeutet dass, dass die Umkehrung - also die ursprüngliche Annahme - falsch sein muss.

Könnte man nicht schlicht Rundungsfehler ins Spiel bringen und annehmen, dass der Median von der Addition der beiden Funktionen ein anderes Ergebnis liefert, als die Addition der Mediane der jeweiligen Funktionen f1 und f2?

Könnte man, aber die Einschränkung der Numerik ergibt sich nicht willkürlich und ist in der Aufgabenstellung auch nicht beschrieben.

[Architekt]

Ich war jetzt mal so frech und habe diesen Beweis abgegeben:

Wir wissen das x ein Pixel-Wert ist, daher gilt x ∈ ℕ (∀x ≥ 0 ∧x ≤ 255)
Weiterhin nehmen wir an, dass a ∈ ℝ (wobei der genaue Wert von a beliebig ist)
Da ℕ + ℝ → ℝ gilt, ist demnach (x+ a) ∈ ℝ ∧ (x - a) ∈ ℝ
Da f1(x) = x + a und f2(x) = x - a gilt f1(x) → ℝ ∧ f2(x) → ℝ
Da med[f1(x) + f2(x)] = med[ℝ + ℝ]auf Grund von Rundungsfehlern für alle unsere oben definierten x Werte zu einem anderen Ergebnis führt, als med[f1(x)] + med[f2(x)] = med[ℝ] + med[ℝ], gilt obige Aussage als bewiesen.

Ich hoffe, er ist zumindest im Ansatz korrekt.

[Xin]

Ich war jetzt mal so frech und habe diesen Beweis abgegeben:

Da med[f1(x) + f2(x)] = med[ℝ + ℝ]auf Grund von Rundungsfehlern für alle unsere Werte zu einem anderen Ergebnis führt, als med[f1(x)] + med[f2(x)] = med[ℝ] + med[ℝ], gilt obige Aussage als bewiesen.

Ich hoffe, er ist zumindest im Ansatz korrekt.

Mutig... Weil wir in der gegenteiligen Annahme einfach alles verkehrt machen und daher zu keinem richtigen Ergebnis kommen, muss halt die Annahme richtig sein.

Toi Toi Toi

[cloidnerux]

Wenn jedes x_i aus x innerhalb von 0-255 wird es recht einfach:
f1(x) ist eine Transformation von einem Vektor zu einem Vektor
med(x) ist eine Transformation zu einem Skalar, dessen Rückgabewert aufgrund der Beschränktheit der einzelnen x_i auch innerhalb 0-255 liegen muss, die Summe Zweier solcher Operationen ist daran aber nicht gebunden.

Bedeutet, dass für ein y=f1(x)+f2(x) jedes y_i auch in 0-255 liegen muss.
Setzten wir das in die Gleichung ein:

Code: Alles auswählen

med(y) = med(f1(x))+med(f2(x))

sehen wir, dass die rechte Seite grundsätzlich nicht den Beschränkungen unterliegt und so auch einen Wert über 255 ergeben kann.

Was man auch Argumentativ belegen kann, da ein Bilder nicht weißer als Weiß sein kann, kann auch der Median nicht größer sein.

[Xin]

Was man auch Argumentativ belegen kann, da ein Bilder nicht weißer als Weiß sein kann, kann auch der Median nicht größer sein.

Was aber nur gilt, wenn wir Beschränkungen in die Aufgabenstellung dazu dichten, die Weiß als ein unüberschreitbares Maximum definiert.

Da es um Helligkeit geht, kommt auch in der Realität nach Weiß nunmal schwarz, was aber nicht das gleiche wie der Wert 0 ist.
Dieses Schwarz nennt man daher auch blind, gefolgt vom Verdampfen des Sehnervs usw.
Blind zum ist auch in der Betriebsanleitung meiner Taucherlampen aufgeführt als Begründung, dass man ein Spot mit 2600 Lumen eben doch etwas zu hell wäre, um damit jemandem ins Gesicht zu leuchten. Mehr als Weiß ist in der Realität also durchaus möglich.

Ich sehe da - abgesehen vom TÜV - keinen Grund, warum eine Lichtquelle daran gebunden wäre, dort zu Enden wo wir sagen 'Och, dass blendet aber'. Und in der Aufgabenstellung habe ich keinen TÜV gefunden, also auch keine Begrenzung von 0 bis 255.

Ansonsten gefällt mir die Begründung, dass y im Gegensatz zur Summe der beiden "Medians" in den gleichen Grenzen wie x liegt wirklich sehr gut, denn das greift ja unabhängig davon, ob eine Beschränkung existiert oder nicht.