基于物体影长数据的定位方法研究

高佳慧， 胡国勇， 陈锦瀚，陈建超

(广东财经大学 a.数学与统计学院； b.信息学院，广州 510320)



基于物体影长数据的定位方法研究

高佳慧a， 胡国勇a， 陈锦瀚b，陈建超a

(广东财经大学 a.数学与统计学院； b.信息学院，广州 510320)

摘要:根据物体在太阳光下的影子变化数据来判断其所在的地点和日期，是一项具有现实意义的研究。通过分析时角、赤纬角及当地的经纬度与物体影长的物理学关系，将地点的空间定位问题转化为数学上的优化问题并建立模型进行求解。在日期已知时，利用确定性的两阶段空间搜索算法进行模型求解；在日期未知时，改进模型，利用细菌觅食优化算法(bacterial foraging optimization， BFO)进行求解。经检验，两种定位方法的效果均良好，可具体应用于解决现实生活中的地点定位。

关键词:太阳影子；物体定位；空间搜索算法；细菌觅食优化算法

随着现代通信技术的发展和智能手机的普及，定位技术逐渐深入人们的生活。近年来，相机的应用逐渐普及，直接通过相机拍摄的视频定位将具有很大的应用潜力空间。

近年来，相关学者在图像定位领域已经进行相应研究。Hays等[1]通过采集超过600万张的带有地理标记的GPS图像，利用数据驱动进行场景匹配的单个图像经纬度估计；但是，这一方法需采集的图像数量庞大，而且这些图像并不能完全反映全球的地貌特征，可操作性较低。武琳[2]通过获取同一场景中两个影子轨迹的视频帧，利用图片中的4组阴影观测点来进行相机校准，并根据Analemmatic日晷原理得到阴影轨迹的二次曲线，以此来估计相机所在位置，实现了在未经过影子校准的情况下的经纬度估计。

2015年全国大学生数学建模竞赛A题[3]是一道已知一个物体的影子变化数据，要求对该物体的拍摄地点和日期进行确定的问题。 本研究从赛题中给出的直立长杆的影子变化数据出发，通过分析太阳影子形成的物理学原理，将定位问题转化为数学上的优化模型，并分别利用两阶段空间搜索算法和细菌觅食优化算法(bacterial foraging optimization, BFO)对模型进行相应求解。在建立数学模型的过程中，本研究主要考虑了以下两种情况：日期已知时，根据物体影子的变化推测出所在地点；日期未知时，直接根据物体影子的变化推测出对应日期和所在地点。

1已知日期时的物体定位算法

1.1模型构建

物体的影子将随着一天中太阳高度角α的变化而发生改变。而太阳高度角α同时受地理位置和时间的影响，它可以通过时角ω、赤纬角δ及当地的经度β和纬度φ计算出来[4-5]:

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

(1)

其中，赤纬角δ、时角ω、地方标准时ts的计算公式分别为[6]:

(2)

(3)

(4)

其中，地方标准时计算公式中的正负号分别适用于东半球时和西半球时的情形[7]。

由于太阳照射固定直杆形成影子，光线方向与水平面夹角为太阳高度角，故影子长度l与太阳高度角α、直杆长度h之间的数学关系式为：

l=h/tanα。

(5)

结合式(1)和式(5)，利用各时刻直杆的影长li可分别计算对应的物体高度：

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

(6)

其中ω是一个随时间变化的量，见式(3)和式(4)。

对于式(6)，如果能找到物体所在的准确地点，那么各hi必定是相等的。而当搜索的经纬度逼近准确的地点时，定位的偏差值将会变小，这组hi的方差也变小。因此，本研究以经度β、纬度φ为自变量，以不同时刻的杆长hi的方差最小化为目标，建立如下数学优化模型：

min var(hi)。

(7)

其中，

1.2两阶段空间搜索算法求解

由于地球表面是近似规则的，并且地球自转具有规律性，因此,在正确的经纬度点附近，上述数学模型中的目标函数必定随着定位偏差的减小而递减。故本研究建立空间搜索算法，采取固定步长的前向搜索在全球范围内进行搜索，以找到能使var(hi)最小的值。

为加快搜索速度，将搜索过程分为全球粗搜索和局部精确搜索两个阶段。即先在全球范围内以5°为步长进行搜索，找到匹配度较高的集中区域后，再以0.25°为步长，进行较为精确的局部搜索。

建立的空间两阶段搜索算法步骤如下：

2)计算纬度为φ0，记录经度为β0时的h0的方差varh0。

4)设置步长为Δφ，令φ1=φ0+Δφ，重复步骤3，直到φi=90°，结束搜索。

5)输出varhi趋于0的经纬度点。

6)选择varhi趋于0的几个区域，令Δβ=0.25°，重复步骤1～5。

根据竞赛题附件1[3]所提供的2015年4月18日14:42—15:42的21个数据点，进行全球经纬度点搜索匹配。

考虑到局部搜索的精确性及数据点分布的广度，采用同样的方式， 在全球范围内选取搜索算法中其余几个匹配度较高的点。结果显示有4个点的匹配度较高，如表1所示。

表1　空间搜索算法搜索结果

1.3结果分析

图1　[18.5° N,110° E]影子长度检验图Fig.1　Testing of model’s accuracy in [18.5° N,110° E]

将求得的4个地点代入式(6)进行模型检验。以海南( [18.5°N,110°E])为例，可得2015年4月18日14:42—15:42时的影长变化数据。将其与竞赛题附件1[3]给出的数据进行比较，结果如图1所示。

