Speed up möglich? [gelöst]
-
knivil schrieb:
Es gab da mal einen Thread, da wurde davon abgeraten, durch Studieren des Sourcecodes irgendwelche Einsichten zu gewinnen. Vielleicht beschreibst du mal in Worten, welches Problem du hast, wie deine Datenstruktur aufgebaut ist (fuer Quadtrees gibt es viele Moeglichkeiten) und welches Problem du loesen willst.
Ok, es handelt sich beim Ganzen ums Segmentieren von Videosequenzen. ( 'Vorgängerpost': http://www.c-plusplus.net/forum/viewtopic-var-t-is-244798-and-start-is-0-and-postdays-is-0-and-postorder-is-asc-and-highlight-is-.html ) Da dabei sehr viele Daten anfallen möchte ich die einzelnen Frames als Quadtrees darstellen ( ähnliche Werte nach LoG Filterung zu einer Node zusammenfassen )
Das ganze funktioniert soweit gut - halt nur zu langsam.knivil schrieb:
ein Nachbar ist von der Anderen erfolgt ...
Warum soll ein Konten ueberhaupt etwas ueber seine Nachbarn wissen wollen? Warum sollen die gefunden werden ...
.. sorry für mein 'Deutsch'
Die Nachbarschaft wird benötigt für die korrekte Segmentierung. Diese erfolgt mittels einem GraphCut ( http://en.wikipedia.org/wiki/Graph_cuts_in_computer_vision )knivil schrieb:
for (it = tmp->begin(); it != tmp->end(); ++it)Was ist denn tmp und was ist drin ... da geht es doch schon los ...
tmp ist eine Kopie des Vectors mit allen Nodes. Diese Kopie wurde angelegt, dass die Nodes die nicht mehr in Frage kommen als Nachbarn, gelöscht werden können.
knivil schrieb:
Auch hat eine QuadtreeNode fuer gewoehnlich Zeiger auf ihre 4 Kindknoten und einen Zeiger auf den Eltern(Vater/Mutter)-Knoten. Dabei brauche ich dann nur absteigend/aufsteigend iterieren, um einen Nachbarn zu finden. Das skaliert mit der Tiefe des Baumes, also O( log n) mit n als Gesamtzahl der Knoten. Wenn das fuer alle Blattknoten gemacht wird, so ist es sogar noch schneller, da oft nur einmal aufsteigend zum Elternknoten gewechselt werden muss und dann einmal absteigend zum benachbarten Kindknoten.
Ich versuchte die Nodes meines Quadtrees möglichst klein zu halten, da mein Antrieb einen Quadtree zu verwenden die 'Out of Memory' Meldung ist. ( Bei 4GB Ram ). Aus diesem Grund weiss eine Node nichts über seine Kinder oder die Mutter ( diese wird nach dem splitten gleich gelöscht). Aus diesem Grund weiss eine Node auch nicht gleich selbst wer seine Nachbarn sind, sondern dies wird im Nachhinein erst berechnet.
Hmm, aber hinsichtlich der langwierigen Suche nach den Nachbarn wäre es vielleicht doch besser den vollständigen Baum zu belassen und dann an diesem direkt die Nachbarn zu ermitteln.
knivil schrieb:
Ich habe Quadtrees fuer die Beschleunigung von Kollisionserkennung implementiert. Fuer was moechtest du Quadtrees verwenden?
Hört sich interessant an.
-
Ich versuchte die Nodes meines Quadtrees möglichst klein zu halten, da mein Antrieb einen Quadtree zu verwenden die 'Out of Memory' Meldung ist.
Die groesse der Nodes ist natuerlich im Vergleich zur Anzahl unbedeutend (theoretisch). Die wird von dem O in O(4^n) geschluckt. Eine feste Maximaltiefe ist vielleicht von Noeten. Bei n (Tiefe) von 7 mag das schon 500 MByte sein (ka. muesste ich bei mir erst nachsehen). Auch solltest du wissen, dass man normalerweise Speicherplatz gegen Rechengeschwindigkeit eintauscht. Bei deinem konkreten Problem kann ich dir leider nicht helfen, da es komplett neu fuer mich ist.
Aber ein paar generelle Tips: Nicht alle Bereiche muessen vollstaendig ... ka. wie ich ausdruecken soll ... traversiert sein. D.h. ein grosser Bereich der z.B. schwarz ist, braucht keine feinere Segmentierung, so das der Bereich von einer grossen Node geringer Tiefe abgedeckt. Damit spart man z.B. alle Folgenodes, die ja exponentiell anwachsen. Somit hat man einen "patiellen" Quadtree, wo nicht alle Aste gleich tief reichen. Auch kannst du sie dynamisch gestallten. D.h. falls du etwas genauer als eine Node sein musst, dann kannst du dynamisch den "partiellen" Baum an einer Node expandieren oder aber im umgekehrten Fall ... kontrahieren/Aeste abschneiden.
Ich fand die einfache Traversierung bei gleichzeitiger Zusammenhangsinformation + Performancegewinn gerade entscheidend und wuerde keines dieser aufgeben wollen. Dann sind naehmlich andere Datenstrukturen vielleicht besser geeignet.
Zu deinem Speicherproblem ... bei 4GByte kannst du vielleicht etwas herausholen, wenn dein Speicher nicht zusammenhaengend sein muss. Bei Baeumen muss er das naemlich nicht (zumindestens habe ich das bei einem Quadtree noch nie gebraucht). Wenn du z.B. einen std::vector vergroesserst, dann kann doppelt soviel neuer Speicher angefordert werden, wie aktuell belegt ist. Bsp: bei 1Gbyte aktuell + 2Gbyte neu = 3Gbyte werden fuer Zwischendurch benoetigt. Hinzu kommt, dass die 2 GByte zusammenhaengend sein muessen. Hast du z.B. 5Gbyte, so kann dir das Programm genauso um die Ohren fliegen, wenn der Speicher (durch andere Programme) fragmentiert wurde.
Siehe http://www.sgi.com/tech/stl/Vector.html unter Notes Punkt 3.
-
knivil schrieb:
Die groesse der Nodes ist natuerlich im Vergleich zur Anzahl unbedeutend (theoretisch).
.. sorry, wie meinst du das jetzt? Angenommen meine Node Klasse hätte eine grösse von 40Bytes. Angenommen ich hätte die genannten 200'000 Nodes ( anstelle von 700x800 pixel = 480'000 pixel ) pro Frame und 250 Frames. Ergibt einen benötigten Speicher von 1907MB Ram! Wenn ich da meine Nodes Grösse auf 12 Bytes halten kann brauche ich 'nur' 572MB Ram. Wie ich das sehe spielt das nicht nur theoretisch eine Rolle.
knivil schrieb:
Die wird von dem O in O(4^n) geschluckt. Eine feste Maximaltiefe ist vielleicht von Noeten. Bei n (Tiefe) von 7 mag das schon 500 MByte sein (ka. muesste ich bei mir erst nachsehen). Auch solltest du wissen, dass man normalerweise Speicherplatz gegen Rechengeschwindigkeit eintauscht. Bei deinem konkreten Problem kann ich dir leider nicht helfen, da es komplett neu fuer mich ist.
Aber ein paar generelle Tips: Nicht alle Bereiche muessen vollstaendig ... ka. wie ich ausdruecken soll ... traversiert sein. D.h. ein grosser Bereich der z.B. schwarz ist, braucht keine feinere Segmentierung, so das der Bereich von einer grossen Node geringer Tiefe abgedeckt. Damit spart man z.B. alle Folgenodes, die ja exponentiell anwachsen. Somit hat man einen "patiellen" Quadtree, wo nicht alle Aste gleich tief reichen. Auch kannst du sie dynamisch gestallten. D.h. falls du etwas genauer als eine Node sein musst, dann kannst du dynamisch den "partiellen" Baum an einer Node expandieren oder aber im umgekehrten Fall ... kontrahieren/Aeste abschneiden.
Danke für die Tips. Ja, das hab ich schon so gemacht. Jedes Frame besteht aus sozusagen 'imaginären Pixel' ( = final leafs / nodes ) wobei diese unterschiedliche Grössen haben können. Also ein 'Multiresolution' Bild. Dabei werden die Nodes nur dort expandiert wo 'interessante Gebiete' sind.
Ich fand die einfache Traversierung bei gleichzeitiger Zusammenhangsinformation + Performancegewinn gerade entscheidend und wuerde keines dieser aufgeben wollen. Dann sind naehmlich andere Datenstrukturen vielleicht besser geeignet.
knivil schrieb:
Zu deinem Speicherproblem ... bei 4GByte kannst du vielleicht etwas herausholen, wenn dein Speicher nicht zusammenhaengend sein muss. Bei Baeumen muss er das naemlich nicht (zumindestens habe ich das bei einem Quadtree noch nie gebraucht). Wenn du z.B. einen std::vector vergroesserst, dann kann doppelt soviel neuer Speicher angefordert werden, wie aktuell belegt ist. Bsp: bei 1Gbyte aktuell + 2Gbyte neu = 3Gbyte werden fuer Zwischendurch benoetigt. Hinzu kommt, dass die 2 GByte zusammenhaengend sein muessen. Hast du z.B. 5Gbyte, so kann dir das Programm genauso um die Ohren fliegen, wenn der Speicher (durch andere Programme) fragmentiert wurde.
Meines Wissens muss der von mir belegte Speicher auch nicht zusammenhängend sein
Wie kann ich das bewerkstelligen?
-
Wie ich das sehe spielt das nicht nur theoretisch eine Rolle.
Deswegen habe ich es auch in Klammern gesetzt.
Wie kann ich das bewerkstelligen?
Ich weiss nicht wie deine zugrundeliegende Datenstruktur aussieht, aber
(*it)->getPosInVector();liess einige Vermutungen bzgl. std::vector zu. Ich kann ja ma alten Sourcecode ausgraben, wird aber erst morgen.
12 Bytes
Ich rede von 5 Zeigern a la 4Byte -> 20 Byte mehr. Hmm ... macht vielelicht schon was aus.
-
knivil schrieb:
Wie ich das sehe spielt das nicht nur theoretisch eine Rolle.
Deswegen habe ich es auch in Klammern gesetzt.
ok
knivil schrieb:
Wie kann ich das bewerkstelligen?
Ich weiss nicht wie deine zugrundeliegende Datenstruktur aussieht, aber
(*it)->getPosInVector();liess einige Vermutungen bzgl. std::vector zu. Ich kann ja ma alten Sourcecode ausgraben, wird aber erst morgen.
Wäre nett. Und ja, ich verwende std::vector
knivil schrieb:
12 Bytes
Ich rede von 5 Zeigern a la 4Byte -> 20 Byte mehr. Hmm ... macht vielelicht schon was aus.
Würde das Ganze fast verdreifachen.. also ja. Macht schon was aus
-
Irgendwo gabs mal hier nen thread zu Iteratoren und geschwindigkeit, da wurde erwähnt das man unter Windows zumindest da noch was drehen kann, wenn man bestimmte defines setzt.
Auch solltest du dich fragen ob std::vector der richtige Container ist, du hast ja z.b. viele Löschoperationen etc.
-
phlox81 schrieb:
Irgendwo gabs mal hier nen thread zu Iteratoren und geschwindigkeit, da wurde erwähnt das man unter Windows zumindest da noch was drehen kann, wenn man bestimmte defines setzt.
Leider ( ... naja, eigentlich zum Glück
) bin ich nicht unter Windows.phlox81 schrieb:
Auch solltest du dich fragen ob std::vector der richtige Container ist, du hast ja z.b. viele Löschoperationen etc.
Vielen Dank für den Link. Genau sowas habe ich vermisst! Sehr gut.
-
Sorry, mir ist die Problemstellung immer noch nicht ganz klar. Du hast ein Pixelbild und möchtest nun ähnlichfarbige Bereiche segmentieren. Wenn ich das richtig verstehe möchtest Du folgendes tun:
- irgendwelche farblich ähnliche Bereiche zusammenfassen zu größeren Blöcken
- einen Graph bauen, der diese größeren Blöcke als Knoten enthält und eine Kante zwischen Blöcken B1,B2, wenn diese benachbart sind.
Stimmt das so weit? Dann ist mir noch nicht klar welche Formanforderungen Du an die Bereiche aus 1) stellst.
Außerdem ist mir unklar (kann aber auch dran liegen, dass ich das Problem nicht verstanden habe), wie ein Quad-Tree dabei helfen soll. Nach Bauchgefühl würde ich derzeit eher auf Union-Find als geeignete Datenstruktur tippen.
edit: und wie Du damit genau Speicher sparst ist mir auch unklar. Selbst wenn Du den kompletten Quadtree im Speicher behältst (statt nur der Leafs) ist doch der Speicheraufwand nur unwesentlich größer -- selbst wenn jeder Knoten nur 2 Kinder hätte statt 4 wäre der Overhead nur Faktor 2.
-
Jester schrieb:
Sorry, mir ist die Problemstellung immer noch nicht ganz klar. Du hast ein Pixelbild und möchtest nun ähnlichfarbige Bereiche segmentieren. Wenn ich das richtig verstehe möchtest Du folgendes tun:
- irgendwelche farblich ähnliche Bereiche zusammenfassen zu größeren Blöcken
- einen Graph bauen, der diese größeren Blöcke als Knoten enthält und eine Kante zwischen Blöcken B1,B2, wenn diese benachbart sind.
Stimmt das so weit? Dann ist mir noch nicht klar welche Formanforderungen Du an die Bereiche aus 1) stellst.
Ja, stimmt in etwa. Die eigentlich erzielte Formatierung ist allerdings nicht nur auf den Farbinformationen basierend.
zu 1)
Nach Filterung mittels LoG Filter ähnliche Bereiche aus dem erhaltenen Kantenbild zusammenfassen. Klappt wunderbar. Aufgrund diesen Daten wird der Quadtree aufgebaut. Die geschieht genügend schnell. Das Problem kommt beim nächsten Schritt, dem aufbauen der Nachbarschaft. Dies beansprucht zu viel Zeit mit der oben angegebenen Variante.zu 2)
.. ganz genau.Jester schrieb:
Außerdem ist mir unklar (kann aber auch dran liegen, dass ich das Problem nicht verstanden habe), wie ein Quad-Tree dabei helfen soll. Nach Bauchgefühl würde ich derzeit eher auf Union-Find als geeignete Datenstruktur tippen.
Durch den Quadtree kann ich die Anzahl Knoten im Graphen drastisch reduzieren und somit viel des knappen RAM Speichers sparen.
Ohne Quadtree würde jedes Pixel als 'eigenständiger' Knoten in den Graphen aufgenommen .
-
Du solltest die Nachbarschaft entweder direkt beim Aufbau des Quadtrees mitmachen (ist aber vermutlich nicht ganz trivial) oder den Quadtree weglassen, ich glaube nicht, dass der wirklich viel hilft. Mir scheint das wie gesagt eher ein Union-Find Problem zu sein.
Ich würde pro Frame folgendes Vorgehen vorschlagen:
a) konstruiere einen Graphen, der einen Knoten pro Pixel enthält, sowie Kanten zu seinen Nachbarn (keine Bange, der ist zwar groß aber wir schmeißen ihn nachher weg)b) Setze eine Union-Find-Datenstruktur (google danach, falls Du es nicht kennst, boost hat eine fertige Implementation) auf, die alle Pixel enthält
c) Verwende die Union-Find-DS um benachabarte Knoten mit hoher Ähnlichkeit zu verschmelzen (also: durchlaufe alle Pixel, schau für jeden den Nachbarn an und verschmelze mittels Union-Find, wenn sie ähnlich sind).
d) Gehe nochmal durch alle Knoten und lege einen frischen Graph an, der bekommt für jede Menge in der Union-Find-DS (also für jeden Bereich) einen Knoten, die Kanten bekommst Du ebenfalls mit der Union-Find-DS indem Du einmal alle Nachbarn Deines Bereichs abklapperst (also alle Pixel des Bereichs einmal anschaust).
Das ganze läuft bei geeigneter Implementierung fast in Linearzeit, nämlich O(n*alpha(n)), dabei ist alpha die inverse Ackermann-Funktion -- die wächst so langsam, dass sie für realistische Eingabegrößen Werte <= 4 annimmt. Dabei ist n die Anzahl der Pixel in Deinem Bild. Rein asymptotisch gesehen kansnt Du also kaum schneller werden, schließlich mußt Du jeden Pixel schon mal irgendwann anschauen.
-
Moeglichkeiten gibt es viele, hier aber meine noch schuldig gebliebene Quadtree-Implementation: Quadtree. Interessant fuer dich sind nur die Funktionen QuadTree::create( const AARect& rect, unsigned int depth ) und extendNode. Bei crate wird einfach ueber extendNode der Graph aufgebaut, bis eine bestimmte Tiefe erreicht wurde. Aber du kannst ja das an ein Praedikat binden. Den Rest wie IQuadTreeElement kannst du getrost ignorieren, von dieser Klasse mussten alle Elemente erben, die sich von einem Quadtree verwalten lassen wollten. Und nearElements suchte nur nach Elementen im Quadtree, nicht nach Nodes in der Nachbarschaft. Auch werden alle Nodes in einer Liste von Zeigern vorgehalten, so dass fuer die Bereinigung (delete) nicht die Nodes recursiv traversiert werden muessen (ist meine allgemeine Strategie bei Graphen).
-
Hei,
Nochmals vielen Dank für eure Antworten. Ich hatte mich nach Abwägen aller Möglichkeiten dazu entschieden, den Quadtree umzubauen, dass dieser vollständig erhalten bleibt ( also auch die internen Nodes ).
Der Baum ist nun fertig gebaut .. und siehe da: Aufsetzen der Nachbarschaft ist sehr(!) viel schneller!
Das ganze war allerdings nicht ganz so trivial. Jetzt habe ich aber eine schöne, kurze, rekursive und v.a. schnelle Variante.
Einziger Nachteil: grössere Platzbedarf - aber das war von Anfang an klar.@knivil: Vielen Dank für deinen Baum. Ich habe ihn schlussendlich zwar nicht gebraucht aber trotzdem merci
