Forum: Digitale Signalverarbeitung / DSP / Machine Learning Sobel Operator

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

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

$$\left(\begin{array}{c}1\\1\\\end{array}\right)\texttt{,} \left(\begin{array}{c}1\\1\\\end{array}\right)\texttt{und} \left( \begin{array}{ccc}1 & 0 & -1 \\\end{array} \right)\texttt{:}$$

$$\left(\begin{array}{c}1\\1\\\end{array}\right)\ast \left(\begin{array}{c}1\\1\\\end{array}\right)= \left( \begin{array}{ccc}1 \\ 2 \\ 1 \end{array} \right)$$

$$\left( \begin{array}{ccc}1 \\ 2 \\ 1 \end{array} \right)\ast \left( \begin{array}{ccc}1 & 0 & -1 \\\end{array} \right)= \left( \begin{array}{ccc}1&0&-1\\2&0&-2\\1&0&-1\end{array} \right)$$

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?

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 ;-)

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"

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.

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.

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.

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/latest/py_tutorials/py_imgproc/py_gradients/py_gradients.html

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.

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.

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

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

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=PP1&dq=sloss%20arm%20system%20developers%20guide&hl=de&pg=PA273#v=onepage&q=sloss%20arm%20system%20developers%20guide&f=false

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

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

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

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.