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

高佳慧， 胡國勇， 陳錦瀚，陳建超

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

?

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

高佳慧a， 胡國勇a， 陳錦瀚b，陳建超a

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

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

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

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

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

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

1已知日期時的物體定位算法

1.1模型構(gòu)建

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

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

(1)

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

(2)

(3)

(4)

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

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

l=h/tanα。

(5)

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

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

(6)

其中ω是一個隨時間變化的量，見式(3)和式(4)。

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

min var(hi)。

(7)

其中，

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

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

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

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

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

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

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

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

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

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

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

1.3結(jié)果分析

圖1　[18.5° N,110° E]影子長度檢驗圖Fig.1　Testing of model’s accuracy in [18.5° N,110° E]

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

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

2未知日期時的物體定位算法

2.1模型的建立

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

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

(8)

其中，

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

細(xì)菌覓食算法作為一種生物啟發(fā)式算法，是根據(jù)大腸桿菌的覓食過程而提出的一種仿真隨機(jī)搜索算法[8]。類似于其他基于群體智能的隨機(jī)搜索算法，細(xì)菌覓食算法求解優(yōu)化問題的一般過程為：對問題的解進(jìn)行編碼，設(shè)計評價函數(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、游動次數(shù)Ns、游動步長C及細(xì)菌規(guī)模S。第i個個體的信息表示為θi，其健康值為Hi。

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

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

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

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

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

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

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

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

此時桿長和影長的比例ki(i=1，…，14)的計算公式為：

表3　空間搜索算法對應(yīng)地點分布表

表4BFO算法對應(yīng)地點及日期分布表

Table 4　Locations and dates based on bacterial foraging optimization

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

4結(jié)語

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

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

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

參考文獻(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]武琳. 基于太陽陰影軌跡的經(jīng)緯度估計技術(shù)研究[D].天津：天津大學(xué), 2010.

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

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

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

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

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

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

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

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

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

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

doi:10.3969/j.issn.1671-8798.2016.03.006

收稿日期:2016-03-01

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

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

中圖分類號:TP301.6; O29

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

文章編號: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