❇️ 👋🏽 ↗️ Berechnung des Massenschwerpunkts für O (1) mit integrierten Bildern 👾 👌🏽 👍🏻

Ein integriertes Bild ist ein Algorithmus, mit dem Sie die Summe der Werte, die in einer rechteckigen Teilmenge eines mehrdimensionalen Arrays enthalten sind, effizient berechnen können. Seine Idee geht auf das Studium mehrdimensionaler Wahrscheinlichkeitsverteilungsfunktionen zurück, und bis jetzt hat er eine erfolgreiche Anwendung in den Bereichen gefunden, in denen die Wahrscheinlichkeitstheorie direkt als Hauptwerkzeug verwendet wird. Zum Beispiel bei der Mustererkennung.

Heute werden wir einen merkwürdigen Fall betrachten, wie integrierte Bilder in einem radikal anderen Bereich angewendet werden können - der Computerphysik. Mal sehen, was passiert, wenn wir mit ihnen den Schwerpunkt des Pulsfeldes berechnen und welchen Nutzen sich aus dieser Symbiose ergeben kann.

In diesem Artikel werde ich erzählen:

Um welche Art von Aufgabe handelt es sich?
Lesen Sie mehr über integrierte Bilder.
N (-);
;
, , .

N

Eine rigorose Lösung für die Gravitationswechselwirkung eines Systems von N Körpern bezieht sich auf Algorithmen mit quadratischer Komplexität: Alle anderen Körper im System haben einen Gravitationseffekt auf jeden Körper ^[1] . Folglich, um die Kraft der Gravitations Wechselwirkung Notwendigkeit für jeden des N zu berechnen ² pair / 2.

Um zu veranschaulichen, wie zeitaufwändig eine strenge Lösung ist, können Sie versuchen, die Komplexität der Berechnung eines realen Systems mit der Leistung moderner Computer zu korrelieren.

Um die Gravitationskraft zwischen zwei Körpern im dreidimensionalen Raum zu berechnen, müssen Sie 20 Operationen mit einem Gleitkomma (FLOP) ausführen. Im Sonnensystem gibt es ungefähr 100 Körper, die größer als 200 Kilometer sind (einschließlich der Sonne, 9 Planeten, Zwergplaneten und Satelliten) ^[2]. Die ungefähre Anzahl von Asteroiden in der erdnahen Umlaufbahn beträgt etwa 20.000 ^[3] . Im Asteroidengürtel gibt es 1,1 bis 1,9 Millionen Körper, die größer als 1 km sind ^[4], und etwa eine Million ähnliche Asteroiden in den Jupiter-Gruppen „Trojaner“ ^[5] und „Griechisch“. Im Kuipergürtel befinden sich etwa 100 Millionen Objekte, die größer als 20 km sind ^[6] und etwa 2 Billionen mehr, in der Oort-Wolke ^[7] .

Die Rechenleistung, die erforderlich ist, um das letzte Gravitationsproblem strikt zu lösen, ist nur eine Größenordnung geringer als die Rechenleistung, die erforderlich ist, um die Arbeit des menschlichen Gehirns auf neuronaler Ebene zu simulieren (2,5 × 10 ²⁶ ) ^[8]. Aus diesem Grund wird die rigorose Lösung normalerweise durch eine ungefähre ersetzt.

Einer der am weitesten verbreiteten Algorithmen zur ungefähren Lösung des Gravitationsproblems - Tree Code - weist eine quasilineare Zeitkomplexität O (N * logN) auf ^[9] . Der Baumcode erstellt einen räumlichen Baum und berechnet für jeden Knoten in diesem Baum die Gesamtmasse und den Massenschwerpunkt aller Körper, die in ihn fallen. Darüber hinaus kann der Baumcode bei der Berechnung der auf jeden Körper einwirkenden Gravitationskräfte nicht den direkten Einfluss anderer Körper, sondern den Einfluss von Baumknoten berücksichtigen und je nach Entfernung immer größere Knoten auswählen, die Parameter einer immer zahlreicheren Teilmenge von Körpern enthalten.

