基于视频采集的Visual Map数据库建立方法及利用该数据库的室内视觉定位方法

摘要

基于视频采集的Visual Map数据库建立方法及利用该数据库的室内视觉定位方法，涉及室内定位导航领域。是为了解决现有方法的室内视觉定位精度低，且费时费力的问题。本发明在快速建立基于视频的Visual Map数据库的基础上，通过载有视频获取设备的平台在匀速直线过程中进行视频拍摄，并且通过对所获得的视频进行处理来记录视频中帧的坐标位置信息以及图像匹配信息。在线的定位阶段，系统将带定位用户上传的图片与基于视频的Visual Map数据库通过利用感知哈希算法计算而来的哈希值进行粗匹配，再通过获得的粗匹配帧与上传图片通过SURF算法和相应的对极几何算法来完成基于视觉的室内定位。本发明适用于室内视觉定位场合。

说明书

技术领域

本发明涉及室内定位导航领域。 

背景技术

随着智能手机的普及，位置定位服务越来越受到人们的重视。而现如今的卫星定位只解决了室外定位的问题，室内定位仍未得到统一。近年来基于Wifi的室内定位方法由于其部署方便，得到了比较广泛的关注，但是目前的研究成果显示，其定位精度受室人流疏密、墙壁遮挡等因素的影响较大。综合设备的部署成本和定位精度的影响因素考虑，并结合发展较为成熟的图像处理技术，视觉定位技术逐渐成为室内定位研究的另一个热点，并获得了越来越多的关注。关于视觉定位方法的研究始于机器人定位领域，但是近年来随着具有摄像头的智能手机的发展，视觉室内定位方法由于其所需设备简单，除用户配备摄像头的智能手机外，无需添加其他硬件设备而得到广泛的关注。 

基于视觉的室内定位通过将用户所在位置的图像信息来估计出移动设备的位置，从而进行定位。通常该定位系统分为两步：即建立基于视频采集的Visual Map数据库的离线阶段和在线的定位估计阶段。如表1所示： 

表1 

视频帧>位置坐标>哈希值>F₁(X_1,Y₁)>H₁…>…>…>F_n(X_n,Y_n)>H_n

Visual Map数据库是由视频帧，该帧所对应的地理位置信息和该帧的哈希值(该哈希值由感知哈希算法计算而来)组成，其中n表示帧的个数。传统的用于视觉定位的数据库为图片库，获取方法为先在室内环境下按照一定间隔均匀设置参考点，使其覆盖需定位区域。然后在每个参考点分别朝向不同方向进行照相以获得基于图片的数据库。但这种对图像进行采集和位置标注的方式十分费时费力。 

发明内容

本发明内容是为了解决现有方法的室内视觉定位精度低，且费时费力的问题，从而提供一种基于视频采集的Visual Map数据库建立方法及利用该数据库的室内视觉定位方法。 

基于视频采集的Visual Map数据库建立方法，它由以下步骤实现： 

步骤一、根据需要定位的室内环境，选择坐标原点P0(X₀,Y₀)，建立平面二维直角坐标系； 

步骤二、通过载有视频获取设备的平台在匀速直线过程中进行视频拍摄，并且通过对所获得的视频进行处理来记录视频中帧的位置坐标信息，该位置坐标通过拍摄平台的运动速度和该帧的序号以及该视频的帧速率，通过公式： 

$>\left(\begin{array}{c}{X}_n=X_0+v\frac{n}{m}\cos \alpha \\ Y_n=Y_0+v\frac{n}{m}\sin \alpha \end{array}\right)---\left(1\right)$>

获得；其中，n为该帧的序号，v为拍摄平台运动速度，α为拍摄平台运动方向和坐标系x轴夹角，(X₀,Y₀)为坐标原点，(X_n,Y_n)为该帧在步骤一中所建立的平面坐标系中的位置坐标； 

步骤三、通过感知哈希算法计算出已经标记位置坐标信息的帧的哈希值，并存储，完成Visual Map数据库的建立。 

基于上述Visual Map数据库的室内视觉定位方法，它由以下步骤实现： 

步骤A、通过感知哈希算法计算出待定位用户上传的图像的哈希值； 

