2019, Vol. 44引用本文 |
| 图像显著度和信息量均衡的地标链生成方法 |  [PDF全文] |
行人导航服务需要以尽可能小的空间认知负担来引导行人[1]。地标是重要的导航线索，利用地标参考的路线指示可降低行人认路负担、增加行人导航自信[2]。现有研究主要利于地图和地标影像序列引导用户[3, 4]，提供的地标影像让行人对所处环境认知仍不全面。地标选择研究包括基于行程距离、路径复杂度和路段地标数量的路径选择算法[5]、有向通视图构建与地标链生成方法[6]等，没有地标的视觉显著程度等属性，行人在利用地标作为导航线索时，无显著视觉特征的地标会消耗行人大量的视觉搜索时间，甚至可能导致行人辨识地标失败。
本文利用导航路径上的全景图增强地标线索，提出基于图像显著度和信息量均衡的地标链生成方法，建立了地标显著度、全景图信息量和地标切换次数的多目标模型，并利用遗传算法[7, 8]求解该多目标优化问题生成最优地标链。
1 地标链生成方法 1.1 地标链选择的多目标优化模型地标链是指行人能够通过连续的地标引导完成寻路任务的地标序列，如图 1所示。
 |
| 图 1 导航路径上的地标序列 Fig.1 A Sequence of Landmarks on the Navigation Path |
地标显著度是指地标在全景图中的视觉显著度，显著度高的地标更容易引起行人的注意[9, 10]。地标在全景图中一般会占据一定的图像区域，本文利用改正后的ITTI模型[11, 12]来计算全景图中的地标显著度。选择全景图中视觉显著度高的地标作为备选导航地标；采用对比色理论[13]，通过地标区域占比最高的颜色，寻找它在色相环中的对比色，利用对比色来框选地标，让全景图地标更明显，并用图像增强引起的图像信息量[14]变化作为地标链生成过程的一个优化指标。
本文提出一种面向地标链选择的多目标模型，包括最大的地标视觉显著度、最小的全景图信息量变化、最少的地标切换次数3个优化目标。
| $ \left\{ \begin{array}{l} {S_{{\rm{max}}}} = \mathop \sum \limits_{i = 1}^n {S_{i, j}}\\ {I_{{\rm{min}}}} = \mathop \sum \limits_{i = 1}^n \Delta {I_{i, j}}\\ {N_{{\rm{min}}}} = \mathop \sum \limits_{i = 2}^n {n_i} \end{array} \right. $ | (1) |
式中, S为地标链上所有最优地标在全景图上显著度的和，其中Sij表示编号为i的全景图上编号为j的地标的显著度值，由改正后的ITTI模型计算得到；I为地标链上所有最优地标在显著标记后带来的全景图信息量变化的和；ΔIij表示编号为j的地标经过显著标记后造成编号为i的全景图信息量变化，全景图的信息量即图像的二维信息熵；N为全路径中地标的总切换次数；ni表示地标切换次数，
| $ {V_{{\rm{max}}}} = {w_1}S' + {w_2}I' + {w_3}N' $ | (2) |
式中，w1、w2、w3表示3种优化目标的权重(w1+w2+w3=1)；S′、I′、N′分别表示目标S、I、N进行归一化处理后的值，使3种优化目标的值具有相同的量纲，式(2)可以表示为：
| $ \begin{array}{l} {V_{{\rm{max}}}} = {w_1}\frac{{S - {S_{{\rm{min}}}}}}{{{S_{{\rm{max}}}} - {S_{{\rm{min}}}}}} + {w_2}\frac{{{I_{{\rm{max}}}} - I}}{{{I_{{\rm{max}}}} - {I_{{\rm{min}}}}}} + \\ \;\;\;\;\;\;\;\;\;{w_3}\frac{{{N_{{\rm{max}}}} - N}}{{{N_{{\rm{max}}}} - {N_{{\rm{min}}}}}} \end{array} $ | (3) |
式中, Smax、Smin分别表示地标链上所有最优地标在全景图上显著度和的最大、最小值；Imax、Imin分别表示地标链上所有最优地标在显著标记后造成全景图信息量变化和的最大值、最小值；Nmax、Nmin分别表示地标切换次数的最大值、最小值。
1.2 地标链选择的优化算法本文利用遗传算法解决多目标模型的优化问题。对全景图中的地标进行编号，选择实数编码(如1~100), 在每张全景图中选择一个地标，整个地标链就是一条染色体编码；设置种群规模的大小为n，初始化种群数据；以目标函数Vmax为优化目标，按照个体适应值占群体的概率
实验区域选择在武汉市汉街商业步行街，路径从步行街入口开始，穿过街道到达终点(地铁站)，路线全程如图 2所示。首先，利用Ricoh Theta全景相机等间距拍摄导航路径上的连续鱼眼全景图，共计72张，编号1~72；然后，利用理光景达PC版软件进行鱼眼全景图的倾斜和上下矫正得到矩形全景图；最后，从全景图中提取地标共计50个，分别编号1~50，标记后全景图信息量减去标记前全景图得到全景图信息量的变化值，编号1~72的72张全景图，共50个地标在每张全景图中的显著度值和进行地标标记引起的全景图信息量变化如图 2所示。
 |
| 图 2 全景图中进行显著标记后的地标显著度和标记前后全景图的信息量的改变量 Fig.2 Landmark Significance in the Panorama After Marking and Change of Panorama Information |
本文设计了9种权重组合(w1，w2，w3)分别为：1(1，0，0)、2(0，1，0)、3(0，0，1)、4(1/2，1/3，1/6)、5(1/2，1/6，1/3)、6(1/3，1/2，1/6)、7(1/3，1/6，1/2)、8(1/6，1/2，1/3)、9(1/6，1/3，1/2)，并对这9种权重组合进行了实验，其中，权重组合1~3不进行目标均衡，权重组合4~9是对目标重要程度不同所赋予的不同权重，行人可以根据实际情况选择或设计自己偏好的权重组合。权重组合1~3是地标链的地标显著度、全景图信息量变化和地标切换次数的单目标模型，可以分别计算出它们各自的最大值和最小值，得到多目标优化模型的模型参数值：Smin为8 434.58, Smax为14 705.57, Imin为3.59, Imax为6.84, Nmin为8，Nmax为71。
2.2 导航路径的地标链选择结果本文根据前面计算得到的模型参数值迭代计算权重组合4~9得到最优地标链，迭代次数如图 3所示。
 |
| 图 3 不同权重组合下的迭代收敛 Fig.3 Iterative Convergence of Different Weight Combinations |
由图 3(a)可知，针对实验数据集，传统遗传算法迭代2 000次内可以得到收敛结果；由图 3(b)可知，本文通过引进vi，加入优化策略后，迭代在100次以内就可以收敛，大大减少了迭代次数。权重组合1得到的解是地标显著度和最大的地标链组合，会导致地标切换次数多且全景图信息量变化过大；权重组合2得到的解是显著增强后全景图信息量总变化最小的地标链，而其地标显著度低且地标切换次数多；权重组合3得到的解是全路径范围内地标切换次数最小的地标链，带来的问题表现为地标显著度过低；权重组合4和权重组合5得到的解的地标显著度较高，在全景图信息量和地标切换次数上的侧重较小；权重组合6和权重组合8得到的解的全景图信息量变化较小，而地标显著度相对较低，地标切换次数相对较多；权重组合7和权重组合9得到的解的地标切换次数较少，地标显著度和全景图信息量的变化效果相对较差。
实验结果的最优地标链中地标的显著度如图 4所示。从图 4可以看出，最优地标链的曲线(红色)位于所有曲线的上部区域，说明地标链上的整体地标显著度均较高，能够为行人带来较大的视觉吸引力。实验结果表明，该权重组合下的多目标优化计算得到的地标链中，地标的显著度均大于全景图中全部地标的显著度均值，且69%的地标为单张全景图中显著度最高的地标。实验结果表明，该模型在计算过程中可以较好地顾及指标地标显著度，能够选择视觉上更明显的地标形成地标链。
 |
| 图 4 在权重组合5下的最优地标链在显著标记后的地标显著度 Fig.4 Landmark Significance of Optimal Landmark Chain in Weight Combination 5 After Marking |
表 1统计了组成该地标链的地标的显著度值及地标链显著度均值和地标链显著度最大值。通过表 1可以发现，本文选择的导航地标在显著性标记后造成的全景图信息量变化有70%小于全景图中全部地标的均值，而且18%的地标直接选择了引起全景图信息量变化最小的地标，在应用过程中，地标链上的地标在显著性标记后对全景图信息量影响较小。
| 表 1 地标链中地标的显著度取值 Tab.1 Landmark Significance in the Landmark Sequences |
 |
笔者统计出在权重组合5下选择的导航地标在显著性标记后造成的全景图信息量变化，以及全景图中所有地标在显著性标记后造成的全景图信息量变化均值和最小值如表 2所示。
| 表 2 地标链中地标标记后全景图信息量变化值 Tab.2 Change of Panorama Information in the Landmark Sequences |
 |
2.3 与传统地标链生成方法的对比
通过对比本文方法与文献[6]中的地标链生成算法可以发现，两种方法生成的地标链在地标显著度上差异明显，如图 5所示，本文方法生成的地标链地标显著度有65%是高于文献[6]的，28%是重合的；本文方法地标切换次数比文献[6]中方法少。其原因主要是由于传统方法在地标链规划算法中仅考虑了地标切换次数和单次引导距离，没有考虑地标的本身特性，也没有考虑地标在真实环境中的视觉显著性。
 |
| 图 5 两种方法生成地标链的地标显著度差异 Fig.5 Difference of the Landmark Sequences in Landmark Significance |
笔者统计出本文和文献[6]两种方法生成的地标链在地标显著度、全景图信息量变化和地标切换次数3个目标整体上的差异。本文方法和文献[6]方法的地标切换次数分别为24次和31次；地标链的地标显著度均值分别为190.640 0和158.930 0；全景图信息量变化的均值分别为0.069 3和0.069 8。
3 结束语本文提出了基于图像显著度和信息量均衡的地标链生成方法，该方法建立了地标显著度、全景图信息量和地标切换次数的多目标模型，并实现了基于遗传算法的多目标优化方法。通过实验，验证了该模型能够同时兼顾行人导航过程中对地标视觉显著性高、图像信息量小及地标切换次数少的多重需求，并与其他地标序列生成方法进行了对比，验证了该方法的可行性和有效性。在本文的实验研究中，仅选取了商业步行街环境下的路线进行了实验，要得到更精细的行人导航服务，今后将考虑对行人导航环境进一步分类，针对不同类型的环境对多目标模型的目标或权重分配进行相应的调整。
| [1] |
Fang Zhixiang, Li Qingquan, Zhang Xing, et al. A GIS Data Model for Landmark-Based Pedestrian Navigation[J]. International Journal of Geographical Information Science, 2012, 26(5): 817-838. DOI:10.1080/13658816.2011.615749 |
| [2] |
May J A, Ross T, Steven H B, et al. Pedestrian Nav-igation Aids: Information Requirements and Design Implications[J]. Personal and Ubiquitous Computing, 2003, 7(6): 331-338. DOI:10.1007/s00779-003-0248-5 |
| [3] |
Hile H, Grzeszczuk R, Liu A, et al. Landmark-Based Pedestrian Navigation with Enhanced Spatial Reaso-ning[C]. International Conference on Pervasive Computing, Nara, Japan, 2009 https: //www.researchgate.net/publication/221015889_Landmark-Based_Pedestrian_Navigation_with_Enhanced_Spatial_Reasoning
|
| [4] |
Hile H, Vedantham R, Cuellar G, et al. Landmark-Based Pedestrian Navigation from Collections of Geotagged Photos[C]. International Conference on Mobile and Ubiquitous Multimedia, Umeå, Sweden, 2008 https: //www.researchgate.net/publication/221342528_Landmark-based_pedestrian_navigation_from_collections_of_geotagged_photos?ev=prf_cit
|
| [5] |
张星, 李清泉, 方志祥, 等. 顾及地标与道路分支的行人导航路径选择算法[J]. 武汉大学学报·信息科学版, 2013, 38(10): 1 239-1 242. |
| [6] |
张星, 李清泉, 方志祥. 面向行人导航的地标链生成方法[J]. 武汉大学学报·信息科学版, 2010, 35(10): 1 240-1 244. |
| [7] |
涂雪珠.遗传算法在多目标优化中的应用[D].福州: 福州大学, 2004 http://cdmd.cnki.com.cn/Article/CDMD-10386-2004035016.htm
|
| [8] |
Goldberg D. Genetic Algorithm in Search, Optimization, and Machine Learning[M]. Boston: Addison-Wesley Professional, 1989.
|
| [9] |
冯辉.视觉注意力机制及其应用研究[D].北京: 华北电力大学, 2011
|
| [10] |
Borji A, Sihite D N, Itti L. Probabilistic Learning of Task-Specific Visual Attention[C]. IEEE Conference on Computer Vision and Pattern Recognition, Providence, Rhode Island, 2012 https: //www.researchgate.net/publication/262349491_Probabilistic_learning_of_task-specific_visual_attention
|
| [11] |
Itti L, Koch C, Niebur E. A Model of Saliency-Based Visual Attention for Rapid Scene Analysis[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1998, 20(11): 1 254-1 259. DOI:10.1109/34.730558 |
| [12] |
Achanta R, Hemami S, Estrada F, et al. Frequency-Tuned Salient Region Detection[C]. Computer Vision and Pattern Recognition, Miami, FL, USA, 2009
|
| [13] |
Fareed M M S, Qi Chun, Ahmed G, et al. Saliency Detection by Exploiting Multi-features of Color Contrast and Color Distribution[J]. Computers and Electrical Engineering, 2018, 70: 551-566. DOI:10.1016/j.compeleceng.2017.08.027 |
| [14] |
牛勇, 邱香, 傅小兰. 视角和信息量对静态图像短时记忆的影响[J]. 人类工效学, 2007, 13(1): 1-3. DOI:10.3969/j.issn.1006-8309.2007.01.001 |
| [15] |
Ting Chuankang, Su Chienhao, Lee Chungnan. Multi-parent Extension of Partially Mapped Crossover for Combinatorial Optimization Problems[J]. Expert Systems with Applications, 2010, 37(3): 1 879-1 886. DOI:10.1016/j.eswa.2009.07.082 |