分割線掃描魚眼圖像有效區域提取算法

程德強，劉 洋，柳 雪，趙 國，張佳琳

（中國礦業大學 信息與電氣工程學院，江蘇 徐州 221000）

分割線掃描魚眼圖像有效區域提取算法

程德強，劉 洋，柳 雪，趙 國，張佳琳

（中國礦業大學 信息與電氣工程學院，江蘇 徐州 221000）

對于超大廣角魚眼圖像的校正，關鍵是必須準確地提取出魚眼圖像的有效區域，并且同時確定有效區域的中心和半徑。現有的魚眼鏡頭校正算法針對高清魚眼視頻監控有一定的不足，因此為滿足高清魚眼視頻監控的高分辨率需求，在現有算法的基礎上提出一種分割線掃描算法。該算法首先劃定一條特定水平分割線，由此尋找最接近邊界線的范圍區域，減少不必要像素點的檢測，然后在此區域內精確尋找有效區域邊界線。經實驗表明，該算法在不降低提取精度的同時，可以顯著降低魚眼圖像有效區域提取的時間復雜度和計算量，將以往算法的200萬計算量降低到萬量級以下。

魚眼鏡頭；輪廓提取；分割線掃描

1 魚眼圖像研究

隨著信號處理和圖像處理技術的發展，基于魚眼全景監控攝像頭的視覺處理技術得到快速發展，中國已于2013年底發射“嫦娥三號”，搭載的“玉兔號”月球車所配備的就是全景攝像頭，拍攝的全景圖和展開圖如圖1所示。另外，魚眼鏡頭還廣泛應用于全景安全監控、地鐵走廊監控等長距離和大場地空間，相較一般的攝像頭，其視場角接近于180°甚至超過180°，所以相比普通鏡頭，魚眼鏡頭能夠拍攝到更大場景畫面，獲取到更多的空間信息。為了捕獲更多的信息，目前高清魚眼鏡頭也得到了廣泛應用，它所獲得的圖像對校正有著更高的要求，圖2是1 080p高清魚眼鏡頭所拍攝的魚眼圖像，分辨率達到1 920×1 280，單幀圖像像素點數目高達250萬。當鏡頭的視場角由幾十度提高到180°時，圖像將產生嚴重畸變[1]，所以對校正的時間復雜度和計算量有很大的挑戰。

針對魚眼大廣角畸變圖像的校正研究，目前也已經相當成熟，魚眼圖像校正的關鍵在于準確提取出魚眼圖像的有效區域，同時確定出有效區域的中心和半徑。本文主要研究針對高清魚眼鏡頭的實時視頻監控，提出的算法可以在不降低提取精度的同時，顯著降低魚眼圖像有效區域提取的時間復雜度和計算量，將以往算法[2-6]的200萬計算量降低到萬量級以下。

圖1 玉兔號拍攝的全景圖及校正圖

圖2 高清魚眼鏡頭拍攝的魚眼圖像

2 魚眼圖像校正原理

針對魚眼圖像校正模型的研究，主要有基于經度坐標的校正模型、等距投影校正模型、球面透視投影模型和基于內容的校正模型，但是對于超過180°的超大廣角魚眼鏡頭，一般目前應用最多的是球面透視投影模型，文獻[2]提出一種透視投影模型，空間點到魚眼圖像點的坐標變換不是簡單的線性轉換，且給出如下流程[2]：第一步，建立空間點P與球面中心圓點的關系，即向量OP；第二步，通過向量OP得到空間點P與球面模型映射點的關系；第三步，通過模型計算得到球面點與投影點的關系。

如圖3所示，球面上的點與投影點保持一一映射的關系，這種投影關系可以由m=D（p）來表示；反之，為了逆向得到校正輸出點，通過p=D-1（m）即可得到，通過這種映射關系，就可以實現對畸變圖像的校正。

圖3 魚眼校正模型

3 魚眼圖像的有效區域提取

3.1 算法原理

根據魚眼圖像的特征，相比較黑色像素部分，有效區域基本占據了整幅魚眼圖像的大部分區域，目前對于魚眼畸變圖像的有效提取主要有4種算法：最小二乘擬合算法[3]、面積統計算法[4]、區域生長算法[5]和逐行逐列掃描線[6]算法。其中最小二乘擬合算法和面積統計算法由于是對整幅魚眼畸變圖像的所有像素點進行掃描判斷，因此其時間復雜度和空間復雜度都要比逐行逐列掃描線算法要高，故在實際應用中，應用最廣的也是算法最成熟的是逐行逐列掃描線算法。當對高清圖像進行處理時，單幀像素點數目高達250萬，即使是應用最多的逐行逐列掃描線算法，有效計算量一般也在百萬次以上，計算量相當大。為了減少計算量和復雜度，本文提出的算法思路是首先劃定一特定水平分割線，由此尋找最接近邊界線的范圍區域，減少不必要像素點的檢測，然后再在此區域內精確尋找有效區域邊界線。

3.2 算法具體實現過程

魚眼圖像有效區域的左右邊界線的確定流程如圖4所示。

圖4 有效區域左右邊界線提取流程

