高佳慧， 胡國(guó)勇， 陳錦瀚，陳建超

(廣東財(cái)經(jīng)大學(xué) a.數(shù)學(xué)與統(tǒng)計(jì)學(xué)院； b.信息學(xué)院，廣州 510320)

?

基于物體影長(zhǎng)數(shù)據(jù)的定位方法研究

高佳慧a， 胡國(guó)勇a， 陳錦瀚b，陳建超a

(廣東財(cái)經(jīng)大學(xué) a.數(shù)學(xué)與統(tǒng)計(jì)學(xué)院； b.信息學(xué)院，廣州 510320)

摘要:根據(jù)物體在太陽(yáng)光下的影子變化數(shù)據(jù)來(lái)判斷其所在的地點(diǎn)和日期，是一項(xiàng)具有現(xiàn)實(shí)意義的研究。通過(guò)分析時(shí)角、赤緯角及當(dāng)?shù)氐慕?jīng)緯度與物體影長(zhǎng)的物理學(xué)關(guān)系，將地點(diǎn)的空間定位問(wèn)題轉(zhuǎn)化為數(shù)學(xué)上的優(yōu)化問(wèn)題并建立模型進(jìn)行求解。在日期已知時(shí)，利用確定性的兩階段空間搜索算法進(jìn)行模型求解；在日期未知時(shí)，改進(jìn)模型，利用細(xì)菌覓食優(yōu)化算法(bacterial foraging optimization， BFO)進(jìn)行求解。經(jīng)檢驗(yàn)，兩種定位方法的效果均良好，可具體應(yīng)用于解決現(xiàn)實(shí)生活中的地點(diǎn)定位。

關(guān)鍵詞:太陽(yáng)影子；物體定位；空間搜索算法；細(xì)菌覓食優(yōu)化算法

隨著現(xiàn)代通信技術(shù)的發(fā)展和智能手機(jī)的普及，定位技術(shù)逐漸深入人們的生活。近年來(lái)，相機(jī)的應(yīng)用逐漸普及，直接通過(guò)相機(jī)拍攝的視頻定位將具有很大的應(yīng)用潛力空間。

近年來(lái)，相關(guān)學(xué)者在圖像定位領(lǐng)域已經(jīng)進(jìn)行相應(yīng)研究。Hays等[1]通過(guò)采集超過(guò)600萬(wàn)張的帶有地理標(biāo)記的GPS圖像，利用數(shù)據(jù)驅(qū)動(dòng)進(jìn)行場(chǎng)景匹配的單個(gè)圖像經(jīng)緯度估計(jì)；但是，這一方法需采集的圖像數(shù)量龐大，而且這些圖像并不能完全反映全球的地貌特征，可操作性較低。武琳[2]通過(guò)獲取同一場(chǎng)景中兩個(gè)影子軌跡的視頻幀，利用圖片中的4組陰影觀測(cè)點(diǎn)來(lái)進(jìn)行相機(jī)校準(zhǔn)，并根據(jù)Analemmatic日晷原理得到陰影軌跡的二次曲線，以此來(lái)估計(jì)相機(jī)所在位置，實(shí)現(xiàn)了在未經(jīng)過(guò)影子校準(zhǔn)的情況下的經(jīng)緯度估計(jì)。

2015年全國(guó)大學(xué)生數(shù)學(xué)建模競(jìng)賽A題[3]是一道已知一個(gè)物體的影子變化數(shù)據(jù)，要求對(duì)該物體的拍攝地點(diǎn)和日期進(jìn)行確定的問(wèn)題。 本研究從賽題中給出的直立長(zhǎng)桿的影子變化數(shù)據(jù)出發(fā)，通過(guò)分析太陽(yáng)影子形成的物理學(xué)原理，將定位問(wèn)題轉(zhuǎn)化為數(shù)學(xué)上的優(yōu)化模型，并分別利用兩階段空間搜索算法和細(xì)菌覓食優(yōu)化算法(bacterial foraging optimization, BFO)對(duì)模型進(jìn)行相應(yīng)求解。在建立數(shù)學(xué)模型的過(guò)程中，本研究主要考慮了以下兩種情況：日期已知時(shí)，根據(jù)物體影子的變化推測(cè)出所在地點(diǎn)；日期未知時(shí)，直接根據(jù)物體影子的變化推測(cè)出對(duì)應(yīng)日期和所在地點(diǎn)。