步骤B、根据步骤A获得的哈希值从Visual Map数据库中搜索到4帧图像，完成粗匹配过程； 

步骤C、将步骤B中得到的4帧粗匹配图像与用户上传图像通过SURF算法进行匹配点计算； 

步骤D、通过RANSAC算法从步骤C中每对图像得到的匹配点中选择8对匹配点，并记录其相对应图像中的坐标； 

步骤E、将步骤C中得到的像素坐标通过对极几何来计算出用户的位置坐标，完成室内视觉定位。 

步骤E中所述将步骤C中得到的像素坐标通过对极几何来计算出用户的位置坐标的具体方法为： 

步骤E1、采用8点法求基本矩阵F，所述基本矩阵F是对极几何的数学描述； 

对极几何中基本矩阵F的基本关系式为： 

x′^TFx＝0          (2) 

其中，X，X′分别表示两幅匹配图像中的一对匹配点在其像素坐标系中的坐标； 

将获得的8对匹配点X_i(u_i,v_i,1)，X′_i(u′_i,v′_i,1)，(1≤i≤8)代入公式(2)中，令基本矩阵F＝(f_ij)，即： 

$>\left(\begin{array}{ccccccccc}{u}_1^{\prime }{u}_1& u_1^{\prime }{v}_1& u_1^{\prime }& v_1^{\prime }{u}_1& v_1^{\prime }{v}_1& v_1^{\prime }& u_1& v_1& 1\\ .& .& .& .& .& .& .& .& .\\ .& .& .& .& .& .& .& .& .\\ .& .& .& .& .& .& .& .& .\\ u_8^{\prime }{u}_8& u_8^{\prime }{v}_8& u_8^{\prime }& v_8^{\prime }{u}_8& v_8^{\prime }{v}_8& v_8^{\prime }& u_8& v_8& 1\end{array}\right)f=0---\left(3\right)$>

其中，f＝(f₁₁,f₁₂,f₁₃,f₂₁,f₂₂,f₂₃,f₃₁,f₃₂,f₃₃)^T； 

求解该线性方程组，获得基本矩阵F； 

步骤E2、调用建立Visual Map数据库所用相机的内部参数矩阵K₁，并读取待定位用户的相机内部参数矩阵K₂；相机内部参数矩阵K由公式(4)给出： 

$>K=\left(\begin{array}{ccc}{k}_{u}f& k_u\cot \theta & u_0\\ 0& k_{v}f/\sin \theta & v_0\\ 0& 0& 1\end{array}\right)---\left(4\right)$>

其中，f为相机焦距，k_u，k_v表示相机的像素点尺寸，u₀，v₀表示图像的尺寸即图像坐标系中u轴和v轴所包含像素点的个数，θ表示图像坐标系中u轴和v轴之间的夹角，并由公式(5)求得本质矩阵E： 

Ε＝K₂^TFK₁           (5) 

步骤E3、由于步骤E2计算出的本质矩阵E包含了用户拍照位置与数据库中匹配图像所处位置之间的旋转矩阵R和转移向量t，如公式(6)所示： 

E＝[t]_×R              (6) 

其中，[]_×表示反对称矩阵，如公式(7)所示， 

$>{\left(\begin{array}{c}{x}_1\\ x_2\\ x_3\end{array}\right)}_{\times }=\left(\begin{array}{ccc}0& -x_3& x_2\\ x_3& 0& -x_1\\ -x_2& x_1& 0\end{array}\right)---\left(7\right)$>

从而通过本质矩阵E求出旋转矩阵R和转移向量t； 

步骤E4、在步骤E3中求出的转移向量t是以用户拍照位置为参考系得出的，将其转换至世界坐标系中，如公式(8)所示， 

t_w＝-R_r^-1R^-1t            (8) 

其中：t_w表示在规定的世界坐标系中用户拍照位置与匹配图像位置之间的方向向量，R_r^-1表示匹配图像在被采集时相机的旋转矩阵； 

步骤E5、已知世界坐标系中两幅图像的方向向量及其中一个匹配图像的二维位置坐标(X_d,Y_d)，确定一条过匹配图像的直线，如公式(9)所示， 

