尹洪松，唐莉萍，曾培峰（.東華大學(xué)　信息科學(xué)與技術(shù)學(xué)院，上?！?60；.東華大學(xué)　計算機科學(xué)與技術(shù)學(xué)院，上海　060）

基于Bresenham的任意寬度直線生成算法

尹洪松1，唐莉萍1，曾培峰2
（1.東華大學(xué)信息科學(xué)與技術(shù)學(xué)院，上海201620；2.東華大學(xué)計算機科學(xué)與技術(shù)學(xué)院，上海201620）

直線生成算法是計算機圖形的基本算法，而現(xiàn)有算法都有其弊端，因此提出一種基于Bresenham任意寬度直線的生成算法。該算法首先根據(jù)直線的斜率、長度和寬度計算出直線所形成的邊界，然后讓單線寬直線沿著邊界移動，使整個區(qū)域填充。該算法生成的直線兩端與邊界垂直，在直線斜率變化的情況下，直線寬度不會發(fā)生變化，且具有應(yīng)用背景廣泛、運算速度快、占用內(nèi)存小等特點。

直線生成；Bresenham畫線算法；區(qū)域填充

0　引言

嵌入式圖形系統(tǒng)的圖形顯示是通過光柵顯示器來實現(xiàn)的，而光柵顯示器實際上是一個像素矩陣，光柵顯示器通過點亮一個個像素，確定最佳逼近于圖像的像素集。直線是嵌入式圖形系統(tǒng)中最基本的元素，因此直線生成算法也是其他各類圖形算法的基礎(chǔ)，得到了廣泛的研究?，F(xiàn)有的直線生成算法主要有：DDA算法、中點畫線算法以及Bresenham算法等，其中應(yīng)用最廣泛的是Bresenham算法［1-3］，其優(yōu)點是不需要進行小數(shù)和取整運算，只需要進行整數(shù)加法和乘法運算來計算出待生成的像素點的坐標。Bresenham算法是只針對于單像素寬的直線。而實際應(yīng)用中，經(jīng)常使用的線段是有線寬和線型的。對于多線寬直線的生成，目前國內(nèi)外的研究不多，現(xiàn)有方案主要有線刷子算法、正方形刷子算法和區(qū)域填充算法。

線刷子算法原理：假設(shè)直線斜率在［-1，1］之間，垂直的長度線寬的線段中心對準線段起點，線段順著單像素線條軌跡移動，直到末端。對于斜率絕對值大于1的，該刷子是水平方向的。線刷子算法具有算法簡單、效率高的特點，但是刷子法生成的直線端點形狀不理想，寬度小于指定寬度，而且寬度隨斜率的改變而改變。

正方形刷子算法則是把邊長為指定線寬的正方形沿著中心線平移，獲得具有寬度的直線。與線刷子算法類似，其末端也是水平的或者垂直的，且線寬隨線段斜率的改變而改變。

區(qū)域填充算法［4-6］則是使用改進的Bresenham計算出線段所形成矩形區(qū)域邊界，畫出封閉的區(qū)域，然后利用種子填充算法將矩形區(qū)域填充起來。其優(yōu)點是生成直線端頭標準，寬度可控，很接近理想多寬度直線。但是算法復(fù)雜，而且在背景與線段區(qū)域邊界形成多分割區(qū)域時，容易形成填充孤島，無法填充整個區(qū)域；填充過程中無法利用像素坐標之間的內(nèi)在聯(lián)系；且該算法應(yīng)用于CAD/CAM造型系統(tǒng)，使用種子填充算法，占用內(nèi)存大。

綜上可以看出，以上算法都有其局限性，因此本文提出一種新的任意寬度直線的生成算法，該算法能夠生成的任意寬度直線的末端與直線方向垂直，寬度可控，算法簡單，占用內(nèi)存小，適用背景廣的任意直線算法，適合嵌入式設(shè)備。

1　算法思想與步驟

1.1Bresenham算法

Bresenham算法是應(yīng)用最廣泛的直線掃描轉(zhuǎn)換算法。其原理是：不考慮像素形狀、大小的影響，經(jīng)過各行、各列像素中心構(gòu)造一組網(wǎng)格線，若直線斜率絕對值小于1，則按直線從起點到終點的順序計算直線與各垂直網(wǎng)格線的交點，然后確定該列像素與此交點的最近像素；若直線斜率絕對值大于1，則計算與水平線的交點最近像素。該算法的優(yōu)點在于采用增量計算，使得對于每一列，只要檢查當(dāng)前誤差項的符號，就可以確定該列的所求像素。

