基于积分图的LATCH算法改进①

陈方飞,冯 瑞

1(复旦大学 计算机科学技术学院,上海 201210)

2(上海视频技术与系统工程研究中心,上海 201210)

基于积分图的LATCH算法改进①

陈方飞1,冯 瑞2

1(复旦大学 计算机科学技术学院,上海 201210)

2(上海视频技术与系统工程研究中心,上海 201210)

LATCH(基于机器学习的三像素块描述子)在原有局部二值描述子的基础上通过将二像素块比较改为三像素块提升了局部二值描述子的准确率,但提高准确率的同时带来了更大的时耗,在研究LATCH以及其他二值描述子的基础上,借鉴积分图在目标检测中的应用,将积分图的思想应用在改进LATCH描述子中,减少了LATCH描述子中各像素块内的重复计算量.实验证明,改进算法的描述子计算时间较原算法缩减了30%–40%,而配准精度与原算法保持相近.

局部二值描述子;LATCH;像素块;积分图

图像局部视觉特征信息的有效表示在许多计算机视觉应用中都是至关重要的,如图像索引,需要从查询库中进行大量局部特征提取与计算而定位与查询项匹配度最高的图像.因此计算机视觉领域研究中有很大部分关注于如何确定局部信息描述子或如何提升已有描述子的精度与效率.经过多年的研究与发展,图像局部信息描述子形成了两大主流研究方向:基于分布的描述子与二值描述子.

基于分布的描述子主要描述特征表征量(如梯度,梯度方向等)的图像分布信息,其中突出的描述子有HOG[1],SIFT[2]描述子,SIFT描述子通过计算特征局部区域梯度方向分布表征特征点局部视觉信息.基于分布的描述子在特征描述的准确度有显著效果,但随着精度不断增加,计算时耗与内存开销也在不断增加.

近年来,由于计算机视觉应用中图像数据库容量急剧上升,图像分辨率增大.对特征描述子的计算时耗需求触动了二值描述子的逐渐发展.二值特征描述子比较像素块之间的值得到一个二进制串,二进制串可以直接通过计算哈明码距离进行匹配,极大提高了运算速度.其中突出的描述子有BRIEF[3],ORB[4]以及FREAK[5].

传统二值描述子提高速度的同时带来了匹配准确度的下降,2015年 Gil Levi与 Tal Hassner提出了LATCH[6]算法,并且以加入OpenCV函数库中,在传统二值描述子的基础上,针对匹配准确度,从以下两方面进行了改进:

① 三像素块比较代替两像素比较

② 像素块位置通过机器学习选出最优位置组合

LATCH算法在准确度上提升了,但三像素块带来更大的计算量.通过深层研究发现,LATCH中主要时间消耗在每次对每像素块进行遍历计算中.

参照文献[7]中,通过积分图消除重复运算的方法,本文对LATCH算法进行如下改进

① 修改像素块比较公式,适应积分图计算

② 应用积分图计算局部特征描述子

实验证明,改进算法的描述子计算时间较原算法缩减了30%～40%,而配准精度与原算法保持相近.

1 LATCH算法

LATCH前二值特征描述子比较以特征点K为中心检测窗口W内特定像素对比较的结果.设检测窗口W内T对有序样本坐标集如式(1)所示:

通过如下公式(2)可以求出每个像素对比较的二值结果:

比较窗口内所有像素对,形成该特征点处二进制串,可以描述该关键点特征.由于是单像素间的比较,容易受噪声影响.LATCH在此基础上提出了三像素块之间的比较计算得到比特串,增强抗噪能力.

1.1 三像素块比较

单像素间的比较,容易受噪声影响,部分研究通高斯平滑消除噪声影响,但消除噪声也将造成关键点处信息丢失.Gil Levi与Tal Hassner提出通过三像素块的比较解决噪声的影响并提升匹配精度.

在每个检测窗口W内定义了T组三像素块,窗口内像素块集如式(3):

每个像素块定义为 像素块,上述表达式中每个像素块坐标k×k为像素块中心点坐标.通过式4评估锚点像素块为像素块中心点坐标.通过式4评估锚点像素块与两个对比像素块与之间的相似度作为一个该特征点的一个比位.

1.2 基于学习的像素块组合

每个检测窗口中三像素块位置组合数规模庞大,一个49×49检测窗口,假定像素块大小为7×7,三像素块位置组合数规模在亿的数量级.而特征描述计算过程中用到的三像素块组合是有限的,如何在规模庞大的数据组合中选出有限的组合,使匹配效果达到最优是一个重要问题.Gil Levi与Tal Hassner提出了基于机器学习确定较优组合的方法.

1.2.1 学习数据集

