三维地图降维的基本思路是采用“ 降维” 的思想把图书馆原始三维地图转化为二维地图, 即将图书馆按楼层进行“ 切片” , 然后将切片平铺在一个平面上, 再将所有的楼梯视为连接线, 把每层“ 切片” 连接起来, 构成一个大的二维地图。

图书馆内定位和导航需要依赖一个完整的路标系统(Landmark System), 在特定的关键点位置上设置路标, 并进行编码, 以方便后续管理和使用。

(1) 图中路标位置的选取

图书馆每层“ 切片” 中的房间正门、楼梯出入口、拐角、书架等视为路标结点, 把通道视为线, 将所有结点连接成一个网状图。

(2) 路标编码

为方便管理手机和用户扫描, 对路标进行编码, 并采用广泛使用的QR码(Quick Response Code)生成相应的二维码, 各关键点位置编码按表2中的规则进行编制。

表2

表2

表2 路标编码规则 地点编码 编码位数 取值范围 分馆编码 1 1-9 楼层编码 2 01-99 楼梯编码 2 01-99 房间、拐角编码 3 001-999 书架路标编码 3 001-999

表2 路标编码规则

分馆编码取1-9之间的一位整数, 用于表示不同的分馆; 楼层编码取2位^[5]; 楼梯编码按一定规则由小到大顺序编制, 其末尾6位都为0; 房间、拐角等结点依据楼梯编码再递增生成编码, 这些结点的末尾3位保持为0; 房间内对书架进行编码, 同一个房间内的书架编码仅最后3位有区别。这样的编码方式在绝大多数情况下能满足大多数使用需求。典型场景编码示例如表3所示:

表3

表3

表3 路标编码示例 地点 编码 主馆3楼1号楼梯003房间新书书库 10301003000 主馆3层阅览室第2个书架 10301002002 主馆3层2号楼梯 10302000000 主馆3层2号楼梯附近通道上一拐角 10302001000

表3 路标编码示例

(3) 路标之间连接边的权值计算

将路标作为结点, 通路作为连接线, 根据建筑CAD图纸按文献[7]中的方法生成一个大的网络图。各路标之间权值的具体计算方法如下: 水平方向路标之间的权值取路标之间的步行时间。通过距离除以成人平均步行速度(1.2米/秒)的方式计算; 垂直方向路标之间的权值可根据层高用几何方法计算, 也可以按如下公式计算:

(1)

其中, w₁为楼梯上下方向之间的权值, m代表阶梯数量, x为一个阶梯的高度, y为一个阶梯的宽度, n为楼梯连接区域直线距离上地面瓷砖数量, l为一块瓷砖的长度。

电梯路标之间的权值计算要考虑电梯平均等待时间, 主要是计算图书馆层高, 如无合适工具测量, 可按如下公式计算:

w₂=x/v+t₁(2)

其中, x为每层楼的高度; v为电梯运行速度, 其值参考JG/T5010-92电梯的配置与选择, 一般10层以下图书馆选用1 m/s, 10-20层选1.5-1.75 m/s, 超过20层选2-2.5 m/s; t₁为平均等待时间, 一般为一个常数, 需要根据电梯实际运行速度具体情况具体对待。

当前位置确定: 通过扫描当前路标位置信息二维码, 确定当前位置; 目标位置确定: 目标位置指拟寻找图书所在的书架。有些非常规范的图书自动化管理系统中, MARC数据905字段中的馆藏信息非常完善, 记录每本图书所在的书架及所在层数。此时确定目标位置则非常简单, 直接通过Web Service技术将此馆藏数据读取出来并显示到手机客户端。但是, 目前大多数图书馆因为现实条件的限制, 905字段中仅存储了索书号、馆名等简单信息, 没有存储图书详细馆藏位置。考虑到大多数图书馆的实际情况, 在本系统中重新建立图书索书号与所在书架的多对一映射关系, 具体映射关系如图1所示:

图1

	Figure Option ViewDownloadNew Window
	图1 图书索引号与馆藏位置映射图

基于此位置映射表, 在本系统中借助Web Service技术在手机端搜索图书信息, 并通过索书号到位置映射表中找到图书所在书架。

仅提供当前位置定位并对目标位置地点进行标识是最基本的智能处理, 如能进一步提供导航路线将提高用户体验。目前如果直接对所有馆内结点所构成的图进行路径搜索, 效率将比较低。经过分析发现, 图书馆内路标结点的分布存在一定的规律, 一般在给定地图的情况下, 只需关键结点的指示就可以找到行走路径^{[8, 9]}, 根据表2的编码规则, 同一个房间内所有书架结点前8位编码相同, 且末尾三位为000的编码代表房间入口, 不全为0的代表房间内书架。基于此可以得出在搜索当前位置与目标位置时, 大部分房间内的结点是不用参与到路径搜索运算的, 房间内结点的搜索只涉及终点所在的房间。为提高搜索效率, 构建生成高层路径图, 即将馆内各房间、通道拐角、楼梯等路标结点抽象为一个结点, 连接各房间的通道抽象为连接线, 构建成一个简化的高层抽象路径图。

