一种面向移动终端目标图像自动裁剪的快速区域定位算法

贺　辉　张泽生　肖红玉　黄　静

（北京师范大学珠海分校信息技术学院　珠海　519087）

1　引言

图像处理软件作为智能手机的常用软件，对复杂图像进行增强、分割等处理及检测识别，并从中获取重要信息，是人工智能的重要领域［1］。而在许多实际应用中，对用户感兴趣区域图像内容进行自动定位与校正是问题的关键，也是对图像进行检测识别和理解的基础，其准确程度直接影响后续检测识别的精度［2］。对图像某个区域的定位有很多方法，其中常见的有模板匹配定位法、几何特征（如边缘特征）定位法、小波变换定位方法等。这些方法都广泛应用于人脸检测、期刊图像文件处理系统、车牌识别等领域［3］。目前绝大多数方法无法对存在透视畸变的图像进行纠偏［4］，少数采用边缘检测与直线拟合的方式实现了透视畸变的校正，但是对于背景较为复杂的图片，这些算法极易受到背景中存在的其它长边界的干扰，造成定位错误［5］。唐毅等提出基于连通域几何特征的图像感兴趣区域自动定位方法，取得了优于基于模板匹配的定位方法实验结果［3］。蔡峰等的研究也表明基于连通域分析的方法可以取得较好的定位结果［6～7］。本文图片笔记应用中目标图像往往背景复杂，基于边缘检测算法的定位方法极易受到伪边界的干扰。但由于目标图像内容底色比较均匀，在恰当的二值分割基础上，可以发挥基于连通域特征分析定位方法［8］的优势，取得较好效果，测试结果证明了这一点。

2　算法描述

2.1　图像二值化

针对本文研究图像感兴趣内容区域与背景色差明显的特点，使用Otsu算法或者全局阈值迭代法可以对目标区域进行大致的分割。但是全局阈值算法的局限性导致获得的分割结果极易受到光照的影响而造成区域的虚多或残缺。无论哪一种情况，对于后续的顶点定位处理均存在十分不利的影响。因此阈值分割不仅应当考虑区域的整体灰度特性，还应当保留区块的线特性，通过检测区域边缘，实现针对目标区域的阈值分割［9～11］。参考文献［12］的思路，本文兼顾区域特征和边缘特征的阈值分割算法步骤如下。

1）输入RGB图像灰度化，结果记为G；

2）使用Sobel算子分别计算图像水平、垂直梯度，二者的绝对值相加得到边缘图像L；

3）使用OTSU方法分别处理G和L得到二值图像T1和T2；

4）遍历二值化的边缘T2，对其中非零点的3×3邻域求均值Avg，并设定邻域内像素点的阈值为Avg；

5）根据原图灰度信息及修改过的像素阈值，修改T1各个像素点的值，最终得到保留了边缘特性的目标二值图像T1。

算法测试结果如图1所示。

图1　图像二值化结果

从图1结果可见，本文算法阈值分割结果在成功保留了图像的区域特征基础上考虑到了区域边缘的结构，目标分割效果优于一般的全局阈值算法和局部阈值算法。

2.2　基于连通域特征的快速区域定位

区域定位的准确与否直接影响到后续的目标裁剪、检测识别等精度和可靠性。本文基于二值图像连通域特征的目标区域定位算法主要包括2个步骤提取候选区域和定位四边形区域定点，算法流程如图2所示。

图2　本文区域定位算法流程图

2.2.1连通域分析提取候选区域

1）提取所有连通域

通过在二值图像上搜索连通域，并根据连通域的面积大小进行排序筛选，提取在图像中的所有可能包含目标的连通域。经过对大量真实场景图像测试后发现：若设定限制条件，使得目标连通域面积占图像总面积的5%~10%以上时，能够在保证识别结果正确的情况下限制算法对无效结果的识别。

2）去除无关连通域

常用的凸包查找算法有Jarvis步进法、Graham's扫描法、Melkman法等多种方式［13］。去除无关连通域，需要进一步分析目标连通域与其它连通域的结构差异。在测试、对比分析的过程中可以发现：在拍摄图片作为笔记的过程中，目标区域一般处于屏幕核心位置，且不存在遮挡的情况下均为凸四边形。因目标区域的存在，导致背景部分连通域经常会带有明显的内凹或缺陷。于是在进行连通域筛选时，将连通域自身面积与其凸包面积相比较，排除面积比小于某常数的连通域，实现对目标区域的筛选。在实验过程中，设定参数ε为［0.85，0.9］之间时，能够实现绝大多数情况下的正确筛选。测试结果如图3所示，对于这一定位区域明显小于正常定位区域的图片，仅需要三次连通域分析，就能够实现对目标区域的正确定位。

图3　测试图片（左）与定位结果（右）

2.2.2定位四边形区域顶点

1）椭圆拟合

任意凸四边形均存在外接椭圆［12］。在平面直角坐标系中，一般通过如式（1）形式的圆锥曲线方程表示椭圆，平面直角坐标系中的椭圆如图4所示。

图4　平面直角坐标系中的椭圆

使用椭圆进行拟合，一般采用最小二乘法进行运算，得到的结果保证测量误差的平方和最小。最小二乘法实现步骤是：寻找出参数集合，使数据点与椭圆之间的总距离达到最小，一般使用代数距离或者欧式距离作为度量标准。当使用代数距离进行最小二乘运算时，将式（1）中的条件设置为A+C=1；计算得出每一个方程对应系数，形成评估函数 F(a，b，c，d，e，f)（式（2））［14～15］：

