一种基于最大树结构的形态学滤波方法

摘要

本发明公开了一种基于最大树结构的形态学滤波方法，先构建最大树。以最大树为基础建立形态滤波器，其滤波过程包括最大树构建、滤波和复原。将一幅灰度图像表示为最大树结构，运用枝剪规则，对该最大树节点进行枝剪，去掉不符合枝剪规则的最大树节点，从而达到滤波效果。在执行这个步骤时，删除最大树中不符合规则的节点，即删除图像中的连通区域，删除节点所含像素点根据滤波规则被赋予新灰度值。最后，将枝剪后的最大树复原成图像。利用最大树的形态滤波器，使用该滤波器进行滤波操作时，成功避免了选取结构元素的环节，同时优化了滤波效果。

说明书

技术领域

本发明涉及一种基于最大树结构的形态学滤波方法。

背景技术

数学形态学现如今的应用范围几乎覆盖图像处理的所有领域。基于数学形态学原 理的形态滤波器是一种非线性滤波器，即使形态滤波器发展到现在，研究人员一 直注重于对形态学滤波器功能的改进，以达到更好的滤波效果。选取一种结构元 素做“探针”来探索考究输入图像中的几何结构，当输入图像中的几何结构与所选 定的结构元素相吻合时，则该几何结构被保留，否则被删除，即为形态学滤波器 滤波的基本思想。形态学滤波器不仅能滤除输入图像所含的噪声而且同时保持了 更多输入图像中对象的细节。由算子决定的滤波器基本运算方式主要有腐蚀、膨 胀、开运算和闭运算，正方形、长方形、线条形、圆形和不规则形等是常用的结 构元素形状。

但是在实际应用中采用基本形态学滤波器和广义形态学滤波器时普遍存在 一个问题：滤波操作过程中需要的结构元素在选取时颇受限制，只有选定最优的 结构元素才能达到较好的图像滤波效果，一旦结构元素选取的不得当，就不能达 到理想中的滤波效果，图像被保留部分和被删除部分可能与实际需求不相符。为 了选择适合处理输入图像的最优结构元素，需要借助遗传算法、粒子群优化算法 和层叠算法，因此结构元素的选取变得复杂和繁琐。

因此，有必要设计一种新型的形态学滤波方法。

发明内容

本发明所要解决的技术问题是提供一种基于最大树结构的形态学滤波方法， 该基于最大树结构的形态学滤波方法以最大树为基础建立形态滤波器，步骤简 单，效率高。

发明的技术解决方案如下：

一种基于最大树结构的形态学滤波方法，包括以下步骤：

步骤1：通过递归迭代方法构建最大树；

步骤2：对最大树进行枝剪；

步骤3：图像复原。

步骤1中，最大树的构建方法包括以下步骤：

1)设定当前灰度值h的初始值为0；

2)通过洪泛搜索找出图像中所有临时节点中存储的是灰度值大于等 于h的所有像素点；将灰度值等于h的像素点作为当前根节点；灰度值大于h 的节点作为下一个临时节点

3)使得h＝h+1，返回步骤2)，直到图像中所有的像素点均被处理完；

4)最初的节点为根节点，其余节点为叶子节点；形成了最大树用于表示图像中 各像素点的联通关系，将每条支路节点所含像素点坐标值存入支路矩阵mt 中；

支路矩阵mt有256行；mt的第一行存储根节点的灰度值及像素点坐标(x，y)；

具体存储方式为：第一行、第一列mt(1，1)存储根节点的灰度值h大小；第一行、 第二列mt(1，2)存储根节点第一个像素点的横坐标x，第一行、第三列mt(1，3)存 储第一个像素点的纵坐标y，mt(1，4)存储根节点第二个像素点的横坐标x， mt(1，5)存储第二个像素点的纵坐标y，...，依此类推，将所有根节点的像素点坐标 值全部存储在支路矩阵的第一行中；在支路矩阵中，每行存储至少一个灰度值相 同的连通域；

mt第二行则存储根节点的叶子节点；，...，依此类推。【当多个像素点在一个连通域 时，该连通域内所有像素灰度值相同。为此，本专利将连通域的多个像素点坐标 依次存储在支路矩阵的某一行，存储的每个像素都有横坐标和纵坐标，根据这个 两个坐标值确定像素点坐标。

根据支路矩阵的每一行中同一个连通域内像素点的数量，即可确定该灰度值 对应连通域的面积，该面积用像素点的个数来表示，即该节点(每一个节点对应 一个连通域)的面积属性值】

