一种基于可重叠矩形子模式的NAM图像表示方法

摘要

本发明公开了一种基于可重叠矩形子模式的NAM图像表示方法，包括编码过程和解码过程，编码过程主要是利用扩展的Gouraud阴影法和可重叠矩形NAM的4个准则，将灰度图像矩阵分割为可相互重叠的同类块；再对所有同类块进行编码，获取其颜色表P和坐标表Q，解码过程主要是根据坐标表Q，解码出坐标矩阵H、V和I，再根据H、V和I和颜色表P，利用扩展的Gouraud阴影法重建解码图像，并计算其PSNR。本发明在保证图像质量的前提下，具有更低的比特率和更少的块数，从而具有更快的处理速度；不仅可应用于传统的JPEG市场，而且还可应用于新兴领域，如无线通讯、网路传输、医疗图像等。

说明书

技术领域

本发明涉及计算机图像处理，特别涉及一种基于可重叠矩形子模式的非对 称逆布局模型(NAM)图像表示方法。

背景技术

图像表示是计算机图形学、计算机视觉、机器人、图像处理和模式识别等 领域里的一个重要问题。有效的图像表示方法不仅能节省存储空间，而且还能 提高图像处理的速度。图像表示是目前最活跃的研究领域之一。就二值图像的 表示方法而言，有码字集表示方法、字符串表示方法及树结构的表示方法等， 然而这些表示方法均是基于空间数据结构的。不同于空间数据结构的表示方法， Mohamed提出了一种基于非重叠矩形的二值图像表示方法(Mohamed SA， Fahmy MM.Binary image compression using efficient partitioning into rectangular  regions.IEEE Transactions on Communications，1995，43(5)：1888-1892)，并将这种 表示方法有效地应用到二值图像的压缩中，取得了较好的效果。后来，Quddus 对Mohamed的这一方法作了进一步的研究，提出了一种基于可重叠矩形的二值 图像表示方法(Quddus A，Fahmy  MM.Binary text image compression using overlapping rectangular partitioning.atter  Recognition Letters，1999，20(2)：81-88)，其实验结果表明使用可重叠矩形进行划 分所得到的矩形的总数总是少于使用非重叠矩形进行划分所得到的矩形的总 数。Quddus将这种表示方法成功应用到对文本图像的压缩中，获得了比Mohamed 更好的实验结果。对于一幅二值图像而言，与非重叠矩形划分相比，可重叠矩 形划分总能够获得更高的表示效率(Quddus A，Fahmy  MM.Binary text image compression using overlapping rectangular partitioning. Pattern Recognition Letters，1999，20(2)：81-88)。

然而，由于实际中的图像大多是灰度图像，所以对灰度图像表示方法的研 究具有更为广泛的用途和实际的意义。基于B-树三角形编码(BTTC)方法，Distasi 等人首次提出了基于空间数据结构的灰度图像表示算法(R. Distasi，M.Nappi，S. Vitulano.Image compression by B-tree triangular coding.IEEE Transactions on  Communications，1997，45(9)：1095-1100)。由于Distasi首次将空间数据结构的设 计从二值图像的表示扩展到了灰度图像的表示上来，因此基于BTTC的空间数 据结构的灰度图像表示确实是一个先驱性的工作。后来，基于S树数据结构(W. D.Jonge，P.Scheuermann，A.Schijf.S+-Trees：An efficient structure for the  representation of large pictures.Computer Vision and Image Understanding，1994， 59(3)：265-280)和Gouraud阴影法(J.D.Foley，A.V.Dam，S.K.Feiner，et al. Computer Graphics，Principle，and Practice，second ed.Reading，MA： Addision-Wesley，1990)，Chung等(K.Chung，J.Wu.Improved image compression  using S-tree and shading approach.IEEE Transactions on Communications，2000， 48(5)：748-751)提出了一种基于S树的空间数据结构的灰度图像表示(STC)方法。 STC方法的实验结果表明：在保持图像质量和不牺牲图像压缩比的情况下，STC 方法比BTTC方法的执行时间至少要少一半。随后，Chung等提出了一种基于 DCT域和空域的混合灰度图像表示方法，简称为SDCT表示方法(Chung KL，Liu  YW，Yan WM.A hybrid gray image representation using spatial-and DCT-based  approach with application to moment computation.Journal of Visual Communication  and Image Representation，2006，17(6)：1209-1226)。其实验结果表明：在保持图像 质量的前提下，SDCT表示方法在压缩比提高率方面比STC表示方法平均提高 了63.08％，是一种有效的灰度图像表示方法。然而由于SDCT表示方法的编解 码时间复杂度是相同的，且是高于STC表示方法的。因此，相对于STC表示方 法，SDCT表示获得的较高的压缩比是以牺牲算法的编解码时间复杂度为代价 的。

