www.mikrocontroller.net

Forum: Digitale Signalverarbeitung / DSP Sobel Operator


Autor: Bum Bum Kurt (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Kann mir jemand erklären wie die Sobel Maske zustande kommt und wieso 
eine Faltung mit dem Filterkern:

-1 0 1
-2 0 2
-1 0 1

einer Ableitung der Grauwerte entspricht? Finde dazu leider keine 
mathematische Erklärung und in meinem Skript steht dazu nur:

diskret: Ableitung -> Differenz :-) Den Prof. kann ich leider nicht 
fragen, da ich mit dem Studium fertig bin. Vielleicht hat jemand von 
euch ne Erklärung dafür. Ich verstehe wie man den Filter anwendet, mir 
fehlt lediglich der Grundgedanke dahinter. Woher kommt diese Maske ?

Autor: Alexander Liebhold (lippi2000)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Das Ganze läuft eigentlich unter numerisch Differentieren. Was bedeutet 
Differenzieren? Der Anstieg in jedem Punkt.

Betrachte mal nur eine Pixelzeile. (kann man recht einfach in Exel mal 
durchspielen) Der einfachste Weg den Anstieg zwischen 2 Punkten zu 
bestimmen ist doch die Subtraktion der Amplituden...

Für dich heißt das: Dein aktuelles Pixel soll dem Anstieg der 
benachbarten Pixel entsprechen. Also Wert vom Nachfolger minus Wert vom 
Vorgänger. Somit hast du die 1.Zeile deiner Faltungsmatrix. [-1 0 1]

Nun hat dein Pixel aber noch weiter Umgebungspixel, da wird dies dann 
einfach auf die anderen ausgeweitet.

Ich hoffe der Denkanstoß hilft dir weiter, das war ja jetzt der 
Sobel-Operator für X-Richtung. Für Y-Richtung wird dieser einfach um 90° 
gedreht.

Gruß Alexander

Autor: Mark Brandis (markbrandis)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Bum Bum Kurt schrieb:
> Kann mir jemand erklären wie die Sobel Maske zustande kommt
>
> -1 0 1
> -2 0 2
> -1 0 1

Durch Kombination (lineare Faltung) der Operatoren


Vielleicht habe ich auch irgendwo Spalten vertauscht, ist auch schon 
lange her die Vorlesung ;-)

Anmerkung: Kann es sein, dass hier der \newline Befehl aus LaTeX nicht 
funktioniert?

Autor: Bum Bum Kurt (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Alexander Liebhold schrieb:
> Das Ganze läuft eigentlich unter numerisch Differentieren. Was bedeutet
> Differenzieren? Der Anstieg in jedem Punkt.
>
> Betrachte mal nur eine Pixelzeile. (kann man recht einfach in Exel mal
> durchspielen) Der einfachste Weg den Anstieg zwischen 2 Punkten zu
> bestimmen ist doch die Subtraktion der Amplituden...
>
> Für dich heißt das: Dein aktuelles Pixel soll dem Anstieg der
> benachbarten Pixel entsprechen. Also Wert vom Nachfolger minus Wert vom
> Vorgänger. Somit hast du die 1.Zeile deiner Faltungsmatrix. [-1 0 1]
>
> Nun hat dein Pixel aber noch weiter Umgebungspixel, da wird dies dann
> einfach auf die anderen ausgeweitet.


Das ist mir auch klar, ich dachte nur das da ein tieferer mathematische 
Sinn dahintersteckt :) Aber der Denkanstoß hat geholfen somit ist mir 
auch alles klar. Warum man da groß mit Faltung rummacht ist allerdings 
übertrieben :-) Ich könnte so denken wie lippi und bastel mir dann 
aufgrund dessen den Filterkern. Vielen Dank an euch Beide !!!! Habs 
verstanden ;)

Autor: Mark Brandis (markbrandis)
Datum:

Bewertung
-1 lesenswert
nicht lesenswert
Bum Bum Kurt schrieb:
> Warum man da groß mit Faltung rummacht ist allerdings
> übertrieben :-)

Im Grunde genommen ist doch die Signalverarbeitung nichts anderes als 
eine einzige große Faltungsorgie ;-)

Autor: Nachtfuchs (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Alexander Liebhold schrieb:
> Das Ganze läuft eigentlich unter numerisch Differentieren. Was
> bedeutet
> Differenzieren? Der Anstieg in jedem Punkt.
>
> Betrachte mal nur eine Pixelzeile. (kann man recht einfach in Exel mal
> durchspielen) Der einfachste Weg den Anstieg zwischen 2 Punkten zu
> bestimmen ist doch die Subtraktion der Amplituden...
>
> Für dich heißt das: Dein aktuelles Pixel soll dem Anstieg der
> benachbarten Pixel entsprechen. Also Wert vom Nachfolger minus Wert vom
> Vorgänger. Somit hast du die 1.Zeile deiner Faltungsmatrix. [-1 0 1]


Überragende Antwort! Danke Alexander, genau das hat mir gefehlt. Warum 
steht das nirgends in nem Buch, Skript oder sonst wo? Optimal, so 
einfach kanns sein :)

