Konvexe Hülle: Erforschung der konvexen Hülle in der Computer Vision

Von Fouad Sabry

Was ist eine konvexe Hülle?

Die konvexe Hülle, die konvexe Hülle oder der konvexe Abschluss einer Form ist die kleinste konvexe Menge, die die Form enthält. Dieses Konzept wird im Bereich der Geometrie verwendet. Es ist möglich, die konvexe Hülle auf zwei verschiedene Arten zu definieren: entweder als Schnittpunkt aller konvexen Mengen, die eine bestimmte Teilmenge eines euklidischen Raums enthalten, oder genauer gesagt als Menge aller konvexen Punktkombinationen, die darin enthalten sind Teilmenge. Die konvexe Hülle einer begrenzten Teilmenge der Ebene kann als die Form angesehen werden, die von einem Gummiband umgeben ist, das um die Teilmenge gespannt ist.

Ihr Nutzen

(I) Einblicke und Validierungen zu den folgenden Themen:

Kapitel 1: Konvexe Hülle

Kapitel 2: Konvexe Menge

Kapitel 3 : Polyeder

Kapitel 4: Polytop

Kapitel 5: Minkowski-Addition

Kapitel 6: Dualität (Mathematik)

Kapitel 7: Carathéodorys Satz (konvexe Hülle)

Kapitel 8: Krummlinige Perspektive

Kapitel 9: Satz von Radon

Kapitel 10: Konvexes Polytop

(II ) Beantwortung der häufigsten öffentlichen Fragen zur konvexen Hülle.

(III) Beispiele aus der Praxis für die Verwendung der konvexen Hülle in vielen Bereichen.

Für wen dieses Buch gedacht ist

Profis, Studenten und Doktoranden, Enthusiasten, Bastler und diejenigen, die über das Grundwissen oder die Informationen für jede Art von konvexem Rumpf hinausgehen möchten.

 

 

• Sprache: Deutsch
• Herausgeber: Eine Milliarde Sachkundig [German]
• Erscheinungsdatum: 5. Mai 2024

Buchvorschau

Kapitel 1: Konvexe Hülle

Die konvexe Hülle, die konvexe Hülle oder der konvexe Abschluss einer Form in der Geometrie ist die kleinste konvexe Menge, die die Form enthält. Die konvexe Hülle kann definiert werden als der Schnittpunkt aller konvexen Mengen, die eine bestimmte Teilmenge eines euklidischen Raums enthalten, oder als die Menge aller konvexen Kombinationen von Punkten in der Teilmenge. Für eine begrenzte Teilmenge der Ebene kann die konvexe Hülle als die Form gesehen werden, die von einem verlängerten Gummiband umschlossen wird.

Offen sind die konvexen Rümpfe offener Mengen, und kompakte Sätze haben konvexe Hüllen, die kompakt sind.

Jeder konvexe Kompaktsatz ist die konvexe Hülle seiner Extremitäten.

Der konvexe Hüllenoperator ist ein Beispiel für einen Closure-Operator. Jedes Antimatroid kann dargestellt werden, indem dieser Closure-Operator auf endliche Punktmengen angewendet wird.

Die konvexe Hülle einer endlichen Anzahl von Punkten in der Ebene oder anderen niedrigdimensionalen euklidischen Räumen zu finden, stellt algorithmische Herausforderungen dar, und das zweifache Problem der überlappenden Halbräume sind wesentliche Probleme der Rechengeometrie.

Sie können zeitlich für O(n\log n) zwei- oder dreidimensionale Punktmengen gelöst werden, und zwar in Zeit, die der Worst-Case-Ausgabekomplexität entspricht, die durch den Satz der oberen Schranke in höheren Dimensionen gegeben ist.

Konvexe Hüllen wurden neben endlichen Punktmengen auch für einfache Polygone, Brownsche Bewegung, Raumkurven und die Inschriften von Funktionen untersucht. In der Mathematik, Statistik, kombinatorischen Optimierung, Ökonomie, geometrischen Modellierung und Ethologie haben konvexe Hüllen zahlreiche Anwendungen. Konvexer Schädel, orthogonale konvexe Hülle, konvexe Schichten, Delaunay-Triangulation und Voronoi-Diagramm sind verwandte Strukturen.

Eine Ansammlung von Punkten in einem euklidischen Raum ist konvex, wenn sie die Liniensegmente enthält, die jedes Paar ihrer Punkte verbinden.

Die konvexe Hülle einer gegebenen Menge X kann definiert werden als

Die (eindeutige) minimale konvexe Menge, die X

Der Schnittpunkt aller konvexen Mengen, die X

Die Menge aller konvexen Kombinationen von Punkten in X

Die Vereinigung aller Simplices mit Scheitelpunkten in X

Bei Mengen, die in der euklidischen Ebene und nicht in einer einzelnen Linie begrenzt sind, ist die Begrenzung der konvexen Hülle die einfache geschlossene Kurve mit minimalem Umfang, die enthält X .

Man kann sich vorstellen, ein Gummiband so zu dehnen, dass es die gesamte Menge umgibt S , und es dann loslässt, so dass es schrumpfen kann; wenn es sich zusammenzieht, umschließt es die konvexe Hülle von S .

Bei dreidimensionalen Objekten gibt die anfängliche Definition der konvexen Hülle an, dass es sich um das kleinstmögliche konvexe Begrenzungsvolumen handelt. Die Definition mit Schnittpunkten konvexer Mengen kann auf nicht-euklidische Geometrie erweitert werden, und die Definition mit konvexen Kombinationen kann von euklidischen Räumen auf beliebige reelle Vektorräume oder affine Räume erweitert werden; Konvexe Hüllen können auch abstrakt zu orientierten Matroiden verallgemeinert werden.