尽管上述的空间数据结构表示有许多优点，但是它们过于强调分割的对称 性，因此不是最优的表示方法。借助于Packing问题的思想，以寻找分割最大化 的非对称分割方法为目标，本发明人曾提出了一种基于矩形子模式的非对称逆 布局模型(NAM)的彩色图像表示方法(郑运平，陈传波.一种基于非对称逆布局 模型的彩色图像表示方法.软件学报，2007，18(11)：2932-2941)，这种表示方法的基 本思想是：给定一个已经布局好了的模式和一个预先定义的不同形状的矩形子 模式，然后从这个给定的模式中抽出互不重叠的矩形子模式，用这些矩形子模 式的组合来表示给定的模式。然而该文提出的基于矩形NAM的彩色图像表示方 法的是图像的一种无损表示方法，并不适合图像的有损表示。后来，为了更有 效地对图像进行表示和压缩，本发明人借助于BTTC和STC灰度图像表示算法 的思想，提出了一种新的灰度图像表示算法，简称为RNAMC表示算法(郑运 平，陈传波.一种新的灰度图像表示算法研究.计算机学报， 2010，33(12)：2397-2406)。在RNAMC表示算法中，由于逆布局结果是非重叠的， 因此只需给定左上、右下及孤立块的码字，即可得到一个标识顶点类型的矩阵R， 在矩阵R中，符号“1”和“2”分别用来标识矩形的左上角和右下角，符号“-1”仅 用来标识孤立点矩形。RNAMC表示算法逆布局后的互不重叠的同类块具有如下 特点，即：如果以光栅扫描的方式扫描矩阵R，每一个矩形的左上顶点和右下顶 点在列方向上是最近的。只要原始图像被分割后的矩形互不重叠，矩阵R就是 可以解码的。因此在RNAMC表示算法中，只能将原始图像逆布局为互不重叠 的同类块，否则该算法是无法解码的。该算法的复杂度与BTTC和STC的复杂 度是一样的，即：编解码部分的时间复杂度分别为O(m log m)和O(m)，其中m 为灰度图像的像素数。实验结果表明：与流行的STC和SDCT表示方法相比， 在保持图像质量的前提下，RNAMC表示算法具有更高的压缩比和更少的块数， 因而能够更有效地减少数据存储空间，是灰度图像表示的一种良好方法。但在 RNAMC表示算法中，子模式是不允许重叠的，而可重叠矩形划分能够获得比非 重叠矩形划分更高的表示效率，因此，需要提供一种基于可重叠矩形子模式的 NAM图像表示方法。

发明内容

本发明的目的在于克服上述现有技术的缺点和不足，提供一种基于可重叠 矩形子模式的NAM图像表示方法，能够更有效地提高图像表示时的压缩比及降 低图像表示时的同类块总数，进一步提高图像模式的表示和操作效率。

本发明的目的通过以下技术方案实现：

一种基于可重叠矩形子模式的NAM图像表示方法，包括编码过程和解码过 程，

所述编码过程包括以下步骤：

S1将灰度图像矩阵G分割为可重叠的同类块，具体包括以下步骤：

S1.1定义同类块为满足下述条件的矩形子模式：该矩形子模式内所有像素 的灰度值g(x，y)均满足条件|g(x，y)-g_est(x，y)|≤ε；其中，ε为用户设定的误差允许 量；g_est(x，y)表示该矩形子模式中坐标(x，y)处的近似灰度值，其定义如下：设(x₁， y₁)、(x₂，y₂)分别为该矩形子模式左上角和右下角的坐标值，x₁≤x≤x₂，y₁≤y≤y₂；

如果x₁＜x₂且y₁＜y₂，则g_est(x，y)＝g₅+(g₆-g₅)×i₁，

