一种基于非对称逆布局模型的图像边界提取方法

摘要

本发明公开了一种基于非对称逆布局模型的图像边界提取方法，该提取方法首先要对二值图像进行NAM表示，得到总子模式数和坐标表。然后从左上角第一个子模式开始，依次按光栅扫描的顺序扫描，每扫描到一个子模式就获取相关参数值，如果邻居像素所属的区域和当前子模式不属于同一个区域且可以合并，则执行带按秩合并和路径压缩策略的并查集算法合并区域，否则继续扫描下一个邻居像素。当这个块的左边界和上边界的邻居像素全部扫描完毕，此块处理完毕，更新边界信息，按以上步骤处理下一个子模式，直到所有子模式处理完成，最后输出二值图像的边界信息。本发明具有占用存储空间小，图像边界提取速度快等优点。

说明书

技术领域

本发明涉及一种计算机图像处理技术，特别涉及一种基于非对称逆布 局模型(NAM)的图像边界提取方法。

背景技术

图像边界提取技术与图像表示方法密切相关，这里主要就图像的分层 数据结构和图像的边界提取技术来介绍相关的研究现状和国内外的最新发 展趋势。

(1)图像的分层数据结构；

图像表示是目前最为活跃的研究领域之一，它在图像压缩、特征提取、 图像检索、图像去噪和图像复原、图像边界提取等应用中起着非常关键的 作用。有效的图像表示算法不仅能节省存储空间，而且还有利于提高图像 处理的速度。目前已有许多基于空间数据结构的二值图像表示算法，如:字 符串表示算法、树结构的表示算法和码字集表示算法。就二值图像的压缩 算法来说，尽管压缩标准JBIG的压缩性能总是优于目前任何基于空间数据 结构的二值图像表示算法，但是由于JBIG表示算法涉及到熵编码过程，对 于许多应用来说是不可能操作压缩的JBIG格式的。分层数据结构在计算机 视觉、机器人、计算机图形学、图像处理、模式识别等领域里是非常重要 的区域表示方法。四元树(QT,Quad Tree)是图像分层表示的一种形式，它是 研究得最早的、也是研究得最多的一种分层表示形式。早期的四元树表示 都是基于指针的四元树结构，为了显著减少存储空间，Gargantini等人消除 了指针方案，提出了称之为线性四元树(LQT,Linear Quad Tree)的表示方法。 Subramanian等人研究了基于空间二元树分割(BSP,Binary Space Partitioning) 的图像表示方法。图像经过BSP树表示后，其表示结果可直接支持图像的 压缩与分割等算法。基于混合的二元树和四元树表示，Kassim等人提出了 一种基于分层分割的图像表示方法。基于B-树三角形编码方法，Distasi等 人提出了基于空间数据结构的灰度图像表示算法。基于S-树数据结构和 Gouraud阴影法，Chung等人提出了一种基于S-树的空间数据结构的灰度 图像表示(STC,S-Tree Coding)方法(K.L.Chung,J.G.Wu.Improved image  compression using S-tree and shading approach.IEEE Transactions on  Communications，2000，48(5):748-751.)。随后，Chung等人提出了一种 基于DCT域和空域的混合灰度图像表示(SDCT，Spatial-and DCT-based) 方法(K.L.Chung，Y.W.Liu，W.M.Yan.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)。

