基于自由像片重疊區(qū)域的算法研究

馬毅蕊，鄧 鋼，呂金輝

(昆明理工大學(xué) 國(guó)土資源工程學(xué)院地理信息系統(tǒng)系，云南 昆明 650093)

圖像拼接技術(shù)是將一組存在重疊部分的圖像序列進(jìn)行空間匹配對(duì)準(zhǔn)，經(jīng)重采樣融合后形成一幅包含各圖像序列信息的寬視角場(chǎng)景、完整、高清晰的新圖像的技術(shù)[1]。該技術(shù)廣泛應(yīng)用在攝影測(cè)量學(xué)、虛擬現(xiàn)實(shí)技術(shù)、遙感影像處理、醫(yī)學(xué)圖像分析和計(jì)算機(jī)圖形學(xué)等領(lǐng)域。

一般來(lái)說(shuō)，圖像拼接流程包括圖像預(yù)處理、圖像配準(zhǔn)和圖像合成三個(gè)步驟。在進(jìn)行多幅圖像的拼接時(shí)，首先應(yīng)確定標(biāo)準(zhǔn)像幅，標(biāo)準(zhǔn)像幅往往選擇處于研究區(qū)中央的圖像，以后的拼接工作都以此圖像作為基準(zhǔn)進(jìn)行；其次確定拼接的順序，即以標(biāo)準(zhǔn)像幅為中心，由中央向四周逐步進(jìn)行。值得注意的是，拼接工作的著眼點(diǎn)是全部待拼接的圖像，而落腳點(diǎn)卻總是兩幅相鄰圖像間的拼接。遙感圖像拼接工作主要是基于相鄰圖像的重疊區(qū)，無(wú)論是色調(diào)調(diào)整還是幾何鑲嵌，都是將重疊區(qū)域作為基準(zhǔn)進(jìn)行的。重疊區(qū)域的確定是否準(zhǔn)確，直接影響拼接的效果[2]。本文結(jié)合計(jì)算機(jī)圖形學(xué)的知識(shí)，提出了一種確定自由像片重疊區(qū)域的算法。實(shí)驗(yàn)結(jié)果表明，該算法適合對(duì)多張影像進(jìn)行重疊區(qū)域的確定。

1 圖像配準(zhǔn)

圖像配準(zhǔn)主要指對(duì)參考圖像和待拼接圖像中的匹配進(jìn)行提取，在提取出的信息中尋找最佳的匹配，完成圖像間的對(duì)齊[1]。

本文通過(guò)仿射變換進(jìn)行圖像配準(zhǔn)，配準(zhǔn)后自由像片重疊區(qū)域的確定問(wèn)題就轉(zhuǎn)化為多邊形重疊區(qū)域的確定問(wèn)題，即兩個(gè)或多個(gè)面求交集的問(wèn)題。因攝影過(guò)程中像片的自由度較大，重疊部分可能是三邊形、四邊形，甚至是八邊形，故確定多邊形的重疊區(qū)域?qū)⑹且粋€(gè)較為復(fù)雜的過(guò)程，同時(shí)也增加了數(shù)據(jù)處理的難度。下面結(jié)合計(jì)算機(jī)圖形學(xué)的知識(shí)研究有關(guān)該問(wèn)題的一種通用算法[3]。

2 確定多邊形重疊區(qū)域的理論基礎(chǔ)

簡(jiǎn)單多邊形的一般定義是指不自相交的多邊形，它可以包含0個(gè)或多個(gè)空洞。確定兩個(gè)任意多邊形交、并、差的問(wèn)題既是計(jì)算幾何和計(jì)算機(jī)圖形學(xué)的基本問(wèn)題，也是遙感影像處理、GIS疊加分析的理論基礎(chǔ)[4]。本文討論的是比較簡(jiǎn)單的凸多邊形的情況。

