Laden...

[erledigt] Region Growing - Performance/CodeRevision?

Erstellt von Luth vor 15 Jahren Letzter Beitrag vor 15 Jahren 2.043 Views
L
Luth Themenstarter:in
36 Beiträge seit 2006
vor 15 Jahren
[erledigt] Region Growing - Performance/CodeRevision?

Hallo zusammen!

Ich sitz gerade an einem einfachen Terraingenerator den ich mir für die Verwendung mit der Mogre-Engine (.Net-Wrapper für Ogre3D) schreibe. Bei der Generierung einer Höhenkarte lege ich fest, das bei Höhe = 0.1 die Wasserlinie verläuft. Nun habe ich das Problem, das durch die zufällige Höhenverteilung viele kleine "Seen" entstehen können. Die will ich raus haben. Lösungsansatz ist derzeit alle Seen zu finden, die aus weniger Punkten bestehen als eine gegebene Anzahl und die Höhen dieser Punkte anzupassen. Dadurch kann ich "Seen" in vernünftiger Größe behalten und den kleinen Fitzelkram rauswerfen. Die Höhendaten sind derzeit in einem einfachen float[] gespeichert.

Problem:
Finde alle Punkte die zu einem See gehören, und alle Seen

Lösungsansatz - Region Growing
1. Erstelle Liste aller Pixel mit Höhe ≤ 0.1 (Candidates)
2. Erstelle Liste die gefundene Seen enthält (Regions)
3. Nimm ersten Pixel (current) aus Candidates und erstelle neue Region (Reg)
4. Nachbarpixel auch in Candidates? Ja => Zu Reg hinzufügen, aus Candidates löschen
5. Nimm nächsten Pixel (current) aus Reg => gehe zu 4.
6. Wenn reg einmal durchlaufen ist und noch Kandidaten vorhanden sind => gehe zu 3.
7. Wenn Candidates leer ist => Ende

