Bildverarbeitung: Segmentierung

Hallo Leute,

ich arbeite gerade an meiner Diplomarbeit, und bin auf ein Problem gestoßen...


Ich möchte ein Bild segmentieren, wie z.B. dieses:
Bild hier  

Ein buntes Schachbrettmuster, projiziert von einem Beamer und aufgenommen mit einer ganz normalen Kamera. Und was ich jetzt brauche sind die einzelnen Felder, im einfachsten Fall als S/W-Bild bei dem alle Felder weiß sind, getrennt durch schwarze Linien.


Noch ein paar Worte zu dem verwendeten Muster:

1. Die Helligkeit ist idealerweise konstant, und die Sättigung zumindest annähernd. Die Felder unterscheiden sich also im wesentlichen durch ihren Farbwinkel.

2. Die Differenz der Farbwinkel zweier senkrecht oder waagerecht benachbarter Felder beträgt immer entweder 120° oder 240°.


Naja, ich möchte das Bild also segmentieren, und dabei möglichst unabhängig von Sättigung und Helligkeit bleiben. Daher habe ich das Bild zunächst mal nach HSI umgewandelt, und mich bei der Weiterverarbeitung auf den H-Kanal beschränkt. Da der aber Phasensprünge enthält (360° -> 0°) die bei der Verarbeitung stören, habe ich den H-Kanal wieder in ein RGB-Bild konvertiert.

Dieses Bild sieht dann so aus:
Bild hier  


Der nächste Schritt war dann die Berechnung von Gradientenbildern für R, G und B. Und weil ich nur ein einziges brauche, werden die dann noch zu einem Bild verrechnet (für jeden Pixel wird von den 3 Werten jeweils der größte verwendet).

Wenn das dann fertig ist sieht es so aus:
Bild hier  


Das Bild zu segmentieren ist dann zwar immernoch nicht trivial, aber es ist machbar.




So, und jetzt kommt mein eigentliches Problem...
die Methode funktioniert nämlich nicht mehr sobald irgendein farbiges Objekt mit auf dem Bild ist, da dadurch der Farbwinkel des projizierten Musters verfälscht wird.

Hier mal ein Beispiel mit einem gelben Blatt Papier, wie man sieht ist das resultierende Gradientenbild de facto nicht zu gebrauchen.
Bild hier  
Bild hier  
Bild hier  



Also, wie kann ich solche Bilder zuverlässig segmentieren?
Ich habe zwar reichlich Lektüre zu dem Thema im Internet gefunden, aber die verschiedenen Algorithmen werden immer nur ganz grob umschrieben, was die Sache nicht unbedingt erleichtert. Außerdem kostet es zu viel Zeit unterschiedliche Segmentierungsalgorithmen zu implementieren, von denen ich nichtmal weiß ob sie überhaupt für Bilder dieser Art geeignet sind.

Leider verfügt Matlab nur über eine einzige Segmentierungsfunktion, und die arbeitet nach dem Watershed-Algorithmus. Dummerweise bringt mir diese Funktion aber rein garnichts, da ja schon die Vorverarbeitung bei farbigen Objekten fehlschlägt.


Optimal wären für mich jetzt natürlich Programme die unterschiedliche Segmentierungsalgorithmen beherrschen, so daß ich den auswählen kann der für meine Anwendung optimal geeignet ist. Aber auch nach inzwischen bestimmt schon 10-12 Stunden intensiven googelns, habe ich noch nichts derartiges gefunden.


Es ist auch recht frustrierend, daß ich zwar alles über das Muster weiss was es zu wissen gibt, dieses Wissen bei der Segmentierung aber bisher nicht einsetzen konnte. (je mehr Informationen man hat, desto effizienter sollte man die Bilder ja auch segmentieren können)



Naja, vielleicht fällt euch ja irgendwas dazu ein...


Gruß,
Felix

Felix,

ich habe sowas noch nicht gemacht, habe mich aber etwas mit der Theorie der Bildverarbeitung beschäftigt. Insofern musst Du, was ich hier schreibe, als "educated guess" betrachten. -

Das s-w-Kästchenmuster, das Du nach der (ich nehme Laplace) Filterung bekommst, ist hochgradig periodisch. Der Gegenstand, der sich in Dein Bild geschoben hat, modifiziert die Periode des Musters nur wenig, dafür aber umso mehr die Phase.