在幾何造型中，通常利用集合運(yùn)算(交、并、差運(yùn)算)實(shí)現(xiàn)復(fù)雜形體的構(gòu)造，而集合運(yùn)算需要大量的求交運(yùn)算。求交時(shí)所用到的幾何元素大致可分為三類(lèi)：點(diǎn)、線(xiàn)、面。故在求交算法中，求交方法分為點(diǎn)點(diǎn)、點(diǎn)線(xiàn)、點(diǎn)面、線(xiàn)線(xiàn)、線(xiàn)面、面面六種。常用的求交有線(xiàn)與線(xiàn)的求交、線(xiàn)與面的求交和面與面的求交。多邊形與多邊形，即面與面之間的求交是最為復(fù)雜的一種。面與面求交的基本方法主要有代數(shù)方法、幾何方法、離散方法和跟蹤方法四種[5]。本文主要運(yùn)用跟蹤方法來(lái)實(shí)現(xiàn)多邊形的求交。該方法是通過(guò)先求出初始交點(diǎn)，然后從已知的初始交點(diǎn)出發(fā)，相繼跟蹤計(jì)算出下一交點(diǎn)，從而求出整條交線(xiàn)的方法。其中，跟蹤法的初始交點(diǎn)通常采用離散方法求得。

3 確定多邊形重疊區(qū)域的算法流程

自由像片重疊區(qū)域的確定為以后進(jìn)行圖像拼接奠定了良好的基礎(chǔ)。因此有必要對(duì)多邊形重疊區(qū)域的確定問(wèn)題進(jìn)行詳細(xì)的研究。圖像的重疊部分可以是規(guī)則的，也可以是不規(guī)則的，可以是由三條邊所圍成的圖像，也可以是由四條邊甚至更多條邊所圍成的圖像。為了確定多邊形的重疊區(qū)域，本文以相對(duì)比較簡(jiǎn)單且規(guī)則的四邊形為例來(lái)進(jìn)行討論。設(shè)有兩個(gè)四邊形 A={a1，a2，a3，a4}，B={b1，b2，b3，b4}， 其中 ai、bi(i=1、2、3、4)分別為四邊形A與B的頂點(diǎn)。兩頂點(diǎn)間的直線(xiàn)分別用Li、Ri表示(i為較小頂點(diǎn)標(biāo)號(hào))，兩個(gè)四邊形邊的交點(diǎn)表示為 Pij，其中i為左線(xiàn)段序號(hào)，j為右線(xiàn)段序號(hào)。兩四邊形的交集為P=A∩B={k|k∈A∧k∈B}，此交集即為重疊區(qū)域。

通過(guò)分析，對(duì)由兩幅圖像的重疊部分所構(gòu)成的多邊形區(qū)域進(jìn)行以下幾種情況的討論，重疊區(qū)域的頂點(diǎn)坐標(biāo)可通過(guò)計(jì)算獲得，并存儲(chǔ)在交點(diǎn)數(shù)組P[n]中。

(1)所構(gòu)成的多邊形區(qū)域只包含圖A的頂點(diǎn)。此時(shí)，P[n]中的點(diǎn)完全屬于圖A的頂點(diǎn)，則圖B完全覆蓋圖A，圖A為所求的重疊區(qū)域，如圖1所示。

(2)所構(gòu)成的多邊形區(qū)域只包含圖B的頂點(diǎn)。此時(shí)，P[n]中的點(diǎn)完全屬于圖 B，則圖 A完全覆蓋圖 B，圖 B為所求的重疊區(qū)域，如圖1所示。

(3)所構(gòu)成的多邊形區(qū)域由圖A和圖B邊的交點(diǎn)構(gòu)成。此時(shí)，P[n]中的點(diǎn)既有圖像A的頂點(diǎn)又有圖像B的頂點(diǎn)，還包含有圖像A與圖像B的邊的交點(diǎn)，則按照下述方法來(lái)確定重疊區(qū)域：首先找出一個(gè)交點(diǎn)，然后沿其中一條邊(重疊區(qū)域邊)的方向行進(jìn)。由L1可以找到頂點(diǎn)a2，再沿著L2找到P24，此時(shí)要更換交點(diǎn)的追蹤邊，然后轉(zhuǎn)換到R4邊上，找到b1點(diǎn)。依此進(jìn)行，直到最后的邊R1剛好與P11的R1邊連接，形成一個(gè)閉合區(qū)域，如圖2所示。

圖1 一圖完全覆蓋另一圖

圖2 圖A與圖B的重疊圖像

確定多邊形重疊區(qū)域的算法流程如圖3所示。

圖3 算法流程圖

4 確定多邊形重疊區(qū)域的算法描述

