—— 一篇曾经在middlebury上达到SoT的论文，代价聚合用的guided filter，逻辑清晰，性能不够快，但paper从更高的角度来看计算机视觉中的立体匹配、光流以及图像分割，值得一读

嗯，读完了，有种任督二脉被打通的感觉，把这两年多接触到的词，陌生的，熟悉的，全都连起来了

前言

1. 作者指出以下几个领域的算法均可总结为label-based：
   • 立体匹配(stereo matching)
   • 光流(optical flow)
   • 图像分割(image segmentation)

2. label-based类的方法算法本质：

   • 构建三维代价立方体(cost volume)，存储着图像坐标为\((x, y)\)，分配label为\(l\)的代价；

     ——对于立体匹配来说，代价值就是左右视图像素点对之间的相关性

   • 而后，目标就是找到一个最优的label assignment，满足以下条件：

   • obeys the label costs
   • spatially smooth
   • label changes are aligned with edges in the image

   • 为获得满足上述条件的最优的label assignment，通常会有以下手段：

     构建Conditional Markov Random Field将label costs编码成一个由data term和pairwise smoothness term构成的能量函数，并基于诸如graph cut或者belief propagation等方法来最小化此能量函数

3. 上述算法逻辑实际上是全局法求解的本质，特点是速度慢，难以处理大分辨率图像和较大的label空间，因此，有以下两种方式来做加速：

   • 将问题转化为凸优化：针对不同问题加额外的限制，来将问题转化为凸优化问题，以在GPU上得到加速，但存在以下问题：
     • 增加额外的限制，使得模型难以cover住一些困难场景；
     • 为保证平滑项的convex性，可能会造成结果的过度平滑；
   • 使用局部滤波来逼近：通过设计窗口形状、大小以及滤波权重在窗口内实现局部最优代价聚合（窗口外的像素可看做权重为0），优点是速度快，缺点是结果为局部最优

Abstract

• 主要思想：

  通过构建最小生成树来完成最优代价聚合，树节点为像素点，连接树节点的边权重由树节点间的相似度决定

• 贡献点：

  1. 提出了一套filter-based的框架来求解诸如立体匹配，光流以及图像分割等label-based问题
  2. 应用到立体匹配，可以达到当时SoT的real-time效果
  3. 应用到光流，可以处理fine motion structure和large displacement
  4. 应用到图像分割可以得到一个快速且高质量的interactive图像分割结果

• 时间性能：

  1. 硬件：1.8 GHz 酷睿i7 CPU，4 GB缓存
  2. 数据集：middlebury
  3. 耗时：90ms

• future:

  如guided filter原文所述，作者也点出，guided filter可以逼近全局法的一个原因就是：

  the guided filter is one step of a conjugate gradient solver of a particular linear system.

  又一次点出filter-based和energy-based之间的关系...

• 关键文献：

  【11】K. He, J. Sun, and X. Tang. Guided image filtering. In ECCV, 2010.

  【31】K. Yoon and S. Kweon. Adaptive support-weight approach for correspondence search. PAMI, 2006.

研究背景

算法思想

We consider a general labeling problem, where the goal is to assign each pixel \(i\) with coordinates \((x, y)\) in the image \(I\) to a label \(l\) from the set \(L = {1,...,L}\).

代价聚合本质：

\[C_{i, l}^{'} = \sum_j{W_{i, j}(I)C_{j, l}}\tag{1}\]

本文权重计算方式使用的是guided filter：

\[W_{i, j} = \frac{1}{|w|^2}\sum_{k:(i, j) \isin w_k}(1 + \frac{(I_i - \mu_k)(I_j - \mu_k)}{\sigma_k^2 + \epsilon})\tag{2}\]

guided filter保边平滑本质主要来源于:

\[\frac{(I_i - \mu_k)(I_k - \mu_k)}{\sigma_k^2 + \epsilon}\]

当\(\sigma_k^2 \ll \epsilon\)足够大时，邻域间的颜色相似度对权重的影响就会减小，整个权重分布接近于均匀分布，guided filter的表现就越接近于box filter

guided filter的矢量化形式(复杂度为\(O(N)\)的体现)：

\[W_{i, j} = \frac{1}{|w|^2}\sum_{k:(i, j) \isin w_k}(1 + (I_i - \mu_k)^T(\Sigma_k + \epsilon U)^{-1}(I_j - \mu_k))\tag{3}\]

应用

Stereo Matching

算法流程：

1. 代价计算： SAD + gradient
2. 代价聚合：本文方法
3. 视差计算：WTA
4. 后处理：
   • 遮挡检测和补洞：LR-Check, 并以非遮挡区域的最小视差进行填充

   • weighted median filter：权重中值滤波，权重使用的是双边权重...

     \[W_{i, j}^{bf} = \frac{1}{K_i}exp(-\frac{|i - j|^2}{\sigma_s^2})exp(-\frac{|I(i) - I(j)|^2}{\sigma_c^2})\tag{4}\]

一波骚操作...

左右视图的代价聚合是guided filter的权重是将左右视图合成成一张6通道的图来矢量化计算的...

Optical Flow

算法流程：

1. 代价计算： SAD + gradient
2. 代价聚合：本文方法
3. 视差计算：WTA
4. 后处理：
   • 遮挡检测和补洞：LR-Check, 用weighted median filter来补洞，权重使用的是guided filter的权重

   • 亚像素增强(目前还不懂咋操作，先引用起作者原话，后面再来研究)：

     1. Subpixel precision: To find sub-pixel accurate flow vectors, we follow [23] and simply upscale the input images using bicubic interpolation.
     2. This increases the size of the cost volume in the label dimension (but not in the x and y dimensions) and hence raises the running time.
     3. In practice, we found that smoothing the final flow vectors with the guided filter can compensate for a lower upscaling factor.
     4. We empirically found that an upscaling factor of 4 gives vi- sually pleasing results, but in this paper we upscale by a factor of 8 to demonstrate the best possible performance.

Interactive Image Segmentation

1. 代价计算(核心)

   • 根据用户输入的前背景信息，构造前景和背景直方图：\(\theta^F\) 和 \(\theta^B\)

   • 每个直方图包含\(K\)个bins，里边用于统计像素点\(i\)为背景的情况

   • 也可接受用户输入Bounding box，box内部的像素点用于构造\(\theta^F\)，box外部的像素点用于构造\(\theta^B\)

代价函数定义为:

\[C_{i,l} = 1 - \theta_{b(i)}^l\]

对于二分类问题，可将代价函数\(C_{i, l}\)降为两维，\(C_i\)表示一个像素点属于前景区域的代价:

\[C_i = 1 - \frac{\theta_{b(i)}^F}{\theta_{b(i)}^F + \theta_{b(i)}^B}\tag{5}\]

1. 代价聚合：本文方法

2. 图像分割：\(C_i < 0.5\)，则将其置为前景，\(C_i > 0.5\)，则将其置为背景

对于Bounding box方法，作者用了5次迭代更新颜色模型来增强代价计算的精度

NOTE

实验部分说：效果和graph cut相当，性能是 5ms vs 300ms(425ms)，惊呆了我和我的小伙伴...