Illustration aus Wikipedia. Auf dem Körper in der Mitte befinden sich die Massen von Knoten, die durch grüne Rechtecke angezeigt werden. Nur die Massen der nächstgelegenen Körper werden direkt berücksichtigt.

Schwerkraftproblem für das Impulsfeld

Das Impulsfeld ist ein diskretes Vektorfeld mv (p) , das jedem Punkt des betrachteten Raums p ein Masse-Geschwindigkeitspaar zuordnet . Das Pulsfeld kann für einen Raum beliebiger Dimension eingestellt werden. Ein Masse-Geschwindigkeitspaar charakterisiert den Impuls und stellt einen Vektor der Dimension R + 1 dar, wobei R die Dimension des Raums ist, für den das Pulsfeld gegeben ist. Zum Beispiel könnte dies für R = 2 der Vektor { v _x , v _y , m } sein.

Es ist erwähnenswert, dass die mathematisch traditionelle Version der Beschreibung dieses Systems eine Kombination aus einem Vektorgeschwindigkeitsfeld und einem skalaren Massenfeld ist. In diesem Fall erlauben wir uns die Freiheit, Geschwindigkeit und Masse in einem Vektor zu kombinieren, da wir nicht vorgeben, mathematisch zu sein.

Ein kleiner Teil des Vektorfeldes der Impulse: Die Massen werden durch Farbe angezeigt, die Richtungen durch Pfeile. Das

Vektorfeld von Impulsen mit einer Größe von 729 × 729 Elementen. Links sind die Massen. Rechts sind Impulse. Die Impulse in dieser Abbildung sind im HSV-Format farbcodiert (Farbton ist die Richtung des Impulses, und Value zeigt linear die Reihenfolge seines Absolutwerts an, sodass die am wenigsten unterscheidbaren (Wert = 0,05) Impulse in der Größenordnung von 10 bis ⁷ und die hellsten Impulse (Wert = 1) liegen , 0) liegen in der Größenordnung von 10 ³ und höher).

Ähnlich wie diese werden in der Astrophysik häufig Gittermethoden zur Beschreibung physikalischer Systeme eingesetzt, um die Entwicklung von Gaswolken, die Bildung von Sternen und Galaxien zu simulieren. Dazu gehören die SAMR-Methode ^[10] oder das Gittermodell der Hydrodynamik ^[11] .

Wie im Fall des Gravitationsproblems von N Körpern muss bei der Entwicklung eines diskreten Feldes der Gravitationseinfluss aller Massen, aus denen dieses Feld besteht, auf jedes seiner diskreten Elemente berücksichtigt werden. Es ist zu beachten, dass die Komplexität des Problems indirekt von der Dimension des Raums R abhängt : Beispielsweise beträgt für ein Feld in einer Ebene, die aus 1000 × 1000 Elementen besteht, die Gesamtzahl N 10 ⁶Elemente und ein Feld gleicher Größe im dreidimensionalen Raum enthält bereits 10 ⁹ Elemente.

Dennoch gibt es eine Reihe von Tricks, die es ermöglichen, das Gravitationsproblem für das Impulsfeld näherungsweise zu lösen. Die Multigrid-Methode verwendet eine hierarchische Diskretisierung, die mehrere Gitter unterschiedlicher Größe unterstützt ^[12] . Bei der Multipol-Erweiterung werden nahe beieinander liegende Quellengruppen als ein Objekt behandelt ^[13] . Multigrid hat eine quasilineare Rechenkomplexität und eine logarithmische Speicherkomplexität. Eine der Multipol-Erweiterungsoptionen - FMM - demonstriert die lineare Rechenkomplexität im Austausch für eine verringerte Rechengenauigkeit ^[14] .

