Bildverarbeitung Hough-Transformation Alternativen

[mare_crisium]

Au weia, tompcat,

ich habe Deine Fragen noch nicht beantwortet! - Also: Die p_n sind die Parameter der Anpassung, die f_n sind die Funktionen, die mit den Parametern multipliziert werden.

Als Beispiel nimm' die klassische Geradenanpassung (lineare Regression): Da sind die Parameter p_n

p_1 = Steigung und p_0 = Achsenabschnitt.

Die Funktionen f_n sind:

f_1 = x und f_0 = 1

Bei manchen Aufgaben ist es sinnvoll, statt der einfachen linearen Funktion x und der Konstanten 1 andere Funktionen zu verwenden, z.B. Sinus und Kosinus. Was dann herauskommt, ist die Fourieranalyse... Aber lassen wir das !

Die Minimierungsmethode mit dem Differenzieren nach den Parametern p_n funktioniert aber nur, weil der alte Gauss (war 18, als er die Methode 1795 erfand) so genial war, sie genau so zu formulieren, dass sie immer differenzierbar ist und immer zu Gleichungen mit dem Ergebnis Null führt, in denen die Parameter p_n nur als einfache Faktoren wieder auftauchen.

Du hast eine etwas erweiterte die Aufgabe gestellt, nämlich: Lege eine Funktion (in Deinem Fall eine Gerade) so durch die Punktwolke, dass sich die Abweichungssumme durch das Hinzunehmen eines Messpunktes um weniger als z.B. die Standardabweichung ändert. Die Lösung dieser Aufgabe liefert nicht nur die Anpassungsparameter, sondern auch noch den Anfangs- und den Endpunkt der Anpassung.

Beim Zufügen eines Messpunktes ändert sich die Abweichungssumme im allgemeinen sprunghaft, es sei denn, der neue Punkt hätte die Abweichung Null. Du kannst das leicht ausprobieren, indem Du die Anpassung mit einem Satz Punkten durchführst. Dann nimmst Du einen weiteren Punkt dazu und rechnest damit nochmal die Anpassung aus. Anschliessend wirst Du festellen: Durch das Zufügen des Punktes hat die Abweichungssumme einen Sprung gemacht. Funktionen mit solchen Sprüngen kann man nicht differenzieren. Deshalb kann man diese neue Fragestellung mit dem eleganten Differentiationsverfahren von Gauss nicht lösen. Das ist das Problem, auf das ich in dem ersten Abschnitt hinweisen wollte.

Als einzige Möglichkeit fiel mir nur diese ein: Für alle verschiedenen Kombinationen von Punkten die Anpassung durchführen, die Ergebnisse nach dem Wert der Abweichungssumme sortieren und dann die mit den geringsten Abweichungssummen herauspicken. Dazu muss man die Kombinationen aber nummerieren, damit man nach der Sortiererei noch weiss, zu welcher Punktkombination der Wert gehört. Und wie man das hinkriegt, ist der Gegenstand des zweiten Abschnitts.

Bei dem, was wir hier treiben, geht's mir nur darum, den Lesern zu zeigen, was man mit der guten alten Küchenmathematik, wie man sie auf dem Gymnasium lernt, so alles anfangen kann. Wenn man mit Geduld und Zuversicht ein bisschen damit herumspielt, kommt man nämlich erstaunlich weit. Es kann sogar ziemlich spannend werden und Spass machen. Schliesslich sitzt einem dabei auch kein Lehrer im Nacken, der morgen die Hausaufgaben kontrollieren will .

Alles klaro?

Ciao,

mare_crisium

[mare_crisium]

tombcat,

Deine Bemerkung

...weil meine selbst entwickelte Vorverarbeitung nach sich gegenüberstehenden Grauwertkanten sucht, die nicht weiter als 6 Pixel entfernt sein dürfen. Wenn man diese Grenze hochschraubt werden die Fahnen selbstverständlich auch mit erkannt. Das Problem ist, dass diese Fahnen genau den Grauwert des Bodens haben und somit zu 2/3 nicht zu entdeckt sind.

bringt mich auf die Idee, dass Du möglicherweise für die Vorverarabeitung noch keine Laplace-Operatoren einsetzt??? Guck' Dir doch mal das angehängte Dokument an (ich weiss nicht mehr wo ich's her habe) oder google mal nach "Sobel-Filter" oder "Sobel-Operator".

@goara,

auch Glückwunsch meinerseits. Ja, ich bin auch zu meiner Freundin gezogen, die wohnte damals aber im Ausland.

Ciao,

mare_crisium