Das funktioniert soweit auch ganz gut ... läuft allerdings mit 40.000 See-Pixeln gute 60 Sekunden. X( Da ich von C# nur mässig Ahnung habe, würde ich mich sehr freuen wenn mal jemand ein Auge auf den Code werfen könnte um mir Tips hinsichtlich der Performance zu geben. Eventuell berechne ich ja noch viele Sachen doppelt und dreifach, an die man auch einfacher kommen könnte oder die verwendeten Datentypen sind der Aufgabe nicht angemessen oder falsch verwendet. Falls jemand mit sowas Erfahrung hat, würden mich natürlich auch alternative Ansätze oder Tips zu einer möglichen Vorverarbeitung interessieren. Alles was ich dazu bisher im Netz gefunden habe, war viel zu kompliziert um von mir in annehmbarer Zeit implementiert zu werden.

Hier der momentane Code:


      private static List<List<int>> PerformRegionGrowing(float[] hm, float min, float max)
        {
            int i=0;
            _map = hm;
            _size = (int)System.Math.Ceiling((System.Math.Sqrt(_map.Length)));                      
            
            List<int> candidates = new List<int>(); //List of points that are between min and max and have no region assigned           
            List<List<int>> regions = new List<List<int>>(); //List of all connected regions we found
            
            for (i = 0; i < hm.Length; i++)             //Search all candidates
                if ((hm[i] >= min) && (hm[i] <= max)) candidates.Add(i);              

            if (candidates.Count==0)  return null;           
           
            List<int> reg;             //Pixel-List of current region

            bool found = true;
            int x,y,offs,offx,candidate;
            int[] ind = new int[8];

            //Every point has to belong to a region
            while (candidates.Count != 0)
            {
                //Begin new region with the first point in candidates
                reg = new List<int>();
                reg.Add(candidates.ElementAt(0));
                candidates.RemoveAt(0);
                
                offs = 0;
                found = true;
                
                while (found)
                {
                    found = false;
                    current = reg.ElementAt(offs); //The pixel we check next
                    x = current / _size;                //The x-Position    
                    y = current % _size;              //The y-Position
                    offx = x * _size;                    
                   
                    //get indices of the 8 direct neighbours
                    ind[0] = (offx - _size) + (y - 1);
                    ind[1] = (offx)         + (y - 1);
                    ind[2] = (offx + _size) + (y - 1);

                    ind[3] = (offx - _size) + (y);
                    ind[4] = (offx + _size) + (y);

                    ind[5] = (offx - _size) + (y + 1);
                    ind[6] = (offx        ) + (y + 1);
                    ind[7] = (offx + _size) + (y + 1);

                    foreach(int j in ind)
                        if (candidates.Contains(j))
                            {
                                //It is a neighbour and a candidate, so it belongs to the region
                                reg.Add(j);
                                candidates.Remove(j);
                            }

                    if (offs < reg.Count - 1) found = true; //More pixels to check in this region
                    offs++;
                }
                regions.Add(reg);
            }
            return regions;
        }


Wie gesagt, bin ich für jeden Hinweis wie das zu optimieren wäre dankbar.

Bis dann

630 Beiträge seit 2007
vor 15 Jahren

Hallo,

verwende aufjedenfall ein normales Array statt List<> oder übergib List<> im Konstruktor die erwartete maximalgrösse der Liste ( z.b. 40.0000). Wenn die List voll ist wird nähmlich intern das ganze Array in ein doppelt so grosses Array kopiert. Desweiteren ist eine normale for-Schleife schneller als eine foreach.

Das dürft die Anwendung etwas beschleunigen.

Ich denke dass Problem liegt aber wahrscheinlich eher im Algorithmus. Kann dazu aber leider nicht mehr sagen weil ich mich auf diesem Gebiet überhaupt nicht auskenne.

Gruss
tscherno

To understand recursion you must first understand recursion

http://www.ilja-neumann.com
C# Gruppe bei last.fm

L
Luth Themenstarter:in
36 Beiträge seit 2006
vor 15 Jahren

Hallo und erstmal danke für die Antwort!

Wenn ich deinen Vorschlag richtig verstanden habe, geht das leider nicht. Da die Karte ja zufallsgeneriert ist, habe ich vor dem Durchlauf keine Ahnung wieviele Pixel unter der Wasserlinie liegen (die Candidates-Liste). Das können 200 oder 40.000 sein ... je nachdem was der Zufallsgenerator ausspuckt. Weiterhin weis ich ja noch nicht, wieviele verschiedene Regionen ich habe und wieviele Punkte zu der Region gehören, damit fällt die Initialisierung der Liste mit einem vorgegebenen Wert flach, wenn ich das richtig sehe. Aus dem gleichen Grund dürfte die Verwendung von Arrays keinen Vorteil bringen, da ich auch dort die Größe nicht zu beginn weis. Zumindest falls ich nichts übersehen habe ...

Die Foreach-Schleife habe ich mittlerweile gegen eine for( int j=0; j < 8; j++) ausgetauscht. Falls es dadurch einen Geschwindigkeitszuwachs gab, war der allerdings nicht im meßbaren Bereich. 😁

3.430 Beiträge seit 2007
vor 15 Jahren

Hi,

Die Foreach-Schleife habe ich mittlerweile gegen eine for( int j=0; j < 8; j++) ausgetauscht. Falls es dadurch einen Geschwindigkeitszuwachs gab, war der allerdings nicht im meßbaren Bereich.

Ja, das ist klar. Tscherno hat sicherlich geglaubt, dass diese Forschleife sehr oft durchlaufen, deshalb war sein Vorschlag schon richtig. Aber dass es dir da nix bringt ist auch klar, da eine Foreach-schleife nur minimal langsamer ist und bei nur 8 Durchläufen ist der Unterschied wie du schon sagtest, nicht messbar.

Versuche mal die list durch eine arraylist zu ersetzten. Vielleicht bringt dir das eine leichte Verbesserung.
PS: Ich habe aber keine Ahnung ob die ArrayList schneller ist als die List 🤔

Aber ansonsten kann ich da nur das selbe wie Tscherno sagen:

Ich denke dass Problem liegt aber wahrscheinlich eher im Algorithmus. Kann dazu aber leider nicht mehr sagen weil ich mich auf diesem Gebiet überhaupt nicht auskenne.

denn ich kenn mich mit den Algorithmen auch nicht gut aus, aber meistens kann man mit einem besseren Algorithmus das Programm extrem beschleunigen.

mfg
michlG

L
Luth Themenstarter:in
36 Beiträge seit 2006
vor 15 Jahren

Hah! Problem gelöst! 🙂

Ich bin von den Listen halbwegs weg und nehm ein bool[][] - Array zur Speicherung der Kandidaten. Alles was unter der gegebenen Höhe ist, bekommt ein true...der Rest ein false verpasst. Außerdem prüfe ich nicht mehr alle 8 Nachbarn eines Pixels ab, sondern nur noch 4. Damit spar ich mir viele Aufrufe von list<>.Contains() und list<>.Remove(). Das ganze ist dann unglaublich viel schneller. Jetzt brauche ich allerdings auch 20-30 MB mehr RAM, womit ich aber leben kann.

20:50:53: Starting removal of lakes smaller then 400.
20:50:53: Found 5 different lakes with 41569 points.
20:50:53: Finished removal of lakes smaller then 400.
20:50:53: Generated terrain (513x513) in 31 milliseconds.

Hat es vorher 60+ Sekunden benötigt, ist es jetzt fast um den Faktor 2000 schneller nur weil die Listen nicht mehr so eine große Rolle spielen. Ich weis nicht ganz ob ich jetzt darüber lachen soll oder nicht. Zumal man den Code noch weiter optimieren könnte, indem man einige der Prüfbedingungen weglässt und solches Zeug. 8o

Trotzdem nochmal danke für den Tipp für größere Schleifen for(...) statt foreach(...) zu verwenden.

Der neue Code, falls jemand die Änderungen interessieren:


        private static List<List<int>> PerformRegionGrowing(float[]hm, float min, float max)
        {
            int i,j=0;
            int x, y,x1,x2,y1,y2, offx,pixelcount = 0;
            int offs = 0;

            _map = hm;
            _size = (int)System.Math.Ceiling((System.Math.Sqrt(_map.Length)));

            //Flagmap of our terrain, true where 
            bool[,] candidatemap = new bool[_size, _size];
            
            //List of all connected regions we found                                         
            List<List<int>> regions = new List<List<int>>();
            
            //Search all points in the threshold
            for (i = 0; i < _size; i++)
            {
                for (j = 0; j < _size; j++)
                    if ((hm[offs + j] >= min) && (hm[offs + j] <= max))
                    {                        
                        candidatemap[i, j] = true;
                        pixelcount++;
                    }
                
                offs += _size;
            }
            //Buffer for current region
            List<int> reg;

            bool found = true;
            int candidate;

            //Every points has to belong to a region
            while (pixelcount>0)
            {
                //Begin new region simply with the next point in candidates
                reg = new List<int>();
                bool dobreak = false;
                //Search a starting point for that region
                for (i = 0; i < _size; i++)
                {
                    for (j = 0; j < _size; j++)
                    {
                        dobreak = candidatemap[i, j];
                        if (dobreak) break;
                    }
                    if (dobreak) break;                                                   
                }
                
                //We have a start pixel
                reg.Add(i*_size+j);
                pixelcount--;
                candidatemap[i,j]=false;
                //First point of new region
                offs = 0;
                found = true;
                
                while (found)
                {
                    found = false;
                    candidate = reg.ElementAt(offs);
                
                    x = candidate / _size;                    
                    y = candidate % _size;
                    offx = x * _size;                    
                  
                    x1 = x-1;
                    x2 = x+1;
                    y1 = y-1;
                    y2 = y+1;                    
                    //Check if the 4 neighbourgs belong to region and are on the map                    
                    if ((x1>=0)&&(candidatemap[x1,y]))
                    {
                       candidatemap[x1, y] = false;
                       reg.Add(x1*_size+y);
                       pixelcount--;
                    }

                    if ((x2<_size)&&(candidatemap[x2, y]))
                    {
                        candidatemap[x2, y] = false;
                        reg.Add(x2 * _size + y);
                        pixelcount--;
                    }

                    if ((y1>=0)&&(candidatemap[x, y1]))
                    {
                        candidatemap[x, y1] = false;
                        reg.Add(x * _size + y1);
                        pixelcount--;
                    }

                    if ((y2<_size)&&(candidatemap[x, y2]))
                    {
                        candidatemap[x, y2] = false;
                        reg.Add(x * _size + y2); 
                        pixelcount--;
                    }
                   
                    if (offs < reg.Count - 1) found = true;
                    offs++;
                }
                regions.Add(reg);
            }
            return regions;
        }