• 问答
  • 技术
  • 实践
  • 资源
何恺明经典之作—2009 CVPR Best Paper | Dark Channel Prior
技术讨论

作者丨Smarter
来源丨Smarter
编辑丨极市平台

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

Dark Channel Prior

img

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

Haze Imaging Model

img

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

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

Dark Channel Prior

img

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

img

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

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

dark channel prior的统计规律表明,无雾图的dark channel应该是一个近似于全黑的图片,也就是无雾图的 。

img

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

img

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

img

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

img

上面也说到,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拉普拉斯矩阵, 是优化前的transmission,t是优化后的transmission。

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

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

img

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

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

img

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

11.Image Matting(抠图算法)哔哩哔哩bilibili

Efficient Solutions to Refinement

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

A Large-Kernel-Based Linear Solver

上面得到的linear system公式:

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

img

CG是迭代计算的方法,计算复杂度由step4决定(矩阵运算),假设kernel size为r,总的像素点数为N,那么step4的复杂度为 ,需要迭代 轮,总的计算复杂度为 。

img

Large-Kernel发现通过推导,step4可以只需要 复杂度,总的计算复杂度为 算法如下:

img

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

img

实验结果可以看出,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)算法,使得滤波器具有实时性。

img

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,算法如下:

img

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

img

实验结果可以看出,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

kaiminghe.com/publications/thesis.pdf

untitled (kaiminghe.com)

kaiminghe.com/cvpr09/cvpr09slides.pdf

kaiminghe.com/publications/cvpr10matting.pdf

kaiminghe.com/publications/pami12guidedfilter.pdf

eccv10ppt.pdf (kaiminghe.com)

iterative.pdf (huji.ac.il)

[people.csail.mit.edu/alevin/papers/Matting-Levin-Lischinski-Weiss-CVPR06.pdf?](

  • 0
  • 0
  • 170
收藏
暂无评论