用于视频流中的对象识别和跟踪的系统和方法

摘要

本发明提供一种用于在视频流中进行对象检测和对象跟踪的系统方法。将视频流的帧划分为关注区域，并且针对每个关注区域计算区域包含至少一部分要被跟踪的对象的概率。接着基于所计算的概率将每个帧中的关注对象分类。接着，针对每个视频帧构建关注区域(RI)帧，所述关注区域(RI)帧报告视频帧中的关注区域的分类。接着比较两个或者更多个RI帧以确定对象的运动。本发明还提供执行本发明的方法的系统以及包括该系统的装置。例如，装置可以是便携式计算机、移动电话、或者娱乐装置。

说明书

技术领域

本发明涉及用于对象检测和跟踪的方法和系统，以及包含这种系统的装置。

背景技术

下面的现有技术出版物被认为对理解本发明有关。

Digital Image Processing by Rafael C.Gonzalez，Richard E.Woods and Steven L. Eddins，Prentice Hall(2004)，10.4.2-Region Growing.

E.Deja，M.M.Deja，Dictionary of Distances，Elsevier(2006).

Mahalanobis，P C(1936).″On the generalised distance in statistics″.Proceedings of the  National Institute of Sciences of India 2(1)：49-55).

Itakura F.，″Line spectrum representation of linear predictive coefficients of speech  signals，″J.Acoust.Soc.Am.，57，537(A)，1975.

James M.Abello，Panos M.Pardalos，and Mauricio G.C.Resende(editors) (2002).Handbook of Massive Data Sets.Springer.

E.R.Berlekamp，Algebraic Coding Theory，McGraw-Hill 1968.

Richard W.Hamming.Error Detecting and Error Correcting Codes，Bell System  Technical Journal 26(2)：147-160，1950.

Dan Gusfield.Algorithms on strings，trees，and sequences：computer science and  computational biology.Cambridge University Press，New York，NY，USA，1997).

美国专利第5,767,842号和第6,650,318号。

将数据输入到数据处理装置是使用诸如键盘、鼠标或者操纵杆的数据输入装置实 现的。尽管电子装置被不断地小型化，但是各种相关的数据输入装置的大小不能充分 地缩小，这是因为它们必须符合用户的手的大小。因此提出了用户的手不需要触摸装 置来输入数据的方法。例如，授权给Korth的美国专利第5,767,842号和授权给Arnon 的美国专利第6,650,318号公开了一种光学系统，其中使用照相机来监视用户的手和 手指运动。软件应用将这些运动解读为在物理上不存在的计算机键盘或者其它输入装 置上的操作。在这些系统中，相机具有固定位置，因而图像的背景保持恒定。这就允 许软件应用利用存在于恒定背景中的信息来检测每幅图像中的用户的手。因此，该系 统不能用在使用中会运动的装置中，这是因为，在此情况下图像的背景不恒定，所以 图像中没有可靠的背景信息。在使用中会运动的装置包括手持装置，诸如个人数字助 理(PDA)、移动电话、数字照相机和移动游戏机。

发明内容

在其第一个方面中，本发明提供了一种用于在视频流中进行对象检测和跟踪的系 统。本发明的系统基于两个单独的逻辑架构。第一架构将视频流划分为关注区域，其 充当环境中的单独的运动传感器、独立地负责计算在区域中存在被跟踪对象的可能 性。第二架构基于可能性的模式来监视区域集合随着时间的行为，计算被跟踪对象的 位置和运动参数。

本发明的系统包括存储器，其存储要被系统分析的视频流的帧。处理器获取存储 在存储器中的视频流的帧。对象检测模块根据关注区域包含至少一部分的要跟踪的预 定对象的概率、将每个帧中的关注区域分类。如下所述，对象检测模块的对象检测不 涉及帧中的对象的边缘检测。对象跟踪模块接收由对象检测模块所输出的分类的帧作 为其输入，通过比较连续的分类的帧来确定对象的运动。本发明的系统可以用于向装 置输入操作系统(OS)命令，代替诸如键盘、鼠标或者操纵杆的与装置相关联的任何输 入装置或者在这些输入装置之外添加。本发明的系统可以用于任何类型的数据处理装 置，例如个人计算机(PC)、便携式计算机(诸如PDA、膝上型计算机或者奔迈掌上通 (Palm Pilot))、移动电话、收音机或者其它娱乐装置、交通工具、数字照相机、移动 游戏机、计算机医疗装置和智能住宅产品。

