SURF中快速求取积分图像的直接替换算法*

韩 冰,孙继银

(第二炮兵工程学院,西安 710025)

0 引言

SURF(speed up robust features)[1-3]算法 ,是目前效率最高的局部区域特征提取和描述算法,非常适用于目标识别和目标跟踪等对实时性要求较高的军事领域。SURF的高性能与积分图像(integral image)的使用密切相关。积分图像最早由 Crow[4]于1984年提出,用于求取图像的纹理映射。后又被应用于灰度图像匹配[5-6]、人脸识别[7]和目标识别[8-9]。凡是使用过积分图像的算法,在执行速度上都会得到明显的提升,这是由于它在计算一定矩形区域内灰度值和时,只需3个简单加减运算即可完成,能够大大提高算法效率。

积分图像的求取过程是SURF算法的第1步,因此其计算速度和内存占用都会对SURF的整体性能提升造成一定影响。目前已有的快速求取积分图像的算法有两种,一是由Lewis[5]于1995年提出(以下简称 Lewis算法),二是由Viola[7]于2001年提出(以下简称Viola算法)。其中Viola算法也是SURF中所使用的算法[1-3,10]。由于其在执行过程中,共需占用3个图像空间,因而内存消耗过大,而且过多内存占用,会使图像空间之间的查址调用过程消耗过多的时间,使得算法速度变慢。

因此,文中从降低内存消耗和时间花费的角度出发,对已有Viola和Lewis算法分别进行改进,结合SURF算法过程只使用积分图像而不使用原图像的特点,提出了两种只占用1个图像空间的快速积分图像求取算法——直接替换算法I和II(direct replacement algorithm I and II)。经理论分析和实验验证,这两种直接替换算法在执行时不仅大大降低了内存消耗,而且其时间花费均明显少于Viola和Lewis算法。

1 Lewis和Viola算法

积分图像的定义是:图像中任意一点(i,j)的值ii(i,j),表示原图像相应灰色区域灰度值和,如图1和式(1)所示。

图1 积分图像的定义

式中:p表示原图像,p(i′,j′)表示原图像中像素点(i′,j′)的灰度值 。

如果直接利用式(1)求取积分图像,1个像素会被遍历很多次,算法效率很低,速度很慢。而 Lewis和Viola算法却只需对图像像素遍历一遍,速度较快,因此下面将详细分析比较这两种快速的积分图像求取算法。

1.1 Lewis算法

1995年,为了快速计算归一化积相关系数,Lewis提出了一种快速的积分图像求取算法,如式(2)[8-9]所示。

式中:ii(i-1,j)、ii(i,j-1)和ii(i-1,j-1)表示与(i,j)相邻的3个已知像素积分值,p(i,j)为原图像(i,j)位置的像素值。

1.2 Viola算法

2001年,Viola在其人脸识别算法中也提出一种快速求取积分图像的算法[10-12],如式(3)、式(4)所示:

其中,S(i,j)表示图像某一行的列积分值,且S(i,-1)=0,ii(-1,j)=0。

1.3 Lewis与Viola算法比较

这里将从内存消耗和时间花费两个方面对Lewis和Viola算法进行比较。

1)在内存消耗上,如式(3)、式(4)所示,Viola算法需要分配3个图像大小的空间给S、p和ii,内存占用率过高,这在某些内存只有几MB或几十MB的嵌入式系统中,消耗过大;相对而言,Lewis算法只需分配2个图像空间给p和ii,如式(2)所示,因此内存消耗较低。

2)Viola算法计算一个像素积分值只需两个加法运算,而Lewis算法计算一个积分值却需要3个加减运算。因此,理论上Viola算法的速度应当快于Lewis算法。但是实际中,由于Viola算法占用的内存大,其花费在CPU和内存I/O传输的时间就要比Lewis多,因为Viola计算一个像素积分值时需要在3个图像之间进行查址调用,而Lewis只需在2个图像之间进行查址调用。所以,实际计算中,Viola算法的运算速度要比Lewis算法慢,如图2所示。

由图2可以看出,Viola算法的速度确实较慢,其计算一个积分值只需2步加减运算的优势并未发挥出来,而是被在3个图像之间中进行查址调用所占用的时间给掩盖了。因而可以说明对于积分图像求取算法而言,占用图像空间越多,其时间花费也就越多。