Autor: Vincent (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Moin Moin,

ich weiß, dass das hier zu spät ist, aber für Leute die ebenfalls auf 
der Suche nach einer Erklärung sind, gibt es eine aktuelle (2014) von 
Herrn Sobel selbst:

http://www.researchgate.net/publication/239398674_...

Er versucht den Gradienten einer 3x3 Pixelgruppe zu bestimmen. Ein 
Gradient is ja ein Vektor, hat also eine Amplitude und eine Richtung. Er 
bildet hierzu Differenzen zwischen den gegenüberliegenden Pixelpaaren, 
so dass am Ende eine horizontale, eine vertikale und 2 diagonale 
Differenzen entstehen. Diese werden jeweils durch ihre Distanz geteilt 
(man erhält jetzt sozusagen eine Steigung) und mit ihrem Einheitsvektor 
multipliziert. Nach einer weiteren Vektoraddition der entstehenden 
Vektoren ist der Gradient berechnet.

Er zeigt in dem Papier auch, wie diese Vektoraddition in die zwei Sobel 
Operatoren (x und y) zerlegt werden kann. Die Sobel Operatoren bestehen 
nur aus den Koeffizienten der zu summierenden Pixeln. Die Koeffizienten 
sind die vorher berechneten (Differenz geteilt durch Distanz). Damit die 
Koeffizienten Ganzzahlig sind, multipliziert er diese noch mit dem 
Faktor 4.

Das einzige was ich selbst noch nicht verstehe ist, warum er bei den 
Diagonalen Elementen durch 4 teilt, anstatt wie bei den orthognalen 
durch 2. Jedenfalls ist das der Grund, warum am Ende in den Operatoren 
auch -2 und +2 vorkommen.

Autor: Vincent (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Bitte entschuldigt den Doppelpost.

folgende Rechnung könnte den Faktor 4 erklären:

Die vertikale und horizontale Pixeldifferenz ist gleich 2. Deswegen 
teilt Sobel durch 2. Bei diagonalen Pixelpaaren ist die Distanz aber 1 / 
(2 * sqrt(2)). Wenn man nun zusätzlich noch die diagonale Differenz auf 
die beiden orthogonalen Axen aufteilt bzw. projiziert, so kommt als 
Rechnung

1 / (2 * sqrt(2)) * cos pi/4 = 1 / 4

heraus.

Wobei cos mit sin ausgetauscht werden kann, ist also für x und y 
Richtung gleich, da die Diagonale ja im 45 Grad Winkel steht.

Dies ist zwar nur eine Vermutung, passt aber anscheinend perfekt.

Autor: Markus W. (elektrowagi78) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Bum Bum Kurt schrieb:
> -1 0 1
> -2 0 2
> -1 0 1

Diese Matrix unterstützt aber doch nur die Ableitung in X, oder?

Muss man da nicht noch die um 90 Grad gedrehte Matrix berechnen?

Autor: Falk S. (db8fs)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Markus W. schrieb:
> Bum Bum Kurt schrieb:
>> -1 0 1
>> -2 0 2
>> -1 0 1
>
> Diese Matrix unterstützt aber doch nur die Ableitung in X, oder?
>
> Muss man da nicht noch die um 90 Grad gedrehte Matrix berechnen?

Und? Einmal transponieren bitte. Für diagonale Kanten musst du 
eigentlich auch noch 'ne Variante haben.

Bzw. kommt es natürlich wie immer auf die Anwendung an - in den meisten 
Fällen wird man mit 'nem Laplace oder Canny besser fahren bei der 
Kantendetektion.

Siehe auch:
Beitrag "Approximation der partiellen Ableitung bei Pixeln"

Autor: Hannes Jaeger (pnuebergang)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Weil der Thread gerade wiederbelebt wurde

Vincent schrieb:
> folgende Rechnung könnte den Faktor 4 erklären:

Man kann ganz direkt zu den Distanzen kommen, wenn man nur eine passende 
Metrik nimmt.

Er schreibt, er operiert auf einem
> Cartesian Grid.
Grid, also Raster, ist hier der Punkt. Wenn er dabei eine 
Manhattan-Metrik genommen hat, dann kommt er direkt auf die verwendeten 
Distanzen, da in der Manhattan-Metrik die Distanz zwischen zwei Punkten 
die Summe der Beträge der einzelnen Komponenten ist (was du über dein 
Projizieren erreicht hast).

Beispielsweise ist die Distanz der Punkte (1,2) und (3,4) in der 
Manhattan-Metrik:

|1 - 3| + |2 - 4| = 2 + 2 = 4

Aber, er selbst schreibt auch
> Notice that the square root fortuituously drops out of the formula.

Das klingt eher so, als ob er auf anderem Weg zu seinem Ergebnis 
gekommen ist, oder erst spät in dem nicht gezeigten Teil seiner Rechnung 
implizit oder explizit die Manhattan-Metrik verwendet hat.

Autor: Jürgen Schuhmacher (engineer) Benutzerseite
Datum:
Angehängte Dateien:

Bewertung
0 lesenswert
nicht lesenswert
Falk S. schrieb:
> Und? Einmal transponieren bitte. Für diagonale Kanten musst du
> eigentlich auch noch 'ne Variante haben.

Eigentlich sollten sich die Ergebnisse der orthogonalen Betrachtung doch 
komplex ergänzen? Habe das mal für einen 5x5 durchgeführt. Sieht 
eigentlich gut aus. Ich verwende den allerdings auch mit eingebautem 
Fenster.

Autor: Jürgen Schuhmacher (engineer) Benutzerseite
Datum:
Angehängte Dateien:

Bewertung
0 lesenswert
nicht lesenswert
Das Problem mit Sobel und seinen Freunden ist aber immer, dass man eine 
mitunter ein Vorbearbeitung des Bildes benötigt und zudem das Ergebnis 
noch interpretieren muss, wenn man Objekte suchen will und dafür die 
relevanten Punkte ermitteln möchte.

Ich verwende da schon lange einen differenzial geometrischen Filter, der 
auf Gradientenbetrachtung basiert. Der liefert dann entweder die 
positiven oder negativen Wendepunkte oder alternativ die Maxima. Das 
Ergebnis sind nicht Punkte sondern echte Linien mit Breiten von 
überwiegend nur einem Pixel. Das Verfahren ist ziemlich resistent 
gegenüber Rauschen und ungleichmäßig beleuchteten Bildern und geht on 
the fly in einem einzigen Frame. Diese Werte kann man direkt in eine 
Rechenpipeline stopfen, die den Kreismittelpunkt finden kann, bzw. die 
Linie fittet.

Im Bild oben sind die quer laufenden Gradienten in derselben Farbe 
dargestellt, wie die längs laufenden. Das muss man nicht so machen, 
sondern kann die partiell auswerten, wenn man das für das Problem 
braucht.

Autor: Falk S. (db8fs)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Jürgen S. schrieb:
> Falk S. schrieb:
>> Und? Einmal transponieren bitte. Für diagonale Kanten musst du
>> eigentlich auch noch 'ne Variante haben.

> Eigentlich sollten sich die Ergebnisse der orthogonalen Betrachtung doch
> komplex ergänzen?

Hmm, da wär ich mir beim Sobel nicht so sicher, dass beide 
Faltungsmasken spektral die gleiche Darstellung liefern... die 
Frequenzen horizontaler Kanten und die der vertikaler Kanten sind eben 
im Allgemeinen nicht die gleichen. Sobel macht halt nur 'ne Ableitung 
nach x bzw. nach y.

Überführt man die Sobel-X und Sobel-Y-Varianten von folgendem Beispiel, 
behaupte ich einfach mal (ohne das jetzt durch 'ne FFT gejagt zu haben), 
dass da spektral was anderes dabei rumkommt:

http://opencv-python-tutroals.readthedocs.org/en/l...

Autor: Jürgen Schuhmacher (engineer) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Bei Original Sobel sicher nicht, ja - aber man könnte ja weiter denken: 
Ein neutraler Filter mit x,y (1,1, ... -1, -1) und komplexer Berechnung 
wird ausreichend lange Kanten vektoriell in beide Richtungen 
gleichmässig abbilden. Ist halt nur sehr rauschempfindlich.

Autor: Jürgen Schuhmacher (engineer) Benutzerseite
Datum:
Angehängte Dateien:

Bewertung
0 lesenswert
nicht lesenswert
Habe es nochmal ausprobiert: Das Problem ist, dass man mit den Pixeln 
nur dann einen echten 2D-Gradienten abbilden kann, wenn man eben eine 
3x3 Matrix um einen Mittelpunkt bildet. Diese Matrix ist von der 
vektoriellen Länge aber schon zu gross, um kleine Radien sauber zu 
erfassen. Das geht nur mit einem Vektor der Länge 1 korrekt, also der 
Differenz von Punkt zu Punkt. Die ist aber extrem rauschempfindlich und 
praktisch nicht auszuwerten.

Ein Kompromiss zeigt die Grafik oben: Ein 2x2 Filter mit verrutschten 
Mittelpunkten, also einem Vektrokreuz in den Zwischenräumen von Punkten. 
Das resultierende Bild ist um einen halben Pixel versetzt, was bei der 
Analyse zu beachten wäre. Auch das ist noch ziemlich rauschempfindlich, 
kann aber die Kurzen homogen und kontinuierlich abbilden. Problem aber 
auch hier: Die Steilheit der Kante fließt in den Endwert ein, was man 
nicht unbedingt möchte.

: Bearbeitet durch User
Autor: Falk S. (db8fs)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@Juergen: thx für das Beispiel, jetzt wird mir so langsam klar, was Du 
zu tun versuchst: was Du beschreibst geht in Richtung Roberts-Cross 
Kantendetektor.

Das ist halt der miese Trade-Off: nimmt man 'nen rauschunempfindlichen 
Kantendetektor hat der halt die Entrauschung eingebaut und ist teurer. 
Die günstigen Detektoren gehen halt dann nur bei optimalen Bedingungen 
für den Sensor und gutem SNR.

Ich nehme an, Du versuchst, um die Anzahl notwendiger Operationen für 
eine zweidimensionale Kantendetektion zu minimieren. Hast du die 
Möglichkeit solche Faltungen per DSP-Befehlssatzerweiterungen zu 
crunchen (falls die nicht für noch teurere Operationen gebraucht werden) 
- die sollte ja eigentlich bei so einer großen Anzahl gleichförmiger 
Daten mit Multiply/Accumulate eigentlich ganz gut was bringen.

Autor: Jürgen Schuhmacher (engineer) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Falk S. schrieb:
> solche Faltungen per DSP-Befehlssatzerweiterungen zu crunchen
Was meinst Du mit Befehlssatzerweiterung?

Autor: Falk S. (db8fs)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Jürgen S. schrieb:
> Was meinst Du mit Befehlssatzerweiterung?

Na ja, auf älteren ARMs z.B. die DSP-Intrinsics, bei Cortexen könnte 
auch NEON interessant sein.

Siehe auch, Seiten 259ff:
https://books.google.de/books?id=vdk4ZGRqMskC&lpg=...

Edit: für 'ne FPGA-Implementierung entfiele diese Option - höchstens bei 
'nem Zynq.

: Bearbeitet durch User
Autor: Jürgen Schuhmacher (engineer) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Ach so, SW-Gedöhns. Sowas kommt mir nicht rein, ist FPGA :-)

Autor: Falk S. (db8fs)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Jürgen S. schrieb:
> Ach so, SW-Gedöhns. Sowas kommt mir nicht rein, ist FPGA :-)

Sorry, bin zuviel auf ARM unterwegs ^^

Wenn's nur ein Binärbild wäre, könntest Du ja vielleicht die möglichen 
3x3 Nachbarschaften als Eingabe für eine LUT nutzen, die den Wert des 
Mittelpunkts der Nachbarschaft zurückgibt. Liegt halt das Dilemma dann 
in der Binarisierung.

Aber mehr fällt mir da jetzt auch nicht mehr ein. :(

Autor: Jürgen Schuhmacher (engineer) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Wie ich sowas mache, weiß ich schon :D  je nach Anwendung wird mehr oder 
weniger breit gefiltert. In einem Fall 13x13 Subpixel. Da kann man dann 
den Kanternerkenner mit einbauen oder hinten dran hängen.

Antwort schreiben

Die Angabe einer E-Mail-Adresse ist freiwillig. Wenn Sie automatisch per E-Mail über Antworten auf Ihren Beitrag informiert werden möchten, melden Sie sich bitte an.

Wichtige Regeln - erst lesen, dann posten!

  • Groß- und Kleinschreibung verwenden
  • Längeren Sourcecode nicht im Text einfügen, sondern als Dateianhang

Formatierung (mehr Informationen...)

  • [c]C-Code[/c]
  • [avrasm]AVR-Assembler-Code[/avrasm]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] - Link zu Artikel
  • Verweis auf anderen Beitrag einfügen: Rechtsklick auf Beitragstitel,
    "Adresse kopieren", und in den Text einfügen




Bild automatisch verkleinern, falls nötig
Bitte das JPG-Format nur für Fotos und Scans verwenden!
Zeichnungen und Screenshots im PNG- oder
GIF-Format hochladen. Siehe Bildformate.
Hinweis: der ursprüngliche Beitrag ist mehr als 6 Monate alt.
Bitte hier nur auf die ursprüngliche Frage antworten,
für neue Fragen einen neuen Beitrag erstellen.

Mit dem Abschicken bestätigst du, die Nutzungsbedingungen anzuerkennen.