Da bietet es sich an, eine komplexe(!) Fouriertransformation anzuschliessen. Danach nur den Phasenanteil (also den Imaginärteil) in den Ortsraum zurücktransformieren. Das Bild, das Du so erhältst, hat nur noch die halbe Auflösung weil Du die reelle Hälfte der Daten nicht verwendet hast. Dafür bekommst Du ein Muster, das Dir die Bereiche mit Phasenverschiebung anzeigt.

Das könnte hinhauen, glaube ich.

mare_crisium

Also um die Gradientenbilder zu errechnen nehme ich keinen Laplace, sondern ich filtere zweimal mit dem Sobel-Operator (einmal in x, einmal in y, und die beiden Bilder werden dann über sqrt(x^2 + y^2) kombiniert), aber im Endeffekt sollte das ja keinen allzu großen Unterschied machen...


Dein Vorschlag klingt interessant, aber wenn ich dich richtig verstehe soll ich die FT auf das Gradientenbild anwenden? Aber das ist ja schon "kaputt" wenn man so will, denn da wo das gelbe Objekt den Farbwinkel verfälscht sind die Kästchen im Gradientenbild nicht mehr als solche zu erkennen.

Naja, versuchen werde ich es auf jeden Fall, das Ergebnis poste ich dann hier.

Gruß,
Felix

Ok, also wenn man die Phase zurücktransformiert, sieht das Ergebnis so aus:

Bild hier  


Ich habe bei der Segmentierung inzwischen schon einigermaßen akzeptable Ergebnisse erzielt, indem ich nicht vom Farbkanal sondern vom Originalbild den Gradienten gebildet habe. Leider ist die Segmentierung so aber nicht mehr unabhängig von Helligkeit und Sättigung, was mich natürlich stört.

Felix,

wie gesagt, es war eine Vermutung, die, leider, wie Du nachgewiesen hast, nicht funktioniert. Umso mehr freut's mich, dass Du einen anderen Weg gefunden hast. - Ehrlich gesagt, in der Rücktransformation der Phase hätte ich mehr Kontrast erwartet.

mare_crisium

Wie wäre es drei Kreuzkorrelationen über das Ursprungsbild laufen zu lassen: Je eine mit einem Kästchen in R,G,B als Pattern. Die gefundenen Mittelpunkte sind da die Punkte passender Korrelation.

Mit Korrelation habe ich es schon versucht, leider kann das Muster aber auch mehr oder weniger stark verzerrt sein, und dann funktioniert das nicht mehr (selbst bei einem sehr guten Bild funktioniert diese Methode nur mäßig).


Ich habe inzwischen allerdings dennoch ganz ordentliche Resultate bei der Segmentierung, selbst bei ziemlich schwierigen Bildern. Wie bereits erwähnt ist die Helligkeit (Summe aus R, G und B) des Musters annähernd konstant, diese Eigenschaft hatte ich bisher allerdings nicht wirklich genutzt.

Die Lösung ist also ganz einfach das Originalbild durch die Summe der 3 Farbkanäle zu dividieren, das Resultat ist dann ein Bild ohne Helligkeitsunterschiede, was die Segmentierung erheblich zuverlässiger macht (gegenüber der direkten Segmentierung des Originalbilds).


Von diesem Bild ausgehend mache ich es dann so wie bisher, ich berechne ein Gradientenbild und versuche es zu segmentieren. Leider habe ich dabei aber noch immer das alte Problem, daß Matlab nur den Watershed Algorithmus beherrscht, und ich denke daß der für diese spezielle Aufgabe nicht die beste Lösung ist.


Mein Problem hat sich also nicht grundlegend geändert, ich bin imernoch auf der Suche nach einem geeigneten Segmentierungsalgorithmus den ich entweder auf das vorverarbeitete Farbbild oder auf das Gradientenbild anwenden kann.

Sofern das Muster immer noch viereckig ist, sollte das aber klappen. Es wird eigentlich erst dann kompliziert, wenn die Verzerrung nicht über das Bild hinweg konstant ist.