Im Folgenden betrachten wir eine andere Methode, mit der wir das Gravitationsproblem für ein diskretes Impulsfeld in quasilinearer Zeit lösen können und deren Speicher linear komplex ist.

Integriertes Bild

Das Integralbild ermöglicht die Berechnung der konstanten Zeit der Summe der Elemente des Originalbildes in einem beliebigen rechteckigen Bereich ^[15] . In der Computergrafik wurden ursprünglich integrierte Bilder als Alternative zu Mipmapping und anisotroper Filterung vorgeschlagen ^[16] . Darüber hinaus werden sie erfolgreich für die digitale Bildverarbeitung und in Mustererkennungstechniken eingesetzt.

Ein integriertes Bild ist eines der offensichtlichsten Beispiele für einen Kompromiss zwischen Rechenkomplexität und Speicherkomplexität. Ein "naiver" Algorithmus zum Berechnen der Summe von Bildelementen hat eine Zeitkomplexität von O (M * N) und eine Speicherkomplexität von O (1). Das integrierte Bild ermöglicht es Ihnen, dieselben Berechnungen in O (1) -Zeit durchzuführen und weist eine O (M * N) -Speicherkomplexität auf.

Verwendung des integrierten Bildes zur Berechnung der Summe der Elemente in einem bestimmten Bereich

Der Algorithmus zur Berechnung des Integralbildes ist sehr einfach, zeichnet sich durch lineare Rechenkomplexität aus und lässt sich unter GPGPU leicht parallelisieren ^[17] . Es wird wie ein Zwei-Pass-Gauß-Filter implementiert ^[18] : Im ersten Durchgang werden die Teilsummen für die Zeilen berücksichtigt, im zweiten werden diese Teilsummen in Spalten akkumuliert.

Berechnung des integrierten Bildes in zwei Durchgängen. Links ist das Originalbild. In der Mitte befinden sich die Teilbeträge für die Linien. Rechts ist das endgültige integrierte Bild.

Links ist ein Bild mit Massen von Elementen. Rechts ist das integrale Bild. Die Bilder links und rechts verwenden unterschiedliche logarithmische Skalen.

Eine ungefähre Lösung des Gravitationsproblems unter Verwendung eines integrierten Bildes

Da ein integrales Bild der Massen zur Verfügung steht, ist es nicht schwierig, die für den Baumcode und die Multipol-Erweiterung charakteristische Technik daran anzupassen. Also für jedes Element des diskreten Feldes:

Wir berücksichtigen direkt den Einfluss der Massen nur der benachbarten acht Elemente;
Wir berücksichtigen den Einfluss von acht benachbarten Regionen, die aus neun Elementen (3 × 3) bestehen, indem wir die Summe ihrer Massen anhand eines integrierten Bildes berechnen.
Bei jedem nachfolgenden Schritt erhöhen wir die Größe des Bereichs um das Dreifache (9 × 9, 27 × 27, 81 × 81 usw.), bis dieser die Größe des gesamten Vektorfelds überschreitet.

Eine ungefähre Berechnung der Kräfte, die auf ein Element des Vektorfeldes von Impulsen unter Verwendung eines Integralbildes von Massen wirken

Die Komplexität der Näherungslösung des Gravitationsproblems für ein Feld von Impulsen unter Verwendung eines Integralbildes wächst quasilinear wie O (N * 8 * log3 (sqrt (N))) für R = 2 und wie O (N * 26 * log3 (cbrt (N))) für R = 3.

In dieser Form hat diese Lösung jedoch den gleichen Nachteil wie die Multigrid-Technik, nämlich die wahrnehmbare diskrete "Steifheit" der niederfrequenten Komponenten der Schwerkraftfunktion. Der einfachste Weg, dieses Problem zu demonstrieren, ist eindeutig.

