视频帧中基于三点共线标记点的三维定位方法

摘要

本发明请求保护一种视频帧中基于三点共线标记点的三维定位方法，涉及计算机视觉与图像处理技术。本发明针对现有基于平面标志物的跟踪定位算法局限于平面物体，需要较大的可视平面的缺陷，提供一种基于三点共线标记的三维定位方法，获取视频帧中定位标记点的二维坐标信息，建立定位标记坐标系中标记点的坐标与图像坐标系中标记点坐标的对应关系，得到定位标记物在摄像机坐标系下的三维位置信息和三维姿态信息。用于对视频图像中具有三点共线标记的目标三维定位，为三维空间的指点式交互操作提供一种快速、准确的跟踪方法。

说明书

技术领域

本发明涉及计算机视觉与图像处理技术，具体是一种对视频帧中特定目标的跟踪定位技术。

背景技术

增强现实(Augmented Reality)是利用虚拟信息对真实场景进行信息增强的技术。增强现实将用户实际身处的物理环境作为用户的主要感知和交互环境，同时又根据该环境实时生成包括文本、二维图像、三维物体的虚拟信息，通过配准技术将生成的虚拟信息叠加在含有真实场景视频的输出设备上，达到对用户所在的真实场景的解释说明、信息增强或三维展示等目的。

文献《Marker Tracking and HMD Calibration for a video-based AugmentedReality Conferencing System》(H.Kato，M.Billinghurst，in Proceedings of the2^nd International Workshop on Augmented Reality，San Francisco，USA，October，1999)中提出了一种基于正方形标志物的用于增强现实的配准算法，并由此开发出一套开源的增强现实软件开发包——ARToolkit。ARToolkit使用计算机视觉技术得到摄像机在标志物坐标系下的位置和姿态信息，实现了对平面物体的跟踪配准，使开发人员能够以该标志物所在平面为基准设定坐标系，进行后续的可视化信息的叠加。其中用于跟踪配准算法的流程为：对视频帧进行二值化处理，寻找具有四个顶点的大面积区域轮廓，提取顶点的图像坐标并与顶点在世界坐标系下的坐标进行对应，得到单应性矩阵(homography)，该矩阵反应了真实标志物到图像上的透视变换；结合模板匹配技术，可以得到正确的顶点对应关系，从而实现跟踪配准。

由于ARToolkit的跟踪配准算法采用寻找平面标志物轮廓的4个顶点进行对应，局限于平面物体或具有平坦表面物体的跟踪配准，在实际应用过程中需要较大的可视标志物平面，不适合不具备平坦表面的目标跟踪，特别是对于三维空间(或三维虚实融合空间)中类似鼠标、笔等指点式的交互设备的跟踪是不合适的。

发明内容

本发明所要解决的技术问题是针对现有跟踪配准算法局限于平面物体，需要较大可视平面的缺陷，提供一种高效的基于三点共线标记的三维定位方法，用于对视频图像中具有三点共线标记点的目标三维定位，为三维空间的线型目标定位及指点式交互操作提供一种快速、准确的跟踪方法。

本发明的技术方案为解决上述技术问题提供一种高效的基于三点共线标记的三维定位方法，该方法包括步骤：

A：设置三点共线排列的定位标记点作为定位标记物，使之位于视频帧的可视范围内。可选择三个等间距共线排列的，色彩与背景存在反差的标记点作为定位标记物。

B：获取视频帧中定位标记点的二维位置信息。对获取的视频帧进行颜色提取和二值化处理，建立二值化处理后的视频帧图片的累加直方图；根据累加直方图获取定位标记点在图像坐标系中的坐标；如果是合法的定位标记点，记录其在图像坐标系中的二维坐标；确定累加直方图的方法可为，首先根据视频帧图片的二值化图像沿X轴的直方图，获得定位标记点的X坐标，然后在二值化图像上分别取各个定位标记点的X坐标领域内的子图像，确定沿Y轴的直方图，获得各个定位标记点的Y坐标。

