基于改進掃描線逼近的魚眼圖輪廓提取算法的研究

韓迎輝

(常州大學城常州輕工職業技術學院，江蘇常州213164)

為了獲得超寬視角，魚眼鏡頭被大量地應用在群組視頻會議［1］、大范圍監控系統、智能交系統、虛擬實景技術［2］，全景瀏覽及球面電影等領域。魚眼鏡頭可以克服普通鏡頭視場小的缺點，但是魚眼圖像具有嚴重的桶形畸變，在利用魚眼圖像信息之前需要對魚眼圖像進行校正展開。

目前魚眼圖像輪廓提取的算法主要有最小二乘擬合法，面積統計法，區域增長法和掃描線逼近法。最小二乘擬合法［3］提取魚眼輪廓的計算量大并且不一定精確。面積統計法［4］原理簡單但是當有效區域內特別是靠近輪廓有大量黑色像素點存在時計算誤差偏大，而且計算量相對較大，因此適用范圍也有限。區域增長法［5］計算復雜，耗時長，且不一定能夠取得理想結果，更不實用。相比之下，掃描線逼近算法［6-8］的效率最高，效果也比較好，應用廣泛，但仍具有抗噪能力差的缺陷，有些輪廓提取效果還可以提升。本文在已有的掃描線逼近算法的基礎上提出了一種新的魚眼輪廓提取算法，該算法有很強的抗噪能力，能夠精確定位魚眼圖像的中心和半徑，在提高魚眼輪廓提取精度的同時能夠保證不增加運行時間，具有很強的實用價值。

1 傳統的掃描線逼近算法

圖1是一張魚眼鏡頭拍攝的圖像，從圖中可以看出魚眼圖像具有很嚴重的桶形畸變，要想利用魚眼圖像的信息(除了藝術欣賞)就要對魚眼圖像進行校正展開。魚眼圖像的特點是中間圓形區域是圖像涵蓋物景信息的有效區域，四周是黑色的背景部分。在進行魚眼圖像校正之前首先要把魚眼圖像的有效區域提取出來，為后續的魚眼圖像校正做準備。所以說魚眼圖像輪廓的提取效果在魚眼圖像的校正過程中非常重要，常常直接影響圖像的校正結果。

圖1 魚眼圖像

極限亮度差是指圖像中某一行或列的各像素點的最大亮度和最小亮度之間的差值。根據魚眼圖像的特點可知，圖像的全部物景信息都包含在圓形有效區域里，有效區域里像素的亮度值比有效區域外的像素要大得多，掃描線逼近算法就是根據這一特點提出的算法。

既然魚眼圖像的有效區域是圓形的，那么這個圓必然存在一外切正方形，掃描線逼近算法首先求出這個外切正方形進而再求出圓形的中心坐標和半徑。如圖2所示，從魚眼圖像的上下左右四個方位分別建立一條掃描線，從周圍向中心掃描逼近。在圓形有效區域外部，大多是黑色像素點，各像素的亮度值很小，所以掃描線對應的極限亮度差很小，但是當掃描線進入有效區域時，由于物景像素點的增多，掃描線的極限亮度差很大。當掃描線貼近圓形輪廓時極限亮度差劇增，如掃描線left2有一個很大的跳躍值存在，我們可以設一個閾值，當差值大于這個閾值時，我們就認定掃描線到達了魚眼圖像的輪廓邊上了，這條直線對應的位置就是魚眼圖像圓形輪廓的一條切線。

圖2 掃描線逼近算法掃描示意圖

算法的具體步驟為:

首先設定一亮度閾值T，從魚眼圖像的四周開始，建立四條掃描線，像中心逼近掃描。魚眼圖像一般為彩色的RGB圖像，我們首先根據紅R，綠G，藍B信息得到該像素對應的亮度值，圖像像素亮度公式為［7］:

極限亮度差:

其中Imax、Imin分別是掃描中確立的該行或該列的最大和最小亮度值。當Ilim大于設定的閾值T時，則Imax對應的點就是魚眼圖像輪廓上的點，立即停止該方向的掃描。四個方位都掃描完畢時，在理想情況下將得到圓形的外切正方形，那么魚眼圖像的中心坐標和半徑分別為:

理想情況下Rx=Ry，但是當魚眼圖像輪廓附近有比較多的黑色像素時，會導致掃描線定位有偏差，那么得到的外切正方形將畸變成長方形，這時我們可以取兩者的平均值作為半徑。

掃描線逼近算法解決了面積統計法存在的一個問題，即當有效區域內含有像素值比較小的像素點比較多，仍能取得精確的計算結果，但是當大量黑色像素點存在于輪廓邊緣時，特別是存在與四條掃描線的切點附近時掃描線逼近算法計算結果也有偏差。

圖3 新的掃描方案示意圖

2 改進的掃描線逼近算法

2.1 引入掃描步長建立新的掃描方案

