最大稳定极值区域（MSER）的提取与分析

### 最大稳定极值区域（MSER）的提取与分析 #### 1. 构建组件树 在处理图像时，会遇到需要构建属于栈 C 中当前顶部组件的组件树的情况。此时，会调用 `ProcessStack()` 函数来处理组件栈。 `ProcessStack()` 函数（见 Alg. 26.5）会从栈 C 中移除组件，直到栈顶组件的级别与新的“目标”级别 `v = val(q)` 相匹配。具体步骤如下： 1. 在每次迭代中，将栈顶的第一个组件（`c1`）取出并“发出”，即添加到极值组件列表 E 中（Alg. 26.5，第 4 - 5 行）。 2. 除非栈 C 为空，否则检查栈中的下一个组件（Alg. 26.5，第 7 行）： - 如果目标值 `v` 小于栈中下一个组件的级别，则表示尚未为级别 `v` 实例化组件。此时，会创建一个级别为 `v` 的“人工”组件 `c2`（Alg. 26.5，第 8 行）。 - 否则，`c2` 是从栈 C 中弹出的下一个组件（见 Alg. 26.5，第 10 行）。 3. 将之前发出的组件 `c1` “合并”到 `c2` 中，即将 `c2` 设置为 `c1` 的父组件，并将 `c2` 重新压入组件栈 C 中（Alg. 26.5，第 11 - 13 行）。 主循环结束后，会再次调用 `ProcessStack()` 函数以获取全局根组件 `r`（覆盖所有图像像素），此时该组件仍在组件栈中（Alg. 26.4，第 34 行）。至此，所有极值组件都包含在集合 E 中，并且所有父子关系都已正确设置，组件树 `T = ⟨E, r⟩` 构建完成。 以下是 `ProcessStack()` 函数的流程： ```mermaid graph TD; A[开始] --> B[检查栈顶组件级别与目标级别是否匹配]; B -- 不匹配 --> C[取出栈顶组件 c1 并添加到 E]; C --> D[检查栈是否为空]; D -- 不为空 --> E[检查目标值 v 与下一个组件级别关系]; E -- v 小于下一个组件级别 --> F[创建人工组件 c2]; E -- v 不小于下一个组件级别 --> G[弹出下一个组件作为 c2]; F --> H[将 c1 合并到 c2 并压入栈]; G --> H; H --> B; D -- 为空 --> I[结束]; B -- 匹配 --> I; ``` #### 2. 组件树示例 通过简单的测试图像可以直观地了解组件树的结构。图 26.4 展示了从两个简单测试图像得到的组件树的 3D 结构，其中每个斑点代表一个极值区域。每个组件的 x/y 位置标记其中心位置（以图像坐标表示），而 z 坐标对应于相关的亮度级别。组件之间的连接表示父子关系，顶部组件（具有最高灰度值）是树的根节点。蓝色节点是后来被选为 MSER 组件的节点，根组件对应于图像的最大像素值并覆盖整个图像（因此始终位于图像中心），标记为红色。 - 图 26.4 (a) 中的合成图像仅包含阶跃变化。区域在一定范围的亮度级别上保持恒定大小，因此得到的组件树非常简单。 - 图 26.4 (b) 是同一图像的模糊版本，引入了中间灰度级别和平滑变化。在这种情况下，极值区域随着亮度级别的增加而连续增长，从而为组件树添加了额外的节点。 在实际应用中，组件树往往会变得相当大。例如，对于一个大小仅为 200 × 200 的自然灰度图像（图 26.5），得到的树包含 10,128 个组件，其中只有一小部分最终被选为 MSER（标记为蓝色）。在更大的图像中，常见的是找到包含数百万个组件的树。 #### 3. 从组件树中提取 MSER 组件树是输入图像中极值区域的层次结构，最后一步是从组件树中提取一组最大稳定极值区域（MSER），即其组件的一个子集。选择组件作为 MSER 的标准如下： 1. **组件面积**：组件 `c` 的面积 `A = |c|` 必须足够大但不能太大，即 `amin ≤ A ≤ amax`。大小限制相对于图像大小 `AI = M·N` 定义为 `amin = AI·αmin` 和 `amax = AI·αmax`，其中 `αmin` 和 `αmax` 是参数。 2. **组件大小稳定性**：组件的大小必须在给定的亮度级别范围 `∆` 内“稳定”，即其大小变化必须足够小。 3. **最大稳定性**：MSER 必须是最大稳定的，即其大小变化相对于其父组件和所有子组件是局部最小值。 4. **组件多样性**：树层次结构中连续的 MSER 不应彼此过于相似，而应“多样”，即大小明显不同，以避免相邻的重复项。 一些额外的约束条件（不属于原始算法的一部分）在后续会详细说明。完整的 MSER 提取过程总结在 Alg. 26.6 - 26.7 中。 #### 4. 组件大小变化（增长率） 选择一个区域作为最大稳定区域的主要标准是其在给定亮度级别范围内的增长率足够小且为局部最小值。 在树的任何向上路径上，组件的大小会不断增长，即任何树组件都小于其父组件。最小的组件位于叶节点，可能仅由单个像素组成，而最大的组件是根节点，包括所有图像像素。对于从叶节点到树的根节点的路径上的每个组件，可以计算其相对于子组件和父组件的增长率。 组件树 `T = ⟨E, r⟩` 由极值组件集合 E 和根组件 `r ∈ E` 组成。叶组件没有子组件，是树分支上的终端节点。从叶组件 `c0` 到树的根节点 `r = cn` 的路径是一个组件序列 `(c0, c1, ..., cn)`，其中 `par(ci) = ci+1`。沿着这样的路径，组件的大小逐渐增加，即 `|c0| ≤ |c1| ≤ ... ≤ |cn|`，并且亮度级别 `li = level(ci)` 严格增加，即 `l0 < l1 < ... < ln`。 组件大小与亮度级别的关系可以表示为以下函数： \[ size(l) := \begin{cases} 0 & \text{for } l < l0 \\ |ci| & \text{for } li ≤ l < li+1 \\ ∞ & \text{for } l ≥ ln \end{cases} \] 基于此函数，给定组件 `c` 在级别 `l = level(c)` 的大小变化定义为： \[ var(c) = \frac{size(l + ∆) - size(l)}{size(l)} \] 其中 `∆` 是亮度跨度参数。因此，`var(c)` 是组件 `c` 在 `∆` 个连续亮度级别上的相对区域增长率。由于组件大小在向上路径上总是增加的，`var(ci)` 的值在 `[0, ∞]` 范围内。如果组件大小在 `∆` 个亮度步骤内保持恒定，则变化为 0；如果 `level(c)` 距离根节点的级别少于 `∆` 个步骤，则变化为 `∞`。 以下是计算组件大小变化的示例代码（Alg. 26.6 中的 `CalculateVariations()` 函数）： ```python def CalculateVariations(E, ∆): for c in E: var( ```