Die Optimierung bestimmt die Transformationsparameter. Ziel von der Optimierung ist es Datensätze bzw. Bildpaare optimal zueinander auszurichten.

Im Folgenden werden einige Optimierungsverfahren erläutert:

Hill-Climb Verfahren

Das Verfahren möchte einen höheren bzw. besseren Punkt anpeilen. Es wird solange in eine Richtung gelaufen solang es bergab geht. Im Besten Fall hat das Verfahren das globale Minimum gefunden. Die Methode hat drei Parameter:

  • Der Startpunkt
  • Die Reichweite
  • Anazhl der Suche

 

Gradientenabstiegsverfahren

 Das Verfahren läuft in die Richtung mit der stärksten Änderung. Deshalb wird es auch Verfahren des steilsten Abstiegs genannt. Ziel von dem Verfahren ist es das lokale Minimum zu finden. Vor dem Beginn des Verfahren muss eine Lernrate L festgelegt werden. Das Verfahren startet mit einer zufälligen gewählten Wert.

Ablauf des Gradientenabstiegsverfahren:

  • Es wird bei einem beliebigen Punkt angefangen
  • Es wird in Richtung des Minimuns mit der Schrittlänge L gegangen
  • Das Minimum sollte nun ein Stück näher gerückt sein
  • Es wird wieder der aktuelle Gradient berechnet, um sich wieder dem Minimun anzunähern
  • Das Abstiegsverfahren ist am Minimum angekommen sobald der y-Wert mit dem gefunden x-Wert nicht mehr kleiner wird.

In der Abbildung XY wird das Gradientenabstiegsverfahren visuell gezeigt. Die blaue Linie zeigt die Schrittlänge an und die rote Linie ist die Steigung, die als Laufrichtung betrachtet werden kann. Ist die Laufrichtung positiv ist das Verfahren in die falsche Richtung gelaufen und muss in die andere Richtung laufen.

 

Probleme bei dem Verfahren:

  • Das Verfahren weiß nie, ob es ein lokales oder absolutes Minimum gefunden hat
  • Das Verfahren kann stagnieren, wenn es kaum "Berge und Täler" existieren, weil dadurch die Schritte immer kleiner werden
  • Es können gute Minima übersprüngen werden, wenn das Minima in einem Tal liegt, in dem der Algorithmus sich nicht befindet
  • Das Verfahren kann oszillieren, wenn das Verfahren weder ein globales oder lokales Minimum findet, indem der Gradient von einem gegenüberliegenden Abang zu dem anderen gegeenüberliegenden Abhäng hin und her springt. Bei diesem Sonderfall sind die Beträge der Gradienten gleich
  • Ebenso kann das Verfahren indirekt oszillieren. Dies ist eine erweitere Form der Oszillation. Der Unterschied liegt darin, dass die indirekte Oszillation mehrer Schritte benötigt, um wieder auf dem Ausgangspunkt zu gelangen
  • Die Schrittlänge darf nicht zu groß sein, weil dann die Gefahr besteht über das Minimum hinüberzuspringen.

 

Downhill-Simplex

 Downhill-Simplex Verfahren oder auch als Nelder-Mead-Verfahren bekannt. Der Algorithmus basierend auf einen Simplex. Ein Simplex ist ein in der Geometrie spiezilles n-dimensionales Polytop, dass aus N+1 Punkten aufgespannt wird. Das Grundprinzip ist, dass der Algorithmus den schlechtesten Punkt Pmax ersetzt, um das Minimum zu suchen. Der Algorithmus kann vier mögliche Schritte gehen:

  • Reflektion
    • Es wird der schlechteste Punkt am Mittelpunkt des restlichen Simplex reflektiert
  • Expansion
    • Falls der neue Punkt besser ist als alle anderen wird in die selbe Richtung nochmals ein größerer Schritt gesetzt
  • Kontraktion
    • Der schlechteste Punkt wird näher an den Mittelpunkt der anderen Punkte herangerückt
  • Skalierung
    • Es wird die Entfernung zwischen zwei Punkten halbiert

In der Abbildung XY wird visuell der Ablauf von dem Algorithmus dargestellt.

 

 

Simulated Annealing

 Dieses Verfahren ist inspiriert aus der Metallindustrie. Das Glühen beinhaltet das Erwärmen und Abkühlen eines Materials, um seine physikalischen Eigenschaften aufgrund der Änderungen seiner inneren Struktur zu verändern. Der Vorteil von diesem Algorithmus ist, dass im Gegensatz zu beispielsweise das Hill-Climbing Verfahren lokalte Optima weggesteckt werden können. Zuerst wird geprüft, ob die Nachbarlösung besser ist als die aktuelle Lösung. Wenn es so ist, wird es bedingungslos akzeptiert. Wenn jedoch die Nachbarlösung nicht besser ist, müssen einige Faktoren berücksichtigt werden. Erstens, um wieviel schlechter ist die Nachbarlösung; und zweitens, wie hoch die aktuelle "Temperatur" des Systems ist. Bei hohen Temperaturen akzeptiert das System eher schlechtere Lösungen. Grundsätzlich gilt, je kleiner die Energieänderung (die Qualität der Lösung) und je höher die Temperatur, desto wahrscheinlicher ist es für den Algorithmus, die Lösung zu akzeptieren. 

Temperaturinitialsierung

Zur besseren Optimierung sollte bei der Initialisierung der Temperaturvariable eine Temperatur gewählt werden, die anfänglich praktisch jede Bewegung gegen die aktuelle Lösung erlaubt. Dies gibt dem Algorithmus die Möglichkeit, den gesamten Suchraum besser zu erkunden, bevor er sich in einem fokussierteren Bereich abkühlt und absetzt.

Ablauf des Algorithmus:

  • Zuerst muss die Anfangstemperatur eingestellt und eine zufälige Anfangslösung erstellt werden
  • Danach werden die Schleifen so lange ausgeführt bis die Abbruchbedingung erfüllt worden ist. Entweder wurde das Problem ausreichend abgekühlt oder es wurde eine Lösung gefunden
  • Es wird entschieden, ob zur Nachbarslösung gewechselt werden soll
  • Im Anschluss wird die Temperatur wird gesenkt und mit den Schleifen fortgesetzt

 


Quellen:

[1] Hill-climbing Algorithm for Efficient Color-based Image Segmentation, T. OhashiZaher Al AghbariZaher Al Aghbariand A. Makinouchi, Janauary 2003

[2] http://www.neuronalesnetz.de/backpropagation4.html

[3] http://www.neuronalesnetz.de/backpropagation5.html

[3] https://zkmablog.com/2017/02/11/was-ist-das-gradientenabstiegsverfahren/

[4] Vorlesung von Prof. Dr. Christoph Palm, Bildvearbeitung und 3D Visualisierung, SoSe 2016, OTH Regensburg

[5] http://www.theprojectspot.com/tutorial-post/simulated-annealing-algorithm-for-beginners/6

 

Suche

Kategorien

Wir nutzen Cookies auf unserer Website. Einige von ihnen sind essenziell für den Betrieb der Seite, während andere uns helfen, diese Website und die Nutzererfahrung zu verbessern (Tracking Cookies). Sie können selbst entscheiden, ob Sie die Cookies zulassen möchten. Bitte beachten Sie, dass bei einer Ablehnung womöglich nicht mehr alle Funktionalitäten der Seite zur Verfügung stehen.