從上節可知，掃描線逼近算法是逐行逐列進行掃描的，當魚眼圖像有效區域比較小，而黑色背景比較大時，掃描到魚眼輪廓邊緣需要很長時間，掃描效率低下，針對此，本文建立新的掃描方案，引入掃描步長λ，即前后兩次掃描跳躍的行或列值。如圖3所示，以左方向掃描為例，掃描線lefti和lefti+1是前后兩次掃描，但是第lefti+1次掃描的列值比lefti次掃描大λ。當lefti掃描線未進入魚眼圖像有效區域時，則以步長λ進入下一次掃描，記為lefti+1。當lefti+1進入有效區域時，則下一次掃描以步長為1逐列退回掃描，記為lefti+2，就這樣一直退回掃描到魚眼輪廓邊界為止。

2.2 掃描閾值的選取

掃描線逼近算法用的是固定閾值，閾值的選取對算法的結果有一定的影響，特別是對于掃描線逼近算法來說，閾值選取過小，會把噪點當做邊緣，造成計算半徑過大，閾值選取過大有可能錯過邊緣點，使半徑偏小。本論文針對固定閾值的缺陷，根據不同的魚眼圖像采用自動閾值。

一般來說魚眼圖像四周或多或少都存在亮度很低的黑色區域，本文稱為背景部分。一般數碼相機噪聲點的灰度大部分小于30，因此魚眼圖像背景區域絕大部分亮度值也小于30［9］，本文就以30為參考值對閾值進行如下方法設置:首先設定一較小的整數值M，數值在10以下均可。然后取圖像四周最外層的M行M列的像素值，按式(1)計算亮度，然后計算亮度平均值記為Tm，則閾值T為:

其中N為一正整數，本文取為20。本文這樣設置閾值T的目的是防止魚眼圖像黑色區域的亮度過大，而固定閾值30太小不適用于某些魚眼圖像。而且這樣設定閾值還能在一能程度上抑制噪聲點對掃描算法的干擾。

2.3 局部二值化去除噪聲原理

掃描線逼近算法對噪聲的干擾比較敏感，比如背景部分的椒鹽噪聲點，或者亮度較高像素點。容易想到的一個解決方案就是在輪廓提取之前對魚眼圖像進行濾波去噪處理，如中值濾波，均值濾波，高斯濾波等，其中中值濾波處理對椒鹽噪聲的處理效果最好［10］。但是對魚眼圖像進行濾波處理必定會影響魚眼圖像輪廓的提取速度，而且在魚眼圖像輪廓提取階段對魚眼圖像有效區域內的像素信息進行濾波也是不必要的，因此不宜采用濾波處理。

在掃描線逼近算法中，當掃描線掃描到噪聲點時，亮度差超過了設定的閾值，算法誤認為掃描到了輪廓邊界，針對此我們可以在對取得最大亮度的那個點進行定位然后判斷此點是否噪聲點，如何區分此點是噪聲點還是正常點是本節研究的重點。

魚眼圖像有效區域里的圖像像素亮度值比黑色背景部分要大很多，因此可以通過二值化將有效區域和背景部分分割出來，但是由于有效區域里也會含有像素亮度值比較小的點，因此不可能將二者完全分離出來。但是相鄰像素之間是存在一定關聯性的，可以根據它來區分二值化后黑色像素點是屬于有效區域的還是背景部分，區域增長法就是利用這個原理來提取魚眼圖像的輪廓的。

根據相鄰像素之間的關系可以對黑色像素點這樣進行判別，如圖4所示，點q在圓O外，U(q)是q的任意一個鄰域(矩形鄰域亦可)。在U(q)中，屬于圓O的區域為in，面積記為Si;不屬于圓O的區域為 out，面積記為So。由此可得:Hi的面積小于U(q)面積的1/2，即Si/(Si+So)＜0.5;反之，如果點q在圓O內，就有Si/(Si+So)＞0.5。

圖4 像素點鄰域特性

一般來說，二值化過后的鄰域內黑色像素點比鄰域內白色像素點要多時，可以認為該黑色的像素點是屬于背景部分的，否則認為是有效區域的。本文也將利用取得最大亮度差的點的鄰域特性來判斷該點是不是噪聲點。鄰域可選用圓形鄰域或者矩形鄰域，如圖5所示。噪聲點的特性就是與周圍點像素值差別太大，而針對本文，取得最大亮度差的那個點如果是噪聲點的話，像素值必定比鄰域內其他的點大。因此可以對取得極限亮度差的點某個鄰域內的所有點用上小節的閾值進行局部二值化，然后計算鄰域內白色像素點所占的比例(記為S)的大小，若大于某一閾值(記為Ts)如0.5，可斷定此點不是噪聲點，否則就是噪聲點，應該繼續進行掃描。

圖5 像素點的兩種鄰域

2.4 算法流程圖

本文提出的新的魚眼圖像輪廓提取算法的流程圖如圖6所示。

算法的具體步驟如下:

(1)按式(5)計算亮度閾值T。

(2)以左側掃描為例，以步長λ進行掃描，若極限亮度差小于T則繼續以步長λ掃描。