Die Kräfte in dieser Abbildung sind im HSV-Format farbcodiert (Farbton ist die Richtung der Kraft, Wert zeigt die Reihenfolge ihres Absolutwerts linear so an, dass die am wenigsten unterscheidbaren Kräfte (Wert = 0,05) in der Größenordnung von 10 bis ⁷ und die hellsten Kräfte (Wert = 1, 0) liegen in der Größenordnung von 10 ³ und höher).

In der obigen Abbildung ist der Effekt der "Steifheit" der niederfrequenten Komponenten der Schwerkraftfunktion mit bloßem Auge erkennbar. Wenn jedoch in „Multigrid“ diese „Steifheit“ aufgrund einer Abnahme der Abtastfrequenz auftritt, ist dies im integrierten Bild auf den Mangel an Informationen über die Art der räumlichen Verteilung der Massen zurückzuführen. Tatsache ist, dass ein Algorithmus, der Kräfte unter Verwendung eines integrierten Bildes approximiert, berücksichtigt, dass der Schwerpunkt mit dem Mittelpunkt der Region zusammenfällt.

Das Zentrum der Abbildung zeigt das Massenextremum mit einer relativ gleichmäßigen Massenverteilung im Rest des Feldes. Das

Massenextremum fällt in jeden der vier rechteckigen Bereiche. Offensichtlich sollte die Position des Massenschwerpunkts jeder Region ungefähr mit dem durch Weiß angezeigten Element übereinstimmen, dessen Masse drei Größenordnungen größer ist als die Masse der meisten durch Gelb angezeigten Elemente der Region. Bei den Berechnungen der niederfrequenten Komponenten der Schwerkraftfunktion für diese Regionen wird jedoch angenommen, dass ihre Massenschwerpunkte mit den Zentren der durch Kreise angegebenen Regionen übereinstimmen.

Dieses Problem kann gelöst werden, indem zusätzliche Informationen in das integrierte Bild eingefügt werden, wodurch nicht nur die Summe der Massen in einer bestimmten Region, sondern auch die Koordinaten des Massenschwerpunkts berechnet werden können.

Versuchen wir zunächst, uns ein Bild vorzustellen, dessen jedes Element seine eigenen Koordinaten enthält. Das entsprechende Integralbild enthält die Summe der Koordinaten. Daher ist die Summe eines beliebigen Bereichs dieses integrierten Bildes, geteilt durch die Gesamtzahl der Elemente in diesem Bereich, gleich den Koordinaten des Zentrums dieses Bereichs.

Integrales Koordinatenbild

Nehmen wir zum Beispiel den Bereich in der unteren linken Ecke mit den Koordinaten {3; 1} und oben rechts mit den Koordinaten {7; 5}. Die Summe der Koordinaten dieser Region {168; 120} - {18; 45} - {28; 0} + {3; 0} ist {125; 75} beträgt die Gesamtzahl der Elemente 25, daher sind die Koordinaten seines Zentrums {5; 3}.

Alles, was noch getan werden muss, ist, diesen speziellen Fall zu verallgemeinern, in dem wir davon ausgehen, dass alle Elemente des Bildes den gleichen Gewichtskoeffizienten gleich Eins haben. Um unterschiedliche Gewichte zu berücksichtigen, multiplizieren wir die Koordinaten der Elemente mit ihnen. Und wir erhalten die gewichteten Koordinaten des Zentrums der Region, wenn wir die Summe der gewichteten Koordinaten durch die Summe der Gewichtungsfaktoren dividieren.

Integriertes Bild gewichteter Koordinaten. Größere Schrift zeigt Gewichte an

Betrachten Sie den Bereich in der unteren linken Ecke mit den Koordinaten {2; 1} und oben rechts mit den Koordinaten {5; 4}. Die Summe der Gewichtungskoeffizienten dieses Bereichs 4,8 - 1,0 - 0,6 + 0,2 beträgt 3,4, und die Summe seiner gewichteten Koordinaten {11,1; 13,2} - {0,5; 2,0} - {1,5; 0,0} + {0,1; 0,0} ist gleich {9,2; 11.2}. Somit sind die gewichteten Koordinaten des Zentrums dieser Region {2,7; 3.3}.