根据应用，处理器可以可选地包括模式识别模块，模式识别模块从预定的对象运 动的集合识别被跟踪对象的运动的模式。该系统还可以包括存储有查找表的OS命令 执行模块，该OS命令执行模块针对一个或者更多个预定的运动模式的每一个提供关 联的OS命令。当识别出了一个预定的对象运动时，通过系统执行与该运动相关联的 OS命令。

在其第二个方面中，本发明提供了一种包括本发明的系统的数据处理装置。例如， 数据处理装置可以是个人计算机(PC)、诸如PDA、膝上型计算机的便携式计算机、 或者移动电话、收音机或者其它娱乐装置、交通工具、数字式照相机或者移动游戏机。 本发明的装置具有摄像机和处理器，它们被配置为进行如上所述的对象检测和对象跟 踪。例如，要被检测和跟踪的对象可以是用户的手或者手指，或者手持触笔，或者其 它预定的或者专用的装置。

本发明的装置包括存储有查找表的存储器，该查找表针对每个识别出的运动提供 相关联的OS命令。当通过模式识别模块检测到运动模式时，在查找表中查找与该运 动相关联的OS命令，并且接着执行与该运动相关联的OS命令。例如，OS命令可以 是诸如扬声器开/关、MP3/IPTV的下一/前一音轨、控制GPS应用中的地图浏览和打 开语音邮箱服务的激活功能。

根据本发明的此方面，将视频流的帧划分为两个或者更多个关注区域。针对每个 关注区域，执行关注区域中的像素的统计分析。例如，统计分析可以包括针对基于所 述关注区域中的像素限定的一个或者更多个函数中的每一个函数产生直方图。例如， 该函数可以是像素的红色、绿色或者蓝色的任意一个的强度，或者像素的色相、饱和 度或者亮度的任意一个。直方图可以是单变量的直方图或者可以是多变量的直方图， 其中像素属性的n元组的频率被计数。统计分析还可以包括计算任意一个或更多个直 方图的诸如平均数、众数、标准差、或者方差的统计参数的值。使用关注区域的统计 分析的结果、根据该区域包括至少一部分被检测对象的概率对该区域分类。针对每个 分析的帧，产生“关注区域(RI)帧”，它是帧的关注区域的分类的表征。

使用一个或者更多个模式检测模块、根据RI帧来检测对象的特定运动模式。每 个模式检测模块输出在时间窗口期间发生模式检测模块检测到特定的运动模式的概 率。将一个或者更多个模式识别模块的输出输入到运动识别模块，运动识别模块确定 最有可能已发生的运动模式。运动检测模块的确定基于从模式识别模块所输入的概 率，并且还可以将外部输入考虑在内，外部输入例如来自操作系统或者运行的应用的 输入。

由此，在其第一个方面中，本发明提供了一种用于在视频流中进行对象检测和跟 踪的系统，该系统包括：

(a)处理器，其包括对象检测模块和对象跟踪模块；

其中所述对象检测模块被配置为：

(i)针对所述视频流中的两个或者更多个帧中的每个帧中的一个或者更多个关 注区域的每个关注区域计算所述关注区域包含至少一部分要被跟踪的对象的概率；以 及

(ii)根据所计算出的概率将所述两个或者更多个帧的每个帧中的关注区域分 类，并且针对每个视频帧产生关注区域(RI)帧，RI帧报告关注区域的分类；

并且其中，所述对象跟踪模块被配置为：

(i)比较由所述对象检测模块所产生的两个RI帧，并且确定对象的运动。

对象跟踪模块可以包括一个或者更多个模式检测模块，每个模式检测模块被配置 为计算时间窗口期间被跟踪对象的运动的特定模式在所述时间窗口期间发生的概率。 对象跟踪模块还可以包括运动识别模块，所述运动识别模块基于一个或者更多个模式 检测模块所产生的概率来确定最有可能发生的运动模式。运动识别模块的确定可能涉 及将外部信号考虑在内。

本发明的系统还可以包括操作系统(OS)命令执行模块，该模块被配置为执行与所 识别出的运动的模式相关联的OS命令。