圖6 魚眼輪廓提取流程圖

(3)否則暫停掃描，定位取得極限亮度差的像素點。

(4)按照3.3節所描述的方式對該像素點進行局部二值化，計算比例S，若S小于設定的閾值Ts說明此點是噪聲點，應繼續以步長λ前進掃描。

(5)若S大于設定的閾值Ts，說明掃描到了輪廓的邊界點，立即停止前進掃描，以步長1也就是逐列退回向左進行掃描，直到掃描到輪廓邊界為止。

值得注意的是，逐列退回掃描時要一直后退直掃描到輪廓邊界外的那一列，才能斷定已經掃描到了輪廓邊界，這一點未在流程圖中體現出來，務必要注意。

3 實驗結果與分析

本節將給出本文提出的改進的掃描線逼近算法與原算法性能的對比，本文算法的測試環境為:Windows XP sp3 Intel(R)Pentinum(R)Dual CPU 1.46 GHz，1 GB內存，MATLAB 7.4。共選用8幅魚眼圖像進行測試，數據如表1和表2所示，其中圓心坐標和半徑是算法計算得到的，誤差是與的標準值相比得到的，而標準值則是手工測量獲得的。圖1的魚眼圖像(對應圖像序號為3)的輪廓提取結果對比如圖7所示。

圖7 魚眼圖像輪廓提取對比圖

從圖7可以看出改進算法提取的輪廓比原算法更精確，圖7(a)出現的偏差是由圖像右邊的白色噪點引起的，右側的掃描線掃到此行時由于噪聲點的存在使極限亮度差大于設定的閾值，認為掃描到了邊界。

表1 掃描線逼近法實驗結果數據

表2 本文提出的改進掃描線逼近法實驗結果數據

相比的掃描線逼近算法，本文提出的改進的掃描線逼近算法取得了很好的效果。由于本文引入局部二值化的去噪思想，使得含噪聲圖像(對應序號為3)的提取效果改善很多。詳細的對比情況如圖8所示，圓圈代表本文提出的改進算法的圓心坐標誤差，十字代表原掃描線逼近算法，顯而易見本文提出的算法提取的圓心坐標誤差更小。參照表1和表2的數據，本文提出的改進算法的半徑平均誤差為0.91，而原掃描線逼近算法的半徑平均誤差為1.09，可見本文提出的算法效果更好。

圖8 改進前后掃描線逼近算法提取圓心坐標誤差

表2中算法運行時間包括掃描步長為5和1的結果，結合表1中原算法運行時間，繪制時間曲線如圖9。當步長為5時算法運行時間最小，而且大部分小于原算法的運行時間。當改進算法不引入步長掃描時，即步長為1時算法的運行時間較長，因此說明本文引入的步長掃描能夠有效地改進算法的運行時間。

圖9 改進前后掃描線逼近算法的運行時間對比曲線

4 結論

本文針對掃描線逼近算法在提取魚眼圖像輪廓時具有抗噪能力差的缺點，提出改進的掃描線算法，提取的改進算法由于引進新的閾值計算方法和局部二值化去噪思想能夠很好地抑制噪聲，有效改善魚眼圖像輪廓的提取效果，而新的掃描方案，即按步長λ掃描的方案能夠縮短算法的運行時間，提高了計算效率。因此本文提取的算法具有更精確的效果，更短的運行時間，具有很強的實時性和實用價值。

［1］Yang R G，Brownt M S，Sealest W B.Geometrically Correct Imagery for Teleconferencing，Orlando，ACM Multimedia’99，1999(1):179-186.

［2］Xiong Y，Turkowski K.Creating Image-Based VR Using a Self-Calibrating Fisheye Lens［C］//IEEE Computer Society Conference on Computer Vision and Pattern Recognition(CVPR’97)，San Juan，Puerto Rico，1997，6:237-243.

［3］吳方，王霞.魚眼鏡頭圖像變形校正算法研究［J］.計算機科學，2009，36(4B):109-111.

［4］Szeliski R.Video Mosaics for Virtual Environment［J］.IEEE Computer Graphics and Applications，1996，16(2):22-30.

［5］楊丹，游磊，張小洪，等.基于區域生長的魚眼圖像輪廓提取算法［J］.計算機工程，2010，36(8):217-218.

［6］王大宇，崔漢國，陳軍.魚眼圖像輪廓提取及校正研究［J］.計算機工與設計，2007，28(6):2878-2879.

［7］崔漢國，陳軍，王大宇.基于魚眼圖像的虛擬漫游研究［J］.系統仿真學報，2007，9(5):1504-1506.

［8］Li S G，Nakano M，Chiba N.Acquisition of Spherical Image by Fish-Eye Conversion Lens［J］.IEEE Computer Society，2004:235-236.

［9］肖詩勤，楊關良.一種改進的魚眼圖像輪廓提取算法［J］.計算機與數字工程，2010，38(1):147-150.

［10］賈永紅.數字圖像處理［M］.武漢:武漢大學出版社，2003:77-78.