如果x₁≠x₂且y₁＝y₂，则g_est(x，y)＝g₁+(g₄-g₁)×[(x-x₁)/(x₂-x₁)]；

如果x₁＝x₂且y₁≠y₂，则g_est(x，y)＝g₁+(g₄-g₁)×[(y-y₁)/(y₂-y₁)]；

如果x₁＝x₂且y₁＝y₂，则g_est(x，y)＝g₁；

其中g₁、g₂、g₃、g₄分别为该矩形子模式的左上角、右下角、左下角、 右上角的灰度值；g₅＝g₁+(g₂-g₁)×i₂，g₆＝g₃+(g₄-g₃)×i₂，i₁＝(y-y₁)/(y₂-y₁)， i₂＝(x-x₁)/(x₂-x₁)；

定义3个大小均为M×N的水平块矩阵H、垂直块矩阵V和单点块矩阵I， 其中，H、V和I中所有元素均初始化为0；将同类块的计数变量n赋值为0；其 中，M和N均为自然数；

S1.2扫描同类块：

S1.2.1定义2个大小均为M×N的临时矩阵：TempH和TempV，分别用于标 识在扫描过程中水平块和垂直块的分配情况；TempH和TempV中的所有元素均 初始化为0；

S1.2.2从灰度图像矩阵G左上角的第一点开始扫描，根据光栅扫描的顺序 确定一个未被标识的同类块的起始点(x₁，y₁)，按顺序对横坐标和纵坐标进行扫 描，根据扩展的Gouraud阴影法确定出同类块右下角的坐标(x₂，y₂)，得到面积最 大的同类块(即该同类块所包含的像素数目最多)，并将此同类块在灰度图像矩 阵G中作标识；

在扫描过程中遵循以下准则：

若扫描时确定的面积最大的同类块在TempH中对应的位置的值为0，则将 TempH中该同类块对应的位置的值置为1；

若扫描时遇到的同类块在TempH中对应位置的值为1，即该同类块为水平 块且还未重叠过，则先搜索该同类块的左上角的坐标(x₁，y₁)和右下角的坐标(x₂， y₂)再将其变为垂直块；所述变为垂直块的方法为：先将该同类块在TempH中对 应位置的值置为0，在TempV中对应位置的值置为1，再将该同类块在矩阵H 中对应点(x₁，y₁)和点(x₂，y₂)的值分别置为0，在V矩阵中对应点(x₁，y₁)的值置为1、 对应点(x₂，y₂)的值为2；同时扫描过程继续进行，当次扫描结束后将得到的面积 最大的同类块在TempH中对应位置的值置为2；

若扫描时遇到的同类块在TempV中对应位置的值为1，则继续扫描，将当 次扫描结束后得到的面积最大的同类块在TempH中对应位置的值置为2；

若扫描时遇到的同类块在TempH中对应位置值为2，即该同类块为水平块 且还重叠过，则此时扫描结束，此次扫描得到的同类块即为面积最大的同类块；

S1.3将n的值加1，并记录步骤S1.2得到的面积最大的同类块的参数：左 上角的坐标(x₁，y₁)、右下角的坐标(x₂，y₂)、以及4个角的灰度值g₁、g₂、g₃、g₄；

S1.4将步骤S1.3所述的参数存储到颜色表P中，并对矩阵H、I中对应点 (x₁，y₁)、点(x₂，y₂)的位置进行标识；

S1.5判断灰度图像矩阵G中的同类块是否全部被识别完毕；

若是，进行步骤S1.6；

若否，重复步骤S1.2～S1.5；

S1.6输出颜色表P；

S2根据坐标数据压缩算法，按H、V、I的顺序依次对3个矩阵中所有非零 元素的坐标进行编码，将编码结果存储到一个坐标表Q中；

所述解码具体为：根据坐标表Q，解码出矩阵H、V和I，根据H、V、I和 颜色表P，利用扩展的Gouraud方法重建解码图像。

步骤S1.2中所述扫描过程根据行优先扫描的策略，具体为：

在扫描过程中先单独令横坐标X不断增加，直至扫描到灰度值g(x，y)满足 |g(x，y)-g_est(x，y)|＞ε的点为止，再单独令纵坐标Y不断增加，直至扫描到灰度值 g(x，y)满足|g(x，y)-g_est(x，y)|＞ε的点为止。

步骤S1.2中所述扫描过程根据列优先扫描的策略，具体为：

在扫描过程中先单独令纵坐标Y不断增加，直到扫描到灰度值g(x，y)满足 |g(x，y)-g_est(x，y)|＞ε的点为止，再单独令横坐标X不断增加，扫描到灰度值g(x，y) 满足|g(x，y)-g_est(x，y)|＞ε的点为止。

步骤S1.4所述将步骤S1.3所述的参数存储到颜色表P中，并对矩阵H、I 中对应点(x₁，y₁)、点(x₂，y₂)的位置进行标识，具体为：

如果x₁＜x₂且y₁＜y₂，则将参数g₁、g₂、g₃、g₄存储到颜色表P中，即： P{n}←{(g₁，g₂，g₃，g₄)}，并将矩阵H中对应点(x₁，y₁)、点(x₂，y₂)的位置分别用‘1’ 和‘2’进行标识；

如果x₁＝x₂且y₁≠y₂，则将参数g₁，g₄存储到颜色表P中，即：P{n}←{(g₁，g₄)}， 并将矩阵H中对应点(x₁，y₁)、点(x₂，y₂)的位置分别用‘1’和‘2’进行标识；

如果x₁≠x₂且y₁＝y₂，则将参数g₁、g₄存储到颜色表P中，即：P{n}←{(g₁， g₄)}，并将矩阵H中对应点(x₁，y₁)、点(x₂，y₂)的位置分别用‘1’和‘2’进行标 识；

如果x₁＝x₂且y₁＝y₂，则将g₁存储到颜色表P中，即：P{n}←{(g₁)}，并将 矩阵I中对应点(x₁，y₁)的位置用‘1’进行标识。

步骤S2根据坐标数据压缩算法，按H、V、I的顺序，对每个矩阵中所有非 零元素的坐标进行编码，具体为：

逐行扫描大小为M×N的矩阵，如果当前行所有元素均为零，使用一个二进 制位‘0’来表示该行从头到尾都不存在非零元素，不对该行进行编码；如果该行 存在非零元素，则在每一个非零元素前加一个前缀符‘1’，然后在前缀符后加上 用以标识非零元素1和2的码字，并用b个比特来表示每个非零元素所在列的 位置；当该行的最后一个元素为零，则在最后一个非零元素编码完成后，用一 个二进制位‘0’来表示本行剩余的元素均为零。

所述用b个比特来表示每个非零元素所在列的位置，具体为：

若非零元素为所在行的第一个非零元素，则b＝[log₂N]；此时的b个比特用 来指明第一个非零元素关于所在行首端的位置；

若非零元素不是所在行的第一个非零元素，则b＝[log₂(N-c)]，其中c是前一 次编码的非零元素的列的位置；此时的b个比特用来表示这个非零元素关于前 一次编码的非零元素的右端的位置。

所述根据坐标表Q，解码出矩阵H、V和I，根据H、V、I和颜色表P，利 用扩展的Gouraud方法重建解码图像，具体为：

S3.1将一个大小为M×N的矩阵g_est的所有元素赋任意初值，并将同类块的 计数变量n赋值为0；

S3.2根据坐标表Q，按H、V、I的顺序依次解码出3个大小为M×N的H、 V和I矩阵；

S3.3根据颜色表P，给出同类块的总数s；

S3.4同时扫描H、V和I矩阵，若扫描到值为1的像素，则根据P{n}，判 断该同类块的类型并获取其灰度值；

S3.5根据同类块的类型，利用扩展的Gouraud阴影法计算该同类块的所有 g_est(x，y)，其中g_est(x，y)表示该同类块中坐标(x，y)处的近似灰度值；

S3.6按光栅扫描的顺序将该同类块的解码结果赋值给矩阵g_est；

S3.7令n加1，并判断此时是否满足n＜s，若是，重复步骤S3.4～S3.7；若 否，进行步骤S3.8；

S3.8根据矩阵g_est输出灰度图像，并根据如下公式计算峰值信噪比PSNR：

$\mathrm{PSNR}=10{\log }_{10}\left(\frac{{255}^2\times M\times N}{\underset{x=0}{\overset{M-1}{\Sigma }}\underset{y=0}{\overset{N-1}{\Sigma }}{[G(x,y)-g_{\mathrm{est}}(x,y)]}^2}\right).$