在其第二个方面中，本发明提供了一种用于在视频流中进行对象检测和跟踪的方 法，该方法包括：

(i)针对所述视频流中的两个或者更多个帧的每个帧中的一个或者更多个关注 区域的每个关注区域计算所述关注区域包含至少一部分要被跟踪的对象的概率；

(ii)根据所计算出的概率将所述两个或者更多个帧的每个帧中的关注区域分 类，并且针对各视频帧产生关注区域(RI)帧，RI帧报告关注区域的分类；以及

(i)比较由所述对象检测模块产生的两个或者更多个RI帧并且确定对象的运动。

关注区域包含至少一部分要被跟踪的对象的概率可以以以下方法获得，所述方法 包括：

(a)针对所述视频流中的每个帧中的一个或者更多个关注区域的每个关注区域计 算在所述关注区域中的像素的统计分析；

(b)在涉及所述视频流的一个或者更多个先前帧中的所述关注区域的统计分析的 计算中计算所述关注区域的离散分类。

统计分析可以包括针对基于所述关注区域中的像素所限定的一个或者更多个函 数的每个函数产生直方图。一个或者更多个函数可以从包括以下各项的组中选出：

(a)所述像素的红色、绿色或者蓝色的任意一个的强度；以及

(b)所述像素的色相、饱和度或者亮度的任意一个。

本发明的方法还可以包括计算所述一个或者更多个函数的统计参数的值。一个或 者更多个统计参数可以从包括以下各项的组中选出：

(a)平均数；

(b)众数；

(c)标准差；以及

(d)方差。

比较两个或者更多个RI帧的步骤可以包括：

(a)针对每个帧、以及针对所述帧中的每个分类的关注区域，将所述关注区域的分 类与在包含所述帧的时间窗口中获得的多个帧中的关注区域的分类相比较；

(b)基于所述比较确定所选择的关注区域是否包含要被跟踪的对象；

(c)基于该确定、根据关注区域是否包含要被跟踪的对象将所述关注对象重新分 类；以及

(d)基于在时间窗口期间两个或者更多个区域的状态的变化来计算所述对象的运 动的一个或者更多个跟踪参数。

跟踪参数可以从包括以下各项的组中选出：

(a)所述对象的运动的方向；

(b)所述对象的运动的速度；

(c)所述对象的加速度；

(d)以像素计量的所述对象的宽度；以及

(e)以像素计量的所述对象的高度；以及

(f)所述对象在所述帧中的位置。

在其另一个方面中，本发明提供了一种包括本发明的系统的数据处理装置。数据 处理装置可以从包括以下各项的组中选出：

(a)个人计算机(PC)；

(b)诸如PDA或者膝上型计算机的便携式计算机；

(c)移动电话；

(d)收音机；

(e)娱乐装置；

(f)智能住所；

(g)交通工具；

(h)数字照相机；

(i)厨房电器；

(j)媒体播放器或者媒体系统；

(k)基于位置的装置；以及

(l)移动游戏机；

(m)微型投影仪或者嵌入式投影仪；

(n)医疗显示装置；

(o)车载/机载信息娱乐系统。

本发明的装置还可以包括摄像机和显示屏幕中的一个或者两者。

被跟踪对象的一个或者更多个运动的模式可以从包括以下各项的组中选出：

(a)在所述时间窗口期间以像素计量的对象的宽度增加；

(b)在所述时间窗口期间以像素计的对象的所述宽度减少；

(c)所述对象运动接近所述照相机；

(d)所述对象运动远离所述照相机；

(e)所述对象在预定路径上运动；

(f)所述对象旋转；

(g)所述对象为静止；

(h)所述对象进行任意类型的运动；

(i)所述对象进行轻敲运动；

(j)所述对象加速；

(k)所述对象减速；以及

所述对象运动接着停止。

处理器还可以包括操作系统(OS)命令执行模块，操作系统(OS)命令执行模块被配 置为执行所述装置的与所识别出的运动的模式相关联的OS命令。OS命令可以从包 括以下各项的组中选出：

(a)按下显示在所述装置的显示屏幕上的虚拟按键；

(b)将在所述装置的显示屏幕上出现的光标移动到所述屏幕上的新位置；

(c)转动选择转盘；

(d)在多个桌上型计算机之间切换；

