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

摘要

基于图像采集的Visual Map数据库建立方法及利用该数据库的室内定位方法，涉及室内定位导航领域。本发明是为了解决无线电信号在室内由于受到门的开启及闭合、人的走动、墙壁阻挡的多重因素影响，导致WLAN定位精度低的问题。本发明首先通过建立离线Visual Map，并提取用户智能手机所拍相片的特征点与Visual Map中各位置指纹上图像的特征点进行匹配，随后采用对极几何精确的估计出用户位置。本发明适用于室内定位场合。

说明书

技术领域

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

背景技术

随着智能手机的普及，位置定位服务越来越受到人们的重视。而现如今的卫星定位系统只是解决了室外定位的问题，在室内环境中，卫星信号会受到严重的衰减导致定位精度的严重损失。近年来基于WLAN的室内定位方法由于其部署方便，得到了比较广泛的研究，但是目前的研究成果显示，其定位精度受室人流疏密、墙壁遮挡等因素的影响较大。基于视觉的定位方法的研究始于机器人定位领域，但是近年来随着具有摄像头的智能手机的发展及手机计算能力的提升，基于视觉的室内定位方法由于其所需设备简单，除用户配备摄像头的智能手机外无需添加其他硬件设备，且受影响因素相对较少等特点而得到广泛的关注。

发明内容

本发明是为了解决无线电信号在室内由于受到门的开启及闭合、人的走动、墙壁阻挡的多重因素影响，导致WLAN定位精度低的问题，从而提供一种基于图像采集的Visual Map数据库建立方法及利用该数据库的室内定位方法。

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

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

步骤二、从坐标原点开始，沿x轴每隔1米、沿y轴每隔0.5m建立一个参考点，每个参考点分别按照0°，90°，180°，270°的角度，或按照45°，135°，225°，315°的角度均匀间隔采集4幅图像，并计算出该参考点采集图像时相机的旋转矩阵R_r；

步骤三、采用128点SURF算法对每个参考点在4个角度采集到的图像进行特征点提取，并与步骤一所得坐标系中参考点的坐标和步骤二获得的旋转矩阵R_r相对应并存储，完成离线阶段Visual Map数据库的建立。

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

步骤A、在线阶段，将需要定位服务用户提供的图像采用128点SURF算法进行特征点信息的提取；

步骤B、对图像的特征点采用KNN算法，在Visual Map数据库中检索出与所提供特征点最匹配的k幅图像的特征点，并记录k个特征点相应的位置坐标P(X,Y)和旋转矩阵R_r；

步骤C、采用RANSAC算法，剔除匹配图像与用户所提供图像间的误匹配点；

步骤D、筛选出每对匹配图像中的8对匹配点，使用对极几何进行精确定位，完成室内定位。

步骤C中，采用RANSAC算法，剔除匹配图像与用户所提供图像间的误匹配点的方法包括以下步骤：

步骤C1、从匹配点中选择4对匹配点，并计算单应矩阵H；

步骤C2、根据步骤C1计算获得的单应矩阵H计算其余匹配点在对应图像中的理论坐标；

步骤C3、令i的值加1，计算第i个匹配点理论坐标与实际坐标的欧氏距离；i的处始值为0；

步骤C4、判断步骤C3获得的欧氏距离是否小于预设的欧氏距离阈值t，如果判断结果为是，则步骤C5；如果判断结果为否，则返回执行步骤C3；

步骤C5、令n的值加1，并判断n的值是否大于预设迭代次数n₀；如果判断结果为是，则结束；如果判断结果为否，则返回执行步骤C1；

n表示迭代次数，初始值为0。

步骤D中采用对极几何进行精确定位的方法包括以下步骤：

步骤D1、采用8点法求基本矩阵F，基本矩阵F是两幅图像约束关系的数学描述，对极几何中基本矩阵F的基本关系式为：

X'^TFX＝0              (1)