本发明借助于二值图像的可重叠矩形区域编码的思想，提供了一种基于可 重叠矩形子模式的NAM图像表示方法，简称为ORNAMC表示方法。本发明包 括编码和解码过程，其中编码过程主要是利用扩展的Gouraud阴影法和可重叠 矩形NAM的4个准则，将灰度图像矩阵分割为可相互重叠的同类块；再对所有 同类块进行编码，获取其颜色表P和坐标表Q，解码过程主要是根据坐标表Q， 解码出坐标矩阵H、V和I，再根据H、V和I和颜色表P，利用扩展的Gouraud 阴影法重建解码图像，并计算其PSNR。

与现有技术相比，本发明具有以下优点和有益效果：

1、与目前流行STC方法相比，具有更少的块数，在保证图像质量的前提下， 其同类块的数目平均下降了31.31％，从而具有更快的图像处理速度。

2、与流行的基于STC表示的矩计算算法的复杂度进行比较，理论分析表明 基于ORNAMC表示方法的矩计算算法的复杂度是低于STC表示的矩计算算法 的复杂度的，仅为O(n)，此处n为灰度图像用ORNAMC表示时的同类块的数 目，因而ORNAMC表示具有更快的计算速度。

3、与已经商业化了JPEG方法相比，具有更低的比特率和更快的编解码速 度，其编解码复杂度仅为O(m log m)和O(m)，此处m为灰度图像的像素数。 ORNAMC表示方法在保持图像质量的前提下，在压缩比提高率方面比STC表 示方法平均提高了91.84％。

4、与RNAMC方法相比，在保持图像质量的前提下，ORNAMC表示方法 具有更少的子模式数和比特率，因而能够更有效的提高图像表示和操作的效率。

5、本发明不仅可应用于传统的JPEG市场，如打印机、扫描仪、数码相机 等，而且还可应用于新兴领域，如无线通讯、网路传输、医疗图像等。

附图说明

图1为编码过程的示意图。

图2为同类块的示意图。

图3为灰度图像矩阵G的示意图。

图4为标识后的水平块矩阵H。

图5为标识后的垂直块矩阵V。

图6为标识后的单点块矩阵I。

图7为解码过程的示意图。

具体实施方式

下面结合实施例及附图，对本发明作进一步地详细说明，但本发明的实施 方式不限于此。

实施例

本发明一种基于可重叠矩形子模式的NAM图像表示方法，包括编码过程和 解码过程：

如图1所示，编码过程包括以下步骤：

S1将灰度图像矩阵G分割为可重叠的同类块，具体包括以下步骤：

S1.1定义同类块为满足下述条件的矩形子模式：该矩形子模式内所有像素 的灰度值g(x，y)均满足条件|g(x，y)-g_est(x，y)|≤ε；其中，ε为用户设定的误差允许 量；g_est(x，y)表示该矩形子模式中坐标(x，y)处的近似灰度值，其定义如下：设(x₁， y₁)、(x₂，y₂)分别为该矩形子模式左上角和右下角的坐标值，x₁≤x≤x₂，y₁≤y≤y₂；

如果x₁＜x₂且y₁＜y₂，则g_est(x，y)＝g₅+(g₆-g₅)×i₁，

如果x₁≠x₂且y₁＝y₂，则g_est(x，y)＝g₁+(g₄-g₁)×[(x-x₁)/(x₂-x₁)]；

如果x₁＝x₂且y₁≠y₂，则g_est(x，y)＝g₁+(g₄-g₁)×[(y-y₁)/(y₂-y₁)]；

如果x₁＝x₂且y₁＝y₂，则g_est(x，y)＝g₁；

其中g₁、g₂、g₃、g₄分别为该矩形子模式的左上角、右上角、左下角、 右下角的灰度值；g₅＝g₁+(g₂-g₁)×i₂，g₆＝g₃+(g₄-g₃)×i₂，i₁＝(y-y₁)/(y₂-y₁)， i₂＝(x-x₁)/(x₂-x₁)；图2为同类块的示意图。

定义3个大小均为M×N的水平块矩阵H、垂直块矩阵V和单点块矩阵I， 其中，H、V和I中所有元素均初始化为0；将同类块的计数变量n赋值为0；其 中，M和N均为自然数。

S1.2扫描同类块：