Um sicherzustellen, dass diese Schaltung wirklich funktioniert, können Sie dies visuell tun, indem Sie das integrierte Bild mit gewichteten Koordinaten mithilfe der Entfernungstransformation in ein Entfernungsfeld konvertieren ^[19] .

Konvertieren eines integrierten Bildes mit gewichteten Koordinaten in ein Distanzfeld. Links ist ein Bild der Massen. Das folgende Bild zeigt den Abstand zum Massenschwerpunkt für einen Bereich von 3 × 3 Elementen. Als nächstes folgt der Abstand zu den Massenschwerpunkten für Regionen mit Größen von 9 × 9 und 27 × 27 Elementen. Die Abstandswerte in dieser Abbildung sind auf die Größe des für die Abtastung verwendeten Bereichs normiert.

Konvertiert ein integriertes Bild mit gewichteten Koordinaten in ein gerichtetes Distanzfeld. Die Richtung und Entfernung sind im HSV-Format farbcodiert, wobei Farbton die Richtung und Wert die normalisierte Entfernung ist. Die Abstandswerte in dieser Abbildung sind auf die Größe des für die Abtastung verwendeten Bereichs normiert.

Fassen Sie alle oben genannten Punkte zusammen:

, , ( , R = 3) ― , , .
.
O(1).
O(M*N).

. ― . ― .

Zeit, auf eines der Hauptmerkmale integrierter Bilder zu achten, das den Anwendungsbereich immer noch einschränkt, nämlich den Ressourcenverbrauch und die numerische Stabilität. Abhängig vom Wertebereich, den das Originalbild enthält, ist möglicherweise ein längerer Datentyp für das Integralbild erforderlich. Beispielsweise wird bei der Berechnung der Standardabweichungen zusätzlich zum Originalbild (Wertebereich 0..255) ein Bild verwendet, das Quadrate der entsprechenden Werte (Wertebereich 0..65535) enthält. In diesem Fall reicht die Genauigkeit nicht aus, um großformatige integrierte Bilder mit 32 Bit zu berechnen ^[20] .

Eine ähnliche Situation wird bei integrierten Bildern mit gewichteten Koordinaten beobachtet. An sich wächst der Wert der Summe der Koordinaten, die im integrierten Bild gespeichert werden müssen, abhängig von der Bildgröße N: quadratisch für den eindimensionalen Fall 0 + 1 + 2 + ... + N - 1 = (N - 1) * N / 2 und kubisch für zweidimensionales N * (N - 1) * N / 2. Um beispielsweise die Summe einer Ganzzahlkoordinate für ein Bild mit einer Größe von 2048 × 2048 (gleich 4292870144) zu speichern, reicht eine vorzeichenlose 32-Bit-Ganzzahl (deren Maximalwert 4294967295 beträgt) kaum aus. Bei der Berechnung größerer integrierter Bilder tritt ein Überlauf auf.

Die Verwendung von 32-Bit-Gleitkommazahlen in integrierten Bildern verzögert das Problem des Überlaufs um eine astronomische Entfernung (10 ³⁸ - 10 ¹⁰⁾), gleichzeitig wird jedoch die Genauigkeit von Berechnungen mit gewichteten Koordinaten aufgrund des während der Summierung akkumulierten Kürzungsfehlers erheblich verringert ^[21] .

Der absolute Wert des Fehlers bei der Berechnung des gewichteten Massenschwerpunkts einer Region mit einer Größe von 4 × 4 Elementen. Das integrierte Bild enthält Zahlen mit einfacher Genauigkeit (32 Bit).