虽然上述的分层数据表示有许多优点，但是它们过于强调分割的对称 性，因此不是最优的表示方法。借助于Packing问题的思想，以寻找分割最 大化的非对称分割方法为目标，Chen等人提出了图像模式的NAM表示方 法。郑运平等人提出了一种基于扩展的Gouraud阴影法和非重叠矩形子模 式的NAM灰度图像表示方法，简称为RNAMC表示方法(郑运平，陈传 波.一种新的灰度图像表示算法研究.计算机学报,2010，33(12): 2397-2406.)。由于可重叠NAM表示方法一般会比非重叠NAM表示方法效 率高，郑运平等人又提出了一种基于扩展的Gouraud阴影法和重叠矩形子 模式的NAM灰度图像表示方法，简称为ORNAM表示方法(Yunping Zheng, Zhiwen Yu,Jane You,Mudar Sarem.A novel gray image representation using  overlapping rectangular NAM and extended shading approach. Journal of Visual Communication and Image Representation,2012, 23(7):972-983.)。实验结果表明：与STC、SDCT和RNAMC表示方法相比， 在保持图像质量的前提下，ORNAM表示方法具有更高的压缩比和更少的 块数，因而能够更有效地减少数据存储空间，是灰度图像表示的一种良好 方法。最近，郑运平等又提出了一种新的二值图像的NAM表示方法并将 其应用到面积计算中，取得了较好的结果(Yunping Zheng,Mudar Sarem.A  novel binary image representation algorithm by using NAM and coordinate  encoding procedure and its application to area calculation.Frontiers of  Computer Science,2014,8(5):763-772.)。从现状来看，LQT表示主要集中 在降低图像处理运算的复杂性和向更宽的范围扩展，理论上的成果很多， 运用于实际的也不少，并越来越多，仍是当今图像处理领域里一种非常流 行的图像表示方法。

图像表示方法有两个目的：第一，提高图像的表示效率。第二，提高 图像操作的处理速度。

(2)图像的边界提取技术；

边界通常是物体的轮廓，可为人们描述或识别目标以及解释图像提供 至关重要的特征。因此，对图像中的边界进行识别和提取，在计算机视觉 及数字图像分析与应用中起着重要的作用，也具有重要的实用价值。多年 来，图像边界检测与提取一直是数字图像处理、分析与应用领域的重要研 究主题。传统的边界检测方法有导数法、梯度法、拉普拉斯法及各种改进 方法等。近些年，多尺度边缘检测、基于数学形态学的边缘检测和用模糊 逻辑对图像边界进行检测的技术也得到了应用。本质上，传统的边界检测 方法是基于像素灰度变化的方法。一般是先检测每个像素和其相邻像素的 状态，以决定该像素是否处于物体的边界上，然后以图像中像素的灰度值 或用二值灰度图像来表示边界检测图像。传统边界检测与提取方法的关键 在于边界像素点的检出性能和边界点连接算法性能。在复杂图像的边界检 测应用中，效果往往不理想。近年来，面向对象图像分析方法应用逐渐受 到关注。与传统的基于像素灰度处理方法的不同之处为，通过把图像分割 为若干个互不交叠的区域(图像对象)，随后将图像对象作为基本分析处理单 元；这种方式，相对于把像素作为基本处理单元，更适于结合人类关于现 实世界的认知知识，从而能更有效地从图像中提取出在形状和分类上与真 实世界目标(地物)相符合的图像区域。这种基于对象的图像分析是近些年 出现的一种新理论。通过使用分层结构的BSP方法，Wang,C.C.L.等人提 出了一种基于剪切操作的高效的BSP固体边界提取方法。他们的多边形算 法重复执行对应的空间凸划分的体细胞上的裁剪操作，通过遍历细胞连接 计算边界。他们使用基于点的表示随着有限精度运算来提高效率和生成 BSP固体边界近似(Wang,C.C.L.；Manocha,D.,Efficient Boundary  Extraction of BSP Solids Based on Clipping Operations.IEEE Transactions on  Visualization and Computer Graphics,2013,19(1):16-29)。

综上所述，近年来虽然有很多研究人员致力于图像边界提取的研究， 提出了很多新的边界提取技术，但由于问题本身的困难性，目前的方法多 是针对某个具体任务而言的，还没有一个通用的解决办法。图像边界提取 困难的一个重要的原因是图像的复杂性和多样性。由于图像的复杂性，现 有的任何一种单独的图像边界提取算法都难以对一般图像取得令人满意的 分割结果，因而在继续致力于将新的概念、新的理论、新的方法引入图像 边界提取领域的同时，更加重视多种边界提取算法的有效结合，近几年来 提出的方法大多数是结合了多种算法的，与单一的边界提取算法相比，边 界提取集成技术更加有效，而且鲁棒性、稳定性、准确性和自适应性等更 好。

