Mein Vorhaben ist es in einer Bitmap Formen zu finden. (Welche spielt dabei keine Rolle)
Dafür habe ich mir eine Methode geschrieben, die folgendes macht.
Vergleichen kann man dieses Vorhaben mit einer Breitensuche, oder auch Tiefensuche.
Nun zum eigentlichen Problem.
In C# funktioniert der Code einwandfrei. (Breitensuche mit einer Queue und Tiefensuche mit einer Rekursion)
In C++ funktioniert es in der Breitensuche zwar auch, aber es ist extrem langsam und ich weiß nicht woran das liegt.
Hat jemand eine Idee woran das liegen könnte?
Hier die Codeausschnitte und ein paar Bilder einer Leistungsanalyse.
C++ Code
C#
Codezusatz:
Vector2 : Structure, die einfach einen X und einen Y Wert speichert (vergleichbar mit Point)
Buffer : Farbwerte der Bitmap als UINT
GetBrightness() : Methode zum Auslesen des Helligkeitswerts
StructureElement: Klasse, die einfach Informationen über eine Form festhalten soll
BitmapCoordinate: Klasse, die einfach Informationen über die Bitmap, sowie die "generalMask", also die Maske aller besuchten Pixel festhalten soll.
Was ich mir vorstellen könnte ist, dass das BitArray so viel schneller als vector<bool> ist, mir wurde jedoch gesagt, dass vector<bool> bis auf's letzte optimiert ist.
Ich hoffe dass jemand mir helfen kann und dass ich das Problem verständlich geschildert habe.
Dafür habe ich mir eine Methode geschrieben, die folgendes macht.
- Solange einen Pixel weitergehen, bis ein dunkler Pixel gefunden wurde. (Helligkeit wird hier überprüft)
- Dieser Pixel ist offenbar der Anfang einer Form
- Also gehe ich alle Pixel ab, die mit dieser Form zusammenhängen. (Ich gehe nach links, rechts, oben, unten, diagonal links ...)
- Wenn der neue Pixel auch dunkel ist, dann gehe ich wieder in alle Richtungen
- Bei diesem Vorgang merke ich mir alle besuchten Pixel, sodass ich sie nicht nochmal besuche
- Jeder dunkle Pixel wird in einem Array markiert
Vergleichen kann man dieses Vorhaben mit einer Breitensuche, oder auch Tiefensuche.
Nun zum eigentlichen Problem.
In C# funktioniert der Code einwandfrei. (Breitensuche mit einer Queue und Tiefensuche mit einer Rekursion)
In C++ funktioniert es in der Breitensuche zwar auch, aber es ist extrem langsam und ich weiß nicht woran das liegt.
Hat jemand eine Idee woran das liegen könnte?
Hier die Codeausschnitte und ein paar Bilder einer Leistungsanalyse.
C-Quellcode
- // Sucht nach Textelementen
- void Map::Search()
- {
- // Aktuelle Position
- int cp = 0;
- // Breite und Höhe
- int width = this->ptrBmpData->Width;
- int height = this->ptrBmpData->Height;
- // Neues Array erstellen (0 => nicht besucht 1=> besucht)
- std::vector<bool> generalMask(width * height, false);
- // Neuen Zeiger erstellen, der auf den ersten Pixel zeigt (alternativ kann auch Buffer benutzt werden)
- UINT * scan = (UINT*) ptrBmpData->Scan0;
- // Über alle Farbwerte gehen
- for (int cp = 0; cp < (width * height); cp ++)
- {
- // X und Y-Position berechnen
- int x = cp % width;
- int y = cp / width;
- // Wenn der aktuelle Pixel noch nicht besucht wurde und die Helligkeit stimmt
- if (!generalMask[cp] == true && this->GetBrightness(*scan) <= this->maxBrightness)
- {
- // Element, ausgehend vom gefundenen Punkt suchen
- StructureElement elem = this->GetElement(generalMask, x , y , width , height);
- }
- // Als besucht markieren
- generalMask[cp] = true;
- // Zum nächsten Wert
- scan++;
- }
- }
- // Methode um die Position eines Buchstabens zu finden
- StructureElement Map::GetElement(std::vector<bool>& generalMask, int originX, int originY, int width, int height)
- {
- // Maske für die Pixel dieses Buchstabens
- //TODO: Eventuell kleiner machen?
- std::vector<bool> maskResult(width * height);
- // Rechteck für die Ausmaße
- Rect rect(width + 1, height + 1, -1, -1);
- // Methode aufrufen und Daten in die Variablen laden
- GetElementHelper(generalMask,
- maskResult,
- originX,
- originY,
- width,
- height,
- rect);
- cout << originX << "/" << originY << "\n";
- //Strukturelement zurückgeben
- return StructureElement(maskResult,
- originX,
- originY,
- rect.X - rect.Width,
- rect.Y - rect.Height);
- }
- // Rekursive Methode für das Suchen den Positionen und Außmaße
- void Map::GetElementHelper(std::vector<bool>& generalMask, std::vector<bool>& bResult, int originX, int originY, int width, int height, Rect bounds)
- {
- // Neue Queue erstellen. In ihr werden alle noch zu besuchenden Pixel gespeichert
- queue<Vector2>* qVectors = new queue<Vector2>;
- qVectors->push(Vector2((float)originX, (float)originY));
- // Solange etwas in der Qeue ist
- while (!qVectors->empty())
- {
- // Nächsten Wert aus der Queue holen
- Vector2 vActual = qVectors->front();
- qVectors->pop();
- // Wurde der Pixel noch nicht besucht und ist er unterhalb des gewünschten Helligkeitswerts
- if (vActual.GetX() < width && vActual.GetY() < height &&
- this->GetBrightness(this->Buffer[(int)(vActual.GetY() * width + vActual.GetX())]) <= this->maxBrightness &&
- generalMask[(int) (vActual.GetY() * width + vActual.GetX())] == false)
- {
- // Festlegen der Größe
- if (vActual.GetX() < bounds.X)
- bounds.X = (int) vActual.GetX();
- if (vActual.GetY() < bounds.Y)
- bounds.Y = (int) vActual.GetY();
- if (vActual.GetX() > bounds.Width)
- bounds.Width = (int) vActual.GetX();
- if (vActual.GetY() > bounds.Height)
- bounds.Height = (int) vActual.GetY();
- // Als besucht markieren
- generalMask[(int) (vActual.GetY() * width + vActual.GetX())] = true;
- // Als Textpixel markieren
- bResult[(int) (vActual.GetY() * width + vActual.GetX())] = true;
- // Oben und unten
- if (originY > 0)
- qVectors->push(Vector2(vActual.GetX(), vActual.GetY() - 1));
- if (originY + 1 < height)
- qVectors->push(Vector2(vActual.GetX(), vActual.GetY() + 1));
- if (originX > 0)
- {
- // Linke Seite
- qVectors->push(Vector2(vActual.GetX() - 1, vActual.GetY()));
- // Diagonal links
- if (originY > 0)
- qVectors->push(Vector2(vActual.GetX() - 1, vActual.GetY() - 1));
- if (originY + 1 < height)
- qVectors->push(Vector2(vActual.GetX() - 1, vActual.GetY() + 1));
- }
- if (originX + 1 < width)
- {
- // Rechte Seite
- qVectors->push(Vector2(vActual.GetX() + 1, vActual.GetY()));
- // Diagonal right
- if (originY > 0)
- qVectors->push(Vector2(vActual.GetX() + 1, vActual.GetY() - 1));
- if (originY + 1 < height)
- qVectors->push(Vector2(vActual.GetX() + 1, vActual.GetY() + 1));
- }
- }
- }
- delete qVectors;
- qVectors = 0;
- }
C-Quellcode
- public IEnumerable<StructureElement> Search()
- {
- // Dimension
- int width = this._bitmapData.Width;
- int height = this._bitmapData.Height;
- // Output list
- ICollection<StructureElement> elements = new LinkedList<StructureElement>();
- // Actual uint position
- int cp = 0;
- // Generel visited positions
- this.generalMask = new BitArray(width * height);
- // Pointer at the fist uint
- uint* scp = (uint*)_bitmapData.Scan0;
- // Create the first coordinate
- BitmapCoordinate crd = new BitmapCoordinate(generalMask, scp, width);
- // Stick the array
- fixed (uint* cb = this.Buffer)
- // Step through each pixel
- for (uint* cbp = cb, cbdest = cb + this.Buffer.Length; cbp < cbdest; cbp++)
- {
- // Get x and y from position
- int x = cp % width;
- int y = cp / width;
- //nur nicht bereits besuchte und von weiß abweichende Pixel als Struktur-Anfang feststellen
- if (generalMask[cp] == false && this.GetBrightness(*cbp) <= this.maxBrightness)
- elements.Add(GetElement(crd, x, y, width, height)); // Die Struktur innerhalb der Bitmap der Liste aller Strukturen hinzufügen
- generalMask.Set(cp, true);
- cp++; // Increment cp
- }
- return elements;
- }
- private StructureElement GetElement(BitmapCoordinate helper, int originX, int originY, int width, int height)
- {
- // Das Element ausgehend von (originX, originY) suchen
- BitArray bResult = new BitArray(width * height);
- // Resultrectangle
- Rect rct = new Rect() { X = width + 1, Y = height + 1, Right = -1, Bottom = -1 };
- // Methode mit den aktuell besuchten Feldern und einem Feld für die Ergebnisse aufrufen
- GetElementHelper(helper, bResult, originX, originY, width, height, rct);
- //Strukturelement zurückgeben
- return new StructureElement(bResult, _bitmap, originX, originY, new Rectangle(rct.X, rct.Y, rct.Right - rct.X, rct.Bottom - rct.Y));
- }
- private void GetElementHelper(BitmapCoordinate helper, BitArray bResult, int originX, int originY, int width, int height, Rect bounds)
- {
- // Neue Queue erstellen. In ihr werden alle noch zu besuchenden Pixel gespeichert
- Queue<Vector2> qVectors = new Queue<Vector2>();
- qVectors.Enqueue(new Vector2(originX, originY));
- // Solange etwas in der Qeue ist
- while (qVectors.Count > 0)
- {
- // Nächsten Wert aus der Queue holen
- Vector2 vActual = qVectors.Dequeue();
- // Wurde der Pixel noch nicht besucht und ist er unterhalb des gewünschten Helligkeitswerts
- if (vActual.X < width && vActual.Y < height &&
- this.GetBrightness(this.Buffer[(int)(vActual.Y * width + vActual.X)]) <= this.maxBrightness &&
- generalMask[(int)(vActual.Y * width + vActual.X)] == false)
- {
- // Festlegen der Größe
- if (vActual.X < bounds.X)
- bounds.X = (int)vActual.X;
- if (vActual.Y < bounds.Y)
- bounds.Y = (int)vActual.Y;
- if (vActual.X > bounds.Right)
- bounds.Right = (int)vActual.X;
- if (vActual.Y > bounds.Bottom)
- bounds.Bottom = (int)vActual.Y;
- // Als besucht markieren
- generalMask[(int)(vActual.Y * width + vActual.X)] = true;
- // Als Textpixel markieren
- bResult[(int)(vActual.Y * width + vActual.X)] = true;
- // Oben und unten
- if (originY > 0)
- qVectors.Enqueue(new Vector2(vActual.X, vActual.Y - 1));
- if (originY + 1 < height)
- qVectors.Enqueue(new Vector2(vActual.X, vActual.Y + 1));
- if (originX > 0)
- {
- // Linke Seite
- qVectors.Enqueue(new Vector2(vActual.X - 1, vActual.Y));
- // Diagonal links
- if (originY > 0)
- qVectors.Enqueue(new Vector2(vActual.X - 1, vActual.Y - 1));
- if (originY + 1 < height)
- qVectors.Enqueue(new Vector2(vActual.X - 1, vActual.Y + 1));
- }
- if (originX + 1 < width)
- {
- // Rechte Seite
- qVectors.Enqueue(new Vector2(vActual.X + 1, vActual.Y));
- // Diagonal right
- if (originY > 0)
- qVectors.Enqueue(new Vector2(vActual.X + 1, vActual.Y - 1));
- if (originY + 1 < height)
- qVectors.Enqueue(new Vector2(vActual.X + 1, vActual.Y + 1));
- }
- }
- }
- }
Codezusatz:
Vector2 : Structure, die einfach einen X und einen Y Wert speichert (vergleichbar mit Point)
Buffer : Farbwerte der Bitmap als UINT
GetBrightness() : Methode zum Auslesen des Helligkeitswerts
StructureElement: Klasse, die einfach Informationen über eine Form festhalten soll
BitmapCoordinate: Klasse, die einfach Informationen über die Bitmap, sowie die "generalMask", also die Maske aller besuchten Pixel festhalten soll.
Was ich mir vorstellen könnte ist, dass das BitArray so viel schneller als vector<bool> ist, mir wurde jedoch gesagt, dass vector<bool> bis auf's letzte optimiert ist.
Ich hoffe dass jemand mir helfen kann und dass ich das Problem verständlich geschildert habe.