1已知日期時(shí)的物體定位算法

1.1模型構(gòu)建

物體的影子將隨著一天中太陽(yáng)高度角α的變化而發(fā)生改變。而太陽(yáng)高度角α同時(shí)受地理位置和時(shí)間的影響，它可以通過(guò)時(shí)角ω、赤緯角δ及當(dāng)?shù)氐慕?jīng)度β和緯度φ計(jì)算出來(lái)[4-5]:

sinα=sinφ·sinδ+cosφ·cosδ·cosω。

(1)

其中，赤緯角δ、時(shí)角ω、地方標(biāo)準(zhǔn)時(shí)ts的計(jì)算公式分別為[6]:

(2)

(3)

(4)

其中，地方標(biāo)準(zhǔn)時(shí)計(jì)算公式中的正負(fù)號(hào)分別適用于東半球時(shí)和西半球時(shí)的情形[7]。

由于太陽(yáng)照射固定直桿形成影子，光線方向與水平面夾角為太陽(yáng)高度角，故影子長(zhǎng)度l與太陽(yáng)高度角α、直桿長(zhǎng)度h之間的數(shù)學(xué)關(guān)系式為：

l=h/tanα。

(5)

結(jié)合式(1)和式(5)，利用各時(shí)刻直桿的影長(zhǎng)li可分別計(jì)算對(duì)應(yīng)的物體高度：

hi=litan(arcsin(sinφsinδ+cosφcosδcosω))i=1,2，…，n。

(6)

其中ω是一個(gè)隨時(shí)間變化的量，見(jiàn)式(3)和式(4)。

對(duì)于式(6)，如果能找到物體所在的準(zhǔn)確地點(diǎn)，那么各hi必定是相等的。而當(dāng)搜索的經(jīng)緯度逼近準(zhǔn)確的地點(diǎn)時(shí)，定位的偏差值將會(huì)變小，這組hi的方差也變小。因此，本研究以經(jīng)度β、緯度φ為自變量，以不同時(shí)刻的桿長(zhǎng)hi的方差最小化為目標(biāo)，建立如下數(shù)學(xué)優(yōu)化模型：

min var(hi)。

(7)

其中，

1.2兩階段空間搜索算法求解

由于地球表面是近似規(guī)則的，并且地球自轉(zhuǎn)具有規(guī)律性，因此,在正確的經(jīng)緯度點(diǎn)附近，上述數(shù)學(xué)模型中的目標(biāo)函數(shù)必定隨著定位偏差的減小而遞減。故本研究建立空間搜索算法，采取固定步長(zhǎng)的前向搜索在全球范圍內(nèi)進(jìn)行搜索，以找到能使var(hi)最小的值。

為加快搜索速度，將搜索過(guò)程分為全球粗搜索和局部精確搜索兩個(gè)階段。即先在全球范圍內(nèi)以5°為步長(zhǎng)進(jìn)行搜索，找到匹配度較高的集中區(qū)域后，再以0.25°為步長(zhǎng)，進(jìn)行較為精確的局部搜索。

建立的空間兩階段搜索算法步驟如下：

2)計(jì)算緯度為φ0，記錄經(jīng)度為β0時(shí)的h0的方差varh0。

4)設(shè)置步長(zhǎng)為Δφ，令φ1=φ0+Δφ，重復(fù)步驟3，直到φi=90°，結(jié)束搜索。

5)輸出varhi趨于0的經(jīng)緯度點(diǎn)。