基于此分层思想, 提出一种高效的改进A* 算法— — HEAA (Hierarchical Encoded A* Algorithm)^①(① 程序下载地址: http://218.92.23.107/siit.rar.), 将A* 算法与分层思想结合, 对抽象出来的高层路径图应用A* 算法, 避免直接应用A* 算法导致搜索结点过多、效率较低的问题。设当前起点为s, 终点为e, 取二者编码前8位, 末尾加上000, 生成房间结点H_s、H_e, 判断H_s是否与H_e相等, 若相等则位于同一房间内, 直接计算s和e之间的最短导航路径; 若不相等则表示在不同房间内, 在高层抽象路径图上应用A* 算法寻找H_s和H_e的最短路径P1, 然后再求出H_e到e结点的最短路径P2。最后合并P1、P2生成最终路径P。读者在某房间时是可以找到所在房间入口的, 因此不考虑起点s到H_s的路径。

考虑到馆内通道大多按纵横方式分布, 在应用A* 算法时选择Manhattan距离^[10], 算法实现伪代码如下:

void main(){

initialize 2-D graph;

initialize higher layer graph;

input s, e;

//求起点所属房间H_s和终点所属房间H_e

string Hs=left(s, 8)+” 000” ;

string He=left(e, 8)+” 000” ;

if(Hs==He)

P=Astar(s, e);

else

{

P1=Astar(Hs, He);

P2=Astar(He, e);

P=Combine (P1, P2);

}

Output(P); //输出最终路径

}

将该图书馆按层进行切片, 并将各层切片平铺在一个平面上, 把各楼层之间的楼梯视为连线, 将各楼层切片连接到一起, 生成二维地图, 最终效果如图2所示:

图2

	Figure Option ViewDownloadNew Window
	图2 某单位图书馆示意图

为建立图书索书号和图书馆藏位置之间的映射表, 根据图书馆内图书分布情况, 将同一个书架的图书映射为一个结点, 并根据实际情况变化在系统中调整该表。

将图书馆内各房间、拐角、楼梯、书架视为结点并进行编码, 生成网址和结点编码的二维码, 打印后贴于各结点对应的物理位置上, 如楼道的天花板或书架的明显位置^{[11, 12]}。路标结点之间以步行时间为权值^[13], 建立如图3所示的路标系统(权值省略), 再将馆内房间视为一个结点, 生成高层抽象路径图, 如图4所示:

图3

	Figure Option ViewDownloadNew Window
	图3 路标系统

图4

	Figure Option ViewDownloadNew Window
	图4 路标结点的高层抽象路径图

(1) 查询书目: 通过手机登录该图书馆管理系统, 输入要检索图书的名称, 搜索得到图书名称、索书号等信息。

(2) 确定目标位置: 在手机上单击检索到的书目信息, 通过索书号与位置映射表获得实际馆藏详细位置图, 给出类似“ 三楼自科7架” 的位置信息。当图书在多个馆藏地点时, 由读者进行选择, 目标位置以图3中的结点e为例。

(3) 确定当前位置s: 通过扫描当前位置路标二维码的方式确定, 如图3中的s点为起点, 对应房间名称为102, 可以扫描当前位置二维码确定当前位置。

(4) 导航: 导航时先判断起点s的位置, 如其编码末尾3位为000, 则把结点s直接当作高层图上的起始房间结点H_s, 图3中H_s与s就属于此种情况; 如发现起点末尾3位不为000, 则表示起点在房间内, 则先求出其编码前8位后再补3个0, 得到所在房间结点H_s。在确定H_s后, 应用A* 算法求出H_s到目标图书所在房间结点H_e的最短路径P1, 再应用A* 算法求出H_e到e的最短路径P2, 合并P1、P2生成最终路径P。图3中的示例是查询台s到三楼某房间内书架结点e的路径。

本算法中假设目标图书馆中共有n个结点, 图书馆共有m个房间, 每个房间内书架结点数平均为k个, 除书架外结点数为t, 则全馆的结点数为m× k+t个, 即:

n= m× k+t (3)

直接使用A* 算法, 需要参与运算的结点数最多是n个, 即m× k+t个, 而HEAA算法需要参与计算的结点数最多是m+k+t个。A* 算法和HEAA算法最多参与计算的结点数关系如下。

(4)

由公式(4)可以看出, 当房间数m越大, 室内书架k的值越大, 则分子与分母的差异越大。HEAA算法在A* 算法的基础之上做了进一步优化, 尽管在时间复杂度上与原A* 算法保持一致, 但由于使用分层搜索的思想^[14], 减少了参与运算的结点范围, 尤其避免了在不必要的房间内搜索, 总体上提升了算法效率。

本实验基于Android4.03平台, 测试手机为HuaweiT8830, 通过网络连接至服务器。图5中的示例以主馆借书处入口为起点(编码10101003000), 通过系统的查询界面搜索目标图书, 在此搜索名称为“ Android 4高级编程” 的图书, 其索书号为“ TN929.53/276” 。

图5

	Figure Option ViewDownloadNew Window
	图5 基于Web Service的图书搜索界面

点击“ 图书定位” 后可通过图书分类号与书架的映射表得出图书所在位置为“ 三楼自科阅览室书架(编码10102003012)” , 转入到馆内地图界面, 在此界面中扫描当前位置二维码, 可确定当前位置, 再应用HEAA路径搜索算法, 得到导航路径, 整个过程如图6所示:

图6

	Figure Option ViewDownloadNew Window
	图6 图书定位与导航

通过多次随机搜索图书, 获得测试数据, 分析发现在系统中若采用HEAA算法, 在搜索空间上大约能减少30%-50%, 搜索时间也得到了优化, 具体情况如表4所示:

表4

表4

表4 HEAA算法导航测试与对比 (s, e) A* HEAA Node Time Node Time (10101003000, 10102003012) 44 223 15 107 (10101003000, 10201005018) 39 185 19 119 (10101003000, 10301112016) 36 164 24 137

表4 HEAA算法导航测试与对比