学习数据集是建立在文献[8]所提供据集,数据集包括:Liberty,Notre Dame以及Yosemite三个独立数据集,每个数据集包括约20万个 局部图像窗体,窗体是从不同角度拍摄,并在文本文件中标注各个局部图像窗体是否相同(整个图像是对场景的3D拍摄场景,通过Harris提取算法提取出不同场景点的局部窗口,同一场景点的不同拍摄角度具有相同索引号,即为相同).LATCH中使用了其中20万个局部窗体块,其中一半窗体为相同的,另一半为不同.

1.2.2 学习算法

LATCH学习算法的基本思想是通过对大量组合进行匹配结果比较,筛选出较优组合.首先通过随机算法产生5万6千个三像素块组合.以每个像素块组合匹配所有局部窗体结果,每个组合方案根据其匹配结果与标注结果比较可以产生一个 大小的比特串(其中1表示匹配结果与标注结果一致,0为不一致).评估每个组合方案好坏可以通过计算每个比特串的和,即公式(5):

和值越高,效果越好.

但单纯这种选择选择结过可能导致相关性强的几个组合方案同时被选择,为避免该情况需要对每个待选择组合方案与所有已选中组合方案进行相关性计算,只有相关性小于一定阈值才可被选中,相关性的计算可以通过计算各比特串间汉明码确定.

2 LATCH算法改进

LATCH以像素块取代像素点的计算,提升了准确度,而由于需要对每个像素块遍历计算,增加了运算量.本文在研究LATCH算法与积分图算法的基础上,在保持整体不变的情况下,通过改进LATCH算法计算公式以适应积分图运算.减少了计算量,同时也保证了准确度.

2.1 积分图算法

积分图最早是由Paul Viola[9]等人提出的,并被应用到实时的目标检测框架中.是能够计算矩形块特征的快速有效方法.积分图中每个像素位置(x,y)的值不同于简单灰度,或彩色图存储的是像素值,而是从原点到(x,y)包含区域所有像素点的和,其表达式如公式(6):

任意矩形区域 像素和如图1所示.

图1 积分原理图

所以,利用积分图计算矩形区域特征如公式(8)所示:

根据公式,如下代码代码段1是积分图计算伪码:

2.2 基于积分图的LATCH算法改进

由3.1可知,积分图在处理矩形区域和特征计算能够非常有效,而LATCH算法中超过95%计算量在每像素块之间的计算中.如果能将积分图算法引用到LATCH中像素块计算中,可以提高LATCH算法计算效率.

由式(4)LATCH像素块比较计算式可知,像素块计算式对像素块对中每个对应像素进行求差的绝对值再求和.因此不利于积分图计算的开展.而如果只求差,不求绝对值,再求和,如式(9):

对上式进行变换,可得到公式(10):

由上式可知以及积分图算法原理可知,该计算式可以通过积分图算法提升计算效率.如下代码段2是改进LATCH伪代码.

2.3 区域分布特异化

由式(9)可知,改进的LATCH算法中像素块比较公式,所体现的是整个像素块特征,不能在像素块区域内体现区域分布特征.而特征描述中,区域分布同样是表示特征的非常重要信息.因此为了在像素块内同时体现区域信息,对像素块内不同像素带赋予不同权值.其像素带分布如图2所示,根据不同像素带,确定不同权值如公式(11)所示:

图2 像素带分布

3 实验结果

本文实验平台为Windows 7,处理器型号是Intel Core i5-3470,内存大小为4GB,程序采用C++语言编程,通过调用OpenCV 3.0对图像进行基本操作.实验数据集如2.2.1描述数据集,该数据集共有约60万个图像窗口,使用其中20万个图像窗口进行学习训练得到三像素块位置,剩余40万作为验证实验数据集.

3.1 实验评估指标

实验采用文献[10]中局部描述子方法对实验结果进行评估,即基于正匹配率对负匹配率的ROC值得评估方法.其中:

正匹配率(True Positive Rate):指正确匹配的样本数量与可能匹配的样本比值,如式(12):

负匹配率(False Positive Rate):指在描述子数据集中被错误地匹配的概率,如式(13):

%95错误率(%95 Error Rate):正匹配率为95%时的负匹配率,如式(14)所示:

3.2 参数分析

本文所述描述子主要受两个参数影响:每个特征点描述子字节长度,以及像素块大小,下面将对两个影响因子分别分析.

1)描述子长度分析

描述子长度是指每个特征形成的描述特征信息的二进制位数,本文分别对长度为8字节、16子节、32字节以及64字节进行试验,图3是各个字节长度ROC曲线.由图3可知,随着字节长度增大,效果越好,64字节长度虽然比32字节整体效果好,但相差没有特别明显,而且64字节长度将大大提升描述子计算及匹配时间,因此本文采用32字节作为推荐描述子长度.