(e)在中央处理单元上运行预定的软件应用；

(f)关闭应用；

(g)打开或者关闭扬声器；

(h)调高/调低音量；

(i)转换到媒体播放器的下一音轨或者前一音轨，或者在IPTV频道之间转换；

(j)控制GPS应用；

(k)打开语音信箱服务；

(l)在照片/音乐专辑库中巡览；

(m)滚动网页、电子邮件、文档或者地图；

(n)控制移动游戏中的动作；以及

(o)控制交互式视频或者动画内容。

还应理解的是，根据本发明的系统可以是被适当编程的计算机。类似地，本发明 预期一种可被计算机读取以便执行本发明的方法的计算机程序。本发明还预期一种有 形的机器可读存储器，该机器可读存储器收录可被所述机器执行以便执行本发明的方 法的指令的程序。

附图说明

为了理解本发明并了解如何在实践中实施本发明，现在通过仅为非限制性的示例 并参照附图来描述一些实施方式，附图中：

图1示意性地示出了包括被划分为关注区域的多个帧的视频流；

图2示出了根据本发明的一种实施方式的用于对象检测和跟踪的系统；

图3示出了根据本发明的一种实施方式的用于对象检测的方法；

图4a示出了视频流中的三个帧，并且图4b示出了从图4a的帧所获得的关注区 域(RI)帧；

图5示出了根据本发明的一种实施方式的用于对象跟踪的方法；

图6示出了用于对象检测和跟踪的、包括本发明的系统的数据处理装置；

图7示出了运动模式的示例和在各种类型的装置中执行OS命令的用途的示例； 以及

具体实施方式

图1示意性地示出了包括视频帧4的序列的视频序列2。图1示出4个帧：4a、 4b、4c和4d。这仅仅是示例，视频序列2可以包括至少为2的任意数目的视频帧。 每个帧包括被划分为关注区域6的多个像素，在图1中用虚线8表示关注区域的边界。 图1中示出了帧4被划分为36个关注区域6(6行，每行6个关注区域)。这仅仅是示 例，帧4可被划分为至少为2的任意数目的关注区域。关注区域可以具有任意形状， 并且可以交叠。

图2示出了根据本发明的一种实施方式的用于在诸如视频流2的视频流中进行对 象检测和跟踪的系统40。视频流2被输入到存储器44中。存储器44可被处理器46 访问，处理器46获取存储在存储器44中的视频流2的帧6。如以下所解释的，处理 器46包括对象检测模块45和对象跟踪模块47，对象检测模块45分析视频流2，对 象跟踪模块47分析对象检测模块45的输出。对象检测模块45根据关注区域包含要 跟踪的对象的至少一部分的概率将各帧中的关注区域进行分类。对象跟踪模块47接 收由对象检测模块45所输出的分类的帧作为其输入，并且通过比较连续的帧中的关 注区域的分类来确定对象的运动。

系统40还可以包括OS命令执行模块51。在此情况下，存储器44存储查找表， 该查找表针对一个或者更多个预定的运动模式中的每一个提供关联的OS命令。当识 别出一个预定的对象运动时，执行与该运动相关联的OS命令。

如以下所解释的，用户输入装置48可以用于将任何相关数据输入到系统40，诸 如视频流2的标识、或者将被处理器46分析的参数。可以在显示装置50(诸如CRT 屏幕、LED或者打印机)上显示视频流2以及处理的结果。

图3示出了根据本发明的一种实施方式的由处理器46的对象检测模块45执行 的、用于在视频流2的帧中检测对象的处理20。处理开始于步骤18，在步骤18中， 从存储器44获取帧并且将帧划分为两个或更多个关注区域6。可以使用本领域已知 的任何对象分割技术(如在Rafael C.Gonzalez，Richard E.Woods and Steven L.Eddins， Digital Image Processing，Prentice Hall(2004)，Section 10.4.1(Region Growing)中公开 的种子区域生长(seeded region growing))来动态地创建关注区域。另选地，可以将关注 区域静态地限定为一组区域，诸如通过固定的6×6矩阵将帧分割为36个区域。接着， 在步骤24，在帧中选择关注区域6，并且在步骤26对关注区域中的像素进行统计分 析。例如，统计分析可以包括针对基于区域中的像素所限定的一个或更多个函数的每 一个产生直方图10。例如，该函数可以是像素的红色、绿色或者蓝色的任意一个的 强度，或者像素的色相、饱和度或者亮度中的任意一个。直方图可以是单变量的直方 图或者可以是多变量的直方图，其中像素属性的n元组的频率被计数。统计分析还可 以包括计算任意一个或更多个直方图的诸如平均数、众数、标准差、或者方差的统计 参数的值。将统计分析的结果存储在存储器44中。

