[發明專利]基于矩陣分解的圖像無縫克隆方法

在審

• 申請號: 201410072592.8
• 申請日: 2014-02-28
• 公開（公告）號: CN103839220A
• 公開（公告）日: 2014-06-04
• 發明（設計）人: 張丹;董建鋒;張大龍;李盼;趙磊;許端清
• 申請（專利權）人: 浙江大學
• 主分類號: G06T1/00
• 分類號: G06T1/00;G06T5/00
• 代理公司: 杭州天勤知識產權代理有限公司 33224
• 代理人: 胡紅娟

技術領域

本發明涉及計算機圖像領域，尤其涉及一種基于矩陣分解的圖像無縫克隆方法。

背景技術

近幾年，梯度域方法被廣泛運用于圖像處理領域中，包括本征圖像復原、無縫克隆和圖像拼接領域。這些算法的求解通常是解一個大型稀疏線性系統：泊松方程。但是，解泊松方程是一個計算密集型和內存密集型任務，不適合實時圖像編輯。同時，在處理大規模圖像時，如百萬像素圖，甚至是，億像素圖像，這個問題就顯得異常突出。為了解決這個問題，研究人員已經提出了各種各樣的方法。這些方法大致可以分為兩類：基于退化空間的求解器和基于數值分析的求解器。

對第一類，基于退化空間的求解器，一些算法將全分辨率圖像轉換到退化空間，從而大量減少內存開銷和計算開銷。第二類基于數值分析的求解器可以細分為兩個子類：直接解決器和迭代解決器。Pardiso，MUMPS，和SuperLU屬于直接解決器。而共軛梯度，多重網格法和串流多重網格法是比較常用的迭代解決器。直接法的思想是，經過有限步算術計算，可求得方程的精確解的方法，但由于實踐中有四舍五入的存在，這類方法也只能得到近似解，直接法最基本的是高斯消去法。而直接解決器的可擴展性差，不適合求解大型線性系統。迭代法的思想是，采用某種極限過程逐步逼近線性方程的精確解，迭代法需要的計算機存儲單元較少、程序設計簡單，但是迭代解決器不是很健壯，收斂速度慢。

發明內容

針對現有圖像無縫克隆方法技術的不足，本發明提供了一種基于矩陣分解的圖像無縫克隆方法。

一種基于矩陣分解的圖像無縫克隆方法，包括：

（1）根據源圖像中克隆區域的梯度域和目標圖像中融合區域的梯度域構建泊松方程，并根據泊松方程得到對應的拉普拉斯方程；

（2）根據所述的拉普拉斯方程構建原始線性系統和原始線性系統方程；

（3）對所述原始線性系統方程的系數矩陣進行分解得到一個帶狀對角矩陣和殘余矩陣，并根據克隆區域的形狀將所述的帶狀對角矩陣劃分為若干個小帶狀對角矩陣；

（4）將各個小帶狀對角矩陣分配到GPU的各個線程，結合殘余矩陣求解得到融合區域中各個像素點相對于克隆區域中相應像素點的初始像素補償值；

（5）將融合區域中所有像素點相對于克隆區域中相應像素點的初始像素補償值作為原始線性系統的初始輸入，通過直接法迭代得到融合區域中所有像素點相對于克隆區域中相應像素點的最終像素補償值；

（6）以融合區域中各個像素點相對于克隆區域中相應像素點的最終像素補償值與源圖像中該像素點的像素值的和作為融合區域中相應像素點的像素值，完成圖像的無縫克隆。

所述步驟（1）中源圖像中的克隆區域與目標圖像中的融合區域的大小和形狀相同。

無縫克隆法的關鍵是，尋找一個函數滿足目標圖像中克隆區域（融合區域）的邊界條件，且目標圖像中克隆區域的梯度域盡可能與源圖像的梯度域相同。

所述步驟（5）中通過直接法迭代得到融合區域中所有像素點相對于克隆區域中相應像素點的最終像素補償值，即將內部迭代輸出的克融合區域中所有像素點相對于克隆區域中相應像素點的最終像素補償值作為原始線性系統的初始輸入。

本發明的圖像無縫克隆方法，使用梯度域方法構建泊松方程，并得到原始線性系統方程，對原始線性系統的系數矩陣進行分解，產生大小大致相同的帶狀對角矩陣和殘余矩陣。根據克隆區域的形狀將帶狀對角矩陣劃分為小帶狀對角矩陣并分配給GPU的不同線程中進行計算，充分利用了GPU的數據并行處理能力，大大提高了運算速率，使實時圖像處理成為可能，且內存消耗低，可擴展到廣泛的運用程序中。且通過將泊松方程產生的線性系統方程的系數矩陣進行分解，對每一個分解得到的小型矩陣采用并行處理迭代操作，并在得到融合區域中各個像素點的初始像素補償值，將所有像素點的初始像素補償值作為原始系統的初始值（即輸入）代入原始線性系統方程直接求解，在外部迭代器中執行一個直接法計算全解，當外部迭代收斂時，完成求解，可以克服直接法和迭代法的缺點：比直接解決器的可擴展性更好，比傳統預處理迭代解決器更健壯。

所述步驟（3）中根據公式：

A=D+R

將原始線性系統的系數矩陣A劃分為帶狀對角矩陣D和殘余矩陣R，具體如下：將系數矩陣A的每一行的第一個和最后一個不為零的元素設為零，得到帶狀對角矩陣D，保留系數矩陣A中每一行的第一個和最后一個不為零的元素，其余值設為零，得到殘余矩陣R。

所述步驟（3）通過以下步驟將帶狀對角矩陣劃分為若干個小帶狀對角矩陣：

（3-1）判斷克隆區域是否為規則區域：