通过图1可以发现，实际的数据点都分布在反演结果的影长数据线之上，搜索的误差极小。以同样的方式对其余地点进行验证，可以发现准确度都较高。

2未知日期时的物体定位算法

2.1模型的建立

若存在某一经纬度和日期，使得当通过式(6)反推不同时刻直杆长度时，litanαi都近似相等，则是满足竞赛题附件[3]中影子变化的地点和日期。故搜索经纬度、时间、高度时，使litanαi之间的差最小。以经度β、纬度φ、日期序号N为自变量，建立优化模型：

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

(8)

其中，

2.2细菌觅食算法求解

细菌觅食算法作为一种生物启发式算法，是根据大肠杆菌的觅食过程而提出的一种仿真随机搜索算法[8]。类似于其他基于群体智能的随机搜索算法，细菌觅食算法求解优化问题的一般过程为：对问题的解进行编码，设计评价函数，产生初始解的群体，利用群体之间的互相影响进行优化[9-10]。细菌觅食优化算法的整体流程[11-12]如下。

1)初始化趋向性步骤的次数Nc、复制步骤执行的次数Nre、迁徙操作执行的次数Ned、迁徙概率Ped、游动次数Ns、游动步长C及细菌规模S。第i个个体的信息表示为θi，其健康值为Hi。

2)迁徙循环loop:l=l+1(l=1:Ned)；循环体包含步骤①至步骤③。

①复制循环loop:k=k+1(k=1:Nre)；在复制循环的每次迭代中，Hi都初始化为0。循环体包含步骤a)和至步骤b)。

b)根据Hi对种群进行排序，将靠后的一半个体删去。对剩下的个体进行复制，生成细菌规模为S的新种群。

③判断迁徙循环的结束条件，满足则结束循环，输出结果。

表2　细菌觅食优化算法搜索结果

同样，根据式(6)，对表2中的地点和日期等数据反演数据线进行检验。结果显示，竞赛题附件2[3]的实际影子坐标点都基本分布在这6条反演曲线上，故根据细菌觅食算法所求得的地点及时间也是准确的。

3两种定位方法在视频影子数据分析中的应用

日常情况下，视频中的物体影长的数据并未提取出来，因此，首先需要对视频数据进行读取，才能进行位置搜索。

此时杆长和影长的比例ki(i=1，…，14)的计算公式为：

表3　空间搜索算法对应地点分布表

表4BFO算法对应地点及日期分布表

Table 4　Locations and dates based on bacterial foraging optimization

两者的求解结果基本趋于一致，模型之间相互验证。

4结语

本研究根据天文学知识和物理公式，将物体的时空定位问题转化成了非线性优化问题。并设计了数学上的优化模型，利用两阶段空间搜索算法单独对地点(经纬度)实现了逐步求精的地点定位求解；并进一步改进模型，利用细菌觅食优化算法实现了地点(经纬度)和时间(月、日)的定位求解。通过一系列视频处理，实现了该技术在视频拍摄日期及地点定位中的应用。

将2015年数学建模竞赛A题[3]的数据代入本研究模型进行地点和日期定位。通过对比竞赛题答案中所公布的真实地点及日期，发现本研究模型的地点(经纬度)定位准确，但日期(月、日)定位出现偏差，这可能是由于细菌觅食算法陷入了局部最优所致。

在现实生活中，此定位方法对于任何具有高度的物体都适用。另外，由于此定位方法所需数据可通过简易的测量工具(直杆、卷尺、秒表)得出，易于获取，故其具有较强的实用性，可直接应用于航海过程中的船只定位，也适用于视频的拍摄地点定位。

参考文献:

[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]武琳. 基于太阳阴影轨迹的经纬度估计技术研究[D].天津：天津大学, 2010.

[3]全国大学生数学建模竞赛组委会.2015年高教社杯全国大学生数学建模竞赛赛题[EB/OL]. (2015-09-12) [2016-01-14].http:∥www.mcm.edu.cn/html_cn/node/ac8b96613522ef62c019d1cd45a125e3.html.

[4]张闯, 吕东辉, 顼超静. 太阳实时位置计算及在图像光照方向中的应用[J]. 电子测量技术, 2010, 33(11):87.

[5]曹俊茹, 李奎, 宋振柏, 等.大地纬度计算日影高度角方法[J].测绘通报,2012(8):58.

[6]方荣生. 太阳能应用技术[M].北京: 中国农业机械出版社, 1985.

[7]徐丰, 王波, 张海龙. 建筑日照分析中太阳位置计算公式的改进研究[J]. 重庆建筑大学学报, 2008, 30(5):130.

[8]迟旭燕. 基于改进BFO算法的芯片堆叠热布局优化研究[D].西安：西安电子科技大学,2013.

[9]张娜. 细菌觅食优化算法求解车间调度问题的研究[D]. 长春：吉林大学, 2007.

[10]章国勇,伍永刚,谭宇翔.一种具有量子行为的细菌觅食优化算法[J].电子与信息学报, 2013(3):614.

[11]姜建国, 周佳薇, 郑迎春,等. 一种自适应细菌觅食优化算法[J]. 西安电子科技大学学报(自然科学版), 2015, 42(1):75.

[12]陈建超, 胡桂武, 杜小勇. 自适应变步长菌群优化算法[J]. 计算机工程与应用, 2012, 48(33):31.

doi:10.3969/j.issn.1671-8798.2016.03.006

收稿日期:2016-03-01

作者简介:高佳慧(1996—)，女，湖南省衡阳人，2013级数学与应用数学专业本科生。

通信作者:陈建超，讲师，博士，主要从事计算机智能和数据挖掘研究。

中图分类号:TP301.6; O29

文献标志码: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