6)選擇varhi趨于0的幾個(gè)區(qū)域，令Δβ=0.25°，重復(fù)步驟1～5。

根據(jù)競(jìng)賽題附件1[3]所提供的2015年4月18日14:42—15:42的21個(gè)數(shù)據(jù)點(diǎn)，進(jìn)行全球經(jīng)緯度點(diǎn)搜索匹配。

考慮到局部搜索的精確性及數(shù)據(jù)點(diǎn)分布的廣度，采用同樣的方式， 在全球范圍內(nèi)選取搜索算法中其余幾個(gè)匹配度較高的點(diǎn)。結(jié)果顯示有4個(gè)點(diǎn)的匹配度較高，如表1所示。

表1　空間搜索算法搜索結(jié)果

1.3結(jié)果分析

圖1　[18.5° N,110° E]影子長(zhǎng)度檢驗(yàn)圖Fig.1　Testing of model’s accuracy in [18.5° N,110° E]

將求得的4個(gè)地點(diǎn)代入式(6)進(jìn)行模型檢驗(yàn)。以海南( [18.5°N,110°E])為例，可得2015年4月18日14:42—15:42時(shí)的影長(zhǎng)變化數(shù)據(jù)。將其與競(jìng)賽題附件1[3]給出的數(shù)據(jù)進(jìn)行比較，結(jié)果如圖1所示。

通過(guò)圖1可以發(fā)現(xiàn)，實(shí)際的數(shù)據(jù)點(diǎn)都分布在反演結(jié)果的影長(zhǎng)數(shù)據(jù)線之上，搜索的誤差極小。以同樣的方式對(duì)其余地點(diǎn)進(jìn)行驗(yàn)證，可以發(fā)現(xiàn)準(zhǔn)確度都較高。

2未知日期時(shí)的物體定位算法

2.1模型的建立

若存在某一經(jīng)緯度和日期，使得當(dāng)通過(guò)式(6)反推不同時(shí)刻直桿長(zhǎng)度時(shí)，litanαi都近似相等，則是滿足競(jìng)賽題附件[3]中影子變化的地點(diǎn)和日期。故搜索經(jīng)緯度、時(shí)間、高度時(shí)，使litanαi之間的差最小。以經(jīng)度β、緯度φ、日期序號(hào)N為自變量，建立優(yōu)化模型：

min∑|litanαi-ljtanαj|(i≠j,i、j=1,2,…,n)。

(8)

其中，

2.2細(xì)菌覓食算法求解

細(xì)菌覓食算法作為一種生物啟發(fā)式算法，是根據(jù)大腸桿菌的覓食過(guò)程而提出的一種仿真隨機(jī)搜索算法[8]。類似于其他基于群體智能的隨機(jī)搜索算法，細(xì)菌覓食算法求解優(yōu)化問(wèn)題的一般過(guò)程為：對(duì)問(wèn)題的解進(jìn)行編碼，設(shè)計(jì)評(píng)價(jià)函數(shù)，產(chǎn)生初始解的群體，利用群體之間的互相影響進(jìn)行優(yōu)化[9-10]。細(xì)菌覓食優(yōu)化算法的整體流程[11-12]如下。

1)初始化趨向性步驟的次數(shù)Nc、復(fù)制步驟執(zhí)行的次數(shù)Nre、遷徙操作執(zhí)行的次數(shù)Ned、遷徙概率Ped、游動(dòng)次數(shù)Ns、游動(dòng)步長(zhǎng)C及細(xì)菌規(guī)模S。第i個(gè)個(gè)體的信息表示為θi，其健康值為Hi。

2)遷徙循環(huán)loop:l=l+1(l=1:Ned)；循環(huán)體包含步驟①至步驟③。

①?gòu)?fù)制循環(huán)loop:k=k+1(k=1:Nre)；在復(fù)制循環(huán)的每次迭代中，Hi都初始化為0。循環(huán)體包含步驟a)和至步驟b)。

