2017-12-30-003-泊松融合及其最佳化演算法
影象融合，就是把不同的影象的不同部分放在一起，形成一張新的影象。融合得越自然，演算法就越好。想到融合，最簡單的演算法就是在融合邊界把兩張影象的透明度線性相加（Alpha影象融合），形成一張新的影象，比如這幅著名的蘋果橘子圖：
影象的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/mv
clone/
開原始碼實現：
https：//
github。com/jelinson/MVC
開原始碼實現：
https：//
github。com/pablospe/MVC
Demo
三、基於卷積金字塔的泊松融合加速
演算法示意圖
基於卷積金字塔的加速演算法與基於MVC泊松融合加速演算法的作者都是 Zeev Farbman（大牛佩服膜拜），該演算法是其在SIGGRAPH Asia 2011上發表的論文 Convolution Pyramids 中提出的。並且基於卷積金字塔的演算法除了應用於泊松影象融合加速之外，還可以用於梯度域整合、離散資料插值等方面。
論文的主頁（包括官方程式碼）：
http：//www。
cs。huji。ac。il/labs/cgla
b/projects/convpyr/
如果您有發現比以上幾種演算法更快的泊松融合加速演算法，歡迎留言或者私信告訴我，感激不盡！
PS：如果您在閱讀的過程中，發現了文章中的錯誤，歡迎留言或者私信指出。謝謝啦！
