CN103765477A - 通过图形匹配和环形检测而用自动模型初始化进行线跟踪 - Google Patents

Abstract

移动平台中的基于视觉的跟踪系统使用经检测线群组来跟踪对象。所述跟踪系统检测所述待跟踪对象的所俘获图像中的线。线群组由所述经检测线形成。可通过计算所述经检测线的交叉点并使用交叉点来识别连接线而形成所述线群组，其中所述线群组是使用连接线而形成。可建构所述经检测线的图形并对其进行交叉点识别。使用连接产生所关注子图，并用所述所关注子图形成所述线群组。一旦形成所述线群组，就使用所述线群组来例如通过比较所述对象的当前图像中的所述线群组与所述对象的先前图像中的线群组而跟踪所述对象。

Description

通过图形匹配和环形检测而用自动模型初始化进行线跟踪

对相关申请案的交叉参考

本申请案主张2012年3月9日申请的标题为“通过图形匹配和环形检测而用自动模型初始化进行线跟踪(Line Tracking With Automatic Model Initialization by GraphMatching and Cycle Detection)”的第13/416,721号美国专利申请案的优先权，所述申请案又依据35USC 119主张2011年9月2日申请的标题为“通过图形匹配和环形检测而用自动模型初始化进行线跟踪(Line Tracking With Automatic Model Initialization byGraph Matching and Cycle Detection)”的第61/530,907号美国临时专利申请案的优先权，所述两申请案转让给本受让人，且以引用的方式并入本文中。

技术领域

本文中所描述的标的物的实施例大体上涉及定位和跟踪，且更特定来说，涉及基于视觉的跟踪。

背景技术

基于视觉的跟踪系统用于估计相机相对于参考图像的定位和定向(姿态)。参考图像通常基于由相机或其它相机所俘获的真实世界环境的部分的多个图像(有时被称作帧)。在确定相机的姿态的情况下，可执行例如(但不限于)扩增实境的应用。对于例如扩增实境的应用来说，准确且稳健的跟踪是特别重要的，这是因为其能实现虚拟扩增与真实世界环境之间的紧密配准。

一种类型的基于视觉的跟踪基于检测和跟踪图像中的线。举例来说，在正跟踪的对象具有非常小的纹理的状况下，线跟踪算法是很有用的。然而，常规的线跟踪缺乏许多扩增实境应用所要的稳健性。因此，需要改善线跟踪。

发明内容

移动平台中的基于视觉的跟踪系统使用经检测线群组来跟踪对象。所述跟踪系统检测待跟踪的所述对象的所俘获图像中的线。线群组由所述经检测线形成。可通过计算所述经检测线的交叉点，并使用交叉点来识别连接线而形成所述线群组，其中所述线群组是使用连接线而形成。可建构所述经检测线的图形并对其进行交叉点识别。使用连接产生所关注子图，并用所述所关注子图形成所述线群组。一旦形成所述线群组，就使用所述线群组来例如通过比较所述对象的当前图像中的所述线群组与所述对象的先前图像中的线群组而跟踪所述对象。

在实施例中，一种方法包含俘获待跟踪对象的图像；检测所述对象的所述图像中的多个线；从所述多个线形成线群组；以及使用所述线群组来跟踪所述对象。

在实施例中，一种设备包含：相机；以及连接到所述相机的处理器，所述处理器经配置以：检测由所述相机所俘获的待跟踪对象的图像中的多个线，从所述多个线形成线群组，以及使用所述线群组来跟踪所述对象。

在实施例中，一种设备包含：用于俘获待跟踪对象的图像的装置；用于检测所述对象的所述图像中的多个线的装置；用于从所述多个线形成线群组的装置；以及用于使用所述线群组来跟踪所述对象的装置。

在实施例中，一种其上包含所存储的程序代码的非暂时性计算机可读媒体包含：用以俘获待跟踪对象的图像的程序代码；用以检测所述对象的所述图像中的多个线的程序代码；用以从所述多个线形成线群组的程序代码；以及用以使用所述线群组来跟踪所述对象的程序代码。