S1.2.1定义2个大小均为M×N的临时矩阵：TempH和TempV，分别用于标 识在扫描过程中水平块和垂直块的分配情况；TempH和TempV中的所有元素均 初始化为0；

S1.2.2从灰度图像矩阵G左上角的第一点开始扫描，根据光栅扫描的顺序 确定一个未被标识的同类块的起始点(x₁，y₁)，按顺序对横坐标和纵坐标进行扫 描，根据扩展的Gouraud阴影法确定出同类块右下角的坐标(x₂，y₂)，得到面积最 大的同类块，并将此同类块在灰度图像矩阵G中作标识；

扫描时可根据行优先策略或列优先策略，其中行优先策略为：

在扫描过程中先单独令横坐标X不断增加，直至扫描到灰度值g(x，y)满足 |g(x，y)-g_est(x，y)|＞ε的点为止，设该点的横坐标为x，则该点的前一点的横坐标即 为同类块右下角的横坐标x₂；再单独令纵坐标Y不断增加，直至扫描到灰度值 g(x，y)为满足|g(x，y)-g_est(x，y)|＞ε的点为止，设该点的纵坐标为y，则该点的前一 点的横坐标即为同类块右下角的纵坐标y₂。

其中列优先策略为：

在扫描过程中先单独令纵坐标Y不断增加，直至扫描到灰度值g(x，y)满足 |g(x，y)-g_est(x，y)|＞ε的点为止，设该点的纵坐标为y’，则该点的前一点的横坐标即 为同类块右下角的纵坐标y₂；再单独令横坐标X不断增加，直至扫描到灰度值 g(x，y)满足|g(x，y)-g_est(x，y)|＞ε的点为止，设该点的横坐标为x’，则该点的前一点 的横坐标即为同类块右下角的横坐标x₂。

在扫描过程中遵循以下准则：

若扫描时确定的面积最大的同类块在TempH中对应的位置的值为(即没遇 到任何之前的块)，则将TempH中该同类块对应的位置的值置为1；

若扫描时遇到的同类块在TempH中对应位置的值为1，即该同类块为水平 块且还未重叠过，则先搜索该同类块的左上角的坐标(x₁，y₁)和右下角的坐标(x₂， y₂)再将其变为垂直块；所述变为垂直块的方法为：先将该同类块在TempH中对 应位置的值置为0，在TempV中对应位置的值置为1，再将该同类块在矩阵H 中对应点(x₁，y₁)和点(x₂，y₂)的值分别置为0，在V矩阵中对应点(x₁，y₁)的值置为1 和对应点(x₂，y₂)的值为2；同时扫描过程继续进行，当次扫描结束后将得到的面 积最大的同类块在TempH中对应位置的值置为2；

若扫描时遇到的同类块在TempV中对应位置的值为1(即遇到先前的垂直 块)，则开始与该垂直块重叠，并继续扫描，将当次扫描结束后得到的面积最大 的同类块在TempH中对应位置的值置为2；

若扫描时遇到的同类块为水平块且还重叠过，即该同类块在TempH中对应 位置值为2，则不能再次与该水平块重叠，此时扫描结束，此次扫描得到的同类 块即为面积最大的同类块。

S1.3将n的值加1，并记录步骤S1.2得到的最大同类块的参数：左上角的 坐标(x₁，y₁)、右下角的坐标(x₂，y₂)、以及4个角的灰度值g₁、g₂、g₃、g₄；其 中灰度值的具体存储记录用K码表示；

S1.4将步骤S1.3所述的参数存储到颜色表P中，并对矩阵H、I中对应点 (x₁，y₁)、点(x₂，y₂)的位置进行标识(对矩阵V中对应点(x₁，y₁)、点(x₂，y₂)的位置的 标识已在步骤S1.2中完成)，具体为：

如果x₁＜x₂且y₁＜y₂，则将参数g₁、g₂、g₃、g₄存储到颜色表P中，即： P{n}←{(g₁，g₂，g₃，g₄)}，并将矩阵H中对应点(x₁，y₁)、点(x₂，y₂)的位置分别用‘1’ 和‘2’进行标识；

如果x₁＝x₂且y₁≠y₂，则将参数g₁，g₄存储到颜色表P中，即：P{n}←{(g₁，g₄)}， 并将矩阵H中对应点(x₁，y₁)、点(x₂，y₂)的位置分别用‘1’和‘2’进行标识；

