基于邊界定位和對(duì)稱性的高速圖像旋轉(zhuǎn)算法

崔振輝，李林川，龐 景

(1. 天津大學(xué)智能電網(wǎng)教育部重點(diǎn)實(shí)驗(yàn)室，天津 300072；2. 天津市電力通信公司，天津 300010；3. 中國(guó)人民解放軍93619部隊(duì)，天津 301716)

隨著計(jì)算機(jī)技術(shù)、傳感器技術(shù)和圖像處理技術(shù)的更新與發(fā)展，電力設(shè)備在線監(jiān)測(cè)系統(tǒng)的應(yīng)用不斷普及．?dāng)?shù)字圖像處理作為在線監(jiān)測(cè)系統(tǒng)的一個(gè)重要研究領(lǐng)域，同時(shí)也是計(jì)算機(jī)圖像處理軟件的一項(xiàng)核心技術(shù)．在數(shù)字圖像處理過(guò)程中，經(jīng)常要用到旋轉(zhuǎn)，一般的嵌入式設(shè)備的圖像處理硬件加速能力較弱，而大數(shù)據(jù)量圖像的實(shí)時(shí)旋轉(zhuǎn)對(duì)計(jì)算能力要求頗高，運(yùn)算量極大，非常耗時(shí)，導(dǎo)致系統(tǒng)圖像旋轉(zhuǎn)速度偏慢，看似簡(jiǎn)單的圖像旋轉(zhuǎn)問(wèn)題成為了快速圖像處理的瓶頸．

現(xiàn)有的一些典型圖像旋轉(zhuǎn)算法由于各自存在的問(wèn)題都不宜直接應(yīng)用于監(jiān)測(cè)系統(tǒng)對(duì)大量高精度圖像的實(shí)時(shí)處理．例如：直接法[1-2]的計(jì)算復(fù)雜度較大，需依次對(duì)每個(gè)目標(biāo)像素進(jìn)行逆向映射和插值運(yùn)算，執(zhí)行效率非常低；三步法[3-6]是將旋轉(zhuǎn)矩陣分解成 3個(gè)簡(jiǎn)單的錯(cuò)切變換矩陣之積，每個(gè)錯(cuò)切變換都可以通過(guò)水平(豎直)地平移一行(列)像素來(lái)實(shí)現(xiàn)，這需要按列進(jìn)行運(yùn)算，違反了程序的局部性原理，不適宜用來(lái)處理大數(shù)據(jù)量圖像；基于快速傅里葉變換(fast Fourier transform，F(xiàn)FT)的旋轉(zhuǎn)算法[7-9]也是將旋轉(zhuǎn)分成 3步來(lái)實(shí)現(xiàn)，每一步使用一維的 FFT變換對(duì)圖像進(jìn)行重采樣來(lái)實(shí)現(xiàn)，此過(guò)程將頻繁地進(jìn)行圖像由空域到頻域，然后再由頻域到空域的轉(zhuǎn)換，且需要 2次對(duì)過(guò)渡圖像進(jìn)行存儲(chǔ)，增大了內(nèi)存開銷，在處理大數(shù)據(jù)量時(shí)執(zhí)行效率較低；基于Bresenham畫線法的快速旋轉(zhuǎn)算法[10-15]采用了增量定位的思想來(lái)計(jì)算逆向映射點(diǎn)的位置，減少了旋轉(zhuǎn)過(guò)程中大量的浮點(diǎn)運(yùn)算及取整運(yùn)算，很大程度上提高了圖像旋轉(zhuǎn)的整體效率，但該算法的缺點(diǎn)是會(huì)出現(xiàn)較明顯的邊緣鋸齒現(xiàn)象，降低了圖像旋轉(zhuǎn)質(zhì)量．

在以上研究的基礎(chǔ)上，筆者提出了一種基于邊界定位及對(duì)稱性的高速圖像旋轉(zhuǎn)算法，大大提高了圖像旋轉(zhuǎn)速度，并且保證了圖像的旋轉(zhuǎn)質(zhì)量，滿足了電力系統(tǒng)在線監(jiān)測(cè)中數(shù)字圖像處理的需要．

1 基于Bresenham畫線法的快速圖像旋轉(zhuǎn)算法的優(yōu)缺點(diǎn)分析