在步骤30中，对刚被分析的关注区域进行分类。关注区域的分类是描述在关注 区域中存在被跟踪对象的概率的离散函数。使用涉及视频流的当前帧中的关注区域的 统计分析和视频流的一个或更多个先前帧中的关注区域的统计分析的方法确定关注 区域的分类。在一种实施方式中，应用距离函数以计算所选择的区域中的各种参数和 统计特征与表示被跟踪对象经过该区域的参数和统计特征的相似性。区域和对象参数 例如可以包括不同形状和轮廓的存在以及它们的频率，而统计特征可以例如包括色 相、亮度和饱和度的直方图以及颜色模式。将组合的距离结果与先前帧中的关注区域 的结果进行比较。例如，色相参数中的距离可以指示与被跟踪对象的颜色相同的对象 已经进入该区域。这可以使该区域被分类为具有包含被跟踪对象的更高的概率。该距 离函数例如可以是欧几里得距离(E.Deja，M.M.Deja，Dictionary of Distances，Elsevier  (2006))；马哈拉诺比斯距离(Mahalanobis，P C(1936).“On the generalised distance in  statistics”.Proceedings of the National Institute of Sciences of India 2(1)：49-55)；板仓- 齐藤(Itakura saito)距离(Itakura F.，″Line spectrum representation of linear predictive  coefficients of speech signals，″J.Acoust.Soc.Am.，57，537(A)，1975)；切比雪夫距离 (James M.Abello，Panos M.Pardalos，and Mauricio G.C.Resende(editors) (2002).Handbook of Massive Data Sets.Springer.)；李(Lee)距离(E.R.Berlekamp， Algebraic Coding Theory，McGraw-Hill 1968)；汉明距离(Richard W.Hamming.Error  Detecting and Error Correcting Codes，Bell System Technical Journal 26(2)：147-160， 1950)；或者莱文斯坦(Levenshtein)距离(Dan Gusfield.Algorithms on strings，trees，and  sequences：computer science and computational biology.Cambridge University Press， New York，NY，USA，1997)。将所选择的关注区域的分类存储在存储器44中(步骤31)。

在步骤32，确定帧的另一关注区域是否要被检测模块45分析。如果分析，则处 理返回步骤24，选择当前帧中的另一关注区域。否则，处理继续到步骤34，在步骤 34中产生针对视频帧的“关注区域(RI)帧”，并且处理终止。输入视频帧的RI帧是帧 的关注区域的分类的表征。图4a示出了在三个不同的时间(分别为时间t₀、t₁和t₂)所 获得的视频流的3个帧110a、110b和110c。在该示例中，将帧任意地划分为用虚线 112指示的静止的关注区域。另选地，可以使用将帧动态地划分为关注区域的方法。 例如，预设种子区域的集合生长为保持统计均一性的更大的区域。例如，位于图4 的天空区域的种子区域将生长直至该区域达到色相直方图和边缘频率急剧变化的地 面。可以通过预先知道要跟踪的期望的运动的轴线、或者多个帧的统计分析来辅助该 划分处理，其中该统计分析确定应从原始关注组中省略的高方差区域。在从t₀到t₂的时间间隔期间，要跟踪的对象114在帧中运动。图4b示出了分别对应于视频帧110a、 110b和110c的关注区域帧116a、116b和116c。在图4的示例中，根据对象114的至 少一部分是否位于关注区域中(在图4b中通过关注区域的网纹网状线来指示)，或者 该关注区域是否不包含对象114的至少一部分(图4b中的无网纹网状线的关注区域)， 将每个关注区域分类为两种类别中的一种。由此，在时间t₀获得的RI帧116a中，将 位于帧的右侧的区域117a分类为包含对象114。可以通过计算区域和被跟踪对象的 相似性等级(例如通过测量被跟踪对象的色相直方图和所选择的区域的直方图之间的 欧几里德距离)来得到该分类。使用相同的方法，在中间帧116b中，两个区域117b 和117c被分类为包含对象114，并且在随后的帧116c中，两个区域117d和117e被 分类为包含对象114。