有效的图像表示方法不仅能节省存储空间，而且还能提高图像处理的 速度。图像模式的NAM表示方法是对图像模式的一种逆布局表达方式， 本质上是将图像模式表示为预先定义的子模式集合，可以将子模式进行存 储，因此该方法也直接支持图像的边界提取等处理算法。

发明內容

本发明目的在于针对现有图像边界提取技术中存在的问题，提供一种 基于非对称逆布局模型(NAM)的图像边界提取方法，该图像边界提取方 法可以显著提高图像边界提取的表示和提取效率。基于NAM的边界提取 算法首先要对图像进行编码，得到编码后的总子模式数n，坐标表W。然 后从左上角第一个子模式开始，依次按光栅扫描的顺序扫描子模式，每扫 描到一个子模式就从坐标表中获取此子模式四个角落的坐标值，接着扫描 这个子模式的西边界和北边界处的所有邻居像素，如果邻居像素所属的区 域和当前子模式不属于同一个区域且可以合并，则执行带按秩合并和路径 压缩策略的并查集算法合并区域，否则继续扫描下一个邻居像素。当这个 子模式的左边界和上边界的邻居像素全部扫描完毕，此子模式处理完毕， 更新边界信息，按以上步骤处理下一个子模式，直到所有子模式处理完成 即可提取出二值图像的边界信息。

本发明的目的通过以下技术方案实现：一种基于非对称逆布局模型的 图像边界提取方法，包括以下步骤：

步骤S1、使用基于非对称逆布局模型的二值图像表示法将大小为G×H 的图像b进行编码，得到编码后的总子模式数n，坐标表W。

具体表示方法如下：

步骤S1.1、将矩阵变量M的所有元素赋值为0，M的大小与待处理的 二值图像b相等，均为G×H，同时令子模式的计数变量n＝0；其中，G和 H均为自然数；

步骤S1.2、按光栅扫描的顺序确定二值图像b中的一个未被标识的矩 形子模式的起始点(x₁,y₁)，根据该起始点确定一个面积最大的子模式，并将 子模式在二值图像b中作标识；

步骤S1.3、记录子模式的参数，即：左上角的坐标(x₁,y₁)、右下角的坐 标(x₂,y₂)；令n＝n+1；

步骤S1.4、循环执行步骤(S1.2)到(S1.3)，直到二值图像b中的子模 式均被标识完毕；

步骤S1.5、根据下述坐标数据压缩算法，对矩阵变量M中所有非零元 素的坐标进行编码，并将编码结果存储到一个坐标表W中；

①逐行扫描大小为G×H的矩阵变量M，如果该行所有元素均为零， 那么就不用编码该行，在这种情况下，使用一个二进制位“0”来表示本行从 头到尾都不存在非零元素，并将该二进制位“0”存储到该行的编码表W中； 否则，如果该行存在非零元素，那么就在每一个非零元素前加一个前缀符 “1”，然后在前缀符后加上用以标识非零元素1、2和-1的码字，最后将该 前缀符“1”和其后的码字存储到该行的编码表W中；

②用x个比特来表示这个非零元素所在列的位置，并将这x个比特存 储到该行的编码表W中，其中x的值按如下二种情况进行计算；

对于在某一行遇到的第一个非零元素，x＝[log₂H]；这里的x个比特用 来指明第一个非零元素关于本行首端的位置；

对于在某一行遇到的除了第一个非零元素以外的其他非零元素， x＝[log₂(H-c)]，其中c是前一次遇到的非零元素的列的位置；这里的x个比 特用来表示这个非零元素关于前一次编码的非零元素的右端的位置；

③在某一行的最后一个非零元素编码完后，使用一个二进制位“0”来 表示本行剩余的元素均为零，并将这个二进制位“0”存储到该行的编码表W 中，否则，如果该行的最后一个非零元素的位置在本行的末尾，那么就不 必使用“0”来表示本行剩余的元素均为零；