在笛卡兒坐標(biāo)系中，以圖像的中心為原點(diǎn)O，向右為x軸正方向，向上為y軸正方向，圖像中的任一點(diǎn) ( x0, y0)，以圖像的中心為圓心順時(shí)針旋轉(zhuǎn)α角后坐標(biāo)變?yōu)?x, y)，則有

因?yàn)橄到y(tǒng)實(shí)際要用的是屏幕坐標(biāo)系，屏幕坐標(biāo)系以左上角為原點(diǎn)，向右為x軸正方向，向下為y軸正方向，因此要進(jìn)行 2種坐標(biāo)系間的平移轉(zhuǎn)換．屏幕坐標(biāo)系和笛卡兒坐標(biāo)系的對(duì)應(yīng)關(guān)系如圖 1所示，圖中O1、O2代表屏幕坐標(biāo)系，( x1, y1)、(x2,y2)分別為 O1、O2中的任一點(diǎn)， O0代表笛卡兒坐標(biāo)系，設(shè)圖像的寬和高分別為 w和h，目標(biāo)圖像的寬和高分別為 w1和 h1．

圖1 不同坐標(biāo)系對(duì)照Fig.1 Mapping relation of different coordinate systems

則坐標(biāo)系1O變成坐標(biāo)系0O的變換矩陣為

坐標(biāo)系0O變成坐標(biāo)系2O的變換矩陣為

故可通過(guò)3次數(shù)學(xué)運(yùn)算來(lái)完成圖像的旋轉(zhuǎn)，首先應(yīng)用式(2)將坐標(biāo)系1O變成坐標(biāo)系0O，然后應(yīng)用式(1)在坐標(biāo)系0O中將該點(diǎn)順時(shí)針旋轉(zhuǎn)某一角度，最后應(yīng)用式(3)將坐標(biāo)系平移到新的屏幕坐標(biāo)系2O中．這樣，就得到了旋轉(zhuǎn)變換矩陣

式(4)采用的是正向映射法，是上面 3個(gè)矩陣的級(jí)聯(lián)．在圖像的幾何旋轉(zhuǎn)變換中一般采用逆向映射法，即首先生成一個(gè)空白目標(biāo)圖像，然后依次求出每個(gè)目標(biāo)像素映射在原圖像中的對(duì)應(yīng)位置，并得到它的灰度值，將其拷貝至目標(biāo)圖像，如果超出原圖范圍，則將灰度值置成255．式(4)的逆變換為

以上即為運(yùn)用直接法進(jìn)行圖像旋轉(zhuǎn)的過(guò)程，該方法是圖像旋轉(zhuǎn)最樸素思想的表現(xiàn)，體現(xiàn)了旋轉(zhuǎn)的基本原理，缺點(diǎn)是需要逐個(gè)像素點(diǎn)進(jìn)行精確的逆向映射計(jì)算，效率低下．基于 Bresenham畫線法的快速圖像旋轉(zhuǎn)法[10]則采用了增量定位思想，即在逐點(diǎn)計(jì)算目標(biāo)圖像中的點(diǎn)在原圖像中的對(duì)應(yīng)位置時(shí)，不必每次都重新計(jì)算精確的坐標(biāo)，只需通過(guò)當(dāng)前點(diǎn)以及一個(gè)決策函數(shù)來(lái)動(dòng)態(tài)地判斷其位置．這個(gè)決策函數(shù)的計(jì)算比較簡(jiǎn)單，只涉及一些簡(jiǎn)單的整數(shù)加減運(yùn)算．

假設(shè)變換后圖像中的某一像素點(diǎn)的逆向映射實(shí)數(shù)坐標(biāo)為(xp, yp)，離該實(shí)數(shù)坐標(biāo)最近的像素點(diǎn)坐標(biāo)(即整數(shù)坐標(biāo))為(ap, bp)．為了確定下一個(gè)像素點(diǎn)的具體映射位置，該算法引入了Bresenham畫線法中的誤差項(xiàng)的概念，即記錄映射點(diǎn)與其最鄰近的像素點(diǎn)之間的誤差．以逐行確定像素點(diǎn)的逆向映射位置為例，定義行和列方向上的誤差分別為 a x=xp?ap，ay = yp? bp．在決定下一個(gè)相鄰像素點(diǎn)的映射位置時(shí)，先更新誤差項(xiàng)，令 a x = ax + cosα，a y = a y ? s inα．當(dāng) a x＞ 0 .5時(shí)，原來(lái)的 ap增加 1，并且將ax本身減 1；否則，保持 ap不變．類似地，當(dāng) a y＜?0 .5時(shí)，將原來(lái)的 bp減 1，并且ay自身加 1；否則，保持 bp不變．逐列確定像素點(diǎn)仍有以上類似的遞推公式．