图2 Lewis和Viola算法的时间花费比较

2 直接替换算法

积分图像的求取是SURF算法的第1步,因此其执行速度的快慢会对SURF算法的整体性能产生一定的影响。图3给出了SURF算法的执行流程。可以看出,图中除步骤①需要使用原图像外,其余②～⑥步均未用到原图像,其中②、⑤、⑥步使用的是积分图像,③、④步没有用到任何图像,只用到了之前步骤中求出的det(Hessian)尺度空间。因此对于SURF算法,原图像只被用于积分图像的计算。

图3 SURF算法的执行流程

如果在计算积分图像时直接用积分值来替换原图像中的像素值,不仅可以达到节约内存的目的,而且无需在图像之间进行像素值的查址调用,从而可以提升算法速度。因此文中从降低内存消耗和减少时间花费的角度出发,提出了两种适合SURF使用,并只需占用1个图像空间的快速求取积分图像的直接替换算法。

2.1 直接替换算法I

第一种直接替换算法是对原Lewis算法的改进,其详细执行过程如图4所示。

图4 直接替换法I的算法过程

假设原图像大小为 H×W(高H,宽 W),则积分图像的求取步骤为:

Step 1 计算第0行,第 1至第(W-1)列的积分图像像素值,如式(5)所示。

Step2 计算第0列,第1至第(H-1)行的积分图像像素值,如式(6)所示。

Step3 计算第1至第(H-1)行,第1至第(W-1)列的积分图像像素值,如式(7)所示。

在直接替换法I的执行过程中,直接使用积分值代替了原像素值,因而整个过程只占用了1个图像空间。另外,CPU只需要针对1个图像空间做读写操作,而不用像Lewis那样在2个不同的图像空间中进行寻址、读取和写入操作,因而花费在I/O传输上的时间较少,所以速度也有所提升。

2.2 直接替换算法II

图5 直接替换算法II的算法过程

第二种直接替换算法是对原Viola算法的改进,其详细的执行步骤如图5所示。假设原图像大小为 H×W(高 H,宽W),则积分图像的求取步骤为:

Step1 首先定义一个变量s,并将原图像 p中(0,0)处的像素值赋给它,如式(8)所示。

Step2 计算第0行,第1至第(W-1)列的积分图像像素值,如式(9)和式(10)所示。

Step3 计算第1至第(H-1)行,第0至第(W-1)列的积分图像像素值。

首先计算第i行,第0列的积分图像像素值,如式(11)和式(12)所示。然后计算第i行,第1至第(W-1)列的积分图像像素值,如式(13)和式(14)所示。

直接替换算法II将原Viola算法中用于存储列积分值的中间图像S,简化为用一个变量s来代替,然后再用计算得到的图像积分值直接替换原像素值,因此整个过程也只占用1个图像空间即可完成。

2.3 两种直接替换算法的比较

下面将在内存消耗和算法执行速度方面对以上两种直接替换算法进行比较。

1)两种算法的内存消耗基本相同,只是从过程上来看,由于直接替换算法II要比算法I多引入了一个变量s,因此直接替换算法II比算法I要多消耗至少4个字节的内存。

2)从算法速度上看,将式(7)与式(13)、式(14)进行对照可以看出,直接替换算法II求取一个积分值时只需要2个加减运算即可完成,直接替换算法I则需要3个加减运算。因此在一般的串行流程下,直接替换算法II的运行速度要快于直接替换算法I。然而,如果在有并行运算能力的硬件环境下,直接替换算法I可以通过并行技术进行加速,加速后的直接替换算法I能够获得快于直接替换算法II串行执行时的速度。具体分析如下。

图6 直接替换算法I的并行执行

对于直接替换算法I来说,式(7)中图像坐标(i-1,j)和(i,j-1)处的积分值在求取过程中只有一个同时依赖的元素,即坐标(i-1,j-1)处的积分值,只要(i-1,j-1)处的像素积分值求出之后,在并行条件下,(i-1,j)和(i,j-1)处的像素积分值就可以同时求出,因此,同样计算4个相邻坐标处的像素积分值,串行条件下,需要4步才能完成,并行条件下只需3步即可实现,如图6所示。

依据以上思想,可以将直接替换算法I在并行条件下的执行步骤改进如下。具体过程如图7所示。

Step1 按照式(5)计算第0行,第 1至第(W-1)列的积分图像像素值。

