Wann ist Eigenentropie (3 Eigenwerte) minimal?

25.01.2020, 14:28	te one	Auf diesen Beitrag antworten »
Wann ist Eigenentropie (3 Eigenwerte) minimal? Hallo, es handelt sich hier um eine Verständnisfrage zu einem Paper. Daher habe ich keine genaue Aufgabenstellung. Ich versuche das aber mal klar zu definieren: Ich habe viele 3D-Punkte und möchte pro Punkt einige Features berechnen. Diese Features sind abhängig von der lokalen Nachbarschaft (zB ist der Punkt Teil von etwas eher 2-dimensionalem wie dem Boden oder etwas 3-dimensionalem wie einem Auto?) Nun ist die Frage wieiviele Nachbarpunkte man für diese Berechnungen nutzt. Dazu haben findige Menschen mal herausgefunden, dass man die Kovarianzmatrix von immer größer werdenden Nachbarschaften untersucht und jeweils die Eigenentropie berechnet. Die optimale Größe der Nachbarschaft ist genau die, mit kleinster Eigenentropie. $\begin{eqnarray} eigenentropie= - e_1 \cdot \ln{e_1} - e_2 \cdot \ln{e_2} - e_3 \cdot \ln{e_3} \end{eqnarray}$ Wobei gilt $\begin{eqnarray} e_i = \frac{\lambda_i}{\lambda_1 + \lambda_2 + \lambda_3} \end{eqnarray}$ und $\begin{eqnarray} \lambda_i \end{eqnarray}$ die Eigenwerte der Kovarianzmatrix sind. Nun meine Frage: Kann ich die mathematisch minimieren und zB die Aussgabe treffen, dass die Eigenentropie minimal ist, wenn zB nur ein e_i stark ausgeprägt (also Nahe 1) ist? Mir würde jetzt als erstes einfallen mal einen 3D-Plot zu erstellen mit Achsen je von 0 bis 1 (Summe der e_i ist ja 1), dann könnte man das mal versuchen intuitiv zu verstehen. Wobei die Frage ist, wie ich in diesem Plot dann den zugehörigen Wert der Eigenentropie darstelle... Hier fehlt mir absolut die Erfahrung und sicher ein paar Mathe-Kenntnisse Danke schonmal für alle Tipps. Korrektur aus zweitem Beitrag übernommen und diesen gelöscht, damit es nicht so aussieht, als ob schon jemand antwortet. Steffen
26.01.2020, 12:56	zyko	Auf diesen Beitrag antworten »
RE: Wann ist Eigenentropie (3 Eigenwerte) minimal? Leider habe ich mich mit den Entropiewerten insbesondere deren Abhängigkeit von der betrachteten Umgebung nicht befasst. Einen Überblick zu den Eigenwerten der Kovarianzmatrix in einer Umgebung eines Punktes einer POINT CLOUD findest du in https://pdfs.semanticscholar.org/dcd6/bd...9900.1580038842 Weitere Überlegungen dazu in http://citeseerx.ist.psu.edu/viewdoc/dow...p=rep1&type=pdf Ob damit Rückschlüsse auf die Grenzen der Umgebung mittels Entropiebetrachtungen möglich sind, weiß ich nicht. Ich kann mir dies i.A. nicht vorstellen; denn i.d.R. ist die Dichte/Abstand der gemessenen Punkte in verschiedenen Messrichtungen unterschiedlich (Inzidenzwinkel,Messabstand), sodass diese Richtungsvarianz nicht unwesentlich die Auswertung erschwert.
30.01.2020, 17:56	te one	Auf diesen Beitrag antworten »
Vielen Dank für die Antwort. Leider war nicht direkt meine Frage in den Papern behandelt. Ich habe mir daher einen Plot erstellt, um Minima/Maxima sehen zu können. Ein Maximum (nämlich -ln(1/3)) liegt bei e_i = 1/3 vor. Also bei "quadratischen" Umgebungen. Minima liegen vor, wenn zwei Werte gegen 0 gehen und der andere gegen 1. Das sind also eher 1-dimensionale Umgebungen/"Linien" in der Punktwolke.
30.01.2020, 18:20	zyko	Auf diesen Beitrag antworten »
Achtung bei der Berücksichtigung von quaderförmigen Umgebungen: das Ergebnis ist in diesem Fall nicht Rotationsinvariant. Besser kugelförmige Umgebungen berücksichtigen, d.h. alle Punkte, deren euklidischer Abstand zum Zentrum kleiner als eine vorgegebene Schwelle ist. Ist deine Aussage, dass die Entropie beim Wechsel der Umgebungsstruktur minimal ist, eine Vermutung von dir oder gibt es dazu Nachweise? Ich vermute, dass dies nicht generell gilt. Beispiele: a) Kugelumgebung Übergang zu einer Ebene? b) ebene Umgebung Übergang zu kugelförmigen Objekten Falls es sich um Laserentfernungsdaten handelt, dann werden im Allgemeinen nur Oberflächenpunkte erfasst. Bei Bäumen kann es passieren, dass man 'First Pulse' und 'Last Pulse' erhält. Dies bedeutet aber nicht, dass die gesamte Baumstruktur erfasst wird.
30.01.2020, 19:21	te one	Auf diesen Beitrag antworten »
Alles gute Punkte, ich sehe schon du denkst mit Ich beschreibe nun doch mal etwas genauer um was es geht. Und zwar betrachte ich die hier angewandte Methode: https://www.isprs-ann-photogramm-remote-...-3-181-2014.pdf Es geht darum, für jeden Punkt eines Laserscans ("First Pulse", nur Kooridnaten, keine Reflectance/Color) lokale Features zu berechnen, durch die man später neue Scans labeln kann. Heißt: - Ich stecke gelabelte Scans rein (Haus, Baum, Auto, ...) - berechne pro 3D-Punkt verschiedene lokale Merkmale - lerne das ganze einem Classifier - kann zukünftig neue Scans labeln Für die Berechnung lokaler Merkmale eines Punktes nimmt man normalerweise eine Nachbarschaft von x (sagen wir mal 100) Punkten (hier haben wir die von dir kugelförmige Umgebung - denn es sind die x nächsten Nachbarn), macht eine Principal-Component-Analysis auf der Kovarianzmatrix der Nachbarschaft (dadurch hat man Hauptachsen in der Nachbarschaft), und rechnet da bisschen rum. In dem genannten Paper wurde aber gezeigt, dass es besser ist, wenn man die Nachbarschaftsgröße je nach Punkt etwas verschieden wählt. Also nimmt man nicht immer 100 Nachbarpunkte, sondern man sucht zB im Intervall [10,100] die Zahl an Nachbarn, die die Eigenentropy (auf der Kovarianzmatrix der x Nachbarn) minimiert. Nun aber noch zu den Eigenwerten: Meines Wissens nach (habe keine Quelle... Erklärung für die Vermutung folgt) geben die Eigenwerte der Kovarianzmatrix an, wie "stark" die drei, durch die PCA gefundenen Hauptachsen, in dieser Nachbarschaft vorhanden sind. Wenn man Normalen auf 3D-Punkt-Nachbarschaften berechnet, nimmt man den Eigenvektor mit kleinstem Eigenwert. Will ich also die Hauptachse meiner Daten, würde ich den Eigenvektor mit größten Eigenwert wählen. Durch meine Analyse folgere ich nun, dass der Alogrithmus also 1-dimensionale Anordnungen bevorzugt. Betrachten wir ein (liegendes, weil ASCII) Schild im 3D Scan: ......... ......... ......................................... ......... ......... Für einen Punkt links: Kleine Nachbarschaften (alle Punkte links) zeigen eher 2D-Verhalten, Große (ganzes Schild) eher 1D. Also würde man hier eine große Nachbarschaft wählen Für einen Punkt rechts: Kleine Nachbarschaften zeigen eher 1D-Verhalten, Große (ganzes Schild) eher 2D. Man würde also nur den rechten/unteren Teil des Schildes als Nachbarschaft zur Featureberechnung nutzen. Und du hast natürlich recht: Ich bekomme immer nur Oberflächen-Punkte. Heißt also, dass auch sehr konvexe Objekte (Haus, Kiste, ...) eher planar erscheinen können. Andere Objekte wie Baumkronen werden durch das Blätterwerk eher 3-dimensional im Laserscan. Aber das sind dann Dinge, die mein Classifier lernen muss. Derzeit geht es mir erstmal darum, welche Nachbarschaften überhaupt bevorzugt werden. Und nach meine Erläuterung von oben dürfte dafür folgende Priorität gelten 1D > 2D > 3D Ich habe meine Grafik mal angehängt. Da aufgrund der Formel für die Eigenentropie die Summe der drei normalisierten Eigenwerte immer 1 ergeben muss, habe ich das zweidimensional als Heatmap aufgetragen. Der dritte Eigenwert ergibt sich dann aus der Differenz von 1 und den beiden anderen Werten. Da die Funktion minimiert wird, sind blaue Bereiche bevorzugt -> sind genau die Stellen, wo ein Eigenwert gegen 1 geht und die anderen gegen 0. [attach]50522[/attach]
30.01.2020, 21:12	HAL 9000	Auf diesen Beitrag antworten »
Die Entropie $\begin{eqnarray} E = -\sum_{k=1}^n p_k\ln(p_k) \end{eqnarray}$ einer diskreten Wahrscheinlichkeitsverteilung $\begin{eqnarray} (p_1,\ldots,p_n) \end{eqnarray}$ wird a) maximal für die Gleichverteilung $\begin{eqnarray} p_1=\ldots=p_n=\frac{1}{n} \end{eqnarray}$ mit Wert $\begin{eqnarray} E=\ln(n) \end{eqnarray}$ , und b) minimal für Einpunktverteilungen, d.h. $\begin{eqnarray} p_k=1 \end{eqnarray}$ für ein $\begin{eqnarray} k \end{eqnarray}$ , während für alle anderen $\begin{eqnarray} j \end{eqnarray}$ mit $\begin{eqnarray} j\neq k \end{eqnarray}$ dann $\begin{eqnarray} p_j=0 \end{eqnarray}$ gelten muss. Dabei beweist man a) z.B. mit der Jensenschen Ungleichung, während b) noch einfacher ist: Es ist $\begin{eqnarray} -p\ln(p)\geq 0 \end{eqnarray}$ für alle $\begin{eqnarray} 0<p\leq 1 \end{eqnarray}$ , wobei die 0 nur erreicht wird für $\begin{eqnarray} p=1 \end{eqnarray}$ sowie im Grenzwert $\begin{eqnarray} \lim_{p\searrow 0} p\ln(p)=0 \end{eqnarray}$ (obwohl strenggenommen $\begin{eqnarray} 0\ln(0) \end{eqnarray}$ nicht definiert ist, rechnet man bei solchen Entropiebetrachtungen in diesem Fall mit dem Grenzwert 0 für diesen Term). Damit ist $\begin{eqnarray} E\geq 0 \end{eqnarray}$ , wobei 0 wirklich nur erreicht werden kann, wenn alle $\begin{eqnarray} p_k \end{eqnarray}$ gleich 0 oder 1 sind. Da ja nun für eine Verteilung auch noch $\begin{eqnarray} \sum_{k=1}^n p_k=1 \end{eqnarray}$ gelten muss, bleibt nur b) übrig. P.S.: Für die Informationsentropie nimmt man übrigens eher $\begin{eqnarray} \log_2 \end{eqnarray}$ statt $\begin{eqnarray} \ln \end{eqnarray}$ .
Anzeige

