本方法提出的原因

在Matas提出的标准MSER获取过程中，虽然很好的计算了MSER区域有哪些，但由于MSER的结构为 $(U_j, i_k, q_k)$，即只保留了MSER的包含的像素的并查集、产生时的灰度阈值、区域面积相对变化率，无法方便的获取MSER包含的像素有哪些，需要额外的洪水填充(Flood-Fill)方法还原。 在 MSER 检测过程中，这些像素及其四邻域连通关系已经在连通分量的构建与合并过程中被处理过；而为了恢复 MSER 的完整像素集合，Flood Fill 需要再次遍历这些像素并重新判断邻域连通性，从而产生可以避免的额外计算开销。

因此，Erik Murphy-Chutorian和Mohan Trivedi提出了基于NDS森林的MSER(N-tree Disjoint-Set Forests MSER)。

本方法的步骤

步骤以《【MSER】初始MSER》为基础进行扩展，以下简称为《初始》

1. 按照《初始》中的步骤1到步骤3，开始遍历像素的有序序列 $L$

2. 在初始化像素 $p$ 时，额外为像素 $p$ 创建节点 $Node^{NDS}: Index \leftarrow i \quad Neighbor[1:4] \leftarrow \emptyset$

   初始化像素 $p$，标记 $Active(p) \leftarrow true$，为像素 $p$ 创建：

   • 并查集 $U_j$ ：$Component(p) \leftarrow U_j, \quad Parent(U_j) \leftarrow U_j, \quad Size(U_j) \leftarrow 1$
   • 历史记录 ：$Birth(U_j) \leftarrow i, \quad Death(U_j) \leftarrow \empty, \quad History(U_j) \leftarrow \emptyset$

   将 $U_j$ 加入到 $T$ 中

3. 按照《初始》中的步骤5，遍历像素 $p$ 的四邻域

4. 完成 $U_{r_p}$ 和 $U_{r_q}$ 的合并后，为像素 $p$ 和像素 $q$ 的节点 $Node^{NDS}(p)$ 和 $Node^{NDS}(q)$ 的 $Neighbor$ 中分别压入

   • 像素 $p$ ：$Neighbor[j] \leftarrow q$

   • 像素 $q$ ：$Neighbor[k] \leftarrow p$

   检查像素所在并查集的根节点 $r_p = Find(U_j), p \in U_j$ 是否等于 $r_q = Find(U_k), q \in U_k$。若是，则跳过像素 $q$；若否，则合并像素 $p$ 和像素 $q$ 所在的并查集，分别为 $U_{r_p}$ 和 $U_{r_q}$

   合并规则为：比较 $Size(U_{r_p})$ 与 $Size(U_{r_q})$。

   • $Size(U_{r_p}) > Size(U_{r_q})$：

     将 $U_{r_q}$ 并入 $U_{r_p}$，标记 $Death(U_{r_q}) \leftarrow i, \quad Parent(U_{r_q}) \leftarrow U_{r_p}$，更新 $U_{r_p}$ 的 $Size(U_{r_p}) \leftarrow Size(U_{r_p}) + Size(U_{r_q})$。

   此处不要更新 $History(U_{r_p})$，等待该灰度阈值下的所有像素均处理完成后再统一更新

   • $Size(U_{r_p}) = Size(U_{r_q})$：

     可根据自定义规则决定集合的并入，如可根据 $Birth(U_{r_q})$ 与 $Birth(U_{r_p})$ 的大小决定

   • $Size(U_{r_p}) < Size(U_{r_q})$：

     将 $U_{r_p}$ 并入 $U_{r_q}$，步骤与 $Size(U_{r_p}) > Size(U_{r_q})$ 时对称

5. 按照《初始》中的步骤7到步骤13进行，但在对反相图进行计算的时候，需要额外建立一个NDS森林

如何获取指定MSER包含的像素

1. 假设指定的MSER为 $(U, i, q)$，找到并查集 $U$ 的根 在NDS森林中对应的N树

2. 从MSER中的任意节点开始遍历这颗N树，通常可通过并查集 $U$ 的根对应的节点开始，找到所有与起始节点连通的且 $index$ 不大于 $i$ 的节点。若某个节点的 $index _p> i$ ，则无须继续遍历该分支。

   注意，此操作为删除N树中所有 $index > i$ 的节点，这可能会导致N树分裂为多个子树。在视觉效果上，这意味着MSER代表的区域较浅的像素消失，分裂为多个小区域

3. 步骤2中找到的点的集合即此MSER包含的所有像素