Step2 按照式(6)计算第0列,第 1至第(H-1)行的积分图像像素值。

Step3 按照式(7)求取第1至第(H-1)行,第1至第(W-1)列的积分值,求取过程执行并行计算,每次同时计算两行的积分值。

对于直接替换算法II而言,其算法过程不容易进行并行实现,这是因为在计算积分值时,直接替换算法II必须依赖存储列积分值的变量s,只有先计算出s的值才能算出每个积分值,而且s的值在计算每一个积分值时都需要不断更新,因此在并行条件下,利用直接替换算法II计算整个积分图像时,只能进行串行条件下的逐行运算,实现同时求取几个像素积分值的并行运算不太容易。

因此如果计算图7中2行共12个像素的积分值,直接替换法II共需要执行24个加法运算,直接替换算法I逐像素求取时需要执行36个加减运算,而在并行求取时,相当于只需要执行3+3×4+3=18个加减运算即可完成,因此经过并行加速后的直接替换算法I比直接替换算法II的执行速度要快。

图7 基于直接替换算法I的积分图像并行求取

3 实验分析与验证

3.1 实验环境

文中在CPU为Genuine Intel(R)T2400 Core Duo,主频 1.83GHZ,内存1G的PC机实验环境下,在Visual Studio 2008中,使用C#语言编程实现了求取积分图像的Viola算法、Lewis算法和文中提出的直接替换算法I和II,并对它们的内存消耗和时间花费进行了实验测试。实验用图来自http://www.robots.ox.au.uk/～vgg提供的Graffiti图像,将其进行裁剪后得到如图8所示的测试图。实验时对该图像进行缩放变换,依次选取分辨率为128×128～1024×1024的图像序列进行测试,其图像间的像素增长间隔为128。

3.2 内存占用分析和测试

3.2.1 图像空间的定义及其内存占用分析

这里将一幅图像所占用的内存定义为一个图像空间。图像空间所占用的内存大小与其自身像素值的存储格式密切相关。

对于未处理过的原图像,一般为灰度图像,其像素值最大为255,由于256=28,因此原图像一般采用字节型或8位整型数来存储单个像素。相对而言,积分图像中的每一个像素值代表了原图像一定区域的像素值和,如果假设原图像尺寸为256×256,考虑其中所有像素灰度值都为255的极限情况,那么积分图像最右下角的像素值就为:28×28×28=224。这时如果还简单的使用字节型或8位整型数来存储单个像素,就会造成数据丢失的错误,这时应使用32位(4字节)的整型或浮点型。更进一步分析,假设原始图像尺寸为8192×8192,同样也考虑原图像所有像素灰度值都为255的极限情况,那么积分图像右下角的像素值就为:213×213×28=234。在这种情况下,32位的整型或浮点型数也无法存储单个像素,因此需要改用64位(8字节)的长整型或双浮点型数来存储。

综上所述,对于原图像而言,其像素值的存储格式与图像尺寸无关,采用字节型或8位整型存储即可,对于积分图像而言,其像素值的存储格式与图像尺寸有关,只要图像长宽均不超过4096,就可使用32位的整型或浮点型来存储,否则,要改用64位的长整型或双浮点型。

3.2.2 四种算法内存消耗比较与测试

假设原图像的大小为H×W(H和W均小于4096)。

对于Viola算法,原图像p占用的内存空间为H×W字节,中间图像S和积分图像ii分别占用4×H×W字节,整个算法过程共占用至少9×H×W字节的内存。

对于Lewis算法,原图像p占用的内存空间为H×W字节,积分图像ii占用4×H×W字节,则整个算法过程需占用5×H×W字节的内存。

对于直接替换算法I,由于存在像素值替换,因此在处理前,需要统一原图像p与积分图像ii像素值的数据类型,即全部采用32位的整型或浮点型数来存储像素。这样整个算法过程只需占用4×H×W字节的内存空间即可完成。

对于直接替换算法II,需要引入变量s来代替原Voila算法中的图像S,这里需要将s的存储格式定义为32位的整型或浮点型数据。另外与直接替换法I相同,在处理前也需要将原图像与积分图像ii的像素值的类型统一为32位的整型或浮点型,因此该算法过程占用的内存空间为4×H×W+4。

文中分别对Viola算法、Lewis算法和文中的直接替换算法I和II在运行过程中实际内存消耗进行了测试,详细的测试结果如表1所示。

