ABSTRACT

Based on the straight rod as the research object, this paper uses the quadratic fitting method, genetic algorithm and the quantum genetic algorithm (ga) to deal with shadow data and video, to set up the sun’s shadow positioning model, from which the location and date can be concluded. Firstly, we transform some pictures in the video and extract gray level matrix, process rod and rod shadow matrix in binarization; secondly, calculate the shadow length at different times by the relationship of the proportional, through the quadratic fitting for the approximate scope of longitude; then, mesh edit the latitude and longitude, iterate through all the points by the heuristic algorithm; finally, we regard the shadow got by the latitude and longitude and the actual shadow as the objective function. When modeling, we find that the heuristic algorithm’s convergence speed is slow, therefore we use the genetic algorithm to the global search. In order to determine the possible date, we set up the sun shadow locating model which is based on genetic algorithm with binary coding to initialize the population, converted to a decimal calculation fitness, through iteration obtain the geographic coordinates.

Keywords:Shadow Positioning, Matching, Heuristic Algorithm, Genetic Algorithm, Gray Matrix

基于遗传算法的太阳影子定位模型及研究

张慧

青海大学化工学院应用化学系，青海 西宁

收稿日期：2016年1月7日；录用日期：2016年1月25日；发布日期：2016年1月28日

摘 要

本文以直杆为研究对象，利用二次拟合方法、遗传算法和量子遗传算法对影长数据和视频进行处理，来建立太阳影子定位模型，从而可以得出拍摄地点与日期。首先，转化视频中部分图片并提取出灰度矩阵，对其中直杆、杆影矩阵进行二值化处理；其次，根据其比例关系算出不同时刻的杆影长度，通过二次拟合求得经度的大致范围；接着，对经纬度网格化，采用启发式算法遍历所有格点；最后，将经纬度求出的影长与实际影长的相似度作为目标函数，得出地理坐标。建模时，发现启发式算法的收敛速度较慢，故运用遗传算法对经纬度全局搜索。为确定可能的拍摄日期，建立基遗传算法的太阳影子定位模型，采用二进制编码初始化种群，转化为十进制计算适应度，通过迭代得出结果。

关键词 :影子定位，拟合，启发式算法，遗传算法，灰度矩阵

1. 引言

通过视频中的信息计算出经纬和日期是目前计算机视觉领域的研究热点问题，计算经纬度和估算日期不仅自身具有重要的价值理论而且对其他的计算机视觉问题也有极其重要的启发意义。太阳影子定位技术就是通过分析视频中物体的太阳影子变化规律，确定视频拍摄的地点和日期的一种方法，因此在计算机视觉领域研究中是一种热门技术，受到很多学者的热捧。如何设计出合理简单的数学模型应用到太阳影子定位技术中，使太阳影子定位技术能够更加简易完善，在计算机视觉领域中得到更广泛的应用，则具有不可估量的研究价值和意义。

2. 通用符号说明

基于遗传算法的太阳影子定位模型中所使用的符号释义如下：

3. 模型介绍及实例分析

3.1. 影子长度变化的模型建立

太阳光线照射过杆，使杆、影子与太阳光线形成一直角三角形，如图1所示。

故可列出公式：

(1-1)

其中，为直杆的影子长度，为直杆的高度，为太阳高度角。

基于太阳高度角的影长变化模型

查阅参考文献[1] 知

(1-2)

其中，为太阳高度角，为该点的纬度，为太阳赤纬，为太阳时角。

所以，

(1-3)

而由参考文献[2] 、[3] 知

(1-4)

其中，为太阳赤纬，为日数，自每年1月1日开始计算，为太阳时角，为真太阳时，以24小时计。

对于式(1-4)中的，由参考文献[3] 知

(1-5)

其中，为该点的经度，为真太阳时，为北京时间，为时差。

3.2. 知日期地点确定模型

通过对影子轨迹拟合估计出当地正午时间，再根据北京时间求出初始经度，以此作为初值解，建立基于遗传算法的太阳影子定位模型。

