【摘要】针对三角形子模式的不足，使用正方形作为NAM表示模型的预定义子模式，提出了一种新的灰度图像表示方法。从单个子模式需记录的参数、算法时间复杂度、编码产生的总数据量等方面进行了理论分析，实验表明：与灰度图像的TNAMG表示方法和LQT表示方法相比，本文方法能够显著减少目标块记录的数量并节省数据存储空间，是一种高效、紧凑的灰度图像表示方法。 【关键词】正方形子模式NAM灰度图像表示方法 一、引言 图像是人类最直接的、最主要的信息源，随着互联网的发展，多媒体应用也日益增多，由于图像和视频本身的数据量非常大，给存储和传输带来了很多不便，因而如何高效、实时地表示图像成为了多媒体技术中的一个研究热点[1，2]。图像表示方法应能够有效的节省存储空间并具备高效的运算方式，支持图像压缩、特征提取、复原等各种处理过程[3]。最早得到普遍应用的二维数组表示方法难以在节省空间和加快算法速度方面做出进一步的改进。因此，边界链码、行程编码等多种图像表示方法先后被提出[4-6]。同等条件下与二维数组表示法相比，这些方法占用的存储空间更少，但其本质特点也使其在支撑某些图像操作时出现问题[4，5]。如图像的边界链码表示难以实现区域逻辑运算，行程编码表示则会弱化边界特征。随后，依据图像自身的二维相关性，人们采用树形结构实现分层的表示图像，并给出了一些可行的方法，如四元树、线性四元树、DF-expression、S-tree、二元树及Bincodes等图像表示方法[6-9]。这类方法显著减少了冗余，保留了图像的块状纹理特征，而且经层次数据结构表示后，图像运算可在“块-块”的模式下进行[10]，其过程最终可表征为对树形数据结构的节点遍历，使算法的计算总量与具有同一灰度级的图像块数量成线性关系，时间复杂度得到降低，因此能够有效支撑各类图像处理过程，提高算法效率。其中，Gargantini提出的线性四元树（Linear Quadtree，LQT）表示方法[9]是目前得到最为广泛研究和应用的图像分层表示方法。 二、基于SNAMG的灰度图像表示算法描述 灰度图像中不同像素点可能会有多种灰度值，故其匹配、记录过程必须将像素和子模式的灰度值纳入考虑。因此SNAMG表示方法的原理可表述如下：预定义一个灰度正方形子模式框架，然后使用逆布局算法在给定的灰度图像模式中提取出不同大小和灰度的正方形子模式，再用这些子模式的记录组合来表示该给定灰度图像。 根据上述所得出的SNAMG表示方法的抽象算法描述如下： 设原始模式为祝，重建后的非失真模式为祝’，则SNAMG是由到的一个非失真变换： 祝’=W（祝）（1） 其中，W（）是正向变换函数，或称为编码函数。 正向编码过程为 三、实验结果及分析 为了验证基于SNAMG的灰度图像表示算法的有效性，本文从实际的角度进行将其与基于TNAMG的灰度图像表示算法[13]和基于LQT的灰度图像表示算法[11]进行了比较。图1是用来测试的4幅大小均为28×28、位深均为8的经典灰度图像，为体现算法在不同情况下的性能，这些图像的复杂度均不相同，可以间接反映灰度图像的SNAMG表示算法的适应性。另外，由于主要是和LQT表示方法进行对比，本实验中计算图像复杂度的仍然依据LQT的块数来计算的。 对4幅图像进行仿真编码的结果，具体数据如表1所示，表中的参数Image：灰度图像的名称；Cg：灰度图像的复杂度；N：子模式或节点的数量；浊：压缩比；鬃LQT_T：LQT与TNAMG的总数据量之比；鬃LQT_S：LQT与SNAMG的总数据量之比。 从表中Cg的值可以看出，Building的复杂度最低，Flower的居中，Flight和Peppers的复杂度最高。表中N的数值表明SNAMG、TNAMG表示逆布局后的子模式数量比LQT表示的节点数少得多，且作用于不同图像产生的子模式数量与图像复杂度对应，说明SNAMG和TNAMG具有很好的适应性。而且SNAMG的子模式数量比TNAMG的子模式还要少1056～4693个，故SNAMG在降低目标块记录数量方面要优于TNAMG。最后，可通过表 中鬃LQT_T和鬃LQT_S数据比较一下SNAMG、TNAMG和LQT 这三种表示方法编码后的总的数据量。对于测试的4幅图像，LQT的总数据量是TNAMG表示的1.758～3.2119倍，是SNAMG表示的2.1102～4.8810倍，即TNAMG、SNAMG的编码结果占用空间均比LQT少，且SNAMG比TNAMG还能再节省14.45%～34.20%的存储空间。这说明 SNAMG对灰度图像的表示能力总是优于TNAMG对灰度图像的表示能力，且能够比TNAMG更有效地节省数据存储空间。实验数据表明：在用于灰度图像表示时，本文提出的SNAMG表示方法性能优于TNAMG表示方法和LQT表示方法，空间紧凑性更好。 四、小结 本文借助于正方形布局问题的思想，提出了基于SNAMG的灰度图像表示方法，并给出了编码、解码算法的具体步骤。并通过使用标准‘Building和‘Peppers’等4幅图像处理领域里惯用的经典图像为典型测试对象进行仿真，实验结果与理论分析结果一致。因此，灰度图像的SNAMG表示方法是一种更为高效、紧凑的表示方法，在节省存储空间和加快图像处理操作方面具有较高的实用价值。 参考文献 [1] W. Liu， W. Zeng， L. Dong. Efficient compression of encrypted grayscale images [J]. IEEE Transactions on Image Processing， 2010， 19（4）： 1097- 1102. [2] S. Alcaraz-Corona， R.M. Rodriguez-Dagnino. Bi-level image compression estimating the markov order of dependencies [J]. IEEE Journal of Selected Topics in Signal Processing， 2010， 4（3）： 605- 611. [3] Jie He， Yunping Zheng， Hui Guo. A Square NAM Representation Method for Binary Images [J]. Applied Mechanics and Materials Jounral，2011，（143-144）：755-759. [4]郑运平，陈传波，黄巍等.一种改进的TNAM灰度图像表示算法研究[J].小型微型计算机系统， 2009， 30（2）： 322-326. [5]方少红，郑运平，陈传波[J].改进的TNAM二值图像表示方法.计算机科学， 2010， 37 （4）： 261- 264.
【摘要】针对三角形子模式的不足，使用正方形作为NAM表示模型的预定义子模式，提出了一种新的灰度图像表示方法。从单个子模式需记录的参数、算法时间复杂度、编码产生的总数据量等方面进行了理论分析，实验表明：与灰度图像的TNAMG表示方法和LQT表示方法相比，本文方法能够显著减少目标块记录的数量并节省数据存储空间，是一种高效、紧凑的灰度图像表示方法。 【关键词】正方形子模式NAM灰度图像表示方法 一、引言 图像是人类最直接的、最主要的信息源，随着互联网的发展，多媒体应用也日益增多，由于图像和视频本身的数据量非常大，给存储和传输带来了很多不便，因而如何高效、实时地表示图像成为了多媒体技术中的一个研究热点[1，2]。图像表示方法应能够有效的节省存储空间并具备高效的运算方式，支持图像压缩、特征提取、复原等各种处理过程[3]。最早得到普遍应用的二维数组表示方法难以在节省空间和加快算法速度方面做出进一步的改进。因此，边界链码、行程编码等多种图像表示方法先后被提出[4-6]。同等条件下与二维数组表示法相比，这些方法占用的存储空间更少，但其本质特点也使其在支撑某些图像操作时出现问题[4，5]。如图像的边界链码表示难以实现区域逻辑运算，行程编码表示则会弱化边界特征。随后，依据图像自身的二维相关性，人们采用树形结构实现分层的表示图像，并给出了一些可行的方法，如四元树、线性四元树、DF-expression、S-tree、二元树及Bincodes等图像表示方法[6-9]。这类方法显著减少了冗余，保留了图像的块状纹理特征，而且经层次数据结构表示后，图像运算可在“块-块”的模式下进行[10]，其过程最终可表征为对树形数据结构的节点遍历，使算法的计算总量与具有同一灰度级的图像块数量成线性关系，时间复杂度得到降低，因此能够有效支撑各类图像处理过程，提高算法效率。其中，Gargantini提出的线性四元树（Linear Quadtree，LQT）表示方法[9]是目前得到最为广泛研究和应用的图像分层表示方法。 二、基于SNAMG的灰度图像表示算法描述 灰度图像中不同像素点可能会有多种灰度值，故其匹配、记录过程必须将像素和子模式的灰度值纳入考虑。因此SNAMG表示方法的原理可表述如下：预定义一个灰度正方形子模式框架，然后使用逆布局算法在给定的灰度图像模式中提取出不同大小和灰度的正方形子模式，再用这些子模式的记录组合来表示该给定灰度图像。 根据上述所得出的SNAMG表示方法的抽象算法描述如下： 设原始模式为祝，重建后的非失真模式为祝’，则SNAMG是由到的一个非失真变换： 祝’=W（祝）（1） 其中，W（）是正向变换函数，或称为编码函数。 正向编码过程为 三、实验结果及分析 为了验证基于SNAMG的灰度图像表示算法的有效性，本文从实际的角度进行将其与基于TNAMG的灰度图像表示算法[13]和基于LQT的灰度图像表示算法[11]进行了比较。图1是用来测试的4幅大小均为28×28、位深均为8的经典灰度图像，为体现算法在不同情况下的性能，这些图像的复杂度均不相同，可以间接反映灰度图像的SNAMG表示算法的适应性。另外，由于主要是和LQT表示方法进行对比，本实验中计算图像复杂度的仍然依据LQT的块数来计算的。 对4幅图像进行仿真编码的结果，具体数据如表1所示，表中的参数Image：灰度图像的名称；Cg：灰度图像的复杂度；N：子模式或节点的数量；浊：压缩比；鬃LQT_T：LQT与TNAMG的总数据量之比；鬃LQT_S：LQT与SNAMG的总数据量之比。 从表中Cg的值可以看出，Building的复杂度最低，Flower的居中，Flight和Peppers的复杂度最高。表中N的数值表明SNAMG、TNAMG表示逆布局后的子模式数量比LQT表示的节点数少得多，且作用于不同图像产生的子模式数量与图像复杂度对应，说明SNAMG和TNAMG具有很好的适应性。而且SNAMG的子模式数量比TNAMG的子模式还要少1056～4693个，故SNAMG在降低目标块记录数量方面要优于TNAMG。最后，可通过表 中鬃LQT_T和鬃LQT_S数据比较一下SNAMG、TNAMG和LQT 这三种表示方法编码后的总的数据量。对于测试的4幅图像，LQT的总数据量是TNAMG表示的1.758～3.2119倍，是SNAMG表示的2.1102～4.8810倍，即TNAMG、SNAMG的编码结果占用空间均比LQT少，且SNAMG比TNAMG还能再节省14.45%～34.20%的存储空间。这说明 SNAMG对灰度图像的表示能力总是优于TNAMG对灰度图像的表示能力，且能够比TNAMG更有效地节省数据存储空间。实验数据表明：在用于灰度图像表示时，本文提出的SNAMG表示方法性能优于TNAMG表示方法和LQT表示方法，空间紧凑性更好。 四、小结 本文借助于正方形布局问题的思想，提出了基于SNAMG的灰度图像表示方法，并给出了编码、解码算法的具体步骤。并通过使用标准‘Building和‘Peppers’等4幅图像处理领域里惯用的经典图像为典型测试对象进行仿真，实验结果与理论分析结果一致。因此，灰度图像的SNAMG表示方法是一种更为高效、紧凑的表示方法，在节省存储空间和加快图像处理操作方面具有较高的实用价值。 参考文献 [1] W. Liu， W. Zeng， L. Dong. Efficient compression of encrypted grayscale images [J]. IEEE Transactions on Image Processing， 2010， 19（4）： 1097- 1102. [2] S. Alcaraz-Corona， R.M. Rodriguez-Dagnino. Bi-level image compression estimating the markov order of dependencies [J]. IEEE Journal of Selected Topics in Signal Processing， 2010， 4（3）： 605- 611. [3] Jie He， Yunping Zheng， Hui Guo. A Square NAM Representation Method for Binary Images [J]. Applied Mechanics and Materials Jounral，2011，（143-144）：755-759. [4]郑运平，陈传波，黄巍等.一种改进的TNAM灰度图像表示算法研究[J].小型微型计算机系统， 2009， 30（2）： 322-326. [5]方少红，郑运平，陈传波[J].改进的TNAM二值图像表示方法.计算机科学， 2010， 37 （4）： 261- 264.