31.01.2020, 12:32	zyko	Auf diesen Beitrag antworten »
Deine Idee Trainingsdaten zu verwenden mag sinnvoll sein, aber es ist zu bedenken, dass die Punktdichte bei kleinem Inzidenzwinkel erheblich von der Punktdichte senkrecht dazu abweicht. Bei airborne Laserscan Daten kann man mit Einschränkungen davon ausgehen, dass die Punktdichte quer zum Flugzeug in der Größenordnung der Punktdichte in Flugrichtung ist bzw. näherungsweise abgeschätzt werden kann. Bei einem terrestrischen Laserscanner kannst du nicht generell davon ausgehen, dass für eine senkrechte Wand horizontal und vertikal annähernd die gleichen Punktabstände vorliegen, ins besonders wenn die Wand schräg zur Messrichtung (Scan von langen Fluren/Gebäuden) steht. Deshalb halte ich es für problematisch, die Menge der Trainingspunkte über deren Anzahl zu begrenzen. Besser erscheint mir die Forderung in beide (i.a. senkrecht und quer zur Scanrichtung) Richtungen annähernd gleich viel Punkte zur Berechnung heranzuziehen. Da ich inzwischen Rentner bin, stehen mir leider keine Laserdaten zur Verfügung, sodass ich damit nicht mehr experimentieren kann. Bedenke bitte, dass die Klassifikationsleistung erheblich von der Punktdichte abhängt und somit von dem Abstand des Sensors vom Objekt (Haus, Baum etc.).
31.01.2020, 14:29	te one	Auf diesen Beitrag antworten »
@HAL 9000 Dankeschön für die Aufklärung. Jetzt weiß ich, wie ich das "offiziell" zeigen/beweisen kann Mal sehen, ob das noch seinen Weg in meine Arbeit findet oder ich es bei meiner Grafik belasse. @zyko Super, dass du die Punktdichte anspricht. Genau das hat mir nämlich ebenfalls bei diesem Verfahren "im Bauch geschmerzt". Daher untersuche ich die Klassifikationsgenauigkeit, wenn man die Scans vorher reduziert. Derzeit wende ich eine Reduktion auf Octrees an: Ab einer Kantenlänge von sagen wir mal 10cm lasse ich die weitere Aufteilung meines Octrees stoppen und nutze nur einen zufällig gewählten Punkt pro 10x10x10cm Cube. Damit werden dichte Regionen sparser und Regionen mit wenigen Punkten bleiben unberührt. Das ganze habe ich dann noch etwas weiter gesponnen und gezeigt, dass es Sinn macht, die Features nicht nur auf einer reduzierten Punktwolke zu berechnen, sondern 2 oder 3 verschiedene Reduktionen vorzuberechnen und diese dann zur Featureberechnung zu nutzen. Gibt dann halt doppelt oder dreimal so viele Features pro Punkt. Leider performen moderne Ansätze (Neuronale Netze) etwas besser. Dafür bringt mein Verfahren etwas mehr Verständnis über den Classifier und die Möglichkeit manueller Anpassungen mit sich (statt BlackBox wie in NNs). Außerdem ist in meiner Arbeit (handelt sich bei dem ganzen hier um meine Masterarbeit) ein Tool zum Erzeugen von Laserscans in simulierten Umgebungen entstanden. Als Input nutze ich Szenen in Blender (da kann man zB auch gut Szenen aus der Unreal Engine von Spielen laden), dort werden die Objekte recht simpel halbautomatisch klassifiziert und in ein passendes Format für einen bestehenden Lidar-Simulator gepackt. Dort lassen sich dann terrestrische oder airborne Scans simulieren - wobei man die Punktwolken direkt, durch das Wissen aus der Blender-Szene, gelabelt bekommt Das alles gibts OpenSource, hoffe dass hierdurch etwas größere Datensätze entstehen. Dann können auch Rentner zukünftig ohne Hardware Laserscans durchführen Aus Interesse noch eine persönliche Frage: Offensichtlich kommst du aus dem Laserscanning-Umfeld. Hast du an einer Uni oder bei einem Unternehmen gearbeitet? Jetzt während der Masterarbeit muss man sich ja mal umsehen was aus einem wird... Gerne auch per PN

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »