2017-12-30-003-泊松融合及其優化演算法

圖像融合，就是把不同的圖像的不同部分放在一起，形成一張新的圖像。融合得越自然，演算法就越好。想到融合，最簡單的演算法就是在融合邊界把兩張圖像的透明度線性相加（Alpha圖像融合），形成一張新的圖像，比如這幅著名的蘋果橘子圖：

泊松融合是圖像處理領域非常著名的圖像融合演算法，自從2003年在論文 Poisson Image Editing 中提出以後，取得了極大的成功，並且在此基礎上進行許多改進的研究。

關於泊松融合的相關知識網路上面有很多的資源可以參考，也可以查看 論文 或者書籍 Computer Version for Visual Effects（這本書非常棒，一生推，可以下載PDF並且YouTube有作者的相關課程視頻，作者講課也非常好）中的相關章節，本文主要介紹泊松融合演算法的優化。

泊松融合的本質是求解線性方程組，其演算法複雜度為O（ N），其中：N為融合區域的像素點個數。雖然求解線性方程組的優化方法有很多（牛頓迭代法、高斯-賽德爾迭代法、雅克比迭代法，梯度下降法，共軛梯度法等）但是放在圖像融合這個大背景之下，便需要具體問題具體分析。因此，許多圖像處理領域的大牛學者又提出了許多泊松融合的加速演算法，下面按照時間順序為大家介紹。

一、基於四叉樹的加速

該演算法是Adobe公司的圖像處理大牛 Aseem Agarwala 在2007年的SIGGRAPH上提出的泊松融合的加速演算法，並運用到當時的 PhotoShop 軟體之中，論文名稱為：Efficient Gradient-Domain Compositing Using Quadtrees

演算法的複雜度：O（ ），其中n為融合區域的像素點的個數。

該方法的核心是通過減少最終線性方程組中未知數的個數提高泊松融合的效率。下面首先簡介一下什麼是四叉樹分解：

1、四叉樹分解示意圖：

2、四叉樹分解後，如何操作？

決定參與構成最終線性方程組的像素點。

①：只有為十字交叉處的點參與運算；

②：丁字路處的交點不參與運算；

③：其餘線路上的點都不參與運算；

3、空白之處的像素點不參與運算，如何獲得如何後的灰度值取值？

使用插值演算法獲得空白處的像素點的灰度值（插值演算法比求解線性方程組來說效率要高很多）

上面只列出了論文的核心思想，細節問題可詳細閱讀論文。

論文主頁：Efficient Gradient-Domain Compositing Using Quadtrees

論文開源實現（非作者）：xin-xinhanggao/efficient_quadtree

二、基於MVC的泊松融合加速

該方法是 Zeev Farbman 在2009年的SIGGRAPH上面提出的基於Mean-Value Coordinates方法的泊松融合加速演算法，論文名稱：Coordinates for Instant Image Cloning

這個論文論點是：將泊松方程轉換成拉普拉斯方程，然後再用Mean-Value Coordinates近似求解。整個問題就變成了插值問題，問題複雜度變成了O(m)，其中，m是要粘貼圖像外輪廓的像素數，並且一般情況下都有m << n（融合區域像素點個數）。演算法極其簡單，完全可以實時的交互運行。具體細節可以閱讀原文查看。

論文主頁：http://www.cs.huji.ac.il/~danix/mvclone/

開源代碼實現：https://github.com/jelinson/MVC

開源代碼實現：https://github.com/pablospe/MVCDemo

三、基於卷積金字塔的泊松融合加速

基於卷積金字塔的加速演算法與基於MVC泊松融合加速演算法的作者都是 Zeev Farbman（大牛佩服膜拜），該演算法是其在SIGGRAPH Asia 2011上發表的論文 Convolution Pyramids 中提出的。並且基於卷積金字塔的演算法除了應用於泊松圖像融合加速之外，還可以用於梯度域集成、離散數據插值等方面。

論文的主頁（包括官方代碼）：http://www.cs.huji.ac.il/labs/cglab/projects/convpyr/

如果您有發現比以上幾種演算法更快的泊松融合加速演算法，歡迎留言或者私信告訴我，感激不盡！

PS：如果您在閱讀的過程中，發現了文章中的錯誤，歡迎留言或者私信指出。謝謝啦！