Bresenhan算法誤差項d遞增如圖1所示。設(shè)該直線的起始點為A（x1，y1），終點為B（xn，yb），則直線的斜率為K=dy/dx，dx=xn-x1，dy=yn-y1。從起點A，下一個像素的行坐標是x1+1，列坐標則遞增1或者不變。是否增1，取決于圖1所示誤差項d的值。因為A點為圖像的起點，圖像經(jīng)過其中心，所以誤差項d的初始值為0。當(dāng)x增加1，d的值相應(yīng)遞增直線的斜率K，即d=d+K，若d≥1，則減去1，讓d始終在0～1之間。x1+1列像素中，到直線最近的點為C、D，C點到直線垂直距離A′C=1-d，D點到直線的垂直距離為A′D=d。當(dāng)d＞0.5時，則A′C＜A′D，則C點距離直線更近，取C點；而當(dāng)d＜0.5時，D點更近，取D點；當(dāng)d=0.5時，與上述兩個像素一樣近，約定取C點。為了避免浮點運算，將直線的斜率放大2×dx，K=dy/dx×2×dx=2×dy，誤差項d=d+dy×2，當(dāng)d＞2×dx，則更靠近C（x1+1，y1+1）；當(dāng)d≤2×dx，則更靠近D（x1+1，y1）。對于K＞1，可以將坐標軸顛倒，根據(jù)Y變化計算X。對于K＜0的情況，Y變化相反，那么X增加1，則Y的變化不變或減小1。通過遞增運算，計算直線通過最近的每一個點，畫出直線。

圖1　Bresenham算法誤差項d遞增

1.2多線寬算法

（1）算法思想

任意寬度直線生成算法中，直線刷子法利用生成的單寬度直線，在直線沿Y軸移動到另一端（若直線的斜率在［-1，1］）。若直線斜率不在［-1，1］內(nèi)，則改成沿X軸移動。而區(qū)域填充算法是使用Bresenham算法計算指定寬度直線的邊界形成封閉區(qū)域，再進行利用種子填充算法填充，形成的直線兩端標準。結(jié)合兩種算法的優(yōu)點，讓單線寬線段沿著計算出的邊界移動，即可以得到指定寬度的直線。

用內(nèi)存存儲每一列Y的增量，讓單線沿著Bresenham算法形成的區(qū)域兩端移動，因為線平行，計算它們連線只需要利用存儲的Y的增量，產(chǎn)生新的直線，形成的直線兩端垂直，且算法計算簡單，沒有種子填充算法的設(shè)定起始種子的局限。

（2）算法基本步驟

為了方便討論，假設(shè)直線斜率在［0，1］之間，其他情況可以通過坐標軸變換得到。假設(shè)直線L的起點為O（x0，y0），其終點坐標為O′（x1，y1），令x1＞x0，y1＞y0，直線的寬度為D，并記終點O兩側(cè)的直線終點分別是A、B，點O′兩側(cè)的直線終點分別是C、D，且記直線AB為L1，直線CD為L2。

①根據(jù)給出的直線的首位坐標，計算出其dx和dy；

②根據(jù)指定的寬度，計算出其B與O點的偏移量，得出A、B的坐標；

③計算出AB直線中坐標增量，存入內(nèi)存中；

④將點在AD、BC移動，根據(jù)內(nèi)存中Y的變化量，計算出新的A′B′直線，直到到達另一個邊界。

（3）直角保持與寬度控制

如圖2所示，理想情況下直線OO′與直線BC、AD垂直，則可以推導(dǎo)出KBC×KOO′=-1。直線OO′斜率為KOO′=dx/dy，那么得到直線AD的斜率，則可以根據(jù)式（1）、（2）計算出邊界點A與起點O的偏移量，由于ABCD是矩形，O′是B、C中點，O是A、D中點，則B、C與O′點的偏移量與A、D與O′的偏移量相等，因此得到A、B、C、D坐標。

圖2　帶寬度直線矩形域圖

平移AB用Bresenham算法計算出下一個端點B′點坐標時，直接使用OO′的dy代替AD的dx，OO′的dx代替AD的dy，保證AD最大限度垂直于OO′。BC直線上的做法相同，保證新產(chǎn)生A′B′的OO′與平行。這樣就可以保證線段兩端與線段垂直。

2　實驗結(jié)果及分析

2.1顯示效果

圖3是本算法生成的直線顯示圖。從圖中可以看出，該算法產(chǎn)生的直線的兩端與邊界垂直，而且能很好地控制定制直線的寬度，使其在角度變化的情況下，直線寬度基本沒有變化。

圖3　不同斜率下生成的直線

2.2復(fù)雜度分析

以斜率絕對值小于1為例。設(shè)長度為a，寬度為b，則一共有a×b個像素需要點亮。其運算量主要在于計算像素點的坐標。在第一次計算完成邊界線AB后，其Y坐標變化被存儲起來，由于以后畫出的直線與第一條直線平行，因此以后每次計算坐標只需要加上內(nèi)存讀取器Y坐標的變化0或者1。其復(fù)雜度近似為O（N）。

