留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

利用多等级相关性反馈进行空间场景匹配

陈占龙 张丁文 谢忠 吴亮

陈占龙, 张丁文, 谢忠, 吴亮. 利用多等级相关性反馈进行空间场景匹配[J]. 武汉大学学报 ● 信息科学版, 2018, 43(9): 1422-1428. doi: 10.13203/j.whugis20160360
引用本文: 陈占龙, 张丁文, 谢忠, 吴亮. 利用多等级相关性反馈进行空间场景匹配[J]. 武汉大学学报 ● 信息科学版, 2018, 43(9): 1422-1428. doi: 10.13203/j.whugis20160360
CHEN Zhanlong, ZHANG Dingwen, XIE Zhong, WU Liang. Spatial Scene Matching Based on Multilevel Relevance Feedback[J]. Geomatics and Information Science of Wuhan University, 2018, 43(9): 1422-1428. doi: 10.13203/j.whugis20160360
Citation: CHEN Zhanlong, ZHANG Dingwen, XIE Zhong, WU Liang. Spatial Scene Matching Based on Multilevel Relevance Feedback[J]. Geomatics and Information Science of Wuhan University, 2018, 43(9): 1422-1428. doi: 10.13203/j.whugis20160360

利用多等级相关性反馈进行空间场景匹配

doi: 10.13203/j.whugis20160360
基金项目: 

国家重点研发计划 2017YFC0602204

国家自然科学基金 41401443

国家自然科学基金 41671400

湖北省自然科学基金 2015CFA012

中央高校基本科研业务费专项资金优秀青-基金 CUG160226

详细信息

Spatial Scene Matching Based on Multilevel Relevance Feedback

Funds: 

The National Key R & D Program of China 2017YFC0602204

the National Natural Science Foundation of China 41401443

the National Natural Science Foundation of China 41671400

the Natural Science Foundation of Hubei Province 2015CFA012

the Fundamental Research Funds for the Central Universities CUG160226

