【深度学习】何恺明经典之作—2009 CVPR Best Paper

本文介绍一下中国大陆第一篇计算机视觉顶会的best paper，也是何恺明第一次在计算机视觉领域大放异彩的一篇经典之作—Dark Channel Prior。另外本文在Dark Channel Prior算法的基础上，介绍何恺明后续提出的Large-Kernel和Guided Filter两种加速方法。

Dark Channel Prior

图像去雾任务的目标是把一张雾图转变成一张无雾图和一张深度图。

Haze Imaging Model

一张雾图可以表示成haze imaging model：

$\mathbf { I } ( \mathbf { x } ) = \mathbf { J } ( \mathbf { x } ) t ( \mathbf { x } ) + \mathbf { A } ( 1 - t ( \mathbf { x } ) )$

其中I是hazy image，J是scene radiance，A是atmospheric light，t是传递系数。可以理解为I是雾图，J是无雾图，A是空气光图，这样子看就跟image matting公式非常类似(无雾图是背景，空气光图是前景)。其中深度图可以通过公式 $d = - \beta \ln t$ 得到。

Dark Channel Prior

kaiming he通过大量无雾图片统计发现了dark channel prior—在无雾图的局部区域中，3个通道的最小亮度值非常小接近于0(不包括天空区域)。

先通过min(r, g, b)，得到单通道图片，然后通过最小滤波器得到dark channel图片。

和haze imaging model相对应，可以把dark channel图片写成：

$\mathrm { J } ^ { \text {dark } } = \min _ { \Omega } \left( \min _ { \mathrm { c } } \mathrm { J } ^ { \mathrm { c } } \right)$

dark channel prior的统计规律表明，无雾图的dark channel应该是一个近似于全黑的图片，也就是无雾图的 $\min _ { \Omega } \left( \min _ { \mathrm { c } } \mathrm { J } ^ { \mathrm { c } } \right) \rightarrow 0$ 。

可以对haze imaging model进行等价变换，如上图所示。

由dark channel prior规律对t进行近似。A可以通过图片10%最亮区域得到近似值。也就是A已知，可以求解出t。

直接计算得到的t图片是粗糙的，没有办法细致的对雾进行区分。

上面也说到，haze imaging model公式和matting model公式非常类似，而image matting一种常用的做法是，输入图片和trimap图片(包含三部分区域: 白色前景、黑色背景和灰色未知)，用封闭式抠图算法得到alpha matting。仿照image matting的方式，图像去雾也可以通过输入图片和transmission图片(类似trimap图片)，得到refined transmission(类似alpha matting)。

image matting通常用马尔科夫随机场(MRF)来得到alpha matting，于是haze removal也可以通过MRF公式来得到优化后的transmission，公式如下：

$\mathrm { E } ( \mathbf { t } ) = \lambda \| \mathbf { t } - \tilde { \mathbf { t } } \| ^ { 2 } + \mathbf { t } ^ { \mathrm { T } } \mathbf { L } \mathbf { t }$

其中L是matting拉普拉斯矩阵，\tilde { \mathbf { t } }是优化前的transmission，t是优化后的transmission。

通过拉格朗日乘子法可以得到linear system：

$( \mathrm { L } + \lambda \mathrm { U } ) \mathbf { t } = \lambda \tilde { \mathbf { t } }$

linear system一般可以通过Conjugate Gradients方法计算得到。何恺明后续提出了Large-Kernel和Guided Filter两种方法对linear system计算进行加速。

通过上述的推导计算，A、I和t都已知，那么可以通过haze imaging model还原出去雾图片J。

Dark Channel Prior整体算法流程如下：

关于linear system如何推导，可以看以下资料

https://www.bilibili.com/video/BV1o54y1a7Yp?spm_id_from=333.999.0.0

Efficient Solutions to Refinement

何恺明后续提出Large-Kernel和Guided Filter两种方法对linear system计算进行加速。

A Large-Kernel-Based Linear Solver

上面得到的linear system公式:

$( \mathrm { L } + \lambda \mathrm { U } ) \mathbf { t } = \lambda \tilde { \mathbf { t } }$

linear system一般可以通过Conjugate Gradients(CG)方法计算得到，算法如下：

CG是迭代计算的方法，计算复杂度由step4决定(矩阵运算)，假设kernel size为r，总的像素点数为N，那么step4的复杂度为 $\mathrm { O } \left( r ^ { 2 } N \right)$ ，需要迭代 $\mathrm { O } \left( N ^ { \frac { 1 } { 2 } } / r \right)$ 轮，总的计算复杂度为 $\mathrm { O } \left( r ^ { 2 } N \right) \times \mathrm { O } \left( N ^ { \frac { 1 } { 2 } } / r \right) = \mathrm { O } \left( r N ^ { \frac { 3 } { 2 } } \right)$ 。

