灰度图像Legendre矩快速精确算法

灰度图像Legendre矩快速精确算法

高月芳1),2)，韩国强1)，李桂清1)，陈茂资2), 王栋２）

1)(华南理工大学计算机科学与工程学院，广州 5100）2) (华南农业大学信息学院人机交互研究中心, 广州 5102）

摘  要：本文提出一种快速精确计算灰度图像Legendre矩算法。该算法首先使用局部图像块表示(partial image block representation,简称PIBR )策略根据灰度值将图像分块表示，然后对每个图像块整体进行积分计算图像的Legendre矩。该方法在保证计算精度的前提下，具有较快的计算速度。实验结果验证了本算法的有效性。

关键字：Legendre矩；局部图像块表示；灰度图像

中图法分类号：TP391.41    文献标识码：A    

Exact and fast computation of Legendre Moments for gray images 

Yuefang Gao1), 2), Guoqiang Han1), Guiqing Li1), Maozi Chen 2), Dong Wang2)

1) (School of Computer Science and Engineering, South China University of Technology, Guangzhou 5100)

2) (Research Center of Human Computer Interaction, College of Informatics, South China Agricultural University, Guangzhou, China, 5102)

Abstract: This paper presents a new algorithm for exact and fast computation of Legendre moments on gray-scale images. In this paper, a partial image block representation algorithm is used to extract blocks of all intensities values. After the blocks extraction, the image can be redefined and computed using integral formula in terms of blocks of different intensities, instead of individual pixels which can reduce significantly the computational complexity in the computation of Legendre moments. The obtained results explain the superiority of the proposed method. 

Keywords: Legendre moments, partial image block representation, gray images

1 引言

自Hu首次提出矩理论以来，矩技术广泛应用于图像处理领域[1]。其中，正交矩(如Legendre矩[2])由于具有最小的信息冗余，且矩变换可逆，在图像重建[3]、图像检识别[4-5]等领域得到广泛应用。

由于直接计算Legendre矩涉及到大量的加法和乘法运算，人们提出了各种算法来提高其计算性能[6-10]。这些方法用求和取代积分来近似计算数字图像的Legendre矩。虽然提高了计算速度，但却忽略了计算精度。进而影响其在图像重建，特征提取等应用中的性能。舒华忠和Papakostas分别提出Legendre矩快速精确算法，但均局限于二值图像处理[11-13]。为精确计算一般灰度图像的Legendre矩，Yap和Hosny等通过对整个图像像素区域上的Legendre多项式采用数值积分的方式计算Legendre矩来消除离散近似误差[14-15]。由于需对图像中每个像素进行上述积分运算，所需运算量大。Papakostas等[16]提出局部图像块表示(partial image block representation ,简称PIBR)算法精确计算灰度图像的几何矩，通过对图像块整体而非单个图像像素积分计算来提高计算速度。本文旨在把PIBR方法推广到灰度图像Legendre矩的快速精确计算中。

本文通过对文献[15]中提出的方法做进一步改进， 采用PIBR算法根据灰度值的不同将原始图像进行分块表示，然后对不同灰度值的图像块整体使用数值积分方式计算其Legendre矩。由于是对图像块整体而非单个图像像素进行积分运算，这样可以在保证计算精度的前提下，减少整个图像的计算复杂度，缩短计算时间，提高Legendre矩的计算性能。

2 数字图像的Legendre矩精确计算

对于密度函数为的二维图像，其阶Legendre矩定义为：

    ，    (1)

其中为阶Legendre多项式，其定义为：

，，为偶数  (2)

给定一幅大小为二维图像，，由于Legendre矩仅在[-1,1]方形空间正交，为计算Legendre矩，首先需要将图像映射到区域。令，其中，。把看成逐片连续函数，即, ,。代入公式(1)可得其精确计算公式[15]：

                          (3)

其中

                (4)