Edit: Anhang gelöscht wg. Upload-Quota

[tompcat]

Hi Mare

Danke für den Hinweis, aber ich hab schon viele Vorlesungen gehört, die sich damit befassen. Ich habe ganz bewust nur die kleinen Balken erkennen wollen, weil dort das tiefenbild besser ist. Meine Vorverarbeitung sucht gegenüberliegende Kanten und geht vom Sobel-bild aus und sucht von jedem Punkt aus, der über dem Threshold liegt nach einem weiterem Punkt, in Gradientenrichtung um einen Punkt zu finden der eine entgegengesetzte GradientenRichtung hat und ebenso über dem Threshold liegt. Klingt wahnsinnig kompliziert ist es aber nicht und liefert saugeile Ergebnisse. Funktioniert leider nur sehr effizient, wenn nicht sehr weit nach dem Gegenüberliegendem punkt gesucht wird. Und in den Bildern sind somit die Balken ein Leuchtfeuer für den hough.

So jetzt hab ich genug zeit mir deine Idee durchzulesen. Ich lass dann von mir hören

Tompcat

[mare_crisium]

Hi Tompcat,

danke für die erläuternden Bilder und den Text; mir war nicht klar, wie tief Du Dich schon eingearbeitet hast - jetzt hab' ich kapiert, was Du machst. Im Grunde suchst Du nach einem benachbarten Spiegelbild des Bildbereichs um die Sobelkante. Sieht ein bisschen nach einem modifizierten optical flow aus ?

Ciao,

mare_crisium

[mare_crisium]

Hi, tompcat,

ich habe hier die neue Version "Punktstrecke_V05.pdf" angehängt. Darin ist der Trick mit der Nummerierung der Vektorkombinationen, der ein bisschen gewöhnungsbedürftig ist, an einem Beispiel erklärt. Ausserdem ist der Fehler in der ersten Formel für r_0 korrigiert: Es muss durch I dividiert werden, nicht durch K.

Ciao,

mare_crisium

Edit: Anhang gelöscht wg. Upload-Quota

[tompcat]

Hi. Also mitlerweile verstehe ich nun den großteil. Bin natürlich noch nicht davon begeistert, dass die anzahl der Vergleiche exponentiell zunimmt. Ich hoffe irgendewas zu schaffen, was einfach das manschliche Verstädniss von Linien nachahmt. Das geht bei uns auch irgendwie in echtzeit (vieleicht weil wir immer nur den kleinen ausschnitt interprätieren, den wir in einem Augenblick sehen). Ich würde schon gerne mit diesem algorithmus durch ein hochaufgelöstes bild gehen und an die 500 Punkte auswerten.

Ich bin nicht sehr begeistert davon im vorhinein einen Radius zu benutzen um Punkte auszuschließen. Ich denke als mensch kannst du eine lange stark verauschte Linie genausogut erkennen wie eine wenig verauschte kleine linie. Der Radius würde dazu führen, dass man die stark verrauschte große linie nicht mehr erkennen würde. Leider weiß man nicht im voraus, wie lang und wie verauscht eine Linie nun wirklich ist. Ich denke da muss eine art gewichtung rein. Je mehr elemente für eine Linie stimmen umso mehr durfen sie auseinander sein. Das darf sich aber nicht zusehr hochschaukeln können.

hab aber noch eine Fragen:

Wieso gibt es 2^i unterschiedliche gewichtsvectoren?

Tompcat

[mare_crisium]

tja,

als mensch kannst du eine lange stark verauschte Linie genausogut erkennen wie eine wenig verauschte kleine linie

Sehen und Erkennen ist für Menschen ein Vorgang, der weitgehend unbewussten abläuft und uns so unwahrscheinlich leicht fällt, dass es einem einfach nicht in den Kopf will, warum es dafür keinen simplen, eleganten Algorithmen gibt . Es ist meines Wissens noch nicht einmal klar, nach welchen Kriterien die menschliche "Bildauswertung" dabei vorgeht. -

Ein paar Ideen habe ich noch, aber bis daraus ein Algorithmus geworden ist (wenn überhaupt), dauert das ziemlich lange . Ich bastele daran herum, zunächst einmal eine unverrauschte Strecke sauber zu erkennen.

Die Anzahl der Gewichtsvektoren entspricht der Anzahl aller Kombinationen von K Nullen bzw. Einsen. Weil das genau zwei verschiedene Symbole sind (0 und 1) ist die Gesamtzahl der Kombinationen 2^K. Wären es 3 Symbole (z.B. -1,0 und +1), dann wären es 3^K.

Ciao,

mare_crisium