More Information
    Author Bio:

    CHEN Zhanlong, PhD, associate professor, specializes in GIS theory research, geo-computation and spatial analysis, high performance computation. E-mail:Chenzhanlong2005@126.com

    Corresponding author: ZHANG Dingwen, PhD. E-mail:dingwenzhang@yahoo.com
  • 摘要: 现有的空间场景匹配方法利用低级描述子(如局部几何形状描述子、方向、拓扑)或其组成的简单二元空间关系建立模型来试图满足用户的描述需求,缺乏对用户级主观概念的反馈机制。将用户反馈机制应用到空间场景匹配过程中,以研究机器在学习用户需求后对空间场景匹配的影响。在运算过程中,用户对匹配结果进行相关度评估并反馈给模型,模型根据反馈结果动态地更新检索参数权重以模拟用户的主观感知,从而使得调整后的匹配运算更加贴近用户需求。通过进行用户调查及分析特征向量权重的收敛情况验证了此方法的有效性和效率,实验结果表明,根据用户反馈进行空间场景匹配具有很高的用户主观性强度,用户只需进行2~3次的反馈就能得到较为满意的结果,空间场景的匹配结果更符合人的空间认知。
  • 图  1  空间查询场景与数据库场景

    Figure  1.  Spatial Query Scene and Candidate Scene

    图  2  武汉居民地域数据

    Figure  2.  Wuhan Residential RegionData

    图  3  方向相似性匹配结果

    Figure  3.  Retrieval Results with Directional Similarity

    图  4  形状相似性匹配结果

    Figure  4.  Retrieval Results on Shapes Similarity

    图  5  不同返回场景数量的权重收敛曲线图

    Figure  5.  Convergence Curves of Weights with Different Feedback Scene Amount

    表  1  实验数据基本情况

    Table  1.   Introduction of Experimental Data

    数据集 点数量/个 区数量/个 总面积/km2
    武汉居民地域数据 47 112 1 576 146.05
    匹配场景 292 5 3.63
    下载: 导出CSV

    表  2  基于用户反馈算法的空间场景匹配运算有效性

    Table  2.   Effectiveness of Spatial Scene Retrieval Based on User Relevance Feedback

    用户 第1次迭代 第2次迭代 第3次迭代
    1 0.61 0.74(+13%) 0.83(+22%)
    2 0.58 0.69(+11%) 0.78(+20%)
    3 0.60 0.75(+15%) 0.81(+21%)
    4 0.55 0.67(+12%) 0.75(+20%)
    5 0.51 0.62(+11%) 0.84(+33%)
    6 0.63 0.75(+12%) 0.89(+26%)
    7 0.56 0.7(+14%) 0.82(+28%)
    8 0.53 0.69(+16%) 0.8(+33%)
    9 0.57 0.71(+14%) 0.89(+32%)
    10 0.62 0.79(+17%) 0.85(+23%)
    11 0.61 0.73(+12%) 0.82(+21%)
    12 0.64 0.72(+8%) 0.84(+20%)
    13 0.51 0.63(+12%) 0.77(+26%)
    14 0.49 0.6(+11%) 0.78(+29%)
    15 0.57 0.68(+11%) 0.88(+31%)
    16 0.54 0.67(+13%) 0.78(+24%)
    17 0.50 0.59(+9%) 0.77(+27%)
    18 0.59 0.72(+13%) 0.89(+30%)
    19 0.62 0.79(+17%) 0.91(+29%)
    20 0.57 0.72(+15%) 0.84(+27%)
    下载: 导出CSV

    表  3  不同样本数量的权重收敛情况

    Table  3.   Convergence of Weights with Different Sample Amount

    样本数量 权重 第0次迭代 第1次迭代 第2次迭代 第3次迭代
    20 WD 0.5 0.620 7 0.653 8 0.653 8
    WS 0.5 0.379 4 0.346 2 0.346 2
    10 WD 0.5 0.500 0 0.545 5 0.555 6
    WS 0.5 0.500 0 0.454 5 0.444 4
    5 WD 0.5 0.411 8 0.583 3 0.583 3
    WS 0.5 0.588 2 0.416 7 0.416 7
    下载: 导出CSV

    表  4  不同迭代次数下的场景匹配概率

    Table  4.   Spatial Scene Matching Probability Under Different Iterations

    迭代前 第1次迭代 第2次迭代 第3次迭代
    S1 0.935 0.856 0.808 0.808
    S2 0.899 0.745 0.713 0.713
    S3 0.848 0.873 0.896 0.896
    S4 0.809 0.753 0.701 0.701
    S5 0.799 0.973 0.985 0.985
    S6 0.798 0.647 0.596 0.596
    S7 0.797 0.865 0.893 0.893
    S8 0.796 0.751 0.726 0.726
    S9 0.795 0.892 0.913 0.913
    S10 0.794 0.643 0.587 0.587
    下载: 导出CSV
  • [1] 刘涛, 杜清运, 闫浩文.空间点群目标相似度计算[J].武汉大学学报·信息科学版, 2011, 36(10):1149-1153 http://ch.whu.edu.cn/CN/abstract/abstract684.shtml

    Liu Tao, Du Qingyun, Yan Haowen.Spatial Similarity Assessment of Point Clusters[J]. Geomatics and Information Science of Wuhan University, 2011, 36(10):1149-1153 http://ch.whu.edu.cn/CN/abstract/abstract684.shtml
    [2] 刘涛, 杜清运, 毛海辰.空间线群目标相似度计算模型研究[J].武汉大学学报·信息科学版, 2012, 37(8):992-995 http://ch.whu.edu.cn/CN/abstract/abstract293.shtml

    Liu Tao, Du Qingyun, Mao Haichen. Spatial Similarity Assessment Model and Its Application in Line Groups[J].Geomatics and Information Science of Wuhan University, 2012, 37(8):992-995 http://ch.whu.edu.cn/CN/abstract/abstract293.shtml
    [3] Moratz R, Lücke D, Mossakowski T. A Condensed Semantics for Qualitative Spatial Reasoning About Oriented Straight Line Segments[J].Artificial Intelligence, 2011, 175(16):2099-2127 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=JJ0224560840
    [4] Li Bonan, Fonseca F. TDD:A Comprehensive Model for Qualitative Spatial Similarity Assessment[J].Spatial Cognition and Computation, 2006, 6(1):31-62 doi:  10.1207/s15427633scc0601_2
    [5] 陈占龙, 周林, 龚希, 等.基于方向关系矩阵的空间方向相似性定量计算方法[J].测绘学报, 2015, 44(7):813-821 http://d.old.wanfangdata.com.cn/Periodical/chxb201507016

    Chen Zhanlong, Zhou Lin, Gong Xi, et al. A Quantitative Calculation Method of Spatial Direction Similarity Based on Direction Relation Matrix[J].Acta Geodaetica et Cartographica Sinica, 2015, 44(7):813-821 http://d.old.wanfangdata.com.cn/Periodical/chxb201507016
    [6] Jan S, Schwering A, Schultz C, et al. RCC11: A Finer Topological Representation for the Alignment of Regions in Sketch Maps[C]. International Workshop on Qualitative Reasoning, Minneapolis, USA, 2015
    [7] Chipofya M, Schwering A, Binor T. Matching Qualitative Spatial Scene Descriptions á la Tabu[M]//Chipofya M, Schwering A, Binor T. Advances in Soft Computing and Its Applications. Berlin, Heidelberg: Springer, 2013
    [8] Rocha R, Saito P T M, Bugatti P H. A Novel Framework for Content-Based Image Retrieval Through Relevance Feedback Optimization[C]. Iberoamerican Congress on Pattern Recognition, Montevideo, Uruguay, 2015
    [9] Lu H, Huang X, Yang L, et al. A Novel Long-Term Learning Algorithm for Relevance Feedback in Content-Based Image Retrieval[J]. Telecommunications Systems, 2013, 54(3):265-275 doi:  10.1007/s11235-013-9732-z
    [10] Mosbah M, Boucheham B. Majority Voting Re-ranking Algorithm for Content Based-Image Retrieval[C]. Metadata and Semantics Research Conference, Manchester, UK, 2015
    [11] 陈占龙, 吕梦楼, 吴亮, 等.基于特征矩阵和关联图的空间场景相似性度量方法[J].武汉大学学报·信息科学版, 2017, 42(7):956-962 http://ch.whu.edu.cn/CN/abstract/abstract5780.shtml

    Chen Zhanlong, Lü Menglou, Wu Liang, et al. Space Scene Similarity Measurement Based on Feature Matrix and Associated Graph[J]. Geomatics and Information Science of Wuhan University, 2017, 42(7):956-962 http://ch.whu.edu.cn/CN/abstract/abstract5780.shtml
    [12] 陈占龙, 冯齐奇, 吴信才.复合面状对象拓扑关系的表达模型[J].测绘学报, 2015, 44(4):438-444 http://d.old.wanfangdata.com.cn/Periodical/chxb201504012

    Chen Zhanlong, Feng Qiqi, Wu Xincai. Representation Model of Topological Relations Between Complex Planar Objects[J]. Acta Geodaetica et Cartographica Sinica, 2015, 44(4):438-444 http://d.old.wanfangdata.com.cn/Periodical/chxb201504012
    [13] Chen Zhanlong, Xu Yongyang, Wu Liang. Vector Planar Elements:Geometrical Similarity Measurement Based on Fourier Descriptors[J]. Geomatica, 2015, 69(4):385-394 doi:  10.5623/cig2015-401
    [14] Tong S, Koller D. Support Vector Machine Active Learning with Applications to Text Classification[J]. Journal of Machine Learning Research, 2001, 2(11):45-66 doi:  10.1162-153244302760185243/
    [15] Rui Y, Huang T. Optimizing Learning in Image Retrieval[C]. IEEE Conference on Computer Vision and Pattern Recognition, Hilton Head Island, SC, USA, 2000
    [16] Chen Y, Zhou X S, Huang T S. One-Class SVM for Learning in Image Retrieval[C]. International Conference on Image Processing, Makedonia Palace Hotel, Thessaloniki, Greece, 2001
    [17] Zhou X S, Huang T S. Small Sample Learning Du-ring Multimedia Retrieval Using Biasmap[C]. The 2001 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, Kauai, Hawaii, USA, 2001
    [18] Rui Y, Huang T S, Ortega M, et al. Relevance Feedback:A Power Tool for Interactive Content-Based Image Retrieval[J]. IEEE Transactions on Circuits and Systems for Video Technology, 1998, 8(5):644-655 doi:  10.1109/76.718510
  • [1] 罗芳, 艾廷华, 贾小斌.  空间自相关支撑下的地类分布模式一致性评价 . 武汉大学学报 ● 信息科学版, 2022, 47(7): 1017-1024. doi: 10.13203/j.whugis20200179
    [2] 张嘉琪, 杜开虎, 任书良, 王瑞凡, 关庆锋, 陈文辉, 姚尧.  多源空间大数据场景下的家装品牌线下广告选址 . 武汉大学学报 ● 信息科学版, 2022, 47(9): 1406-1415. doi: 10.13203/j.whugis20190468
    [3] 黄丽娜, 姚翔宇, 田姮, 应申.  空间认知能力与三维寻路绩效的相关性分析 . 武汉大学学报 ● 信息科学版, 2022, 47(5): 673-682. doi: 10.13203/j.whugis20200247
    [4] 李维炼, 朱军, 张昀昊, 付林, 胡亚, 尹灵芝, 戴义.  空间语义约束的泥石流灾害VR场景融合建模及交互方法 . 武汉大学学报 ● 信息科学版, 2020, 45(7): 1073-1081. doi: 10.13203/j.whugis20180329
    [5] 潘晓, 张翠娟, 吴雷, 闫晓倩.  众源地理空间数据的空间文本相关性分析 . 武汉大学学报 ● 信息科学版, 2020, 45(12): 1910-1918. doi: 10.13203/j.whugis20200185
    [6] 张丁文, 陈占龙, 谢忠.  利用松弛标记法进行空间场景匹配 . 武汉大学学报 ● 信息科学版, 2018, 43(5): 752-758. doi: 10.13203/j.whugis20150719
    [7] 翟卫欣, 程承旗.  一种空间权重矩阵的优化方法 . 武汉大学学报 ● 信息科学版, 2017, 42(6): 731-736. doi: 10.13203/j.whugis20150015
    [8] 陈占龙, 吕梦楼, 吴亮, 徐永洋.  基于特征矩阵和关联图的空间场景相似性度量方法 . 武汉大学学报 ● 信息科学版, 2017, 42(7): 956-962. doi: 10.13203/j.whugis20140450
    [9] 陈换新, 孙群, 肖强, 肖计划.  空间数据融合技术在空间数据生产及更新中的应用 . 武汉大学学报 ● 信息科学版, 2014, 39(1): 117-122.
    [10] 许俊奎, 武芳, 钱海忠, 马芳博.  一种空间关系相似性约束的居民地匹配算法 . 武汉大学学报 ● 信息科学版, 2013, 38(4): 484-485.
    [11] 罗安, 王艳东, 龚健雅.  顾及上下文的空间信息服务组合语义匹配方法 . 武汉大学学报 ● 信息科学版, 2011, 36(3): 368-372.
    [12] 冯昕, 杜世宏, 舒红.  空间权重矩阵对空间自相关的影响分析——以我国肾综合征出血热疾病为例 . 武汉大学学报 ● 信息科学版, 2011, 36(12): 1410-1413.
    [13] 王汉东, 乐阳, 李宇光, 黄玲.  城市商业服务设施吸引力的空间相关性分析 . 武汉大学学报 ● 信息科学版, 2011, 36(9): 1102-1106.
    [14] 邓敏, 徐凯, 赵彬彬, 徐锐.  基于结构化空间关系信息的结点层次匹配方法 . 武汉大学学报 ● 信息科学版, 2010, 35(8): 913-916.
    [15] 雷波, 李清泉.  复杂交通场景中车辆视频检测的背景提取与更新 . 武汉大学学报 ● 信息科学版, 2009, 34(8): 906-909.
    [16] 孙建国, 艾廷华, 帅赟, 郭峰林.  类型地图的空间相关关系 . 武汉大学学报 ● 信息科学版, 2008, 33(1): 101-104.
    [17] 一种基于空间虚拟场景的森林冠层雷达相干散射模型 . 武汉大学学报 ● 信息科学版, 2008, 33(2): 120-123.
    [18] 傅仲良, 吴建华.  多比例尺空间数据库更新技术研究 . 武汉大学学报 ● 信息科学版, 2007, 32(12): 1115-1118.
    [19] 方圣辉, 龚浩.  动态调整权重的光谱匹配测度法分类的研究 . 武汉大学学报 ● 信息科学版, 2006, 31(12): 1044-1046.
    [20] 张力, 沈未名, 张祖勋, 张剑清.  基于空间约束的神经网络影像匹配 . 武汉大学学报 ● 信息科学版, 2000, 25(1): 55-59.
  • 加载中