Large-Kernel发现通过推导，step4可以只需要 $\mathrm { O } ( N )$ 复杂度，总的计算复杂度为 $\mathrm { O } \left( N ^ { \frac { 3 } { 2 } } / r \right)$ 算法如下：

实际上，(4.13)和(4.14)中的所有运算都是滑动窗口的均值、方差或协方差，可以通过box filter统一计算得到，跟kernel size的大小无关。

实验结果可以看出，large kernel对去雾质量影响不大，但是能够极大的加快算法速度。

Guided Image Filtering

kaiming he发现t和 $\tilde { \mathbf { t } }$ 具有类似的强度，但是t和I的边缘保持一致。也就是说， $\tilde { \mathbf { t } }$ 可以经过一个滤波过程转换成t，类似于保边滤波的效果。

linear system公式可以转化成：

$\mathbf { t } = \lambda ( \mathrm { L } + \lambda \mathrm { U } ) ^ { - 1 } \tilde { \mathbf { t } }$

这实际上是一个位置敏感的滤波过程:

$t _ { i } = \sum _ { j } W _ { i j } \tilde { t } _ { j }$

$t_i$ 是 $\tilde { t } _ { j }$ 的加权平均值，其中权重Wij完全由图像I决定。也就是说图像I通过调整权值来“引导”滤波过程，确保t的边缘与I一致。

通过上述观察，kaiming he提出了一种新颖的guided filter来替代soft matting step，不需要求解linear system。并且进一步提出了一种跟kernel size r无关的O(N)算法，使得滤波器具有实时性。

Guided image filtering是结合两幅图片信息的过程，一个filtering input image(表示为p)和一个guide image(表示为I)生成一个filtering output image(表示为q)。p决定了q的颜色,亮度,和色调，I决定了q的边缘。对于图像去雾来说，transmission就是p，雾图就是I，refined transmission就是q。

假设q是图像I中以像素点k为中心的窗口w_k的线性变换：

$q _ { i } = a _ { k } I _ { i } + b _ { k } , \forall i \in w _ { k }$

由于一个像素点会由多个窗口计算得到，一个简单的做法是对相关的窗口计算求平均：

$\begin{aligned} q _ { i } & = \frac { 1 } { | w | } \sum _ { k : i \in w _ { k } } \left( a _ { k } I _ { i } + b _ { k } \right) \\ & = \bar { a } _ { i } I _ { i } + \bar { b } _ { i } \end{aligned}$

通过推导，guided filter只需要O(N)复杂度就能得到q，算法如下：

guided filter直接计算得到q，不需要迭代求解linear system。

实验结果可以看出，guided filter效果很好，比起large kernel速度更快。

总结

dark channel prior通过暗通道先验对haze imaging model进行化简，近似计算得到粗糙的transmission，然后将haze imaging model和matting model联系起来，巧妙的将图像去雾问题转化为抠图问题，得到refined transmission，精彩！large-kernel在CG算法的基础上通过公式推导，避免了kernel size对计算复杂度的影响，从而加快了linear system的计算速度；而guided filter则通过公式转换，和滤波联系起来，提出新颖的guided filter，巧妙的避开了linear system的计算过程，极大加快了transmission优化的速度。

不得不说kaiming he的科研嗅觉太敏锐了，做haze removal可以联想到和matting的关系，并且发现了dark channel prior，然后通过扎实的数理功底，找出soft matting速度优化的可能性，并且通过filter的启发，找出O(N)解法，简直太神了！

Reference

http://kaiminghe.com/publications/thesis.pdf

http://kaiminghe.com/publications/pami10dehaze.pdf

http://kaiminghe.com/cvpr09/cvpr09slides.pdf

http://kaiminghe.com/publications/cvpr10matting.pdf

http://kaiminghe.com/publications/pami12guidedfilter.pdf

http://kaiminghe.com/eccv10/eccv10ppt.pdf

https://www.cs.huji.ac.il/~csip/iterative.pdf

http://people.csail.mit.edu/alevin/papers/Matting-Levin-Lischinski-Weiss-CVPR06.pdf?


往期精彩回顾


    




适合初学者入门人工智能的路线及资料下载
机器学习及深度学习笔记等资料打印
机器学习在线手册



    
深度学习笔记专辑
《统计学习方法》的代码复现专辑
AI基础下载
黄海广老师《机器学习课程》视频课
黄海广老师《机器学习课程》711页完整版课件
本站qq群851320808，加入微信群请扫码：

【深度学习】何恺明经典之作—2009 CVPR Best Paper | Dark Channel Prior

Dark Channel Prior

Efficient Solutions to Refinement

总结