步驟1：首先在魚眼圖像的水平中間線上進行邊界點的掃描，如圖5所示。P1P2所在直線為水平分割線，其位置是魚眼圖像高度的1/2，先如向右箭頭方向掃描。

圖5 分割線掃描算法

步驟2：由式（1）計算出當前點的像素亮度值

將該點像素亮度值I與下一點的像素亮度值Incxt進行比較，由式（2）判斷其差值是否滿足條件

式中：T為預設閾值，如果當前點滿足上述條件，則將該點設為臨時邊界點，在圖5中標為P1點；如果不滿足上述條件，則繼續下一點的比較。同理，如向左箭頭方向掃描，計算該點像素亮度值是否滿足式（2），如果滿足條件，則將該點設為臨時右邊界點，圖中標為P2點；如果不滿足上述條件，則繼續下一點的比較。其中P1和P2點并不一定恰好是魚眼圖像有效區域的邊緣，這是由于魚眼圖像中可能存在的黑色像素導致的，如果魚眼圖像中邊緣有黑色物體，單純地由水平分割線上的點的關系無法實現準確的有效區域邊緣識別，所以進行如下計算。

步驟3：以P1點為起點，作P1P2線的垂線段，此垂線段的高度為魚眼圖像高度的1/2，如圖2所示的魚眼圖像，魚眼圖像的有效區域基本位于整幅魚眼圖像的中間位置，因此為減少不必要的計算量，垂線段的高度為魚眼圖像的1/2即可達到提取目標，這也通過實驗證實了其可行性，然后向魚眼圖像邊緣方向移動，由式（1）計算此垂線段上的每個點的像素亮度值，并由式（3）求得最大亮度值與最小亮度值之差，即極限亮度值之差

式中：Δ為極限亮度值之差。再由式（4）判斷極限亮度值之差是否滿足條件

式中：Δnext為下一個掃描線段的極限亮度值之差。

如果滿足上述條件，則將下一點所在的縱向直線設為魚眼圖像有效區域的左邊界線；如果不滿足上述條件，則繼續下一點所在垂線上的極限亮度值之差的比較。

步驟4：與步驟3原理相同，以P2點為起點，作P1P2線的垂線段，此垂線段的高度為魚眼圖像高度的1/2，并向魚眼圖像邊緣方向移動，計算此垂線上所有點的極限亮度值之差是否滿足式（4），如果滿足此條件，則將下一點所在的縱向直線設為魚眼圖像有效區域的右邊界線；如果不滿足，則繼續下一點所在垂線上的極限亮度值之差的比較。

魚眼圖像有效區域的上下邊界線的提取流程如圖6所示。

步驟5：確定出魚眼圖像有效區域的左右邊界線之后，以P1P2的中點作P1P2的垂線Q1Q2，從此垂線交于魚眼圖像的上邊緣點開始向內移動，如圖5所示，由式（1）計算當前點的像素亮度值，并判斷是否與下一點的亮度值之差滿足式（2），如果滿足此條件，則將下一點設為臨時上邊界點，在圖中標為Q1點；如果不滿足上述條件，則繼續下一點像素亮度值的比較。同理，從此垂線交于魚眼圖像的下邊緣點開始向內移動，由式（1）計算當前點的像素亮度值與前一點的亮度值之差是否滿足式（2），如果滿足此條件，則將下一點設為臨時下邊界點，在圖中標為Q2點；如果不滿足上述條件，則繼續下一點像素亮度值的比較。其中Q1和Q2點并不一定恰好是魚眼圖像有效區域的邊緣，這與P1和P2點也不恰好是邊緣點的原因一樣，這都是由魚眼圖像中可能存在的黑色像素導致的。

圖6 有效區域上下邊界線提取過程

步驟6：同樣為了減小魚眼圖像有效區域中的黑色像素帶來的檢測誤差，對上下邊界線的確定進行如下處理，以臨時上邊界點Q1為起點，作Q1Q2的垂線段，此垂線段的長度為魚眼圖像寬度的1/2，并向魚眼圖像的邊緣移動，由式（3）求得此垂線段上的最大亮度值與最小亮度值之差，即極限亮度值之差，然后判斷極限亮度值之差是否滿足式（4），如果滿足此條件，則將下一點所在的水平直線設為魚眼圖像有效區域的上邊界線；如果不滿足此條件，則繼續下一點所在垂線上的極限亮度值之差的比較。

步驟7：同步驟6原理相同，以臨時下邊界點Q2為起點，作Q1Q2的垂線段，此垂線段的長度為魚眼圖像寬度的1/2，并向魚眼圖像的邊緣移動，判斷極限亮度值之差是否滿足式（4），如果滿足此條件，則將下一點所在的水平直線設為魚眼圖像有效區域的下邊界線；如果不滿足上述條件，則繼續下一點所在垂線上的極限亮度值之差的比較。

3.3 有效區域中心與半徑的確定

如果魚眼圖像有效區域為標準圓形，其圓心坐標和半徑即可簡單表示為

4 算法分析與實驗結果

4.1 算法復雜度比較分析