3.2.1. 拟合确定初始经度(附件1见附录)

利用二次曲线拟合来估计2015年4月18日的当地正午时间，依据附件1，对杆影长度进行拟合去逼近此动态过程，最终达到估计的目的。将杆影附件中数据加以处理，杆影长度随时间变化，如表1所示。

再利用相应时间与表1中数据按二次曲线进行拟合，使用最小二乘法确定拟合方程为

(2-1)

其中，为附件1杆影长度，为附件1当地时间。

因为杆影最短的时刻即为当地正午时刻，故，所以初始经度为

其中，为附件1初始经度，为附件1杆影最短时刻。

3.2.2. 基于启发式算法的太阳影子定位模型

根据直杆在水平面上的影子顶点数据推断可能的地点，本文通过确定约束条件，以求解的竿影长和实际竿影长的相似度作为目标函数，建立基于启发式算法的太阳影子定位模型，具体步骤如下：

图1. 太阳光线、杆与其影子所成示意图

表1. 影长随时间变化(数据来自全国大学生数学建模竞赛)

Step 1：初始化。根据拟合方法确定的经度为111.02度，考虑到误差影响，取经度范围为，纬度范围取，选定步长为，接下来将经纬度范围网格化，记下该网格为矩阵，通过经纬度确定可能的地点。

Step 2：确定目标函数。求解的经纬度公式 (1-3) 得出太阳高度角不妨设杆长为米，可以根据公式(1-1)计算出21个时刻所对应的影长，为消去杆长的影响，按照如下公式进行处理：

(2-2)

可以得出影长之比，记附件中的影长为，(为附件中坐标)，可以得出实际影长之比：

表示可能的拍摄地点，则优化目标记为：

(2-3)

Step 3：首先以步长为对经度进行循环，对于每一确定的经度，对纬度进行循环，利用得到的经纬度算出目标函数值，记，再继续搜索下一对经纬度，进而计算出目标函数值，与进行比较：

为网格化的矩阵，为优化的经纬度坐标。

Step4：遍历所有经纬度，确定最优的目标值，从而确定可能的拍摄地点。

3.2.3. 基于遗传算法的太阳影子定位模型

遗传算法：遗传算法(Genetic Algorithm)是一类借鉴生物界的进化规律(适者生存，优胜劣汰遗传机制)演化而来的随机化搜索方法。它是由美国的J. Holland教授1975年首先提出，其主要特点是直接对结构对象进行操作，不存在求导和函数连续性的限定；具有内在的隐并行性和更好的全局寻优能力；采用概率化的寻优方法，能自动获取和指导优化的搜索空间，自适应地调整搜索方向，不需要确定的规则。遗传算法的这些性质，已被人们广泛地应用于组合优化、机器学习、信号处理、自应控制和人工生命等领域。遗传算法也是计算机科学人工智能领域中用于解决最优化的一种搜索启发式算法，是进化算法的一种。这种启发式通常用来生成有用的解决方案来优化和搜索问题。

由于前面的模型收敛速度慢，不适用数据量大的搜索，于是本文利用遗传算法的全局搜索能力对网格中的经纬度筛选，以影长和实际影长的比例作为适应度，建立基于遗传算法的太阳影子定位模型，模型建立流程图如图2所示。

具体步骤如下：

Step 1：编码。采用二进制编码方法，对于个地点的搜索问题，染色体分为段，其中0表示该地点未被选择，1表示选择该地点。考虑到可能有若干个可能的拍摄地点，故将染色体中出现1的概率记为5/n，表示可能有5个拍摄地点。

Step 2：种群初始化。在完成染色体编码以后，必须产生一个初始种群作为初始解，由于初始种群的个数为随机产生，种群规模的大小则影响计算效率和搜索精确性：过大则导致算法效率过低；过小则会使研究没有价值性，不具有广泛性。因此，这里综合选定初始种群的数目为50个。

