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

戴幸奎+潘濤+尹思?jí)?/p>

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

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

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

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

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

隨著科學(xué)技術(shù)的發(fā)展，如今的圖片數(shù)百萬(wàn)甚至上千萬(wàn)像素都很常見。隨著像素?cái)?shù)量級(jí)的增大，Poisson圖像編輯在時(shí)間和空間方面，求解線性系統(tǒng)所需的時(shí)間更長(zhǎng)，需要的空間更大。因此，盡管梯度域技術(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)知識(shí)，學(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)。

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

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

此算法可以分為三個(gè)階段：構(gòu)造四叉樹；求解線性系統(tǒng)；線性插值。本論文講述的算法的步驟，第一步是關(guān)于四叉樹的原理，四叉樹的構(gòu)建以及四叉樹如何劃分圖像，選擇像素點(diǎn)等等。第二步是關(guān)于泊松圖像編輯方面的相關(guān)知識(shí)，了解泊松方程的構(gòu)建與計(jì)算，從而為后續(xù)梯度域合成做準(zhǔn)備。第三步關(guān)于求解Poisson圖像編輯的線性系統(tǒng)，獲得算選像素點(diǎn)的初始值與合成后的差值，通過(guò)線性插值的方法計(jì)算所有像素的差值，最終完成梯度域的合成。通過(guò)做大量的實(shí)驗(yàn)，然后對(duì)算法和實(shí)驗(yàn)進(jìn)行分析和論證，從而發(fā)現(xiàn)問(wèn)題，查找原因。至此就完成了圖像的合成。第五章是在完成算法的基礎(chǔ)上，通過(guò)大量圖片來(lái)進(jìn)行相應(yīng)的實(shí)驗(yàn)，通過(guò)分析和論證得出相應(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)邊界的無(wú)縫融合。泊松圖像編輯的主要思想是重建圖像像素的復(fù)合區(qū)域，其采用了基于圖像梯度信息和目標(biāo)圖像的邊界信息的插值方法。

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

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

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

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

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