OpenCV MSER 算法介绍

算法 › 翻译 › OpenCV

MSER 算法原理介绍以及在 OpenCV 中的实现。

1. Maximally Stable Extremal Regions

这本节翻译自文献 Robust Wide Baseline Stereo from Maximally Stable Extremal Regions。

其中描述了一个新的图像元素类型－最大极值稳定区域 (the Maximally Stable Extremal Regions)。相关概念可以通俗的介绍如下。想象使用所有阈值对灰度图像 $I$ 进行二值化。假定低于阈值的为黑色，高于阈值的为白色。我们想象将这所有的二值图像组成一个电影 $I_t$ ，其中 $t$ 是阈值为 $t$ 的二值图像。这样我们首先将会看到一个纯白的图像，随后，与局部强度极小值对应的黑点将出现并增长。在某个点上，与两个局部极小值对应的区域将合并。最终整幅图像将变成纯黑。电影所有帧的所有连通分量的集合是所有极大区域的集合；通过反转 $I$ 的强度并运行相同的过程，可以得到极小的区域。如下给出了MSER概念的形式化定义和必要的辅助定义。

定义：

图像 $I$ 满足以下映射关系：$D \subset Z^2 \to S$ 。极致区域需满足以下条件：

  1. 集合 $S$ 上存在全序关系 $\leq$，即满足自反性，反对称性和传递性。$S$ 可以定义为 $S={0, 1, \dots, 255}$，也可以定义为实数 $S=R$。
  2. 邻接关系 $A$ 定义为 $A \subset D \times D$，即 $A$ 是 $D$ 上的关系的子集。若用 4 邻域表示邻接关系可表示如下：$p,q \in D $ 是邻接的，当且仅当 $\Sigma^d_1 |p_i-q_i|<1$ （$d$ 表示图像维度）。

区域 $Q$ 是一个连续的 $D$ 的子集，对于 $\forall p,q \in Q$ ，都存在一个序列 $p, a1, a_2, \dots, a_n, q$ 和 $pAa_1, a_iAa{I+1}, a_nAq$。

边界 $\partial Q ={q \in D \backslash Q: \exists p \in Q: qAp} $ ，即 $Q$ 的边界 $\partial Q$ 中每一个点都至少邻接一个不属于 $Q$ 的点。

极值区域 $Q \in D$ 满足 $\forall p \in Q, \forall q \in \partial Q$ : $I(p) > I(q)$ （极大强度区域）或 $I(p) < I(q)$ （极小强度区域）。

极大稳定极值区域（MSER），令 $Q1,\dots,Q{i-1},Qi\dots$ 是一组连续嵌套的极值区域，如 $Q_i \subset Q{i+1}$ 。极值区域 $Q{i^\star}$ 是最大稳定的当且仅当 $q(i) = |Q{i+\Delta} \backslash Q_{i-\Delta} | / |Q_i|$ 在 $i^\star$ 处取得最小值。$\Delta \in S$ 是该方法的一个参数。

在许多图像中，局部二值化图像在一定区域的阈值范围内是稳定的。这些区域值得注意，因为它们具有下列性质：

  • 图像强度仿射变换的不变性。
  • 相邻的协方差具有连贯性。
  • 稳定性，因为极值区域能够使得在一个阈值范围内稳定不变。
  • 多尺度探测，由于不涉及平滑，因此可以检测到非常精细和非常大的结构。
  • 所有极值区域可以在 $O(nlog log n)$ 中被枚举，其中 $n$ 是图像中的像素数量。

枚举极值区域的方法如下：首先像素按强度存储，如果 $S$ 小的话利用 BINSORT [12]排序，这一步的计算复杂度为 $O(n)$ ，如 $S={0, 1, \dots, 255}$。排序后，将像素按照递增或者递减的顺序放置在图像中，可以使用高效的 union-find 算法[12] 维护其连通域及其区域。这里的 union-find 的实现复杂度为 $O(nloglogn)$ ，几乎线性。该算法在实践中是非常快速的。MSER 检测算分数仅仅花费了 0.14 s 在一台 CPU 为 Athlon XP 1600+ 的 Linux PC 上处理一张 530x350 的图像 ($n=185500$)。

这个过程将会产生一个存储了每一个连通域的面积作为强度的函数的数据结构。将两个连通域合并的过程将被看做是较小的连通域的终止，和将小连通域的像素全部加入到大连通域中。最终，选择区域函数变化率局部最小的强度作为阈值从而产生最大稳定的极值区域。在输出中，每个 MSER 由局部强度最小值(或最大值)和阈值的位置表示。

注意。上述算法的结构与一个高效的分水岭算法基本相同[17]。但是，两个算法的输出结果却是完全不同的。分水岭算法是将图像区域 $D$ 进行分割，如分割成一组区域 $R_i$，$\cup R_i = D$，$R_j \cap R_k = \phi$。在分水岭算法中主要关注的当连通域合并时 (两个连通域相接触) 阈值取值。 此时的阈值本文中并不关心，因为其非常的不稳定－当合并后连通域的面积将会产生巨大的跳跃。在MSER检测中，我们寻求一个阈值范围，使连通域保持有效不变。MSER 检测也与阈值有关。每一个极值区域都是一个关于阈值图像的连同域。但是，不寻求全局或“最优”阈值，所有阈值都经过测试，并评估连通域的稳定性。MSER 检测的输出并不是一个二值图像。对于某些存在多个稳定阈值的图像来说，在这种情况下输出的就是一个嵌套子集系统。最后，MSERs 可以定义在任何像素值为有序集的图像上 (即使是高维)。

2. Linear Time Maximally Stable Extremal Regions

MSER 在 OpenCV 中的实现并不是 MSER 的原始算法，而是采用了一种叫做 Linear Time Maximally Stable Extremal Regions 的算法。原文。

3. MSER 在 OpenCV 中的使用

3.1 相关函数

1
2
3
4
5
6
7
8
9
10
Python:
retval = cv.MSER_create( [, _delta
                         [, _min_area
                         [, _max_area
                         [, _max_variation
                         [, _min_diversity
                         [, _max_evolution
                         [, _area_threshold
                         [, _min_margin
                         [, _edge_blur_size]]]]]]]]]	)

该函数用于构造一个 MSER 检测对象。由于这里只介绍对灰度凸显的检测，所以只用到前三个参数。后面的参数是用于彩色图像的，详见 OpenCV 文档。

  1. delta：该值将用于 $(sizei - size{i-delta})/size_{i-delta}$ 的比较，默认为 5。
  2. min_areas：小于该面积的区域将被忽略，默认值为 60。
  3. max_areas：大于该面积的区域将被忽略，默认值为 14400。
  4. max_variation：与其子区域相似的区域将被忽略，默认值 0.25。
1
2
Python:
msers, bboxes = cv.MSER.detectRegions( image )

该函数进行 MSER 检测，检测的结果将存储于 msers 和 bboxes 中。msers 列表中每一个元素是一组点构成的列表，列表中的所有点为该 MSER 的区域。对应下标的 bboxes 中的元素为一个矩形，可以将属于该 MSER 的点集框住。

  1. image：输入图像（可以是 8UC1、8UC3、8UC4，其大小必须大于等于 3x3）。