Step 3：适应度函数。将可能的经纬度记为矩阵,其中表示点的经纬度 (具体值见附件1)，二进制的染色体记为，记下中为1的位置，对应经纬度即为可能的拍摄地点。再利用求解的经纬度按照问题一的公式(3)得出太阳高度角

图2. 太阳光线、杆与其影子所成示意图

，不妨设杆长为米，可以根据公式(1)计算出21个时刻所对应的影长，为消去杆长的影响，按照如下公式进行处理：

可以得出影长之比，记附件中的影长为，(为附件中坐标)，可以得出实际影长之比：

表示可能的拍摄地点，则该染色体的适应度记为：

即适应度为影长与原始影长相似度，优化的目标就是选择适应度函数尽可能大的染色体，适应度函数值越大的染色体越优质，反之越劣质。因此，这里的代数满足条件指的就是是否满足个体适应度函数的最大值，若满足则保留，否则进入下个循环。

Step 4：交叉变异操作。本文的交叉和变异概率选用动态参数，参数的变化与进化代数相关。在种群早期，高交叉率，低变异率；在种群后期，低交叉率，高变异率。用这种方法减少种群早熟的可能性。经过多次试验发现参数为：

其中，表示交叉概率，表示变异概率，表示当世代数，表示总代数，在0.875~0.958之间变化，在0.0208~0.0625之间变化。

Step 5：选择。选择操作即从旧群体中以一定概率选择个体到新群体中，个体被选中的概率跟适应度值有关，个体被选中的概率跟适应度值有关，个体适应度值越大，被选中的概率越大，从而实现优胜劣汰的过程。

Step 6：解码。对二进制染色体解码，即选取适应度最高的染色体，其编码为1所对应的经纬度即为可能的拍摄地点。

3.2.4. 模型求解

利用遗传算法的全局搜索能力对网格中的经纬度筛选，以影长和实际影长的比例作为适应度，依据附件2、附件3的数据求得地点结果，如表2所示。

3.3. 太阳影子定日期和地点模型

3.3.1. 多项式拟合确立初始经度(附件2和附件3见附录)

利用曲线拟合方法来估计当地正午时间，依据附件2、附件3，将杆影长度进行拟合去逼近此动态过程，最终达到估计的目的。将杆影附件中数据加以处理，得到附件2、附件3部分时间的杆影长度分别如表3、表4所示。

再利用表3、表4中数据分别与相应时间按二次曲线进行拟合，使用最小二乘法确定拟合方程为

(3-1)

(3-2)

表2. 附件1大致经纬度及地点

表3. 附件2影长随时间变化

表4. 附件3影长随时间变化

其中，为附件2杆影长度，为附件2当地时间，为附件3杆影长度，为附件3当地时间。

因为杆影最短的时刻即为当地正午时刻，故，，所以初始经度为

(3-3)

(3-4)

其中，为附件2初始经度，为附件2杆影最短时刻，附件3初始经度，为附件3杆影最短时刻。

3.3.2. 基于遗传算法的太阳影子定位模型

根据直杆在水平面上的影子顶点数据推断可能的地点和日期，本文通过确定约束条件，以求解的竿影长和实际竿影长的相似度作为目标函数，建立基于遗传算法的太阳影子定位模型。

具体步骤如下：

Step 1：种群初始化。由题目可知可行解是由纬度，经度和日期组成，本文选用二进制编码把问题的可行解表示成遗传算法中的染色体，附件2中通过拟合求出的经度为，故纬度的取值范围，经度取值范围为，月取值范围，日取取值范围，根据二进制和十进制的对应关系，将十进制转化为二进制。

纬度二进制编码的一个可行解表示为；

经度二进制编码的一个可行解表示为；

月二进制编码的可行解能表示为，日二进制编码的可行解能表示为

将纬度、经度和日期的二进制编码并成一个行向量，该行向量即为染色体，其中一个可行解为：