其中，X和X'分别表示两幅匹配图像中的一对匹配点在其像素坐标系中的坐标；筛选出步骤C所述每对匹配图像中的8对匹配点X_i(u_i,v_i,1)，X_i'(u_i',v_i',1)，i＝1,2,…,8代入公式(2)中，令基本矩阵F＝{f_ij}(i＝1,2,3；j＝1,2,3₎，如公式(2)所示：

$>\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^{\prime }& 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^{\prime }& v_8^{\prime }& u_8& v_8& 1\end{array}\right)f=0---\left(2\right)$>

通过求解该线性方程组来计算基本矩阵F；

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

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

$>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(3\right)$>

其中，f为相机焦距，k_u和k_v表示相机的像素点尺寸，u₀和v₀分别表示图像的尺寸即图像坐标系中u轴和v轴所包含像素点的个数，θ表示图像坐标系中u轴和v轴之间的夹角；

根据公式(4)求得本质矩阵E：

Ε＝K₂^TFK₁                 (1)

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

E＝[t]_×R                (5)

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

$>{\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(6\right)$>

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

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

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

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

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

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

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

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

$>\underset{x,y}{\min }\left\{N_j{d}_{\mathrm{ij}}(x_i,y_i)\right\}---\left(9\right)$>

其中，d_ij(x_i,y_i)表示第i(i＝1,2,...,6)个交点到第j(j＝1,2,3,4)个直线的距离_，N_j表示第j个直线所对应的图像与用户提供图像的匹配点数，d_ij(x_i,y_i)表达式如公式(10)表示：

$>d_{\mathrm{ij}}(x_i,y_i)=\frac{|a_i{x}_i+b_i{y}_i+c_i|}{\sqrt{{a_i}^2+{b_i}^2}}---\left(10\right)$>

其中_，a_i＝t(2)_，b_i＝-t(1)_，c_i＝-t(2)x_i+t(1)y_i，x_i和y_i表示第i个交点的位置坐标。

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

步骤D31、将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结果的幅值最大；

步骤D32、根据公式(11)和公式(12)，分别计算出矩阵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(11\right)$>

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

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

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

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

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

其中，u₁₃表示矩阵U第1行第3列的元素，u₂₃表示矩阵U第2行第3列的元素，u₃₃表示矩阵U第3行第3列的元素；

旋转矩阵R如公式(15)所示：

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

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

步骤D34、构造矩阵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，如公式(16)所示：

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

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

步骤D35、令向量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)满足条件(17)时，取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(17\right)$>

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

本发明使用图像采集的Visual Map建立方式记录每个参考点的位置、相机的旋转矩阵和SURF算法得出的特征点信息，对需要定位的用户手机所拍摄的相片提取特征点，将其与数据库中各图像的特征点进行匹配，选出匹配度最高的若干幅图像及与其相对应的图像的位置信息和旋转矩阵，之后使用RANSAC算法剔除匹配图像中的误匹配点，最后使用对极几何完成对用户位置的估计。本发明WLAN定位精度高。

附图说明

图1是本发明的基于图像采集的Visual Map建立及室内定位方法过程示意图。

图2是对参考点位置指纹信息和相应的图像信息采集的示意图。

图3是RANSAC算法的流程示意图。

具体实施方式

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

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

步骤二：从坐标原点开始，沿x轴每隔1米，沿y轴每隔0.5m建立一个参考点，每个参考点采集4幅图像，分别按照0°，90°，180°，270°或45°，135°，225°，315°的角度均匀间隔进行图像采集，如图3所示。并计算出该参考点采集图像时相机的旋转矩阵R_r；

步骤三：采用128点SURF算法对每个参考点4个角度采集到的图像进行特征点提取，并与步骤一所得坐标系中参考点的坐标和步骤二获得的旋转矩阵相对应，最终完成离线阶段Visual Map的建立。

具体实施方式二、利用具体实施方式一所述的Visual Map数据库的室内定位方法，它由以下步骤实现：

步骤A、在线阶段，将需要定位服务用户提供的图像在手机端采用128点SURF算法进行特征点信息的提取，并将特征点传送至服务器；

步骤B、对图像的特征点采用KNN算法，在服务器中检索出与所提供特征点最匹配的k幅图像的特征点，并记录k个特征点相应的位置坐标P(X,Y)和旋转矩阵R_r；

