1.本发明属于图像地理定位领域，是一种结合山区场景语义图建模和近似图编辑距离匹配的山区图像地理定位方法和系统。
背景技术：
2.图像地理定位任务是给定一张无地理位置标签的图像，识别并定位其拍摄位置。山区图像地理定位是图像地理定位中重要的一个分支，在山区搜救、旅游开发、反恐维稳等方面都有重要的应用前景。目前已经有一些山区图像地理定位的研究，但是山区图像地理定位还面临一些问题：山区图像数量较少，难以覆盖到大部分山地区域，无法使用现有的图像来构建山区图像数据库；山地区域场景图像往往只包含山体、天空、植被等弱纹理目标，难以实现基于局部纹理特征的图像匹配，同时语义信息、关系信息等未被有效利用。这些问题对山区图像定位带来了一定的困难。所以探究基于场景语义图的山区图像地理定位，有效利用上述的语义和关系信息来构建检索数据库并进行山区图像匹配定位为山区图像地理定位提供另外一种思路具有重要的研究意义。
技术实现要素：
3.本发明针对现有技术的不足，提供一种基于场景语义图的山区图像地理定位方法，本发明通过对渲染的深度图像提取几何特征，综合山区语义信息与关系信息，建立山区场景语义图检索数据库，然后利用近似图编辑距离算法进行图匹配，得到山区图像地理定位结果。
4.为了达到上述目的，本发明提供的技术方案是：一种基于场景语义图的山区图像地理定位方法，包括如下步骤：
5.步骤1，基于数字高程数据的对山地区域场景图片的深度图像进行渲染，获得参考图像库；
6.步骤2，对参考图像库中的图像进行山体几何特征特征提取；
7.步骤3，山区场景语义图建模；
8.语义图基于无向图结构，基于上述山区图像山体几何特征提取所得每一张图像的所有山体多边形及其之间的关系建模为图g(v，e)，图g由顶点集合v和边集合e构成，每座山体多边形构成一个顶点，山体多边形和多边形之间的关系构成边，并且分别为顶点和边设计相应的属性特征，以便进行图与图之间的编辑距离计算；
9.步骤4，基于近似图编辑距离的算法来计算两个语义图的编辑距离，计算将查询图g1转化为匹配图g2的编辑路径，输出编辑路径和路径的编辑距离，编辑距离结果越小表示两个图之间越相似，当距离在一定的误差范围之内，认为定位成功。
10.进一步的，步骤1的具体实现方式如下；
11.首先利用osg工具集，将dem数据的高程信息转换为具有lod三角网模型；
12.利用构建好的lod三角网模型，模拟真实场景图片的生成过程，制作深度渲染图
片，深度渲染图片中，每个像素表示该像素对应的真实位置处距离拍摄位置的距离，因为图像记录真实深度范围有限，将获取的是深度归一化值，最远处的值为1，最近处的值为0。
13.进一步的，步骤2的具体实现方式如下；
14.山体几何特征包括7项，前六项属于基本特征，第七项属于矩特征；
15.①
面积和周长
16.面积表示多边形的像素大小，周长是多边形边界上的像素长度；
17.②
边界描述
18.用链码描述边界，链码是一种通过对八邻域边界方向进行编码表示边界；
19.③
外接矩形和凸包
20.外接矩形完全包围多边形，凸包是一个满足多边形全部落在其内的凸多边形，且面积最小，使用graham法求解；
21.④
偏心率和伸长率
22.多边形的偏心率和伸长率和其长轴和短轴相关，长轴是多边形内可以容纳的最长线段，短轴是垂直于长轴的最长线段，偏心率是多边形短轴和长轴的比率；伸长率是外接矩形的宽度和长度的比值；
23.⑤
圆形性
24.多边形的圆形性表示近似圆形的程度，包括：紧凑度、球度、凸度；
25.⑥
形状变化程度
26.形状变化程度表示多边形和标准形状的差异，计算过程：计算多边形上的每一个点到等面积圆形边界的距离，计算所有距离的平方和然后除以点的数量，得到距离的均方误差，即为山体多边形的形状变化程度；
27.⑦
矩特征
28.hu矩用来系统性地描述多边形的特征，hu矩构造了7个不变性特征量，当多边形只进行任意平移、任意缩放以及任意旋转操作，hu矩保持不变；
29.由于上述7个不变性特征量因为量纲不一致，范围变化大，不能直接用于计算多边形之间的形状差异，所以对每个特征值先进行log变换：
30.hi＝-sign(hi)log(|hi|)
31.其中sign是符号函数，如果hi大于0则为1，小于0则为-1。
32.进一步的，步骤3的具体实现方式如下；
33.(1)场景语义图顶点构建
34.顶点构建是将图像中的山体多边形以及场景信息建模为图g中的顶点，图g中的顶点使用v＝{v1，v2…
,vn}表示由山体多边形形成的顶点集合，n为图像中山体的数量，每个山体多边形构成一个顶点v，每个顶点的特征包含山体多边形的边界、位置、面积、主轴角度以及hu矩特征；
35.(2)场景语义图边构建
36.边构建是将图像中的山体多边形之间的关系建模为语义图的边，顶点两两之间构成一条边，边使用e＝{e
11
,e
12
...,e
ij
...,e
nn
}表示，其中e
ij
表示连接顶点vi和vj的边，两两顶点构建一条边，所以边的数量为顶点之间的相对关系作为边的属性，边的属性包括：长度、角度。
37.进一步的，步骤4中基于近似图编辑距离进行山区图像定位的具体实现方式如下；
38.近似图编辑距离算法基于有序树，在构建新节点时根据二分图匹配算法进行编辑路径求解，求解过程为：设查询图g1和匹配图g2分别有n和m个顶点，所有的n m个顶点看做一个新图g
new
中的点，对于顶点，构建一个(n m)
×
(n m)编辑距离矩阵，对于g1和g2中的边也进行这样的操作；对于(n m)
×
(n m)的编辑距离矩阵使用二分图匹配算法寻找最优的顶点编辑，再根据顶点最优编辑确定相关联的边的编辑；
39.首先分别构建顶点和边的编辑距离矩阵cv和ce，μ表示顶点属性，ζ表示边属性，定义两个基本图g1＝(v1，e1，μ1，ζ1)和g2＝(v2，e2，μ2，ζ2)；v1＝(u1,
…
un)，v2＝(v1,
…
vm)；v1和v2分别表示查询图g1和匹配图g2的顶点集合，e1和e2分别表示查询图g1和匹配图g2的边集合，cv表示新图的顶点编辑距离矩阵，矩阵维度是(x y)
×
(x y)，其中x＝n，y＝m；ce表示新图的边编辑距离矩阵，矩阵维度为(x’ y’)
×
(x’ y’)，其中cv与ce的构建原理如下：
[0040][0041]
定义中间变量集合ε，可以将点回收至ε，或从ε中取点插入图中，使用(v
→
ε)表示删除一个顶点，(ε
→
v)表示插入一个顶点；因此上图中，c
ij
表示g1第i个顶点替换为g2第j个顶点(ui→
vj)距离，c
iε
表示g1第i个顶点删除(ui→
ε)距离，c
εj
表示g2第j个顶点插入(vj→
ε)距离；右下角(m
×
n)部分矩阵表示(ε
→
ε)，所以全为0，∞符号所在位置表示无效编辑操作；
[0042]
接下来进行有序树的构建和探索，有序树的构建和探索按照深度优先顺序，这种顺序下节点p比其子节点children(p)先访问，然后再回溯访问有序树的其他路径，有序树的根节点为r，满足已匹配顶点集已匹配边集待匹配顶点集pending-vertices
1,2
(r)＝v1∪v2，pending-edges
1,2
(r)＝e1∪e2，已编辑距离g(r)＝∞，未编辑距离lb(r)＝∞，初始化open集合包含有序树的节点，即部分编辑路径集合；
[0043]
将根节点r添加至open集合，然后构建有序树下一个节点，构建的准则是：对g1的顶点集合v1进行排序，每次从最有潜力的顶点及其编辑操作开始构建有序树的下一个节点；顶点排序过程是：找到一个二分图之间代价最小的顶点编辑路径，然后将行坐标最小的编辑操作所在的顶点作为最有潜力的顶点，这样就得到r节点的所有子节点children(r)，然后将children(r)添加至open集合，对open集合中所有的有序树节点即部分编辑路径计算代价值g(p) lb(p)，找到使之最小的p
min
，如果p
min
是一条完整的编辑路径，那么就返回结果，如果p
min
为空，那么就回溯遍历当前节点父节点的其它子节点。
[0044]
进一步的，编辑操作包括替换、插入和删除，操作对象包括顶点和边。
[0045]
进一步的，多边形主轴角度获取方式的计算公式为：
[0046][0047]
μ
20
、μ
02
和μ
11
均为二阶hu矩所构造的特征量。
[0048]
本发明提供一种基于场景语义图的山区图像地理定位系统，包括如下模块：
[0049]
图像库获取模块，用于基于数字高程数据的对山地区域场景图片的深度图像进行渲染，获得参考图像库；
[0050]
特征提取模块，用于对参考图像库中的图像进行山体几何特征特征提取；
[0051]
语义图构建模块，用于进行山区场景语义图建模；
[0052]
语义图基于无向图结构，基于上述山区图像山体几何特征提取所得每一张图像的所有山体多边形及其之间的关系建模为图g(v，e)，图g由顶点集合v和边集合e构成，每座山体多边形构成一个顶点，山体多边形和多边形之间的关系构成边，并且分别为顶点和边设计相应的属性特征，以便进行图与图之间的编辑距离计算；
[0053]
定位模块，用于基于近似图编辑距离的算法来计算两个语义图的编辑距离，计算将查询图g1转化为匹配图g2的编辑路径，输出编辑路径和路径的编辑距离，编辑距离结果越小表示两个图之间越相似，当距离在一定的误差范围之内，认为定位成功。
[0054]
与现有技术相比，本发明的优点和有益效果：本文针对山区图像地理定位问题，首次提出了基于场景语义图的山区图像地理定位方法。针对山地区域缺乏参考图像问题和山区图像目标纹理弱且难以匹配定位的特点，分别提出了山区图像场景信息提取和建模方法和基于图匹配的山区图像地理定位方法，首先利用山区地形数据建模得到水平视角的深度渲染图像，其次对山区深度渲染图像进行特征和语义关系提取构建山区场景语义图，最终通过语义图匹配实现定位。与现有技术相比，本发明构建得到了山区渲染图像的参考图像库，并提出基于图编辑距离的山区场景语义图相似度匹配算法，可以有效实现山区图像地理定位，具有广泛的应用价值。
附图说明
[0055]
图1为技术路线图；
[0056]
图2为lod三角网模型局部细节图；
[0057]
图3为深度图像渲染示意图；
[0058]
图4为山体多边形及其矩特征示例；
[0059]
图5为山区场景语义图构建示意图；
[0060]
图6为实验数据的场景语义图建模示意图；
[0061]
图7为实验数据语义图之间的编辑路径与编辑距离示例；
[0062]
图8为编辑距离匹配结果可视化示意图；
[0063]
图9为基于场景语义图的山区地理定位结果展示。
具体实施方式
[0064]
下面结合附图和实施例对本发明的技术方案作进一步说明。
[0065]
本发明通过对渲染的深度图像提取几何特征，综合山区语义信息与关系信息，建立山区场景语义图检索数据库，然后利用近似图编辑距离算法进行图匹配，得到山区图像
地理定位结果。本文技术路线主要包括两个部分：山区图像场景信息提取和建模方法、基于图匹配的山区图像地理定位。总体技术路线如附图1所示。
[0066]
1.基于数字高程数据的山区深度图像渲染
[0067]
对于山地区域的场景图片，由于缺乏足够的纹理信息和参考图片，场景图片目标定位利用遥感基础地理数据实现，即数字高程模型(dem)。dem一般采用栅格数据形式存储，并提供下视垂直视角的几何信息。但是，场景图片是拍摄者从接近水平的视角进行拍摄。因此，需要先对dem构建lod三角网，再渲染用户视角的图片，并构成参考图像库。
[0068]
(1)基于dem构建lod三角网模型
[0069]
细节层次结构(level of detail，lod)基于启发式算法，使用一个树结构来编码模型，每个树节点都表示一个地物对象的一个细节层次，叶节点层次最丰富。考虑到遥感基础地理数据覆盖范围大、数据量大的特点，三维渲染平台需要支持海量数据的渲染能力。本发明采用开源三维开发工具集osg构建三维渲染场景，实现模拟图片生成：首先利用osg工具集，将dem数据的高程信息转换为具有lod三角网模型。附图2是lod三角网模型局部细节图。
[0070]
(2)基于lod模型渲染模拟深度图像
[0071]
基于lod模型渲染模拟深度图像利用构建好的lod三角网模型，模拟真实场景图片的生成过程，制作深度渲染图片。深度渲染图片中，每个像素表示该像素对应的真实位置处距离拍摄位置的距离。因为图像记录真实深度范围有限，本发明获取的是深度归一化值，最远处的值为1，最近处的值为0。
[0072]
附图3是基于lod模型构建的水平视角深度渲染图。可以看到深度渲染图整体呈现黑白灰色。距离相机越远，颜色越白，反之越深。同时靠近相机的部分的细节较为明显，远处的山体的细节更加模糊，缺少清楚的细节。
[0073]
2.山区深度图像山体几何特征提取
[0074]
上述步骤(2)所得山区深度渲染图像中山体填充轮廓即为一个山区语义实体，此语义实体为多边形，其几何特征包括7项，前六项属于基本特征，第七项属于矩特征：
[0075]
①
面积和周长
[0076]
面积表示多边形的像素大小。周长是多边形边界上的像素长度。
[0077]
②
边界描述
[0078]
用链码描述边界，链码是一种通过对八邻域边界方向进行编码表示边界。
[0079]
③
外接矩形和凸包
[0080]
外接矩形完全包围多边形。凸包是一个满足多边形全部落在其内的凸多边形，且面积最小，使用graham法求解。
[0081]
④
偏心率和伸长率
[0082]
多边形的偏心率和伸长率和其长轴和短轴相关。长轴是多边形内可以容纳的最长线段，短轴是垂直于长轴的最长线段。偏心率是多边形短轴和长轴的比率；伸长率是外接矩形的宽度和长度的比值。
[0083]
⑤
圆形性
[0084]
多边形的圆形性表示近似圆形的程度，包括：紧凑度、球度、凸度。
[0085]
⑥
形状变化程度
[0086]
形状变化程度表示多边形和标准形状的差异，计算过程：计算多边形上的每一个点到等面积圆形边界的距离，计算所有距离的平方和然后除以点的数量，得到距离的均方误差，即为山体多边形的形状变化程度。
[0087]
⑦
矩特征
[0088]
hu矩可以用来系统性地描述多边形的特征，hu矩构造了7个不变性特征量。当多边形只进行任意平移、任意缩放以及任意旋转操作，hu矩保持不变。
[0089]
需要注意的是，上述7个不变性特征量因为量纲不一致，范围变化大，不能直接用于计算多边形之间的形状差异。所以对每个特征值先进行log变换：
[0090]hi
＝-sign(hi)log(|hi|)
[0091]
其中sign是符号函数，如果hi大于0则为1，小于0则为-1。
[0092]
附图4是一个山体多边形示例，以其左下角为原点提取的基本矩特征和hu矩，及根据矩特征计算得到的形心和角度。
[0093]
3.山区场景语义图建模
[0094]
附图5是山区场景语义图构建示意图，语义图主要基于无向图结构，将由上述山区图像山体几何特征提取所得每张图像的所有山体多边形及其之间的关系建模为图g(v，e)。图g由顶点集合v和边集合e构成。每座山体多边形构成一个顶点。山体多边形和多边形之间的关系构成边。并且分别为顶点和边设计相应的属性特征，以便进行图与图之间的编辑距离计算。
[0095]
(1)场景语义图顶点构建
[0096]
顶点构建是将图像中的山体多边形以及场景信息(如边界、位置和面积等)建模为图g中的顶点。图g中的顶点使用v＝{v1，v2
…
,vn}表示由山体多边形形成的顶点集合，n为图像中山体的数量，每个山体多边形构成一个顶点v。最终，每个顶点的特征包含山体多边形的边界、位置、面积、主轴角度以及hu矩五项。场景语义图顶点属性及说明如下表：
[0097]
表1场景语义图顶点属性
[0098]
顶点属性说明边界数组形式储存位置山体多边形形心面积边界内像素数量主轴角度基于hu矩获得，范围[-180
°
,180
°
]hu矩经过log变换的hu矩
[0099]
其中，多边形主轴角度获取方式的计算公式为：
[0100][0101]
μ
20
、μ
02
和μ
11
均为二阶hu矩所构造的特征量。
[0102]
(2)场景语义图边构建
[0103]
边构建是将图像中的山体多边形之间的关系建模为语义图的边。顶点两两之间构成一条边。边使用e＝{e
11
,e
12
...,e
nn
}表示。其中e
ij
表示连接顶点vi和vj的边。两两顶点构建一条边，所以边的数量为顶点之间的相对关系作为边的属性，边的属性主要包括：长
度、角度，场景语义图边属性如下表：
[0104]
表2场景语义图边属性
[0105][0106]
4.基于近似图编辑距离的山区图像定位
[0107]
(1)原理介绍
[0108]
近似图编辑距离算法基于有序树，在构建新节点时根据二分图匹配算法进行编辑路径求解。求解过程为：设图g1和g2分别有n和m个顶点。所有的n m个顶点看做一个新图g
new
中的点，对于顶点，构建一个(n m)
×
(n m)编辑距离矩阵，对于g1和g2中的边也进行这样的操作。对于(n m)
×
(n m)的编辑距离矩阵使用二分图匹配算法寻找最优的顶点编辑，再根据顶点最优编辑确定相关联的边的编辑。基本编辑操作包括替换、插入、删除，操作对象包括顶点、边。
[0109]
首先分别构建顶点和边的编辑距离矩阵cv和ce，μ表示顶点属性，ζ表示边属性。定义两个基本图g1＝(v1，e1，μ1，ζ1)和g2＝(v2，e2，μ2，ζ2)。v1＝(u1,
…
un)，v2＝(v1,
…
vm)。v1和v2分别表示查询图g1和匹配图g2的顶点集合，e1和e2分别表示查询图g1和匹配图g2的边集合，cv表示新图的顶点编辑距离矩阵，矩阵维度是(x y)
×
(x y)，其中x＝n，y＝m；ce表示新图的边编辑距离矩阵，矩阵维度为(x’ y’)
×
(x’ y’)，其中cv与ce的构建原理如下：
[0110][0111]
定义中间变量集合ε，可以将点回收至ε，或从ε中取点插入图中，使用(v
→
ε)表示删除一个顶点，(ε
→
v)表示插入一个顶点。因此上图中，c
ij
表示g1第i个顶点替换为g2第j个顶点(ui→
vj)距离，c
iε
表示g1第i个顶点删除(ui→
ε)距离，c
εj
表示g2第j个顶点插入(vj→
ε)距离。右下角(m
×
n)部分矩阵表示(ε
→
ε)，所以全为0。∞符号所在位置表示无效编辑操作。
[0112]
接下来进行有序树的构建和探索，有序树的构建和探索按照深度优先顺序，这种顺序下节点p比其子节点children(p)先访问，也意味有序树的构建和探索会先尽可能的深，然后再回溯访问有序树的其他路径。有序树的根节点为r，满足已匹配顶点集已匹配边集从顶点集合v1到v2的待匹配顶点集pending-vertices
1,2
(r)＝v1∪v2，从边集合e1到e2的待匹配边集pending-edges
1,2
(r)＝e1∪e2，已编辑距离g(r)＝∞，未编辑距离lb(r)＝∞。初始化open集合包
含有序树的节点，即部分编辑路径集合。
[0113]
首先，将根节点r添加至open集合，然后构建有序树下一个节点。构建的准则是：对g1的顶点集合v1进行排序，每次从最有潜力的顶点及其编辑操作开始构建有序树的下一个节点，这样就可以加速有序树的构建过程。顶点排序过程是：找到一个二分图之间代价最小的顶点编辑路径，然后将行坐标最小的编辑操作所在的顶点作为最有潜力的顶点。这样就得到r节点的所有子节点children(r)，然后将children(r)添加至open集合。然后对open集合中所有的有序树节点即部分编辑路径计算代价值g(p) lb(p)，找到使之最小的p
min
。如果p
min
是一条完整的编辑路径，那么就返回结果。如果p
min
为空，那么就回溯遍历当前节点父节点的其它子节点。
[0114]
(2)山区图像语义图匹配与定位实验
[0115]
实验具体使用上述所介绍的基于图编辑距离的算法来计算两个语义图的编辑距离，计算将查询图g1转化为匹配图g2的编辑路径。输出编辑路径(p
min
)和路径的编辑距离(最小的代价值g(p) lb(p))。如果距离结果越小表示两个图之间越相似。如附图6所示，对两张山区图像进行语义图建模：经过渲染得到山体语义实体，提取山体几何特征，建立山体场景语义图。
[0116]
计算两幅实验图像分别构建的语义图g1和g2之间的距离，g1有5个顶点，10条边；g2有2个顶点，1条边。计算g1和g2的距离可得如下表所示结果：
[0117]
表3g1和g2完全不同时的编辑距离输出结果
[0118][0119]
如附图7所示，可以看到图g1和g2的编辑距离为26172.22。顶点编辑路径包含5对顶点。(0
→
0),(2
→
1)表示将查询图g1的顶点0和2分别替换为匹配图g4的顶点0和1。(1
→
ε)、(3
→
ε)、(4
→
ε)表示将g1的其它顶点全部删掉，最终根据语义图之间的编辑距离反映图像之间的相似度。整个过程耗时0.18s，具备一定的可推广应用价值。
[0120]
如附图8所示，可以通过山区图像山体实例图像看到，左边图像的山体0和2和右边图像中的0和1从面积和相对方位方面综合考虑较为匹配。
[0121]
经过场景语义图匹配后，对每张查询图片都会得到一个参考结果序列。查询图像和参考图像都具有经纬度坐标，可以计算查询图像和参考图像之间的距离，如果距离在一定的误差范围之内，认为定位成功，查询图像的定位结果如图9所示。
[0122]
本发明还提供一种基于场景语义图的山区图像地理定位系统，包括如下模块：
[0123]
图像库获取模块，用于基于数字高程数据的对山地区域场景图片的深度图像进行渲染，获得参考图像库；
[0124]
特征提取模块，用于对参考图像库中的图像进行山体几何特征特征提取；
[0125]
语义图构建模块，用于进行山区场景语义图建模；
[0126]
语义图基于无向图结构，基于上述山区图像山体几何特征提取所得每一张图像的
所有山体多边形及其之间的关系建模为图g(v，e)，图g由顶点集合v和边集合e构成，每座山体多边形构成一个顶点，山体多边形和多边形之间的关系构成边，并且分别为顶点和边设计相应的属性特征，以便进行图与图之间的编辑距离计算；
[0127]
定位模块，用于基于近似图编辑距离的算法来计算两个语义图的编辑距离，计算将查询图g1转化为匹配图g2的编辑路径，输出编辑路径和路径的编辑距离，编辑距离结果越小表示两个图之间越相似，当距离在一定的误差范围之内，认为定位成功。
[0128]
各模块的具体实现方式与各步骤相同，本发明不予撰述。
[0129]
本文中所描述的具体实施例仅仅是对本发明精神作举例说明。本发明所属技术领域的技术人员可以对所描述的具体实施例做各种各样的修改或补充或采用类似的方式替代，但并不会偏离本发明的精神或者超越所附权利要求书所定义的范围。