b)根據(jù)Hi對(duì)種群進(jìn)行排序，將靠后的一半個(gè)體刪去。對(duì)剩下的個(gè)體進(jìn)行復(fù)制，生成細(xì)菌規(guī)模為S的新種群。

③判斷遷徙循環(huán)的結(jié)束條件，滿足則結(jié)束循環(huán)，輸出結(jié)果。

表2　細(xì)菌覓食優(yōu)化算法搜索結(jié)果

同樣，根據(jù)式(6)，對(duì)表2中的地點(diǎn)和日期等數(shù)據(jù)反演數(shù)據(jù)線進(jìn)行檢驗(yàn)。結(jié)果顯示，競(jìng)賽題附件2[3]的實(shí)際影子坐標(biāo)點(diǎn)都基本分布在這6條反演曲線上，故根據(jù)細(xì)菌覓食算法所求得的地點(diǎn)及時(shí)間也是準(zhǔn)確的。

3兩種定位方法在視頻影子數(shù)據(jù)分析中的應(yīng)用

日常情況下，視頻中的物體影長(zhǎng)的數(shù)據(jù)并未提取出來(lái)，因此，首先需要對(duì)視頻數(shù)據(jù)進(jìn)行讀取，才能進(jìn)行位置搜索。

此時(shí)桿長(zhǎng)和影長(zhǎng)的比例ki(i=1，…，14)的計(jì)算公式為：

表3　空間搜索算法對(duì)應(yīng)地點(diǎn)分布表

表4BFO算法對(duì)應(yīng)地點(diǎn)及日期分布表

Table 4　Locations and dates based on bacterial foraging optimization

兩者的求解結(jié)果基本趨于一致，模型之間相互驗(yàn)證。

4結(jié)語(yǔ)

本研究根據(jù)天文學(xué)知識(shí)和物理公式，將物體的時(shí)空定位問(wèn)題轉(zhuǎn)化成了非線性優(yōu)化問(wèn)題。并設(shè)計(jì)了數(shù)學(xué)上的優(yōu)化模型，利用兩階段空間搜索算法單獨(dú)對(duì)地點(diǎn)(經(jīng)緯度)實(shí)現(xiàn)了逐步求精的地點(diǎn)定位求解；并進(jìn)一步改進(jìn)模型，利用細(xì)菌覓食優(yōu)化算法實(shí)現(xiàn)了地點(diǎn)(經(jīng)緯度)和時(shí)間(月、日)的定位求解。通過(guò)一系列視頻處理，實(shí)現(xiàn)了該技術(shù)在視頻拍攝日期及地點(diǎn)定位中的應(yīng)用。

將2015年數(shù)學(xué)建模競(jìng)賽A題[3]的數(shù)據(jù)代入本研究模型進(jìn)行地點(diǎn)和日期定位。通過(guò)對(duì)比競(jìng)賽題答案中所公布的真實(shí)地點(diǎn)及日期，發(fā)現(xiàn)本研究模型的地點(diǎn)(經(jīng)緯度)定位準(zhǔn)確，但日期(月、日)定位出現(xiàn)偏差，這可能是由于細(xì)菌覓食算法陷入了局部最優(yōu)所致。

在現(xiàn)實(shí)生活中，此定位方法對(duì)于任何具有高度的物體都適用。另外，由于此定位方法所需數(shù)據(jù)可通過(guò)簡(jiǎn)易的測(cè)量工具(直桿、卷尺、秒表)得出，易于獲取，故其具有較強(qiáng)的實(shí)用性，可直接應(yīng)用于航海過(guò)程中的船只定位，也適用于視頻的拍攝地點(diǎn)定位。

參考文獻(xiàn):

[1]HAYS J, EFROS A A. IM2GPS: estimating geographic information from a single image[C]∥Computer Vision and Pattern Recognition, 2008. IEEE Computer Society Conference on Computer Vision and Pattern Recognition. Anchoragr, AK: IEEE, 2008:1-8.

