一種面向移動終端目標(biāo)圖像自動裁剪的快速區(qū)域定位算法

賀　輝　張澤生　肖紅玉　黃　靜

（北京師范大學(xué)珠海分校信息技術(shù)學(xué)院　珠?！?19087）

1　引言

圖像處理軟件作為智能手機(jī)的常用軟件，對復(fù)雜圖像進(jìn)行增強、分割等處理及檢測識別，并從中獲取重要信息，是人工智能的重要領(lǐng)域［1］。而在許多實際應(yīng)用中，對用戶感興趣區(qū)域圖像內(nèi)容進(jìn)行自動定位與校正是問題的關(guān)鍵，也是對圖像進(jìn)行檢測識別和理解的基礎(chǔ)，其準(zhǔn)確程度直接影響后續(xù)檢測識別的精度［2］。對圖像某個區(qū)域的定位有很多方法，其中常見的有模板匹配定位法、幾何特征（如邊緣特征）定位法、小波變換定位方法等。這些方法都廣泛應(yīng)用于人臉檢測、期刊圖像文件處理系統(tǒng)、車牌識別等領(lǐng)域［3］。目前絕大多數(shù)方法無法對存在透視畸變的圖像進(jìn)行糾偏［4］，少數(shù)采用邊緣檢測與直線擬合的方式實現(xiàn)了透視畸變的校正，但是對于背景較為復(fù)雜的圖片，這些算法極易受到背景中存在的其它長邊界的干擾，造成定位錯誤［5］。唐毅等提出基于連通域幾何特征的圖像感興趣區(qū)域自動定位方法，取得了優(yōu)于基于模板匹配的定位方法實驗結(jié)果［3］。蔡峰等的研究也表明基于連通域分析的方法可以取得較好的定位結(jié)果［6～7］。本文圖片筆記應(yīng)用中目標(biāo)圖像往往背景復(fù)雜，基于邊緣檢測算法的定位方法極易受到偽邊界的干擾。但由于目標(biāo)圖像內(nèi)容底色比較均勻，在恰當(dāng)?shù)亩捣指罨A(chǔ)上，可以發(fā)揮基于連通域特征分析定位方法［8］的優(yōu)勢，取得較好效果，測試結(jié)果證明了這一點。

2　算法描述

2.1　圖像二值化

針對本文研究圖像感興趣內(nèi)容區(qū)域與背景色差明顯的特點，使用Otsu算法或者全局閾值迭代法可以對目標(biāo)區(qū)域進(jìn)行大致的分割。但是全局閾值算法的局限性導(dǎo)致獲得的分割結(jié)果極易受到光照的影響而造成區(qū)域的虛多或殘缺。無論哪一種情況，對于后續(xù)的頂點定位處理均存在十分不利的影響。因此閾值分割不僅應(yīng)當(dāng)考慮區(qū)域的整體灰度特性，還應(yīng)當(dāng)保留區(qū)塊的線特性，通過檢測區(qū)域邊緣，實現(xiàn)針對目標(biāo)區(qū)域的閾值分割［9～11］。參考文獻(xiàn)［12］的思路，本文兼顧區(qū)域特征和邊緣特征的閾值分割算法步驟如下。

1）輸入RGB圖像灰度化，結(jié)果記為G；

2）使用Sobel算子分別計算圖像水平、垂直梯度，二者的絕對值相加得到邊緣圖像L；

3）使用OTSU方法分別處理G和L得到二值圖像T1和T2；

4）遍歷二值化的邊緣T2，對其中非零點的3×3鄰域求均值A(chǔ)vg，并設(shè)定鄰域內(nèi)像素點的閾值為Avg；

5）根據(jù)原圖灰度信息及修改過的像素閾值，修改T1各個像素點的值，最終得到保留了邊緣特性的目標(biāo)二值圖像T1。

算法測試結(jié)果如圖1所示。

圖1　圖像二值化結(jié)果

