"nacheinander" Falten

philomat
Erstie
Erstie
Beiträge: 17
Registriert: 28. Mär 2011 14:50

"nacheinander" Falten

Beitrag von philomat »

hi,

bin mir nicht sicher wie genau ich die gleichung
I_x = filter1 * filter2 * I_original
verstehen soll.
heißt das, ich falte filter2 mit dem originalbild und erhalte ein temporäres bild, dass ich dann mit filter1 falte?
also:
I_temp = filter2 * I_original
I_x = filter1 * I_temp

wenn das der richtige weg ist, spielt dann die reihenfolge eine rolle, also ob ich zuerst mit filter2 oder filter1 falte?

Benutzeravatar
Ronny
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 133
Registriert: 18. Nov 2005 14:33
Wohnort: IGD

Re: "nacheinander" Falten

Beitrag von Ronny »

philomat hat geschrieben: heißt das, ich falte filter2 mit dem originalbild und erhalte ein temporäres bild, dass ich dann mit filter1 falte?
Das ist richtig.
philomat hat geschrieben: wenn das der richtige weg ist, spielt dann die reihenfolge eine rolle, also ob ich zuerst mit filter2 oder filter1 falte?
Die Reihenfolge spielt keine Rolle.

mw1039
Computerversteher
Computerversteher
Beiträge: 346
Registriert: 12. Apr 2011 12:18

Re: "nacheinander" Falten

Beitrag von mw1039 »

Genau. Die Faltung ist kommutativ und assoziativ. D.h. \(f_1 * f_2 * I = f_1 * (f_2 * I) = f_2 * f_1 * I = f_2 * (f_1 * I) = (f_1 * f2) * I = \dots\)
D.h. es spielt gar keine Rolle in welcher Reihenfolge du etwas machst. Aber fuer den Rechenaufwand macht es am meisten Sinn, wenn du \(f_1 * (f_2 * I)\) oder \(f_2 * (f_1 * I)\) berechnest.

kai j
Erstie
Erstie
Beiträge: 20
Registriert: 2. Nov 2011 22:50

Re: "nacheinander" Falten

Beitrag von kai j »

mal kurz dazu, laut wikipedia ist es scheinbar auch möglich, das Bild jeweils mit einer Matrix \(A\) zu falten,
wobei \(I_x = \begin{pmatrix} -1 & 0 & +1 \\ -2 & 0 & +2 \\ -1 & 0 & +1\end{pmatrix} \ast I\) ist. Genaugenommen ist es ja das Matrixprodukt aus \(\begin{pmatrix} 0.25 \\ 0.5 \\ 0.25 \end{pmatrix} \cdot \begin{pmatrix} 0.5 & 0 & -0.5 \end{pmatrix}\), halt nur mit dem Skalar \(-8\) multipliziert.

Das hieße doch im Umkehrschluss aber, dass \(\begin{pmatrix} 0.25 \\ 0.5 \\ 0.25 \end{pmatrix} \ast \begin{pmatrix} 0.5 & 0 & -0.5 \end{pmatrix}\) und \(\begin{pmatrix} 0.25 \\ 0.5 \\ 0.25 \end{pmatrix} \cdot \begin{pmatrix} 0.5 & 0 & -0.5 \end{pmatrix}\) das selbe ergeben, oder nicht?

Bitte um ein bissel Erleuchtung :)

http://en.wikipedia.org/wiki/Sobel_operator

Edit:

und wo wir schon mal dabei sind, in der Formel
\(G = \sqrt{I^2_x + I^2_y}\), bedeuten da die Quadrate, dass man die jeweiligen Matrizen mit sich selbst multipliziert? o_0

mw1039
Computerversteher
Computerversteher
Beiträge: 346
Registriert: 12. Apr 2011 12:18

Re: "nacheinander" Falten

Beitrag von mw1039 »

Ah, eine sehr gute Frage :)

Im Spezialfall von einem \(n \times 1\) und einem \(1 \times n\) Vektor ergibt die Multiplikation und die Faltung zufaellig das gleiche, im allgemeinen Fall aber nicht.

Das Bild kann man auch mit dem \(3\times3\)-Filter falten. Das entspricht dann folgender Klammerung: \((f_1 * f_2) * I\). Das will man aber meistens nicht, weil dann pro Pixel im Ergebnisbild 9 statt \(2\cdot3\) Multiplikationen ausgefuehrt werden muessen. Deswegen haben wir den \(3\times3\) vorher in den \(3 \times 1\) und den \(1 \times 3\) Filter zerlegt. Das geht im Spezialfall von sog. linear separierbaren Filtern.

Ausserdem ist die \(3 \times 1\)-Variante viel leichter programmierbar als die \(3 \times 3\)-Variante.

