結合Bresenham直線算法的運動模糊方向判斷方法

梁 菁

（梧州學院 計算機科學系，梧州 543002）

0 引言

在拍攝時成像設備和被拍攝景物之間發生相對運動而造成圖像模糊稱為運動模糊。在我們國家，許多城市的道路上都安裝有“天眼”設備，高速公路的收費站也設有攝像頭，這些攝像設備能夠拍攝下所有經過車輛包括車牌號碼、車型等信息的圖像。但圖像形成時由于車輛大多數處于運動的狀態而產生了模糊的現象，這就是運動模糊。圖像模糊給識別車輛信息造成了麻煩，所以我們要利用一些方法對圖像進行恢復，以獲取需要的信息。

在圖像的拍攝形成、存儲、傳輸和輸出顯示過程中，受到噪聲或相對運動的影響，會發生不同程度的變質、失真和退化。根據模糊圖像提供的信息，運用某些先驗知識，建立數學模型，從而將退化圖像以最大的保真度恢復原來的圖像，便是圖像恢復的目標和任務[1]。

目前已經有許多運動模糊圖像復原的算法，如維納濾波法、L-R算法，但這些算法都要求有足夠的退化知識，知道點擴散函數才能對模糊圖像進行恢復。對于實際拍攝所得的模糊圖像，在恢復之前就必須先求出相應的點擴散函數PSF(Point Spread Function)[2]，才能用上述的恢復算法進行圖像復原。

勻速直線運動模糊圖像的點擴散函數由模糊運動的方向與運動長度來確定，所以求出圖像運動的方向以及運動了多長的距離是恢復過程中重要的步驟。

一些學者[3]提出了應用倒頻譜分析法估算PSF參數的方法，但這種方法在模糊長度范圍為5至55像素時估算誤差較小，當模糊長度超過這個范圍時，誤差值會急劇增加。有研究人員[4]提出對模糊圖像進行兩次傅立葉變換，對處理后的圖像利用灰度統計方法檢測傾斜角以判斷運動方向的方法，但沒有給出實現的具體算法。而且在文獻給出的兩次傅立葉變換后的圖像中，所提及的這種計算方法核心的部分—亮線并不明顯，給圖像灰度統計帶來不少難度。

本文提出一種結合計算機圖形學中Bresenham算法對圖像的頻譜圖進行灰度求和進而確定運動模糊方向的算法。

1 運動模糊的原理及分析

數字圖像在計算機上是以位圖的形式存在的，位圖是一個矩形點陣，矩形點陣中每個元素稱為像素，它是數字圖像中的基本單位。一幅M×N大小的圖像，是由M×N個明暗不等的像素組成。在數字圖像中各個象素的明暗程度是由灰度值來表示的。若將白色的灰度值定義為255，黑色的灰度值定義為0，則由黑到白的明暗度可以均勻地劃分為256個等級，每個等級表示一種唯一的灰度。

圖像的運動模糊是在成像設備快門開啟至關閉這一曝光過程中被攝物和成像系統相對運動造成的。我們以勻速直線運動模糊為例來進行討論。因為勻速直線運動模糊圖像具有一般性和代表性，變速的、非直線的運動在成像瞬間可以視為勻速直線運動。

所以從物理現象上看，運動模糊圖像實際上就是同一景物圖像經過一系列距離延遲后再疊加，最終形成的圖像。而我們所處理的數字圖像由若干個像素來構成，所以圖像運動實際上是組成這幅圖像的所有像素進行移動。

一幅圖像可以定義為一個二維函數f(x,y),其中x和y是空間坐標，而f在任意一對(x,y)處的幅度稱為該點處圖像的灰度或亮度。在線性平移空間不變運動模糊系統中，用f(x,y)表示輸入的原始圖像，g(x,y)表示輸出的模糊圖像，則兩者的關系可以用下面的方程來表示：

其中h(x,y)為退化函數的空間表示，n(x,y)表示加性噪聲。為了將問題簡化，暫時不考慮噪音的影響，則(1)方程簡化為：

由于空間域的卷積等同于頻域的乘積，所以(2)中各項經過傅立葉變換后，可以用等價的頻域表示來表達：

假設在成像設備的快門開啟到關閉這段曝光時間T內圖像運動距離為L，則：

若H(u,v)在某一對確定的(u,v)處值為零，那G(u,v)在對應于該組(u,v)處也為零。也就是說G(u,v)和H(u,v)有相同的零點，G(u,v)的頻譜也會有一系列與sinc(π×(u×cosθ+v×sinθ)×L)的零點對應的暗條紋。