步骤S1.6、输出坐标表W，其中W是由矩阵变量M的所有行的行编 码表顺序连接而得到的。

步骤S2、置一个当前扫描子模式的序号j，并令j＝0，同时设置一个指 针矩阵B，大小为G×H，用于表示每个像素指向的区域。

步骤S3、在坐标表中得到W[j]。

步骤S4、根据W[j]，算出当前子模式的大小size和左边界、上边界坐 标信息。

步骤S5、从左边界最下方开始，往上扫描，对每个左边界像素L找出 它左边的一个像素LL(即LL在X方向比L小1)，并利用矩阵B找出像素L 和像素LL所属的区域，再用带按秩合并和路径压缩策略的并查集算法找出 这两个区域的祖先区域，若两个区域是同一区域，则跳到下一个像素，否 则，如果两个区域不属于同一区域，则根据均值和方差判断这两个祖先是 否可合并。

本步骤和下一步骤中所用的2个数据结构如下：

①Region数据结构域：

{Mean，Var，Size，Father，Count，EdgeLink}

其中Mean表示此区域的灰度均值，Var表示此区域的灰度方差，Size 表示此区域的大小，即像素数，这三个域用来支持区域的合并操作。域Father 是一个指针，用来指向此区域的父节点，Count用来这个区域的后代区域的 数量，以上两个域用来支持并查集算法。域EdgeLink指向这个区域的边界， 可以用来追踪此区域的边界信息。

②Edge数据结构域：

{PreLink，First，Last，SucLink}

PreLink和SucLink用来支持双向链表，First和Last指向角落顶点的 起点和终点。

步骤S6、左边界扫描完毕后，从上边界最左方开始，往右扫描，对每 个上边界像素T找出它上边一个像素TT(即TT在Y方向比T小1)，并利用 矩阵B找出像素T和像素TT所属的区域，再用带按秩合并和路径压缩策 略的并查集算法找出这两个区域的祖先区域，若两个区域是同一区域，则 跳到下一个像素；否则，如果两个区域不属于同一区域，则根据均值和方 差判断这两个祖先是否可合并。

步骤S7、更新边界信息，j++，跳转至步骤S3，直到所有子模式处理 完毕。

步骤S8、输出二值图像b的边界信息。

本发明的原理：本发明借助于布局问题和二值图像的四元树区域表示 方法的思想，通过二值图像的NAM表示为基础，提供了一种基于非对称 逆布局模型的图像边界提取方法，该方法可以显著提高图像边界提取的表 示和操作效率。基于非对称逆布局模型的图像边界提取方法首先要对二值 图像进行NAM表示，得到总子模式数n和坐标表W。然后从左上角第一 个子模式开始，依次按光栅扫描的顺序扫描，每扫描到一个子模式就获取 相关参数值，如果邻居像素所属的区域和当前子模式不属于同一个区域且 可以合并，则执行带按秩合并和路径压缩策略的并查集算法合并区域，否 则继续扫描下一个邻居像素。当这个块的左边界和上边界的邻居像素全部 扫描完毕，此块处理完毕，更新边界信息，按以上步骤处理下一个子模式， 直到所有子模式处理完成，最后输出二值图像的边界信息。本发明方法的 时间复杂度为O(nLα(n))，其中n表示同类块的块数，L表示每块的边长大 小,α(n)是ackerman函数的逆函数。

本发明相比现有技术具有如下优点：

1、在图像边界提取的表示方面，对于给定的4幅图像，NAM(LQT) 的子模式数平均为11585(36633)，NAM(LQT)的压缩比CR平均为1.3801 (0.2862)，也即RNAM的压缩比是LQT的压缩比的4.8222倍。同时NAM 表示算法在子模式的数目方面也比LQT表示算法减少了68.38％，显然， NAM在子模式的数目(减少了68.38％)和压缩比提高率(提高了382.22％) 方面是优于LQT的。