從圖1結(jié)果可見，本文算法閾值分割結(jié)果在成功保留了圖像的區(qū)域特征基礎(chǔ)上考慮到了區(qū)域邊緣的結(jié)構(gòu)，目標(biāo)分割效果優(yōu)于一般的全局閾值算法和局部閾值算法。

2.2　基于連通域特征的快速區(qū)域定位

區(qū)域定位的準(zhǔn)確與否直接影響到后續(xù)的目標(biāo)裁剪、檢測識別等精度和可靠性。本文基于二值圖像連通域特征的目標(biāo)區(qū)域定位算法主要包括2個步驟提取候選區(qū)域和定位四邊形區(qū)域定點，算法流程如圖2所示。

圖2　本文區(qū)域定位算法流程圖

2.2.1連通域分析提取候選區(qū)域

1）提取所有連通域

通過在二值圖像上搜索連通域，并根據(jù)連通域的面積大小進(jìn)行排序篩選，提取在圖像中的所有可能包含目標(biāo)的連通域。經(jīng)過對大量真實場景圖像測試后發(fā)現(xiàn)：若設(shè)定限制條件，使得目標(biāo)連通域面積占圖像總面積的5%~10%以上時，能夠在保證識別結(jié)果正確的情況下限制算法對無效結(jié)果的識別。

2）去除無關(guān)連通域

常用的凸包查找算法有Jarvis步進(jìn)法、Graham's掃描法、Melkman法等多種方式［13］。去除無關(guān)連通域，需要進(jìn)一步分析目標(biāo)連通域與其它連通域的結(jié)構(gòu)差異。在測試、對比分析的過程中可以發(fā)現(xiàn)：在拍攝圖片作為筆記的過程中，目標(biāo)區(qū)域一般處于屏幕核心位置，且不存在遮擋的情況下均為凸四邊形。因目標(biāo)區(qū)域的存在，導(dǎo)致背景部分連通域經(jīng)常會帶有明顯的內(nèi)凹或缺陷。于是在進(jìn)行連通域篩選時，將連通域自身面積與其凸包面積相比較，排除面積比小于某常數(shù)的連通域，實現(xiàn)對目標(biāo)區(qū)域的篩選。在實驗過程中，設(shè)定參數(shù)ε為［0.85，0.9］之間時，能夠?qū)崿F(xiàn)絕大多數(shù)情況下的正確篩選。測試結(jié)果如圖3所示，對于這一定位區(qū)域明顯小于正常定位區(qū)域的圖片，僅需要三次連通域分析，就能夠?qū)崿F(xiàn)對目標(biāo)區(qū)域的正確定位。

圖3　測試圖片（左）與定位結(jié)果（右）

2.2.2定位四邊形區(qū)域頂點

1）橢圓擬合

任意凸四邊形均存在外接橢圓［12］。在平面直角坐標(biāo)系中，一般通過如式（1）形式的圓錐曲線方程表示橢圓，平面直角坐標(biāo)系中的橢圓如圖4所示。

圖4　平面直角坐標(biāo)系中的橢圓

使用橢圓進(jìn)行擬合，一般采用最小二乘法進(jìn)行運算，得到的結(jié)果保證測量誤差的平方和最小。最小二乘法實現(xiàn)步驟是：尋找出參數(shù)集合，使數(shù)據(jù)點與橢圓之間的總距離達(dá)到最小，一般使用代數(shù)距離或者歐式距離作為度量標(biāo)準(zhǔn)。當(dāng)使用代數(shù)距離進(jìn)行最小二乘運算時，將式（1）中的條件設(shè)置為A+C=1；計算得出每一個方程對應(yīng)系數(shù)，形成評估函數(shù) F(a，b，c，d，e，f)（式（2））［14～15］：

而后，對函數(shù)F求極值，在式（3）成立時，F(xiàn)取得最小值。

最后，使用高斯消元法對這一線性方程組進(jìn)行求解，求得橢圓方程的所有參數(shù)。