附图说明

图1A和1B分别说明能够以如本文中所描述的稳健方式执行基于视觉的线跟踪的移动平台的前侧和后侧。

图2说明基于视觉的跟踪单元的两个主要组件。

图3说明基于视觉的跟踪单元中的线检测组件。

图4说明边缘连接算法。

图5说明线拟合中所使用的线近似。

图6说明基于视觉的跟踪单元中的线跟踪。

图7A、7B和7C说明包含经处理以用于线拟合的若干边缘的图像。

图8是说明使用线群组而跟踪对象的方法的流程。

图9说明三个点之间的线。

图10说明顶点A、B、C和D之间的线。

图11说明环形检测和分裂。

图12A和12B分别说明展示边缘的原始图形和展示所提取环形的图形。

图13说明类似于图10的顶点A、B、C和D之间的线，但其标记有边缘e₁到e₄。

图14说明作为基于矩阵表示的环形检测的实例的四个顶点之间的五条线。

图15说明分裂图14中所说明的图形。

图16是能够使用线群组跟踪对象的移动平台的框图。

具体实施方式

图1A和1B分别说明能够以如本文中所描述的稳健方式执行基于视觉的线跟踪的移动平台100的前侧和后侧。移动平台100说明为包含外壳101、可为触摸屏显示器的显示器102以及扬声器104和麦克风106。移动平台100进一步包括用以为基于视觉的跟踪单元112而对环境进行成像的相机110。基于视觉的跟踪单元112跟踪线群组。大多数常规的线跟踪系统的缺点中的一种为单独地跟踪线，这限制了过程的稳健性。跟踪线群组改善了跟踪过程的稳健性。另外，基于视觉的跟踪单元112可使用自动模型初始化以获得待跟踪的线群组。自动模型初始化可为例如图形匹配和环形检测。基于视觉的跟踪单元112可与无参考的跟踪和基于参考的跟踪一起使用。

如本文中所使用，移动平台指代任何便携式电子装置，例如蜂窝式或其它无线通信装置、个人通信系统(PCS)装置、个人导航装置(PND)、个人信息管理器(PIM)、个人数字助理(PDA)或其它合适的移动装置。移动平台可能够接收无线通信和/或导航信号，例如导航定位信号。术语“移动平台”还既定包含(例如)通过短程无线、红外线、有线连接或其它连接而与个人导航装置(PND)通信的装置，而不管装置处或PND处是否发生卫星信号接收、辅助数据接收和/或定位相关处理。并且，“移动平台”既定包含所有电子装置，其包含能够进行基于视觉的跟踪的无线通信装置、计算机、膝上型计算机、平板计算机等。

如图2所说明，基于视觉的跟踪单元112包含两个主要组件：线检测200和跟踪220。如图2和图3中所说明，线检测200包含初始化202、边缘检测204、边缘连接206和线段拟合208。如图2和图6中所说明，跟踪220包含执行局部搜索、计算边缘集合的分布和帧到帧跟踪，如图2中所说明。线检测200中的初始化202包含提供待跟踪对象的输入图像。可由所属领域中熟知的例如坎尼(Canny)边缘检测器、索贝尔(Sobel)边缘检测器、维特(Prewitt)边缘检测器或其它适当的边缘检测器执行边缘检测204。接着，执行经由非最大压制的边缘薄化，从而以边缘图的形式产生边缘点的集合。接着，可执行边缘连接206，从而导致边缘分段。作为实例，图4说明可使用的边缘连接算法。边缘连接算法检查边缘图中的每一边缘点，并通过检查局部邻域中的边缘图和识别此区中的其它边缘点而用边缘分段ID来标记点。作为实例，局部邻域可为围绕边缘点的8×8像素区。接着执行线段拟合208，以由多个线段表示边缘。作为实例，图5说明点A到点B之间的曲线α上的线拟合。对于点A和点B之间的曲线α上的每一点C来说，算法首先识别线AB上的点D，使得线CD垂直于线AB，换句话说，<AB，CD>＝0。记下距离CD，且识别导致最大距离CD的点C，由图5中的点C*表示。如果最大距离(即点C*和对应点D*之间的最大距离)小于合适的预选阈值T，那么认为线AB为曲线α的良好近似。另一方面，如果最大距离大于阈值T，那么对于个别线AC*和C*B中的每一者重复所述算法。