2、在图像边界提取的速度方面，基于NAM表示的边界提取的执行速 度比基于LQT表示的边界提取的执行速度平均提高了92.39％，因而是一 种更有效的边界提取算法，具有占用存储空间小，图像边界提取速度快。

因此，本发明提供的NAM边界提取方法是优于LQT边界提取方法的。 本发明既可应用于传统的图像边界提取市场，又可应用于新兴领域，如网 路传输、无线通讯、医疗图像等。

3、本发明与现有的基于LQT的边界提取方法相比，基于NAM的边 界提取方法具有更低的比特率和更少的子模式数，从而能够更有效地减少 数据存储空间和提高图像边界提取的速度,因而是二值图像的一种更好的边 界提取方法，这种边界提取方法可以应用于图像处理的各个方面，在降低 存储空间、加快传输速度、提高模式匹配效率等方面具有良好的理论参考 意义和实际应用价值。

附图说明

图1是本发明基于NAM的边界提取方法的完整流程图。

图2是基于NAM的二值图像的表示方法流程图。

图3a是本发明所用的512×512大小的标准二值图像F16。

图3b是本发明所用的512×512大小的标准二值图像Goldhill。

图3c是本发明所用的512×512大小的标准二值图像Lena。

图3d是本发明所用的512×512大小的标准二值图像Peppers。

图4a给出了图3c的LQT方法的分割效果。

图4b给出了LQT方法的区域合并的效果。

图4c给出了用LQT方法提取到的二值图像的边界。

图5a给出了图3c的LQT方法的分割效果。

图5b给出了NAM方法的区域合并的效果。

图5c给出了用NAM方法提取到的二值图像的边界。

具体实施方式

实施例

本发明目的在于针对现有图像边界提取技术中存在的问题，提供一种 基于非对称逆布局模型(NAM)的图像边界提取方法，其总体流程如图1 所示，可以显著提高图像的边界提取速度且同时能有效降低存储空间。基 于非对称逆布局模型的图像边界提取方法首先要对二值图像进行NAM表 示，得到总子模式数n和坐标表W。然后从左上角第一个子模式开始，依 次按光栅扫描的顺序扫描，每扫描到一个子模式就获取相关参数值，如果 邻居像素所属的区域和当前子模式不属于同一个区域且可以合并，则执行 带按秩合并和路径压缩策略的并查集算法合并区域，否则继续扫描下一个 邻居像素。当这个块的左边界和上边界的邻居像素全部扫描完毕，此块处 理完毕，更新边界信息，按以上步骤处理下一个子模式，直到所有子模式 处理完成，最后输出二值图像的边界信息。本发明方法的时间复杂度为 O(nLα(n))，其中n表示同类块的块数，L表示每块的边长大小,α(n)是 ackerman函数的逆函数。实验结果表明：与当前的流行的基于LQT的边界 提取方法相比，本发明提出的基于NAM的边界提取方法具有更低的比特 率和更少的子模式数，从而能够更有效地减少数据存储空间和提高图像边 界提取的速度,因而是二值图像的一种更好的边界提取方法。这种方法可以 应用于图像处理的各个方面，在降低存储空间、加快传输速度、提高模式 匹配效率等方面具有良好的理论参考意义和实际应用价值。

如图2所示，本发明提供的图像表示方法通过对给定的一幅大小为 G×H的二值图像b用矩形NAM进行表示，得到互不相同的子模式的集合 和一个坐标表W，然后基于这些子模式，提出了一种基于非对称逆布局模 型的图像边界提取方法。具体包括以下步骤：

(S1)使用基于非对称逆布局模型的二值图像表示法将大小为G×H的 图像b进行编码，得到编码后的总子模式数n，坐标表W。

具体表示方法如下：

(S1.1)将矩阵变量M的所有元素赋值为0，M的大小与待处理的二值 图像b相等，均为G×H，同时令子模式的计数变量n＝0；其中，G和H 均为自然数；

(S1.2)按光栅扫描的顺序确定二值图像b中的一个未被标识的矩形子 模式的起始点(x₁,y₁)，根据该起始点确定一个面积最大的子模式，并将子模 式在二值图像b中作标识；