上述基于 Bresenham畫線法的快速圖像旋轉(zhuǎn)法進(jìn)行圖像旋轉(zhuǎn)時(shí)，需要進(jìn)行 4次浮點(diǎn)乘法以及在行、列方向上的 2次取整運(yùn)算來(lái)確定目標(biāo)圖像中第 1行第1列像素點(diǎn)的逆向映射位置，其余像素點(diǎn)的定位可僅通過(guò)簡(jiǎn)單地判別誤差項(xiàng)的大小和位置增量來(lái)進(jìn)行．此方法完全消除了傳統(tǒng)實(shí)現(xiàn)方法中雙層循環(huán)內(nèi)大量的浮點(diǎn)乘法及取整運(yùn)算，大幅度地提高了圖像的旋轉(zhuǎn)效率，但是在進(jìn)行圖像旋轉(zhuǎn)時(shí)會(huì)出現(xiàn)較明顯的邊緣鋸齒問(wèn)題，分析如下．

就圖 2而言，在計(jì)算原圖像左邊緣像素點(diǎn)f的逆向映射位置時(shí)，其求取過(guò)程是以與該像素點(diǎn)位于同一行的第 1個(gè)像素點(diǎn)p的逆向映射柵格位置 k ( m , n)為基點(diǎn)，并結(jié)合誤差項(xiàng)ax和ay的判別來(lái)進(jìn)行的．當(dāng)ax＞ 0 .5時(shí)，m++，ax??；類似地，當(dāng) a y＜? 0 .5時(shí)，n??，ay++，依此類推，直到求出點(diǎn) f的逆向映射位置為止．由此可見，在上述計(jì)算過(guò)程的開始就引入了舍入誤差δ(?0.5≤δ≤0.5)，此舍入誤差δ又將會(huì)被帶入下一個(gè)像素點(diǎn)q的求取過(guò)程中．因此，相對(duì)于運(yùn)用直接法而言，計(jì)算邊緣像素點(diǎn)的逆向映射位置的誤差就增大了，從而導(dǎo)致了目標(biāo)圖像中比較明顯的邊緣鋸齒現(xiàn)象．

圖2 邊緣像素點(diǎn)示意Fig.2 Schematic diagram of edge pixels

由前面的分析可知，若使得基點(diǎn)k落在原圖像邊界線上，則可以較大程度地消除邊緣鋸齒現(xiàn)象，這也正是本文提出邊界定位思想的緣由所在．

2 基于邊界定位和對(duì)稱性的高速旋轉(zhuǎn)算法

2.1 邊界定位思想的應(yīng)用

由上節(jié)可知，基于Bresenham畫線法的快速圖像旋轉(zhuǎn)法會(huì)產(chǎn)生邊緣鋸齒現(xiàn)象，針對(duì)此問(wèn)題，采用了邊界定位思想，首先確定原圖像邊界線在目標(biāo)圖像中的方程表達(dá)式，然后結(jié)合掃描行i的值直接確定該掃描行的目標(biāo)圖像邊緣像素點(diǎn)的具體位置，采用直接法對(duì)該邊界像素點(diǎn)進(jìn)行逆向映射的定位處理，因此可以消除基于 Bresenham畫線法的旋轉(zhuǎn)法所產(chǎn)生的圖像邊緣鋸齒問(wèn)題；同時(shí)也可跳過(guò)目標(biāo)圖像邊界線外大量不需要處理的目標(biāo)像素點(diǎn)，省去了無(wú)關(guān)計(jì)算量．

考慮旋轉(zhuǎn)角度 α ∈ ( 0,π / 2)的情況，其他區(qū)間可以進(jìn)行類似地推導(dǎo)．

在圖 3中，設(shè)原圖像的 4個(gè)頂點(diǎn)在坐標(biāo)系 O0下的點(diǎn)分別為A、B、C、D，根據(jù)旋轉(zhuǎn)公式得到該 4個(gè)頂點(diǎn)旋轉(zhuǎn)后的坐標(biāo)分別為分別再經(jīng)過(guò)坐標(biāo)平移公式

圖3 邊界定位示意Fig.3 Schematic diagram of boundary location

