为什么提出此方法

Matas提出的MSER计算方法中，使用的并查集的时间复杂度为 $O(kN)$，其中 $k = \alpha (N)$， $\alpha(N)$ 为常数 $N$ 的反阿克曼函数值。 为了消除受反阿克曼函数影响的常数 $k$，令时间复杂度为真正的线性时间，David Nistér 与 Henrik Stewénius 提出了本方法。

计算组件树的步骤

1. 设原图为8位图片，图片的大小为 $rows \times cols$。预处理原始图像，若原始图像不是以连续的内存存储的，则先复制原始图像令其以连续的内存存储。之后，以长度为 $rows \times cols$ 的像素状态数组 $L$ 存储处理的图像的像素。

2. 新建路径边界像素记录队列 $heap$，其中 $heap$ 的长度为256，队列的每个元素 $heap[i]$ 为灰度值等于 $i$ 的像素的边界像素栈

3. 创建活动组件栈 $S$，初始化为包含一个边界组件（灰度阈值为256）、一个只包含起始像素灰度值的记录的组件栈（该像素在步骤5中进行说明）

4. 遍历灰度图中的边界像素，将其特殊标记为已访问

   每个像素由一个32位的int记录如下的信息：

   • 高3位：4邻域中，遍历到的邻居像素的index，合法值0-5，默认值为0，标记像素尚未访问；值1-4记录4邻域的遍历进度，即上下左右四个方向的像素；特殊标记值为5，表示像素无须访问邻域，包含像素为图像边界、像素的邻域已完全遍历两种情况。后文中使用 $vis()$ 函数获取该3位
   • 低29位：像素链表中，当前像素的下一像素的index值。后面使用 $next()$ 函数获取该29位

5. 从图像中位于 $(1, 1)$ 处的像素开始遍历，即从 $L[cols+1]$ 处开始遍历

   此处为与Matas提出的方法的核心区别之一，原文如降雨，同时填充灰度图的每个点位。本方法从一点开始填充，如在某一点位打开水龙头进行填充。

   理论中，可以从任意一点开始遍历。但在工程实现中，为了方便，通常按照步骤5中的 $(1,1)$ 处像素开始遍历

6. 设当前像素为像素 $p$，从像素 $p$ 访问历史记录的 $index$ 开始（$index$ 的默认值为0），继续遍历像素 $p$ 的4邻域中未访问的像素。设遍历4邻域时的当前像素为 $q$，令 $index \leftarrow index + 1$，然后更新像素 $q$ 的访问标记 $vis(q) \leftarrow index + 1$ 。检查像素 $q$ 的灰度值 $G(q)$：

   • 若 $G(q) < G(p)$ ：将像素 $p$ 放回路径边界队列 $heap[G(p)]$ 中；更新像素 $p$ 的四邻域遍历进度，即像素 $q$ 在像素 $p$ 的四邻域中的 $index$ ；迁移当前像素为 $q$ ；为像素 $q$ 在组件栈中新建组件，并在组件栈中记录像素 $q$ 的灰度作为该组件的灰度阈值 ；更新 全局灰度阈值为像素 $q$ 的灰度 $currentGray \leftarrow G(q)$ ；
   • 若 $G(q) \geq G(p)$，将像素 $q$ 放到路径边界队列 $heap[G(q)]$ 中

7. 当像素 $p$ 的4邻域中的像素均被访问过后：

   • 更新像素 $p$ 的访问标记 $vis(p) \leftarrow 5$

   • 尝试更新活动组件栈 $S$ 的栈顶组件 $comp$ ：

     • 若 $comp$ 内有像素，则更新 $comp$ 用于记录包含像素的链表，令当前队尾像素指向的下一像素为像素 $p$

     • 若 $comp$ 内没有像素，则更新 $comp$ 用于记录包含像素的链表，令队首像素为像素 $p$

     由此可见，comp内部是以单链表的形式存储组件包含的像素的

   • 更新 $comp$ 用于记录包含像素的链表的队尾像素为像素 $p$

   • 更新 $comp$ 用于记录包含像素的链表的大小 $comp.size \leftarrow comp.size + 1$

8. 若路径边界队列中，记录像素 $p$ 同灰度像素的像素栈 $heap[G(p)]$ 非空，则从 $heap[G(p)]$ 中取出栈顶像素，作为当前像素，对其执行步骤6-7

9. 若路径边界队列中没有与像素 $p$ 同灰度的像素，即 $heap[G(p)]$ 为空，则先增大灰度阈值 $currentGray \leftarrow currentGray +1$，查询 $heap[currentGray]$ 是否为空：

   • 若 $heap[currentGray]$ 为空，则继续增大灰度阈值 $currentGray \leftarrow currentGray + 1$，直至灰度阈值达到256时结束
   • 若 $heap[currentGray]$ 不为空，则取 $heap[currntGray]$ 的栈顶像素作为当前像素，对其执行步骤6-7

10. 灰度阈值更新后：

    • 若当前灰度阈值小于活动组件栈的次栈顶组件记录的灰度阈值，则更新组件内部的像素变化历史
    • 若当前灰度阈值等于活动组件栈的词栈顶组件记录的灰度阈值，则弹出 $comp$，合并活动组件栈 $S$ 的新栈顶组件与弹出的组件

11. 当 $heap$ 中不存在像素且灰度阈值达到256后，活动组件栈 $S$ 中应当仅剩余一个真实组件和灰度阈值为256的边界组件，此时，更新真实组件的历史，并在更新时特殊标记为最终更新