Bresenham-Linien-Algorithmus: Effiziente pixelgenaue Linienwiedergabe für Computer Vision

Von Fouad Sabry

Was ist der Bresenham-Linienalgorithmus

Der Bresenham-Linienalgorithmus ist ein Linienzeichnungsalgorithmus, der die Punkte eines n-dimensionalen Rasters bestimmt, die ausgewählt werden sollten, um einen Abschluss zu bilden Annäherung an eine gerade Linie zwischen zwei Punkten. Es wird üblicherweise zum Zeichnen von Linienprimitiven in einem Bitmap-Bild verwendet, da es nur ganzzahlige Addition, Subtraktion und Bitverschiebung verwendet, was alles sehr kostengünstige Operationen in historisch gängigen Computerarchitekturen sind. Es handelt sich um einen inkrementellen Fehleralgorithmus und einen der frühesten Algorithmen, die auf dem Gebiet der Computergrafik entwickelt wurden. Zum Zeichnen von Kreisen kann eine Erweiterung des ursprünglichen Algorithmus namens Mittelpunktkreisalgorithmus verwendet werden.

Ihr Nutzen

(I) Einblicke und Validierungen zu folgenden Themen:

Kapitel 1: Bresenhams Linienalgorithmus

Kapitel 2: Linienzeichnungsalgorithmus

Kapitel 3: Xiaolin Wus Linienalgorithmus

Kapitel 4: Digitaler Differentialanalysator (Grafikalgorithmus)

Kapitel 5: Mittelpunktkreisalgorithmus

Kapitel 6: Kettenregel

Kapitel 7: Ableitung

Kapitel 8: Steigung

Kapitel 9: Differentialrechnung

Kapitel 10: Plot-Algorithmen für die Mandelbrot-Menge

(II) Antwort an die Öffentlichkeit Top-Fragen zum Bresenham-Linien-Algorithmus.

(III) Beispiele aus der Praxis für die Verwendung des Bresenham-Linien-Algorithmus in vielen Bereichen.

Für wen dieses Buch gedacht ist

Profis, Studenten und Doktoranden, Enthusiasten, Hobbyisten und diejenigen, die über das Grundwissen oder die Informationen für jede Art von Bresenham-Linien-Algorithmus hinausgehen möchten.

• Sprache: Deutsch
• Herausgeber: Eine Milliarde Sachkundig [German]
• Erscheinungsdatum: 5. Mai 2024

Buchvorschau

Kapitel 1: Bresenhams Linienalgorithmus

Der Linienalgorithmus von Bresenham ist ein Linienzeichnungsverfahren, das die n-dimensionalen Rasterpunkte identifiziert, die ausgewählt werden sollen, um eine gerade Linie zwischen zwei Punkten anzunähern. Es wird häufig verwendet, um Linienprimitive in einem Bitmap-Bild (z. B. auf einem Computerbildschirm) zu zeichnen, da es nur ganzzahlige Addition, Subtraktion und Bitverschiebung erfordert, was alles relativ kostengünstige Operationen in historisch vorherrschenden Computerarchitekturen sind. Es ist einer der frühen Algorithmen, die im Bereich der Computergrafik entwickelt wurden, und ist ein inkrementeller Fehleralgorithmus. Eine Modifikation des ursprünglichen Algorithmus kann verwendet werden, um Kreise zu erstellen.

Während Antialiasing-fähige Techniken wie der Wu-Algorithmus auch in der modernen Computergrafik weit verbreitet sind, bleibt Bresenhams Linienalgorithmus aufgrund seiner Geschwindigkeit und Einfachheit von Bedeutung. Der Algorithmus wird in Plottern und den Grafikchips moderner Grafikkarten verwendet. Auch in zahlreichen Software-Grafikbibliotheken vorhanden. Aufgrund der Einfachheit des Algorithmus wird er häufig in die Grafikhardware oder Firmware aktueller Grafikkarten implementiert.

Heute bezieht sich der Begriff Bresenham auf eine Familie von Algorithmen, die Bresenhams ursprünglichen Ansatz erweitern oder verändern.

Der Linienalgorithmus von Bresenham ist nach Jack Elton Bresenham benannt, dem IBM-Mitarbeiter, der ihn 1962 entwickelte. Im Jahr 2001 veröffentlichte Bresenham:

Ich arbeitete im Rechenlabor des IBM San Jose Development Lab. Über das Schreibmaschinenterminal 1407 wurde ein Calcomp-Plotter mit einem IBM 1401 verbunden. Der Algorithmus wurde im Sommer 1962 oder möglicherweise einen Monat früher in der Produktion eingesetzt. Calcomp (Jim Newland und Calvin Heft) besaß Kopien der Programme, weil Unternehmen sie damals offen teilten. Als ich im Herbst 1962 nach Stanford zurückkehrte, spendete ich ein Exemplar an die Bibliothek des Stanford-Rechenzentrums. Auf der nationalen ACM-Tagung 1963 in Denver, Colorado, wurde eine Beschreibung der Strichzeichnungsroutine zur Präsentation angenommen. In jenem Jahr wurden nur die Tagesordnung der Referenten und Themen in einer Ausgabe der Mitteilungen der ACM veröffentlicht. Nach meinem Vortrag fragte jemand vom IBM Systems Journal, ob sie die Arbeit veröffentlichen dürften. Ich willigte gerne ein, und es wurde 1965 veröffentlicht.

Bresenhams Ansatz wurde erweitert, um Kreise, Ellipsen, kubische und quadratische Bézier-Kurven sowie native Anti-Aliasing-Versionen dieser Kurven zu erzeugen.

Die folgenden Konventionen werden verwendet:

Die obere linke Koordinate ist (0,0), so dass die Pixelkoordinaten nach rechts und unten wachsen (z. B. befindet sich das Pixel bei (7,4) direkt über dem Pixel bei (7,5)), während die untere rechte Koordinate (1,1) ist).

Die Mittelpunkte der Pixel haben ganzzahlige Koordinaten.

Die Endpunkte der Linie sind die Pixel bei (x_{0},y_{0}) und (x_{1},y_{1}) , wobei die erste Koordinate die Spalte und die zweite Koordinate die Zeile darstellt.

Der Algorithmus wird zunächst nur für das Oktant angezeigt, in dem das Segment nach unten und nach rechts ( x_{0}\leq x_{1} und y_{0}\leq y_{1} ) verläuft und dessen horizontale Projektion x_{1}-x_{0} länger ist als die vertikale Projektion y_{1}-y_{0} (die Linie hat eine positive Steigung kleiner als 1).

In diesem Achtel berechnet die Technik für jede Spalte x zwischen x_{0} und x_{1} , genau eine Zeile y, die ein Pixel der Linie enthält, während jede Zeile zwischen y_{0} und y_{1} mehrere gerasterte Pixel enthalten kann.

Die Bresenham-Technik wählt die ganze Zahl y aus, die dem Pixelmittelpunkt entspricht, der dem idealen (gebrochenen) y für dasselbe x am nächsten liegt. In aufeinanderfolgenden Spalten kann y gleich bleiben oder um 1 steigen. Die allgemeine Gleichung der Linie, die durch die Endpunkte verläuft, lautet:

{\frac {y-y_{0}}{y_{1}-y_{0}}}={\frac {x-x_{0}}{x_{1}-x_{0}}} .

Da wir die Spalte x haben, können wir die Zeile des Pixels, y, erhalten, indem wir diese Zahl auf die nächste ganze Zahl runden:

y={\frac {y_{1}-y_{0}}{x_{1}-x_{0}}}(x-x_{0})+y_{0}

.

Die Steigung (y_{1}-y_{0})/(x_{1}-x_{0}) hängt nur von den Endpunktkoordinaten ab und kann im Voraus berechnet werden, und das ideale y für aufeinanderfolgende ganzzahlige Werte von x kann berechnet werden, beginnend mit y_{0} der Steigung und wiederholtem Addieren.

In der Praxis behält der Algorithmus die y-Koordinateninformation nicht bei, die jedes Mal um m = ∆y/∆x  zunimmt, wenn x um eins zunimmt. Auf jeder Ebene wird eine Fehlergrenze beibehalten, die den Abstand zwischen (a) dem Punkt, an dem die Linie das Pixel verlässt, und (b) der oberen Kante des Pixels angibt.

Dieser Wert wird zuerst auf ( {\displaystyle y_{0}-0.5} aufgrund der Verwendung der Mittelkoordinaten des Pixels) gesetzt, jedes Mal, wenn die x-Koordinate um eins erhöht wird, wird m addiert.

Wenn die Ungenauigkeit größer als 0,5 ist, sind wir uns bewusst, dass sich die Linie um ein Pixel nach oben verschoben hat. Wir müssen die y-Koordinate erhöhen und eins vom Fehler subtrahieren, um den Abstand von der Oberseite des neuen Pixels widerzuspiegeln.

Der Bresenham-Algorithmus muss in zwei Schritten abgeleitet werden. Der erste Schritt besteht darin, die Steigungsschnittform der Gleichung einer Linie in eine andere Form zu übersetzen und dann diese neue Gleichung zu verwenden, um eine Linie zu zeichnen, die auf dem Konzept der Fehlerakkumulation basiert.

Die Steigungsschnittform einer Linie wird wie folgt geschrieben:

y=f(x)=mx+b

wobei m die Steigung und b der y-Achsenabschnitt ist.