$>y=\frac{t_w\left(2\right)}{t_w\left(1\right)}·(x-X_d)+Y_d---\left(9\right)$>

其中：t_w是步骤四得出的转移向量，是一个3×1的列向量，t_w(2)代表t_w第二行的元素，同理t_w(1)代表t_w第一行的元素； 

步骤E6、将粗匹配得到的4帧图像分别和用户上传图像按照上述步骤求出4条直线，该4条直线存在若干交点，采用公式(10)完成最优点的确定，即：定位结果的确定： 

$>\underset{x,y}{\min }\underset{i}{\Sigma }{N}_i{d}_i(x,y)---\left(10\right)$>

其中：N_i表示第i个匹配图像与用户提供图像的匹配点数，d_i(x,y)表示选定的交点到第i个匹配图像所做直线的距离，如公式(11)表示， 

$>d_i(x,y)=\frac{|a_{i}x+b_{i}y+c_i|}{\sqrt{{a_i}^2+{b_i}^2}}---\left(11\right)$>

其中：a_i＝t(2)，b_i＝-t(1)，c_i＝-t(2)x_i+t(1)y_i，x_i和y_i表示第i幅匹配图像对应的坐标。 

步骤E3中从本质矩阵E恢复旋转矩阵R和转移矩阵t的算法，其特征在于以下步骤： 

步骤E31、将3×3阶的本质矩阵E分解为E＝[e_a e_b e_c]的形式，其中e_a,e_b,e_c为 3×1阶列向量；对e_a,e_b,e_c三个列向量两两求外积得e_a×e_b,e_a×e_c和e_b×e_c，并选出其中幅值最大的一组，且设e_a×e_b结果的幅值最大； 

步骤E32、根据公式(12)和公式(13)，分别计算出矩阵V＝[v_a v_b v_c]以及矩阵U＝[u_a u_b u_c]： 

$>\left(\begin{array}{c}{v}_c=(e_a\times e_b)/|e_a\times e_b|\\ v_a=e_a/\left|e_a\right|\\ v_b=v_c\times v_a\end{array}\right)---\left(12\right)$>

$>\left(\begin{array}{c}{u}_a=E{v}_a/\left|E{v}_a\right|\\ u_b=E{v}_b/\left|E{v}_b\right|\\ u_c=u_a\times u_b\end{array}\right)---\left(13\right)$>

步骤E33、构造矩阵D形式如下： 

$>D=\left(\begin{array}{ccc}0& 1& 0\\ -1& 0& 0\\ 0& 0& 1\end{array}\right)---\left(14\right)$>

矩阵V和矩阵U，得出转移向量t如公式(15)所示： 

t＝[u₁₃ u₂₃ u₃₃]         (1) 

其中：u₁₃表示矩阵U第1行第3列的元素，u₂₃表示矩阵U第2行第3列的元素，u₃₃表示矩阵U第3行第3列的元素；旋转矩阵R如公式(16)所示： 

$>\left(\begin{array}{c}{R}_a=\mathrm{UD}{V}^T\\ R_b=U{D}^T{V}^T\end{array}\right)---\left(16\right)$>

可知，旋转矩阵R有两个取值R_a或R_b； 

步骤E34、构造矩阵H_a＝[R_a|t]，H_b＝[R_a|-t]，H_c＝[R_b|t]，H_d＝[R_a|-t]；其中：H_a＝[R_a|t]表示3×3阶的旋转矩阵R和3×1阶的转移向量t合并成为4×4阶的向量H_a，如公式(17)所示： 

$>H_a=\left(\begin{array}{cc}{R}_a& t\\ 0_{1\times 3}& 1\end{array}\right)---\left(17\right)$>

H_b，H_c，H_d的构造方式同理； 

步骤E35、令向量P＝[1 1 1 1]^T，并计算L₁＝H_aP，L₂＝H_bP，L₃＝H_cP，L₄＝H_dP，当L_i(i＝1,2,3,4)满足条件(18)时，取L_i对应的R和t作为最终的旋转矩阵R和转移向量t； 

$>\left(\begin{array}{c}{L}_i\left(3\right)>0\\ L_i\left(4\right)>0\end{array}\right)---\left(18\right)$>

