🤖 AI

Lipschitz Optimization for Formal Verification of Homographies

Dieses Papier stellt einen formalen Verifikationsrahmen vor, der durch Ausnutzung von Lipschitz-Optimierung und stückweiser Stetigkeit von Homographien enge lineare Schranken für Pixelwerte unter 3D-Kamerabewegungsstörungen ableitet und dadurch die ersten rigorosen Robustheitsgarantien für visuelle neuronale Netze in planaren Szenarien ermöglicht, ohne auf komplexe Simulationen oder Surrogatmodelle zurückzugreifen.

Ursprüngliche Autoren: Jean-Guillaume Durand, Panagiotis Kouvaros, Maxime Gariel, Alessio Lomuscio

Veröffentlicht 2026-05-25

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Jean-Guillaume Durand, Panagiotis Kouvaros, Maxime Gariel, Alessio Lomuscio

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Stellen Sie sich vor, Sie lehren einen Roboter, ein Auto zu fahren oder ein Flugzeug zu landen. Sie haben ihm ein „Gehirn" (ein neuronales Netz) gegeben, das darauf trainiert ist, Dinge wie Stoppschilder, Straßenmarkierungen oder Landebahnen zu erkennen. Doch es gibt ein Problem: Diese Gehirne sind zerbrechlich. Wenn Sie die Beleuchtung, die Farbe oder den Winkel des Fotos nur geringfügig ändern, könnte der Roboter plötzlich denken, ein Stoppschild sei ein Geschwindigkeitsschild oder eine Landebahn sei bloß Gras.

Um sicherzustellen, dass diese Roboter sicher sind, müssen wir mathematisch beweisen, dass sie keine Fehler machen, selbst wenn die Dinge etwas wackelig werden. Diese Arbeit stellt eine neue, superpräzise Methode vor, um diesen Beweis zu führen, speziell für den Fall, dass sich die Kamera im dreidimensionalen Raum bewegt.

Hier ist die Aufschlüsselung ihrer Arbeit mit einfachen Analogien:

1. Das Problem: Das „Gummiband" vs. die „Realwelt"

Die meisten aktuellen Sicherheitsprüfungen für KI sind wie das Spannen eines Gummibandes über ein Bild. Sie gehen davon aus, dass die KI weiterhin funktioniert, wenn man die Pixel ein wenig wackeln lässt (wie etwa die Helligkeit ändert oder Rauschen hinzufügt). Dies wird als „ $\ell_p$ -Norm"-Prüfung bezeichnet.

In der realen Welt wackelt die Kamera jedoch nicht nur die Pixel; sie bewegt sich. Wenn Sie den Kopf drehen (Gieren), neigen (Nicken) oder nach vorne gehen, verändert sich das Bild auf komplexe, geometrische Weise.

Die Analogie der Arbeit: Stellen Sie sich ein flaches Stück Papier mit einer Zeichnung darauf vor. Wenn Sie nur Rauschen hinzufügen, ist das wie das Bestreuen des Papiers mit Pfeffer. Wenn Sie jedoch die Kamera bewegen, ist es, als würden Sie dieses Papier aus einem anderen Winkel betrachten. Die Zeichnung wird verzerrt, gedehnt und gestaucht. Die alten „Gummiband"-Sicherheitsprüfungen sind zu locker; sie versuchen, diese Verzerrung mit einer riesigen, unscharfen Wolke zu überdecken, die unmögliche Bilder einschließt (wie ein Stoppschild, das sich in eine Pizza verwandelt). Dies macht die Sicherheitsprüfung nutzlos, da sie nicht beweisen kann, dass die KI sicher ist.

2. Die Lösung: Die „Magische Karte" (Homographie)

Die Autoren erkannten, dass für viele Dinge, die für Roboter wichtig sind – wie flache Straßenschilder, der Boden oder eine Landebahn – die Verzerrung, die durch die Bewegung der Kamera verursacht wird, einer spezifischen, vorhersagbaren mathematischen Regel folgt, die als Homographie bezeichnet wird.