而后，对函数F求极值，在式（3）成立时，F取得最小值。

最后，使用高斯消元法对这一线性方程组进行求解，求得椭圆方程的所有参数。

2）顶点定位［16］

使用椭圆对四边形目标的凸包区域进行拟合，能够得到一个近似为凸包轮廓外接椭圆的方程。此时，目标四边形的顶点落在椭圆的边缘附近。为了方便计算，建立一个新的平面坐标系，将椭圆中心作为原点，椭圆方程便成为式（4）的形式。

其中，a.b分别为椭圆的长、短半轴长，α表示点（x，y）与椭圆长半轴的逆时针旋转角。将凸包点集内的点进行坐标变换后，代入椭圆方程当中，令

由于点 f(x，y)数量较少，比较所有点的f(x，y)值，抽取其中最大值所对应点作为顶点之一；删除该 f(x，y)的值，再次从大到小遍历f(x，y)，以最大值法筛选出其他三个顶点；同时设置约束条件，使得四个点与凸包轮廓质心连线的夹角两两之间小于α，以防顶点被重复定位。在实验过程中，设置α=5°~10°可以较好实现对于区域顶点的定位。

测试结果如图5所示。由图5可见，对于透视畸变明显的图像，也能够实现准确定位。

图5　测试原图（左）以及定位结果图（右）

3　基于Android平台的目标图像自动裁剪实验及结果分析

在本文自主研发的Android平台图片笔记APP中，在区域定位基础上对会议拍摄内容，包括幻灯片、黑白板等进行自动裁剪实验，对存在几何透视畸变的图片，定位后进行了基于消隐点的透视畸变矫正［17～19］。为确保可比性，预处理过程和方法一致，对比结果如图6～8所示。

图6　裁剪结果图：原图（a）基于边缘检测算法的定位方法（b）本文算法（c）

图7　裁剪结果图：原图（a）基于边缘检测算法的定位方法（b）本文算法（c）

图8　裁剪结果图：原图（a）基于边缘检测算法的定位方法（b）本文算法（c）

3.1　裁剪效果图分析

本实验图像均通过日常拍摄得到，涵盖了大量不同的复杂场景。对比上述结果不难发现，本文算法相比于基于边缘检测算法的定位算法在处理带有复杂背景、伪边界的目标图像时具有更高的正确率。

3.2　算法执行速度分析

分辨率调整能够大大提高预处理以及后续区域定位的运算速度，经过反复测试，最终确定将图像分辨率调整为500×500，以提高预处理及后续操作的速度，减少运算量。针对2种分辨率不同的图像，算法执行时间比对如表1所示。本算法测试通过HTC 802t完成，表1为该手机的软件、硬件参数。

表1　HTC 802t手机参数

表2　算法执行时间

从表2内容可见，本文算法图片定位时间稳定在100ms～200ms之间，校正时间主要受到目标区域大小的影响而发生变化。与基于边缘检测的定位校正算法相比，本文算法总体耗时减少超过80%，表明其执行速度快，易于优化，更适合在移动设备当中应用。

4　结语

对于图片笔记管理软件而言，使用自动定位、校正算法，对图片中笔记区域进行定位，并对定位结果进行透视畸变校正，能够大大降低操作的复杂程度，去除无用的背景信息，改善软件使用中的用户体验。其中，区域定位算法的准确率在很大程度上决定了用户交互扫描图片操作的复杂程度。本文着重分析了笔记图像普遍具备的区域特征，设计并实现了对图像目标的自动定位算法，基本解决了现在被广泛投入应用的边缘拟合算法所存在的诸多弊端，如算法复杂度高、容易受到伪边界干扰、优化困难等。本文算法具有较强的应用价值。对于区域筛选方面，本文使用了轮廓面积与凸包面积比实现目标区域的选择。在后续工作中，可以考虑通过轮廓多边形的面积、周长、凸包等数学表现，及其内接、外接多边形的性质，对轮廓大致形状进行估计，自动判断、区分出四边形与其他多边形，进一步提高算法的鲁棒性。

［1］王华旭.Android平台图像处理软件框架的开发与设计［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］周翔，陈会，张锴，等.复杂背景下的图像文本区域定位方法研究［J］.计算机工程与应用，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］唐毅，郑丽敏，任发政，等.基于几何特征的图像感兴趣区域的自动定位研究［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平台图像分割算法研究及系统实现［D］.济南：山东大学，2015.JINXin.Research and Implement on Android Platform-based on image segmentation algorithm［D］.Jinan：Thesis forMaster Degree，Shan Dong University，2015.

［5］贺辉，刘琨，肖红玉.银行票据自动裁剪方案设计与控件开发［J］.计算机与数字工程，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］.计 算 机 应 用 ，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］胡小锋，周勇，叶庆泰.复杂背景彩色图像中的文字分割［J］.光学技术，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］陈寅鹏，丁晓青.复杂车辆图像中的车牌定位与字符分割方法［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］关强，薛河儒，姜新华.基于Android平台的图像预处理系统的研究［J］.内蒙古农业大学学报（自然科学版）.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］张庆英，岳卫宏，肖维红，等.基于边界特征的图像二值化方法应用研究［J］.武汉理工大学学报，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］.计算机辅助设计与图形学学报，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］.北京航空航天大学学报，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］.河南科技大学学报（自然科学版），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］.小型微型计算机系统，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］苗立刚.基于形态学的文档图像透视校正算法［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］.南京理工大学学报，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.