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

賀　輝　張澤生　肖紅玉　黃　靜

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

1　引言

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

2　算法描述

2.1　圖像二值化

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

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

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

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

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

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

算法測(cè)試結(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)裁剪、檢測(cè)識(shí)別等精度和可靠性。本文基于二值圖像連通域特征的目標(biāo)區(qū)域定位算法主要包括2個(gè)步驟提取候選區(qū)域和定位四邊形區(qū)域定點(diǎn)，算法流程如圖2所示。

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

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

1）提取所有連通域

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

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

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

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

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

1）橢圓擬合

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

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

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

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

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

2）頂點(diǎn)定位［16］

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

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

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

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

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

3　基于Android平臺(tái)的目標(biāo)圖像自動(dòng)裁剪實(shí)驗(yàn)及結(jié)果分析

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

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

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

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

3.1　裁剪效果圖分析

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

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

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

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

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

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

4　結(jié)語(yǔ)

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

［1］王華旭.Android平臺(tái)圖像處理軟件框架的開發(fā)與設(shè)計(jì)［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］周翔，陳會(huì)，張鍇，等.復(fù)雜背景下的圖像文本區(qū)域定位方法研究［J］.計(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ū)域的自動(dòng)定位研究［J］.計(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ái)圖像分割算法研究及系統(tǒng)實(shí)現(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ù)自動(dòng)裁剪方案設(shè)計(jì)與控件開發(fā)［J］.計(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ì) 算 機(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)強(qiáng)，薛河儒，姜新華.基于Android平臺(tái)的圖像預(yù)處理系統(tǒng)的研究［J］.內(nèi)蒙古農(nóng)業(yè)大學(xué)學(xué)報(bào)（自然科學(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é)報(bào)，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］王強(qiáng)，馬利莊.圖像二值化時(shí)圖像特征的保留［J］.計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，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簡(jiǎn)單圖形識(shí)別［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é)報(bào)，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é)報(bào)（自然科學(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］胡立華，張繼福.基于圖像的四邊形自動(dòng)檢測(cè)方法［J］.小型微型計(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］陳德運(yùn)，尹芳，吳銳.基于消失點(diǎn)的場(chǎng)景文本透視變形校正方法［J］.南京理工大學(xué)學(xué)報(bào)，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.