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

程德強(qiáng)，劉 洋，柳 雪，趙 國(guó)，張佳琳

（中國(guó)礦業(yè)大學(xué) 信息與電氣工程學(xué)院，江蘇 徐州 221000）

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

程德強(qiáng)，劉 洋，柳 雪，趙 國(guó)，張佳琳

（中國(guó)礦業(yè)大學(xué) 信息與電氣工程學(xué)院，江蘇 徐州 221000）

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

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

1 魚眼圖像研究

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

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

圖1 玉兔號(hào)拍攝的全景圖及校正圖

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

2 魚眼圖像校正原理

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

如圖3所示，球面上的點(diǎn)與投影點(diǎn)保持一一映射的關(guān)系，這種投影關(guān)系可以由m=D（p）來(lái)表示；反之，為了逆向得到校正輸出點(diǎn)，通過(guò)p=D-1（m）即可得到，通過(guò)這種映射關(guān)系，就可以實(shí)現(xiàn)對(duì)畸變圖像的校正。

圖3 魚眼校正模型

3 魚眼圖像的有效區(qū)域提取

3.1 算法原理

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

3.2 算法具體實(shí)現(xiàn)過(guò)程

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

圖4 有效區(qū)域左右邊界線提取流程

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

圖5 分割線掃描算法

步驟2：由式（1）計(jì)算出當(dāng)前點(diǎn)的像素亮度值

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

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

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

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

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

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

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

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

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

圖6 有效區(qū)域上下邊界線提取過(guò)程

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

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

3.3 有效區(qū)域中心與半徑的確定

如果魚眼圖像有效區(qū)域?yàn)闃?biāo)準(zhǔn)圓形，其圓心坐標(biāo)和半徑即可簡(jiǎn)單表示為

4 算法分析與實(shí)驗(yàn)結(jié)果

4.1 算法復(fù)雜度比較分析

假設(shè)圖像的分辨率為W×H，魚眼圖像的有效區(qū)域半徑為R，先分析面積統(tǒng)計(jì)法、經(jīng)典掃描線法和改進(jìn)掃描線法的計(jì)算復(fù)雜度。

根據(jù)面積統(tǒng)計(jì)法的算法原理，進(jìn)行一次完整的分割過(guò)程，需要對(duì)整幅圖像的每個(gè)像素處理，實(shí)際的計(jì)算量為

經(jīng)典逐行逐列掃描線算法由于掃描到邊界時(shí)就不再繼續(xù)掃描，計(jì)算量相比面積統(tǒng)計(jì)法，減少了中心區(qū)域的計(jì)算，其計(jì)算量為

文獻(xiàn)[8]對(duì)經(jīng)典掃描線算法的改進(jìn)，去除了經(jīng)典算法4條掃描線重復(fù)掃描區(qū)域，但是此改進(jìn)算法需要對(duì)像素點(diǎn)操作的次數(shù)為

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

式中：ζ，η和φ為一相對(duì)較小的整數(shù)。

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

表1 不同算法有效區(qū)域提取時(shí)間對(duì)比

4.2 仿真結(jié)果

本文的仿真實(shí)驗(yàn)是在VS2008界面下，基于OpenCV實(shí)現(xiàn)的，針對(duì)本實(shí)驗(yàn)室所拍攝的魚眼圖像進(jìn)行有效提取的實(shí)驗(yàn)室結(jié)果如圖7所示，其中心坐標(biāo)為（928.6，540.7），半徑為540.26像素。

圖7 魚眼圖像輪廓提取結(jié)果

5 結(jié)束語(yǔ)

本文針對(duì)高分辨率和高頻率的高清魚眼視頻監(jiān)控，為了能夠得到更好地實(shí)時(shí)校正監(jiān)控效果，提出一種分割線掃描提取有效區(qū)域算法，相比較面積統(tǒng)計(jì)法和掃描線法，以及改進(jìn)的掃描線法，分割線掃描算法能大幅度減少魚眼圖像有效區(qū)域的提取時(shí)間，最后對(duì)本實(shí)驗(yàn)室所獲取的高清魚眼圖像進(jìn)行有效區(qū)域提取，并給出中心坐標(biāo)和半徑，為后續(xù)實(shí)現(xiàn)魚眼圖像的校正打下重要基礎(chǔ)。

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

[2]英向華，胡占義.一種基于球面投影約束的魚眼鏡頭校正方法[J].計(jì)算機(jī)學(xué)報(bào)，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] 楊丹，游磊，張小洪，等．基于區(qū)域生長(zhǎng)的魚眼圖像輪廓提取算法[J].計(jì)算機(jī)工程，2010，36（8）：217-218．

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

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

[8] 江芳，袁縱橫.魚眼圖像輪廓提取方法的對(duì)比[J].計(jì)算機(jī)系統(tǒng)應(yīng)用，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 文獻(xiàn)標(biāo)志碼：A DOI：10.16280/j.videoe.2015.06.001

【本文獻(xiàn)信息】程德強(qiáng)，劉洋，柳雪，等.分割線掃描魚眼圖像有效區(qū)域提取算法[J].電視技術(shù)，2015，39（6）.

國(guó)家自然科學(xué)基金委員會(huì)與神華集團(tuán)有限責(zé)任公司聯(lián)合資助項(xiàng)目（U1261105）

時(shí) 雯

2014-06-05