Wenn Du einfach ein Weisses oder Schwarzes Feld nimmst und über das Originalbild per Kreuzkorr laufen lässt sollten sich Minimal nud Maxima ergeben, die in den Zentren der jeweilgen Felder liegen. Durch angenommen die Felder sind rechteckig, kannst Du dann die Feldgrenzen Interpolieren. An dieser Stelle kannst Du in einem der Farbkanäle per LoG und anschließende Nullstellensuche den Kantenpunkt ermitteln.

Felix,

kannst Du nochmal an einem Beispiel zeigen, wie das "durch die Summe der RGB-Kanäle dividierte" Bild und das Gradientenbild aussieht? Meines Wissens berechnet sich der Grauwert eines Bildpunktes aus den RGB-Werten nach

Grauwert = 0,299R + 0,584G + 0,114B (siehe Wikipedia)

Demnach liefe Deine Berechnung auf den Wert

Y = 0,299/(G+B) + 0,584/(R+B) +0,114/(R*G)

hinaus. Dass der Kontrast dabei nicht so gross ist, kann ich mir vorstellen. Mir ist unklar, wie Du trotz des flauen Kontrastes zu einem akzeptable (d.h. rauscharmen) Gradientenbild kommst.

mare_crisium

wenn du einfach eine pixelersetzung drüberlaufen lässt erst in x dann in y richtung sollte so aussehen :
[ 1 0 -1]
und
[1
0
-1]
sollten die kanten doch hervorgehoben werden ?

oder eine fouriertransformation (fft ) und dann einen "spaltförmigen" filter drüber...

das mit dem gradient sollte allerdings auch gehen, .. was passiert denn wenn du ein RGB bild hast und jeweils den gradienten für jeden kanal bildest? dann sollt die summe der 3 ergebnisse das gesuchte gitter sein...

Zitat:

---

Zitat von ogni42

Sofern das Muster immer noch viereckig ist, sollte das aber klappen. Es wird eigentlich erst dann kompliziert, wenn die Verzerrung nicht über das Bild hinweg konstant ist.

---

Leider wird aber genau das nahezu immer der Fall sein. Die Größe der Kästchen kann mehr oder weniger stark variieren, und die Verzerrungen können je nach Position auch unterschiedlich ausfallen.

Zitat:

---

Wenn Du einfach ein Weisses oder Schwarzes Feld nimmst und über das Originalbild per Kreuzkorr laufen lässt sollten sich Minimal nud Maxima ergeben, die in den Zentren der jeweilgen Felder liegen. Durch angenommen die Felder sind rechteckig, kannst Du dann die Feldgrenzen Interpolieren.

---

Wenn sie wirklich alle noch genau rechteckig wären ja, aber im allgemeinen Fall muss man eher von Trapezen oder Parallelogrammen ausgehen.

Zitat:

---

kannst Du nochmal an einem Beispiel zeigen, wie das "durch die Summe der RGB-Kanäle dividierte" Bild und das Gradientenbild aussieht?

---

natürlich...

ich habe hier mal ein Beispielbild, das dazugehörige Summenbild (R+G+B), das durch die Division entstandene korrigierte Bild, und das aus diesem korrigierten Bild gewonnene Gradientenbild. Damit User ohne DSL nicht gar zu sehr gequält werden, gibt es diese Bilder (obwohl ich sie schon etwas verkleinert habe) diesmal nur als Links :wink:

1. Original
2. "Helligkeit"
3. korrigiertes Bild
4. Gradient

Zitat:

---

Meines Wissens berechnet sich der Grauwert eines Bildpunktes aus den RGB-Werten nach

Grauwert = 0,299R + 0,584G + 0,114B (siehe Wikipedia)

---

Naja, ich denke die Frage ist einfach wie man Helligkeit definiert...
ich habe das Bild in den HSI-Farbraum umgewandelt, und da war die Definition I=R+G+B. Letztendlich entspricht das auch am besten den Eigenschaften die das Muster ohnehin schon hat, denn die Summe aller 3 Kanäle ist überall 1 (bedingt durch den Beamer und die Kamera stimmt das natürlich nicht mehr 100%ig).

Zitat:

---

wenn du einfach eine pixelersetzung drüberlaufen lässt erst in x dann in y richtung sollte so aussehen :
[ 1 0 -1]
und
[1
0
-1]
sollten die kanten doch hervorgehoben werden ?