如果x₁≠x₂且y₁＝y₂，则将参数g₁，g₄存储到颜色表P中，即：P{n}←{(g₁，g₄)}， 并将矩阵H中对应点(x₁，y₁)、点(x₂，y₂)的位置分别用‘1’和‘2’进行标识；

如果x₁＝x₂且y₁＝y₂，则将g₁存储到颜色表P中，即：P{n}←{(g₁)}，并将 矩阵I中对应点(x₁，y₁)的位置用‘1’进行标识。

以从一幅大小为512×512的F16图像中提取出的大小为16×16的子图像矩 阵(如图3所示)为例，当ε＝20时可以把矩阵分割为可重叠的3类同类块，即： 水平块、垂直块和单点块，且分别在水平块矩阵H、垂直块矩阵V和单点块矩 阵I中用单独的标签来标识不同的同类块及其顶点类型，标识后的水平块矩阵 H、垂直块矩阵V和单点块矩阵I分别如图4、图5、图6(本实施例中无单点块) 所示。

S1.5判断灰度图像矩阵G中的同类块是否全部被识别完毕；

若是，进行步骤S1.6；

若否，重复步骤S1.2～S1.5；

S1.6输出颜色表P；

S2根据坐标数据压缩算法，按H、V、I的顺序依次对3个矩阵中所有非零 元素的坐标进行编码，将编码结果存储到一个坐标表Q中；

所述对每个矩阵中所有非零元素的坐标进行编码，具体为：

逐行扫描大小为M×N的矩阵，如果当前行所有元素均为零，使用一个二进 制位‘0’来表示该行从头到尾都不存在非零元素，不对该行进行编码；如果该行 存在非零元素，则在每一个非零元素前加一个前缀符‘1’，然后在前缀符后加上 用以标识非零元素1和2的码字(编码过程中使用的前缀码字集如下表1所示)， 并用b个比特来表示每个非零元素所在列的位置；当该行的最后一个元素为零， 则在最后一个非零元素编码完成后，用一个二进制位‘0’来表示本行剩余的元素 均为零。

所述用b个比特来表示每个非零元素所在列的位置，具体为：

若非零元素为所在行的第一个非零元素，则b＝[log₂N]；此时的b个比特用 来指明第一个非零元素关于所在行首端的位置；

若非零元素不是所在行的第一个非零元素，则b＝[log₂(N-c)]，其中c是前一 次编码的非零元素的列的位置；此时的b个比特用来表示这个非零元素关于前 一次编码的非零元素的右端的位置。

表13类顶点符号的码字集

如图7所示，解码过程为：根据坐标表Q，解码出矩阵H、V和I，根据H、 V、I和颜色表P，利用扩展的Gouraud方法重建解码图像，具体为：

S3.1将一个大小为M×N的矩阵g_est的所有元素赋任意初值，并将同类块的 计数变量n赋值为0；

S3.2根据坐标表Q，按H、V、I的顺序依次解码出3个大小为M×N的H、 V和I矩阵；

S3.3根据颜色表P，给出同类块的总数s；

S3.4同时扫描H、V和I矩阵，若扫描到值为1的像素，则根据P{n}，判 断该同类块的类型并获取其灰度值；

S3.5根据同类块的类型，利用扩展的Gouraud阴影法计算该同类块的所有 g_est(x，y)，其中g_est(x，y)表示该同类块中坐标(x，y)处的近似灰度值；

S3.6按光栅扫描的顺序将该同类块的解码结果赋值给矩阵g_est；

S3.7令n加1，并判断此时是否满足n＜s，若是，重复步骤S3.4～S3.7；若 否，进行步骤S3.8；

S3.8根据矩阵g_est输出灰度图像，并根据如下公式计算峰值信噪比PSNR：

$\mathrm{PSNR}=10{\log }_{10}\left(\frac{{255}^2\times M\times N}{\underset{x=0}{\overset{M-1}{\Sigma }}\underset{y=0}{\overset{N-1}{\Sigma }}{[G(x,y)-g_{\mathrm{est}}(x,y)]}^2}\right).$