Der absolute Wert des Fehlers bei der Berechnung des gewichteten Massenschwerpunkts einer Region mit einer Größe von 32 × 32 Elementen. Das integrierte Bild enthält Zahlen mit einfacher Genauigkeit (32 Bit).

Der größte absolute Wert wird durch die Berechnung des gewichteten Massenschwerpunkts für kleine Regionen erreicht. Eine Vergrößerung der Region um zwei Größenordnungen führt zu einer Verkleinerung des absoluten Rechenfehlers um vier Größenordnungen. In diesem Fall wurde keine Abhängigkeit des Berechnungsfehlers vom Wertebereich der Gewichtungskoeffizienten (die zur Berechnung der gewichteten Koordinaten der Elemente verwendet werden) gefunden.

Eine Vergrößerung des Gewichtsbereichs hat keinen Einfluss auf den Absolutwert des Fehlers bei der Berechnung des gewichteten Massenschwerpunkts. Die Grafik zeigt die Fehler für den „schlechtesten“ Bereich (in der oberen rechten Ecke des integrierten Bildes). Die Größe des integrierten Bildes beträgt 256 × 256 Elemente.

Der Absolutwert des Fehlers bei der Berechnung des gewichteten Massenschwerpunkts nimmt mit zunehmender Größe des Bereichs ab. Die Grafik zeigt die Fehler für den „schlechtesten“ Bereich (in der oberen rechten Ecke des integrierten Bildes).

Basierend auf der oben beschriebenen Analyse können wir schließen, dass die Verwendung von Zahlen mit einfacher Genauigkeit zur Berechnung gewichteter Massenschwerpunkte unter Verwendung integrierter Bilder nur für Bilder mit einer Größe von etwa 512 × 512 Elementen praktisch sinnvoll ist. Mit einer weiteren Vergrößerung wird die Größe des Fehlers mit der Größe des Bildelements vergleichbar. Und obwohl dieser Fehler mit zunehmender Größe der Region abnimmt, haben Regionen kleiner Größe den größten Einfluss auf das Endergebnis - die Größe der Schwerkraft -, daher sollten nur die entsprechenden Fehler berücksichtigt werden.

Bei größeren Bildern können Sie gewichtete Koordinaten mit doppelter Genauigkeit verwenden oder eine andere Diskretisierungsebene hinzufügen: Teilen Sie das Originalbild in mehrere Teile auf und lesen Sie die integrierten Bilder für jeden dieser Teile separat. Unter dem Gesichtspunkt der rechnerischen Komplexität ändert sich die Komplexität des Summenberechnungsalgorithmus nicht, wenn mehr als ein Integralbild verwendet wird, um die Summe der Elemente einer Region zu berechnen, aber dieses "mehr als eins" eine Konstante ist.

Fazit

Das obige Beispiel der Verwendung eines integrierten Bildes kann wahrscheinlich angepasst werden, um einen optimalen Algorithmus O (1) für die Abtastung nach Wichtigkeit (Wichtigkeitsabtastung) zu entwickeln. Bestehende - und aus Sicht der GPU äußerst ressourcenintensive - Algorithmen haben eine lineare Komplexität O (N) und finden Anwendung in modernen Methoden der globalen Beleuchtung ^{[22, 23]} .

Im Allgemeinen sind integrierte Bilder meiner Meinung nach einer der am meisten unterschätzten Algorithmen. Sie können gleichzeitig eine hervorragende Alternative zu Mipmapping und anisotroper Filterung sein, und wenn man berücksichtigt, wie letztere auf der GPU implementiert sind ^{[24, 25]} , ist es durchaus möglich, dass sie bereits eine effektivere Maßnahme sind.

Verweise

Liste anzeigen

Berechnung des Massenschwerpunkts für O (1) mit integrierten Bildern

N

Schwerkraftproblem für das Impulsfeld

Integriertes Bild

Eine ungefähre Lösung des Gravitationsproblems unter Verwendung eines integrierten Bildes

Fazit

Verweise

More articles: