本文介紹一下中國大陸第一篇計算機視覺頂會的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是傳遞系數?？梢岳斫鉃镮是霧圖，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?

往期精彩回顧適合初學者入門人工智能的路線及資料下載機器學習及深度學習筆記等資料打印機器學習在線手冊深度學習筆記專輯《統計學習方法》的代碼復現專輯 AI基礎下載黃海廣老師《機器學習課程》視頻課黃海廣老師《機器學習課程》711頁完整版課件

本站qq群851320808，加入微信群請掃碼：

總結

以上是生活随笔為你收集整理的【深度学习】何恺明经典之作—2009 CVPR Best Paper | Dark Channel Prior的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。