【为求得节点C_x即连通区域P_x的面积，充分利用支路矩阵mt的作用。连通 区域的面积可理解为该区域包含的像素点个数，故只要计算出像素点的总数即可 求出该平面区域的面积，只需求出支路矩阵mt中每行不为0的值个数num，即 可得出平面区域像素点的总体数量，如下公式：

$\mathrm{Area}=\frac{\mathrm{num}}{2};$

解释：每个连通域中所有像素的灰度值都是一致的，因此，支路矩阵中的每一行 只存储同一灰度值对应连通域的像素灰度值及其坐标。在构造最大树过程中，根 据图像中像素灰度值的关系来识别连通域，例如，若图像中当前像素的灰度值为 g，访问该像素上、下、左、右、右上、左上、左下、右下八个方向相邻像素的 灰度值是否为g，若是，则为连通像素点，否则，不是连通像素点，当所有像素 遍历完后，所有连通像素点构成的区域为连通域。在支路矩阵中，每行可能存储 多个灰度值相同的连通域，而且每个连通域相邻两个像素的横坐标或纵坐标应具 有连续性，如果两个相邻像素点的横坐标或纵坐标值不具连续性，即发生跳变， 则为不同连通域，因此，求连通域的面积时，必须统计同一连通域内的像素点数 量，也就是说，该公式只能用于同一连通域内。】

步骤2中，采用直接规则对最大树种的所有节点进行处理，完成最大树的 枝剪；直接规则Λ为：

$\Lambda \left(C_h^k\right)=\left(\begin{array}{c}{C}_h^k,\mathrm{if\tau }\left(C_h^k\right)\ge r\\ C_{h^{\prime }}^j,\mathrm{if\tau }\left(C_h^k\right)<r\end{array}\right);$

其中，为待判断节点，为节点的父节点，τ(C)为节点C的面积属性值， 其值为节点C的像素个数，r为预设的阈值。【实例中r根据噪声来选择，如选 择15】

通过直接规则处理后节点灰度值变化直接在支路矩阵mt中更新，更新后的 支路矩阵记为新支路矩阵。

步骤3中，依据步骤2中更新后的支路矩阵mt完成图像复原，具体步骤为：

对更新支路矩阵每一行进行处理后，就构建了对应的输出图像灰度值矩阵f， 根据f再显示输出图像，完成了图像的恢复；

对第k行的处理方法如下：

扫描更新支路矩阵第k行，列扫描初始值为2，上限值为新支路矩阵的行数 目y_num；行扫描初始值为1，上限值为新支路矩阵mt的行数目x_num；

判断支路矩阵第k行每一列的值是否不为0，即mt(x，y)≠0，此为条件1；【如 果满足该规则，则第k行的某一像素点在当前连通域内，否则，该像素点不在当 前连通域内。】

如果新支路矩阵mt第k行每一列的值满足判断条件1，同时判断以下两个条 件：

条件2：该值mt(x，y)是否能被2整除；

条件3：该行的下一个值mt(x，y+1)是否不能被2整除；

若mt(x，y)同时满足上述三个条件，则将mt(x，y)赋给i，将MT(x，y+1)赋给 j；然后扫描处理更新支路矩阵中的下一个元素，直到该行中所有的元素都被处 理完；

然后利用新支路矩阵mt第一列值mt(x，1)修改图像像素点灰度值矩阵f，即 f(i，j)＝mt(x，1)。

有益效果：

本发明的基于最大树结构的形态学滤波方法，把图像的最大灰度级作为树的 叶子节点，图像的最小灰度级作为树的根节点，同时，将同一灰度级的连通区域 作为树的节点，以此构建的树就被称为最大树。以最大树为基础建立形态滤波器， 其滤波过程包括最大树构建、滤波和复原。将一幅灰度图像表示为最大树结构， 运用枝剪规则，对该最大树节点进行枝剪，去掉不符合枝剪规则的最大树节点， 从而达到滤波效果。在执行这个步骤时，删除最大树中不符合规则的节点，即删 除图像中的连通区域，删除节点所含像素点根据滤波规则被赋予新灰度值。最后， 将枝剪后的最大树复原成图像。使用基于最大树的滤波器进行图像滤波操作时， 成功避免了结构元素选取环节，优化了图像滤波效果。对于最大树构建过程，运 用先进先出的队列技术，对所有像素进行泛洪搜索，设计支路矩阵进行数据存储， 有效提高了最大树构建、图像复原的效率。