其中，L_i是4×1阶的列向量，L_i(3)和L_i(4)分别表示向量L_i的第3行第1列元素和第4行第1列元素。 

本发明减少了Visual Map数据库建立的工作量，并利用对极几何的相关算法提高现有基于图像匹配的方法的精度，进而提高了室内视觉定位精度。 

附图说明

图1是RANSAC算法流程示意图； 

图2是在室内地图上选择坐标原点并建立坐标系的示意图； 

图3是计算帧的位置坐标示意图； 

图4是像素坐标系示意图； 

图5是基于视频采集的Visual Map数据库的室内视觉定位方法流程示意图。 

具体实施方式

具体实施方式一、基于视频采集的Visual Map数据库建立方法，它包括下述步骤： 

步骤一、根据需要定位的室内环境，选择坐标原点P0(X₀,Y₀)，建立平面二维直角坐标系，如图2所示； 

步骤二、通过载有视频获取设备(手机)的平台在匀速直线过程中进行视频拍摄，并且通过对所获得的视频进行处理来记录视频中帧的位置坐标信息，该位置坐标可以通过拍摄平台的运动速度和该帧的序号以及该视频的帧速率计算得到，如公式(1)所示： 

$>\left(\begin{array}{c}{X}_n=X_0+v\frac{n}{m}\cos \alpha \\ Y_n=Y_0+v\frac{n}{m}\sin \alpha \end{array}\right)---\left(1\right)$>

其中，n为该帧的序号，v为拍摄平台运动速度，α为拍摄平台运动方向和坐标系x轴夹角，(X₀,Y₀)为坐标原点，(X_n,Y_n)为该帧在步骤一中所建立的平面坐标系中的位置坐标，如图3所示； 

步骤三、通过感知哈希算法计算出已经标记位置坐标信息的帧的哈希值，完成数据库的建立，本发明将该数据库称之为Visual Map。 

具体实施方式二、基于具体实施方式一的视频采集的Visual Map数据库的室内视觉定位方法，它包括下述步骤： 

步骤一、通过感知哈希算法计算出待定位用户上传的图像的哈希值； 

步骤二、根据步骤一通过感知哈希算法计算所得的哈希值从Visual Map数据库中搜索到4帧图像，完成粗匹配过程； 

步骤三、将步骤二中得到的4帧粗匹配图像与用户上传图像通过SURF算法进行匹配点计算； 

步骤四、通过RANSAC算法从步骤三中每对图像得到的匹配点中选择8对匹配点，并记录其在相对应图像中的坐标； 

步骤五、根据步骤四中得到的像素坐标通过对极几何来计算出用户的位置坐标，完成室内定位。 

步骤E中所述将步骤C中得到的像素坐标通过对极几何来计算出用户的位置坐标的具体方法为：它包括下述步骤： 

步骤一：采用8点法求基本矩阵F。基本矩阵F是对极几何的数学描述。对极几何中基本矩阵F的基本关系式为： 

x′^TFx＝0           (2) 

其中，X，X′分别表示两幅匹配图像中的一对匹配点在其像素坐标系中的坐标。将实施方式一中步骤四得到的8对匹配点X_i(u_i,v_i,1)，X′_i(u′_i,v′_i,1)，(1≤i≤8)代入公式(2)中，令基本矩阵F＝(f_ij)，如公式(3)所示： 

$>\left(\begin{array}{ccccccccc}{u}_1^{\prime }{u}_1& u_1^{\prime }{v}_1& u_1^{\prime }& v_1^{\prime }{u}_1& v_1^{\prime }{v}_1& v_1^{\prime }& u_1& v_1& 1\\ .& .& .& .& .& .& .& .& .\\ .& .& .& .& .& .& .& .& .\\ .& .& .& .& .& .& .& .& .\\ u_8^{\prime }{u}_8& u_8^{\prime }{v}_8& u_8^{\prime }& v_8^{\prime }{u}_8& v_8^{\prime }{v}_8& v_8^{\prime }& u_8& v_8& 1\end{array}\right)f=0---\left(3\right)$>