C：对图像坐标系中定位标记点的二维坐标进行处理，得到定位标记物的三维位置信息和三维姿态信息。定位标记物的三维位置信息包括定位标记坐标系原点在摄像机坐标系下的三维坐标，三维姿态信息包括定位标记点所共线与摄像机坐标系的三轴的夹角关系，其中定位标记坐标系为极坐标系。

建立定位标记坐标系下定位标记点的坐标与图像坐标系下定位标记点的坐标的对应关系，根据对应关系建立方程组，解方程组得到定位标记物的三维位置信息和三维姿态信息。将定位标记坐标系下定位标记点的坐标按离坐标原点的距离值从小到大排列，图像坐标系下定位标记点的坐标按X坐标值从小到大排列，形成定位标记点在两坐标系下的点与点的对应关系，建立方程组。可使用奇异值分解求最优解，得到摄像机的外部参数，即标记点的三维位置与姿态信息。定位标记物的三维位置信息包括定位标记坐标系原点在摄像机坐标系下的三维坐标，三维姿态信息包括定位标记点所共直线与摄像机坐标系的三轴的夹角关系。

由于本发明实现线型物体的在三维空间的定位定姿，具有以下有益效果：本方案使用三点共线标记跟踪定位技术，与ARToolkit的平面标志物的跟踪定位技术相比，更适合于对线型物体(如棍、棒、笔等)的跟踪定位，特别是在三维空间指点式人机交互领域应用有较大优势。首先，使用三个共线标记点，不要求的交互设备具备较大的可视平面，只要求可视三点，因此使用本跟踪方案的交互设备比使用基于平面标志物的交互设备在外形设计上相对灵活；其次，三点共线标记特别适合于线型物体的跟踪，这类线型物体用于指点式交互设备是一种自然隐喻，可对应于现实中的笔式交互设备等，给用户的体验是自然合理的。

附图说明

图1定位标记点的排布示意图

图2定位标记点所确定的线段在定位标记坐标系中的位置关系示意图

图3基于三点共线标记的三维定位方法流程图

具体实施方式

以下针对附图和具体实例对本发明的实施进行具体说明。

附图1是设置三点共线等距排列的定位标记点示意图。标记点设置应满足以下要求：

确保应用过程中摄像机对定位标记点的可见性，即定位标记点在具体应用环境中不会被遮挡；定位标记点的间距视具体应用环境而定，根据实际场景中跟踪目标大小与摄像机的视野确定定位标记点间距，定位标记点的间距与目标大小和摄像机的视野为正比关系，一般目标越大、视野越宽，标记点的间距就越大。通常，对于手持式笔形物体的跟踪，在距离摄像机约50厘米范围内的定位标志点的间距，取7到8厘米比较合适，从而保证笔的长度不超过18厘米；标记点能够较容易地从图像中被提取出来，可采用与背景颜色差异较大的LED亮点作为标记点，也可采用与背景有较大颜色差异的圆形标贴。为方便起见，标记颜色一般选红、绿、蓝三元色中的一种。实例中采用绿色LED亮点。例如简单地，可将3个LED以7厘米的距离等间距地安装在一根平直的塑料棒上，如附图1所示。

附图2是定位标记点对应线段在定位标记坐标系中的位置关系示意图。

本实施方案涉及到以下三个坐标系：

(1)以图像的左上角为原点，水平轴为X轴，垂直轴为Y轴，单位为像素建立图像坐标系，为二维直角坐标系。

(2)以镜头光心为原点，X轴和Y轴分别与图像坐标系的X轴和Y轴平行，Z轴与图像平面垂直，单位为毫米，建立摄像机坐标系，为三维直角坐标系。