附图说明

图1灰度图像最大树；

图2图像的最大树构建流程；

图3灰度图像连通区域的最大树结构；

图4直接规则程序流程图；

图5最大树构造示意图；

图6不同比例因子的直接规则滤波效果；

图7直接规则复原流程图。

具体实施方式

以下将结合附图和具体实施例对本发明做进一步详细说明：

实施例1：

为构建灰度图像的最大树，首先找出以图像局部背景为基础时的全部临时节 点临时节点中存储的是灰度值大于等于h的像素点，利用二值化操作， 将灰度值等于h的像素点作为当前根节点，灰度值大于h的节点作为下一个临时 节点。逐渐递推下去，即可将图像的所有连通区域均找寻出来。为具体说明该过 程，如图1所示，原始图像是由7个扁平区域组成的，分别为{A，B，C，D，E，F，G}。 每个字母后面紧跟的数字代表了该扁平区域的灰度值，该例子中的灰度值范围是 0到2。

首先设定阈值h为0，二值化操作后可以得到：所有灰度值为0像素点(A区) 为树的根节点。而灰度值高于h＝0的像素点构成了两个连通区域，即 两个节点：和这样就构造了第一棵树(灰度值 为[0，1])。增加阈值为h＝1，把临时节点当做原始图像，例如临时节点 它所有灰度值在h＝1的像素点都得以保留，并且创造 出了最后一个节点然而，灰度值严格高于阈值h的所有像素点(这里所指 为{E，C})创造了两个不同的连通区域，并得到两个叶子节点，即和 利用所有可能的阈值h(从0到最高灰度值)，通过迭代过程完成了对 所有灰度值为h的节点k的最大树构建。

对于灰度级较多的图像，最大树通过递归迭代方法进行构建，采用分层先进 先出(FIFO)队列的洪泛搜索策略，当它获得一个像素点的灰度值时，会立即更新 被淹没节点的辅助数据缓冲区。此函数接下来就会检查其相邻像素的灰度值，并 将其放在合适的队列中。如果一个相邻像素有一个更高的灰度级即h′＞h，则h′继 续进行递归式地洪泛搜索。一旦一个节点被完全淹没，就要通过其父节点和属性 字段来确定其位置。这个函数会将辅助数据返回到其父节点，并且在这个灰度级 上将继续进行洪泛搜索。当所有的像素都处理完时该进程就终止。

当输入图像灰度值转换为最大树节点关系网后，本发明设计了一种支路矩 阵，该矩阵每一行代表一个节点。将最大树的每一条支路节点都存入矩阵mt中， 支路矩阵的个数m就是最大树的支路数。由于每幅图像对应的最大树深度至少为 256，支路矩阵mt有256行，mt的第一行存储根节点的灰度值及像素点坐标 (x，y)，具体存储方式为：第一行、第一列mt(1，1)存储该节点的灰度值h大小； 第一行、第二列mt(1，2)存储根节点第一个像素点的横坐标x，第一行、第三列 mt(1，3)存储第一个像素点的纵坐标y，mt(1，4)存储根节点第二个像素点的横坐 标x，mt(1，5)存储第二个像素点的纵坐标y。依此类推，将所有根节点的像素点 坐标值全部存储在支路矩阵的第一行中，mt第二行则存储根节点的叶子节点， 按照第一行的存储规则，将该支路的所有节点都存入矩阵mt中。灰度图像构建 最大树的流程图如图2所示。

由于灰度图像最大树的建立表现在标记节点在矩阵中所处的位置，为了直观 表现灰度图像的建立过程，如图3所示，灰度图像中不同的连通区域所对应的最 大树结构图。根据人物围巾虚线段包围的部分画出对应的最大树，由于灰度图像 比二值图像复杂，灰度级多，所以同样的连通区域建立的最大树节点不仅个数不 相同，而且深度也不同。

连通区域部分父节点(临时根节点)的灰度值为50，灰度值为89的节点代 表围巾中的波浪花纹，灰度值为68的节点代表左侧矩形框的外圈，灰度值为114 的叶子节点代表矩形框中的亮点；灰度值为77的叶子节点代表右侧矩形框的外 圈，灰度值为139的叶子节点代表矩形框中的亮点；由此完成了灰度图像连通区 域的最大树表示。