步骤C、采用RANSAC算法，剔除匹配图像与用户所提供图像间的误匹配点，提高定位精度，该算法流程图如图4所示。其中t表示预先设定的欧氏距离的阈值，n表示迭代次数，初始值为0，n₀表示预先设定的迭代次数；

步骤D、筛选出每对匹配图像中的8对匹配点，使用对极几何进行精确定位，并将位置信息从服务器传送至用户手机端，完成定位。

基于对极几何的精细室内定位方法。它包括下述步骤：

步骤D1、采用8点法求基本矩阵F。基本矩阵F是两幅图像约束关系的数学描述。对极几何中基本矩阵F的基本关系式为：

X'^TFX＝0                (1)

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

$>\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^{\prime }& 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^{\prime }& v_8^{\prime }& u_8& v_8& 1\end{array}\right)f=0---\left(2\right)$>

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

直接通过求解该线性方程组来计算基本矩阵F。

步骤D2、计算建立Visual Map数据库所用相机的内部参数矩阵K₁，并计算待定位用户的相机内部参数矩阵K₂。相机内部参数矩阵K由公式(3)给出：

$>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(3\right)$>

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

Ε＝K₂^TFK₁                 (4)

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

E＝[t]_×R                  (5)

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

$>{\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(6\right)$>

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

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

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

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

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

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

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

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

$>\underset{x,y}{\min }\left\{N_j{d}_{\mathrm{ij}}(x_i,y_i)\right\}---\left(9\right)$>

其中d_ij(x_i,y_i)表示第i(i＝1,2,...,6)个交点到第j(j＝1,2,3,4)个直线的距离，N_j表示第j个直线所对应的图像与用户提供图像的匹配点数，d_ij(x_i,y_i)表达式如公式(10)表示：

$>d_{\mathrm{ij}}(x_i,y_i)=\frac{|a_i{x}_i+b_i{y}_i+c_i|}{\sqrt{{a_i}^2+{b_i}^2}}---\left(10\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的算法，它包括以下步骤：

步骤D31、将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结果的幅值最大。

步骤D32、根据公式(11)和公式(12)，分别计算出矩阵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(11\right)$>

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

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

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

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

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

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

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

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

步骤D34：构造矩阵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，如公式(16)所示，

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

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

步骤D35：令向量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)满足条件(17)时，取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(17\right)$>

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

本发明首先通过建立离线Visual Map，并提取用户智能手机所拍相片的特征点与Visual Map中各位置指纹上图像的特征点进行匹配，随后采用对极几何估计出用户的位置。视觉定位系统分为两步即建立Visual Map的离线阶段和在线的位置估计阶段。

在离线阶段建立的Visual Map如表1所示。

表1

RP₁(X₁,Y₁)R_r1f₁₁f₁₂……f_1mRP₂(X₂,Y₂)R_r2f₂₁f₂₂……f_2m……………………………………RP_n(X_n,Y_n)R_rnf_n1f_n2……f_nm

其中，R_ri(i＝1,2,…,n)表示采集第i副图片时相机的旋转矩阵，f_ij(i＝1,2,…,n,j＝1,2,…,m)表示对第i副图片采用SURF算法得到的第j个特征向量。

Visual Map是由参考点(Reference Point，简称RP)组成，参考点包含三部分信息，分别是参考点的物理位置、在该位置上以不同角度拍摄的若干张相片的旋转矩阵及每张照片中代表每个特征点信息的特征向量，其中，n表示参考点个数与每个参考点不同拍摄角度数量的乘积，m表示每幅图像使用SURF算法提取的特征点个数。这里采用SURF算法进行特征点的提取，是因为该算法对旋转、尺度缩放、亮度变化保持不变形，对视角变化、仿射变换、噪声也保持一定程度的稳定性。

在线阶段采用的定位方式是用SURF算法提取用户智能手机所拍摄相片的特征点，并将其与数据库中各图像的特征点进行匹配，选出匹配度最高的若干幅图像及与其相对应的图像的位置信息和旋转矩阵，之后使用RANSAC(Random，Sample Consensus)算法剔除匹配图像中的误匹配点，最后使用对极几何完成对用户位置的估计。