但是模糊圖像經傅立葉變換后的頻譜圖并沒有什么直觀的規律可循，這是由于傅立葉頻譜的范圍為[0,106]，甚至更高。當頻譜顯示在線性縮放至8比特的監視器上時，高值部分占優，導致頻譜中低亮度值的可視細節丟失。于是進一步對頻譜作對數變換，將其動態范圍大幅度降低，使可視細節增加，方便觀察。

模糊圖像經過對數變換后，可以清楚地看到其傅氏頻譜圖中條紋的存在，但條紋的走向規律還不是十分一目了然，仍舊不便于觀察研究。所以為了簡化頻譜的視覺分析，將原點的變換值由圖像左上角的位置移動到頻率矩形的中心位置。

這樣條紋的走向更加清晰并且有規律可循了。將不同模糊方向的頻譜進行比較分析,發現頻譜圖中條紋的方向與模糊圖像的運動方向總是垂直的。只要能判斷出條紋方向的角度，就可以計算出運動的角度。頻譜圖中條紋有著對稱性，過圖像中心的條紋寬度最大，其它條紋均勻對稱分布在其兩邊。但如此多的條紋不便于確定角度，根據傅立葉變換的互異性[5]，再對經過位移處理后的頻譜圖做傅立葉變換。

沿水平方向成30度角運動的模糊圖像頻譜圖經過對數變換、位移處理、二次傅立葉變換的頻譜圖如圖1所示。

圖1 圖像頻譜圖

從圖1(c)中可以觀察到在圖像的運動方向上，其對應的頻譜有一條明顯的亮線，檢測這條亮線與水平方向的夾角便可以直接得出運動的方向了。若要對圖4中的亮線測試角度，可以采取灰度求和的方法。以圖像中心作為直線其中一個端點，在與水平方向0°至180°范圍內計算每個角度對應直線的灰度值，哪個角度對應的直線灰度值最大，該直線必定就是那條亮線，角度便可以確定了。

2 Bresenham直線生成算法

要計算某條直線的灰度，實際上是求那條直線上所有點的灰度和。要快速確定哪些像素點落在同一條直線上，可以使用計算機圖形學中的Bresenham算法[6,7]。此算法因由J.E. Bresenham提出而得名。因為在圖形顯示設備上顯示直線，要由計算機計算出直線上要顯示的各點坐標并逐個顯示這些點。但由于顯示設備所采用的設備坐標系是整數坐標系，直線上的各點，其坐標卻未必正好位于設備坐標系的整數位置上，這就需要選擇距該直線最近的像素點逼近顯示該直線。

所謂“兩點確定一條直線”，要在顯示設備上生成一條直線，首先必須知道直線的兩個端點A(xa,ya)和B(xb,yb),設xB≠xA, yB≠yA。接著便要確定AB之間直線上各個點的坐標。用Bresenham算法確定直線AB上的各點相應坐標，即把直線AB上的點在圖形顯示器上畫出來的步驟如下：

1) 計算點A與點B之間的坐標差值，有Δx=xB-xA, Δy=yB-yA；記錄Δx、Δy的正負，如果Δx＞0，則sx=1, 如果Δx＜0，則sx=-1; 如果Δy＞0，則sy=1, 如果Δy＜0，則sy=-1;

2)對Δ x，Δ y分別取絕對值，得Δx’=|Δx|,Δy’=|Δy|,比較Δx’與Δy’的大小，如果Δx’＞=Δy’則執行步驟3)，否則執行步驟4)；

3)計算偏差判別式的初始值d=2×Δy’-Δx’，確定直線其中一個端點A為當前處理的點，令x=xA, y=yA，重復以下步驟，直至循環次數i＞Δx’;

（1）根據x, y的值畫出當前點；

（2）分別計算更新x、y和d的值，如果d＞=0，那么x=x+sx ,y=y+sy ,d=d-2×(Δx’-Δy’)，否則x=x+sx, d=d+2×Δy’,y的值不變；

（3）循環次數i遞增。

4) 計算偏差判別式的初始值d=2×Δx’-Δy’，確定直線其中一個端點A為當前處理的點，令x=xA, y=yA，重復以下步驟，直至循環次數i＞Δy’;

(1) 根據x, y的值畫出當前點；

