基于四叉樹的高效梯度域圖像融合

戴幸奎+潘濤+尹思夢

（南京郵電大學，江蘇 南京 210046）

【摘 要】隨著科技的不斷發(fā)展，數(shù)千萬像素的圖片很常見，由于面對這種大數(shù)量級的圖片，傳統(tǒng)的利用泊松圖像編輯求解圖像融合的方法已不再適用。雖然梯度域合成是強大的和廣泛使用，但它具有較差的可擴展性。計算n像素復合需要求解具有n個變量的線性系統(tǒng)，當對于實際上常見的數(shù)千萬像素復合材料執(zhí)行時，解決這樣大的系統(tǒng)，其求解的線性方程規(guī)模太大能快速地壓倒標準計算機的主存儲器，且耗時太長，甚至要占用很大的內存。為了降低泊松方程構建的線性系統(tǒng)的規(guī)模，提高運行效率，節(jié)約時間，本文描述了一種提高梯度域合成效率的分層方法，在此引入了四叉樹這種層級空間數(shù)據(jù)結構，通過對融合圖像的分解，選擇出少量的像素點求解，最終通過線性插值的方法，補全其余像素點的差值，完成圖像合成，來近似達到求解泊松方程構建完整線性系統(tǒng)的效果。

【關鍵詞】圖像編輯；梯度域合成；四叉樹

現(xiàn)在是信息時代，圖形是人們獲取信息、表達信息、傳遞信息的一種手段。隨著數(shù)字圖像處理技術的興起，人們生活在不知不覺間發(fā)生了翻天覆地的變化。圖像、圖形逐漸成為傳播信息的主要的載體，雖然人眼識別高，可以找到成千上萬的顏色，但在許多情況下，對圖像來說人眼模糊甚至不可見。數(shù)字圖像處理技術可以幫助人們理解世界更客觀、準確地。因此，數(shù)字圖像處理技術顯得尤為重要。對圖像處理有較好的理解。

圖像合成是通過將源圖像中的對象或區(qū)域嵌入到目標圖像中，生成新的圖像的一種解決問題的基本方案。在合成圖像的過程中，為了使合成的圖像更加自然，合成邊界必須保持無縫。然而，如果原始圖像和目標圖像具有明顯不同的紋理特征，那么直接合成的圖像就會有一個清晰的邊界。為了解決這一問題，一種利用構造的泊松方程求解像素最優(yōu)值的方法就這樣誕生了。這種方法不僅可以很好地融合源圖像梯度信息，并且可以很好地融合源圖像和目標圖像的背景。該方法根據(jù)用戶指定的邊界條件求解泊松方程，在梯度域上實現(xiàn)連續(xù)性，實現(xiàn)邊界的無縫融合。泊松圖像編輯的主要思想是重建圖像像素的復合區(qū)域，其采用了基于圖像梯度信息和目標圖像的邊界信息的插值方法。Poisson圖像編輯是計算攝影和視頻中最廣泛使用的算法之一；但是它不能很好地擴展到今天的百萬像素數(shù)字圖像。

隨著科學技術的發(fā)展，如今的圖片數(shù)百萬甚至上千萬像素都很常見。隨著像素數(shù)量級的增大，Poisson圖像編輯在時間和空間方面，求解線性系統(tǒng)所需的時間更長，需要的空間更大。因此，盡管梯度域技術的廣泛適用性，但這種差的可擴展性限制了其在數(shù)字攝影軟件中的采用。

在2007年Aseem Agarwala 發(fā)表了Efficient gradient-domain compositing using quadtrees.這篇論文在Poisson圖像編輯的基礎上引入了四叉樹，減小了求解的線性系統(tǒng)的規(guī)模，不但提高了圖像合成的效率，還減小了求解線性系統(tǒng)所需的時間空間。

本文研究的目的與意義了解了圖像拼接的相關知識，學習和掌握數(shù)字圖像處理的基本理論和方法；學習和掌握matlab等工具的使用；掌握基于四叉樹的梯度域圖像拼接算法的基本思想和處理流程；用實際圖像進行大量的實驗驗證和分析；最后完成這個算法。

Efficient gradient-domain compositing using quadtrees這篇論文就是關于基于四叉樹的梯度域圖像拼接算法，也是我的本文研究。而我的研究就是，查閱相關文獻，學習理解文獻的圖像處理算法，并完成算法的實現(xiàn)。