2）頂點定位［16］

使用橢圓對四邊形目標(biāo)的凸包區(qū)域進(jìn)行擬合，能夠得到一個近似為凸包輪廓外接橢圓的方程。此時，目標(biāo)四邊形的頂點落在橢圓的邊緣附近。為了方便計算，建立一個新的平面坐標(biāo)系，將橢圓中心作為原點，橢圓方程便成為式（4）的形式。

其中，a.b分別為橢圓的長、短半軸長，α表示點（x，y）與橢圓長半軸的逆時針旋轉(zhuǎn)角。將凸包點集內(nèi)的點進(jìn)行坐標(biāo)變換后，代入橢圓方程當(dāng)中，令

由于點 f(x，y)數(shù)量較少，比較所有點的f(x，y)值，抽取其中最大值所對應(yīng)點作為頂點之一；刪除該 f(x，y)的值，再次從大到小遍歷f(x，y)，以最大值法篩選出其他三個頂點；同時設(shè)置約束條件，使得四個點與凸包輪廓質(zhì)心連線的夾角兩兩之間小于α，以防頂點被重復(fù)定位。在實驗過程中，設(shè)置α=5°~10°可以較好實現(xiàn)對于區(qū)域頂點的定位。

測試結(jié)果如圖5所示。由圖5可見，對于透視畸變明顯的圖像，也能夠?qū)崿F(xiàn)準(zhǔn)確定位。

圖5　測試原圖（左）以及定位結(jié)果圖（右）

3　基于Android平臺的目標(biāo)圖像自動裁剪實驗及結(jié)果分析

在本文自主研發(fā)的Android平臺圖片筆記APP中，在區(qū)域定位基礎(chǔ)上對會議拍攝內(nèi)容，包括幻燈片、黑白板等進(jìn)行自動裁剪實驗，對存在幾何透視畸變的圖片，定位后進(jìn)行了基于消隱點的透視畸變矯正［17～19］。為確?？杀刃?，預(yù)處理過程和方法一致，對比結(jié)果如圖6～8所示。

圖6　裁剪結(jié)果圖：原圖（a）基于邊緣檢測算法的定位方法（b）本文算法（c）

圖7　裁剪結(jié)果圖：原圖（a）基于邊緣檢測算法的定位方法（b）本文算法（c）

圖8　裁剪結(jié)果圖：原圖（a）基于邊緣檢測算法的定位方法（b）本文算法（c）

3.1　裁剪效果圖分析

本實驗圖像均通過日常拍攝得到，涵蓋了大量不同的復(fù)雜場景。對比上述結(jié)果不難發(fā)現(xiàn)，本文算法相比于基于邊緣檢測算法的定位算法在處理帶有復(fù)雜背景、偽邊界的目標(biāo)圖像時具有更高的正確率。

3.2　算法執(zhí)行速度分析

分辨率調(diào)整能夠大大提高預(yù)處理以及后續(xù)區(qū)域定位的運算速度，經(jīng)過反復(fù)測試，最終確定將圖像分辨率調(diào)整為500×500，以提高預(yù)處理及后續(xù)操作的速度，減少運算量。針對2種分辨率不同的圖像，算法執(zhí)行時間比對如表1所示。本算法測試通過HTC 802t完成，表1為該手機(jī)的軟件、硬件參數(shù)。

表1　HTC 802t手機(jī)參數(shù)

表2　算法執(zhí)行時間

從表2內(nèi)容可見，本文算法圖片定位時間穩(wěn)定在100ms～200ms之間，校正時間主要受到目標(biāo)區(qū)域大小的影響而發(fā)生變化。與基于邊緣檢測的定位校正算法相比，本文算法總體耗時減少超過80%，表明其執(zhí)行速度快，易于優(yōu)化，更適合在移動設(shè)備當(dāng)中應(yīng)用。

4　結(jié)語

