戴幸奎+潘濤+尹思夢

（南京郵電大學(xué)，江蘇 南京 210046）

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

【關(guān)鍵詞】圖像編輯；梯度域合成；四叉樹

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

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

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

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

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

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

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

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

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

研究的內(nèi)容就是使用四叉樹的有效的梯度域合成算法的三個(gè)階段，相關(guān)詳細(xì)的論述會(huì)在后面相應(yīng)的文章里講述。

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

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

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

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

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

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