同时，本题选择100个种群进行迭代繁衍。

Step 2：适应度函数。适应度函数是用来区分群体个体好坏的标准，是进行自然选择的唯一依据，将染色体中的二进制转化为十进制，于是可以得到相应的纬度、经度和日期，用求解的经纬度和日期按照问题一的公式(4-3)得出太阳高度角，不妨设杆长为米，可以根据公式(4-1)计算出21个时刻所对应的影长，为消去杆长的影响，按照如下公式进行处理：

可以得出影长之比，记附件中的影长为，(为附件中坐标)，可以得出实际影长之比：

表示可能的拍摄地点，则该染色体的适应度记为：

Step 3：交叉变异操作。交叉变异操作。本文的交叉和变异概率选用动态参数，参数的变化与进化代数相关。在种群早期，高交叉率，低变异率；在种群后期，低交叉率，高变异率。用这种方法减少种群早熟的可能性。经过多次试验发现参数为：

Step 4：选择操作。选择操作从旧群体中选择优良个体组成新的种群，以繁衍得到下一代本题基于适应度对旧群体进行选择，设定种群大小为100，故选取适应度最高的100个种群作为父代进行优胜劣汰。

Step 5：解码。将适应度最高的染色体解码，即将二进制转化为十进制，得到相应的纬度、经度和日期。

3.3.3. 模型求解

利用遗传算法对网格中的经纬度筛选，采用附表2、附表3中的数据，以影长和实际影长的比例作为适应度，将适应度最高的染色体解码，即将二进制转化为十进制，得到相应的纬度、经度和日期，如表5、表6所示。

3.4. 视频的预处理

用Matlab读取avi视频，将其转成jpg图片序列。

视频均为avi格式给出，处理结果图片见图3。为建立模型，从8:55开始，每隔1分钟提取出1张图片，共提取出40张图片，并从中提取出各帧的数据，提取第一帧如图3所示。

3.4.1. 灰度矩阵的获取

视频中提取出的图片均以jpg格式的图片给出。为建立模型，必须得到数字依据。所以读取各图片的灰度信息，将第张图片的灰度信息分别存入灰度值矩阵中:

其中，第张图像的数据矩阵中的元素值一般都在之间，灰度图像根据这些数据利用线性插值来

表5. 附件2大致经纬度及地点

表6. 附件3大致经纬度及地点

图3. 第一帧彩色图片

和图中的颜色种类匹配，不同的元素数值代表不同的亮度或灰度级，数值0代表黑色，数值255代表白色，数值越大，表明该位置像素点亮度越高。

3.4.2. 灰度矩阵的处理

利用Matlab编程，利用灰度矩阵做出灰度图像，第1帧的灰度图像如图4所示(将彩色图像转换为灰度图像)。

3.4.3. 二值矩阵的建立

为防止灰度值溢出，Matlab计算的灰度值会被限制在0~255之间。在模型计算中，为方便确定模型中杆长及杆影灰度矩阵，需将灰度值矩阵中杆长及杆影部分转化成二值矩阵，具体操作：

对于杆长的灰度矩阵，令

图4. 第一帧的灰度图像

对于随时间变化的杆影灰度矩阵，令

3.4.4. 杆长与杆影矩阵的定位

利用Matlab软件编程，对灰度矩阵进行多次运算，求解出杆长、杆影二值化矩阵边缘，从而确定合适的。

3.5. 模型建立

3.5.1. 边界定位模型

为了得到视频中随时间变化的杆影长度，采用边界定位法。它是基于二值化矩阵的两极化特性：二值化后的杆影灰度图像的右上边界的255灰度值与左下边界的255灰度值即为杆影的边界，即杆影的长度为两灰度值之间的距离。边界定位模型的具体步骤如下：

STEP 1：右上边界模型的构建

将第张图片的右上边界进行右上边界定位，即求第张图片矩阵从第行由下向上，第列由左向右开始，检测灰度值首先为255的元素，并提取其位置数据——。