图6说明基于视觉的跟踪单元中的线跟踪220。对于先前帧上的线检测200阶段中所识别的每一线段，在当前帧中识别局部搜索区(222)。图7A说明包含围绕边缘区L具有局部搜索区250的若干边缘的图像，所述搜索区可为8×8像素区。然后，对于局部搜索区中的每一像素，基于当前图像计算梯度的量值和定向(224)。在一实施例中，坎尼(Canny)算子可用于计算图像梯度。或者，索贝尔(Sobel)核心或维特(Prewitt)核心，或等效的梯度计算核心可用于计算图像梯度。另外，可对梯度图执行非最大压制。计算梯度定向和梯度量值的分布，并将其用于识别搜索区中具有类似于线段L的分布的边缘点的子集(224)。可利用线性回归技术来计算边缘点的所选子集的主要方向，以选择最接近的边缘候选者(226)，如图7B中所说明。在一实施例中，可利用主成分分析(PCA)来识别边缘点的所选子集的主要方向。将线段拟合于当前帧中的边缘点的子集上(228)，并进一步优化线段的参数以最小化拟合误差(230)，如图7C中所说明。

为提高线跟踪系统的稳健性，将线群组合成群组以形成可接着进行跟踪的较好描述。图8为说明使用线群组而跟踪对象的方法的流程。如图8中所说明，俘获待跟踪对象的图像(302)，例如如由移动平台100所俘获的视频或图像的多个帧中的一者。例如如上文图3中所描述或以任何其它所要方式检测对象图像中的多个线(304)。由多个线形成线群组(306)，并例如如上文图6中所描述或以任何其它所要方式使用线群组以从一帧到下一帧跟踪对象(308)。线群组可为例如闭合图形中的连接线，例如正方形、矩形或环形。

可通过计算多个线的所有交叉点，并使用交叉点来识别连接线而形成线群组(306)。举例来说，可通过从多个线建构图形；计算多个线的所有交叉点；以及使用每一对交叉点之间的连接产生所关注的子图而形成线群组。一旦识别交叉点，可如下建构所述线的集合的图形G：

G(A，B)＝1，如果

    方程式1

其中T为合适的所选阈值。作为实例，图9说明点A、B和C，以及线(A，B)和(A，C)。可如下写出此图形的矩阵G：

$G=\begin{array}{c}\begin{array}{ccc}A& B& C\end{array}\\ \left[\begin{array}{ccc}0& 1& 1\\ 1& 0& 0\\ 1& 0& 0\end{array}\right]\begin{array}{c}A\\ B\\ C\end{array}\end{array}$     方程式2

作为实例，图10说明具有由如下描述的顶点A、B、C和的另一可能子图：

$T=\begin{array}{c}\begin{array}{cccc}A& B& C& D\end{array}\\ \left[\begin{array}{cccc}0& 1& 0& 1\\ 1& 0& 1& 0\\ 0& 1& 0& 1\\ 1& 0& 1& 0\end{array}\right]\begin{array}{c}A\\ B\\ C\\ D\end{array}\end{array}$     方程式3

接着，可使用所关注的线群组形成所关注的子图。从跟踪视角来说的所关注子图可为三角形、正方形、矩形、任意多边形或环形。

一旦线群组已形成为例如所关注的子图，就可使用匹配技术从帧到帧跟踪线群组(308)。可在具有参考或无参考的情况下执行匹配。