渥巴錫之仲兄作為人質死于阿斯特拉罕，史載明確。具體拘禁之地、死亡之地，未留下史載，但人質不是普通的囚犯，將薩賴安置在作為當年阿斯特拉罕衙署所在地的小克里姆林宮、居住在這座白色大樓里，似也不失是一種合理的推測。若如此，小克里姆林宮也是土爾扈特人又一處傷心之地。

(2) 分別計算更新x、y和d的值，如果d＞=0，那么x=x+sx ,y=y+sy ,d=d-2×(Δy’-Δx’)，否則y=y+sy, d=d+2×Δx’,x的值不變；

(3) 循環次數i遞增；

Bresenham直線算法是一個遞推算法，根據當前已知點的坐標推算出下一個點的坐標。在每一步的推算中，都不需要對點坐標x、y的值進行浮點數和四舍五入運算，算法程序運行速度快，利于在硬件上實現。

3 算法的實現

可以總結出確定模糊運動方向的算法步驟：

1) 對模糊圖像做傅立葉變換，將原點的變換值移動到頻率矩形的中心；

2)頻譜圖做對數變換；

4) 計算頻譜圖中亮線與水平方向的夾角度數。

若要計算圖1(c)中的亮線傾斜角度，可以圖像中心作為直線其中一個端點，同時也作為圖像坐標平面的原點，在與水平方向0°至180°范圍內計算每個角度對應直線的灰度值，要計算某條直線的灰度值，實際上是求那條直線上所有點的灰度值之和。具體計算時可以以1°為單位遞增逐個角度檢驗。若對角度精度要求比較高，可以在確定了大概的角度后，再以0.1°為單位遞增角度值做更精確檢測。將每一個角度的正切值計算出來后便可得到對應直線的斜率，有了斜率利用Bresenham算法可以快速確定某一角度值對應的那條直線上的像素點,哪個角度對應的直線灰度值最大，該直線必定就是那條亮線，該直線對應角度即為運動模糊方向。

當模糊運動方向為120°時，用本文提出的算法檢測頻譜圖所得的數據如圖2所示。

圖2 0°至180°灰度值的計算情況

在Matlab 6.5的實驗環境下，先對標準圖像庫中的圖像cameraman.tif用imf i lter函數處理，生成不同運動方向的模糊圖像，然后用結合Bresenham算法的角度估算方法分別判斷各模糊圖像的運動角度，實驗結果如表1所示：

表1 運動模糊角度檢測

實驗證明，本文提出的運動模糊角度判別方法比較準確地判斷出了圖像運動的方向,誤差不超過1°。

4 結束語

本文提出了一種結合計算機圖形學中Bresenham 算法對圖像的頻譜圖進行灰度求和進而確定運動模糊方向的算法。Bresenham 直線算法用于快速生成一條直線，將Bresenham 算法應用于判斷圖像運動方向的方法目的在于快速計算出某一條直線灰度值的和。

經過實驗驗證，本文提出的運動模糊角度判別方法比較準確地判斷出了圖像運動的方向。但這個算法能夠判斷的運動方向只是局限在0°至180°的范圍內，也就是無法區分運動模糊的真實方向是θ=θ’還是θ=θ’+180°。若當運動模糊的真實方向是θ=θ’+180°,而采用θ=θ’作為參數進行圖像恢復，所恢復的圖像幅值不變，只是各像素位移發生變化[8]。

將本文提出算法的判斷估算范圍從0°至180°擴大到0°至360°是今后研究的方向。

[1] 潘琪.運動模糊仿真圖像的正確生成 [D].廣州:暨南大學.2005.

[2] 洪漢玉,陳以超.復雜背景運動模糊圖像的盲復原算法研究[J].計算機與數字工程,2006,34(12):7-11.

[3] 謝偉,秦前清.基于倒頻譜的運動模糊圖像PSF參數估計[J]. 武漢大學學報(信息科學版),2008,33(2):128-131.

[4] 劉微.運動模糊圖像恢復算法的研究與實現[D].北京:中國科學院.2006.

[5] 羅納德·N·布雷斯韋爾著.殷勤業,張建國譯.傅立葉變換及其應用[M] 西安:西安交通大學出版社,2005:24-26.

[6] 魏海濤.計算機圖形學(第2版)[M].北京:電子工業出版社,2007:2-8.

[7] 金延贊.計算機圖形學[M].浙江:浙江大學出版社,2003:134-140.

[8] 蔡慧敏,張艷寧,王志印,段鋒,孫瑾秋.一種勻速直線運動模糊參數估計方法[J].計算機工程與應用,2008,44(19):175-177.