有了坐標(biāo)系 O1下的 4個(gè)坐標(biāo)，則可以確定原圖像中4條邊界線旋轉(zhuǎn)后的直線 l0、l1、l2、l3的方程表達(dá)式．直線方程的逆表達(dá)式為 x = s lope y+const,其求解過(guò)程如下．

首先，求得直線的斜率．直線1l和2l的斜率為直線0l和3l的斜率為

其次，根據(jù)公式const = x ? s lopey可確定直線方程的常數(shù)項(xiàng)．直線 l0、l1、l2、l3的常數(shù)項(xiàng)分別為edgeConst0、e d geConst1、e d geConst2、e d geConst3．

在逐行掃描目標(biāo)圖像并進(jìn)行像素點(diǎn)的逆向映射位置求取時(shí)，首先要對(duì)掃描行i的值進(jìn)行判斷，以確定需要參與運(yùn)算的直線方程；然后再通過(guò)該直線方程表達(dá)式進(jìn)一步求得目標(biāo)圖像掃描行i中的左邊緣像素點(diǎn)所在的列左邊界和右邊緣像素點(diǎn)所在的列右邊界．例如：圖 3中目標(biāo)圖像第i行的左邊界和右邊界的表達(dá)式分別為 b oundLeft=slopeLeft i + e dgeConst1和boundRight=slopeRight i + e dgeConst3．

由推導(dǎo)可知，根據(jù) 4條邊界線 l0、l1、l2、l3的直線方程，并結(jié)合對(duì)圖像掃描行值的判斷，可依次計(jì)算出目標(biāo)圖像中每個(gè)像素行的左、右邊緣像素點(diǎn)所在列的值．為了有效地解決基于 Bresenham畫線法的圖像旋轉(zhuǎn)法出現(xiàn)的邊緣鋸齒問(wèn)題，采用直接法對(duì)左、右邊緣像素點(diǎn)進(jìn)行處理．因?yàn)橹苯臃▏?yán)格遵守旋轉(zhuǎn)的數(shù)學(xué)模型，沒(méi)有引入中間誤差，能夠使原圖像的邊界像素點(diǎn)進(jìn)行較精確地定位，從而平滑了旋轉(zhuǎn)后的圖像邊緣，并且通過(guò)定位還可以省去圖像邊界線外大量無(wú)關(guān)目標(biāo)像素點(diǎn)的計(jì)算量．

2.2 圖像對(duì)稱思想的應(yīng)用

在圖 4所示的坐標(biāo)系 OA中，由原矩形圖像的像素柵格示意可知，對(duì)于圖像內(nèi)任意像素點(diǎn) p ( x0,y0)，都有唯一像素點(diǎn) q ( x1, y1)與其關(guān)于圖像的中心點(diǎn)坐標(biāo)對(duì)稱．易知，其旋轉(zhuǎn)后分別映射在目標(biāo)圖像中的像素點(diǎn)與像素點(diǎn)同樣關(guān)于目標(biāo)圖像的中心點(diǎn)坐標(biāo)對(duì)稱，反之亦然．因此，在逐行逐列進(jìn)行目標(biāo)像素點(diǎn)的逆向映射位置計(jì)算時(shí)，只需對(duì)目標(biāo)圖像的上半部分像素點(diǎn)進(jìn)行計(jì)算，其下半部分像素點(diǎn)的映射位置可由對(duì)稱性關(guān)系求得，因此新圖像中像素點(diǎn)的逆向映射運(yùn)算次數(shù)由原來(lái)的次減為

圖4 圖像像素柵格示意Fig.4 Schematic diagram of image pixel-grid

3 實(shí)驗(yàn)及分析

3.1 旋轉(zhuǎn)效果對(duì)比

新型旋轉(zhuǎn)算法是在基于 Bresenham畫線法的基礎(chǔ)上，采用傳統(tǒng)的直接法對(duì)原圖像的邊緣像素進(jìn)行處理，大大消除了圖像旋轉(zhuǎn)后的邊緣鋸齒現(xiàn)象，提高了旋轉(zhuǎn)圖像的質(zhì)量．實(shí)驗(yàn)中分別運(yùn)用直接法、基于Bresenham畫線法和基于邊界定位和對(duì)稱性算法對(duì)一幅大小為 128×128像素的 24位真彩色位圖進(jìn)行45°旋轉(zhuǎn)，以上 3種算法均采用最臨近插值法，其效果如圖5所示．