如果待跟踪对象的先前知识可用，那么可利用此信息且可通过匹配当前输入帧与所关注的已知对象而执行准确的子图和对象跟踪。作为实例，就2D跟踪来说，可有助于对象跟踪的先前知识的类型可为待跟踪对象的参考图像；就3D跟踪来说，可为对象的参考3D模型；来自3D对象的不同视图的一系列帧；或甚至为2D模型或3D模型的边缘图。

在无先前知识的情况下，通过比较后续帧，即通过比较当前帧与先前帧(其可为紧接着的之前帧或先于当前帧多个帧的帧)来执行跟踪。在无先前知识的情况下，可执行环形检测，其中如下文所论述，认为图形中的闭合路径为所关注区域的边界。

在匹配阶段中，给出当前图像中的经检测线的集合，计算所有交叉点。通过考虑每一对交叉点之间的连接而建置图形。接着，进行模型初始化以检测所关注子图，并使用准确的子图图形匹配来比较经检测子图与模型帧的子图(在基于参考的跟踪的状况下)和先前帧的子图(在无参考的跟踪的状况下)。

另外，可将线群组组合在一起以检测环形。环形检测包含将图形和每一所得子图重复地分裂成两个，直到每一所得子图含有一个环形为止。将含有一个环形的所得子图报告为所关注子图。图11中说明环形检测，其展示含有4个环形的图形分裂成两个，由此产生含有1个环形和3个环形的子图。具有3个环形的子图再次分裂以产生额外的子图，其进一步分裂直到每一子图仅具有1个环形为止。接着，将含有1个环形的所有子图返回为结果。此过程的两个主要分量为以下所说明的环形检测和图形分裂。作为实例，图12A和12B分别说明用虚线和点划线识别的展示边缘的原始图形，和展示所提取环形的图形。

可以各种方式执行环形检测。为有助于论述，令H₀表示顶点的空间。举例来说，参看图10中所说明的子图，H₀为顶点集合{A，B，C，D}的幂集，使得

$A=\left[\begin{array}{c}1\\ 0\\ 0\\ 0\end{array}\right]\begin{array}{c}A\\ B\\ C\\ D\end{array}$ $A\&CirclePlus;B=\left[\begin{array}{c}1\\ 1\\ 0\\ 0\end{array}\right]$ $A\&CirclePlus;A=\left[\begin{array}{c}0\\ 0\\ 0\\ 0\end{array}\right]$ $A*a=\left[\begin{array}{c}a\\ 0\\ 0\\ 0\end{array}\right]$     方程式4

另外，令H₁表示类似于图10但标记有边缘e₁到e₄的如图13中所展示的边缘集合{e₁，e₂，e₃，e₄}的幂集，使得：

$e_1=\left[\begin{array}{c}1\\ 0\\ 0\\ 0\end{array}\right]\begin{array}{c}{e}_1\\ e_2\\ e_3\\ e_4\end{array}$ $e_1\&CirclePlus;e_2=\left[\begin{array}{c}1\\ 1\\ 0\\ 0\end{array}\right]$ $e_1\&CirclePlus;e_2=\left[\begin{array}{c}0\\ 0\\ 0\\ 0\end{array}\right]$ $e_1*a=\left[\begin{array}{c}a\\ 0\\ 0\\ 0\end{array}\right].$     方程式5

还可使用如下定义的边界算子

执行环形检测：

$\begin{array}{c}\&PartialD;:H_1\&RightArrow;H_0\\ \&PartialD;\left(e_1\right)=A+D\\ \&PartialD;(e_1+e_2)=\&PartialD;\left(e_1\right)+\&PartialD;\left(e_2\right)=A+D+D+C=A+C\end{array}$     方程式6

因此，根据边界算子，可如下定义环形c∈H₁：

方程式7

应注意，环形C的空间为向量空间，且为

的零空间，且环形的数目等于等于零的

的特征值的数目。

作为实例，对于图13中所展示的图形，可以数学方式将边界算子

表示为：

其中如下给出矩阵D：

