Pixelfeld in Bild finden



  • Hi,

    wie kann ich ein vorher definiertes Pixelfeld in einem Bild finden und dessen Position bekommen? Ich habe z.B. ein Bitmap und möchte die Position von einem roten 5x5 Pixel Feld finden. Wie gehe ich da am besten vor?

    MfG, Michael



  • du vergleichst dein bild pixelweise mit einer maske..



  • Hi,

    wie sieht dann so eine Maske aus? Weil ich kann ja immer nur einen Pixel vergleichen! Soll ich dann wenn der erste Pixel passt die Nachbarn vergleichen und so weiter? Gibt's da auch andere Möglichkeiten?

    MfG, Michael



  • du machst dir quasi ein bild von dem, was du finden willst und schiebst das pixelweise über dein suchbild



  • Wie sieht des dann programmtechnisch aus?

    -> Maske auf (0|0) lesen.
    -> Ersten Pixel der Maske mit entsprechendem Pixel des Bildes vergleichen.
    -> Passt das erste Pixel, dann den nächsten Pixel der Maske vergleichen. Wenn nicht Maske eins weiter schieben und wie vergleichen.

    So in etwa?

    MfG, Michael



  • ja



  • Ich würde in 5er-Schritten suchen (bei 5x5 Quadrat), dann bist du viel schneller. Also zuerst pixel (4,4), dann Pixel (9,4), dann (13,4) usw. bis zum ende (rechter rand) und dann weiter mit der nächsten Zeile (also 5 darunter) ... pixel (4,9), dann Pixel (9,9), dann (13,9) usw. und dann die nächste Zeile (also 5 darunter) usw bis zum Ende (rechte untere Ecke). Bei einem Treffer suchst du die direkte (zunächst max. 5 zusammenhängende Pixel) umgebung ab, ansonsten nicht. Ähnlich wie beim Schiffe versenken, falls du das kennst.

    Klar, wies gemeint ist? 😉

    Zum Verständnis:

    _ _ _ _ _ 0 0 0 0 0
    _ _ _ _ _ 0 0 0 0 0
    _ _ _ _ _ 0 0 0 0 0
    _ _ _ _ _ 0 0 0 0 0
    _ _ _ _ x 0 0 0 0 0
    0 0 0 0 0 0 0 0 0 0
    0 0 0 0 0 0 0 0 0 0
    0 0 0 0 0 0 0 0 0 0
    0 0 0 0 0 0 0 0 0 0
    0 0 0 0 0 0 0 0 0 0

    Nachdem x (4,4) kein Treffer ist kannst du die Pixel _ alle auschließen, deswegen der enorme Geschwindigkeitsvorteil.



  • das ist im grunde genau dasselbe wie einen suchstring in einem text finden

    einfach so pixel-pixel ueberpruefung ist ziemlich aufwendig, es gibt extra suchalgorithmen die um einiges schneller sind (worst case von jeden pixel einzeln vergleichen ist ne laufzeit von N*M wobei die 2 variablen für pixel im muster und pixel im suchbild stehen)

    schau dir mal knuth-morris-pratt an oder boyer-moore, die haben ne laufzeit von n+m

    knuth morris pratt ist nicht sooo kompliziert und um es zu implementieren muss man es sowieso nicht unbedingt verstehen, bei großen bildern und mustern macht das schon nen bemerkbaren unterschied



  • der KMP-Algo ist doch aber nicht wirklich nötig und sinnvoll, wenn sein Quadrat einfarbig ist, oder?



  • Hi,

    @Dust:

    der KMP-Algo ist doch aber nicht wirklich nötig und sinnvoll, wenn sein Quadrat einfarbig ist, oder?

    das mit dem roten Quadrat war nur ein Beispiel. In diesem Pixelfeld können auch verschiedene Farben vorhanden sein.

    @Vevusio:
    ich hab mir mal den knuth-morris-pratt Algo angeschaut. Find den eigentlich ganz gut, muss jetzt aber schauen wie ich des auf ein zweidimensionales Array übertrage. Die Beschreibungen, die ich bisher gefunden habe beziehen sich auf ein eindimensionales Array.

    MfG, Michael



  • Ein Such-Pattern für die erste Zeile und dann (bei Match) in den darunterliegenden Zeilen an die entsprechende Stelle und schauen obs passt.

    43785676547321
    65724657346376
    46736374537453

    die Ziffern stehen für Pixel verschiedener Farbe (gleiche Ziffer = gleiche Farbe)

    dein Bild:

    6765
    6573
    3745

    Hast du in der ersten zeile die 6765 gefunden, dann gucken obs darunter passt, wenn ja nächste Zeile usw. ansonsten weiter suchen, wenn du ohne erfolg die erste Zeile nach 6765 durchsucht hast (was hier nicht der Fall wäre) gehts in der 2. weiter ...

    Das als meine erste Idee... hab jetzt nicht länger als 2 min drüber nachgedacht ... aber sollte so funktionieren.


Log in to reply