假設圖像的分辨率為W×H，魚眼圖像的有效區域半徑為R，先分析面積統計法、經典掃描線法和改進掃描線法的計算復雜度。

根據面積統計法的算法原理，進行一次完整的分割過程，需要對整幅圖像的每個像素處理，實際的計算量為

經典逐行逐列掃描線算法由于掃描到邊界時就不再繼續掃描，計算量相比面積統計法，減少了中心區域的計算，其計算量為

文獻[8]對經典掃描線算法的改進，去除了經典算法4條掃描線重復掃描區域，但是此改進算法需要對像素點操作的次數為

而改進的分割線掃描線算法，以當前掃描線為邊界代替魚眼圖像的邊界，計算量相比經典逐行逐列掃描線算法更少，根據分割線掃描算法的原理，臨時分界點的確定過程中，只是對單個像素進行計算，其計算量僅為相對較小的整數φ，水平掃描線寬度為W/2，豎直掃描線高度為H/2，并且兩條掃描線在由臨時分界點確定最終分界線過程中，只經過一段相對較短的距離，所以此過程的計算量為W/2×ζ+H/2×η，因此總的計算量為

式中：ζ，η和φ為一相對較小的整數。

從式（7）～（10）可明顯得出，在高分辨率和高頻率視頻監控前提下，以上各算法計算量N1＞N2＞N3?N4，在對1 080p圖像進行處理時可以將原算法的200萬計算量降低到萬量級以下，通過仿真實驗計算得到有效區域提取的算法時間對比如表1所示。

表1 不同算法有效區域提取時間對比

4.2 仿真結果

本文的仿真實驗是在VS2008界面下，基于OpenCV實現的，針對本實驗室所拍攝的魚眼圖像進行有效提取的實驗室結果如圖7所示，其中心坐標為（928.6，540.7），半徑為540.26像素。

圖7 魚眼圖像輪廓提取結果

5 結束語

本文針對高分辨率和高頻率的高清魚眼視頻監控，為了能夠得到更好地實時校正監控效果，提出一種分割線掃描提取有效區域算法，相比較面積統計法和掃描線法，以及改進的掃描線法，分割線掃描算法能大幅度減少魚眼圖像有效區域的提取時間，最后對本實驗室所獲取的高清魚眼圖像進行有效區域提取，并給出中心坐標和半徑，為后續實現魚眼圖像的校正打下重要基礎。

[1]于景良，王德福，倪志剛，等.全景電視攝像技術的研究[J].電視技術，1993，17（11）：2-5.

[2]英向華，胡占義.一種基于球面投影約束的魚眼鏡頭校正方法[J].計算機學報，2003，26（12）：1702-1708.

[3]NOMURA Y，SAGARA M，HIROSHI N.Simple calibration algo?rithm for high-distortion-lens camera[J].IEEE Trans.Pattern Analysis and Machine Intelligence，1992，14（11）：1095-1099.

[4] SZELISKI R.Video mosaics for virtual environment[J].IEEE Com? puter Graphics and Applications，1996，16（2）：22-30.

[5] 楊丹，游磊，張小洪，等．基于區域生長的魚眼圖像輪廓提取算法[J].計算機工程，2010，36（8）：217-218．

[6] 王大宇，崔漢國，陳軍.魚眼圖像輪廓提取及校正研究[J].計算機工程與設計，2007，28（6）：2878-2879．

[7]常丹華，趙丹，楊峰明，等.提取魚眼圖像輪廓的算法改進及圖像校正[J].激光與紅外，2012，42（4）：448-451.

[8] 江芳，袁縱橫.魚眼圖像輪廓提取方法的對比[J].計算機系統應用，2011，20（4）：214-218.

Algorithm for Dividing Line Scan Fisheye Image Region Extraction

CHENG Deqiang，LIU Yang，LIU Xue，ZHAO Guo，ZHANG Jialin
（School of Information and Electrical Engineering，China University of Mining&Technology，Jiangsu Xuzhou 221000，China）

For correcting the ultra wide angle of fish-eye image，the key is accurately extracting the effective coverage of fish-eye image，and determining the center and radius of effective coverage.In view of video surveillance of high definition fish-eye，the existing correction algorithms of fish-eye lens have some insufficient.In order to satisfy the high definitionof fish-eye video surveillance，the cut line scanning algorithm basing on existing algorithms is proposed in the paper.Aiming at reducing unnecessary detections of pixel points，a specific level cut line must be determined to find the range and region which most closing boundary line.Then the boundary line of effective coverage can be precisely found in the region.The experimental results show that the algorithm can significantly reduce the time complexity and computational complexity when the algorithm extracts efficient coverage of fish-eye image，meanwhile maintain the original extraction precision，and reduce the computational complexity from 2 000 000 to 10 000 or below.

fisheye lens；contour extraction；line scan

TN919.81 文獻標志碼：A DOI：10.16280/j.videoe.2015.06.001

【本文獻信息】程德強，劉洋，柳雪，等.分割線掃描魚眼圖像有效區域提取算法[J].電視技術，2015，39（6）.

國家自然科學基金委員會與神華集團有限責任公司聯合資助項目（U1261105）

時 雯

2014-06-05