---

Klar, sowas ähnliches mache ich ja auch...

dein Beispiel sieht mir nach einem Prewitt-Operator aus, ich verwende den sog. Sobel-Operator:

Code:

---

1 0 -1
2 0 -2
1 0 -1

---

der funktioniert fast genauso, nur daß er das Ergebnis in Kantenrichtung nochmal ein bischen glättet.

Zitat:

---

das mit dem gradient sollte allerdings auch gehen, .. was passiert denn wenn du ein RGB bild hast und jeweils den gradienten für jeden kanal bildest? dann sollt die summe der 3 ergebnisse das gesuchte gitter sein

---

Das mache ich doch...
mit dem Unterschied daß ich nicht die Summe der 3 Gradientenbilder verwende, sondern das Maximum.

Felix,

danke für die Bilder - die haben mir Dein Problem viel anschaulicher gemacht!

Du projizierst ein räumlich periodisches Lichtmuster, nennen wir's mal ein Lichtraster, auf eine Oberfläche. Dann machst Du ene Abbildung der Projektion. Auf der Aufnahme verzerren Oberflächenrelief und Perspektive das Raster. Du willst aus Verzerrung des Lichtrasters, dessen originale Helligkeitsverteilung Du ja kennst, auf das Oberflächenrelief zurückschliessen. Stimmt's so?

Angenommen Du projizierst das Lichtraster auf eine ebene Fläche und fotographierst das Ganze. Dann kannst Du mit einer einfachen Transformation des Rasters die Helligkeitsverteilung im Bild berechnen. - Dann projizierst Du das Raster auf eine Oberfläche mit Relief und machst wieder eine Aufnahme. Im Vergleich zur ersten Aufnahme haben sich hier die Mitten der Rasterpunkte verschoben und verformt. -

Du hast eine bekanntes Helligkeitsmuster, das sich verformt... - Bei so einer Aufgabenstellung denke zuerst an den "optical flow"-Algorithmus. Kennst Du den?

Es könnte aber auch so gehen: Stell Dir das Lichtraster als ein Bündel einzelner Strahlen vor (wie ein Bündel Salzstangen), die vom Objektiv des Beamers zum Objekt gehen. Aus dem Foto der ebenen Fläche weisst Du, wo auf dem Bild jeder einzelne Strahl auf die Ebene fällt. Du kannst sie direkt nummerieren. Dann guckst Du auf der zweiten Aufnahme (der mit dem Relief) wo Lichtstrahl Nr. X seinen Fleck erzeugt hat und berechnest daraus einen Verschiebungsvektor. Dieses Verschiebungsfeld sollte nur da Brüche (Unstetigkeiten) aufweisen, wo ein Oberflächenobjekt aufhört und ein neues anfängt. Das wäre dann die Segmentierung. - Du kannst aber das Verschiebungsfeld mit einer umgekhrten Perspektiven-Transformation auch direkt in ein Relief umrechnen.

Was meinst Du?

mare_crisium

Zitat:

---

Zitat von mare_crisium

Du projizierst ein räumlich periodisches Lichtmuster, nennen wir's mal ein Lichtraster, auf eine Oberfläche. Dann machst Du ene Abbildung der Projektion. Auf der Aufnahme verzerren Oberflächenrelief und Perspektive das Raster. Du willst aus Verzerrung des Lichtrasters, dessen originale Helligkeitsverteilung Du ja kennst, auf das Oberflächenrelief zurückschliessen. Stimmt's so?

---

So ähnlich, ja...
also es geht hier um aktive Triangulation (3D-Bilderfassung), wobei mich nur die Verschiebung der einzelnen Kästchen in X-Richtung interessiert (identifiziert werden die Kästchen durch ihre Farbe).

Zitat:

---

Angenommen Du projizierst das Lichtraster auf eine ebene Fläche und fotographierst das Ganze. Dann kannst Du mit einer einfachen Transformation des Rasters die Helligkeitsverteilung im Bild berechnen. - Dann projizierst Du das Raster auf eine Oberfläche mit Relief und machst wieder eine Aufnahme.

---