,和分别表示在和方向的取样间隔，且对， 。公式(4)可重新表示为如下形式：

                                   (5)

其中：

                    (6)

       

                  (7)

,分别为公式(6-7)中积分的上限和下限。为一因子，具有如下形式：

                         (8)

且满足如下递归关系[15]：

              (9)

公式(3)通过对整个图像像素区域上的Legendre多项式采用数值积分的方式（公式（6-7）所示）精确计算Legendre矩，由于需要对图像中每个像素进行积分运算，运算量大。

3 数字图像精确Legendre矩的分块计算

正如上述分析，若把数字图像看作分段常数函数，则图像的Legendre矩可转化为对Legendre多项式的积分，因此能够得到公式(11)所示的显示计算公式。但即使使用公式(9)简化的计算，每一个矩值的复杂度仍为，时间开销大。为此，本文采用PIBR策略根据图像灰度值将图像分块表示，通过将每个图像块作为一个整体进行积分运算而非单个图像像素积分运算方法计算图像的Legendre矩，从而达到降低计算复杂度的目的。

3.1 局部图像块表示(PIBR)算法

图像块描述方法的定义为[13]：(1) 图像块是图像中的一个矩形区域，边平行于图像的轴，且一个块中的像素具有相同的灰度值；(2) 如果一幅图像用图像块来表示，且每个像素都属于且只属于一个快，那就说明这个图像使用块来表示的。此外，由于图像块是矩形的，所以最小的块只包含一个像素。

PIBR算法是图像块描述算法(image block representation，简称IBR)的扩展，IBR算法仅适用于对二值图像进行分块，PIBR算法在IBR算法基础上进行扩展，进而可用于对灰度图像进行分块表示。该算法包含一个扫描图像过程和记表过程，其实现可分为以下四个步骤：

步骤1：对图像的每一行进行扫描，找到第行的不同灰度值的目标区间。

步骤2：将这些区间和第行中那些具有相同灰度值的像素块进行比较。

步骤3：如果一个区间和上述灰度值的任何块都不匹配，则其为一个新块。

步骤4：如果该区间和相同灰度值的区间匹配，则此块的最后一行即为第行。

循环上述四个步骤直至图像的最后一行，就可以把灰度图像根据灰度值的不同分成一系列的长方形的块，每一组的块具有相同的灰度值。

3.2 快速计算

灰度图像经过PIBR算法处理后，图像可用二元组来描述，其中灰度值集合,为图像块集合, 其中

有块的像素值均是。表示图像中的灰度值，为图像中的灰度值的个数，最大值为255。为图像中经PIBR算法后灰度值为的像素组成的图像块，是灰度值为的像素构成的图像块的个数。分别记图像块的左上角和右下角坐标为和。则公式(3)可重写为：

                                 (10)

其中：

                                 (11)

              (12)

            (13)

由于公式(11-12)将公式(3)中双重求和计算变换为两个一维计算，且公式(12)将图像块作为一个整体进行积分计算代替公式(6-7)中对整个图像中每个像素进行积分运算，进而减少了加法操作和乘法操作，提高计算速度。 

3.3 算法复杂度分析

直接计算Legendre矩的时间开销很大，对于一幅大小为的图像，采用公式(11)直接计算的时间复杂度为，即每计算一个阶的Legendre矩需要计算次多项式乘法操作和加法操作。

本文提出的算法的时间开销包括两部分：一是采用PIBR算法对图像进行分块处理所花费的时间；二是使用公式(12)计算Legendre矩所花费的时间。由于前者花费时间相对于整个计算而言很短，可以忽略不计。而后者说花费的时间主要依赖于计算每个所需的时间。

由于其包含的图像块数为，而一般情况下。因此，从上述分析可以看出，改进算法的计算性能优于直接算法的计算性能。

4  实验结果与分析

在本节，本文对不同类型不同尺寸的图像进行了分析和比较，以测试本文提出算法的合理性和有效性，并分析算法可能存在的不足。