图3 描述子长度对比结果

2)像素块大小分析

影响描述子表示特征信息能力的另一个因子是像素块大小.本文分别以5×5、7×7、9×9、11×11像素块大小进行比较试验,图4是各个尺寸ROC曲线,由图可知,随着尺寸增大,描述子表示特征信息效果越好,但当增大一定尺寸后,效果开始变差,这是由于像素块尺寸过大,将导致描述子各位间区分度下降.从而使描述子整体准确度降低.

图4 像素块尺寸对比结果

3.3 实验结果对比

本文主要针对LATCH算法在运行效率上的不足进行改进,因此本文主要与LATCH算法实验结果进行比较.定量比较改进算法与原算法在描述在计算效率以及表示特征信息准确度两方面效果.

(1)运行效率

运行效率的比较首先通过ORB算法对720P图像特征点计算,再计算原算法与改进算法对整副图像描述子计算耗时,本文对10幅图像进行试验,最终计算对每个特征点描述子计算平均耗时,结果如表1所示,由表可知,改进算法相对原算法计算耗时极大减少.

表1 运行效率对比

2)准确度

为定量分析改进算法与原算法间的准确度差别,本文在原算法与改进算法ROC曲线基础上,分别计算AUC值,ACC值以及95Err值进行比较.下表2,是计算中对比结果,由表可知,改进算法在准确度上与原算法几乎一致.

表2 准确度对比

4 结语

本文在研究LATCH算法的基础上,提出了通过改进比较公式,引用积分图算法,减少算法在像素块内的计算时间,实验表明本文在几乎不影响精确度的情况下,极大地减少了运算时间,提高运行效率.本文主要有两个贡献点:(1)系统介绍了LATCH算法原理(2)提出了基于积分图思想的LATCH算法改进,改进了LATCH算法中像素块间比较公式以适应与LATCH算法,并对改进算法与原算法进行定量分析.

1 Dalal N,Triggs B.Histograms of oriented gradients for human detection.CVPR.San Diego,CA,USA.2005,1. 886–893.

2 Lowe DG.Distinctive image features from scale-invariant keypoints.IJCV,2004,60(2):91–110.

3 Leutenegger S,Chli M,Siegwart RY.Brisk:Binary robust invariantscalablekeypoints.ICCV,Barcelona.2011.2548–2555.

4 Yang X,Cheng KT.Ldb:An ultra-fast feature for scalable augmented reality on mobiledevices.In Mixed and Augmented Reality(ISMAR).2012.49–57.

5Alahi A,Ortiz R,Vandergheynst P.Freak:Fast retina keypoint. CVPR.Providence,USA.2012.510–517.

6 Levi G,Hassner T.LATCH:Learned arrangements of three patch codes.Winter Conference on Applications of Computer Vision(WACV).Lack Placid.2016.1–9.

7黄文杰,陈斌.一种快速图像处理的积分图方法.计算机应用,2005,25(S1):266–269.

8 Brown M,Hua G,Winder S.Discriminative learning of local image descriptors.PAMI IEEE,2011,33(1):43–57.

9 Viola P,Jones M.Rapid object detection using a boosted cascade of simple features.CVPR.USA.2001,1.511–518.

10 Mikolajczyk K,Schmid C.A performance evaluation of local descriptors.PAMI IEEE,2005,27(10):1615–1630.

Improved LATCH Based on Integral Image

CHEN Fang-Fei1,FENG Rui2

1(School of Computer Science,Fudan University,Shanghai 201210,China)
2(Shanghai Engineering Research Center for Video Technology and System,Shanghai 201210,China)

LATCH(Learned Arrangements of Three Patch Codes)improves the accuracy of local binary descriptor by comparing three pixel blocks rather than tow pixel blocks.However,the improvement of accuracy brings a larger time consuming.Based on the study of LATCH and other local binary descriptors,using integral graph theory in improved LATCH descriptor,it reduces repeated calculation of each pixel blocks in LATCH descriptors.According to the experiment results,the computation time of the improved algorithm is reduced by 30%–40%compared with the original algorithms,while the accuracy of the improved algorithm is similar to that of the original algorithm.

local binary descriptor;LATCH;patch;integral image

国家科技支撑计划(2013BAH09F01);上海市科委科技创新行动计划(14511106900);基于BIM+GIS城市大数据计算平台的智慧临港应用示范(ZN2016020103)

2016-08-08;收到修改稿时间:2016-09-18

10.15888/j.cnki.csa.005716