(3)建立定位标记坐标系，结合附图2，设定位标记点所在线段LO的一个端点O为定位标记坐标系的原点，当把定位标记坐标系看成极坐标系时，极轴与摄像机坐标系的X轴平行，LO上的任意一点坐标为其中l为线段LO上任意一点到原点O的距离，为线段LO与Z轴的夹角，θ为线段LO到OXY平面的投影与X轴的夹角；当把定位标记坐标系对应为直角坐标系时，X、Y、Z轴分别与摄像机坐标系的X、Y、Z轴平行，LO上的任意一点坐标为[X^w，Y^w，Z^w]。

任一点从极坐标系到直角坐标系的变换式为：

其中X^w、Y^w、Z^w、l的单位均为毫米，和θ的单位为弧度。

由摄像机坐标系的点[X^c，Y^c，Z^c]映射到图像坐标系的点[x，y]的变换关系式如下：

$s\left(\begin{array}{c}x\\ y\\ 1\end{array}\right)=\left(\begin{array}{ccc}{a}_x& 0& u_0\\ 0& a_y& v_0\\ 0& 0& 1\end{array}\right)\left(\begin{array}{c}{X}^c\\ Y^c\\ Z^c\end{array}\right)---\left(2\right)$

其中s是比例因子，u₀、v₀分别为摄像机光轴与图像平面的交点在图像坐标系中的水平和垂直坐标，a_x＝f/dx，a_y＝f/dy，而f为摄像机的焦距，dx、dy分别为每个像素在水平与垂直方向上的物理尺寸，单位为毫米。

摄像机内部参数矩阵为：

$\left(\begin{array}{ccc}{a}_x& 0& u_0\\ 0& a_y& v_0\\ 0& 0& 1\end{array}\right)=M_{\mathrm{int}}---\left(3\right)$

由定位标志坐标系的点[X^w，Y^w，Z^w]映射到摄像机坐标系点[X^c，Y^c，Z^c]的变换关系式如下：

$\left(\begin{array}{c}{X}^c\\ Y^c\\ Z^c\end{array}\right)=\left(\begin{array}{cccc}1& 0& 0& T_x\\ 0& 1& 0& T_y\\ 0& 0& 1& T_z\end{array}\right)\left(\begin{array}{c}{X}^w\\ Y^w\\ Z^w\\ 1\end{array}\right)---\left(4\right)$

其中[T_x，T_y，T_z]为定位标志坐标系的原点在摄像机坐标系中的坐标。

结合式(1)，则定位标志坐标系中点的极坐标映射到摄像机坐标系点[X^c，Y^c，Z^c]的变换关系如下：

其中，

为摄像机外部参数矩阵，根据每帧图像计算得到这五个参数。

由式(2)和式(5)可得，定位标志坐标系的点映射到图像坐标系点[x，y]的变换关系式为：

将内部参数矩阵(式(3))与外部参数矩阵(式(6))相乘：

M_intM_ext＝C_3×2                    (8)

即

其中矩阵

$C_{3\times 2}=\left(\begin{array}{cc}{c}_{11}& c_{12}\\ c_{21}& c_{22}\\ c_{31}& c_{32}\end{array}\right)---\left(10\right)$

为点从定位标志坐标系到图像坐标系的变换矩阵，其中，Cij为变换参数。

于是式(7)可表示为：

$s\left(\begin{array}{c}x\\ y\\ 1\end{array}\right)=\left(\begin{array}{cc}{c}_{11}& c_{12}\\ c_{21}& c_{22}\\ c_{31}& c_{32}\end{array}\right)\left(\begin{array}{c}l\\ 1\end{array}\right)---\left(11\right)$

展开，并消去s得到：

$\left(\begin{array}{c}x=\frac{c_{11}l+c_{12}}{c_{31}l+c_{32}}\\ y=\frac{c_{21}l+c_{22}}{c_{31}l+c_{32}}\end{array}\right)---\left(12\right)$

将式(12)调整得到线性方程组：

$\left(\begin{array}{cccccc}l& 1& 0& 0& -\mathrm{lx}& -x\\ 0& 0& l& 1& -\mathrm{ly}& -y\end{array}\right)c_{6\times 1}=0---\left(13\right)$