對于圖片筆記管理軟件而言，使用自動定位、校正算法，對圖片中筆記區(qū)域進(jìn)行定位，并對定位結(jié)果進(jìn)行透視畸變校正，能夠大大降低操作的復(fù)雜程度，去除無用的背景信息，改善軟件使用中的用戶體驗。其中，區(qū)域定位算法的準(zhǔn)確率在很大程度上決定了用戶交互掃描圖片操作的復(fù)雜程度。本文著重分析了筆記圖像普遍具備的區(qū)域特征，設(shè)計并實現(xiàn)了對圖像目標(biāo)的自動定位算法，基本解決了現(xiàn)在被廣泛投入應(yīng)用的邊緣擬合算法所存在的諸多弊端，如算法復(fù)雜度高、容易受到偽邊界干擾、優(yōu)化困難等。本文算法具有較強的應(yīng)用價值。對于區(qū)域篩選方面，本文使用了輪廓面積與凸包面積比實現(xiàn)目標(biāo)區(qū)域的選擇。在后續(xù)工作中，可以考慮通過輪廓多邊形的面積、周長、凸包等數(shù)學(xué)表現(xiàn)，及其內(nèi)接、外接多邊形的性質(zhì)，對輪廓大致形狀進(jìn)行估計，自動判斷、區(qū)分出四邊形與其他多邊形，進(jìn)一步提高算法的魯棒性。

［1］王華旭.Android平臺圖像處理軟件框架的開發(fā)與設(shè)計［J］.軟件，2014（2）：46-47.WANG Huaxu.Development and Design of the Android Platform Image Processing Software Framework［J］.Soft-ware，2014（2）：46-47.

［2］周翔，陳會，張鍇，等.復(fù)雜背景下的圖像文本區(qū)域定位方法研究［J］.計算機(jī)工程與應(yīng)用，2013，49（12）：101-105.ZHOU Xiang，CHEN Hui，ZHANG Kai，et al.Method for text region localization in complex background images［J］.Computer Engineering and Applications，2013，49（12）：101-105.

［3］唐毅，鄭麗敏，任發(fā)政，等.基于幾何特征的圖像感興趣區(qū)域的自動定位研究［J］.計算機(jī)工程，2007，33（1）：200-203.TANG Yi，ZHENG Limin，REN Fazheng，et al.Study on Automatic Location for Interested Region of Image Based on Geometrical Features［J］.Computer Engineering，2007，33（1）：200-203.

［4］靳鑫.基于Android平臺圖像分割算法研究及系統(tǒng)實現(xiàn)［D］.濟(jì)南：山東大學(xué)，2015.JINXin.Research and Implement on Android Platform-based on image segmentation algorithm［D］.Jinan：Thesis forMaster Degree，Shan Dong University，2015.

［5］賀輝，劉琨，肖紅玉.銀行票據(jù)自動裁剪方案設(shè)計與控件開發(fā)［J］.計算機(jī)與數(shù)字工程，2016（7）：1327-1332.HE Hui，LIU Kun，XIAO Hongyu.Bills auto-cropping based on adaptive image binary representation［J］.Computer&digitalengineering，2016（7）：1327-1332.

［6］蔡鋒，劉立柱.基于連通域分析和支持向量機(jī)的傳真圖像 關(guān) 鍵 詞 定 位［J］.計 算 機(jī) 應(yīng) 用 ，2010，30（5）：1259-1261.CAIFeng，LIU Lizhu.Key words location of the fax images based on connected component analysis and SVM［J］.Journal of computer applications，2010，30 （5） ：1259-1261.

［7］胡小鋒，周勇，葉慶泰.復(fù)雜背景彩色圖像中的文字分割［J］.光學(xué)技術(shù)，2006，32（1）：141-143，147.HU Xiaofeng，ZHOU Yong，YE Qingfeng.Text segmentation in complex color images［J］.optical technique，2006，32（1）：141-143，147.