本文研究的目的與意義也是鍛煉自己綜合分析和解決問題的能力和獨立工作能力、組織管理和社交能力，也是學習深化、拓寬、綜合運用所學知識的重要過程；還是我對學習、研究與實踐成果的全面總結。其次綜合運用所學基礎理論、專業(yè)知識及基本技能來分析和解決實際問題的能力。同時對于增強我的事業(yè)心和責任感，提高我的全面素質具有重要意義。

使用四叉樹的有效的梯度域合成算法是建立在Poisson圖像編輯的基礎之上的。由于圖片像素數(shù)量級的提升，原有的Poisson圖像編輯在時間空間上逐漸無法滿足圖片合成的需求。由此引入了四叉樹這個概念，對圖像進行劃分，從而選擇部分有效的像素點去求解比原來較小的線性系統(tǒng)，最后通過線性插值，雙線性插值等方法求解所有的像素點的值。

此算法可以分為三個階段：構造四叉樹；求解線性系統(tǒng)；線性插值。本論文講述的算法的步驟，第一步是關于四叉樹的原理，四叉樹的構建以及四叉樹如何劃分圖像，選擇像素點等等。第二步是關于泊松圖像編輯方面的相關知識，了解泊松方程的構建與計算，從而為后續(xù)梯度域合成做準備。第三步關于求解Poisson圖像編輯的線性系統(tǒng)，獲得算選像素點的初始值與合成后的差值，通過線性插值的方法計算所有像素的差值，最終完成梯度域的合成。通過做大量的實驗，然后對算法和實驗進行分析和論證，從而發(fā)現(xiàn)問題，查找原因。至此就完成了圖像的合成。第五章是在完成算法的基礎上，通過大量圖片來進行相應的實驗，通過分析和論證得出相應的結論，由此驗證算法效果。

研究的內容就是使用四叉樹的有效的梯度域合成算法的三個階段，相關詳細的論述會在后面相應的文章里講述。

圖像融合利用泊松圖像編輯完成，他是一種利用構造的泊松方程求解像素最優(yōu)值的方法。這種方法不僅可以很好地融合源圖像梯度信息，并且可以很好地融合源圖像和目標圖像的背景。該方法根據(jù)用戶指定的邊界條件求解泊松方程，在梯度域上實現(xiàn)連續(xù)性，實現(xiàn)邊界的無縫融合。泊松圖像編輯的主要思想是重建圖像像素的復合區(qū)域，其采用了基于圖像梯度信息和目標圖像的邊界信息的插值方法。

該方法通過將可能出現(xiàn)在合成區(qū)域之間的邊界處的高頻偽像轉換成分布在圖像上的低頻變化，來隱藏合成圖像區(qū)域之間的接縫。

我們的方法在梯度域中合成圖像區(qū)域非常有效；一個明顯的擴展是對視頻執(zhí)行梯度域合成，其中可擴展性關注甚至更大。這個擴展應該是直接使用八叉而不是四叉樹。

我們的技術是有效的，因為我們可以創(chuàng)建一個初始解到線性系統(tǒng)，其殘差是稀疏的。同樣可以說幾個其他梯度域問題，如陰影去除，去除閃爍圖像中的反射，以及照相表面的再現(xiàn)，因為在這些情況下，期望的梯度場大部分匹配原始圖像，除了被衰減或設置為零的某些梯度。這一觀察表明，我們的方法可以用來提高效率。然而，它不能直接應用于沒有這樣的初始解的其他梯度域問題。

我們還計劃探索一個擴展，可以允許更有效的外核重建從一般梯度場。可以針對圖像的每個圖塊獨立地計算解，從而創(chuàng)建具有僅沿著圖塊邊界的非零殘差的初始解。然后，可以沿著這些瓦片邊界對四叉樹進行細分，并且用于計算對初始解的偏移。

雖然梯度域合成是一種非常有效的技術，用于合成圖像和視頻區(qū)域，它不是像以前簡單地使用它用于大分辨率的圖像的影像數(shù)據(jù)成像。我們的梯度域合成的近似方法，在產生視覺上相同的結果的同時，還可以在令人驚訝的很少的時間和記憶中計算，即使對于非常大的復合材料。我們希望我們的技術將成為解決計算攝影和視頻算法的可擴展性的技術之一。