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 und liegen, gehören auf jeden Fall dazu. Aber welche noch?

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 und  kann man in der Normalvektorform darstellen als

wobei ein beliebiger Punkt auf der Geraden ist und ein beliebiger Normalvektor auf die Gerade. Der Vektor ist ein Vektor in Richtung der Geraden, der Vektor also ein möglicher Normalvektor. Damit kann man diese Gleichung schreiben als

Geradengleichung für Pixel

Die Pixel-Koordinaten der beiden Punkte sind  und . Entsprechend hätte man gerne, dass die Pixel auf der Geraden die Gleichung

erfüllen, wobei und sind.

Dabei gibt es aber zwei Probleme. Erstens, und , wobei die Umrechnungsfaktoren und 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 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  liefern

Wir starten im Pixel , wo gilt. Von dem Pixel, in dem wir gerade stehen, können wir entweder einen Schritt in -Richtung oder einen in -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 Schritte in -Richtung und  in -Richtung. Zusätzlich zu müssen wir also noch  Pixel einfärben.

Der folgende C++ Pseudocode zeigt die Details des Algorithmus (zur Erinnerung: 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 – und -Richtung mit hinein rechnen. Wie wir aber gleich sehen werden, wird das Problem durch Erhöhung der Pixelzahl ohnehin gemindert.

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.

Weiter im nächsten Teil.