将图像建立为最大树后，针对最大树进行枝剪操作。如常用的规则 T(C)＝(τ(C)＜r)，其中r为比例因子。该规则的意义是如果要进行枝剪的节点 属性值τ(C)【该属性为面积，根据节点C的像素个数计算】小于规定的比例因 子r，则该节点将要被删除，这意味着该节点的灰度值要被父节点的灰度值代替， 其要承袭父节点的灰度值。需要说明的是，属性值τ(C)为节点C的面积，通过 统计该节点连通区域的像素点数量得到，比例因子r的取值根据图像中噪声点的 面积获得。在最大树的滤波过程中，上述规则的决策为：如果节点的属性值 那么就直接删除节点其像素的灰度值降低至最高祖先，而其所 有后继节点不受影响。

对于灰度级较多的图像f，本发明设计了直接规则对最大树的节点进行枝 剪。对输入图像f的连通区域属性进行滤波时，实质上是对构建成功的最大树对 应节点进行属性滤波。

针对连通区域属性滤波形式是：

$\Lambda \left(C_h^k\right)=(\tau \left(C_h^k\right)\ge r)---\left(1\right)$

其中τ代表属性度量，代表属性值，r为比例因子。对于连通区域如 果为真，那么Г_A返回连通区域得以保留，表示最大树节点 的操作规则。对该规则的另一种解释是：如果要进行滤波的连通区域(节点)属性 值小于规定的比例因子r，则节点将要被删除，这就意味着该节点的灰度值h 要被其自身父节点的灰度值取代，即承袭祖先节点的灰度值h′。

满足滤波规则的节点C_x删除并不意味着所有属于该节点的像素点都要被删 除，而是该节点的像素值承袭其父节点的像素值(任一节点所含像素点灰度值大 小均相等)。

直接规则的滤波原理是：如果第k个灰度值为h树节点其属性值满足直接规则Λ_direct，则删除节点根据公式(2)，对于树节点如果为真，那么Г_Λ返回连通区域得以保留。如果节点的属性值 那么就直接删除节点其像素的灰度值h降低至父节点当前的灰度值h′， 若其后代节点C_x不满足Λ_direct，则C_x得以保留，灰度值大小保持不变。

直接规则Λ如下所示：

$\Lambda \left(C_h^k\right)=\left(\begin{array}{c}{C}_h^k,\mathrm{if\tau }\left(C_h^k\right)\ge r\\ C_{h^{\prime }}^j,\mathrm{if\tau }\left(C_h^k\right)<r\end{array}\right)---\left(2\right)$

其中，为待判断节点，为节点的父节点。

综上所述，直接滤波规则其实就是仅仅删除属性值小于阈值r的节点 。利用支路矩阵mt进行直接规则滤波设计，算法总体设计思路为：

Step1：首先确定每个节点C_x的属性值τ(C_x)大小。

Step2：判断枝剪的条件：每个节点的属性值τ(C_x)是否小于给定的阈值即比 例因子r。

Step3：若某节点满足枝剪条件Λ_direct，则将该节点所有像素点的灰度值h 全部用其父节点的当前灰度值h′取代。

具体每一步的设计过程：

首先确定每个节点即连通区域的属性值，扫描每个支路矩阵mt，判断每 行每列的值是否不为0。

而后判断枝剪条件，直接规则只有一个判断条件，即若最大树的节点属性值 小于阈值r，则节点被删除，其灰度值h将被其对应父节点灰度值h′ 取代，由于矩阵mt每行的第一列都存有该行即该节点的灰度值大小，只需要将 该行的第一列值mt(x，1)用其父节点所在行的第一列值mt(x-1，1)代替；如果不满 足直接规则Λ_direct，则该行的第一列值mt(x，1)保持不变。利用上述思路，扫描所 有的支路矩阵mt。直接规则流程图如图4所示。

直接规则不需要用标记矩阵存储灰度值发生变化的节点所在mt中的行值， 因为在对紧随其后的支路矩阵mt_i进行扫描时，不满足规则的节点C_x依旧会被删 除，但是因为父节点固定，所以依旧会被重新赋父节点当前灰度值。故最终即使 不同的支路矩阵中含有相同的节点，当遍历完所有支路矩阵mt后，这些相同节 点的灰度值也依旧相同。

