Kovarianzmatrix & Ellipsoide

26/11/2007 - 11:55 von Stephan Berger | Report spam
Hallo liebe Mathematiker(innen) :)

ich habe hier ein Verstàndnisproblem (naja, wohl eher ein
fehlende-Grundlagen Problem) mit meiner Studienarbeit im Fach Informatik.
Der Reihe nach: ich soll Merkmalsextraktoren implementieren, welche die
Grundlage zur Klassifikation von Leukozyten bilden. Die Details sind
eigentlich nicht relevant, daher nur kurz zum Begriff Merkmalsextraktor:
ein Algorithmus der (in meinem Fall) ein Bild als Eingabe erhàlt und
"dass was er sieht" als Zahl ausgibt. Einfaches Beispiel: Mittelwert und
Standardabweichung der Werte des R, G oder B Kanals.
Für Leukozyten ist die Form des Zellkerns interessant. Ich bin dabei auf
zwei Merkmale gestoßen, Circular und Elliptic Variance. Mein Problem
besteht darin die mathematischen Grundlagen des zweiten zu verstehens,
damit es etwas klarer wird erlàutere ich erstmal Circular Variance.

Bei der Circular Variance betrachtet man den Schwerpunkt und die Kontur
einer Binàrmaske (die markiert sozusagen wo sich Pixel befinden, die zum
Kern gehören). Man betrachtet den Abstand zwischen Schwerpunkt und
Konturpixel und berechnet Mittelwert und Varianz. Einfach gesagt setzt
man in den Schwerpunkt der Binàrmaske einen Kreis mit Radius "mittlere
Abstand Kontur - Schwerpunkt" und Berechnet die mittlere quadratische
Abweichung der Konturpixel, daher Circular Variance.

Da ich es gleich brauche: Der Abstand vom Schwerpunkt in x-, und
y-Richtung wird also jeweils als Zufallsvariable betrachtet, deren
Kovarianzmatrix sei C.
Soweit, so gut. Der Autor des Papers schreibt nun sinngemàß:
-
Asugehender von der Cirvular Variance ist der nàchste logische Schritt
die Anzahl der Freiheitsgrade zu erhören, indem man Dehnung zulàßt und
dann den mittleren quadratischen Fehler berechnet.
-
Soweit, so gut, er will also statt dem Kreis eine Ellipse nehmen, da
diese sich "genauer" auf die Binàrmaske "mappen" làßt. Das soll
natürlich nicht irgendeine Ellipse sein, sondern eine die gewisse
àhnlichkeiten in Bezug auf die Region hat:
-
Intuitiv erscheint es logisch eine Ellipse zu finden, die die gleiche
Kovarianzmatrix hat C_{Ellipse} = C. Praktisch wàhlt man den umgekehren
Ansatz und erhàlt:

\sigma_{rc} = \frac{1}{N} * \sum_{i}{
\sqrt{(p_i - c)^T * C^{-1} * (p_i - c)}
}
ellvar = \frac{1}{N*\sigma_{rc}} * \sum_{i} {
{ \sqrt{(p_i - c)^T * C^{-1} * (p_i - c)}
- \sigma_{rc}
}^2
}
(Anm: N ist die Zahl der Konturpixel, die Summe làuft über alle
Konturpixel p_i, c ist der Schwerpunkt der Binàrmaske)
-
Also, ich hab natürlich schon versucht selbst etwas zu recherchieren:

- C ist als Kovarianzmatrix von reellen Zahlen
symmetrsch und positiv semidefinit.
- damit ist C diagonalisierbar, wobei D_C selbst wieder eine
Kovarianzmatrix ist

- Ein Ellipsoid kann beschrieben werden als:
\{ x \in R^n : x^T * Q * x = 1 \}
wobei Q eine positiv definite symmetrische Matrix ist