其中，c_6×1＝(c₁₁ c₁₂ c₂₁ c₂₂ c₃₁ c₃₂)^T为变换参数向量        (14)

附图3所示是基于三点共线标记的三维定位方法流程图，其步骤如下：

301设置定位标记物参数和摄像机内部参数。

定位标记物参数为定位标记点的相对位置信息。为了确定定位标记点在定位标记坐标系中的位置，优选地，设定具有端点位置的定位标记点为定位标记坐标系原点，测量确定其他定位标记点到原点的距离。

本实例中，定位标记点的间距为7厘米，则定位标记物参数为[0，70，140]。

摄像机内部参数在一定的使用时间内是固定不变的，所以，可事先通过外部独立标定过程获得这些参数，并以内部参数矩阵形式(如式(3)所示)保存于文件中，每次应用时直接调用即可。

302获取视频帧。本实施方案中使用VC调用DirectShow视频库(DSVL)可以直接获得视频帧数据。具体实现步骤为：

(1)在程序初始化时调用，建立视频获取对象的实例并初始化，

DSVideo*dsv＝new DSVideo()；

dsv-＞init()；

(2)在程序的循环中调用以不断获取视频帧，采集视频帧并获得图像数据结构，

IplImage*image＝dsv-＞GetNextFrame()；

303：对获取的视频帧进行图像处理，获取视频帧中定位标记点的二维位置信息，在本实例中，包括提取具有特定颜色的LED亮点，对其进行二值化处理获取二值化图像，从二值化图像中得到LED亮点的图像位置。

B1：提取具有特定颜色的LED亮点的二值化处理。从原始彩色图像中获得具有特定颜色特征像素的灰度图像，确定对应位置的像素值，将灰度图像转为二值图像。以本方案中的绿色LED作为定位标记点为例，优选地，可采用如下步骤：

B11：从原始彩色图像中获得具有绿色颜色特征像素的灰度图像。由原始的RGB三通道图像，算法模块使用颜色空间转换式，对每个像素点进行操作：

tempPix＝SrcPix_Green-SrcPix_Red×0.3-SrcPix_Blue×0.3；    (15)

$\mathrm{GrayPix}=\left(\begin{array}{c}\mathrm{tempPix},\mathrm{tempPix}>0\\ 0,\mathrm{else};\end{array}\right)---\left(16\right)$

其中SrcPix_Red，SrcPix_Green，SrcPix_Blue分别为原始彩色图像的每个像素点的RGB分量，GrayPix则为所求灰度图像的对应位置的像素值。

B12：采用阈值分割的方法将灰度图像转为二值图像。给定阈值T，则二值图像像素值BinaryPix的计算式为

$\mathrm{BinaryPix}=\left(\begin{array}{c}255,\mathrm{GrayPix}>T\\ 0,\mathrm{else};\end{array}\right)---\left(17\right)$

此时得到的图像为提取了特定颜色的二值化图像，其中像素值为255区域对应到定位标记点的图像区域。同样，可以分别使用以下变换式替换式(15)得到特定颜色为红色和蓝色的定位标记点的二值化图像。

tempPix＝SrcPix_Red-SrcPix_Green×0.3-SrcPix_Blue×0.3；    (18)

tempPix＝SrcPix_Blue-SrcPix_Red×0.3-SrcPix_Green×0.3；    (19)

B2：从二值化图像中求得LED亮点在图像中的坐标。确定二值化图像沿X轴的直方图，获得定位标记点的X坐标，在二值化图像上分别取各个定位标记点的X坐标领域内的子图像，确定沿Y轴的直方图，获得各个定位标记点的Y坐标。

B21：获得沿X轴的累加直方图。建立一个长度为二值化图像宽度的一维数组，将二值化图像的每一列像素值求和并将结果保存到一维数组的对应位置，得到累加直方图。