Es ist nicht offensichtlich, dass die erste Definition sinnvoll ist: Warum sollte es eine eindeutige minimale konvexe Menge geben, die X für jedes X ? Die zweite Bedeutung, der Schnittpunkt aller konvexen Mengen mit X , ist jedoch klar definiert.

Es handelt sich um eine Teilmenge jeder anderen konvexen Menge Y , die enthält, X weil Y sie zu den sich schneidenden Mengen gehört.

Es handelt sich also um genau die einzigartige minimale konvexe Menge, die enthält X .

Daher sind die ersten beiden Definitionen identisch.

Jede konvexe Menge, X die enthält, muss (unter der Annahme, dass sie konvex ist) alle konvexen Kombinationen von Punkten in enthalten X , so dass die Menge aller konvexen Kombinationen im Schnittpunkt aller konvexen Mengen enthalten ist, die enthalten X .

Umgekehrt ist die Menge aller konvexen Kombinationen selbst eine konvexe Menge, die enthält, X so dass sie auch den Schnittpunkt aller konvexen Mengen enthält, die enthalten X , so dass die zweite und dritte Definition die gleiche Bedeutung haben.

Nach dem Satz von Carathéodory ist nach dem Satz von Carathéodory, wenn X eine Teilmenge eines d -dimensionalen euklidischen Raumes ist, jede konvexe Kombination von endlich vielen Punkten von X auch eine konvexe Kombination von an den meisten d+1 Punkten in X .

Die Menge der konvexen Kombinationen eines (d+1) -Tupels von Punkten ist ein Simplex; In zwei Dimensionen ist es ein Dreieck, während es in drei Dimensionen ein Tetraeder ist.

Daher gehört jede konvexe Kombination von Punkten von X zu einem Simplex, dessen Eckpunkte gleich X der dritten und vierten Definition sind.

In zwei Dimensionen ist der konvexe Rumpf manchmal in zwei Abschnitte unterteilt, die obere Hülle und die untere Hülle, die sich vom äußersten linken und rechten Punkt des Rumpfes erstrecken. Im Allgemeinen kann man die Grenze von konvexen Hüllen beliebiger Dimension in nach oben gerichtete Punkte (Punkte, bei denen ein nach oben gerichteter Strahl von der Hülle diskontinuierlich ist), nach unten gerichtete Punkte und Extrempunkte unterteilen. Die nach oben und unten gerichteten Teile der Begrenzung für dreidimensionale Hüllen bilden topologische Scheiben.

Die geschlossene konvexe Hülle eines Satzes ist der Abschluss der konvexen Hülle, während die offene konvexe Hülle das Innere (oder in einigen Quellen das relative Innere) der konvexen Hülle ist.

Die geschlossene konvexe Hülle von X ist der Schnittpunkt aller geschlossenen Halbräume, die X enthalten.

Wenn die konvexe Hülle von X selbst bereits eine geschlossene Menge ist (wie es z.B. der Fall ist, wenn X es sich um eine endliche Menge oder allgemeiner um eine kompakte Menge handelt), ist sie folglich identisch mit der geschlossenen konvexen Hülle.

Ein geschlossener Schnittpunkt von Halbräumen ist jedoch selbst geschlossen, daher kann eine nicht geschlossene konvexe Hülle auf diese Weise nicht dargestellt werden.

Wenn die offene konvexe Hülle einer Menge X d -dimensional ist, dann gehört jeder Punkt der Hülle zu einer offenen konvexen Hülle von an den meisten 2d Punkten von X .

Die Menge der Eckpunkte eines Quadrats, des regelmäßigen Oktaeders oder des höherdimensionalen Kreuzpolytops liefert Beispiele, wo genau 2d Punkte benötigt werden.

Die konvexe Hülle eines offenen Satzes ist vom topologischen Standpunkt aus immer selbst offen, während die konvexe Hülle eines kompakten Satzes immer selbst kompakt ist. Es gibt jedoch geschlossene Mengen, deren konvexe Hülle nicht geschlossen ist. Insbesondere der geschlossene Satz

{\displaystyle \left\{(x,y)\mathop {\bigg |} y\geq {\frac {1}{1+x^{2}}}\right\}}

Die konvexe Hülle von (die Ansammlung von Punkten, die auf oder über der Hexe von Agnesi liegen) ist die offene obere Halbebene.

Der Extrempunkt einer konvexen Menge ist ein Punkt, der nicht auf einem offenen Liniensegment zwischen zwei anderen Punkten in der Menge liegt. Jeder Extrempunkt einer konvexen Hülle muss im mitgelieferten Satz enthalten sein; Andernfalls kann es nicht als konvexe Kombination von angegebenen Punkten erstellt werden. Jede kompakte Konvex, die in einem euklidischen Raum (oder allgemeiner in einem lokal konvexen topologischen Vektorraum) gesetzt wird, ist nach dem Krein-Milman-Theorem die konvexe Hülle ihrer Extrempunkte.

Der Operator convex-hull besitzt die Attribute eines Closure-Operators:

Sie ist beträchtlich, was bedeutet, dass die konvexe Hülle jeder Menge X eine Obermenge von ist X .

Sie nimmt nicht ab, d.h. für jeweils zwei Mengen X und Y mit X\subseteq Y ist die konvexe Hülle von X eine Teilmenge der konvexen Hülle von Y .

Sie ist irreversibel, d.h. für jedes X ist die konvexe Hülle der konvexen Hülle von X gleich der konvexen Hülle von X