(S1.3)记录子模式的参数，即：左上角的坐标(x₁,y₁)、右下角的坐标(x₂, y₂)；令n＝n+1；

(S1.4)循环执行步(S1.2)到(S1.3)，直到二值图像b中的子模式均被 标识完毕；

(S1.5)根据下述坐标数据压缩算法，对矩阵变量M中所有非零元素的 坐标进行编码，并将编码结果存储到一个坐标表W中；

①逐行扫描大小为G×H的矩阵变量M，如果该行所有元素均为零， 那么就不用编码该行，在这种情况下，使用一个二进制位“0”来表示本行从 头到尾都不存在非零元素，并将该二进制位“0”存储到该行的编码表W中； 否则，如果该行存在非零元素，那么就在每一个非零元素前加一个前缀符 “1”，然后在前缀符后加上用以标识非零元素1、2和-1的码字，最后将该 前缀符“1”和其后的码字存储到该行的编码表W中；

②用x个比特来表示这个非零元素所在列的位置，并将这x个比特存 储到该行的编码表W中，其中x的值按如下二种情况进行计算；

对于在某一行遇到的第一个非零元素，x＝[log₂H]；这里的x个比特用 来指明第一个非零元素关于本行首端的位置；

对于在某一行遇到的除了第一个非零元素以外的其他非零元素， x＝[log₂(H-c)]，其中c是前一次遇到的非零元素的列的位置；这里的x个比 特用来表示这个非零元素关于前一次编码的非零元素的右端的位置；

③在某一行的最后一个非零元素编码完后，使用一个二进制位“0”来 表示本行剩余的元素均为零，并将这个二进制位“0”存储到该行的编码表W 中，否则，如果该行的最后一个非零元素的位置在本行的末尾，那么就不 必使用“0”来表示本行剩余的元素均为零；

(S1.6)输出坐标表W，其中W是由矩阵变量M的所有行的行编码表顺 序连接而得到的。

(S2)置一个当前扫描子模式的序号j，并令j＝0，同时设置一个指针矩 阵B，大小为G×H，用于表示每个像素指向的区域。

(S3)在坐标表中得到W[j]。

(S4)根据W[j]，算出当前子模式的大小size和左边界、上边界坐标信 息。

(S5)从左边界最下方开始，往上扫描，对每个左边界像素L找出它左 边的一个像素LL(即LL在X方向比L小1)，并利用矩阵B找出像素L和像 素LL所属的区域，再用带按秩合并和路径压缩策略的并查集算法找出这两 个区域的祖先区域，若两个区域是同一区域，则跳到下一个像素，否则， 如果两个区域不属于同一区域，则根据均值和方差判断这两个祖先是否可 合并。

本步骤和下一步骤中所用的2个数据结构如下：

①Region数据结构域：

{Mean，Var，Size，Father，Count，EdgeLink}

其中Mean表示此区域的灰度均值，Var表示此区域的灰度方差，Size 表示此区域的大小，即像素数，这三个域用来支持区域的合并操作。域Father 是一个指针，用来指向此区域的父节点，Count用来这个区域的后代区域的 数量，以上两个域用来支持并查集算法。域EdgeLink指向这个区域的边界， 可以用来追踪此区域的边界信息。

②Edge数据结构域：

{PreLink，First，Last，SucLink}

PreLink和SucLink用来支持双向链表，First和Last指向角落顶点的 起点和终点。

(S6)左边界扫描完毕后，从上边界最左方开始，往右扫描，对每个上 边界像素T找出它上边一个像素TT(即TT在Y方向比T小1)，并利用矩阵 B找出像素T和像素TT所属的区域，再用带按秩合并和路径压缩策略的并 查集算法找出这两个区域的祖先区域，若两个区域是同一区域，则跳到下 一个像素；否则，如果两个区域不属于同一区域，则根据均值和方差判断 这两个祖先是否可合并。

(S7)更新边界信息，j++，跳转至(S3)，直到所有子模式处理完毕。