跟踪模块47接收在视频流的时间窗口期间由检测模块45所产生的RI帧作为其 输入。跟踪模块47可以与检测模块45同时工作，随着分类的帧被检测模块45产生 而接收分类的帧。另选地，跟踪模块47可以与检测模块45顺序地工作，仅在将视频 流的全部帧分类之后才接收所分类的帧。

图5示出了由根据本发明的一种实施方式的对象跟踪模块47执行的对象跟踪处 理。在步骤52中，将时间窗口的RI帧输入到跟踪模块47，在步骤54，对RI帧进行 滤波以去除随机噪声。接着将经滤波的RI帧输入到一个或者更多个独立的模式检测 模块56。每个模式检测模块56被配置为根据经滤波的RI帧来检测对象的特定的运 动模式，并且输出在时间窗口期间模式检测模块的特定的运动模式发生的概率。各个 模式检测模块56对部分的或全部的输入的RI帧施加模式识别测试。例如，再次参照 图4b，模式检测模块56将检测对象从帧的左侧向帧的右侧的运动。一个或者更多个 模式识别模块56的输出被输入到运动识别模块58。运动识别模块58确定在时间窗 口期间最可能发生的运动模式。运动检测模块58的确定基于从一个或者更多个模式 识别模块56输入的概率，并且还可以将外部输入考虑在内，外部输入例如为来自操 作系统或者运行的应用的输入。接着输出运动识别模块58的运动确定(步骤60)，并 且处理终止。

图6示出了根据本发明的此方面的一种实施方式的包括系统40的数据处理装置 72。例如，数据处理装置72可以是个人计算机(PC)、诸如PDA、膝上型计算机或者 奔迈掌上通的便携式计算机、或者移动电话、收音机或者其它娱乐装置、交通工具、 数字式照相机或者移动游戏机。装置72具有摄像机76。装置72还可以设置有显示 屏幕74和诸如键盘78的各种数据输入装置，其中，键盘78具有用于将数据输入到 数据输入装置72的多个按键80。

摄像机76观察由虚线指示的圆锥或者棱锥空间体86。摄像机76可以在装置72 上具有固定位置，在此情况下观察空间86相对于装置72是固定的，或者在装置72 上是可定位的，在此情况下观察空间86相对于装置72是可选择的。摄像机76捕捉 的图像被摄像机76数字化并且输入到处理器46(另见图2)。如上所述，处理器46的 对象检测模块45检测摄像机76所获得的帧中的预定对象94。对象94例如可以是处 于各种位置的用户的手指或者整个手，诸如伸开的手、闭合的手、或者手背。如果装 置2是手持式装置，则用户在使用中可以使用他的另一只手89来抓握装置2。手89 还可以用于激活与装置72相关联的真实输入装置，诸如激活键盘78上的按键80。

存储器44存储查找表，该查找表针对每个测试提供相关联的OS命令。当通过 模式识别模块49检测到运动模式时，在存储于存储器44中的查找表中查找与该运动 相关联的OS命令，接着OS执行模块51执行与该运动相关联的OS命令。例如，OS 命令可以是按压在显示屏幕上显示的虚拟键、将显示屏幕上出现的光标移动到所述屏 幕上的新位置、在处理器46上运行存储在存储器44中的软件应用、或者关闭装置 72。装置可以提供已经执行了OS命令的指示。例如，可以通过在屏幕4的虚拟键盘 上简单地示出被按压的按键、或者通过简单地改变按键的外观来指示等同于按压虚拟 键盘上的按键的OS命令。指示已经执行了OS命令的其它可能方法包括：简单地放 大或者以其它方式改变被按压的键或者光标在屏幕4上的外观；在屏幕4上显示图标； 产生声音以及使装置振动。

图7示出了可以由模式检测模块56识别出的运动模式的示例、以及根据装置72 的类型如何使用运动模式以执行OS命令的示例。运动100包括将手移向装置72。运 动102包括将手移向装置72接着将手从装置移开。运动104包括在装置上方从左向 右移动手，并且运动106包括在装置上方从右向左移动手。