Bildverarbeitung; Skeleton-Berechnung

[Tobias P. (hubertus)]

Hallo allerseits

ich hab da mal eine Frage zur Bildverarbeitung. Ich will den 'Skeleton' 
von einem Binärbild berechnen. Dazu habe ich aus einem Buch 
(Gonzalez/Woods, Digital Image Processing) einen Algorithmus entnommen 
und in Matlab implementiert. Ich bin mir zu 99% sicher, den Algorithmus 
wie beschrieben implementiert zu haben, dennoch liefert er nicht genau 
das richtige Resultat.
Ich bin nicht sicher, ob im Buch ein Druckfehler vorliegt, oder ob ich 
selber einen Denkfehler gemacht habe... daher die Frage, ob sich mal 
jemand meinen Code anschauen könnte.

Der Algorithmus zum Berechnen der Pixel des Skeleton ist wie folgt:

a) Berechnung aller Randpixel. Ein Randpixel ist ein Pixel, der 
mindestens einen Nachbar mit dem Wert 0 hat. (in einem Binärbild). Das 
macht bei mir die Funktion getborder(). Die liefert einen Vektor wo die 
x- und y-Koordinaten der Randpunkte drin stehen.

Dann eine Schleife über alle Randpunkte. Der jeweils betrachtete 
Randpunkt sei mit X bezeichnet; die Nachbarn sind dann:


p9 p2 p3
p8 X p4
p7 p6 p5


b) Für jeden Randpunkt folgendes Prüfen:
   1) 2 <= (p2 + p3 + p4 + p5 + p6 + p7 + p8 + p9) <= 6
   2) Anzahl der 0-1 Transitionen in der Liste [p2 p3 p4 p5 p6 p7 p8 p9 
p2] ist gleich 1
   3) p2  p4  p6 = 0
   4) p4  p6  p8 = 0
   5) wenn das zutrifft, dann den aktuellen Pixel in eine Liste legen
c) wenn man obiges für alle Randpunkte ausgeführt hat, dann alle Pixel 
in der Liste auf 0 setzen
d) das selbe wie oben machen, aber 3) und 4) werden ersetzt durch:
   3a) p2  p4  p8 = 0
   4a) p2  p6  p8 = 0
   5a) wenn das zutrifft, dann den Pixel in eine Liste setzen
e) alle Pixel, die in der Liste stehen, auf 0 setzen
f) Die Prozedur so lange wiederholen, bis keine Pixel mehr gelöscht 
wurden.

Ich meine, mein Matlab-Code macht genau das, aber das Resultat ist nicht 
korrekt. Wenn man ein Binärbild eines Quadrats hat, dann sollte doch ein 
grosses X resultieren, aber es resultiert bei mir immer nur ein 
einzelner Pixel.

Ideen? bin sehr gespannt.


Gruss Tobias

[Harry (Gast)]

was kommt den raus?

[Possetitjel (Gast)]

Tobias P. schrieb:

> Anzahl der 0-1 Transitionen in der Liste [p2 p3 p4 p5 p6
> p7 p8 p9 p2] ist gleich 1

Das geht nicht.

In einem vollständigen Umlauf kann nicht genau EIN Übergang
vorhanden sein.

[Tobias P. (hubertus)]

Hallo allerseits

sorry für meine späte Antwort. Hatte die Email-Benachrichtigung bei der 
1. Antwort nicht gesehen.

@Possetjel:
Doch das geht schon, denn es handelt sich um die Anzahl der Übergänge 
von 0 auf 1. Die Folge [0 0 0 0 1 1 1 1 0] hat genau einen solchen 
Übergang. Hat mich auch erst verwirrt, aber es steht so in dem Buch von 
wo ich den Algorithmus abgetippt habe.

Im Anhang habe ich das Bild angehängt, wo man das Skeleton noch dem 
Originalbild überlagert sieht (schwarz). Das wäre intuitiv und auch 
gemäss Buch das richtige Resultat,

[Tobias P. (hubertus)]

Im Anhang noch das Resultat, was mit meiner Implementierung berechnet 
wird (rot). Es geht in die richtige Richtung, aber irgendwie fehlt was 
:-(

[Jürgen S. (engineer)]

Wie prozessierst Du denn dabei die Grauwerte und Pixelfehler im Bild? Da 
sind doch in aller Regel unbeseitigte spots drin.

[Tobias P. (hubertus)]

Hi Jürgen

ich habe das Graustufenbild mittels Schwellwert in ein Binärbild 
umgewandelt. Da schwarz und weiss bei dem Beispielbild deutlich genug 
abgegrenzt sind voneinander ergibt das ein perfektes Binärbild ohne 
jegliche Löcher. (es ist mir jedenfalls nichts aufgefallen)

[Martin L. (maveric00)]

Hallo,

schon einmal mit einer anderen (deutlich höheren) Auflösung probiert? 
Zumindest sieht das Skelett in Deinem Bild wesentlich dicker aus als im 
Beispielbild, und auch die Abweichungen im Detailgrad könnten damit zu 
tun haben.

Schöne Grüße,
Martin

[Mikro 7. (mikro77)]

Btw: ImageMagick unterstützt eine Vielzahl von CV Operationen. Es kann 
hilfreich bei der Fehlersuche sein wenn man die eigene Ausgabe mit der 
von IM vergleicht. 
http://www.imagemagick.org/Usage/morphology/#thinning_skeleton

Edit (war neugierig): Bild nach...

convert bone2.png -threshold 80% -morphology Thinning:-1 Skeleton bone2_skeleton.png

[Tobias P. (hubertus)]

Hallo Hallo,

@MArtin L:
ja in meinem Beispielbild habe ich das Skelett noch im GIMP 
nachgezeichnet, weil man es auf dem schlechten Bild sonst kaum erkennen 
kann. Darum ist es so dick. Aber in Wirklichkeit ist es tatsächlich nur 
1 Pixel breit. Und leider bleibe das Resultat gleich, wenn ich ein 
grösseres oder kleineres Bild benutze :-(

@Mirko
Danke für den Tip. Das Resultat von ImageMagick sieht ein wenig anders 
aus als meines, und auch als im Buch :-) offenbar ist das Skelett nicht 
ganz 100%ig eindeutig. Aber es geht sicher in die richtige Richtung. Ich 
schau mir mal an, wie das dort implementiert ist. Der Punkt ist der: man 
kann das Skelett schon mit Morphologischen Operationen berechnen, diese 
möchte ich aber nicht benutzen, weil es dann nicht garantiert ist, dass 
alle Teile zusammenhängend bleiben. Stattdessen möchte ich einen 
Algorithmus benutzen, welcher nicht auf Morphologie basiert.

[Jürgen S. (engineer)]

Meines Erachtens braucht es hier ein Feldweises Vorgehen, dass die 
maximale Krümmung der entstehenden Koordinatenlinien begrenzt. Wenn ich 
mir das Gezittere in der Längsachse des Knochens ansehe, ist das nicht 
so tauglich. Mit entsprechenden Randbedinungen kommt man dann auch 
leicher über die Bildfehler und das Rauschen drüber.