下面以256×256大小的图像处理领域里惯用的‘Lena’、‘Goldhill’、‘Peppers’、 ‘Boat’、‘Robot1’、‘Robot2’、‘Robot3’和‘Robot4’灰度图像作为测试对象，通过 与RNAMC、STC和SDCT等表示方法进行直接或间接比较，说明ORNAMC 表示方法的有效性及优越性。给定4种不同的误差容许量ε＝10、20、30和40， 表2～4、表2具体给出了ORNAMC和STC表示方法的同类块的数目。表3具 体给出了ORNAMC和STC表示方法的PSNR，表4具体给出了ORNAMC和 STC表示方法的压缩比。

从SDCT和RNAMC的实验结果可知：在保持图像质量的前提下，SDCT 表示方法和RNAMC表示算法在压缩比提高率方面比STC表示方法分别平均提 高了63.08％和82.91％。另外，在算法的编解码复杂度方面，SDCT表示方法的 编解码时间复杂度是相同的，且是高于STC表示方法的。因此，相对于STC表 示方法，SDCT表示方法获得的较高的压缩比是以牺牲算法的编解码时间复杂度 为代价的。而RNAMC和STC表示方法的复杂度是相同的，即：编解码部分的 时间复杂度分别为O(n log n)和O(n)，其中n为灰度图像的像素数。同时，RNAMC 的实验结果还表明：在保持图像质量的前提下，RNAMC表示算法在同类块的数 目方面比STC表示方法平均减少了18.54％。ORNAMC表示算法的编解码复杂 度与RNAMC是相同的。

从表2～4不难看出，随着ε的增加，ORNAMC和STC表示方法的压缩比 均呈增加趋势，而同类块数和PSNR均呈下降趋势。对于给定的8幅图像，更进 一步的计算结果表明：在不同的误差容许量下(ε＝10、20、30和40)， ORNAMC(STC)的同类块数平均为2907(4232)，ORNAMC(STC)的PSNR平均为 31.1106(33.9774)，ORNAMC相对于STC的压缩比提高率平均为91.84％。因此， 尽管ORNAMC表示算法在PSNR方面比STC表示方法平均下降了8.44％，但 在压缩比提高率方面却比STC表示方法平均提高了91.84％，同时ORNAMC表 示算法在同类块的数目方面也比STC表示方法平均减少了31.31％，从而更有利 于提高图像表示的效率和图像处理的速度。

另外，在相同的误差容许量下，比如：当ε＝20，对于给定的8幅图像， RNAMC(STC)的同类块数平均为2978(4443)，RNAMC(STC)的压缩比平均为 7.0508(3.6886)，RNAMC(STC)的PSNR平均为32.0583(34.8910)，显然，RNAMC 在同类块的数目(平均减少了32.97％)和压缩比提高率(平均提高了91.15％)方面 是优于STC的，尽管RNAMC的PSNR比STC平均下降了8.12％。通常，如果 重建图像的PSNR达到30左右，人眼主观上是分辨不出原始图像与重建图像之 间的差异的。显然，当ε＝20，这2种算法重建后的图像的PSNR均达到了30以 上。

RNAMC的实验结果表明：在保持图像质量的前提下，RNAMC表示算法在 压缩比提高率方面比STC表示方法平均提高了82.91％，在同类块的数目方面比 STC表示方法平均减少了18.54％。

而ORNAMC表示算法在保持图像质量的前提下，在压缩比提高率方面比 STC表示方法平均提高了91.84％，在同类块的数目方面比STC表示方法平均减 少了31.31％。显然，在保持图像质量的前提下，ORNAMC表示算法能够比 RNAMC和SDCT表示方法更有效地提高图像表示时的压缩比及降低图像表示 时的同类块总数。

由上述分析可知，与RNAMC、SDCT和STC表示方法相比，在保持图像 质量的前提下，ORNAMC表示算法具有更高的压缩比和更少的块数，从而能够 更有效地减少数据存储空间和提高图像操作的处理速度，因而是灰度图像的一 种更好的表示方法。

表2ORNAMC和STC表示的同类块的数目

表3ORNAMC和STC表示的PSNR

表4ORNAMC和STC表示的压缩性能的比较

上述实施例为本发明较佳的实施方式，但本发明的实施方式并不受所述实 施例的限制，其他的任何未背离本发明的精神实质与原理下所作的改变、修饰、 替代、组合、简化，均应为等效的置换方式，都包含在本发明的保护范围之内。