(S8)输出二值图像b的边界信息。

本实例对LQT和NAM这两种表示算法进行了比较。所采用的测试图 像的大小、名称分别为512×512大小的‘F16’、‘Goldhill’、‘Lena’和‘Peppers’ 等4幅灰度图像,如图3a、图3b、图3c和图3d所示。

本实例先给出了NAM和LQT表示方法的实验结果的比较，这2种方 法的表示效率可以用以下2个参数进行度量,即:子模式的数目和压缩比。表 1(表1为压缩性能的比较表)给出了NAM表示算法和LQT表示算法在 压缩性能上的比较。表2(表2为子模式数和块数的比较表)给出了NAM 和LQT表示算法在子模式数和块数的数目上的比较。

Algorithm F16 Goldhill Lena Pepper LQT 0.3244 0.2060 0.2720 0.3425 NAM 1.7443 0.8786 1.2486 1.6488

表1

Algorithm F16 Goldhill Lena Pepper LQT 31078 48946 37072 29437 NAM 8396 17203 11374 9365

表2

从表1和2可以看出,对于给定的4幅图像，NAM(LQT)的CR平均为 1.3801(0.2862),NAM(LQT)的子模式平均为11585(36633),也即NAM的压 缩比是LQT的压缩比的4.8222倍，从而更有利于节省存储空间；而且NAM 表示在子模式的数目方面也比LQT表示平均减少了68.38％,从而更有利于 提高图像表示的效率和图像处理的速度。

综上所述,与LQT表示算法相比,NAM表示算法具有更高的压缩比和 更少的块数,从而能够更有效地减少数据存储空间,因而是二值图像的一种 更好的表示方法。

如图4a、图4b和图4c所示，为‘Lena’的LQT的分割、合并和边界提 取结果；如图5a、图5b和图5c所示，为‘Lena’的NAM的分割、合并和 边界提取结果。图4为LQT方法的一个实例，其中，图4a给出了图3c的 LQT方法的分割效果，图4b给出了LQT方法的区域合并的效果，图4c给 出了用LQT方法提取到的二值图像的边界。图5为NAM方法的一个实例， 其中，图5a给出了图3c的LQT方法的分割效果，图5b给出了NAM方法 的区域合并的效果，图5c给出了用NAM方法提取到的二值图像的边界。

下表3(表3为NAM表示与LQT表示的分割性能比较表)所示，为 NAM表示与LQT表示的分割效率的比较。

Image F16 Goldhill Lena Peppers NP 262144 262144 262144 262144 NB_LQT31078 48946 37072 29437 NB_NAM8396 17203 11374 9365 Nreg_LQT575 2405 1788 1628 Nreg_NAM575 2405 1788 1628 T_LQT1406 2688 1875 1343 T_NAM94 156 141 140 (T_LQT-T_NAM)/T_LQT93.31％ 94.20％ 92.48％ 89.58％

表3

表3中NP表示测试图像的像素总数，单位为个；NB_LQT和NB_NAM分别 表示图像用LQT表示和NAM表示时的子模式的数量，单位为个；Nreg_LQT和Nreg_NAM分别表示图像用LQT表示和NAM表示时分割后的区域的数量， 单位为个；T_NAM和T_LQT分别表示基于LQT表示和基于NAM表示的分割 算法的执行时间，单位为毫秒。

对于给定的4幅图像，NAM(LQT)的CR平均为1.3801(0.2862), NAM(LQT)的子模式平均为11585(36633),也即NAM的压缩比是LQT的压 缩比的4.8222倍，从而更有利于节省存储空间；而且NAM表示在子模式 的数目方面也比LQT表示平均减少了68.38％,从而更有利于提高图像表示 的效率和图像处理的速度.

另外，从表3中不难看出，基于NAM表示的分割算法的执行速度比 基于LQT表示的分割算法的执行速度平均提高了92.39％，因而是一种更 有效的分割算法。

综上所述，本实施例的结果证实了分析的正确性。

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