Fläche in Bild finden

  • VB.NET

Es gibt 18 Antworten in diesem Thema. Der letzte Beitrag () ist von ErfinderDesRades.

    Fläche in Bild finden

    Moin, Moin,

    Ich möchte in einem Bild eine weiße Fläche mit bestimmter Größe finden (z.B. 100x30 px). An diese Stelle möchte ich später etwas zeichnen. Das bekomme ich hin.
    Mein Problem ist jetzt, dass meine momentane Methode seehr langsam ist. (Mehrere Sekunden für eine Zeile).

    Ich hoffe ihr könnt mi helfen einen Ansatz zu finden. ;)


    Gruß HamburgerJungeJr

    Hier mein bisheriger Code:

    VB.NET-Quellcode

    1. Dim MinBreite As Integer = 100
    2. Dim MinHöhe As Integer = 100
    3. it = New ImageTraverser(PictureBox1.Image)
    4. Dim c()() As Integer = it.ToArray()
    5. Dim Toleranz As Integer = CInt(765 * (1 - ((100 - 100) / 100)))
    6. Dim Frei As List(Of Point) = New List(Of Point)
    7. Dim Flächen As List(Of Point) = New List(Of Point)
    9. Fläche = New Rectangle(0, 0, MinBreite, MinHöhe)
    10. For Y = 0 To it.ImageHeight - 1
    11. For X = 0 To it.ImageWidth - 1
    12. Dim f As Color = Color.FromArgb(c(Y)(X))
    13. If CDbl(f.R) + CDbl(f.G) + CDbl(f.B) >= Toleranz Then
    14. Frei.Add(New Point(X, Y))
    15. End If
    16. Next
    17. Next
    19. Dim Arr() As Point = Frei.ToArray()
    20. For Y = Frei(0).Y To it.ImageHeight - Fläche.Height
    21. For X = 0 To it.ImageWidth - Fläche.Width
    22. 'Flächen = Frei.FindAll(Function(Punkt) Fläche.Contains(Punkt)) ' Alternative zu Arr.Count()
    23. If Arr.Count(Function(Punkt) Punkt.X >= Fläche.X And Punkt.Y >= Fläche.Y) = Fläche.Height * Fläche.Width Then
    24. Debug.Print("a")
    25. GoTo Abbruch
    26. Else
    27. Fläche.X = X
    28. End If
    29. Next
    30. Fläche.X = 0
    31. Fläche.Y = Y
    32. Next
    33. Abbruch:
    34. For Y = Fläche.Y To Fläche.Y + Fläche.Height
    35. For X = Fläche.X To Fläche.X + Fläche.Width
    36. it.SetPixel(X, Y, Color.Yellow)
    37. Next
    38. Next



    PS. Hoffe es gibt noch kein Thema dazu. Ich wusste nicht, nach was ich suchen soll. :D

    Moin,

    die Bitmap-Methoden sind sehr langsam. Schau dir mal das an: [Beta] FastGraphicsLib 1.0.0.5

    PS: GoTo's sind böse, entferne die bitte. Und warum bist du soviel am Casten?
    Mit freundlichen Grüßen,
    Thunderbolt

    Erstmal vielen Dank für Eure Antworten.

    @timmi31061

    Welche Bitmap-Methoden meinst du?
    Habe ich eine andere Möglichkeit Bytes zu addieren? Color.R/.G/.B gibt mir nur einen Byte zurück. Mit diesem Teil schaffe ich eine Toleranz zu reinem Weiß, da später gescannte Dokumente verarbeitet werden sollen.
    Wie kann ich statt mit Goto zwei Schleifen abbrechen?

    @ErfinderDesRades
    Der ImageTraverser ist eine Alternative zu den .Net Standard-Komponenten. (codeproject.com/Articles/18474/ImageTraverser)

    Gruß
    HamburgerJungeJr

    Jo, der ImageTraverser scheint dieselbe Idee der FastGraphicsLib umzusetzen - da wird letztere kaum Verbesserung bringen, und Bitmap.SetPixel tritt ja überhaupt nicht auf.

    ich sehe das ganze also nur als sehr knifflige Knobel-Aufgabe, wie man rechteckige zusammenhängende Flächen von ähnlichen Werten in einer 2D-Werte-Matrix ausbaldowert.

    Erster Schritt wäre halt eine vernünftige Funktions-Deklaration, etwa

    VB.NET-Quellcode

    1. Private Function GetAreas(it As ImageTraverser, minBrightness As Double, minSize As Size) As IEnumerable(Of Rectangle)
    Damit wären die Rahmenbedingungen gesteckt (eine von vielen Möglichkeiten, sie zu stecken), und dann darf geknobelt werden :D

    Ich knobel heut aber nicht mit, weil ich knobel grad was anneres ;)

    ich verstehe deinen Algo nicht.
    Zunächstmal sammelst du alle Punkte, die das Farb-Kriterium erfüllen, aber dann die Geschichte mit Array.Count() ist mir schleierhaft.

    ich täte iwie von jedem infragekommenden Punkt ausgehen, und ihn nach rechts und nach unten erweitern, und dabei prüfen, ob alle Erweiterungs-Punkte auch das Farbkriterium erfüllen.

    Weitere Optimierung wäre, die gefundenen Flächen aus den zu durchsuchenden Punkten zu entfernen.

    Guck mal, ich hab einen neuen Sammelthread eingerichtet: [VB.NET] [SammelThread] Knobel-Aufgaben, knifflige Algorithmen, elegante Lösungen

    Fände ich fabelhaft, wenn du dein Problem dort als Knobelei einstellst.
    Am besten natürlich gleich mit Test-Anwendung und Test-Bild, damit man als Knobler nicht erst die CodeProject-Dll runterladen muß, Anwendung aufsetzen, geeignetes Bild erstellen,... muß, bevors losgeht.

    HamburgerJungeJr schrieb:

    Gibt es irgendeine Methode eine Liste zu durchsuchen, die schneller ist, als meine?

    Nein. Eine Liste von Pixeln ist ungeordnet, weswegen du nicht binär suchen kannst. Du musst stattdessen linear suchen (= alles durchgehen). Mit ein paar Voraussetzungen kannst du das Ganze aber beschleunigen. Dazu habe ich ein paar Fragen:
    - Wie oft kommt die Fläche im Bild vor?
    --> Wenn mehr als einmal: Welches Vorkommen willst du finden?
    - Ist die Größe der Fläche immer bekannt?
    - Ist die Farbe der Fläche immer bekannt?
    - Ist die Fläche homogen, d. h. ist sie überall genau gleich gefärbt?
    - Ist die Fläche immer quadratisch / rechteckig / regelmäßig / gleich geformt?

    Um passende Kandidaten zu finden, reicht es, erst einmal nur jedes dritte Byte im Datenstrom zu betrachten (bei 24-Bit RGB). Wenn du randomisiert auf die Daten zugreifen kannst, kannst du randomisiert suchen und findest die Fläche im Erwartungswert nach (n / 6) Iterationen (n = Breite * Höhe des Bildes in Pixel). Das ist immer noch O(n) - besser wirds auch nicht. Aber die Konstante können wir unter 1/6 drücken, wenn die Fläche nur einmal vorkommt und alle der obigen Voraussetzungen erfüllt sind (ansonsten wirds schlechter). Für kleine Bilder ist das OK, für Gigapixel-Bilder natürlich nicht.
    Gruß
    hal2000

    Morgen @HamburgerJungeJr:
    Ich habe mich mal eben drangesetzt und eine Klasse gebastelt. Prinzip sollte klar sein. Du kannst die Klasse ja dann selber für dich erweitern.
    Funktioniert so dass du alle Pixel durchgehst bis du einen in deiner gewünschten Farbe findest, dann prüfst du ob die gewünschte Fläche an dieser Position ist. Wenn nicht gehst du weiter.

    Code

    VB.NET-Quellcode

    1. Option Strict On
    2. Imports System.Drawing.Imaging
    4. ''' <summary>
    5. ''' Stellt eine Klasse zum Suchen von bestimmten Feldern in einer Bitmap dar
    6. ''' </summary>
    7. Public Class BitmapObservation
    9. ''' <summary>
    10. ''' Speicher für die Bitmap
    11. ''' </summary>
    12. Public Property Bitmap As Bitmap
    14. ''' <summary>
    15. ''' Speicher für die Farbwerte
    16. ''' </summary>
    17. Private Values As Byte()
    19. Private BitmapData As BitmapData
    20. Private Ptr As IntPtr
    21. Private BytesPerPixel As Integer
    23. ''' <summary>
    24. ''' Stellt ein neues Objekt der Klasse dar
    25. ''' </summary>
    26. ''' <param name="b">Bitmap, in der gesucht werden soll</param>
    27. Public Sub New(ByVal b As Bitmap)
    28. If b Is Nothing Then Throw New ArgumentException()
    29. Me.Bitmap = b
    30. End Sub
    32. ''' <summary>
    33. ''' "Lockt" die Farbwerte im Bild
    34. ''' </summary>
    35. Public Sub LockBits()
    36. Dim rect As New Rectangle(0, 0, Me.Bitmap.Width, Me.Bitmap.Height)
    37. Dim bmpData As BitmapData = Me.Bitmap.LockBits(rect, Drawing.Imaging.ImageLockMode.WriteOnly, Me.Bitmap.PixelFormat)
    38. Dim ptr As IntPtr = bmpData.Scan0
    39. Dim bytes As Integer = Math.Abs(bmpData.Stride) * Me.Bitmap.Height
    40. Dim rgbValues(bytes - 1) As Byte
    41. System.Runtime.InteropServices.Marshal.Copy(ptr, rgbValues, 0, bytes)
    42. Me.Values = rgbValues
    43. Me.BitmapData = bmpData
    44. Me.Ptr = ptr
    45. If bmpData.PixelFormat = PixelFormat.Format24bppRgb Then
    46. Me.BytesPerPixel = 3
    47. Else
    48. Throw New NotSupportedException()
    49. End If
    50. End Sub
    52. ''' <summary>
    53. ''' Fügt das Ganze wieder zu einem Bild zusammen
    54. ''' </summary>
    55. Public Function UnlockBits() As Bitmap
    56. System.Runtime.InteropServices.Marshal.Copy(Me.Values, 0, Ptr, Me.Values.Length)
    57. Bitmap.UnlockBits(Me.BitmapData)
    58. Return Bitmap
    59. End Function
    61. Public Function SearchRectangle(c As Color, width As Integer, height As Integer) As Rectangle
    62. Dim result = Me.SearchRectangleHandler(c, width, height)
    63. For y = result.Y To result.Y + result.Height
    64. For x = result.X To result.X + result.Width
    65. 'Farbig markieren
    66. Dim pisiton As Integer = y * BitmapData.Width * Me.BytesPerPixel + x * Me.BytesPerPixel
    67. Me.Values(pisiton) = 100
    68. Me.Values(pisiton + 1) = 1
    69. Me.Values(pisiton + 2) = 100
    70. Next
    71. Next
    72. End Function
    74. Private Function SearchRectangleHandler(c As Color, width As Integer, height As Integer) As Rectangle
    75. 'Boolean um zu speichern ob etwas gefunden wurde
    76. Dim flag As Boolean = True
    77. 'Position wo etwas gefunden wurde
    78. Dim position As Point = New Point(-1, -1)
    79. 'Alle Pixel durchgehen
    80. For y = 0 To Me.BitmapData.Height - 1
    81. For x = 0 To Me.BitmapData.Width - 1
    82. 'Farbe an der aktuellen Position holen
    83. Dim pos As Integer = y * Me.BitmapData.Width * Me.BytesPerPixel + x * BytesPerPixel
    84. Dim color As Color = color.FromArgb(Values(pos + 2), Values(pos + 1), Values(pos))
    85. If color.ToArgb() = c.ToArgb() Then
    86. 'Hier wird geprüft ob der erwartete Endpunkt auch die richtige Farbe hat.
    87. 'Oftmals hat er das nicht deshalb sparst du viel an Zeit
    88. '(Gut wäre es das auch für das rechte und untere Ende zu machen)
    89. Dim boundPos As Integer = (y + height) * Me.BitmapData.Width * Me.BytesPerPixel + ((x + width) * Me.BytesPerPixel)
    90. If Not color.FromArgb(Values(boundPos + 2), Values(boundPos + 1), Values(boundPos)).ToArgb() = c.ToArgb() Then
    91. Exit For
    92. flag = False
    93. End If
    94. 'Alle Pixel, die übereinstimmen sollen absuchen und
    95. 'gucken ob sie auch übereinstimmen
    96. For yStep = y To y + height
    97. For xStep = x To x + width
    98. Dim newPos = yStep * Me.BitmapData.Width * Me.BytesPerPixel + xStep * BytesPerPixel
    99. Dim actualColor As Color = color.FromArgb(Values(newPos + 2), Values(newPos + 1), Values(newPos))
    100. If actualColor.ToArgb() <> c.ToArgb() Then
    101. flag = False
    102. Exit For
    103. Else
    104. End If
    105. Next
    106. Next
    107. 'Wenn die Suche erfolgreich war den gefundenen Abschnitt zurückgeben
    108. If flag = True Then Return New Rectangle(x, y, width, height) Else flag = True
    109. End If
    110. Next
    111. Next
    112. End Function
    113. End Class

    Aufruf

    VB.NET-Quellcode

    1. Private Sub Form1_Load(sender As Object, e As EventArgs) Handles MyBase.Load
    2. Dim bo As New BitmapObservation(CType(Bitmap.FromFile("C:\Users\Alexander\Pictures\test.png"), Bitmap))
    3. bo.LockBits()
    4. bo.SearchRectangle(Color.White, 100, 110)
    5. PictureBox1.Image = bo.UnlockBits()
    6. End Sub


    Viel Spaß beim Rumprobieren :)
    Ob das auch mit ARGB Format klappt weiß ich gerad' nicht.
    (PS: Das Lila Feld ist das gefundene)
    Achja, das hier kann ich dir nur an's Herz legen :p [VB 2010] Tutorial: LockBits
    Bilder

    • find.png

      5,25 kB, 801×449, 130 mal angesehen

    • test.png

      2,34 kB, 980×522, 128 mal angesehen

    Vielen Dank für eure Antworten.

    Ich war für einige Zeit mit anderen Projekten beschäftigt, sodass ich erst jetzt auf dieses Problem zurückkommen konnten.

    Ich hatte mir inzwischen auch noch einige Gedanken gemacht und bin auf folgender Lösung gekommen. (Anhang)

    Falls jemand Verbesserungsvorschläge hat. Ich bin offen für Anregungen.


    Gruß
    HamburgerJungeJr
    Dateien

    • PDFTest.zip

      (443,7 kB, 123 mal heruntergeladen, zuletzt: )

    HamburgerJungeJr schrieb:

    die schneller ist, als meine?
    Das Zauberwort heißt Bildverarbeitung.
    da ist VB.NET leider etwas hinterher.
    LockBits ist ganz nett, aber letztenendes nicht wirklich hilfreich.
    In C# gibt es unsave Code, in C++ kannst Du gleich mit Pointernm über das Bild sausen.
    Wenn Du zeilenweise arbeiten kannst und Dein Algorithmus entsprechend parallelisierbar ist, gugst Du Parallel.For.
    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!

    nein, das kommt v.a. aufs konzept an.
    Die aufgabenstellung ist doch total unklar. Etwa in einem Rechteck mit abgerundeten Ecken kann man hunderte von Rechtecken drin finden - die sich halt überlappen. Soll da iwie das nächtbeste genommen werden, oder das größtmögliche? Oder ist ein bestimmtes Seitenverhältnis Vorgabe?
    (Ah - nach Wortlaut ist eine Minimal-Größe beabsichtigt - aber da haben wir bei mehreren Treffern wieder das Problem, welches genommen werden soll, und bei sich überlappenden Treffern dasselbe Problem hundertfach.)
    Sind bei der Farbe Toleranzen zulässig?
    Was fängt man mit einem Rechteck an, was vlt 3 Pix hoch ist, dafür aber 1000pix breit?

    Solche Sachen sind das Thema

    Als Sprache nehme man die, die der Entwickler am besten kann - ansonsten gelten mal wieder die Rules Of Optimization

Facebook
Telefonspende