Computertomographie (CT), Teil 6

Eine Linie aus kleinen Quadraten

In Teil 5 haben wir die Rasterung besprochen und gesehen, wie man Punkt-Koordinaten in der »realen« Welt in Pixel-Koordinaten umrechnet. Jetzt müssen wir diese Punkte durch eine Linie aus Pixeln verbinden (s. Abb. 1). Die Pixel, in denen die Punkte P und Q liegen, gehören auf jeden Fall dazu. Aber welche noch?

Linie1
Abb. 1: Durch welche Pixel geht die Verbindungslinie von P und Q?

Dieses Problem trat schon zu Beginn der Computergraphikära auf und wurde in den verschiedensten Varianten gelöst. Im Folgenden besprechen wir eine Variante des Bresenham-Algorithmus für Linien.

Geradengleichung für Punkte

Eine Gerade in der Ebene durch die Punkt P(P_x|P_y) und Q(Q_x|Q_y) kann man in der Normalvektorform darstellen als

\displaystyle (x - P_x)\,n_x + (y - P_y)\,n_y = 0\,,

wobei (x|y) ein beliebiger Punkt auf der Geraden ist und (n_x,n_y) ein beliebiger Normalvektor auf die Gerade. Der Vektor (\Delta x,\Delta y) = (Q_x - P_x,Q_y - P_y) ist ein Vektor in Richtung der Geraden, der Vektor (\Delta y,-\Delta x) also ein möglicher Normalvektor. Damit kann man diese Gleichung schreiben als

\displaystyle(x-P_x)\,\Delta y - (y-P_y)\,\Delta x = 0\,.

Geradengleichung für Pixel

Die Pixel-Koordinaten der beiden Punkte sind P(P_i|P_j) und Q(Q_i|Q_j). Entsprechend hätte man gerne, dass die Pixel (i|j) auf der Geraden die Gleichung

\displaystyle(i-P_i)\,\Delta j - (j - P_j)\,\Delta i = 0

erfüllen, wobei \Delta i = Q_i - P_i und \Delta j = Q_j - P_j sind.

Dabei gibt es aber zwei Probleme. Erstens, \Delta i = k_i\,\Delta x und \Delta j = -k_j\,\Delta y, wobei die Umrechnungsfaktoren k_i und k_j nicht exakt gleich sind. Das heißt, dass die Pixellinie nicht exakt parallel zur tatsächlichen Linie ist. Dieses Problem wird umso geringer, je größer die Anzahl der Pixel ist.

Problematischer ist, dass die Pixel (i|j) nur ganze Zahlen annehmen können. Das heißt, dass im Allgemeinen die meisten Pixel unserer Geraden obige Gleichung nicht exakt erfüllen können, sondern eine Abweichung e liefern

\displaystyle(i-P_i)\,\Delta j - (j - P_j)\,\Delta i = e\,.

Wir starten im Pixel P, wo e = 0 gilt. Von dem Pixel, in dem wir gerade stehen, können wir entweder einen Schritt in i-Richtung oder einen in j-Richtung machen. (Bresenham würde hin und wieder diagonal gehen.) Wir rechnen für beide Varianten die neue Abweichung aus, und nehmen die Richtung, in die die absolute Abweichung kleiner ist. Wir gehen \lvert\Delta i\rvert Schritte in i-Richtung und \lvert\Delta j\rvert in j-Richtung. Zusätzlich zu P müssen wir also noch \lvert\Delta i\rvert + \lvert\Delta j\rvert Pixel einfärben.

Der folgende C++ Pseudocode zeigt die Details des Algorithmus (zur Erinnerung: s = 2 r / n ist die Seitenlänge eines Pixels):

void line(P, Q)
{
    // umrechnen in Pixel-Koordinaten
    const int Pi = (int)floor( Px / s) + n / 2;
    const int Pj = (int)floor(-Py / s) + n / 2;
    const int Qi = (int)floor( Qx / s) + n / 2;
    const int Qj = (int)floor(-Qy / s) + n / 2;

    // Abstände in i- und j-Richtung
    const int di = Qi - Pi; // Delta i
    const int dj = Qj - Pj; // Delta j

    // Schritte in i- und j-Richtung
    const int si = (di > 0) ? 1 : -1; // Schritt nach links oder rechts?
    const int sj = (dj > 0) ? 1 : -1; // Schritt nach unten oder oben?

    // wir starten im Pixel P
    int i = Pi;
    int j = Pj;

    // und müssen P jedenfalls zeichnen
    fillPixel(i, j);

    // zu Beginn ist die Abweichung sicher 0
    int e = 0;

    // wir müssen außer P insgesamt |di| + |dj| Pixel füllen
    for (int k = 1; k <= abs(di) + abs(dj); ++k) {
        // mögliche Abweichungen in i- und j-Richtung ausrechnen
        // i und j werden jeweils um plus/minus 1 geändert
        const int e_i_pm_1 = e + si * dj;
        const int e_j_pm_1 = e - sj * di;

        // in die Richtung mit der absolut kleineren Abweichung gehen
        if (abs(e_i_pm_1) < abs(e_j_pm_1)) {
            i += si;
            e = e_i_pm_1;
        }
        else {
            j += sj;
            e = e_j_pm_1;
        }

        // nächsten Pixel zeichnen
        fillPixel(i, j);
    }

}

Das Ergebnis zeigt Abb. 2. Von 4 Pixeln, die ein Quadrat bilden, werden 2–3 eingefärbt. Bei einigen kann man sich fragen, ob es nicht besser wäre, das diagonal gegenüberliegende eingefärbt zu haben. Warum es manchmal nicht so wie erwartet klappt, liegt daran, dass die Punkte nicht immer exakt in der Mitte der Pixel liegen, sondern irgendwo innerhalb, und damit zusammenhängend, dass die Steigung der Pixelgeraden nicht exakt gleich der Steigung der realen Geraden ist. Rein prinzipiell könnte man das beim Vergleich der Abweichungen in i– und j-Richtung mit hinein rechnen. Wie wir aber gleich sehen werden, wird das Problem durch Erhöhung der Pixelzahl ohnehin gemindert.

Linie2
Abb. 2: die von obigem Code berechneten Pixel in einem (16×16)-Bild.

Abb. 3 vergleicht die Linie aus Abb.2 für verschiedene Auflösungen des Bildes, von (16×16) bis (512×512) Pixel. Im letzteren Fall, verschwinden die Pixel praktisch vollständig unter der Linienbreite. Speziell im (32×32)-Fall sieht man, was passiert, wenn die realen Punkte eher am Rand der Pixel zu liegen kommen.

Linie3
Abb. 3: eine Pixellinie zwischen 2 Punkten für verschiedene Bildauflösungen (n\times n).

Weiter im nächsten Teil.

Kommentar verfassen

Trage deine Daten unten ein oder klicke ein Icon um dich einzuloggen:

WordPress.com-Logo

Du kommentierst mit Deinem WordPress.com-Konto. Abmelden / Ändern )

Twitter-Bild

Du kommentierst mit Deinem Twitter-Konto. Abmelden / Ändern )

Facebook-Foto

Du kommentierst mit Deinem Facebook-Konto. Abmelden / Ändern )

Google+ Foto

Du kommentierst mit Deinem Google+-Konto. Abmelden / Ändern )

Verbinde mit %s