由圖5可以看出，基于邊界定位和對(duì)稱性的算法在旋轉(zhuǎn)效果上優(yōu)于基于Bresenham畫線法的旋轉(zhuǎn)法，與直接法在采用相同插值方式的情況下圖像的旋轉(zhuǎn)質(zhì)量是非常接近的，從而保證了圖像的旋轉(zhuǎn)質(zhì)量．

圖5 3種算法的旋轉(zhuǎn)效果對(duì)比Fig.5 Comparison of rotation effects of three algorithms

3.2 時(shí)間效率對(duì)比

為了驗(yàn)證該新型算法的有效性，對(duì)不同尺寸的24位真彩色位圖進(jìn)行了旋轉(zhuǎn)對(duì)比實(shí)驗(yàn)，實(shí)驗(yàn)過(guò)程如下：首先將一幅24位真彩色位圖分別存儲(chǔ)為 128×128，256×256…等不同大小尺寸的位圖作為旋轉(zhuǎn)測(cè)試樣本，然后在采用同一種插值算法的前提下，分別采用不同旋轉(zhuǎn)算法對(duì)測(cè)試樣本進(jìn)行旋轉(zhuǎn) 30°的操作．為了盡量避免一些不確定因素的干擾，每種算法對(duì)每個(gè)測(cè)試樣本均進(jìn)行100次旋轉(zhuǎn)操作，取其時(shí)間開銷平均值作為該算法的時(shí)間開銷．

測(cè)試結(jié)果如表1和圖6所示，表1中，T1為直接法的時(shí)間開銷；T2為三步法的時(shí)間開銷；T3為基于Bresenham 畫線法的旋轉(zhuǎn)算法(為了敘述方便以下簡(jiǎn)稱為畫線法)的時(shí)間開銷；T4為結(jié)合圖像對(duì)稱性的畫線法的時(shí)間開銷；T5為基于邊界定位及對(duì)稱性的旋轉(zhuǎn)算法的時(shí)間開銷．

從表1和圖6可以看出，后3種算法較直接法在旋轉(zhuǎn)速度上有較大優(yōu)勢(shì)；在圖像像素較少的情況下，三步法優(yōu)于直接法，但是當(dāng)圖像增大到一定程度時(shí)，三步法的局部性問(wèn)題將導(dǎo)致其時(shí)間總開銷有所加大；結(jié)合圖像對(duì)稱性的畫線法和基于邊界定位及對(duì)稱性的算法都要比原畫線法效率要高，其中前者較原畫線法提高了 0.89倍，而較直接法提高了 3.94倍，后者較原畫線法提高了 0.54倍，而較直接法提高了 3.11倍；另外，基于邊界定位及對(duì)稱性的算法之所以比結(jié)合圖像對(duì)稱性的畫線法時(shí)間效率要低些，是因?yàn)樵撍惴榱讼龍D像邊緣鋸齒現(xiàn)象，在處理邊緣像素點(diǎn)時(shí)采用了傳統(tǒng)的直接法，相對(duì)增加了計(jì)算量，從而增加了圖像旋轉(zhuǎn)的時(shí)間開銷．

表1 采用最鄰近插值的時(shí)間測(cè)試結(jié)果Tab.1 Time-cost of different algorithms using the nearest neighbor interpolation ms

圖6 不同算法的時(shí)間效率比較Fig.6 Comparison of time-cost among different algorithms

4 結(jié) 語(yǔ)

從基于 Bresenham畫線法的快速圖像旋轉(zhuǎn)算法易產(chǎn)生邊緣鋸齒現(xiàn)象的原因進(jìn)行分析，提出了一種的基于邊界定位和對(duì)稱性的高速圖像旋轉(zhuǎn)算法．從實(shí)驗(yàn)數(shù)據(jù)可以看出本文中提出的快速旋轉(zhuǎn)算法的旋轉(zhuǎn)速度較當(dāng)前幾種典型的算法有了大幅度的提高，并且保證了圖像的旋轉(zhuǎn)質(zhì)量．該算法具有通用性，可以推廣到更廣闊的圖像處理領(lǐng)域中，比如電力設(shè)備在線監(jiān)測(cè)系統(tǒng)的應(yīng)用，圖像處理軟件的開發(fā)，醫(yī)學(xué)、遙感圖像的快速處理等．

［1］ Lee Sung-myun. Apparatus and Method to Rotate a Bitmap Image：USA，2008/0025641 AI[P]. 2008-01-31.