表1 四种算法的内存消耗对比,单位/byte

由表1可以看出,随着原图像尺寸的不断增大,四种算法的内存消耗都随之增大。其中Viola算法的消耗最大、Lewis算法次之、直接替换算法I和II最小。并且随着图像尺寸的进一步不断增大,直接替换算法I和II节省内存消耗的效果会更加明显。对于直接替换算法I和II而言,两者的内存消耗差别不大,算法II只比I多消耗了4个字节内存,从而也验证了以上分析。

3.3 时间花费分析和测试

由1.3节分析可知 Viola与 Lewis算法相比,Lewis算法的速度较快。从2.3节的分析可以看出,在串行条件下,直接替换算法II的执行速度要快于直接替换算法I,但是直接替换算法I可以利用并行加速的方法获得比算法II还要快的速度。

对于直接替换算法I,式(7)中虽然也包含了3个加减法运算,但是它毕竟只占用1个图像空间,整个过程CPU只需对p一个图像空间进行查址调用和读写操作,因此与Viola和Lewis算法相比,直接替换算法I的执行速度应该较快。

文中分别对Viola算法、Lewis算法、直接替换算法I和II执行所花费的时间进行了测试,由于文中测试的实验环境是双核CPU,因此也对直接替换算法I的并行加速部分进行了编程实现,并测试了它的时间花费,详细的测试结果如表2所示。

表2 积分图像求取算法的时间花费对比,单位/ms

由表2可以看出,随着输入原图像尺寸的不断增大,四种算法的时间花费也随之增大,在串行执行的条件下,时间花费最少的为直接替换算法II,其次为直接替换算法I,然后为Lewis算法,花费最高的为Viola算法,另外还可以看出,直接替换算法I经并行加速后,速度比直接替换算法II要快,时间花费最少,从而也验证了以上分析。

4 结束语

文中针对目前SURF中采用的积分图像求取算法内存消耗和时间花费过大问题,通过对Viola算法和Lewis算法分别进行改进,并结合SURF算法只使用积分图像而不使用原图像的特点,提出了两种只占用一个图像空间的快速求取积分图像的直接替换算法。经过文中的理论分析和实验结果验证,得出了以下结论:

1)直接替换算法I和II的内存消耗和时间花费均小于Viola和Lewis算法。随着输入图像尺寸的不断增大,其省时省内存的效果会更加明显。

2)在SURF算法中应用时,由于直接替换算法II在串行执行时的速度最快,因此适合在PC环境下使用。但是算法II不易进行并行实现,相对的,直接替换算法I则非常易于并行实现,并且经并行加速后的直接替换算法I速度要快于算法II,因此它适用于并行的硬件环境,如DSP等。

[1]Herbert Bay,Tinne Tuytelaars,Luc VanGool.SURF:Speeded up robust features[C]//ECCV 2006,Springer LNCS 3951(1),404-417,2006.

[2]Herbert Bay,Andreas Ess,Tinne Tuytelaars,et al.Speeded up robust features(SURF)[J].Computer Vision and Image Understanding,2008,110(3):346-359.

[3]Herbert Bay,Beat Fasel,Luc Van Gool.Interactive Museum guide:Fast and robust recognition of museum objects[C]//IMV,2006.

[4]Franklin C Crow.Summed-area tables for texture mapping[J].Computer Graphics,1984,18(3):207-212.

[5]J P Lewis.Fast template matching[C]//Vision Interface,1995:120-123.

[6]D M Tsai,C T Lin.Fast normalized cross correlation for detection[EB/OL].Online,Internet,available:http://machinevision.iem.yzu.edu.tw/english_version/tech/correlation2-FastNorma-lized.pdf.

[7]Viola P,Jones M.Robust real time face detection[C]//ICCV2001,2001:747-760.

[8]Viola P,Jones M.Rapid object detection using a boosted cascade of simple features[C]//CVPR2001,2001:511-518.

[9]Viola P,Jones M.Robust real-time object detection[C]//Second International Workshop on Statistical and computational Theories of Vision Modeling,Learning,Computing,and Sampling,2001:1-25.

[10]Christopher Evans.Notes on the OpenSURF Library[EB/OL],Online,Internet,available:http://www.chrisevansdev.com/.MSc Computer Science,University of Bristol,2010.