B22：搜索累加直方图(一维数组)的局部最大值，其对应位置即为LED亮点在图像中的水平坐标x。一般情况下，对应到3个LED亮点，累加直方图会有3个局部最大值，按x坐标的顺序，由小到大排列，记录为x₁，x₂，x₃。

B23：以x_i(i＝1，2，3)为中心，δ为领域，取原始图像中起点坐标为[x_i-δ，0]，宽高为[2δ，IMAGE_WIDTH]的子图像区域，计算该子图像沿Y轴的累加直方图，即建立一个长度为二值化图像高度的一维数组，将子图像的每一行像素值求和并将结果保存到一维数组对应位置，得到沿Y轴的累加直方图；搜索累加直方图局部最大值，其对应位置即为x_i对应的亮点在图像中的垂直坐标y_i。于是从二值化图像中找到了代表LED亮点的亮度区域的图像坐标[x_i，y_i]。

304：记录合法的定位标记点。由于可能受到外界其他因素的影响，比如额外的光照、反射光等，根据步骤303提取到的亮度区域的图像坐标[x_i，y_i]不一定全部是LED亮点的图像坐标。故引入如下判断：根据近似共线的特征确定定位标记点。

理论上，所有定位标记点在图像上共线。考虑到设备采集精度以及噪声干扰，合法的定位标记点具有近似共线的特征。具体表达为：对于一组待定的定位标记点，如果任意一点到某确定点(通常取一端点)的斜率相近，则认为它们为合法的定位标记点。如本次检测不是合法标记点，则进行下一帧检测。

305：将定位标志点在定位标记坐标系中三维坐标与在图像坐标系中的坐标形成对应，建立方程组，具体为：

C11：标记点在定位标记坐标系中的顺序按离坐标原点的距离值从小到大排列，如由步骤301初始化时确定的定位标记物参数[0，70，140]，则三个定位标记点在定位标记坐标系中的坐标为其中l₁＝0，l₂＝70，l₃＝140，i＝1，2，3。由于定位标记点是共线的，则其参数相同，为待求参数，l₁，l₂，l₃为个定位标记点距离原点的位置；

定位标记点在图像坐标系中的坐标[x_i，y_i]，i＝1，2，3，按x坐标值从小到大排列。于是得到定位标记点在定位标记坐标系与图像坐标系的对应点关系，

{l_i，[x_i，y_i]}，i＝1，2，3                    (20)

C12：将上述的对应点对代入式(13)，建立方程组：

$\left(\begin{array}{cccccc}{l}_1& 1& 0& 0& -l_1{x}_1& -x_1\\ 0& 0& l_1& 1& -l_1{y}_1& -y_1\\ l_2& 1& 0& 0& -l_2{x}_2& {-x}_2\\ 0& 0& l_2& 1& -l_2{y}_2& -y_2\\ l_3& 1& 0& 0& -l_3{x}_3& -x_3\\ 0& 0& l_3& 1& -l_3{y}_3& -y_3\end{array}\right)\left(\begin{array}{c}{c}_{11}\\ c_{12}\\ c_{21}\\ c_{22}\\ c_{31}\\ c_{32}\end{array}\right)=0---\left(21\right)$

306：解方程组(21)，得到定位标记物的三维位置坐标信息和三维姿态信息。

由于式(21)左边的6×6矩阵是不满秩的，所以有非零解。可以将式(21)化为超定方程组，然后对矩阵使用奇异值分解(SVD)，来解该方程组。由于在解方程组的过程中不需要求逆，所以计算速度很快，可以满足实时性要求。具体如下：对式(21)进行变形，两边同时除以c32得，

$\left(\begin{array}{cccccc}{l}_1& 1& 0& 0& -l_1{x}_1& -x_1\\ 0& 0& l_1& 1& -l_1{y}_1& -y_1\\ l_2& 1& 0& 0& -l_2{x}_2& {-x}_2\\ 0& 0& l_2& 1& -l_2{y}_2& -y_2\\ l_3& 1& 0& 0& -l_3{x}_3& -x_3\\ 0& 0& l_3& 1& -l_3{y}_3& -y_3\end{array}\right)\left(\begin{array}{c}{b}_{11}\\ b_{12}\\ b_{21}\\ b_{22}\\ b_{31}\\ b_{32}\end{array}\right)=0---\left(22\right)$