其中，f＝(f₁₁,f₁₂,f₁₃,f₂₁,f₂₂,f₂₃,f₃₁,f₃₂,f₃₃)^T。直接通过求解该线性方程组来计算基本矩阵F。 

步骤二：调用建立Visual Map数据库所用相机的内部参数矩阵K₁，并读取待定位用户的相机内部参数矩阵K₂。相机内部参数矩阵K由公式(4)给出： 

$>K=\left(\begin{array}{ccc}{k}_{u}f& k_u\cot \theta & u_0\\ 0& k_{v}f/\sin \theta & v_0\\ 0& 0& 1\end{array}\right)---\left(4\right)$>

其中，f为相机焦距，k_u，k_v表示相机的像素点尺寸，u₀，v₀表示图像的尺寸即图像坐标系中u轴和v轴所包含像素点的个数，θ表示图像坐标系中u轴和v轴之间的夹角，如图4所示。在此基础上，由公式(5)求得本质矩阵E 

Ε＝K₂^TFK₁           (5) 

步骤三、由于步骤二计算出的本质矩阵E包含了用户拍照位置与数据库中匹配图像所处位置之间的旋转矩阵R和转移向量t，如公式(6)所示， 

E＝[t]_×R            (2) 

其中，[]_×表示反对称矩阵，如公式(7)所示， 

$>{\left(\begin{array}{c}{x}_1\\ x_2\\ x_3\end{array}\right)}_{\times }=\left(\begin{array}{ccc}0& -x_3& x_2\\ x_3& 0& -x_1\\ -x_2& x_1& 0\end{array}\right)---\left(7\right)$>

从而可以通过本质矩阵E求出R和t； 

在步骤三中求出的转移向量t是以用户拍照位置为参考系得出的，此步将其转换至世界坐标系中，如公式(8)所示， 

t_w＝-R_r^-1R^-1t           (8) 

其中：t_w表示在规定的世界坐标系中用户拍照位置与匹配图像位置之间的方向向量，R_r^-1表示匹配图像在被采集时相机的旋转矩阵。 

步骤五、已知世界坐标系中两幅图像的方向向量及其中一个图像(这里指匹配图像)的二维位置坐标(X_d,Y_d)，可确定一条过匹配图像的直线，如公式(9)所示， 

$>y=\frac{t_w\left(2\right)}{t_w\left(1\right)}·(x-X_d)+Y_d---\left(9\right)$>

其中，t_w是步骤四得出的转移向量，是一个3×1的列向量，t_w(2)代表t_w第二行的元素，同理t_w(1)代表t_w第一行的元素； 

步骤六、将粗匹配得到的4帧图像分别和用户上传图像按照上述步骤求出4条直线，该4条直线存在若干交点，采用公式(10)完成最优点即定位结果的确定， 

$>\underset{x,y}{\min }\underset{i}{\Sigma }{N}_i{d}_i(x,y)---\left(10\right)$>

其中，N_i表示第i个匹配图像与用户提供图像的匹配点数，d_i(x,y)表示选定的交点到第i个匹配图像所做直线的距离，如公式(11)表示： 

$>d_i(x,y)=\frac{|a_{i}x+b_{i}y+c_i|}{\sqrt{{a_i}^2+{b_i}^2}}---\left(11\right)$>

其中，a_i＝t(2)，b_i＝-t(1)，c_i＝-t(2)x_i+t(1)y_i，x_i和y_i表示第i幅匹配图像对应的坐标。 

从本质矩阵E恢复旋转矩阵R和转移矩阵t的方法，它包括以下步骤： 

步骤一、将3×3阶的本质矩阵E分解为E＝[e_a e_b e_c]的形式，其中e_a,e_b,e_c为3×1阶列向量；对e_a,e_b,e_c三个列向量两两求外积得e_a×e_b,e_a×e_c和e_b×e_c，并选出其中幅值最大的一组，为便于一下步骤的执行，这里假设e_a×e_b结果的幅值最大； 

步骤二、根据公式(12)和公式(13)，分别计算出矩阵V＝[v_a v_b v_c]以及矩阵U＝[u_a u_b u_c]； 