Das mit \(G\) wird weiter oben in der Aufgabenstellung erklaert: \(G(i,j)=\sqrt{(I_x(i,j))^2+(I_y(i,j))^2}\) D.h. es wird punktweise quadriert, addiert und die Wurzel gezogen. Ein Pixel von G berechnet sich also nur aus den korrespondierenden Pixeln in \(I_x\) und \(I_y\) und nicht aus dem Matrixprodukt o.ae.. \(G(i,j)\) ist quasi die Laenge des Vektors \(\begin{pmatrix}I_x(i,j)\\I_y(i,j)\end{pmatrix}\)

radix89
Mausschubser
Mausschubser
Beiträge: 66
Registriert: 13. Apr 2011 13:45

Re: "nacheinander" Falten

Beitrag von radix89 »

Wie sieht die zweite Anwendung eines Filters denn aus.
Ich habe ja nach der ersten Anwedung eines ein itemp.
So wie ich es verstehe, brauche ich dieses itemp doch nur für die berechnung des mittleren Elements, oder?
Also so:
erster Filter bsp:
pixellinks*0.5 + pixel*0 + pixelrechts*-0.5 = itemp
zweiter filter bsp:
pixeldrüber*0.25 + 0.5*itemp + pixeldrunter*0.25

oder ist das falsch?
Ich bekomm damit häufig negative Werte raus und kann deswegen kein Bild daraus zusammensetzen.

mw1039
Computerversteher
Computerversteher
Beiträge: 346
Registriert: 12. Apr 2011 12:18

Re: "nacheinander" Falten

Beitrag von mw1039 »

Das ist schon richtig so.
Wichtig ist, dass erst der eine Filter vollstaendig auf das ganze Bild angewandt wird und dann auf das Ergebnis (\(I_{\text{temp}}\)) der zweite Filter angewandt wird.
Negative Pixel sind ok. Das Ergebnis ist ja im engeren Sinne kein Bild mehr, sondern eine Ableitung. Ein positiver Wert sagt dann im Grunde, dass eine positive Kante (z.B. von dunkel nach hell) und ein negativer Wert, dass eine negative Kante (z.B. von hell nach dunkel) gefunden wurde.
Bei der Berechnung von \(G\) fallen die negativen Werte durch das Quadrieren wieder raus.

radix89
Mausschubser
Mausschubser
Beiträge: 66
Registriert: 13. Apr 2011 13:45

Re: "nacheinander" Falten

Beitrag von radix89 »

Okay Danke, hat soweit funktioniert.
Nur ist mein Ergebnisbild ein Stück dunkler als die mathlab result Bilder, aber das ist im Rahmen, oder?

mw1039
Computerversteher
Computerversteher
Beiträge: 346
Registriert: 12. Apr 2011 12:18

Re: "nacheinander" Falten

Beitrag von mw1039 »

Das ist vollkommen ok. Das liegt wahrscheinlich daran, dass ich in matlab noch eine Normalisierung vorgenommen habe (so dass der kleinste "Farb"wert 0 und der groesste 1 ist). Das kannst du auch machen, wenn du willst, musst du aber nicht.
Deswegen steht auch in der Aufgabenstellung, dass man gerne von den Beispielen abweichen darf und dass die eigenen Ergebnisse nur plausibel sein sollen.

Martin_H
Windoof-User
Windoof-User
Beiträge: 41
Registriert: 4. Okt 2010 15:52

Re: "nacheinander" Falten

Beitrag von Martin_H »

Hi,
ich hab das jetzt auch so gefaltet, wie radix89 beschrieben hat (somit werden also nur das obere, untere, linke und rechte Pixel eines jedes betrachteten Pixels betrachtet). Das erzeugte Bild ist allerdings sehr ähnlich zum Eingangsbild, es fand also keine FiIlterung statt. Wenn ich allerdings die Matrix \(I_x = \begin{pmatrix} -1/8 & 0 & +1/8 \\ -1/4 & 0 & +1/4 \\ -1/8 & 0 & +1/8\end{pmatrix} \ast I\) habe (somit also alle 8 Pixel um jedes Pixel betrachte), sieht das erzeugte Bild sehr sehr ähnlich dem vorgegebenem Filter-Bild aus. Wäre es also ok, wenn ich die Filterung mit der Matrix berechne (auch dort habe ich nur 6 Berechnungen, da ich einfach nur die 3 linken und die 3 rechten Pixel betrachte und in die Berechnung mit in Betracht ziehe).

mw1039
Computerversteher
Computerversteher
Beiträge: 346
Registriert: 12. Apr 2011 12:18

Re: "nacheinander" Falten

Beitrag von mw1039 »