$D=\begin{array}{c}\begin{array}{cccc}{e}_1& e_2& e_3& e_4\end{array}\\ \left[\begin{array}{cccc}-1& 0& 0& -1\\ 0& 0& -1& 1\\ 0& -1& 1& 0\\ 1& 1& 0& 0\end{array}\right]\begin{array}{c}\hat{A}\\ \hat{B}\\ \hat{C}\\ \hat{D}\end{array}\end{array}$     方程式8

举例来说，

$\&PartialD;\left(e_1\right)={\mathrm{De}}_1=\left[\begin{array}{c}-1\\ 0\\ 0\\ 1\end{array}\right]=-\hat{A}+\hat{D}.$     方程式9

基于此描述，由于根据模2加法，因此边缘e₁、e₂、e₃和e₄形成环形：

$\&PartialD;(e_1+e_2+e_3+e_4)=\left[\begin{array}{c}0\\ 0\\ 0\\ 0\end{array}\right]=0_{\&prime;\&prime;}^{\&prime;\&prime;}.$     方程式10

作为实例，图14说明四个顶点之间的五条线。可通过查看等于零的拉普拉斯矩阵的特征值的数目而发现环形的数目。在此实例中，由如下给出拉普拉斯矩阵L＝D^TD：

    方程式11

如方程式11中所说明，对于图14中所展示的环形图形，存在两个零特征值，且因此，存在两个环形。因此，应分裂图14中所说明的图形，如图15中所说明，其中分裂发生于边界点处。哈里什.契塔昆塔(Harish Chintakunta)、哈米德.克里姆(Hamid Krim)的“定位传感器网络中的覆盖盲区(Localizing Coverage holes in Sensor Networks)”(IEEESECON，2010年6月，其以引用的方式并入本文中)中的分治算法描述用于图形分裂的合适实施方案。在执行图形分裂之后，发现每一子图中的闭合路径，并将其视为所关注区域的边界。接着，此等所得环形可用于跟踪过程。

图16为能够使用线群组跟踪对象的移动平台100的框图。移动平台100包含相机110，以及用户接口150，其包含能够显示由相机110所俘获的图像的显示器102。用户接口150还可包含用户可经由其将信息输入到移动平台100中的小键盘152或其它输入装置。视需要，可通过将虚拟小键盘集成到具有触摸传感器的显示器102中而排除小键盘152。举例来说，如果移动平台为蜂窝式电话，那么用户接口150还可包含麦克风106和扬声器104。麦克风106可用于输入音频注释。当然，移动平台100可包含与本发明不相关的其它元件。

移动平台100还包含连接到相机110并与其通信的控制单元160，和用户接口150以及可存在的其它系统。举例来说，可存在例如加速度计、陀螺仪、磁力计等运动和/或定位传感器，且其可用于提供用于跟踪的额外信息。如上文所论述，控制单元160从相机110接受数据并处理所述数据。可通过总线160b、处理器161和相关联的存储器164、硬件162、软件165和固件163而提供控制单元160。移动平台100包含线检测单元172、线分组单元174和跟踪单元176，所述单元组成图1中所展示且如上文所描述而操作的基于视觉的跟踪单元112。为了清楚起见，单独地说明线检测单元172、线分组单元174和跟踪单元176，并将其与处理器161分离，但其可为单个单元和/或基于执行于处理器161中的软件165中的指令而实施于处理器161中。如本文中所使用，将理解处理器161以及线检测单元172、线分组单元174和跟踪单元176中的一者或一者以上可(但未必需要)包含一个或一个以上微处理器、内嵌处理器、控制器、专用集成电路(ASIC)、数字信号处理器(DSP)及类似者。术语处理器既定描述由系统而非具体硬件所实施的功能。此外，如本文中所使用，术语“存储器”指代任何类型的计算机存储媒体，其包含与移动平台相关联的长期、短期或其它存储器，且并不限于任何特定类型的存储器或特定数目的存储器，或特定类型的其上存储有存储器的媒体。