Da es sich hierbei nur um eine Funktion von handelt x , kann keine vertikale Linie symbolisiert werden.

Daher wäre es sinnvoll, diese Gleichung als Funktion von sowohl als auch zu schreiben, x y die in der Lage ist, Linien in jedem Winkel zu zeichnen.

Der Winkel (oder die Steigung) einer Linie kann als Anstieg über Lauf oder angegeben werden \Delta y/\Delta x .

Dann, mit algebraischen Operationen,

{\begin{aligned}y&=mx+b\\y&={\frac {(\Delta y)}{(\Delta x)}}x+b\\(\Delta x)y&=(\Delta y)x+(\Delta x)b\\0&=(\Delta y)x-(\Delta x)y+(\Delta x)b\end{aligned}}

Lasst diese letzte Gleichung eine Funktion von x und  sein y , kann sie auch wie folgt geschrieben werden:

{\displaystyle f(x,y):=Ax+By+C=0}

wo sich die Konstanten befinden

{\displaystyle A=\Delta y=y_{1}-y_{0}}{\displaystyle B=-\Delta x=-(x_{1}-x_{0})}{\displaystyle C=(\Delta x)b=(x_{1}-x_{0})b}

Die Zeile wird dann für einige Konstanten A definiert, B und C überall f(x,y)=0 .

Das heißt, für alle, (x,y) die nicht in der Leitung sind, f(x,y)\neq 0 .

Diese Form enthält nur ganze Zahlen, wenn x und y ganze Zahlen sind, da die Konstanten A , B und C als ganze Zahlen definiert sind.

Zum Beispiel könnte die Zeile {\textstyle y={\frac {1}{2}}x+1} then this als geschrieben werden f(x,y)=x-2y+2 .

Der Punkt (2,2) steht auf dem Spiel.

f(2,2)=x-2y+2=(2)-2(2)+2=2-4+2=0

Außerdem steht der Punkt (2,3) nicht auf der Linie.

f(2,3)=(2)-2(3)+2=2-6+2=-2

Beides ist nicht der Punkt (2,1)

f(2,1)=(2)-2(1)+2=2-2+2=2

Beachten Sie, dass sich die Punkte (2,1) und (2,3) auf gegenüberliegenden Seiten der Linie befinden und f(x,y) positiv oder negativ ausgewertet werden.

Eine Linie teilt eine Ebene in zwei Hälften und die Halbebene, die ein Negativ hat f(x,y) , kann als negative Halbebene bezeichnet werden, die andere Hälfte wird als positive Halbebene bezeichnet.

Diese Bemerkung ist entscheidend für den Rest der Herleitung.

Offensichtlich liegt der Startpunkt auf der Linie.

f(x_{0},y_{0})=0

Nur weil die Linie so definiert ist, dass sie an ganzzahligen Koordinaten beginnt und endet, kann sie gezeichnet werden (obwohl es durchaus vernünftig ist, eine Linie mit nicht-ganzzahligen Endpunkten zeichnen zu wollen).

Wenn man bedenkt, dass die Steigung höchstens ist 1 , stellt sich nun das Problem, ob der nächste Punkt bei oder liegen soll (x_{0}+1,y_{0}) (x_{0}+1,y_{0}+1) .

Vielleicht sollte intuitiv der Punkt ausgewählt werden, der näher an der Linie bei x_{0}+1 liegt.

Wenn es näher am vorherigen Punkt liegt, fügen Sie es auf der Linie hinzu, wenn der zweite, dann der zweite.

Um dieses Problem zu beheben, werten Sie die Linienfunktion zwischen diesen beiden Positionen aus:

{\displaystyle f(x_{0}+1,y_{0}+{\tfrac {1}{2}})}

Wenn dieser Wert positiv ist, liegt die Ideallinie unterhalb des Mittelpunkts und näher am Kandidatenpunkt (x_{0}+1,y_{0}+1) . Folglich hat sich die y-Koordinate nach vorne verschoben.

Andernfalls, Die optimale Gerade befindet sich auf oder über der Hälfte, Außerdem hat sich die y-Koordinate nicht verschoben; in diesem Fall wählen Sie den Punkt (x_{0}+1,y_{0}) .

An diesem Mittelpunkt ist der Wert der Linienfunktion die einzige Determinante dafür, welcher Punkt ausgewählt werden soll.

Die Abbildung rechts zeigt den ausgewählten Punkt (2,2) in Blau sowie zwei potenzielle Punkte (3,2) in Grün (3,3). Der schwarze Punkt (3, 2,5) liegt in der Mitte der beiden Kandidatenpunkte.

Anstatt f(x,y) an den Mittelpunkten auszuwerten, kann alternativ die Differenz zwischen den Punkten verwendet werden. Diese alternative Methode ermöglicht