图(5) / 表(4)
计量
  • 文章访问数:  1295
  • HTML全文浏览量:  105
  • PDF下载量:  296
  • 被引次数: 0
出版历程
  • 收稿日期:  2017-09-13
  • 刊出日期:  2018-09-05

利用多等级相关性反馈进行空间场景匹配

doi: 10.13203/j.whugis20160360
    基金项目:

    国家重点研发计划 2017YFC0602204

    国家自然科学基金 41401443

    国家自然科学基金 41671400

    湖北省自然科学基金 2015CFA012

    中央高校基本科研业务费专项资金优秀青-基金 CUG160226

    作者简介:

    陈占龙, 博士, 副教授, 主要研究方向为地理计算与空间分析、高性能计算等。Chenzhanlong2005@126.com

    通讯作者: 张丁文, 博士。dingwenzhang@yahoo.com
  • 中图分类号: P208

摘要: 现有的空间场景匹配方法利用低级描述子(如局部几何形状描述子、方向、拓扑)或其组成的简单二元空间关系建立模型来试图满足用户的描述需求,缺乏对用户级主观概念的反馈机制。将用户反馈机制应用到空间场景匹配过程中,以研究机器在学习用户需求后对空间场景匹配的影响。在运算过程中,用户对匹配结果进行相关度评估并反馈给模型,模型根据反馈结果动态地更新检索参数权重以模拟用户的主观感知,从而使得调整后的匹配运算更加贴近用户需求。通过进行用户调查及分析特征向量权重的收敛情况验证了此方法的有效性和效率,实验结果表明,根据用户反馈进行空间场景匹配具有很高的用户主观性强度,用户只需进行2~3次的反馈就能得到较为满意的结果,空间场景的匹配结果更符合人的空间认知。