在此设计了以下一组四类测试图像组成：一类大小为像素的二值图像，如下图1(a)所示；二是包含较少细节但灰度值有大量细小变化的灰度图像，如下图1(b) 和图1(c) 所示，其大小均为像素；三是包含中等程度细节的灰度图像，如大小为的摄像师图像(图1(d))；最后一组是包含大量细节的大尺寸灰度图像，分别为大小为的编织物图案(图1(e))和的人群图像(图1(f))，为方便表示图像，在下图显示时对其尺寸进行了适当调整。实验环境为：Athlon X2 2.8GHz（双核）CPU，2GB内存，开发语言为C#，操作系统为Windows XP SP3简体中文版，以毫秒(ms)为单位度量计算所花费的时间。

             

(a)                     (b)                         (c)

             

(d)                       (e)                        (f)

图１　一组测试图像

首先，在此分别采用直接算法(公式(11)，简写为Eq.(11))和本文提出的算法(公式(12), 简写为Eq.(12))对图１中的六类图分别计算其前20阶Legendre矩所花费的时间及提高的比率(rate)。其结果如下表１所示：

表１直接法和本文提出的算法的计算性能分析(单位：ms)

矩的

阶数	图１(a)			图１(b)			图１(c)
	Eq. (3)	Eq(10)	rate (%)	Eq. (3)	Eq(10)	rate (%)	Eq. (3)	Eq(10)	rate (%)
3	201.79	16.47	91.873	232.78	193.59	16.732	234.882	191.423	18.209
5	804	66.05	91.784	953.5	775.5	18.668	926	760	17.927
10	7302	601	91.769	8474	7050	16.804	8449	7063	16.404
15	29296	2409	91.777	34367	28281	17.708	33926	28505	15.978
20	82982	6755	91.859	96849	80168	17.224	95586	80.199	16.098

续表１

矩的

阶数	图１(d)			图１(e)			图１(f)
	Eq. (3)	Eq(10)	rate (%)	Eq. (3)	Eq(10)	rate (%)	Eq. (3)	Eq(10)	rate (%)
3	231.05	174.6	24.545	922.46	705.44	23.082	3754.63	3326.15	11.752
5	932	697	25.161	3691	2783	24.6	15085	13274	12.005
10	8469	6369	24.796	33655	25684	23.684	136209	119680	12.135
15	34231	25409	25.772	135612	102431	24.468	540335	462515	14.402
20	96326	71491	25.782	382793	2235	24.441	1520159	1307123	14.014

从表１可以发现，对于一般的二值图像，本文提出的算法的计算速度与直接算法相比要快91%左右，对于包含中等程度细节的灰度图像，其计算速度可提高25%左右，对于包含大量细节的大尺寸灰度图像(如图e)，其计算性能比直接算法要高出24％。相比之下，该算法对包含灰度值有大量细小变化的灰度图像的计算速度提高不多，如上图(b,c,f),仅15%左右。这是因为本文提出的算法是基于图像块进行计算的，因此，图像自身分块的多少及每个图像块的大小对算法的整体运算性能有较大的影响。下表２给出了图1中６幅图像的经PIBR算法

表２PIBR算法对图像的分块及时间开销

图像类型	分块时间(单位：ms)	图像像素个数	块的数量	块的数量相对像素数量减少的比率	图像中不同灰度值的数量
图1(a)	0.58865	14400	1219	91.53472	2
图1(b)	3.34028	16384	13997	14.56909	212
图1(c)	3.35071	16384	14048	14.25781	233
图1(d)	3.26107	16384	12809	21.82007	248
图1(e)	12.93376	65536	51188	21.331	175
图1(f)	55.42308	262144	230049	12.24327	254

