Efficient Integral Image Calculation Based onGray Level Co-occurrence Matrix

1 INTRODUCTION

Gray level co-occurrence matrix (GLCM) is first described by Haralick et al.[1].It captures second-order gray-level information,which is mostly related to human vision perception and discrimination of textures.GLCM has been widely used in texture segmentation,classification,and medical image analysis in particular.

Although the computational complexity of GLCM for an image withN×Nis onlyO(N2),but for many applications,it is necessary to compute GLCM on sub-image (block),which means that there will be many repeat computation happens. The processing power requirements for multiple GLCM computation per time unit can be prohibiting.

Integral image (also called as summed area table by F.Crow[2]),is an algorithm in computer graphics for quickly generating the sum of values in a rectangular subset of a grid. Since Viola and Jones use it in face and pedestrian detection[3-4],it is now widely used in computer vision for object detection framework.

In this paper,we represent each element in GLCM with a corresponding integral image.Details of GLCM computation based on integral image will be described in following sections.Section 2 describes the integral image.Section 3 presents the basic concept of GLCM and its computation based on integral image.Experimental results and conclusion are presented in Section 4 and 5 respectively.

2 INTEGRAL IMAGE

Integral image is an intermediate representation of image,all the rectangular two-dimensional image features can be computed rapidly using this representation.The integral image,as seen in Fig.1 (a),denotedii(x,y),at location (x,y)contains the sum of the pixel values (intensity,one channel of color,or binary image) above and to the left of(x,y).Formally,

(1)

wherei(x,y) is the input image.The integral image can be computed in one-pass over the image using the following pair of recurrences:

s(x,y)=s(x,y-1)+i(x,y)

(2)

ii(x,y)=ii(x-1,y)+s(x,y)

(3)

wheres(x,y) denotes the cumulative row sum ands(x,-l)=ii(-1,y)≡0.

Given the integral image,any rectangular sum of pixel values aligned with the coordinate axes can be computed in four array references (See Fig.1 (b)).For example,to compute the sum of region with black in Fig.1(b),the following for references are required:D-B-C+A.Given the integral image,all the Haar features can be computed in constant time.

(a) The value of the integral image at point (x,y) is the sum of all the pixels above and to the left;(b) The sum of the pixels within rectangle with black can be computed with four array references:D-B-C+A;(c) A source image;(d) Integral image of (c) and the rectangle with gray color in (c) can be computed as follows:15-7-5+1=4.

Fig.1IllustrationofIntegralImage

There are also many extensions of integral image.M.Hussein et al.propose a method called kernel integral image[5]which allows for application of a wide class of non-uniform filters.Y.Ke et al.generalize integral image to three-dimensional (called integral video[6]) for visual event detection.K.Derpanis et al.extend integral image into the higher-order,see[7].In Section 3,we describe how to compute GLCM based on integral image.

3 GLCM COMPUTATION BASED ON INTEGRAL IMAGE

A GLCM is a matrix that is defined over an image to be the distribution of co-occurring values at a given offset (Fig.2 (b) shows four offset directions).Mathematically,a co-occurrence matrixCis a defined over ann×mimageI,parameterized by an offset(Vx,Vy),as:

(4)

When computing the GLCM of blocks in given image,if the blocks are overlapping each other,there will be many repeat computations.So,we first construct an integral image set,

IISet={Iij|i,j=0，1，…，L-1}

(5)

whereIijis an integral image ofC(i,j),Lis the gray value level.Details are given in algorithm 1.

(a) Four offset directions:(-1,+1),(0,+1),(+1,+1),(0,+1),(b) Computation each element of GLCM based on integral image set constructed via gray level image

Fig.2IllustrationofGLCMcomputationbasedonIntegralImage

Algorithm 1.GLCM computation based on Integral Image

Input:I:Gray-level image,

(x,y):left and top coordinate of block,

(Vx,Vy):offset,

w:block width,

h:block height.

Output:Cx,y(i,j),i,j=0，1，…，L-1

(6)

Step3:Computation each elements of GLCM

for(i=0;i

for(j=0;j

Cx,y(i,j)=Get_IImage(Iij,x,y,w,h)

end for

end for

Get_IImage(Iij,x,y,w,h) can be rapidly computed by four array references as shown in Fig.1 (d).

4 PERFORMANCE EVALUATION

Our method has been tested on an image with size 1000×1000,each gray-level value is generated randomly.First we set the gray level as 8,and then vary the block size to evaluate the speed up.The block size varies from 8×8 to 128×128,overlapped with 3/4 width[8].Note that in this experiment,the computation time of integral image is not included.Experiment result is shown in Fig.3.

Fig.3SpeedupofGLCMcomputationbasedonIntegralImagewithvariousblocksize

It is noted that Step 2 in Algorithm 1 will need a lot of computation time.So we vary the gray level from 2 to 10,and then include the computation time of integral image to evaluate the performance our proposed method.It can be seen from Fig.4 that when the gray level increase,the speed up decrease.This is because that in our method we have to constructL2integral images.And the integral images will occupy about 25% computation time.So the speed up decreases when the gray level increases.Even though,when the gray level is less than 6,our method can speed up computation time two times to 18 times.This is useful in most image processing or computer vision applications,for the gray-level is usually about 4.

Fig.4 Speed-up with various gray-levels

5 CONCLUSION

An efficient method of GLCM computation based on integral image is proposed in this paper.It first constructs an integral image set for each element in GLCM,and then the value of each element of GLCM can be rapidly computed based on integral image with for array references.Experiment results show that when the gray-level is less than 6,our method can speed up a lot.

[1]R.M.Haralick,K.Shanmugam,I.Dinstein．Texture features for image classification[J]．IEEE Trans.Syst.Man Cybern,1973，3：610～621.

[2]F.Crow．Summed-area tables for texture mapping[J]．Computer Graphics,Techniques (SIGRAPH’84).1984,18(3):207～212.

[3]P.Viola,M.Jones.Robust real-time face detection[J]．International Joural of Computer Vision,2004，57(2)：137～154.

[4]P.Viola,M.Jones,D.Snow．Detection pedestrians using patterns of motion and appearance[C]．Proceedings of Internation Conference on Computer Vision,2003,734～771.

[5]M.Hussein,F.Porikli,L.Davis.Kernel integral images:a frame work for fast non-uniform filtering[C]．Proceedings of Internation Conference of Computer Vision and Pattern Recognition,2008.

[6]Y.Ke,R.Sukthanka,M.Hebert．Efficient visual event detection using volumetric features[C]．Proceedings of IEEE International Conference on Computer Vision,2005:166～173.

[7]K.G.Derpanis,E.T.H.Leung,M.Sizintze．Fast scale-space feature representations by generalized integral images[R]．Technical report,York University.

[8]姜景連．一類矩陣代數(shù)上保持交換性的導子[J].吉林師范大學學報(自然科學版)，2013,34(3)：86～87.