Matas提出的MSER方法的步骤

1. 将原始图像处理为灰度图，获得灰度图矩阵与灰度集合 $I$

2. 设灰度图像中所有的像素构成的有序序列为 $L$，对 $L$ 按照像素的灰度值进行非降序排序。初始化并查集集合 $T = \empty$

3. 令 $Active(p) \leftarrow false, \forall p \in L$，遍历序列 $L$。设当前像素为 $p$，像素 $p$ 的灰度阈值为 $i \leftarrow G(p)$

4. 初始化像素 $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$ 中

5. 遍历像素 $p$ 四邻域中存在于图像中的像素，设当前像素为 $q$，跳过所有 $Active(q) \neq true$ 的轮次

6. 检查像素所在并查集的根节点 $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})$ 时对称

7. 完成像素 $p$ 的邻域像素的遍历。在序列 $L$ 中，若存在下一像素且下一像素的灰度值与像素 $p$ 的一致，则继续处理下一个像素。

8. 在序列 $L$ 中，若当前元素为队列末尾元素或下一像素与当前像素的灰度值不一致，则遍历 $T$ 中存活的并查集，设当前并查集为 $U_j, Find(U_j) = U_j \land Death(U_j) = \empty$，更新 $History(U_j)[i] \leftarrow Size(U_j)$

9. 遍历 $T$ 中历史记录不为空的并查集，设当前并查集为 $U_j$

10. 遍历并查集 $U_j$ 的 $History(U_j)$，设 $History(U_j)$ 中记录的灰度值集合为 $I_j$，当前灰度为 $i \in I_j$ ，变化率计算的灰度阈值偏移量为 $\Delta$，窗口长度为 $2\Delta$，计算窗口的左边界灰度默认值为 $i_l = i - \Delta$，计算窗口的右边界灰度默认值为 $i_r = i + \Delta$，区域面积的相对变化率计算公式为：

    $$q(U_j, i) = \frac{A_{i+\Delta} - A_{i-\Delta}}{A_i} , A_k = History(U_j)[k] , k \in\{i-\Delta, i, i+\Delta\}$$

    若 左边界满足 $i-\Delta < Birth(U_j)$ 或右边界满足 $Death(U_j) \neq \emptyset \land i+\Delta \geq Death(U_j)$，说明计算的区域面积的相对变化率使用的历史变化区间超过了区域本身的生命周期，应当直接跳过计算，对于其他情况可如下继续计算。

    若 $i-\Delta \notin I_j$，则在灰度集合$I_j$ 中寻找最大的灰度 $i_{l}^{replace}$ 满足

    $$i_l^{replace} = max\{ k \in I_j | k \leq i - \Delta \}$$

    以等效代替 $i-\Delta$ ，令 $i_l = i_l^{replace}$。

    若 $i + \Delta \notin I_j$，则在灰度集合 $I_j$ 中寻找最大的灰度 $i_{r}^{replace}$ 满足

    $$i_r^{replace} = max\{ k \in I_j | k \leq i + \Delta \}$$

    以等效代替 $i+\Delta$ ，令 $i_r = i_r^{replace}$

    每个区域都是随阈值灰度的增长而单向增长的，当某一灰度不存在于灰度值集合 $I_j$ 中时，该区域在此灰度阈值下没有发生面积变化，因此该区域的面积与较低的灰度阈值时的面积相等。所以， $i-\Delta \notin I_j$ 、$i+\Delta \notin I_j$ 时，对应使用较小的满足条件的灰度时的历史记录作为代替。

    若 $i_l \notin I_j \lor i_r \notin I_j$ ，跳过当前灰度阈值；否则，按如下公式计算区域面积相对变化率：

11. 遍历完成 $History(U_j)$ 中的区域面积相对变化率计算后，设得到的区域面积相对变化率队列为 $Q$，$Q$ 中的元素 $q(U_j, i)$ 按照 $i$ 的大小排列。遍历 $Q$，设当前的区域面积相对变化率为 $q_k$，取 $Q$ 中所有满足 $q_k < q_{k-1}$ 且 $q_k <q_{k+1}$ 的元素，那么 $(U_j, i_k ,q_k)$ 为一个MSER，将其放入MSER集合$M^+$ 中。
12. 获取原始图像灰度图的反相灰度图 $G^-(p) = G^{max} - G(p)$，对于反相图有 $i^- = G^{max} - i$，其中 $i^-$ 为正相图中灰度阈值 $i$ 在反相图中的对称灰度阈值，$G^{max}$ 为灰度图像所在灰度值域中灰度的最大值。重复步骤2到步骤11，最终得到MSER集合 $M^-$
13. 最终，最大稳定极值区域集合 $M = M^+ \cup M^-$ 为所求

如何获得每个MSER包含的像素

1. 遍历MSER集合 $M^+$，设当前的MSER为 $M_j = (U, i, q)$，MSER对应区域的像素集合为 $S = \emptyset$。
2. 获取 $U$ 的根节点对应的像素 $p$，从 $p$ 开始做洪水填充(Flood-Fill)，洪水填充的灰度阈值为 $i$，即从 $p$ 开始使用DFS或BFS遍历四邻域的属于 $U$ 的像素，设遍历的当前像素为 $q$， 则将所有满足 $i_q \leq i$ 的加入 $S$。
3. 在MSER集合 $M^-$ 中执行对称操作，寻找满足 $i_q \geq i$ 的像素加入像素集合 $S$