处理后得到的图像块数及分块所花费的时间。从表2可以看出，整个图像经PIBR算法处理后，若包含的图像快越少，且单个图像块包含的像素个数，则计算速度越快，如图像1(a)，该类图像的一个很大的特点就是很方便实用PIBR算法分成较大的图像块，最好情况下比如整个图像只有一个灰度值，则PIBR算法计算后只包含一个图像块，其计算速度最快。最坏情况下比如棋盘类型的图像，这类图像中每个块只包含一个像素，此时采用本文提出的算法和直接算法计算性能一样。

5 结论

Legendre矩的精确快速计算是图像分析中的矩技术的一个重要研究内容。本文提出一种快速精确计算灰度图像Legendre矩算法，算法建立在文献[15]的基础上，采用PIBR算法对图像进行分块，通过将图像块作为一个整体而非单个图像像素积分运算计算图像的Legendre矩，从而达到降低计算复杂度的目的。虽然本文提出的算法的计算性能优于直接算法，但其在计算连续高阶矩值时的计算量仍较大，这并不适用于图像重建等应用。由于公式(13)的计算于图像，因此在图像分块处理后，可将其进行预先计算，并将其放在一个查找表中，以备后续计算使用，避免重复计算，则可在保证计算精度的前提下，进一步提高高阶连续Legendre矩的计算性能。

参考文献

1 Hu M K. Visual pattern recognition by moment invariants [J]. IRE Trans Inform Theory, 1962, 8(2):179～187

2 TEAGUE M R. Image analysis via the general theory of moments [J]. Journal of Optimal Society of American, 1980, 70(8):920-930

3 Teh C H, Chin R T. On image analysis by the methods of moments[J]. IEEE Trans Pattern Anal Machine Intell, 1988, 10(4):496-513

4 Chee-Way Chong, P. Raveendran, R. Mukundan. Translation and scale invariants of Legendre moments. Pattern Recognition, 2004, 37(1): 119-129

5 Wee, C.-Y.   Paramesran, R.  Derivation of blur-invariant features using orthogonal Legendre moments. IET Computer Vision, 1(2): 66-77

6 Shen, J., Shen, D., Orthogonal Legendre Moments and Their Calculation, ICPR96 (II: 241-245)

7 Liao S X Pawlak M · on image analysis by moments · IEEE Transactions on Pattern Analysis 

and Machine Intelligence, 1996/18/03 P254-266 

8 Mukandan R, Ramakrishnan K R. Fast computation of Legendre and Zernike moments. Pattern 

Recognition, 1995, 28(9): 1433-1442

9 H.Z. Shu, L.M. Luo, W.X. Yu and Y. Fu, A new fast method for computing Legendre moments, 

Pattern Recognition 33 (2000) (2), 341–348

10 GY Yang, HZ Shu, C Toumoulin, GN Han, LM Luo, Efficient Legendre moment computation 

for grey level images, Pattern Recognition,(2006) vol. 39(1):74-80

11 秦磊，舒华忠，於文雪，金丰华，C.Toumoulin，罗立民,Legendre矩的两种快速算法,电

子学报，32(1):25-28, 2004

12 Zhou J D, Shu H Z.Two new algorithms for efficient computation of Legendre moments [J]. 

Pattern Recognition, 2002, 35:1143-1152

13 Papakostas, G.A. Karakasis, E.G. Koulouriotis Exact and Speedy Computation of Legendre 

Moments on Binary Images, Eighth International Workshop on Image Analysis for Multimedia 

Interactive Services, 2007. WIAMIS '07. pp 48-51

14 EE, Khalid M. Hosny: Exact Legendre moment computation for gray level images. Pattern 

Recognition 40(12): 3597-3605 (2007)

15 Yap PT, Raveendran P. An efficient method for the computation of Legendre moments. IEEE 

Trans Pattern Anal Machine Intell. 2005; 27(12):1996–2002

16 G. A. Papakostas, E. G. Karakasis, D. E. Koulouriotis. Efficient and accurate computation of 

geometric moments on gray-scale images. Pattern Recognition, 2008, 41(6):15-1904