Die Analogie: Denken Sie an die Bewegung der Kamera als eine magische Karte. Wenn Sie genau wissen, wie sich die Kamera bewegt hat (z. B. „5 Grad nach links gedreht"), können Sie eine perfekte, geschlossene Karte zeichnen, die Ihnen genau sagt, woher jedes einzelne Pixel im neuen Bild im alten Bild stammt. Es ist keine Vermutung; es ist ein präzises geometrisches Rezept.

3. Die Methode: „Lipschitz-Optimierung" (Die Geschwindigkeitsbegrenzung)

Jetzt, wo sie die magische Karte haben, müssen sie beweisen, dass die KI nicht verwirrt wird. Die Herausforderung besteht darin, dass die Karte nicht-linear ist (sie krümmt und verdreht sich), was die Berechnung der genauen Grenzen schwierig macht.

Sie verwendeten eine Technik namens Lipschitz-Optimierung.

Die Analogie: Stellen Sie sich vor, Sie wandern einen Berg hinauf (die Pixelwerte) und möchten wissen, wie hoch der höchste Punkt ist, den Sie innerhalb eines bestimmten Bereichs erreichen könnten. Sie müssen nicht jeden einzelnen Zoll erklimmen. Stattdessen wissen Sie, dass der Berg eine Geschwindigkeitsbegrenzung hat (die Lipschitz-Konstante). Sie wissen, dass Sie, egal wie steil der Pfad ist, nicht schneller als eine bestimmte Rate klettern können.
Indem sie einige Punkte auf dem Berg abtasten und die „Geschwindigkeitsbegrenzung" des Geländes kennen, können sie mathematisch garantieren, dass der Gipfel des Berges (der schlimmste Fall für den Pixelwert) eine bestimmte Höhe nicht überschreiten kann. Dies ermöglicht es ihnen, eine enge, genaue Box um alle möglichen verzerrten Bilder zu zeichnen.

4. Die Ergebnisse: Schneller und Präziser

Das Team entwickelte ein Werkzeug, um diese Mathematik automatisch durchzuführen.

Geschwindigkeit: Sie machten es 89 % schneller als frühere Methoden. Es ist wie ein Upgrade vom Fahrrad zum Sportwagen für diese Sicherheitsprüfungen.
Präzision: Ihre „Sicherheitsbox" ist 7 % enger. Das bedeutet, dass sie keine Zeit damit verschwenden, unmögliche Szenarien zu prüfen. Sie prüfen genau das, was passieren kann.
Entdeckung: Als sie dies an Standard-KI-Benchmarks testeten (wie das Erkennen von Ziffern oder Verkehrsschildern), stellten sie fest, dass viele KI-Modelle gegenüber 3D-Kamerabewegungen sehr zerbrechlich sind. Zum Beispiel könnte ein Modell, das zum Erkennen von Verkehrsschildern trainiert wurde, völlig versagen, wenn sich die Kamera nur leicht neigt, obwohl es alle alten „Rausch"-Tests besteht.

5. Realwelt-Test: Die Landebahn

Um zu zeigen, dass dies in einer realen sicherheitskritischen Situation funktioniert, testeten sie es an einem System, das einem Piloten mitteilen soll, ob eine Landebahn sichtbar ist.

Das Ergebnis: Das System erwies sich als sehr zerbrechlich. Bei kleinen Kamerabewegungen (wie einem leichten Stoß oder einer Kurve) konnte das System nicht garantieren, dass es die Landebahn korrekt identifizieren würde. Dies unterstreicht eine echte Verwundbarkeit, die behoben werden muss, bevor eine solche KI für den Einsatz in der Luftfahrt zertifiziert werden kann.

Zusammenfassung

Kurz gesagt sagt diese Arbeit: „Hören Sie auf zu raten, wie sich die Kamerabewegung auf die KI auswirkt. Wir haben eine präzise mathematische Karte dafür gefunden und haben eine „Geschwindigkeitsbegrenzung"-Regel verwendet, um genau zu beweisen, wie sehr eine KI durch bewegte Kameras verwirrt werden kann. Wir haben festgestellt, dass die aktuelle KI gegenüber Bewegungen viel zerbrechlicher ist als gedacht, und wir haben ein schnelleres, besseres Werkzeug entwickelt, um dies zu beweisen."

Diese Arbeit ist ein entscheidender Schritt auf dem Weg zur Zertifizierung von KI für sicherheitskritische Aufgaben wie das Fliegen von Drohnen, das Fahren von Autos oder das Landen von Flugzeugen, bei denen ein falscher Verdacht nicht nur ein Fehler ist – sondern eine Katastrophe.

Technische Zusammenfassung: Lipschitz-Optimierung für die formale Verifikation von Homografien

1. Problemstellung

Der Einsatz von tiefen neuronalen Netzen (DNNs) in sicherheitskritischen Bereichen wie dem autonomen Fahren, der Luft- und Raumfahrt sowie im Gesundheitswesen erfordert formale Robustheitsgarantien. Aktuelle Methoden zur formalen Verifikation konzentrieren sich hauptsächlich auf durch $\ell_p$ -Normen beschränkte Störungen (z. B. Rauschen, Kontraständerungen), die direkt im Pixelraum wirken. Diese Ansätze versagen jedoch darin, Störungen angemessen zu modellieren, die in der physischen 3D-Welt entstehen, wie etwa Kamerabewegungen, Änderungen des Blickwinkels oder Verschiebungen der Szenengeometrie.

Während $\ell_p$ -Kugeln die resultierenden Bilder physikalischer Störungen theoretisch umfassen können, überapproximieren sie die wahre Mannigfaltigkeit der gestörten Bilder. Dies führt zu losen, uninformative Schranken, die oft versagen, die Robustheit des Netzwerks nachzuweisen. Bestehende Methoden für 3D-Robustheit beschränken sich auf statistische Ansätze (schwächere Garantien), 2D-affine Transformationen (die keine perspektivischen Effekte modellieren können) oder komplexe Simulationen, die explizite 3D-Szenenmodelle erfordern. Es besteht eine kritische Lücke bei der formalen Verifikation projektiver geometrischer Transformationen, insbesondere Homografien, die die Ebene-zu-Ebene-Abbildung zwischen verschiedenen Ansichten einer ebenen Fläche unter 3D-Kamerabewegung beschreiben.

2. Methodik

Die Autoren schlagen einen Rahmen zur formalen Verifikation vor, der auf Robustheit gegen Störungen der 3D-Bewegung der aufnehmenden Kamera abzielt, speziell für Szenen mit vorwiegend ebenen Strukturen (z. B. Straßenmarkierungen, Verkehrszeichen, Bodenebenen).

2.1. Geschlossene Herleitung der Homografie

Die Methode beginnt mit der Etablierung einer geschlossenen Abbildung von Kamerapose-Störungen auf Pixelwerte.

Geometrische Modellierung: Unter Annahme eines Lochkamera-Modells und eines ebenen Szenenmerkmals (z. B. $z=0$ im Weltkoordinatensystem) leiten die Autoren die durch 6-DOF-Kamerapose-Störungen (Roll, Pitch, Gier und Translation) induzierte Homografiematrix $H(\kappa)$ her.
Parametrisierung: Die Homografie wird durch einen Vektor $\kappa$ parametrisiert, der die Abweichung der Pose relativ zu einer Referenzkamera darstellt. Für spezifische Szenarien (z. B. reine Gier-Rotation) leiten die Autoren explizite analytische Ausdrücke für $H(\kappa)$ und seine Inverse $H^{-1}(\kappa)$ her.
Pixelwert-Funktion: Der Wert eines transformierten Pixels $G(\kappa)$ wird berechnet, indem die transformierten Koordinaten über $T^{-1}(\kappa)$ zurück auf das Originalbild abgebildet und bilineare Interpolation angewendet wird. Dies ergibt eine nichtlineare Funktion $G(\kappa) = I \circ T^{-1}(\kappa)$ .

2.2. Stückweise-lineare (PWL) Approximation und Lipschitz-Optimierung

Um das Netzwerk zu verifizieren, muss die nichtlineare Funktion $G(\kappa)$ durch lineare Schranken überapproximiert werden, die durch den Verifizierer propagiert werden können.

Stückweise-lineare Schranken: Der Parameterraum $B$ wird in Teilbereiche unterteilt. Innerhalb jedes Teilbereichs wird die Funktion $G(\kappa)$ durch lineare Schranken ($LB$ und $UB$) angenähert, die aus Stichprobenpunkten abgeleitet werden, gemäß dem Ansatz von Batten et al. [7].
Lipschitz-Stetigkeit: Um sicherzustellen, dass die Schranken korrekt sind (d. h., sie enthalten die wahren Funktionswerte strikt), analysieren die Autoren die Lipschitz-Stetigkeit von $G(\kappa)$ . Sie leiten analytische obere Schranken für die Lipschitz-Konstante $L$ her, indem sie den Gradienten der inversen Transformation $T^{-1}(\kappa)$ berechnen.
Umgang mit Diskontinuitäten: Die Autoren adressieren die Nicht-Stetigkeit der inversen Homografie bei kritischen Winkeln (wo der Nenner gegen Null geht). Sie definieren den Differenzierbarkeitsbereich $Diff(B)$ und identifizieren Kandidatenstellen für maximale Gradienten (Grenzen und spezifische Arkustangens-Werte), um gültige Lipschitz-Konstanten zu berechnen.
Optimierung: Mithilfe der Lipschitz-Optimierung verfeinert der Algorithmus die Schranken iterativ. Er bewertet die Funktion an Stichprobenpunkten und nutzt die Lipschitz-Konstante, um das globale Maximum der Schrankenverletzung zu begrenzen. Wenn die Schrankenverletzung einen Schwellenwert $\epsilon$ überschreitet, wird der Teilbereich aufgeteilt, und der Prozess wiederholt sich bis zur Konvergenz.

2.3. Implementierung

Die Methode wird als Frontend implementiert, das lineare Schranken für jeden nachgelagerten Verifizierer generiert. Die Autoren passten den VENUS-Verifizierer an, um diese stückweise-linearen Schranken zu verarbeiten, und erweiterten dessen Schranken-Propagierungsrahmen, um Prä-Aktivierungs-Schranken aus linearen Eingangsbeschränkungen anstelle von festen Intervallen abzuleiten.

3. Hauptbeiträge

Formale Verifikation projektiver Transformationen: Die Arbeit leitet geschlossene Homografien her, die durch 6-DOF-Pose-Störungen induziert werden, und zeigt deren Kompatibilität mit stückweise-linearen Beschränkungen und Lipschitz-Optimierung auf. Dies ermöglicht nachweislich enge Schranken für Pixelwerte unter nicht-affinen (projektiven) Transformationen.
Effiziente Implementierung: Die Autoren stellen eine effiziente Implementierung bereit, die den bestehenden PWL-Algorithmus [7] verbessert. Verbesserungen umfassen Halbpixel-Korrekturen für exakte Gradienten, die Einbeziehung ausgelassener Parameterwerte in die Lipschitz-Kandidatenmenge, Dichotomie im Parameterraum und Parallelisierung auf Pixelebene.
Benchmarking und Fallstudie: Die Methode wird an VNN-COMP-Benchmarks (MNIST, CIFAR-10, GTSRB) und einem realen Klassifizierer für Startbahn-Sichtbarkeit evaluiert.

4. Ergebnisse

Leistungsverbesserungen: Im Vergleich zu einer Neuimplementierung des PWL-Algorithmus [7] erreicht die vorgeschlagene Methode eine Beschleunigung von bis zu 89 % in der Laufzeit und 7 % engere Schranken bei komplexen Pixelkurven. Bei kleinen Transformationen wurden Branch-and-Bound (BaB)-Iterationen um mehr als 71 % reduziert.
Entdeckung von Schwachstellen: Die Evaluation an VNN-COMP-Benchmarks zeigt, dass Netzwerke, die mit Standard-Datenaugmentierung (einschließlich $\ell_p$ -Norm-Angriffen) trainiert wurden, systematische Schwächen gegenüber 3D-geometrischen Störungen aufweisen. Beispielsweise zeigten GTSRB-Modelle (autonomes Fahren) 0 % zertifizierte Robustheit gegenüber 3D-Störungen (Roll, Pitch, Gier und Translation). Selbst MNIST- und CIFAR-Modelle wiesen eine signifikant geringere Robustheit gegenüber Pitch, Gier und Translation im Vergleich zu $\ell_p$ -Norm-Störungen auf.
Realwelt-Fallstudie: Auf einen auf dem LARD-Datensatz trainierten Klassifizierer für Startbahn-Sichtbarkeit angewendet, zertifizierte die Methode Robustheit für nur 16 % der Testbilder bei 10 cm-Translationen und 1 % bei 1°-Rotationen, was praktische Schwachstellen in sicherheitskritischen Wahrnehmungssystemen aufzeigt.
Sensitivitätsanalyse: Die Studie bestätigt, dass die zertifizierte Robustheit mit zunehmender Amplitude der Transformation (z. B. Gierwinkel) abnimmt, eine bekannte Herausforderung in der formalen Verifikation, die eine Aufteilung des Bereichs erfordert.

5. Bedeutung und Behauptungen

Die Arbeit behauptet, das erste Rahmenwerk zur formalen Verifikation projektiver geometrischer Transformationen vorzustellen, das nicht auf komplexe Simulationen, Surrogat-Netzwerke oder explizite Bildbildungsmodelle angewiesen ist. Durch die Nutzung der analytischen Handhabbarkeit von Homografien für ebene Szenen überbrücken die Autoren die Lücke zwischen der 2D-affinen Verifikation und der vollständigen 3D-Szenenmodellierung.

Die Bedeutung liegt in:

Regulatorische Compliance: Bereitstellung der mathematischen Garantien, die für die Zertifizierung von KI in sicherheitskritischen Industrien (Luftfahrt, autonome Fahrzeuge) erforderlich sind, wobei Kamerabewegung eine Hauptquelle der Unsicherheit darstellt.
Methodischer Fortschritt: Erweiterung der Lipschitz-Optimierung und PWL-Techniken, um nicht-affine, perspektivisch verzerrende Transformationen zu behandeln, die zuvor als analytisch nicht handhabbar für die formale Verifikation galten.
Praktische Einsicht: Demonstration, dass aktuelle State-of-the-Art-Netzwerke gegenüber realistischen 3D-Störungen spröde sind, was darauf hindeutet, dass Robustheitstraining oder -verifikation über $\ell_p$ -Norm-Beschränkungen hinausentwickelt werden müssen, um Variationen der physischen Welt zu adressieren.

Die Autoren bewahren einen bescheidenen Ton und räumen ein, dass große Transformationen Nichtlinearitäten verstärken und dass die Methode derzeit am besten für vorwiegend ebene Szenen mit begrenzter Parallaxe und Okklusion geeignet ist. Sie positionieren ihre Arbeit als prinzipiellen Mittelweg für die Verifikation einer Vielzahl von Anwendungsfällen in der Robotik und Computer Vision.