Guten Tag zusammen,
ich beschäftige mich zur Zeit mit Template Matching und im Zuge dessen auch mit Distanztransformationen auf Binärbildern.
Dazu habe ich einige Bildverarbeitungsbücher in der Bibliothek durchstöbert und einige Paper im Internet gefunden. Hängen geblieben bin ich bei einem Paper der University of Groningen. Link: A General Algorithm For Computing Distance Transform…
Obwohl ich mittlerweile sowohl diesen Algorithmus (auf Grundlage des Pseudo Codes), als auch den Chamfer Algorithmus für die Distanztransformation erfolgreich implementiert habe, würde ich gerne die Mathematik dahin verstehen.
Ich habe mich bisher ausschließlich auf die Metrik des Euklidischen Abstands konzentriert. Aber nachdem ich eine Metrik mit diesem Algorithmus verstanden habe, sollten die anderen ja kein Problem mehr sein.
Der Euklidische Abstand in der 2D Ebene ist ja wie folgt definiert:
<CODE syntax=„latex“>
d(x, y) = \sqrt{(x_1 - y_1)^2 + (x_2 - y_2)^2}
</CODE>
In besagtem Paper werden die Formeln in die folgende Form gebracht:
MIN(k: P(k): f(k))
Also gesucht ist das kleinste f(k) für alle k, die die Bedingung P(k) erfüllen. Der Euklidische Abstand wird daher in diese Form gebracht:
<CODE syntax=latex">
EDT(x, y) = MIN(i,j: 0 \le i < m \wedge 0 \le j < n \wedge b[i, j]: (x-i)^2 + (y-j)^2)
</CODE>
Also für alle Punkte soll der Abstand zu den anderen Punkten des Bildes berechnet werden, wenn es sich um einen Vordergrundpixel handelt. Davon das Minimum ergibt die Euklidische Distanztransformation. Das ganze wird jetzt in zwei Teile gesplittet:
<CODE syntax=latex">
EDT(x, y) = MIN(i: 0 \le i < m: (x-i)^2 + G(i, y)^2)
</CODE>
mit
<CODE syntax=latex">
G(i, y) = MIN(j: 0 \le j < n \wedge b[i, j]: \abs{y -j})
</CODE>
Der Algorithmus wird so in 2 Hauptphasen unterteilt. In der ersten Phase wird jede Spalte <CODE syntax=latex">C_x</CODE> der Bildmatrix B(m \times n) seperat untersucht. Dazu wird zu Beginn der oberste Pixel B(x, 0) der jeweiligen Spalte auf seine Zugehörigkeit zum Vordergrund untersucht. Gehört ein Pixel zum Vordergrund, erhält er die Distanz G(x, y) = 0, andernfalls die Distanz G(x, y) = <CODE syntax=latex">\infty</CODE>. Es ist üblich die Distanz <CODE syntax=latex">\infty</CODE> durch m + n auszudrücken, da die Distanz in einem Nichtleeren Bild niemals größer werden kann.
Danach wird über die Bildpunkte der Spalte <CODE syntax=latex">C_x</CODE> von oben nach unten iteriert. Gehört der Pixel B(x, y) zum Vordergrund, erhält er ebenfalls die Distanz G(x, y) = 0. Im anderen Fall erhält er die Distanz des oberhalb von ihm liegenden Pixels G(x, y) = G(x, y - 1) + 1. Daraus lässt sich folgende Vorschrift ableiten:
<CODE syntax=latex">
GT(i, y) = MIN(j: 0 \le j \le y: \wedge b[i,j]: y-j)
</CODE>
Abschließend wird die aktuelle Spalte rückläufig von unten nach oben durchlaufen. Nun wird die Distanz des gegenwärtigen Pixels mit der des unterhalb dieses Bildpunktes liegenden verglichen. Ist diese geringer, erhält der Pixel den Distanzwert G(x, y) = G(x, y + 1) + 1. Formal ausgedrückt:
<CODE syntax=latex">
GB(i, y) = MIN(j: y \le j < n: \wedge b[i,j]: j-y)
</CODE>
Das Minimum der beiden Funktionen an den jeweiligen Stellen ergibt G(i, y). Damit wäre Phase 1 abgeschlossen. An einem kleinen Beispiel müsste das meiner Meinung nach so aussehen:
Binärbild:
<CODE syntax=latex">
\begin{tabular}{|c|c|c|c|}
\hline
0 & 0 & 0 & 0 \
\hline
0 & 1 & 1 & 0 \
\hline
0 & 0 & 1 & 0 \
\hline
0 & 0 & 0 & 0 \
\hline
\end{tabular}
</CODE>
Nach erstem Teil Phase 1:
<CODE syntax=latex">
\begin{tabular}{|c|c|c|c|}
\hline
8 & 8 & 8 & 8 \
\hline
9 & 0 & 0 & 9 \
\hline
10 & 1 & 0 & 10 \
\hline
11 & 2 & 1 & 11 \
\hline
\end{tabular}
</CODE>
Nach zweitem Teil Phase 1:
<CODE syntax=latex">
\begin{tabular}{|c|c|c|c|}
\hline
8 & 1 & 1 & 8 \
\hline
9 & 0 & 0 & 9 \
\hline
10 & 1 & 0 & 10 \
\hline
11 & 2 & 1 & 11 \
\hline
\end{tabular}
</CODE>
So, in Phase 2 werden nun die einzelnen Zeilen untersucht. Da der y-Wert für die Untersuchung einer Zeile immer konstant bleibt, wird eingeführt, dass G(i, y) = g(i) ist.
Ganz allgemein wird definiert:
<CODE syntax=latex">
DT(x, y) = MIN(i: 0 \le i \le m: f(x, i))
</CODE>
f(x, i) beschreibt dann die Metrikabhängigkeit, für den Euklidischen Abstand z.B.:
<CODE syntax=latex">
f(x, i) = (x-i)^2 + g(i)^2
</CODE>
Wende ich f(x, i) an, erhalte ich meiner Meinung nach:
<CODE syntax=latex">
\begin{tabular}{|c|c|c|c|}
\hline
64 & 2 & 5 & 73 \
\hline
82 & 0 & 1 & 85 \
\hline
104 & 2 & 0 & 101 \
\hline
130 & 8 & 2 & 121 \
\hline
\end{tabular}
</CODE>
So, nun soll DT(x, y) wiederum das Minimum von f(x, i) für alle i von 0 bis m. Verwirren tut mich hier schon, dass i als y Laufvariable in f eingesetzt wird, aber von 0 bis m läuft. m ist doch die Anzahl der x Koordinaten oder nicht? Ich weiß nicht, wie das genau gemeint ist. Häufig führen mich meine Überlegungen zu diesem Ergebnis:
<CODE syntax=latex">
\begin{tabular}{|c|c|c|c|}
\hline
64 & 0 & 0 & 73 \
\hline
64 & 0 & 0 & 73 \
\hline
64 & 0 & 0 & 73 \
\hline
64 & 0 & 0 & 73 \
\hline
\end{tabular}
</CODE>
Damit kann ich nicht allzu viel anfangen. Im Paper wird eine anschauliche geometrische Darstellung erklärt, allerdings verstehe ich nicht so ganz, was in Fig. 2 wirklich abgebildet wird. Den Rest des Papers habe ich mir abgesehen von der Herleitung der Sep Funktion zwar angesehen, aber weder sonderlich viel kapiert, noch geglaubt, dass das Sinn ergibt, wenn ich hier noch hänge.
Es wird auf jeden Fall erklärt, dass Phase 2 wiederum aus 2 Schritten besteht. Einem links-nach-rechts scan und einem umgekehrten Scan. Wozu gehört dann die Anwendung von f(x, i)?
Weiß leider nicht mehr weiter. Also falls jemand Erfahrung mit diesem Algorithmus hat und ein paar Erklärungen dazu abgeben könnte, wäre ich sehr dankbar. Leider finden sich zwar einige Erwähnungen dieses Papers im Internet und in Literatur, aber eine Alternative Erklärung nicht.
Mit freundlichen Grüßen
Namco
