Algorithmen zur Erkennung von Farb- und Graustufenbereichen in Bildern gesucht...

[Frogger]

Hallo

Im Ramen einer Studienarbeit soll ich ein Programm schreiben das in eingelesenen Bildern zusammenhängende Farb-oder Grautonbereiche/Bezirke erkennt. Wenn es in einem eingelesenen Bild z.B. Flächen gibt die man mit dem bloßen Auge voneinander unterscheiden würde anhand eines bestimmten Farbtons oder der Helligkeit, dann soll mein Programm diese Flächen erkennen. D.h. Innerhalb einer Fläche können sich die Pixel in ihrer Helligkeit und in ihrem Farbton zwar unterscheiden , aber falls es auffällige Häufungen von Pixeln mit ähnlicher Helligkeit oder ähnlicher Farbe an bestimmten Stellen des Bildes geben sollte, sollen diese Pixel zu "Flächen" zusammengefasst werden.

Ich habe mir zwar einige Ansätze überlegt wie so etwas funktionieren könnte und schon ein bischen damit experimentiert, hatte auch schon Teilerfolge, aber so richtig ausgereift ist es noch nicht. Ich würde mich freuen wenn mir vielleicht jemand einen Hinweis geben könnte, ob es für solche Aufgaben irgendwelche Standart-Algorithmen gibt. So etwas richtig spezielles habe ich bisher noch nicht gefunden ...

Kann mir da jemand weiterhelfen ?

 

[SilentWarrior]

Naja, also, wir haben sowas ähnliches mal gemacht. Der Standardansatz ist wohl der, dass du einen bestimmten Punkt nimmst, dann gehst du rekursiv nach oben, rechts, links, unten und checkst, ob die Farbe noch akzeptabel ist. Wenn ja, gehst du weiter, wenn nicht, Abbruch. Das machst du solange, bis es nicht mehr weitergeht. Dann suchst du (bzw. der Algorithmus ) sich einen neuen, noch unbesuchten Pixel, und macht dort weiter.

Aber ich nehme an, sowas ähnliches hattest du auch selbst schon, oder? Bestimmt gibt es da noch Optimierungspotenzial (Laufzeit ist wenn ich mich recht entsinne O(?n)).

 

[Tobias Menzel]

Hi,

Google mal nach FloodFill - sollte das sein, was Du brauchst. Du kannst das Bild vorher durch einen Filter jagen, der die Farbwerte quantisiert, oder (wie SilentWarrior sagte) direkt beim "flooden" eine gewisse Toleranz an den Tag legen.

Gruß
.

 

[Frogger]

Zunächst einmal danke für die Antworten.

Im Moment weiß ich noch nicht wie stark bei den Bildern für die das Programm später gebraucht wird die Farbwerte von Pixeln innerhalb eines "Bereichs" abweichen können, deshalb hatte ich die Idee zu einem Algorithmus wie ihr ihn beschreibt erst einmal verworfen weil ich mir vorstellen könnte daß es damit probleme gibt wenn die "Unordnung" in einem Farbbereich besonders groß ist. Z.B. wenn ich jetzt von einem Pixel mit einem Hellen Rot-Ton ausgehend die Nachbarpixel absuche und dabei auf einen oder mehrere dunkelrote Pixel stoße, dann gibt es zwei mögliche Fälle und der Algorithmus hat nicht genug Informationen über das gesamte Bild um zu entscheiden: gehört der Pixel zu einem anderen Bereich der insgesamt in einem dunkleren rot-Ton gefüllt ist , oder gehört der Pixel noch zur selben Fläche in der etwas mehr "Unordnung" bei den rot-Tönen herrscht.

Deshalb habe ich im Moment einen anderen Ansatz. Ich "verwische" das Bild ein Wenig (bilde zu jedem Pixel durchschnittswerte mit den unmittelbaren Nachbarn) damit die Ähnlichkeit der Pixelfarben in einer zusammengehörigen Fläche größer wird. Dann trenne ich die Farbinformationen (Rot-,Grün-,und Blauanteil) der Pixel und bilde für jede Farbinformation Klassen in vierer-schritten. (Indem ich z.B. sage: die Pixel mit einer Grünkomponente von 40 bis 43 gehören in eine gemeinsame Grün-Klasse) .Jeder Pixel hat jeweils eine Zugehörigkeit in einer Rot- einer Grün- und einer Blau-Klasse. Dann betrachte ich nur noch die Klassen und wie häufig sie von Pixeln belegt sind. Dann suche ich die am stärksten belegte "dominante" Klasse und gehe davon aus daß auf beiden Seiten des Spektrums benachbarte Klassen zum selben Bereich gehören solange deren Häufigkeit der Belegungen im Vergleich zur dominanten Klasse stetig abnimmt. Wenn der Algorithmus auf zunehmend "stärker belegte" nachbarn stößt gehe ich davon aus daß diese zu einem neuen Bereich gehören ... schwer in Worten zu erklären , aber so ungefähr habe ich das implementiert, es funktioniert oft ganz gut aber nicht immer.

Naja , morgen bekomme ich die ersten typischen Testbilder und weiß dann sicher auch besser worauf ich mich einstellen muss ... vielleicht reicht die einfachere Vorgehensweise doch aus daß man bei einem Pixel anfängt nach allen Seiten zu suchen.