取决于应用，可通过各种装置实施本文中所描述的方法。举例来说，可以硬件162、固件163、软件165或其任何组合实施这些方法。对于硬件实施方案，处理单元可实施于一个或一个以上专用集成电路(ASIC)、数字信号处理器(DSP)、数字信号处理装置(DSPD)、可编程逻辑装置(PLD)、现场可编程门阵列(FPGA)、处理器、控制器、微控制器、微处理器、电子装置、经设计以执行本文中所描述的功能的其它电子单元，或其组合内。

对于固件和/或软件实施方案，可用执行本文中所描述的功能的模块(例如，程序、功能等等)实施方法。在实施本文中所描述的方法时，可使用任何有形地体现指令的机器可读媒体。举例来说，可将软件代码存储于存储器164中，并由处理器161执行。可在处理器161内或外部实施存储器。

如果以固件和/或软件实施，那么可将功能作为一个或一个以上指令或代码存储在计算机可读媒体上。实例包含编码有数据结构的非暂时性计算机可读媒体，和编码有计算机程序的计算机可读媒体。计算机可读媒体包含物理计算机存储媒体。存储媒体可为可由计算机存取的任何可用媒体。作为实例而非限制，此计算机可读媒体可包括RAM、ROM、快闪存储器、EEPROM、CD-ROM或其它光盘存储装置、磁盘存储装置或其它磁性存储装置，或可用于存储呈指令或数据结构形式的所要程序代码且可由计算机存取的任何其它媒体；如本文中所使用的磁盘和光盘包含压缩光盘(CD)、激光光盘、光学光盘、数字多功能光盘(DVD)、软盘和蓝光光盘，其中磁盘通常以磁性方式再现数据，而光盘用激光以光学方式再现数据。以上各者的组合也应包含在计算机可读媒体的范围内。

尽管出于指导性目的，结合具体实施例来说明本发明，但本发明并不限于此等具体实施例。在不脱离本发明的范围的情况下可作出各种调适和修改。因此，所附权利要求书的精神和范围不应限于前述描述。

Claims (28)

1.一种方法，其包括：

俘获待跟踪对象的图像；

检测所述对象的所述图像中的多个线；

从所述多个线形成线群组；以及

使用所述线群组来跟踪所述对象。

2.根据权利要求1所述的方法，其中所述线群组包括连接线。

3.根据权利要求2所述的方法，其中所述连接线形成闭合图形。

4.根据权利要求1所述的方法，其中从所述多个线形成所述线群组包括：

计算所述多个线的所有交叉点；

使用所述交叉点来识别连接线；以及

用所述连接线形成所述线群组。

5.根据权利要求1所述的方法，其中从所述多个线形成所述线群组包括：

从所述多个线建构图形；

计算所述多个线的所有交叉点；

使用每一对交叉点之间的连接产生所关注子图；以及

从所述所关注子图形成所述线群组。

6.根据权利要求5所述的方法，其进一步包括通过将所述对象的参考模型与所述所关注子图进行匹配而检测所述待跟踪对象。

7.根据权利要求5所述的方法，其中使用所述线群组来跟踪所述对象包括将所述对象的参考模型与所述所关注子图进行匹配。

8.根据权利要求5所述的方法，其中产生所述所关注子图包括：

重复地将所述图形和每一所得子图分裂成两个，直到每一所得子图含有一个环形为止；以及

将含有一个环形的所得子图报告为所关注子图。

9.根据权利要求1所述的方法，其中使用所述线群组来跟踪所述对象包括使用所述线群组来比较所述对象的当前图像与所述对象的先前图像。

10.一种设备，其包括：

相机；

连接到所述相机的处理器，所述处理器经配置以：检测由所述相机所俘获的待跟踪对象的图像中的多个线，从所述多个线形成线群组，以及使用所述线群组来跟踪所述对象。

11.根据权利要求10所述的设备，其中所述线群组包括连接线。