其中

b_ij＝c_ij/c₃₂(i＝1，2，3    j＝1，2)                    (22)

即b₃₂＝1

继续变形，写成超定方程组：

$\left(\begin{array}{ccccc}{l}_1& 1& 0& 0& -l_1{x}_1\\ 0& 0& l_2& 1& -l_1{y}_1\\ l_2& 1& 0& 0& -l_2{x}_2\\ 0& 0& l_2& 1& -l_2{y}_2\\ l_3& 1& 0& 0& -l_3{x}_3\\ 0& 0& l_3& 1& -l_3{y}_3\end{array}\right)\left(\begin{array}{c}{b}_{11}\\ b_{12}\\ b_{21}\\ b_{22}\\ b_{31}\end{array}\right)=\left(\begin{array}{c}{x}_1\\ y_1\\ x_2\\ y_2\\ x_3\\ y_3\end{array}\right)---\left(23\right)$

令

$A_{6\times 5}=\left(\begin{array}{ccccc}{l}_1& 1& 0& 0& -l_1{x}_1\\ 0& 0& l_2& 1& -l_1{y}_1\\ l_2& 1& 0& 0& -l_2{x}_2\\ 0& 0& l_2& 1& -l_2{y}_2\\ l_3& 1& 0& 0& -l_3{x}_3\\ 0& 0& l_3& 1& -l_3{y}_3\end{array}\right)---\left(24\right)$

B_5×1＝[b₁₁ b₁₂ b₂₁ b₂₂ b₃₁]^T      (25)

D_6×1＝[x₁ y₁ x₂ y₂ x₃ y₃]^T        (26)

将式(23)简化为：

A_6×5B_5×1＝D_6×1                  (27)

对矩阵A_6×5进行奇异值分解得：

$A_{6\times 5}=U_{6\times 6}{W}_{6\times 5}{V}_{5\times 2}^T---\left(28\right)$

矩阵求逆得：

$A_{6\times 5}^{-1}=V_{5\times 5}{W}_{5\times 6}^{-1}{U}_{6\times 6}^T---\left(29\right)$

则由式(27)和式(29)可得：

$B_{5\times 1}=A_{6\times 5}^{-1}{D}_{6\times 1}=V_{5\times 5}{W}_{5\times 6}^{-1}{U}_{6\times 6}^T{D}_{6\times 1}---\left(30\right)$

从而解出方程(23)。由式(8)得：

$M_{\mathrm{ext}}=M_{\mathrm{int}}^{-1}{C}_{3\times 2}---\left(31\right)$

令

$M_{\mathrm{int}}^{-1}=\left(\begin{array}{ccc}{m}_{11}& m_{12}& m_{13}\\ m_{21}& m_{22}& m_{23}\\ m_{31}& m_{32}& m_{33}\end{array}\right)---\left(32\right)$

由于，$C_{3\times 2}=\left(\begin{array}{cc}{b}_{11}& b_{12}\\ b_{21}& b_{22}\\ b_{31}& b_{32}\end{array}\right)c_{32}---\left(33\right)$

展开式(31)可得：

根据三角关系约束得到：

$c_{32}=1/{[{\left(\underset{i=1}{\overset{3}{\Sigma }}{m}_{1i}{b}_{i1}\right)}^2+{\left(\underset{i=1}{\overset{3}{\Sigma }}{m}_{2i}{b}_{i1}\right)}^2+{\left(\underset{i=1}{\overset{3}{\Sigma }}{m}_{3i}{b}_{i1}\right)}^2]}^{1/2}---\left(35\right)$

最后由式(34)求出即得到了摄像机的外部参数，即定位标记点的三维位置与姿态信息。