Element in Bitmap finden

  • C++

Es gibt 10 Antworten in diesem Thema. Der letzte Beitrag () ist von LaMiy.

    Element in Bitmap finden

    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.
    1. Solange einen Pixel weitergehen, bis ein dunkler Pixel gefunden wurde. (Helligkeit wird hier überprüft)
    2. Dieser Pixel ist offenbar der Anfang einer Form
    3. Also gehe ich alle Pixel ab, die mit dieser Form zusammenhängen. (Ich gehe nach links, rechts, oben, unten, diagonal links ...)
    4. Wenn der neue Pixel auch dunkel ist, dann gehe ich wieder in alle Richtungen
    5. Bei diesem Vorgang merke ich mir alle besuchten Pixel, sodass ich sie nicht nochmal besuche
    6. 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++ Code

    C-Quellcode

    1. // Sucht nach Textelementen
    2. void Map::Search()
    3. {
    4. // Aktuelle Position
    5. int cp = 0;
    6. // Breite und Höhe
    7. int width = this->ptrBmpData->Width;
    8. int height = this->ptrBmpData->Height;
    10. // Neues Array erstellen (0 => nicht besucht 1=> besucht)
    11. std::vector<bool> generalMask(width * height, false);
    13. // Neuen Zeiger erstellen, der auf den ersten Pixel zeigt (alternativ kann auch Buffer benutzt werden)
    14. UINT * scan = (UINT*) ptrBmpData->Scan0;
    16. // Über alle Farbwerte gehen
    17. for (int cp = 0; cp < (width * height); cp ++)
    18. {
    19. // X und Y-Position berechnen
    20. int x = cp % width;
    21. int y = cp / width;
    23. // Wenn der aktuelle Pixel noch nicht besucht wurde und die Helligkeit stimmt
    24. if (!generalMask[cp] == true && this->GetBrightness(*scan) <= this->maxBrightness)
    25. {
    26. // Element, ausgehend vom gefundenen Punkt suchen
    27. StructureElement elem = this->GetElement(generalMask, x , y , width , height);
    28. }
    30. // Als besucht markieren
    31. generalMask[cp] = true;
    32. // Zum nächsten Wert
    33. scan++;
    34. }
    35. }
    37. // Methode um die Position eines Buchstabens zu finden
    38. StructureElement Map::GetElement(std::vector<bool>& generalMask, int originX, int originY, int width, int height)
    39. {
    40. // Maske für die Pixel dieses Buchstabens
    41. //TODO: Eventuell kleiner machen?
    42. std::vector<bool> maskResult(width * height);
    44. // Rechteck für die Ausmaße
    45. Rect rect(width + 1, height + 1, -1, -1);
    46. // Methode aufrufen und Daten in die Variablen laden
    47. GetElementHelper(generalMask,
    48. maskResult,
    49. originX,
    50. originY,
    51. width,
    52. height,
    53. rect);
    55. cout << originX << "/" << originY << "\n";
    57. //Strukturelement zurückgeben
    58. return StructureElement(maskResult,
    59. originX,
    60. originY,
    61. rect.X - rect.Width,
    62. rect.Y - rect.Height);
    63. }
    65. // Rekursive Methode für das Suchen den Positionen und Außmaße
    66. void Map::GetElementHelper(std::vector<bool>& generalMask, std::vector<bool>& bResult, int originX, int originY, int width, int height, Rect bounds)
    67. {
    68. // Neue Queue erstellen. In ihr werden alle noch zu besuchenden Pixel gespeichert
    69. queue<Vector2>* qVectors = new queue<Vector2>;
    70. qVectors->push(Vector2((float)originX, (float)originY));
    72. // Solange etwas in der Qeue ist
    73. while (!qVectors->empty())
    74. {
    75. // Nächsten Wert aus der Queue holen
    76. Vector2 vActual = qVectors->front();
    77. qVectors->pop();
    79. // Wurde der Pixel noch nicht besucht und ist er unterhalb des gewünschten Helligkeitswerts
    80. if (vActual.GetX() < width && vActual.GetY() < height &&
    81. this->GetBrightness(this->Buffer[(int)(vActual.GetY() * width + vActual.GetX())]) <= this->maxBrightness &&
    82. generalMask[(int) (vActual.GetY() * width + vActual.GetX())] == false)
    83. {
    84. // Festlegen der Größe
    85. if (vActual.GetX() < bounds.X)
    86. bounds.X = (int) vActual.GetX();
    87. if (vActual.GetY() < bounds.Y)
    88. bounds.Y = (int) vActual.GetY();
    89. if (vActual.GetX() > bounds.Width)
    90. bounds.Width = (int) vActual.GetX();
    91. if (vActual.GetY() > bounds.Height)
    92. bounds.Height = (int) vActual.GetY();
    94. // Als besucht markieren
    95. generalMask[(int) (vActual.GetY() * width + vActual.GetX())] = true;
    97. // Als Textpixel markieren
    98. bResult[(int) (vActual.GetY() * width + vActual.GetX())] = true;
    100. // Oben und unten
    101. if (originY > 0)
    102. qVectors->push(Vector2(vActual.GetX(), vActual.GetY() - 1));
    103. if (originY + 1 < height)
    104. qVectors->push(Vector2(vActual.GetX(), vActual.GetY() + 1));
    106. if (originX > 0)
    107. {
    108. // Linke Seite
    109. qVectors->push(Vector2(vActual.GetX() - 1, vActual.GetY()));
    110. // Diagonal links
    111. if (originY > 0)
    112. qVectors->push(Vector2(vActual.GetX() - 1, vActual.GetY() - 1));
    113. if (originY + 1 < height)
    114. qVectors->push(Vector2(vActual.GetX() - 1, vActual.GetY() + 1));
    115. }
    117. if (originX + 1 < width)
    118. {
    119. // Rechte Seite
    120. qVectors->push(Vector2(vActual.GetX() + 1, vActual.GetY()));
    121. // Diagonal right
    122. if (originY > 0)
    123. qVectors->push(Vector2(vActual.GetX() + 1, vActual.GetY() - 1));
    124. if (originY + 1 < height)
    125. qVectors->push(Vector2(vActual.GetX() + 1, vActual.GetY() + 1));
    126. }
    127. }
    128. }
    130. delete qVectors;
    131. qVectors = 0;
    132. }
    C#

    C-Quellcode

    1. public IEnumerable<StructureElement> Search()
    2. {
    3. // Dimension
    4. int width = this._bitmapData.Width;
    5. int height = this._bitmapData.Height;
    6. // Output list
    7. ICollection<StructureElement> elements = new LinkedList<StructureElement>();
    8. // Actual uint position
    9. int cp = 0;
    10. // Generel visited positions
    11. this.generalMask = new BitArray(width * height);
    12. // Pointer at the fist uint
    13. uint* scp = (uint*)_bitmapData.Scan0;
    14. // Create the first coordinate
    15. BitmapCoordinate crd = new BitmapCoordinate(generalMask, scp, width);
    16. // Stick the array
    17. fixed (uint* cb = this.Buffer)
    19. // Step through each pixel
    20. for (uint* cbp = cb, cbdest = cb + this.Buffer.Length; cbp < cbdest; cbp++)
    21. {
    22. // Get x and y from position
    23. int x = cp % width;
    24. int y = cp / width;
    26. //nur nicht bereits besuchte und von weiß abweichende Pixel als Struktur-Anfang feststellen
    27. if (generalMask[cp] == false && this.GetBrightness(*cbp) <= this.maxBrightness)
    28. elements.Add(GetElement(crd, x, y, width, height)); // Die Struktur innerhalb der Bitmap der Liste aller Strukturen hinzufügen
    30. generalMask.Set(cp, true);
    31. cp++; // Increment cp
    32. }
    33. return elements;
    34. }
    36. private StructureElement GetElement(BitmapCoordinate helper, int originX, int originY, int width, int height)
    37. {
    38. // Das Element ausgehend von (originX, originY) suchen
    39. BitArray bResult = new BitArray(width * height);
    40. // Resultrectangle
    41. Rect rct = new Rect() { X = width + 1, Y = height + 1, Right = -1, Bottom = -1 };
    42. // Methode mit den aktuell besuchten Feldern und einem Feld für die Ergebnisse aufrufen
    43. GetElementHelper(helper, bResult, originX, originY, width, height, rct);
    44. //Strukturelement zurückgeben
    45. return new StructureElement(bResult, _bitmap, originX, originY, new Rectangle(rct.X, rct.Y, rct.Right - rct.X, rct.Bottom - rct.Y));
    46. }
    49. private void GetElementHelper(BitmapCoordinate helper, BitArray bResult, int originX, int originY, int width, int height, Rect bounds)
    50. {
    51. // Neue Queue erstellen. In ihr werden alle noch zu besuchenden Pixel gespeichert
    52. Queue<Vector2> qVectors = new Queue<Vector2>();
    53. qVectors.Enqueue(new Vector2(originX, originY));
    55. // Solange etwas in der Qeue ist
    56. while (qVectors.Count > 0)
    57. {
    58. // Nächsten Wert aus der Queue holen
    59. Vector2 vActual = qVectors.Dequeue();
    61. // Wurde der Pixel noch nicht besucht und ist er unterhalb des gewünschten Helligkeitswerts
    62. if (vActual.X < width && vActual.Y < height &&
    63. this.GetBrightness(this.Buffer[(int)(vActual.Y * width + vActual.X)]) <= this.maxBrightness &&
    64. generalMask[(int)(vActual.Y * width + vActual.X)] == false)
    65. {
    66. // Festlegen der Größe
    67. if (vActual.X < bounds.X)
    68. bounds.X = (int)vActual.X;
    69. if (vActual.Y < bounds.Y)
    70. bounds.Y = (int)vActual.Y;
    71. if (vActual.X > bounds.Right)
    72. bounds.Right = (int)vActual.X;
    73. if (vActual.Y > bounds.Bottom)
    74. bounds.Bottom = (int)vActual.Y;
    76. // Als besucht markieren
    77. generalMask[(int)(vActual.Y * width + vActual.X)] = true;
    79. // Als Textpixel markieren
    80. bResult[(int)(vActual.Y * width + vActual.X)] = true;
    82. // Oben und unten
    83. if (originY > 0)
    84. qVectors.Enqueue(new Vector2(vActual.X, vActual.Y - 1));
    85. if (originY + 1 < height)
    86. qVectors.Enqueue(new Vector2(vActual.X, vActual.Y + 1));
    88. if (originX > 0)
    89. {
    90. // Linke Seite
    91. qVectors.Enqueue(new Vector2(vActual.X - 1, vActual.Y));
    92. // Diagonal links
    93. if (originY > 0)
    94. qVectors.Enqueue(new Vector2(vActual.X - 1, vActual.Y - 1));
    95. if (originY + 1 < height)
    96. qVectors.Enqueue(new Vector2(vActual.X - 1, vActual.Y + 1));
    97. }
    99. if (originX + 1 < width)
    100. {
    101. // Rechte Seite
    102. qVectors.Enqueue(new Vector2(vActual.X + 1, vActual.Y));
    103. // Diagonal right
    104. if (originY > 0)
    105. qVectors.Enqueue(new Vector2(vActual.X + 1, vActual.Y - 1));
    106. if (originY + 1 < height)
    107. qVectors.Enqueue(new Vector2(vActual.X + 1, vActual.Y + 1));
    108. }
    109. }
    110. }
    111. }

    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.
    Bilder

    • process.png

      109,17 kB, 1.502×462, 169 mal angesehen

    • time.png

      15,18 kB, 1.046×302, 160 mal angesehen

    Hi
    auf vector<bool> kann man verzichten, indem man direkt auf einem Array operiert. Erzeuge dazu ein Array mit x * y / 32 32-Bit (oder x * y / 64 64-Bit) Ganzzahlen und greife auf das (x, y)-te Element über p = (y * width + x) / 32 (bzw. 64) zu und überprüfe anschließend, ob p & (1 << (y * width + x) % 32) != 0 ist.

    Gruß
    ~blaze~

    Ja, in C++ gibts aber auch noch ne list<>. Das gilt aber auch für vector<>, bis auf eine Ausnahme - der vector<bool>. Ein Array braucht pro bool ein Byte, da man minimal nur 1 Byte im Speicher ablegen kann. Ein vector<bool> braucht für jedes Element nur 1 Bit. Es wird ein Byte allokiert und dann solang mit Bits befüllt bis ein neues gebraucht wird, ich denk mal so regelt das BitArray auch.

    Ich hab schon etwas an dem Code rumgetestet und bin der Meinung, dass es an der Rekursion liegt. Diese ist auch sehr langsam, nur ich hab keine Ahnung wieso das dann in .Net läuft. Also müsste irgendwo n Fehler drin stecken.

    Ich habe es mal so getestet.

    C-Quellcode

    1. int width = 2, height = 2;
    2. unsigned int* mask = 0;
    3. mask = new unsigned int[width * height];
    4. mask[(1 * width + 0) / 32] = 1;
    6. int x = 0, y = 1;
    7. unsigned int tmp = mask[(y * width + x) / 32];
    8. if (tmp & (1 << (y * width + x) % 32) != 0)
    9. cout << "Passt";

    Ich versuche das mal zu implementieren und melde dann, ob es spürbar schneller ist.

    LaMiy schrieb:

    Ich versuche das mal zu implementieren und melde dann, ob es spürbar schneller ist.

    Es ist deutlich schneller. Es wird noch schneller, wenn du so wenig Aufrufe von new machst wie es geht. new ist teuer!
    Siehe auch: de.wikipedia.org/wiki/RAII, obwohl das für deinen Fall wohl nicht geht da der Stack zu klein ist. Aber eigentlich brauchst du new nur ein mal, imho.
    To make foobar2000 a real random music player, I figured out the only way to achieve this is to use Windows Media Player.

    “At some point in time, you recognize that knowing more does not necessarily make you more happy.”

    @LaMiy:: Das sieht ja sehr nach echter Bildverarbeitung aus.
    Vielleicht übersdenkst Du Dein Konzept noch mal völlig neu.
    Mach Dir eine Reihe von Elementar-Operatoren, z.B. (für SW-Bilder)
    Medianfilter (Ausreißer eliminieren)
    Gradient
    (intelligente) Diskriminierung
    Laplacefilter (Kanten finden)
    ...
    desweiteren geeignete Anzeigeoperationen, Histogramm-Korrektur, Falschfarbenbild usw.
    ---
    Und wenn Du ein Bild bearbeitest, wird der bearbeitete Bildinhalt in einen neuen Bildspeicher geschrieben bzw. danach wieder zurückkopiert.
    Und mach Dir gleich einen Undo-Operator mit.
    So kannst Du Dein Bild "experimentell" prozessieren - nach jedem Schritt anzeigen lassen und sehen, was nun kommen könnte
    Falls Du diesen Code kopierst, achte auf die C&P-Bremse.
    Jede einzelne Zeile Deines Programms, die Du nicht explizit getestet hast, ist falsch :!:
    Ein guter .NET-Snippetkonverter (der ist verfügbar).
    Programmierfragen über PN / Konversation werden ignoriert!

    @RodFromGermany:
    Diese Art von Filtern brauche ich wahrscheinlich erst später.
    (aber auch dann nur im kleinen)
    Die Idee mit dem "Undo" Operator finde ich zu Testzwecken sehr gut, wie genau stellst du dir das vor? Einfach "Unlocken" und wieder Locken?

    @all
    Habe mich mit @blaze: über seine Variante unterhalten.
    Soweit sollte es passen, aber es fliegt 'n StackOverflow.
    Jemand eine Idee?
    Code

    C-Quellcode

    1. // Sucht nach Textelementen
    2. void Map::Search()
    3. {
    4. // Aktuelle Position
    5. int cp = 0;
    6. // Breite und Höhe
    7. int width = this->ptrBmpData->Width;
    8. int height = this->ptrBmpData->Height;
    10. // Neues Array erstellen (0 => nicht besucht 1=> besucht)
    11. unsigned int* mask = 0;
    12. mask = new unsigned int[width * height];
    13. ZeroMemory(mask, width * height);
    15. // Neuen Zeiger erstellen, der auf den ersten Pixel zeigt (alternativ kann auch Buffer benutzt werden)
    16. UINT * scan = (UINT*)ptrBmpData->Scan0;
    18. // Über alle Farbwerte gehen
    19. for (int cp = 0; cp < (width * height); cp++)
    20. {
    21. // X und Y-Position berechnen
    22. int x = cp % width;
    23. int y = cp / width;
    25. int p = mask[(y * width + x) / 32];
    26. int pp = 1 << ((y * width + x) % 32);
    28. int a = p & pp;
    29. int yy = a;
    32. // Wenn der aktuelle Pixel noch nicht besucht wurde und die Helligkeit stimmt
    33. if (a == 0 && this->GetBrightness(*scan) <= this->maxBrightness)
    34. {
    35. // Element, ausgehend vom gefundenen Punkt suchen
    36. StructureElement elem = this->GetElement(mask, x, y, width, height);
    37. }
    39. // Als besucht markieren
    40. mask[(y * width + x) / 32] |= (1 << ((width * y + x) % 32));
    41. scan ++;
    42. }
    43. }
    45. // Methode um die Position eines Buchstabens zu finden
    46. StructureElement Map::GetElement(unsigned int* mask, int originX, int originY, int width, int height)
    47. {
    48. // Maske für die Pixel dieses Buchstabens
    49. //TODO: Eventuell kleiner machen?
    50. unsigned int* maskResult = 0;
    51. maskResult = new unsigned int[width * height];
    52. ZeroMemory(maskResult, width * height);
    54. // Rechteck für die Ausmaße
    55. Rect rect(width + 1, height + 1, -1, -1);
    56. // Methode aufrufen und Daten in die Variablen laden
    57. GetElementHelper(mask,
    58. maskResult,
    59. originX,
    60. originY,
    61. width,
    62. height,
    63. rect);
    65. cout << originX << "/" << originY << "\n";
    67. //Strukturelement zurückgeben
    68. return StructureElement(maskResult,
    69. originX,
    70. originY,
    71. rect.X - rect.Width,
    72. rect.Y - rect.Height);
    73. }
    75. // Rekursive Methode für das Suchen den Positionen und Außmaße
    76. void Map::GetElementHelper(unsigned int* generalMask, unsigned int* bResult, int originX, int originY, int width, int height, Rect bounds)
    77. {
    78. int p = generalMask[(originY * width + originX) / 32];
    79. int pp = 1 << ((originY * width + originX) % 32);
    80. int a = p & pp;
    82. float brightness = this->GetBrightness(this->Buffer[(originY * width + originX)]);
    84. // Wurde der Pixel noch nicht besucht und ist er unterhalb des gewünschten Helligkeitswerts
    85. if (originX < width && originY < height && originY > 0 && originX > 0 &&
    86. brightness <= this->maxBrightness &&
    87. a == 0)
    88. {
    89. // Allocation of the vars
    90. if (originX < bounds.X)
    91. bounds.X = originX;
    92. if (originY < bounds.Y)
    93. bounds.Y = originY;
    94. if (originX > bounds.Width)
    95. bounds.Width = originX;
    96. if (originY > bounds.Height)
    97. bounds.Height = originY;
    99. // Set as visited
    100. int xx = generalMask[(originY * width + originX) / 32];
    101. generalMask[(originY * width + originX) / 32] |= 1 << ((originY * width + originX) % 32);
    102. int xxx = generalMask[(originY * width + originX) / 32];
    104. // Mark as not white pixel
    105. bResult[(originY * width + originX) / 32] |= 1 << ((originY * width + originX) % 32);
    107. // Up and down
    108. if (originY > 0)
    109. GetElementHelper(generalMask, bResult, originX, originY - 1, width, height, bounds);
    110. if (originY + 1 < height)
    111. GetElementHelper(generalMask, bResult, originX, originY + 1, width, height, bounds);
    113. if (originX > 0)
    114. {
    115. // Continue at the left side
    116. GetElementHelper(generalMask, bResult, originX - 1, originY, width, height, bounds);
    117. // Diagonal left
    118. if (originY > 0)
    119. GetElementHelper(generalMask, bResult, originX - 1, originY - 1, width, height, bounds);
    120. if (originY + 1 < height)
    121. GetElementHelper(generalMask, bResult, originX - 1, originY + 1, width, height, bounds);
    122. }
    124. if (originX + 1 < width)
    125. {
    126. // Continue at the right side
    127. GetElementHelper(generalMask, bResult, originX + 1, originY, width, height, bounds);
    128. // Diagonal right
    129. if (originY > 0)
    130. GetElementHelper(generalMask, bResult, originX + 1, originY - 1, width, height, bounds);
    131. if (originY + 1 < height)
    132. GetElementHelper(generalMask, bResult, originX + 1, originY + 1, width, height, bounds);
    133. }
    134. }
    135. }

    LaMiy schrieb:

    wie genau stellst du dir das vor?
    Du arbeitest auf einem Array. Mach vor dem Anwenden des Operators eine Kopie vom Feld. Die kannst Du in einer List(Of ) | vector<> speichern und ggf. restaurieren.
    Falls Du diesen Code kopierst, achte auf die C&P-Bremse.
    Jede einzelne Zeile Deines Programms, die Du nicht explizit getestet hast, ist falsch :!:
    Ein guter .NET-Snippetkonverter (der ist verfügbar).
    Programmierfragen über PN / Konversation werden ignoriert!

    So ich habe es nun hiermit gelöst. stackoverflow.com/questions/12…-and-assignment-operators
    Das ist im Prinzip die Methode, die blaze vorgeschlagen hat.
    Klappt sehr gut, und im direkten Vergleich bekam ich mit der Methode vector<bool> 'nen StackOverflow, während die verlinkte Klasse funktioniert hat.
    (Kann eventuell sein, dass ich vector<bool> falsch benutzt habe :D )

Facebook
Telefonspende