［8］陳寅鵬，丁曉青.復(fù)雜車輛圖像中的車牌定位與字符分割方法［J］.紅外與激光工程，2004，33（1）：29-33.CHEN Yanpeng，DING Xiaoqing.License-plate location and character segmentation in complex vehicle images［J］.Infrared and Laser Engineering，2004，33（1）：29-33.

［9］關(guān)強，薛河儒，姜新華.基于Android平臺的圖像預(yù)處理系統(tǒng)的研究［J］.內(nèi)蒙古農(nóng)業(yè)大學(xué)學(xué)報（自然科學(xué)版）.2015，36（5）：133-138.GUANQiang，XUEHeru，JIANG Xinhua.Research on image preprocessing system based on android platform［J］.Journal of Inner Mongolia Agricultural University（Natural science Edition），2015，36（5）：133-138.

［10］張慶英，岳衛(wèi)宏，肖維紅，等.基于邊界特征的圖像二值化方法應(yīng)用研究［J］.武漢理工大學(xué)學(xué)報，2005，27（2）：55-57，64.ZHANG Qingying，YUEWeihong，XIAOWeihong，et al.Study on Image Binarizing Process Based on Edge Features［J］.Journal of WUHAN University of technology，2005，27（2）：55-57，64.

［11］王強，馬利莊.圖像二值化時圖像特征的保留［J］.計算機(jī)輔助設(shè)計與圖形學(xué)學(xué)報，2000，12（10）：746-750.WANG Qiang，MA Lizhuang.Binary-Conversion of Imagewith Feature Preserving［J］.Journalof computer aided design and computer graphics，2000，12（10）：746-750.

［12］周倩，王軍，王亮亮.基于OpenCV輪廓逼近的Android簡單圖形識別［J］.福建電腦，2016，32（2）：122-123.ZHOU Qian，WANG Jun，WANG Liangliang.Android simple pattern recognition based on OpenCV contour approximation［J］.Fujian computer，2016，32（2）：122-123.

［13］閆蓓，王斌，李媛.基于最小二乘法的橢圓擬合改進(jìn)算法［J］.北京航空航天大學(xué)學(xué)報，2008，34（3）：295-298.YAN Bei，WANG Bin，LIYuan.Optimal ellipse fitting method based on least square principle［J］.Journal of Beijing University ofaeronautics and astronautics，2008，34（3）：295-298.

［14］馬向南，李航，劉麗麗，等.最小二乘改進(jìn)算法及其在橢圓擬合中的應(yīng)用［J］.河南科技大學(xué)學(xué)報（自然科學(xué)版），2014，35（3）：18-21.MA Xiangnan，LIHang，LIU Lili，et al.Improved least square algorithm and application in ellipse fitting［J］.Journal of Henan University of Science and Technology：Natural Science，2014，35（3）：18-21.

［15］胡立華，張繼福.基于圖像的四邊形自動檢測方法［J］.小型微型計算機(jī)系統(tǒng)，2014，35（8）：1911-1915.HU Lihua，ZHANG Jifu.Image Based Automatic Detection Quadrilateral Algorithm［J］.JournalofChinese Computer Systems，2014，35（8）：1911-1915.

［16］Richard Hartley，Andrew Zisserman.Multiple View Geometry in Computer Vision［M］.2nd.Cambridge：Cambridge University Press，2003.

［17］苗立剛.基于形態(tài)學(xué)的文檔圖像透視校正算法［J］.光電子·激光，2009，20（9）：1262-1266.MIAO Ligang.Perspective rectification of document images based on morphology［J］.Journal of Optoelectronics·Laser，2009，20（9）：1262-1266.

［18］陳德運，尹芳，吳銳.基于消失點的場景文本透視變形校正方法［J］.南京理工大學(xué)學(xué)報，2011，35（4）：436-441.CHEN Deyun，YIN Fang，WU Rui.Perspective Distortion Correction Method of Scene Text Based on Vanishing Point［J］.Journal of Nanjing University of Science and Technology，2011，35（4）：436-441.