下面為本算法使用Keil軟件在Cortex-M4內(nèi)核下仿真的結(jié)果。其中圖4為長度20、寬度5不變，角度變化下4種算法產(chǎn)生線段時間；圖5為寬度5、角度30不變，長度變化下4種算法產(chǎn)生線段時間；圖6為長度36、角度30不變，寬度變化下4種算法產(chǎn)生線段時間圖。

圖4　角度變化下，運算時間曲線圖

圖5　長度變化下，運算時間曲線圖

圖6　寬度變化下，運算時間曲線圖

注：以上長度、寬度單位為像素，而角度單位為度，運算時間單位為微秒。

由于平行線采用的是線段平移，而且該線刷子法產(chǎn)生的多寬度直線的寬度小于實際直線，因此該算法的效率最高；而正方形刷子法由于像素大量冗余填寫，因此其效率很低；而區(qū)域種子填充算法采用的是種子填充算法，需要頻繁地出棧、入?；蛘哌f歸，因此效率也相對比較低。而本文提出的方法在效率上和線刷子法最接近，而且能夠控制寬度，兩端與直線完全垂直，產(chǎn)生很好的效果。

2.3內(nèi)存消耗分析

為了加快運算速度，本文中的線刷子算法使用內(nèi)存存儲單線段在X（dx＞dy）變化下Y軸的變化量（1或者0），因此其使用的內(nèi)存為dx，單位bit。正方形刷子算法不需要儲存額外數(shù)據(jù)，不需要額外內(nèi)存。種子填充算法需要出棧入棧，因此需要很大的?？臻g。而本論文提出的算法同樣采用這種方案加快運行速度，因此其使用與線刷子算法相同，額外占用的內(nèi)存空間很小。

3　結(jié)論

為了解決現(xiàn)存任意直線生成算法的弊端，提出一種基于Bresenham的算法。本算法首先計算出直線所形成的區(qū)域，然后利用斜率、長度相同單直線沿著邊沿掃描整個區(qū)域，從而實現(xiàn)區(qū)域填充。該算法不僅始末端的效果好，寬度與理想直線接近，在斜率變化時基本不發(fā)生變化，而且算法復(fù)雜度小，適用于各種嵌入式設(shè)備中。圖7是本算法應(yīng)用在一嵌入式系統(tǒng)中的心電圖demo實例，其中心電圖的曲線是用幾段直線替代的。

圖7　算法醫(yī)療應(yīng)用demo

［1］JAMES D F，ANDRIES V D，STEVEN K F，et al.Computer graphics：principles，second edition in C［M］.Pearson Education Press，2004：21-35.［2］BOYER V，BOURDIN J J.Auto-adaptive step straight-line algorithm［J］.IEEE Computer Graphics and Applications，2000，20（5）：67-69.

［3］謝瑩，許榮斌，趙宏坤.基于嵌入式圖形系統(tǒng)的改進Bresenham反走樣算法［J］.計算機技術(shù)與發(fā)展，2006，16（11）：100-102.

［4］駱朝亮，謝忠.一種快速的多線寬直線反走樣算法［J］.計算機工程與應(yīng)用，2011，47（21）：188-190.

［5］李震霄，何援軍.任意寬度直線的繪制與反走樣［J］.武漢大學(xué)學(xué)報（工學(xué)版），2006，39（4）：130-133.

［6］龍艷婷.任意寬度直線生成算法的研究與實現(xiàn)［J］.沈陽工程學(xué)院學(xué)報（自然科學(xué)版），2012，8（4）：353-355，358.

Arbitrary width line generation based on Bresenham algorithm

Yin Hongsong1，Tang Liping1，Zeng Peifeng2
（1.College of Information Science and Technology，Donghua University，Shanghai 201620，China；2.College of Computer Science and Technology，Donghua University，Shanghai 201620，China）

The line generation algorithm is the basic graphics algorithm.And the existing algorithm have its drawbacks.So it is necessary to present an algorithm to generate a straight line of arbitrary width based on Bresenham.The algorithm firstly calculated line boundary according to the slope，length and width of lines，then uses single line with the same slope to fill the whole area.The ends of lines generated is vertical to the boundary line and its width does not change when its slope changes.This algorithm has extensive application background，fast operation speed，and small memory characteristics etc.

arbitrary line generation；Bresenham；area fill

TP311.1

A

1674-7720（2015）16-0024-03

尹洪松，唐莉萍，曾培峰.基于Bresenham的任意寬度直線生成算法［J］.微型機與應(yīng)用，2015，34（16）：24-26，29.

2015-03-17）

尹洪松（1991-），男，碩士研究生，主要研究方向：嵌入式開發(fā)。

唐莉萍（1957-），女，副教授，主要研究方向：圖像處理及模式識別、電子電路設(shè)計、嵌入式系統(tǒng)。