以面积属性为例，图5为一幅图像的最大树，树节点利用峰值区域来表示， 该最大树一共有四层。图(a)表示的就是最大树的峰值区域层次结构，其中表 示的是灰度值为0的父节点，该父节点只有一个叶子节点即P₁⁰，其代表的意义 是所有灰度值为1的像素点集合。当作为父节点时，其有两个叶子节点，分 别为灰度值为2的节点和；作为父节点时，有一个灰度值为3的叶子节 点P₃⁰，节点却没有叶子节点。图(b)代表的是峰值区域的面积属性值，其中父 节点的面积属性值为80，第二层叶子节点P₁⁰的面积属性值为65，第三层叶 子节点和的面积属性值分别为7和12，第四层叶子节点P₃⁰的面积属性值为 30。图(c)是模拟的最大树结构形式。

滤波规则应用中，比例因子r选择为面积属性值15，将该属性值应用于规则 中，图(d)是滤波结果，根据直接滤波规则，当节点的面积属 性值小于15时，该节点直接被滤除掉，即节点和被直接删除掉，同时该两 处节点的灰度值赋予其父节点P₁⁰的灰度值1，其中的叶子节点得以保留。

为求得节点C_x即连通区域P_x的面积，充分利用支路矩阵mt的作用。连通区 域的面积可理解为该区域包含的像素点个数，故只要计算出像素点的总数即可求 出该平面区域的面积，只需求出支路矩阵mt中每行不为0的值个数num，即可 得出平面区域像素点的总体数量，如下公式：

$\mathrm{Area}=\frac{\mathrm{num}}{2}---\left(3\right)$

图6显示的是采用不同的比例因子直接规则处理星系，输出图像不仅按照规 定的比例因子滤除掉了大小符合比例因子的噪声，而且相同像素点的灰度值也会 有变化情况，多次进行实验操作，选取滤波结果明显有差异的比例因子r。

图6显示的是当比例因子r的取值逐渐增大时，采用直接规则处理原始星系 图像的不同滤波结果，图6(a)为原始星系图，图6(b)为图像取反及增强结果，图 6(c)为r＝20的滤波结果图与原始星系图相比，很多前景恒星被滤掉，剩下的恒 星颜色变淡，最明显的三个前景恒星较原始图像变亮；图6(d)为r＝40的滤波 结果，图中明显的三个前景恒星较r＝20变亮些，并且滤除掉r＝20时未删除的 前景恒星；图6(e)为r＝60时也变亮，图6(f)为r＝400时，三个前景恒星最亮， 其他前景恒星噪声也不存在，剩余的螺旋星系非常明显，滤波效果显著。由此可 见，当比例因子r的取值逐渐增大时，滤除噪声的效果也就越好。

根据直接规则描述，完成直接规则滤波后的节点灰度值变化直接在支路矩阵 mt中修改，故支路矩阵mt(x，1)中存储的就是枝剪后的灰度值，直接利用m个支 路矩阵mt修改输入图像像素点灰度值矩阵f。Λ_direct复原过程如下所示：

Step1：根据支路矩阵mt求出每个节点C_x包含的所有像素点坐标位置。

Step2：根据Step1得到的像素点坐标位置，利用新支路矩阵mt第一列值取 代其灰度值大小，即h＝mt(x，1)。

Step3：当m个新支路矩阵mt均修改完输入图像的像素点灰度值矩阵后，将 该矩阵读出来即可。

Λ_direct复原算法修改后的节点灰度值直接存储在原支路矩阵mt中。

直接规则的图像复原的程序流程图，如图7所示。首先，需要求出新支路矩 阵mt中每个节点C_x包含的所有像素点坐标位置。扫描新支路矩阵mt，列扫描初 始值为2，上限值为新支路矩阵mt的行数目y_num；行扫描初始值为1，上限值为 新支路矩阵mt的行数目x_num。判断每行每列的值是否不为0，mt(x，y)≠0，此为 条件(1)。

如果新支路矩阵mt每行每列的值满足判断的条件(1)，同时判断条件：(2)该 值mt(x，y)是否能被2整除；(3)该行的下一列值mt(x，y+1)是否不能被2整除。 若mt(x，y)同时满足上述三个条件，则将mt(x，y)赋给i，将MT(x，y+1)赋给j。

然后利用新支路矩阵mt第一列值mt(x，1)修改图像像素点灰度值矩阵f，也 就变相的修改了输入图像符合最小滤波规则的像素点灰度值，即 f(i，j)＝mt(x，1)。

接着就扫描所有的新支路矩阵mt，伴随着所有新支路矩阵(m个)扫描的结 束，则滤波后新的最大树也就建立成功，意味着成功构建了对应的输出图像灰度 值矩阵，再显示输出图像。