Zhang-Suen Thinning Algorithmus

  • C#
  • .NET (FX) 4.5–4.8

Es gibt 9 Antworten in diesem Thema. Der letzte Beitrag () ist von RodFromGermany.

    Zhang-Suen Thinning Algorithmus

    Ich bin im Moment dabei einen Algorithmus zur Skelettierung in C# zu implementieren.
    Dabei soll der Zhang-Suen Thinning Algorithmus ganz gut sein.
    Hier habe ich eine Java-Implementierung gefunden und sie versucht zu übersetzen. nayefreza.wordpress.com/2013/0…ithm-java-implementation/
    Der unten stehende Code ist dabei rausgekommen.

    Klappt auch sehr gut, aber ist extrem langsam. (ca. 15sek. bei 1000x300 Pixeln)
    Ich habe schon versucht den Algorithmus abschnittweise arbeiten zu lassen. (Nicht über das ganze Bild, sondern nur über relevante Abschnitte)
    Da kam aber ein sehr komisches Ergebnis raus.

    Meine Frage ist ob jemand eine Idee hat wie man das ganze beschleunigen kann?
    (Paralell.For habe ich schon probiert)
    Könnte man vielleicht Zeiger einsetzten?

    Oder kennt jemand eine andere Methode die vielleicht schneller ist?
    Grüße :)

    Implementierung
    Spoiler anzeigen

    C#-Quellcode

    1. private float maxBrightness = 0.9f;
    2. private const uint WHITE = 4294967295;
    4. public uint[] Thinning(uint[] buffer, int originX, int originY, int xWidth, int xHeight, int width, int height)
    5. {
    6. int a, b;
    8. List<Point> lpointsToChange = new List<Point>();
    9. bool hasChange;
    11. do
    12. {
    13. hasChange = false;
    14. for (int y = originY; y < originY + xWidth; y ++)
    15. {
    16. for (int x = originX; x + 1 < originX + xWidth; x++)
    17. {
    18. a = getA(buffer, y, x, width, height);
    19. b = getB(buffer, y, x, width, height);
    21. if (y > 0 && y + 1 < height && x > 0 && x + 1 < width)
    22. {
    23. int p1 = GetValueOfColor(buffer[y * width + x]);
    24. int p2 = GetValueOfColor(buffer[(y - 1) * width + x]);
    25. int p3 = GetValueOfColor(buffer[(y - 1) * width + x + 1]);
    26. int p4 = GetValueOfColor(buffer[(y) * width + x + 1]);
    27. int p5 = GetValueOfColor(buffer[(y + 1) * width + x + 1]);
    28. int p6 = GetValueOfColor(buffer[(y + 1) * width + x]);
    29. int p7 = GetValueOfColor(buffer[(y + 1) * width + x - 1]);
    30. int p8 = GetValueOfColor(buffer[(y) * width + x - 1]);
    31. int p9 = GetValueOfColor(buffer[(y - 1) * width + x - 1]);
    33. if (p1 == 1 && 2 <= b && b <= 6 && a == 1
    34. && (p2 * p4 * p6 == 0)
    35. && (p4 * p6 * p8 == 0))
    36. {
    37. lpointsToChange.Add(new Point(x, y));
    38. hasChange = true;
    39. }
    40. }
    41. }
    42. }
    44. foreach (Point p in lpointsToChange)
    45. buffer[p.Y * width + p.X] = WHITE;
    47. lpointsToChange.Clear();
    49. for (int y = originY; y < originY + xWidth; y++)
    50. {
    51. for (int x = originY; x + 1 < originX + xWidth; x++)
    52. {
    53. a = getA(buffer, y, x, width, height);
    54. b = getB(buffer, y, x, width, height);
    56. if (y > 0 && y + 1 < height && x > 0 && x + 1 < width)
    57. {
    58. int p1 = GetValueOfColor(buffer[y * width + x]);
    59. int p2 = GetValueOfColor(buffer[(y - 1) * width + x]);
    60. int p3 = GetValueOfColor(buffer[(y - 1) * width + x + 1]);
    61. int p4 = GetValueOfColor(buffer[(y) * width + x + 1]);
    62. int p5 = GetValueOfColor(buffer[(y + 1) * width + x + 1]);
    63. int p6 = GetValueOfColor(buffer[(y + 1) * width + x]);
    64. int p7 = GetValueOfColor(buffer[(y + 1) * width + x - 1]);
    65. int p8 = GetValueOfColor(buffer[(y) * width + x - 1]);
    66. int p9 = GetValueOfColor(buffer[(y - 1) * width + x - 1]);
    68. if (p1 == 1 && 2 <= b && b <= 6 && a == 1
    69. && (p2 * p4 * p8 == 0)
    70. && (p2 * p6 * p8 == 0))
    71. {
    72. lpointsToChange.Add(new Point(x, y));
    73. hasChange = true;
    74. }
    75. }
    76. }
    77. }
    79. foreach (Point p in lpointsToChange)
    80. buffer[p.Y * width + p.X] = WHITE;
    82. lpointsToChange.Clear();
    84. } while (hasChange);
    86. return buffer;
    87. }
    89. private int GetValueOfColor(uint value)
    90. {
    91. return (value.GetBrightness() <= maxBrightness) ? 1 : 0;
    92. }
    94. private int getA(uint[] buffer, int y, int x, int width, int height)
    95. {
    96. // 1 = black 0 = white
    97. // helligkeitswerte 1-weiß 0-schwarz
    99. if (y > 0 && y + 1 < height && x > 0 && x + 1 < width)
    100. {
    101. int p2 = GetValueOfColor(buffer[(y - 1) * width + x]);
    102. int p3 = GetValueOfColor(buffer[(y - 1) * width + x + 1]);
    103. int p4 = GetValueOfColor(buffer[(y) * width + x + 1]);
    104. int p5 = GetValueOfColor(buffer[(y + 1) * width + x + 1]);
    105. int p6 = GetValueOfColor(buffer[(y + 1) * width + x]);
    106. int p7 = GetValueOfColor(buffer[(y + 1) * width + x - 1]);
    107. int p8 = GetValueOfColor(buffer[(y) * width + x - 1]);
    108. int p9 = GetValueOfColor(buffer[(y - 1) * width + x - 1]);
    110. int count = 0;
    112. //p2 p3
    113. if (p2 == 0 && p3 == 1) count++;
    114. //p3 p4
    115. if (p3 == 0 && p4 == 1) count++;
    116. //p4 p5
    117. if (p4 == 0 && p5 == 1) count++;
    118. //p5 p6
    119. if (p5 == 0 && p6 == 1) count++;
    120. //p6 p7
    121. if (p6 == 0 && p7 == 1) count++;
    122. //p7 p8
    123. if (p7 == 0 && p8 == 1) count++;
    124. //p8 p9
    125. if (p8 == 0 && p9 == 1) count++;
    126. //p9 p2
    127. if (p9 == 0 && p2 == 1) count++;
    129. return count;
    130. }
    131. else
    132. return 0;
    133. }
    135. private int getB(uint[] buffer, int y, int x, int width, int height)
    136. {
    137. if (y > 0 && y + 1 < height && x > 0 && x + 1 < width)
    138. {
    139. int p2 = GetValueOfColor(buffer[(y - 1) * width + x]);
    140. int p3 = GetValueOfColor(buffer[(y - 1) * width + x + 1]);
    141. int p4 = GetValueOfColor(buffer[(y) * width + x + 1]);
    142. int p5 = GetValueOfColor(buffer[(y + 1) * width + x + 1]);
    143. int p6 = GetValueOfColor(buffer[(y + 1) * width + x]);
    144. int p7 = GetValueOfColor(buffer[(y + 1) * width + x - 1]);
    145. int p8 = GetValueOfColor(buffer[(y) * width + x - 1]);
    146. int p9 = GetValueOfColor(buffer[(y - 1) * width + x - 1]);
    148. return p2 + p3 + p4 + p5 + p6 + p7 + p8 + p9;
    149. }
    150. else
    151. return 0;
    152. }


    Angaben zum Code:
    Gearbeitet wird mit einem uint-Array, welches die Farbwerte jeden Pixel beinhaltet.
    Dieses wird per LockBits erzeugt. (Die Zeit bis die Bitmap "gelockt" ist sind in den 15. Sekunden nicht enthalten)

    Anhang: Wie es später mal aussehen soll. (Nur damit man sich etwas drunter vorstellen kann)
    Bilder

    • wieesseinsoll.png

      6,24 kB, 930×316, 141 mal angesehen

    @LaMiy Mach die Schleifen for (int y = originY; y < originY + xWidth; y ++) mit Parallel.For().
    Summiere in getA und getB die Werte gleich auf.
    Was macht GetBrightness()?

    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!

    LaMiy schrieb:

    Paralell.For hatte ich schon versucht.
    Das bringt eigentlich immer was, die Frage ist, wie gut Du den Innenteil entkopelst.
    Was ist mit GetBrightness()?
    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!

    LaMiy schrieb:

    Was genau meinst du damit?
    Du musst eine Prozedur schreiben, die allein mit dem y-Wert als Parameter die innere Schleife abarbeitet. Gugst Du hier.
    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!

    Statt

    C#-Quellcode

    1. for (int y = a; y < b; y++)
    2. {
    3. for (int x = a; x < b; x++)
    4. {
    5. do(x, y);
    6. }
    7. }
    machst Du so was in der Art:

    C#-Quellcode

    1. Parallel.For (a, b, ACTION(do2));
    2. // ...
    3. do2(int y)
    4. {
    5. for (int x = a; x < b; x++)
    6. {
    7. do(x, y);
    8. }
    9. }


    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!

    ich versteh den Algo nicht, aber ich würde mir denken, da kann man etwas effizienteres schaffen, einfach vom Algo her, ohne unsafe code oder parallel.

    Nämlich die Flächen iwie nach dem Turtle-Prinzip bestimmen.
    Also nicht von oben nach unten und von rechts nach links abgrasen, sondern mit einer Turtle den Rand der Fläche entlanglaufen, und immer ein Pixel wegnehmen, bis nur noch eine Linie bleibt.

    Aber das ist jetzt nur ein Konzept, und die Ausarbeitung wird sicher enorm anspruchsvoll.

    also mal das Turtle-Prinzip angugge kannst du hier: [Sammelthread] Knobel-Aufgaben, knifflige Algorithmen, elegante Lösungen

    LaMiy schrieb:


    C#-Quellcode

    1. for (int y = originY; y < originY + xWidth; y++)
    2. {
    3. for (int x = originY; x + 1 < originX + xWidth; x++)
    4. {
    5. a = getA(buffer, y, x, width, height);
    6. b = getB(buffer, y, x, width, height);
    8. // hier her
    10. if (y > 0 && y + 1 < height && x > 0 && x + 1 < width)
    11. {
    12. int p1 = GetValueOfColor(buffer[y * width + x]);
    13. int p2 = GetValueOfColor(buffer[(y - 1) * width + x]);
    14. int p3 = GetValueOfColor(buffer[(y - 1) * width + x + 1]);
    15. int p4 = GetValueOfColor(buffer[(y) * width + x + 1]);
    16. int p5 = GetValueOfColor(buffer[(y + 1) * width + x + 1]);
    17. int p6 = GetValueOfColor(buffer[(y + 1) * width + x]);
    18. int p7 = GetValueOfColor(buffer[(y + 1) * width + x - 1]);
    19. int p8 = GetValueOfColor(buffer[(y) * width + x - 1]);
    20. int p9 = GetValueOfColor(buffer[(y - 1) * width + x - 1]);
    22. if (p1 == 1 && 2 <= b && b <= 6 && a == 1 // von hier nach oben
    23. && (p2 * p4 * p8 == 0)
    24. && (p2 * p6 * p8 == 0))
    25. {
    26. lpointsToChange.Add(new Point(x, y));
    27. hasChange = true;
    28. }
    29. }
    30. }
    31. }

    Wenn Du die Bedingung (2 <= b && b <= 6 && a == 1) unmittelbar nach Berechnung von a und b abtestest, muss im Negativ-Fall der ganze innere Kram gar nicht erst berechnet werden. :thumbsup:
    Und
    Berechne keine Zwischenwerte, die Du nicht brauchst: p3, p5, p7, p7.
    Kommentiere sie aus, da bleiben sie der Vollständigkeit halber sichtbar.

    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!