為了查找圖A與圖B的重疊區(qū)域，可以先將兩幅圖的頂點(diǎn)坐標(biāo)分別存入數(shù)組A-Point[n]和數(shù)組B-Point[n]中，并定義一個(gè)交點(diǎn)數(shù)組P[n]。該數(shù)組用來(lái)存放由圖A和圖B所構(gòu)成的重疊區(qū)域的所有交點(diǎn)。其中，存儲(chǔ)圖A和圖B各頂點(diǎn)的橫、縱坐標(biāo)以及交點(diǎn)數(shù)組P[n]的橫、縱坐標(biāo)的數(shù)據(jù)結(jié)構(gòu)可分別設(shè)計(jì)如下：

確定圖A與圖B的重疊區(qū)域的算法如下：

上述算法中，判斷交點(diǎn)數(shù)組中的所有點(diǎn)是否完全是圖A或圖B的頂點(diǎn)的方法大致有兩種：

(1)將P[n]中的每個(gè)點(diǎn)的橫、縱坐標(biāo)與圖 A或圖 B的各個(gè)頂點(diǎn)的橫、縱坐標(biāo)相比較，若它們的橫、縱坐標(biāo)值完全相同，則一幅圖完全覆蓋另一幅圖。

(2)判斷交點(diǎn)數(shù)組P[n]中的所有點(diǎn)是否是圖A或圖B的內(nèi)點(diǎn)。若P[n]中的所有點(diǎn)都是圖A的內(nèi)點(diǎn)，則圖A完全覆蓋圖 B，圖 B為重疊區(qū)域；若 P[n]中的所有點(diǎn)都是圖B的內(nèi)點(diǎn)，則圖B完全覆蓋圖A，圖A為重疊區(qū)域(注：因點(diǎn)與多邊形的位置關(guān)系有三種，即：點(diǎn)在多邊形內(nèi)、點(diǎn)在多邊形上、點(diǎn)在多邊形外。故本文把在多邊形內(nèi)的點(diǎn)簡(jiǎn)稱(chēng)為內(nèi)點(diǎn)，在多邊形外的點(diǎn)簡(jiǎn)稱(chēng)為外點(diǎn))。

本文是在計(jì)算機(jī)圖形學(xué)的基礎(chǔ)上進(jìn)行研究的，通過(guò)對(duì)多邊形重疊區(qū)域的分析總結(jié)出圖像與圖像之間重疊區(qū)域的確定問(wèn)題。該算法已用VC++語(yǔ)言實(shí)現(xiàn)，現(xiàn)給出如圖4、圖5所示的一個(gè)算例的執(zhí)行結(jié)果，其中圖4為兩個(gè)四邊形圖A和圖B，圖5為圖A與圖B的重疊區(qū)域。

圖4 原始圖

圖5 重疊區(qū)域

實(shí)踐表明，此種確定多邊形重疊區(qū)域的算法具有很好的實(shí)驗(yàn)結(jié)果，算法結(jié)構(gòu)清晰易懂，易于編程實(shí)現(xiàn)。需要說(shuō)明的是，該算法雖然也可以同時(shí)對(duì)多張(大于兩張)自由像片的重疊區(qū)域進(jìn)行確定，但隨著像片數(shù)量的增多，其處理速度也會(huì)降低。此問(wèn)題也有待于今后進(jìn)一步地探討和研究。

[1]陳挺.圖像拼接算法及實(shí)現(xiàn)[EB/OL].http：//www.studa.net/yingyong/090603/1636506.html，2009-06/2010-04.

[2]黃曉萍.基礎(chǔ)地理信息工程[EB/OL].http：//course.cug.edu.cn/cugThird/base_MAPGIS/classroom/5-3-1.htm，2002-3/2010-04.

[3]王悅，吳云東，張魁珂，等.自由像片重疊區(qū)域的確定及拼接[J].海洋測(cè)繪，2008，28(5)：1-4.

[4]朱雅音，王化文，萬(wàn)豐，等.確定兩個(gè)任意簡(jiǎn)單多邊形交、 并、 差的算法[J].計(jì)算機(jī)研究與發(fā)展 ，2003，40(4)：1-8.

[5]和青芳.計(jì)算機(jī)圖形學(xué)原理及算法教程(Visual C++)[M/CD].http：//wenku.baidu.com/view/bb4117661ed9ad51f01df27d.html， 2010.02.15／2010.04.06.