English Abstract

陈占龙, 张丁文, 谢忠, 吴亮. 利用多等级相关性反馈进行空间场景匹配[J]. 武汉大学学报 ● 信息科学版, 2018, 43(9): 1422-1428. doi: 10.13203/j.whugis20160360
引用本文: 陈占龙, 张丁文, 谢忠, 吴亮. 利用多等级相关性反馈进行空间场景匹配[J]. 武汉大学学报 ● 信息科学版, 2018, 43(9): 1422-1428. doi: 10.13203/j.whugis20160360
CHEN Zhanlong, ZHANG Dingwen, XIE Zhong, WU Liang. Spatial Scene Matching Based on Multilevel Relevance Feedback[J]. Geomatics and Information Science of Wuhan University, 2018, 43(9): 1422-1428. doi: 10.13203/j.whugis20160360
Citation: CHEN Zhanlong, ZHANG Dingwen, XIE Zhong, WU Liang. Spatial Scene Matching Based on Multilevel Relevance Feedback[J]. Geomatics and Information Science of Wuhan University, 2018, 43(9): 1422-1428. doi: 10.13203/j.whugis20160360
  • 空间场景是一组地理对象及其空间关系——拓扑、距离和方向关系的集合。本文主要研究由空间面对象,即多边形集组成的空间场景,如湖泊、地块或建筑物等具有面积属性的地理对象。空间场景匹配可以广泛地应用于手描场景导航、碎片场景定位、相似场景浏览等,无论是在人们的日常生活、科学研究,还是在专业刑侦分析中都可以发挥重大作用。

    空间场景匹配中存在的主要问题有:(1)针对同一空间场景,不同匹配任务中所要求的相似度精度不同;(2)由于匹配目的不同,不同背景的用户对空间场景的描述会有所不同;(3)相似度主要取决于空间场景的描述参数。这三方面的事实相互联系且相互影响,导致人们难以事先设定一个通用的相似性度量算法。传统的空间场景匹配方法基本上是使用局部几何形状描述子或二元空间关系来建立与用户需求的关联,例如,空间对象的几何形状被表现为多维空间中的点[1-2],且通过该空间中两个对应点之间的矢量距离反映几何相似度[3],忽略了实体之间的空间关系。基于要素比较的模型则将空间场景表现为要素的集合,场景相似度计算可表示为要素间的匹配过程[4],没有考虑到人类认知过程的复杂性。转化模型则通过空间关系间的转化来计算相似度[5-6],空间关系之间的转化距离可定义为将一个约束变量转化为另一个约束变量所需的复杂度[7],过于注重空间关系而忽略了对空间实体自身特征的描述。

    “语义间隙”描述了从检索条件中直接提取的低级要素与用户真实需求之间的矛盾。减少语义间隙的一个有效方法是用户反馈算法[8-10](relevance feedback,RF),将检索过程分解为若干个连贯的检索循环,并允许用户基于每次检索循环的结果提供反馈信息,以优化下一个检索循环。基于这些反馈,搜索引擎逐渐学习到用户在当前检索过程中所需的特征。

    本文研究如何利用用户反馈机制解决空间场景匹配的智能化问题,使得空间场景的匹配结果更符合人的空间认知,即将普通的空间匹配转换为用户引导式匹配,过程中包含多次交互且用户成为匹配过程中不可缺少的一部分,其优点是:(1)用户不需了解匹配系统的内部细节;(2)匹配任务被分解为易于理解的步骤;(3)提供一个可控架构来加强重要变量及弱化次要变量在匹配过程中的影响。

    设空间场景的特征向量集为v={vi},1 ≤iNFNF为特征向量个数。本文以实体对间的特征向量为基本单位构建描述空间场景的特征矩阵,由于篇幅原因,空间场景特征向量的提取方法请参考文献[11-13]中的具体描述。对于在有m个实体的数据库场景中搜索出匹配场景Q中的n个对应实体,可先计算出场景间的实体对基于任意特征向量的距离,得到初始匹配矩阵。以图 1为例,匹配场景中有xyz 3个空间实体,现需从数据库场景(包含实体abcd)中找出与匹配场景对应的实体,基于描述场景的特征向量集,可计算出匹配场景中空间实体与数据库中实体的初始匹配概率矩阵(式(1)),其中,矩阵行描述了特征向量vi在每个实体对上的匹配概率,列描述了每个实体对在不同特征向量v上的匹配概率。本文用Pxy, abv1表示空间实体对(x, y)和(a, b)在空间场景特征向量v1上的匹配概率。

    $$ \left[ {\begin{array}{*{20}{c}} {P_{xy,ab}^{{\mathit{\boldsymbol{v}}_1}}}&{P_{xy,ac}^{{\mathit{\boldsymbol{v}}_1}}}& \cdots &{P_{xy,cd}^{{\mathit{\boldsymbol{v}}_1}}}&{P_{xz,ab}^{{\mathit{\boldsymbol{v}}_1}}}&{P_{xz,ac}^{{\mathit{\boldsymbol{v}}_1}}}& \cdots &{P_{xz,cd}^{{\mathit{\boldsymbol{v}}_1}}}&{P_{yz,ab}^{{\mathit{\boldsymbol{v}}_1}}}&{P_{yz,ac}^{{\mathit{\boldsymbol{v}}_1}}}& \cdots &{P_{yz,cd}^{{\mathit{\boldsymbol{v}}_1}}}\\ {P_{xy,ab}^{{\mathit{\boldsymbol{v}}_2}}}&{P_{xy,ac}^{{\mathit{\boldsymbol{v}}_2}}}& \cdots &{P_{xy,cd}^{{\mathit{\boldsymbol{v}}_2}}}&{P_{xz,ab}^{{\mathit{\boldsymbol{v}}_2}}}&{P_{xz,ac}^{{\mathit{\boldsymbol{v}}_2}}}& \cdots &{P_{xz,cd}^{{\mathit{\boldsymbol{v}}_2}}}&{P_{yz,ab}^{{\mathit{\boldsymbol{v}}_2}}}&{P_{yz,ac}^{{\mathit{\boldsymbol{v}}_2}}}& \cdots &{P_{yz,cd}^{{\mathit{\boldsymbol{v}}_2}}}\\ \vdots &{}&{}&{}&{}&{}&{}&{}&{}&{}&{}& \vdots \\ {P_{xy,ab}^{{\mathit{\boldsymbol{v}}_{{N_F}}}}}&{P_{xy,ac}^{{\mathit{\boldsymbol{v}}_{{N_F}}}}}& \cdots &{P_{xy,cd}^{{\mathit{\boldsymbol{v}}_{{N_F}}}}}&{P_{xz,ab}^{{\mathit{\boldsymbol{v}}_{{N_F}}}}}&{P_{xz,ac}^{{\mathit{\boldsymbol{v}}_{{N_F}}}}}& \cdots &{P_{xz,cd}^{{\mathit{\boldsymbol{v}}_{{N_F}}}}}&{P_{yz,ab}^{{\mathit{\boldsymbol{v}}_{{N_F}}}}}&{P_{yz,ac}^{{\mathit{\boldsymbol{v}}_{{N_F}}}}}& \cdots &{P_{yz,cd}^{{\mathit{\boldsymbol{v}}_{{N_F}}}}} \end{array}} \right] $$ (1)

    图  1  空间查询场景与数据库场景

    Figure 1.  Spatial Query Scene and Candidate Scene

    • 在匹配场景Q和数据库场景D间进行全局的相似性度量通常是对特征向量距离进行线性结合,场景匹配相似度计算公式为:

      $$ S\left( {D,Q} \right) = \sum\limits_{i = 1}^{{N_F}} {\sum\limits_{j = 1}^{{N_P}} {{w_i}{d_{ij}}\left( {\mathit{\boldsymbol{v}}_{ij}^D,\mathit{\boldsymbol{v}}_{ij}^Q} \right)} } $$ (2)

      式中,vij为特征子向量; i为特征向量序号;j为空间实体对序号;dij描述了场景间特征子向量vij的距离;wi为特征向量vi的权重;NP为实体对数量。

    • 用户反馈过程中至少包含3个步骤: (1)系统向用户展示一系列结果;(2)用户标记每个结果与当前检索行为的相关性;(3)系统根据反馈结果调整其检索行为。若将相关和不相关结果分别标记为正、负样本,则当前用户的相关性反馈方式主要有3种:(1)对样本进行正、反的二元反馈[14-15]; (2)进行正样本反馈[16-17]; (3)对正、反样本进行相关(不相关)度的评估[18]

      本文尝试将多等级的相关性用户反馈算法[14]与空间场景匹配相结合,提出交互式空间场景匹配的运算框架,并对该算法在空间场景匹配中的有效性和效率进行了分析。文献[18]将相关和不相关两个概念细化为高度相关、相关、一般相关、不相关和极不相关5个等级。各个等级的相关性分数s为:

      $$ s = \left\{ {\begin{array}{*{20}{c}} {\begin{array}{*{20}{c}} {3,}\\ {1,}\\ {0,}\\ { - 1,}\\ { - 3,} \end{array}}&\begin{array}{l} 高度相关\\ 相关\\ 一般相关\\ 不相关\\ 极不相关 \end{array} \end{array}} \right. $$ (3)

      在首次迭代中,将特征向量权重W = {wi}初始化为一组无偏差权重集w0,即每个特征向量初始地拥有同等重要性:

      $$ {w_i} = w_i^0 = \frac{1}{{{N_F}}} $$ (4)

      基于用户反馈结果,对返回结果的特征向量距离值进行分析以重算权重值,设用户返回结果集为R,并用Rt(t=1…5)描述5个等级的结果集,l为集合Rt中结果的数量。在特征向量距离的计算过程中,为避免大数量级的特征向量削弱其他特征向量,本文假设每个距离都有相同的波动范围(从0到1),设特征向量集vk={vijk, i =1…NF, j = 1…NP, k=1…l},则Rt中特征子向量间的平均距离值μij为:

      $$ {\mu _{ij}} = \frac{2}{{l\left( {l - 1} \right)}}\sum\limits_{p = k}^l {\sum\limits_{q = p + 1}^l {{d_{ij}}\left( {\mathit{\boldsymbol{v}}_{ij}^p,\mathit{\boldsymbol{v}}_{ij}^q} \right)} } $$ (5)

      根据平均距离值可以计算出Rt中任意结果pq间的标准化距离向量d

      $$ \mathit{\boldsymbol{d}}\left( {{\mathit{\boldsymbol{v}}^p},{\mathit{\boldsymbol{v}}^q}} \right) = {\left[ {\frac{{{d_{11}}\left( {\mathit{\boldsymbol{v}}_{11}^p,\mathit{\boldsymbol{v}}_{11}^q} \right) - {\mu _{11}}}}{{k{\sigma _{11}}}} \cdots \frac{{{d_{ij}}\left( {\mathit{\boldsymbol{v}}_{ij}^p,\mathit{\boldsymbol{v}}_{ij}^q} \right) - {\mu _{ij}}}}{{k{\sigma _{ij}}}} \cdots \frac{{{d_{nm}}\left( {\mathit{\boldsymbol{v}}_{nm}^p,\mathit{\boldsymbol{v}}_{nm}^q} \right) - {\mu _{nm}}}}{{k{\sigma _{nm}}}}} \right]^{\rm{T}}} $$ (6)

      其中,标准偏差σij为:

      $$ {\sigma _{ij}} = \frac{2}{{l\left( {l - 1} \right)}}\sum\limits_{p = k}^l {\sum\limits_{q = p + 1}^l {{{\left[ {{d_{ij}}\left( {\mathit{\boldsymbol{v}}_{ij}^p,\mathit{\boldsymbol{v}}_{ij}^q} \right) - {\mu _{ij}}} \right]}^2}} } $$ (7)

      对特征向量的标准化距离进行分析,可以重算特征向量的权重值,而通过重算权重值则可以实现在全局匹配操作中对给定特征向量影响值的增强或减弱。设dijt={dijt(vij1, vij2)…dijt(vill-1, vijl)}为结果集Rt中特征向量的标准化距离集,可得:

      $$ \mu _i^t = \frac{1}{{\left| {d_{ij}^t} \right|}}\sum\limits_{p = 1}^t {\sum\limits_{q = p + 1}^k {{d_{ij}}\left( {\mathit{\boldsymbol{v}}_{ij}^p,\mathit{\boldsymbol{v}}_{ij}^q} \right)} } $$ (8)

      本文中,若某场景被标记为相关场景,其必然存在与匹配场景相似的特征; 反之, 则不存在相似之处。对于特征向量vi,将其在5个结果集中的标准化距离与相关分数的乘积相加,并求平均值得:

      $$ {\mu _i} = {\rm{avg}}\left( {\sum\limits_{t = 1}^5 {{s_t}\mu _i^t} } \right) $$ (9)

      其中,st为式(3)中的相关性分数。

      若此值大于0,则表明其在场景匹配中发挥了相应的作用;若小于0,则表明此次匹配中对应的特征向量没有产生影响,则将其权重设置为0。对于其他如平均值为0的模糊情况,则取匹配开始时的初始权重值:

      $$ {w_i} = \left\{ \begin{array}{l} \frac{1}{{{\mu _i}}},{\mu _i} > 0\\ 0,{\mu _i} < 0\\ \frac{1}{{{N_F}}},其他 \end{array} \right. $$ (10)
    • 本文基于上述方法从武汉居民地域数据中选择匹配场景,并从该数据中定位匹配场景的空间位置(见图 2),武汉市居民地域数据从武汉数据集中获取。

      图  2  武汉居民地域数据

      Figure 2.  Wuhan Residential RegionData

      图 2中的居民地域数据进行分析可知,地理对象间的拓扑关系构成单一,只存在相离关系,对象形状都较为规范(大部分为四边形),因此选择方向关系和对象几何形状作为场景的描述参数,并使用笛卡尔方向模型获取空间对象间的方向关系v1,通过傅里叶算子描述空间对象的几何特征v2 :

      $$ v = \left\{ {{\mathit{\boldsymbol{v}}_i}} \right\} = \left\{ {{\mathit{\boldsymbol{v}}_1},{\mathit{\boldsymbol{v}}_2}} \right\} = \left\{ {\mathit{\boldsymbol{C}},\mathit{\boldsymbol{F}}} \right\} $$ (11)

      式中,v为特征向量集合; C为方向关系特征;F为对象几何形状的傅里叶描述子。

    • 影响空间场景算法的3个参数为用户反馈次数It,相关集合中的对象数量及匹配参数权重集。用户反馈次数越多,权重就能更精准,但不能期望用户持续执行反馈行为,因此在实验中将It设置为3,并研究每次反馈后的收敛情况。

    • 在匹配过程中,假设用户每次进行相关性反馈操作,系统会返回10个根据当前权重计算出的最相似场景,图 3 (a)中匹配场景处于左上角,数据的属性描述如表 1所示,匹配场景的点数量、区数量和空间范围都远小于居民地域数据,从1 576个区中匹配出匹配场景中5个区的可能匹配形式约为8.050 8×1013种。

      图  3  方向相似性匹配结果

      Figure 3.  Retrieval Results with Directional Similarity

      表 1  实验数据基本情况

      Table 1.  Introduction of Experimental Data

      数据集 点数量/个 区数量/个 总面积/km2
      武汉居民地域数据 47 112 1 576 146.05
      匹配场景 292 5 3.63

      在初始权重情况下,10个返回场景以从上至下和从左至右的顺序进行排列。某些场景与匹配场景的形状较为相似,其他则可能有相似的方向关系。假设用户真正需求是“基于方向关系寻找相似空间场景”,在基于用户反馈的空间场景匹配框架中,用户不需要将其所需信息一一映射到特征向量上,只需要对返回的空间场景进行相关度评估,并以此来表达自身需求。

      图 3是典型的相似方向关系的场景匹配。在用户进行反馈之前,每幅场景都被默认为与当前匹配场景非常相关,用户可以根据自己判断在相关场景下的相关度下拉列表中进行选择。在该例中,场景(1)、(4)被标记为非常相关,场景(2)、(3)、(5)、(6)、(7)、(8)、(9)、(10)被标记为相关。基于用户的反馈信息,模型动态地调整权重并强调方向要素,改进后的匹配结果如图 3(b)所示。

      相似地,图 4则展示了典型的基于几何形状匹配场景的过程,匹配场景同样位于左上角,最佳的10个返回场景按照从左至右和从上至下的顺序排列。用户根据匹配场景中的形状对返回场景进行评估,场景(4)、(5)、(8)由于具有与匹配场景中相似的空间实体而被标记为高度相关,其他场景则被标记为不相关。基于用户的反馈信息,系统动态地调整权重并强调形状要素,改进后的匹配结果如图 4(b)所示,场景(1)与匹配场景一致。

      图  4  形状相似性匹配结果

      Figure 4.  Retrieval Results on Shapes Similarity

      RI是相关场景(包括高度相关和相关场景)集合,RE是系统返回的结果场景集合,则有效性定义为:

      $$ \eta = \frac{{{R_I}}}{{{R_E}}} $$ (12)

      本文为验证实验有效性,邀请了来自不同专业领域的20个用户对匹配系统进行评估。用户可随机选择感兴趣的空间实体组成场景,并将其作为匹配场景在空间数据库中进行匹配,从而观察系统返回场景并计算用户反馈算法的有效性。用户并不关心系统的实现细节,如特征矩阵由哪些要素组成,只需凭着人类的空间认知本能进行选择和反馈,从而测试系统在学习用户真正需求上的能力。表 2为用户在进行空间场景查询时计算所得的有效性及在用户反馈算法下的有效性增幅百分数。

      表 2  基于用户反馈算法的空间场景匹配运算有效性

      Table 2.  Effectiveness of Spatial Scene Retrieval Based on User Relevance Feedback

      用户 第1次迭代 第2次迭代 第3次迭代
      1 0.61 0.74(+13%) 0.83(+22%)
      2 0.58 0.69(+11%) 0.78(+20%)
      3 0.60 0.75(+15%) 0.81(+21%)
      4 0.55 0.67(+12%) 0.75(+20%)
      5 0.51 0.62(+11%) 0.84(+33%)
      6 0.63 0.75(+12%) 0.89(+26%)
      7 0.56 0.7(+14%) 0.82(+28%)
      8 0.53 0.69(+16%) 0.8(+33%)
      9 0.57 0.71(+14%) 0.89(+32%)
      10 0.62 0.79(+17%) 0.85(+23%)
      11 0.61 0.73(+12%) 0.82(+21%)
      12 0.64 0.72(+8%) 0.84(+20%)
      13 0.51 0.63(+12%) 0.77(+26%)
      14 0.49 0.6(+11%) 0.78(+29%)
      15 0.57 0.68(+11%) 0.88(+31%)
      16 0.54 0.67(+13%) 0.78(+24%)
      17 0.50 0.59(+9%) 0.77(+27%)
      18 0.59 0.72(+13%) 0.89(+30%)
      19 0.62 0.79(+17%) 0.91(+29%)
      20 0.57 0.72(+15%) 0.84(+27%)

      在所有用户实验中,相关性反馈操作提高了匹配的有效性,总的来说,第3次迭代后能得到最大的有效性提升。而且,迭代次数多于5或6次时并不能得到太大的性能提升,这可归结于使用低等级要素来详细描述空间场景内容的限制。

    • 本文通过分析特征向量权重的收敛速度来检验模型的效率。

      1) 权重更新。为验证迭代过程中的权重收敛情况,同时考虑到用户操作的可行性及舒适度,本文分别对训练样本数量为20、10和5时的情况进行了测试。表 3描述了基于上述样本数量,几何特征向量权重和方向特征向量权重在3次迭代中的变化。

      表 3  不同样本数量的权重收敛情况

      Table 3.  Convergence of Weights with Different Sample Amount

      样本数量 权重 第0次迭代 第1次迭代 第2次迭代 第3次迭代
      20 WD 0.5 0.620 7 0.653 8 0.653 8
      WS 0.5 0.379 4 0.346 2 0.346 2
      10 WD 0.5 0.500 0 0.545 5 0.555 6
      WS 0.5 0.500 0 0.454 5 0.444 4
      5 WD 0.5 0.411 8 0.583 3 0.583 3
      WS 0.5 0.588 2 0.416 7 0.416 7

      表 3中可以分析出,权重收敛主要发生在第1、2次迭代中,且几乎都在第3次迭代时达到了稳定,而训练样本为5时,其收敛过程出现波动,图 5为权重收敛情况的对应曲线。根据收敛曲线可知,若样本数量n较大,则在第1次迭代中权重向最终权重收敛最快,这是因为返回结果的数量越多,反馈信息就越多,匹配性能越好。在第2和第3次迭代中,权重的收敛情况对于不同的返回场景数量几乎是独立的,因为在第1次反馈后,大部分理想的对象都已被找出,随后的性能与返回场景的数量几乎是独立的。若结合程序稳定性及用户舒适度进行考虑,训练样本数量设置为10应是最佳选择,但此设置只针对本文实验数据,在实际操作中应根据不同数据的特点进行调优。

      图  5  不同返回场景数量的权重收敛曲线图

      Figure 5.  Convergence Curves of Weights with Different Feedback Scene Amount

      2) 场景匹配概率。以10个样本的情况为例,表 4描述了每次迭代中场景的相似度。

      表 4  不同迭代次数下的场景匹配概率

      Table 4.  Spatial Scene Matching Probability Under Different Iterations

      迭代前 第1次迭代 第2次迭代 第3次迭代
      S1 0.935 0.856 0.808 0.808
      S2 0.899 0.745 0.713 0.713
      S3 0.848 0.873 0.896 0.896
      S4 0.809 0.753 0.701 0.701
      S5 0.799 0.973 0.985 0.985
      S6 0.798 0.647 0.596 0.596
      S7 0.797 0.865 0.893 0.893
      S8 0.796 0.751 0.726 0.726
      S9 0.795 0.892 0.913 0.913
      S10 0.794 0.643 0.587 0.587

      在初始权重的情况下,场景S1具有与匹配场景最大的相似度;第1次迭代后,模型根据用户反馈重新调整权重,此时场景S5的相似度最高,其他场景的相似度也进行了对应的变动;在第2和第3次迭代后,S5和其他相关场景的相似度增强,相应地,不相关场景的相似度进一步降低。

    • 随着地理信息系统及空间分析技术的日趋成熟,空间场景的匹配和快速匹配成为研究热点。传统的空间场景缺乏使用低级的描述要素来表现出高级的人类思维概念的方法,本文基于用户反馈技术将人机交互引入空间场景匹配,用户只需对其匹配场景进行一个粗糙的初始描绘,并通过相关性反馈不断地修改原始描绘信息,较大地缓解了用户描述场景的负担,且能更精确地捕捉到用户的需求。

      下一步的工作将对空间场景匹配过程中最佳的或次佳的权重更新策略进行研究,如期望最大化方法来进行更深入的探索。

参考文献 (18)

目录

    /

    返回文章
    返回