本文介绍一下中国大陆第一篇计算机视觉顶会的best paper，也是何恺明第一次在计算机视觉领域大放异彩的一篇经典之作—Dark Channel Prior。另外本文在Dark Channel Prior算法的基础上，介绍何恺明后续提出的Large-Kernel和Guided Filter两种加速方法。
Dark Channel Prior
图像去雾任务的目标是把一张雾图转变成一张无雾图和一张深度图。
Haze Imaging Model
一张雾图可以表示成haze imaging model：
其中I是hazy image，J是scene radiance，A是atmospheric light，t是传递系数。可以理解为I是雾图，J是无雾图，A是空气光图，这样子看就跟image matting公式非常类似(无雾图是背景，空气光图是前景)。其中深度图可以通过公式 得到。
Dark Channel Prior
kaiming he通过大量无雾图片统计发现了dark channel prior—在无雾图的局部区域中，3个通道的最小亮度值非常小接近于0(不包括天空区域)。
先通过min(r, g, b)，得到单通道图片，然后通过最小滤波器得到dark channel图片。
和haze imaging model相对应，可以把dark channel图片写成：
dark channel prior的统计规律表明，无雾图的dark channel应该是一个近似于全黑的图片，也就是无雾图的 。
可以对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，公式如下：
其中L是matting拉普拉斯矩阵，\tilde { \mathbf { t } }是优化前的transmission，t是优化后的transmission。
通过拉格朗日乘子法可以得到linear system：
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公式:
linear system一般可以通过Conjugate Gradients(CG)方法计算得到，算法如下：
CG是迭代计算的方法，计算复杂度由step4决定(矩阵运算)，假设kernel size为r，总的像素点数为N，那么step4的复杂度为 ，需要迭代 轮，总的计算复杂度为 。
Large-Kernel发现通过推导，step4可以只需要 复杂度，总的计算复杂度为 算法如下：
实际上，(4.13)和(4.14)中的所有运算都是滑动窗口的均值、方差或协方差，可以通过box filter统一计算得到，跟kernel size的大小无关。
实验结果可以看出，large kernel对去雾质量影响不大，但是能够极大的加快算法速度。
Guided Image Filtering
kaiming he发现t和 具有类似的强度，但是t和I的边缘保持一致。也就是说， 可以经过一个滤波过程转换成t，类似于保边滤波的效果。
linear system公式可以转化成：
这实际上是一个位置敏感的滤波过程:
是 的加权平均值，其中权重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的线性变换：
由于一个像素点会由多个窗口计算得到，一个简单的做法是对相关的窗口计算求平均：
通过推导，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?