［2］ 古麗娜，木妮娜. 圖像幾何變換的理論及 MATLAB實(shí)現(xiàn)[J]. 新疆師范大學(xué)學(xué)報(bào)：自然科學(xué)版，2006，25(4)：24-28.Gulina，Munina. Theory and implementation in MATLAB for image geometry transform [J]. Journal of Xinjiang Normal University：Natural Science Edition，2006，25(4)：24-28(in Chinese).

［3］ 陳 芳，趙樹宇. 基于錯(cuò)切原理的三步切移旋轉(zhuǎn)算法的優(yōu)化[J]. 淮陰師范學(xué)院學(xué)報(bào)：自然科學(xué)版，2006，5(3)：254-258.Chen Fang，Zhao Shuyu. The optimized algorithm of image rotation based on shear principle[J]. Journal of Huaiyin Teachers College：Natural Science Edition，2006，5(3)：254-258(in Chinese).

［4］ Danielsson P E，Hemmerin M. High accuracy rotation of images[J]. CVGIP：Graphical Models and Image Processing，1992，54(4)：340-344.

［5］ 陳 芳. 圖像的旋轉(zhuǎn)插值算法和基于鏈碼技術(shù)計(jì)算圖像幾何矩的算法研究[D]. 上海：華東師范大學(xué)信息科學(xué)與技術(shù)學(xué)院，2006.Chen Fang. The Study on Methods of Image Rotation，Interpolation and Computation for Geometry Moment Based on Chain Code [D]. Shanghai：School of Information Science and Technology，East China Normal University，2006(in Chinese).

［6］ Unser M，Thevenaz P，Yaroslavsky L. Convolution-based interpolation for fast，high quality rotation of images[J]. IEEE Transactions on Image Processing，1995，4(10)：1371-1381.

［7］ Yokota Y，Tomita M，Hashimoto H，et al. Construction of an on-line system for FFT processing and analysis of atomic resolution microscopic images and its applications[J]. Ultramicroscopy，1981，6(4)：313-321.

［8］ 汪國(guó)有，項(xiàng)國(guó)平，孫天春. 利用 FFT實(shí)現(xiàn)圖像的快速高質(zhì)量旋轉(zhuǎn)變換[J]. 華中科技大學(xué)學(xué)報(bào)：自然科學(xué)版，2003，31(4)：91-93.Wang Guoyou，Xiang Guoping，Sun Tianchun. Algorithm for the rotation transformation of image by using FFT with fast and high quality[J]. Journal of Huazhong University of Science and Technology：Nature Science Edition，2003，31(4)：91-93(in Chinese).

［9］ Larkin K G，Oldfield M A，Klemm H. Fast Fourier method for the accurate rotation of sampled images[J].Optics Communications，1997，139(1/2/3)：99-106.

［10］ 石 慎，張艷寧，郗潤(rùn)平，等. 基于 Bresenham 畫線算法的圖像快速-高精度旋轉(zhuǎn)算法[J]. 計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2007，19(11)：1387-1392.Shi Shen，Zhang Yanning，Xi Runping，et al. A fasthigh-quality image rotation approach based on Bresenham algorithm[J]. Journal of Computer-Aided Design and Computer Graphics，2007，19(11)：1387-1392(in Chinese).

［11］ 賈銀亮，張煥春，經(jīng)亞枝. Bresenham 直線生成算法的改進(jìn)[J]. 中國(guó)圖象圖形學(xué)報(bào)，2008，13(1)：158-161.Jia Yinliang，Zhang Huanchun，Jing Yazhi. A modified Bresenham algorithm of line drawing[J]. Journal of Image and Graphics，2008，13(1)：158-161(in Chinese).

［12］ Pitteway M L V，Watkinson D J. Bresenham’s algorithm with grey scale [J]. Communications of the ACM，1980，23(11)：625-626.

［13］ Chien Sung-Il，Baek Yung-Mok. A fast black run rotation algorithm for binary images[J]. Pattern Recognition Letters，1998，19(5/6)：455-459.

［14］ Catanzaro Bryan，Su Bor-Yiing，Sundaram Narayanan.Efficient，high-quality image contour detection[C]//2009 IEEE 12th International Conference on Computer Vision. Kyoto，Japan，2009：2381-2388.

［15］ Au Chikit，Woo Tony. Three-dimensional extension of Bresenham’s algorithm with Voronoi diagram[J]. Computer-Aided Design，2011，43(4)：417-426.