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

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

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

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

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

0　引言

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

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

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

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

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

1　算法思想與步驟

1.1Bresenham算法

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

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

圖1　Bresenham算法誤差項(xiàng)d遞增

1.2多線寬算法

（1）算法思想

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

用內(nèi)存存儲(chǔ)每一列Y的增量，讓單線沿著B(niǎo)resenham算法形成的區(qū)域兩端移動(dòng)，因?yàn)榫€平行，計(jì)算它們連線只需要利用存儲(chǔ)的Y的增量，產(chǎn)生新的直線，形成的直線兩端垂直，且算法計(jì)算簡(jiǎn)單，沒(méi)有種子填充算法的設(shè)定起始種子的局限。

（2）算法基本步驟

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

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

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

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

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

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

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

圖2　帶寬度直線矩形域圖

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

2　實(shí)驗(yàn)結(jié)果及分析

2.1顯示效果

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

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

2.2復(fù)雜度分析

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

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

圖4　角度變化下，運(yùn)算時(shí)間曲線圖

圖5　長(zhǎng)度變化下，運(yùn)算時(shí)間曲線圖

圖6　寬度變化下，運(yùn)算時(shí)間曲線圖

注：以上長(zhǎng)度、寬度單位為像素，而角度單位為度，運(yùn)算時(shí)間單位為微秒。

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

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

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

3　結(jié)論

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

圖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)的改進(jìn)Bresenham反走樣算法［J］.計(jì)算機(jī)技術(shù)與發(fā)展，2006，16（11）：100-102.

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

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

［6］龍艷婷.任意寬度直線生成算法的研究與實(shí)現(xiàn)［J］.沈陽(yáng)工程學(xué)院學(xué)報(bào)（自然科學(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］.微型機(jī)與應(yīng)用，2015，34（16）：24-26，29.

2015-03-17）

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

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