Und genau da liegt das Problem...
idealerweise sollten alle notwendigen Informationen aus einer einzigen Aufnahme gewonnen werden. Zusätzliche Aufnahmen sollen nur dann gemacht werden, wenn sich entweder die Position der Kamera relativ zum Beamer ändert, oder wenn eines der beiden Geräte durch ein anderes Modell ersetzt wird. In diesem Fall kann (bzw. muss) zu Justagezwecken ein Feld mit Passmarken aufgenommen werden, deren Abstände bekant sind. Solange sich am System selbst aber nichts ändert, soll für jedes Objekt eine einzige Aufnahme genügen (dadurch wird man nicht auf einen Beamer/Webcam-Aufbau beschränkt sein, sondern kann z.B. genausogut auch einen Diaprojektor in Kombination mit einer Spiegelreflexkamera verwenden).


Mit Verfahren die mehr als eine Aufnahme benötigen kann ich daher leider nichts anfangen :(



Ich muss also weiterhin versuchen entweder Bild 3 oder Bild 4 aus meinem letzten post zu segmentieren (wobei natürlich möglichst nicht allzu viele "falsche" Segmente entstehen sollten, also solche die nicht einem Kästchen entsprechen).

im prinzip ist das problemdoch, dass das bild bei der transformation von 1 nach 3 "kaputt geht" .? oder sehe ich das fasch.
mit dem sobel operator ist das ansosnten ja schon korrekt.
wie sieht denn das ergebnis aus, wenn du die gradientenbildung gleich auf das erste bild anwendest ? (ohne helligkeitsausgleich )
musst du dieses seltsame hippie-muster verwenden, oder darfst du auch andere projektionsmuster benutzen ?

Wieso kaputt?
Die Division sorgt doch nur dafür daß keine störenden Helligkeitsunterschiede mehr vorhanden sind. Ich wage mal zu behaupten, daß die einzelnen Felder des Musters auf dem korrigierten Bild wesentlich besser zu erkennen sind als auf dem Originalbild.

Auch den Gradient vom Originalbild würde ich jetzt mal rein subjektiv schlechter einschätzen als den Gradient vom korrigierten Bild.


Das Muster selbst ist auf meinem Mist gewachsen, und ich könnte es natürlich ändern, sofern du einen Vorschlag dazu hast.

In der Form wie es jetzt ist hat es halt einige vorteilhafte Eigenschaften...
so ist z.B. die Summe der 3 Farbkanäle konstant, die Farbwinkel zweier benachbarter Felder unterscheiden sich grundsätzlich um 120°, und aus einem 4er Block kann man jeweils die Farbe des Objekts an dieser Stelle bestimmen (da die Felder in Kombination etwa wie eine weiße Beleuchtung wirken).

kaput desswegen weil die vergrösserung bzw verkleinerung der kästchen bei diesem schritt passiert: siehe oben bei dem geben blatt.. der gradient tut dannach ja immer noch was er soll, nur sind eben die kästchen verzerrt...

was wäre der nachteil, wenn du direkt ein gitter draufprojezierst.. ? bzw ein schwarz/weisses streifenmuster
wird in der messtechnik zum vermessen von 3d objekten auch so geamcht...

Naja, die einfachste Variante zur 3D-Bilderfassung wäre tatsächlich die sog. Streifenprojektion

Man muss die Streifen aber voneinander unterscheiden können, weshalb bei der Streifenprojektion eine mehr oder weniger lange Sequenz unterschiedlicher Streifenmuster benötigt wird.


Mein Hauptziel ist aber ein Verfahren daß mit einem einzigen Bild auskommt, und da muss man die Streifen (oder in meinem Fall eben die Kästchen) auf irgendeine andere Art identifizieren (daher habe ich mich dazu entschieden, die Koordinaten der Kästchen in ihrer Farbe zu codieren).

Zitat:

---

kaput desswegen weil die vergrösserung bzw verkleinerung der kästchen bei diesem schritt passiert: siehe oben bei dem geben blatt.. der gradient tut dannach ja immer noch was er soll, nur sind eben die kästchen verzerrt...

---

bei meinem ersten Beispiel verwende ich diese Division doch garnicht...
damit habe ich erst bei der Sonne angefangen

wenn ich das richtig verstanden habe, willst Du die Verformung eines Kästchens berechnen?

Wenn ja, dann kannst findest Du im Original grob die Position einer Kante über den Farbwechsel (von einem Kästchen zum nächsten), im Gradientenbild (aus dem I-Kanal gebildet) kannst Du dann die Kante genau bestimmen (die Start- und Endpunkte für die Suche sind dann ja bekannt). Da Du die Position der Kamera und die Größe eines unverzerrten Kästchens kennst, kannst Du die x-Verschiebung bestimmen.

Soweit, so gut. Deine ursprüngliche Frage war ja, wie kommst Du zu der Kante, wenn Dein Objekt (ein)farbig ist? Im Bild des ersten Postings ist ja zu erkennen, dass die Position der Sobel-Kante verschwimmt. Daher mein Vorschlag mit LoG (Laplacian of Gaussian) zu Filtern und dann den Wendepunkt (Wechsel des Vorzeichens) zu bestimmen. Die Maske würde ich allerdings mindestens 5x5, besser 7x7 wählen und mit floats arbeiten. Dann wird die Position erheblich genauer (i.d.R. besser als ein Pixel)

Zitat:

---

wenn ich das richtig verstanden habe, willst Du die Verformung eines Kästchens berechnen?

---

Die Verformung ist für mich eigentlich eher ein unangenehmer Nebeneffekt, mich interessieren hauptsächlich die Positionen der Kästchen.

optimal wäre für mich wie gesagt ein Bild auf dem alle Kästchen weiß sind, getrennt durch 1px breite schwarze Linien.

Zitat:

---

Wenn ja, dann kannst findest Du im Original grob die Position einer Kante über den Farbwechsel (von einem Kästchen zum nächsten), im Gradientenbild (aus dem I-Kanal gebildet) kannst Du dann die Kante genau bestimmen (die Start- und Endpunkte für die Suche sind dann ja bekannt).

---

Also du meinst ich soll überall dort wo der Gradient des Originalbilds "hell" ist (=Kante) nochmal in einem kleineren Ausschnitt die genaue Position der Kante bestimmen?

Versuchen könnte ich es ja mal, allerdings würde ich vermuten daß eine derartige Verarbeitung ziemlich zeitaufwendig ist...

Zitat:

---

Deine ursprüngliche Frage war ja, wie kommst Du zu der Kante, wenn Dein Objekt (ein)farbig ist?

---

stimmt, wobei ich dieses Problem durch meine Korrektur (also die Division durch den I-Kanal) schon relativ gut in den Griff bekommen habe. Den LoG werde ich aber auf jeden Fall mal ausprobieren, denn Subpixel-Genauigkeit ist immer gut.

was haelts du von zwischen den einzelnen farbkaestcehn immer eine weisse linie einzufügen, dann kannst du den durchschnitt von der linie um das kästchen von der mitte abziehn um ungefähr die urspruengliche farbe der mitte zu finden... alternativ ein weisses 4eck in der mitte jedes farbkästchens..

Weisse Linien wären durchaus denkbar...
(kästchen eher nicht, da dann die Farbfelder zu groß werden)
ob bzw. wie gut das funktioniert ist halt im wesentlichen eine Auflösungsfrage, denn die Linien müssen ja auf der Aufnahme auch noch zu sehen sein (und "normale" Digitalkameras können leider nichts auflösen was auf dem Chip kleiner als 3 px ist)

sobald mir der Beamer wieder zur Verfügung steht werde ich das aber auf jeden Fall mal ausprobieren.

theoretisch kannst du bei linienmustern sogar im unterpixelbrecich auflösen..
kannst ja mal versuchen...

Felix,

die helle Linien eines projizierten Liniengitters könntest Du vektorisieren und anschliessend die Schnittpunkte zwischen senkrechten und waagerechten Linien bestimmen. Die Abweichungen der Schnittpunkte von einem regelmässigen Gitter enthalten dann die Information über das Oberflächenrelief. Schwierig wird's nur an den Stellen die der Projektor nicht erreicht (in Deinem Musterbild z.B. der Schattenrand auf der linken Seite der Sonne) und dort wo die Linien, aus dem Blickwinkel der Kamera gesehen, von einem vorspringenden Teil des Reliefs verdeckt werden /z.B. rechts von der Sonne).

mare_crisium.