$>\left(\begin{array}{c}{v}_c=(e_a\times e_b)/|e_a\times e_b|\\ v_a=e_a/\left|e_a\right|\\ v_b=v_c\times v_a\end{array}\right)---\left(12\right)$>

$>\left(\begin{array}{c}{u}_a=E{v}_a/\left|E{v}_a\right|\\ u_b=E{v}_b/\left|E{v}_b\right|\\ u_c=u_a\times u_b\end{array}\right)---\left(13\right)$>

步骤三、构造矩阵D形式如下： 

$>D=\left(\begin{array}{ccc}0& 1& 0\\ -1& 0& 0\\ 0& 0& 1\end{array}\right)---\left(14\right)$>

矩阵V和矩阵U，得出转移向量t如公式(15)所示， 

t＝[u₁₃ u₂₃ u₃₃]            (15) 

其中u₁₃表示矩阵U第1行第3列的元素，u₂₃表示矩阵U第2行第3列的元素，u₃₃表示矩阵U第3行第3列的元素。旋转矩阵R如公式(16)所示， 

$>\left(\begin{array}{c}{R}_a=\mathrm{UD}{V}^T\\ R_b=U{D}^T{V}^T\end{array}\right)---\left(16\right)$>

可以看出旋转矩阵R有两个取值R_a或R_b； 

步骤四、构造矩阵H_a＝[R_a|t]，H_b＝[R_a|-t]，H_c＝[R_b|t]，H_d＝[R_a|-t]。其中H_a＝[R_a|t]表示3×3阶的旋转矩阵R和3×1阶的转移向量t合并成为4×4阶的向量H_a，如公式(17)所示， 

$>H_a=\left(\begin{array}{cc}{R}_a& t\\ 0_{1\times 3}& 1\end{array}\right)---\left(17\right)$>

H_b，H_c，H_d的构造方式同理。 

步骤五、令向量P＝[1 1 1 1]^T，并计算L₁＝H_aP，L₂＝H_bP，L₃＝H_cP，L₄＝H_dP，当L_i(i＝1,2,3,4)满足条件(18)时，取L_i对应的R和t作为最终的旋转矩阵R和转移向量t。 

$>\left(\begin{array}{c}{L}_i\left(3\right)>0\\ L_i\left(4\right)>0\end{array}\right)---\left(18\right)$>

其中，L_i是4×1阶的列向量，L_i(3)和L_i(4)分别表示向量L_i的第3行第1列元 素和第4行第1列元素。 

本发明在快速建立基于视频的Visual Map数据库的基础上，提出了相应的室内视觉定位方法。该方法主要是通过载有视频获取设备(手机)的平台在匀速直线过程中进行视频拍摄，并且通过对所获得的视频进行处理来记录视频中帧的坐标位置信息以及图像匹配信息。在线的定位阶段，系统将带定位用户上传的图片与基于视频的Visual Map数据库通过利用感知哈希算法计算而来的哈希值进行粗匹配，再通过获得的粗匹配帧与上传图片通过SURF算法和相应的对极几何算法来完成基于视觉的室内定位。 

在实际应用中，将粗匹配帧和用户上传图像通过SURF算法进行匹配点计算时，会存在一些误匹配点。误匹配点的存在会导致室内定位的精度下降，因此，应用时需要利用RANSAC(RANdom SAmple Consensus)算法来剔除误匹配点，算法流程如图2所示，其中单应矩阵用来描述两个平面之间的二维投影变换关系，用两个像平面上的4对对应点即可求得单应矩阵，t和n₀为设定的阈值，至少有n₀个匹配点的实际位置坐标和由单应矩阵反算而来的位置坐标的欧氏距离小于t时，认为该单应矩阵是满足该对匹配图像的变换关系的，通过此种方法可以剔除掉不满足上述单应矩阵的误匹配点。 

在实际环境中，载有视频获取设备(手机)的平台以一定速度在需要建立数据库的区域运动，设备终端通过摄像头来采集环境下的视频信息。根据运动开始的起点和终点，以及所获得的视频时间长度并结合室内定位系统的精度要求对相应的帧进行标记，标记其位置信息。然后通过感知哈希算法计算该帧的哈希值，并与该帧的位置坐标相对应，完成数据库的快速建立。