STEP 2：左下边界模型的构建

将第张图片的左下边界进行左下边界定位，即求第张图片矩阵从第行由上向下，第列由右向左开始，检测灰度值首先为255的元素，并提取其位置数据——。

STEP 3：杆影长度的确定

将提取出的第张图片的右上边界位置数据与左下边界位置数据进行计算：

(4-1)

3.5.2. 多项式拟合确立初始经度

建立曲线拟合模型来估计当地正午时间，依据视频采集，将杆影长度进行拟合去逼近此动态过程，最终达到估计经度的目的。从灰度图像中提取出的杆影，得到部分时间的杆影长度如表7所示。

再利用相应时间与表7中数据按二次曲线进行拟合，使用最小二乘法确定拟合方程为

(4-2)

其中，为视频中杆影长度，为当地时间。

因为杆影最短的时刻即为当地正午时刻，故，所以初始经度为

(4-3)

其中，为视频所在地初始经度，为视频所在地杆影最短时刻。

3.5.3. 模型求解

利用Matlab软件编程，将灰度值矩阵中杆长及杆影部分转化成二值矩阵，分别得到直杆矩阵二值化后的灰度图像、杆影矩阵二值化后的灰度图像，如图5、图6所示。

表7. 视频中影长随时间变化

图5. 直杆矩阵二值化后的灰度图像

图6. 杆影矩阵二值化后的灰度图像

4. 结论——模型的总结、归纳及未来发展的展望

① 本文为分析影长的变化规律，运用天文知识，结合相关文献，得出太阳高度角关于太阳时角、赤纬角、方位角和本地纬度的关系式，利用几何关系得出影长，其中为杆长，为太阳高度角，建立基于太阳高度角的影长变化模型。② 知日期确定拍摄地点：要求根据影子顶点数据确定可能的拍摄地点，首先通过二次拟合求得经度的大致范围，再对经纬度网格化，采用启发式算法遍历所有格点，以经纬度求出的影长与实际影长的相似度作为目标函数，得出地理坐标为，大致为海南。建模时，发现启发式算法的收敛速度较慢，故运用遗传算法对经纬度全局搜索，以求得的影长和实际影长的相似度为适应度进行迭代，得出地点位海南省内。③ 有太阳影子确定可能的拍摄地点和日期：沿用问题二的思路进行建模，建立基遗传算法的太阳影子定位模型，采用二进制编码初始化种群，转化为十进制计算适应度，通过迭代得出地理坐标为，大致为新疆自治区和湖北省。④ 确定视频拍摄地点的数学模型，并给出若干个可能的拍摄地点；首先转化视频中部分图片并提取出灰度矩阵，对其中直杆、杆影矩阵进行二值化处理，根据其比例关系算出不同时刻的杆影长度，再沿用前面的思路进行建模，建立基于动态遗传算法的太阳影子定位模型。

通过确定经纬度和日期求出了不同时刻的太阳高度角，此模型可应用于太阳能电池的采光，通过调整电池板的朝向使之与太阳光线垂直，即能最大化接收太阳辐射能，提高其采光率。在我们建立模型的扩展上，未来则可以在时间未知的情况下定位，故该模型可应用于无GPS信号下的大致定位。但需要注意的是该模型只能确定多个可能的可行解，故若需要精确判断还需结合实际情况。特别的在视频确定日期地点的模型中，它不仅可以在计算机视觉领域广泛应用，还可以推广到其他领域，例如：刑事侦查中嫌疑人或物品的信息提取，测绘软件的开发等。目前，我们正致力于这些领域的发展，将基于遗传算法的太阳影子定位技术更加简洁完善。

文章引用

张 慧. 基于遗传算法的太阳影子定位模型及研究
The Sun Shadow Position Model on Gene Algorithms[J]. 数据挖掘, 2016, 06(01): 68-80. http://dx.doi.org/10.12677/HJDM.2016.61009

参考文献 (References)