[2]武琳. 基于太陽(yáng)陰影軌跡的經(jīng)緯度估計(jì)技術(shù)研究[D].天津：天津大學(xué), 2010.

[3]全國(guó)大學(xué)生數(shù)學(xué)建模競(jìng)賽組委會(huì).2015年高教社杯全國(guó)大學(xué)生數(shù)學(xué)建模競(jìng)賽賽題[EB/OL]. (2015-09-12) [2016-01-14].http:∥www.mcm.edu.cn/html_cn/node/ac8b96613522ef62c019d1cd45a125e3.html.

[4]張闖, 呂東輝, 頊超靜. 太陽(yáng)實(shí)時(shí)位置計(jì)算及在圖像光照方向中的應(yīng)用[J]. 電子測(cè)量技術(shù), 2010, 33(11):87.

[5]曹俊茹, 李奎, 宋振柏, 等.大地緯度計(jì)算日影高度角方法[J].測(cè)繪通報(bào),2012(8):58.

[6]方榮生. 太陽(yáng)能應(yīng)用技術(shù)[M].北京: 中國(guó)農(nóng)業(yè)機(jī)械出版社, 1985.

[7]徐豐, 王波, 張海龍. 建筑日照分析中太陽(yáng)位置計(jì)算公式的改進(jìn)研究[J]. 重慶建筑大學(xué)學(xué)報(bào), 2008, 30(5):130.

[8]遲旭燕. 基于改進(jìn)BFO算法的芯片堆疊熱布局優(yōu)化研究[D].西安：西安電子科技大學(xué),2013.

[9]張娜. 細(xì)菌覓食優(yōu)化算法求解車間調(diào)度問(wèn)題的研究[D]. 長(zhǎng)春：吉林大學(xué), 2007.

[10]章國(guó)勇,伍永剛,譚宇翔.一種具有量子行為的細(xì)菌覓食優(yōu)化算法[J].電子與信息學(xué)報(bào), 2013(3):614.

[11]姜建國(guó), 周佳薇, 鄭迎春,等. 一種自適應(yīng)細(xì)菌覓食優(yōu)化算法[J]. 西安電子科技大學(xué)學(xué)報(bào)(自然科學(xué)版), 2015, 42(1):75.

[12]陳建超, 胡桂武, 杜小勇. 自適應(yīng)變步長(zhǎng)菌群優(yōu)化算法[J]. 計(jì)算機(jī)工程與應(yīng)用, 2012, 48(33):31.

doi:10.3969/j.issn.1671-8798.2016.03.006

收稿日期:2016-03-01

作者簡(jiǎn)介:高佳慧(1996—)，女，湖南省衡陽(yáng)人，2013級(jí)數(shù)學(xué)與應(yīng)用數(shù)學(xué)專業(yè)本科生。

通信作者:陳建超，講師，博士，主要從事計(jì)算機(jī)智能和數(shù)據(jù)挖掘研究。

中圖分類號(hào):TP301.6; O29

文獻(xiàn)標(biāo)志碼:A

文章編號(hào):1671-8798(2016)03-0200-05

Positioning method based on length of object’s shadow

GAO Jiahuia, HU Guoyonga, CHEN Jinhanb, CHEN Jianchaoa

(a.School of Mathematics and Statistics; b.School of Information, Guangdong University of Finance and Economics, Guangzhou 510320, China)

Abstract:It is a meaningful research topic to find out when and where an object is by analyzing the trace data of its shadow under the sun. The spatial localization problem can be converted to an optimization issue under appropriate framework, and be solved by building a mathematical model, which is based on the relationship between shadow’s length and such factors as hour angle, declination angle, longitude and latitude. Besides, a two-phase space search algorithm can be implemented to solve the model when given priori information about date; otherwise, the model can be rectified and then be figured out by utilizing the bacterial foraging optimization.The performance of these methods are well-behaved, and can be used in real-world applications.

Keywords:shadow; localization; spatial search algorithm; bacterial foraging optimization