So, dass man Ellipsoide auf diese Art beschreiben kann glaube ich
einfach mal so, klar ist es mir nicht. Mein Problem ist nun:
Der Autor will eine Ellipse finden (wir sind ja im 2D), die "die gleiche
Kovarianzmatrix hat". Wie ist das zu versthehen? Nach dem was ich oben
gelesen habe beschreibt die Kovarianzmatrix doch gar keine Ellipse, da
sie ja "nur" positiv semidefinit ist. Was will der Autor mit C_{Ellipse}
= C zum ausdruck bringen? Kann mir jemand den "intuitiven" Teil da nàher
bringen?
Der Ausdruck (p_i - c)^T * C^{-1} * (p_i - c) erinnert ja schon ein
wenig an die "Ellipsengleichung". Allerdings: warum C^{-1}, also das
inverse der Kovarianzmarix? Dabei tut der Autor auch noch so, als wàre
diese ja ganz einfach zu berechnen. Mir ist nicht klar, warum das
einfach sein soll, ich hab mal gelernt das inverse Matrizen im Allg.
eben nicht einfach zu finden sind, im schlimsmten Fall ist C auch noch
schlecht konditioniert, so dass man es am besten gleich làßt. Gibt es
hier vielleicht Sàtze zu Kovarianzmatrizen, die ich nicht kenne?
Offenbar wird ja bei \sigma_{rc} wieder eine Art Mittelwert gebildet,
aber was beschreibt dieser Mittelwert genau? Vielleicht verstehe ich
dann auch warum der Audruck ellvar tatsàchlich die mittlere quadratische
Abweichung der Konturpixel von einer "gut gemappten" Ellipse darstellt.

Ich wàre sehr Dankbar, wenn mir jemand weiterhelfen kann. Wenn
irgendetwas unklar oder schlecht formuliert immer raus damit, ich
versuche es dann klarer auszudrücken. Und sollte das ganze einfach zu
komplex sein, um es mal eben mit ein paar Sàtzen in einer Newsgroup zu
erklàren, entschuldigt bitte mein Unwissen.

Der vollstàndigkeit halber sei noch die Quelle genannt:
Efficiency of Simple Shape Descriptors, M. Peura and J. Iivarinen
(mehr Daten habe ich leider nicht)

Grüße
Stephan Berger
 

Lesen sie die antworten

#1 Roland Damm
27/11/2007 - 00:01 | Warnen spam
Moin,

Stephan Berger schrub:

Bei der Circular Variance betrachtet man den Schwerpunkt und
die Kontur einer Binàrmaske (die markiert sozusagen wo sich
Pixel befinden, die zum
Kern gehören).



Wenn du sagst, dass das so einfach ist... Glaube ich erst mal
nicht, aber sei es so.

Man betrachtet den Abstand zwischen
Schwerpunkt und
Konturpixel und berechnet Mittelwert und Varianz. Einfach
gesagt setzt man in den Schwerpunkt der Binàrmaske einen Kreis
mit Radius "mittlere Abstand Kontur - Schwerpunkt" und
Berechnet die mittlere quadratische Abweichung der Konturpixel,
daher Circular Variance.



Gut.

Jetzt soll als Verbesserung eine Ellipse eingeschrieben werden.
Nebenbei, das von dir geschilderte Verfahren habe ich nicht
ansatzweise verstanden:-). Musst du das so machen?

Den mittleren Radius kennst du ja jetzt schon.
Also kannst du für alle Randpixel ihren Winkel (zwischen
Randpunkt, Mittelpunkt und Norden) und ihren Abstand vom
mittleren Kreis ausrechnen. Das gibt eine 'Funktion' dr(phi),
also die Radiusdifferenz von echtem Randpunkt zu gedachtem Kreis
über den Winkel. Natürlich ist diese Funktion nur an einigen
vielen Stellen definiert, in phi noch nicht mal àquidistant
geteilt. Macht ja nichts. Du teilst den Vollkreis einfach in
z.B. 1024 Schritte, an diesen Winkeln interpolierst du linear *)
aus den benachbarten bekannten Punkten und làsst eine FFT drüber
hetzen. Für die Ellipse (oder was àhnlich aussehendes) braucht
es nur die Koeffizienten für sin(phi) und cos(phi). Höhere
Koeffizienten könnten sinnvoll sein, aber das wirst du dann
sehen.
[Ist jetzt sogar ein Schritt zu kompliziert, eine FFT liefert dir
den Radius des mittleren Kreises auch schon]

Wahlweise kann man jetzt höhere Koeffizienten berücksichtigen
oder bei der ersten Ordnung abbrechen und die Standardabweichung
der echten Kontur von dieser idealisierten Form berechnen.

*) lineare Interpolation hört sich nach Schrott an, aber bedenke,
dass du damit nur zwischen Pixeln interpolierst, also auch keine
falscheren Informationen verwendest, als wenn du nur auf Pixel
gerundet rechnest. Eher besser.

CU Rollo

Ähnliche fragen