Eigentlich moechten wir nicht, dass ihr mit dem \(3\times3\)-Filter faltet. Wenn du 0-Eintraege im Filter ueberspringst, hast du in der \(3\times3\)-Variante 6 Multiplikationen und mind. 5 Additionen. In der \(3\times1\)-Variante haettest du 5 Multiplikationen und 4 Additionen.
Wenn man das ganze theoretisch betrachtet, hast du einen quadratischen Aufwand verglichen mit einem linearen. Bei Filtern der Groesse 3 ist das noch ok, aber bei groesseren Filtern wird der Unterschied schnell extrem. Wenn man schon den Spezialfall eines separierbaren Filters hat, nutzt man ihn eigentlich auch immer aus.
Hintergrund ist auch, dass es im Assembler moeglicherweise schneller passieren kann, dass dir die Register ausgehen. Das haengt natuerlich auch von deiner konkreten Implementierung ab, aber es ist generell leichter moeglich den \(3\times1\)-Filter schoen zu programmieren. Bei der Programmierung der filter_C()-Funktion faellt das moeglicherweise noch nicht so auf.

Ist es moeglich, dass sich dein Bild nicht doll veraendert, weil du den falschen Filter benutzt hast? Der \((1/4, 1/2, 1/4)\)-Filter nimmt nur eine Glaettung vor (je nachdem ob der Filter waagerecht oder senkrecht ist, ist auch die Glaettung waagerecht oder senkrecht). Der \((1/2, 0, -1/2)\)-Filter nimmt die eigentliche Ableitung vor (auch jeweils waagerecht oder senkrecht). Kann es sein, dass du einmal waagerecht und einmal senkrecht geglaettet hast und nie abgeleitet hast?

Eine Sache die ich bisher immer ueberlesen hab:
radix89 hat geschrieben: pixeldrüber*0.25 + 0.5*itemp + pixeldrunter*0.25
pixeldrüber und pixeldrunter muessen sich auch auf den Pixel darueber bzw. darunter im Bild itemp beziehen.

Martin_H
Windoof-User
Windoof-User
Beiträge: 41
Registriert: 4. Okt 2010 15:52

Re: "nacheinander" Falten

Beitrag von Martin_H »

Hi nochmal,
erstmal danke für die Hilfe. Der Tipp mit erst die erste Faltung komplett auf I anwenden und dann erst die zweite Faltung auf das bereits bearbeitete I anzuwenden war Gold wert :)
Ich habe mir auch nunmal das fertig bearbeitete Ix-Bild ausgeben lassen und dieses ist nicht (wie eigentlich gedacht) größtenteils grau, sondern schwarz und nur die Kanten in x-Richtung sind weiß.
Das Endbild aus Wurzel(Ix^2+Iy^2) stimmt aber mit dem geforderten Endbild überein (bis auf einen Helligkeitsunterschied, aber der ist ja laut obiger Aussage nicht relevant).

Edit: Wenn ich genau dasgleiche Bild (Helligkeitsmaesig), wie in dem bereits vorhandenem Sobel-Bild haben möchte, muss ich nur die Vektoren (0.5, 0, -0.5) in (1, 0, -1) umwandeln.

mw1039
Computerversteher
Computerversteher
Beiträge: 346
Registriert: 12. Apr 2011 12:18

Re: "nacheinander" Falten

Beitrag von mw1039 »

\(I_x\) sollte nur die Kanten in y-Richtung und \(I_y\) die in x-Richtung anzeigen. Genaugenommen solltest du sogar nur die positiven Kanten sehen, weil alle Werte die 0 oder negativ sind, wahrscheinlich schwarz angezeigt werden. Bei \(G\) merkt man das nicht mehr, weil wieder alle Werte positiv sind.
Bei den Bildern in der Aufgabenstellung hatte ich vor der Ausgabe zur Verdeutlichung (damit man ueberhaupt irgendwelche Kanten sieht) so normiert, dass 0 grau ist, positive Werte weiss und negative schwarz sind.

spaci76
Mausschubser
Mausschubser
Beiträge: 52
Registriert: 9. Mai 2009 18:27

Re: "nacheinander" Falten

Beitrag von spaci76 »

Moin,

auf der Folie war ja beim vertikalen Filter der Rand oben und unten mit 0 aufgefüllt.

jetzt hab ich mal ne frage:

Muss dann beim waagerechten filter links und rechts auch ne 0 hin? Denn, wenn ich versuche den waagerechten Filter auf das zuvor mit dem vertikalen Filter bearbeiteten Bildes anzuwenden kann ich das Bild nicht mehr öffnen "PNM-LADER erwartet eine Ganzzahl und fand keine" unter Gnome -> Bildbetrachter.

In der Tat hat dann das bild[0][x] und bild[x][0] und somit der erste Pixel bei bild[1][1]

Kann jemand was mit der Fehlermeldung anfangen?

Vielen Dank im Voraus
cu daniel

mw1039
Computerversteher
Computerversteher
Beiträge: 346
Registriert: 12. Apr 2011 12:18

Re: "nacheinander" Falten

Beitrag von mw1039 »

spaci76 hat geschrieben:Muss dann beim waagerechten filter links und rechts auch ne 0 hin?
Genau.

Hast du mal versucht das Bild mit nem Texteditor zu oeffnen und dir anzugucken, was da drin steht? Deswegen haben wir pgm als Format gewaehlt, weil das recht gut les- und interpretierbar ist.

Antworten

Zurück zu „Archiv“