12.根据权利要求11所述的设备，其中所述连接线形成闭合图形。

13.根据权利要求10所述的设备，其中所述处理器经配置以通过经配置以计算所述多个线的所有交叉点、使用所述交叉点来识别连接线以及用所述连接线形成所述线群组而从所述多个线形成所述线群组。

14.根据权利要求10所述的设备，其中所述处理器经配置以通过经配置以从所述多个线建构图形；计算所述多个线的所有交叉点；使用每一对交叉点之间的连接而产生所关注子图；以及从所述所关注子图形成所述线群组而从所述多个线形成所述线群组。

15.根据权利要求14所述的设备，其中所述处理器进一步经配置以通过经配置以将所述对象的参考模型与所述所关注子图进行匹配而检测所述待跟踪对象。

16.根据权利要求14所述的设备，其中所述处理器经配置以通过经配置以将所述对象的参考模型与所述所关注子图进行匹配而使用所述线群组来跟踪所述对象。

17.根据权利要求14所述的设备，其中所述处理器经配置以通过经配置以反复地将所述图形和每一所得子图分裂成两个，直到每一所得子图含有一个环形为止；以及将含有一个环形的所得子图报告为所关注子图而产生所述所关注子图。

18.根据权利要求10所述的设备，其中所述处理器经配置以通过经配置以比较由所述相机所俘获的所述对象的当前图像与由所述相机所俘获的所述对象的先前图像而使用所述线群组来跟踪所述对象。

19.一种设备，其包括：

用于俘获待跟踪对象的图像的装置；

用于检测所述对象的所述图像中的多个线的装置；

用于从所述多个线形成线群组的装置；以及

用于使用所述线群组来跟踪所述对象的装置。

20.根据权利要求19所述的设备，其中所述线群组包括形成闭合图形的连接线。

21.根据权利要求19所述的设备，其中所述用于从所述多个线形成所述线群组的装置包括：

用于计算所述多个线的所有交叉点的装置；

用于使用所述交叉点来识别连接线的装置；以及

用于用所述连接线形成所述线群组的装置。

22.根据权利要求19所述的设备，其中所述用于从所述多个线形成所述线群组的装置包括：

用于从所述多个线建构图形的装置；

用于计算所述多个线的所有交叉点的装置；

用于使用每一对交叉点之间的连接而产生所关注子图的装置；以及

用于从所述所关注子图形成所述线群组的装置。

23.根据权利要求19所述的设备，其中所述用于使用所述线群组来跟踪所述对象的装置包括用于使用所述线群组来比较所述对象的当前图像与所述对象的先前图像的装置。

24.一种其上包含有所存储的程序代码的非暂时性计算机可读媒体，其包括：

用以俘获待跟踪对象的图像的程序代码；

用以检测所述对象的所述图像中的多个线的程序代码；

用以从所述多个线形成线群组的程序代码；以及

用以使用所述线群组来跟踪所述对象的程序代码。

25.根据权利要求24所述的非暂时性计算机可读媒体，其中所述线群组包括形成闭合图形的连接线。

26.根据权利要求24所述的非暂时性计算机可读媒体，其中所述用以从所述多个线形成所述线群组的程序代码包括：

用以计算所述多个线的所有交叉点的程序代码；

用以使用所述交叉点来识别连接线的程序代码；以及

用以用所述连接线形成所述线群组的程序代码。

27.根据权利要求24所述的非暂时性计算机可读媒体，其中从所述多个线形成所述线群组包括：

用以从所述多个线建构图形的程序代码；

用以计算所述多个线的所有交叉点的程序代码；

用以使用每一对交叉点之间的连接而产生所关注子图的程序代码；以及

用以从所述所关注子图形成所述线群组的程序代码。

28.根据权利要求24所述的非暂时性计算机可读媒体，其中所述用以使用所述线群组来跟踪所述对象的程序代码包括用以使用所述线群组来比较所述对象的当前图像与所述对象的先前图像的程序代码。

Images