使用傅里叶图像相关进行图像跟踪和计算机视觉

• 下载代码
• 下载演示

引言

计算机视觉中最基本的事情之一就是识别和跟踪。人类视觉有些复杂，我们对它的理解并不完美，有时会基于它的失灵（光学错觉）来判断。例如，给定一张有四台发动机的飞机照片，然后看到一张相同的、只有三台发动机的图像，你的大脑需要多长时间才能告诉你它们不一样，这取决于图像的比例。我们的大脑是高度并行处理的，我们会填充/修正并构建一个视图，然后将其呈现给我们的意识，这是一个基于许多生物图像的过滤视图。计算机视觉还不能（还）尝试这种方法，因为计算机的算力还不够。即使模仿人类视觉有好处，我们也会受到其缺点的困扰。有几种好的计算机视觉方法（Haar、傅里叶、特征提取）可以简化/减少计算量。在未来的几年里，也许读者会为世界发现一种新的方法。

本文以及配套的代码演示了一种基于傅里叶的方法及其优势。每种方法都有其优缺点，并适用于不同的场景。傅里叶技术之所以有趣，是因为训练速度快，比Haar快得多，而且代码最容易编写。我最初的目标是利用傅里叶作为快速Haar训练识别重要事物的桥梁。

代码使用了openCV.Net，这是一个非常出色的成像工具包，作者在多个平台上将其用于个人和商业项目，并取得了巨大成功。OpenCV库可以进行高度优化，并且有很好的示例。

背景

Haar、傅里叶和特征算法概述 

Haar

Haar小波技术尤其酷。我推荐阅读Viola和Jones关于提升级联的文章，它非常出色。总结来说，会形成一个“求和”图像，其中[x,y]的值是从0,0到x,y矩形区域内所有值的总和。通过差分多达十几个点，你可以独立于尺度（但不是旋转）计算出图像的任何部分与任何Haar特征的比较结果。分类器在图像上扫描，并形成不同的Haar特征比较。当一组比较只需要少量计算就“失败”时，它就会排除该区域。当一个比较结果良好时，下一个特征可能会以一种方式更精确地进行比较；如果比较结果小于某个阈值，则它可能会沿另一逻辑路径进行不同的比较，或者停止比较。例如，给定一张脸，第一个特征可能会排除任何看起来不圆的东西。下一个分类器可能会将可能性分为有眼镜和无眼镜的脸。这种统计比较、嵌套和精炼就是为什么它被称为提升级联。该技术的问题在于形成级联需要数百张“正面”图像和数百张“负面”图像，然后需要数小时才能创建分类器。有C#的人脸识别演示应用程序运行得非常快。

顺便说一句，作者制作了一个Haar特征查看器来查看几张已发布的Haar特征图，发现它们与目标并不相似。Haar特征图会锁定并提取人眼无法捕捉到的统计特征。例如，人脸的Haar特征图并不十分对称，也没有明显的特征似乎会锁定在眼睛、鼻子或下巴上。当各个层被“提升”/叠加时，看起来会稍微更像人脸。

傅里叶

这是一个不错的技术，因为你可以对源图像和目标图像进行FFT，将它们相乘，然后进行反变换。结果中值最大的位置是目标在源图像中最可能的位置。在OpenCV中，只需两行代码即可得到归一化（0到1=确定性）的似然度以及最大值位置。如果它们相似但不完全相同，则如果尺度、旋转或图像的一部分模糊或被遮挡，结果会出现模糊。另一个非常好的优点是，尽管比Haar慢，但如果源图像中有多个目标，你可以在同一步骤中找到它们。

特征提取

有许多变换可以相对快速地运行，它们可以将图像转换为一组点，这些点代表轮廓的角点或边缘。然后，可以将点的模式表示为旋转和尺度不变的模式进行检查。最清晰的例子是字符识别，但概念上是这样的：选取一些独特的东西，比如距离质心最远的点或最孤立的点，然后描述其他点相对于它的位置，旋转使下一个点相对于第一个点水平。这是一种非常快速的方法，训练起来也相对容易，而且已经有一些很好的此类应用的例子。它的编码也比傅里叶技术稍微困难一些。

傅里叶学习与跟踪

傅里叶数学

傅里叶变换将信号转换为其频率表示，其逆变换将频率转换回信号。假设你有以下信号

f(t) =  2, 0, 0, 2, 0, 0, 2.

傅里叶变换会将该信号与一组函数进行组合，其中每个函数与其他函数明显不同。事实上，函数集中的每个函数都必须是正交的：它们可以用来描述一个无限维向量空间中的单位向量，并且它们彼此之间不相关（一个函数乘以另一个函数在所有边界上的积分都为零）。有许多这样的集合（x，x^2，x^3，x^n，或sin(x)，sin(2x)，...，e^nx，勒让德多项式）。关键是使用一个易于计算和求逆的函数。最常见的是正弦函数。在成像中，有时具有半径特性的东西（柱谐函数）最能描述一个特征，但计算起来很困难；量子力学通常使用勒让德多项式；Haar技术使用Haar小波作为基函数。有关更多数学信息，请访问http://en.wikipedia.org/wiki/Fourier_optics。

当你不是组合连续波形而是处理一组测量值时，变换f(t)的常用方法是计算a、b、c、d... 等值，使得

F(t) = acos(t) + b sin(t) +c sin(2t) + d cos(2t) .... = f(t) = 2, 0, 0, 2, 0, 0, 2.

但是如何解出a、b、c、d？关键在于相关性，每个函数都是正交的，所以

sin (nt) f(t)  = An -> sin(2t)f(t) = c

使用FFT或快速傅里叶变换可以快速完成此操作，大多数数值技术都基于正弦函数的递归模式，关于FFT有大量的文章。

首先对图像的每一行执行FFT。这将创建一个描述值出现频率的行。然后再次对列进行FFT（行FFT的列FFT）。结果是一个大的浮点值数组，代表图像的频率分量。有趣的是，假设你拍摄一张图像，让它通过一个透镜，然后在焦点处观察图像，你会看到一个相似的模式（它的排列方式不同，并且因为它不是离散变换，所以看起来是平滑的），作者的意思是，数据并没有在二维FFT中丢失，只是以不同的方式表达。

相关性

一旦源图像和你想在其中找到的图像（目标）被转换为二维FFT，目标就是将它们重新组合（相乘矩阵）。我几年前学到这个的时候，第一个想法是，为什么？这有什么帮助？实际上发生的是，目标和源图像中匹配的频率会增加，而不匹配的频率会减小，结果是源图像中与目标匹配的位置的二维FFT。通过对结果进行逆二维FFT，你就可以得到目标在源图像中的位置图。

假设你有一张猫坐在沙发上，旁边有一只狗（源图像）的照片，目标是一只狗的脸。结果将是照片中狗脸所在位置的一个亮点。这个亮点有多亮，多清晰，取决于源图像中的狗脸与目标中的狗脸有多相似。如果完全相同（同一只狗，同一张图像），会有一个非常明亮、清晰的点。如果它们看起来相似但不完全是同一只狗，这个点就不会那么亮，并且会有些模糊。还可能会有一个不太亮、模糊的点，表明虽然狗可能不像猫，但它们的头部确实有一些共同的特征。

在上面的例子中，有几个东西被微妙地引入了

Cat * Dog   = Cross correlation

这种比较是你在寻找的东西和你没有在寻找的东西的相关程度。

Dog * Similar Dog = Matching correlation

这就是你可以用你的目标来识别你的目标的新图像的程度。

Dog * Same Dog = Auto correlation

该值表示当只有噪声是唯一区别时，目标和源的比较效果。

对于上面的例子，假设平均值为

Cat * Dog = 0.5,   Dog * Similar Dog = 0.7,     Dog * Same Dog = 0.95

通过对一系列图像进行数值计算，可以计算出阈值，以确定何时识别出某个物体以及何时未识别出，这在平均而言通常是有效的。

现在假设你正在图像中寻找两种不同的犬种，那么“狗 * 相似的狗”的值可能会接近“猫 * 狗”的值（匹配太接近交叉）。通过添加不同的目标（每种犬种一个），可以提高匹配阈值，因为一个目标关注一组特征，而另一个目标关注其他特征。

现在假设你在图像集中寻找任何一种狗，为了使目标数量保持较少，你需要使用看起来截然不同的狗的图像，或者使用看起来像狗但没有任何猫特征的图像。例如，猫通常有明显的胡须，所以移除目标图像中的胡须会提高匹配和自相关数值，同时降低交叉相关值。

学习和跟踪的工作原理

用户加载视频，并在第一帧中选择一个矩形。代码还支持拍摄摄像机视频来创建训练视频。选择的图块成为第一个目标。它应该高度代表用户想要跟踪的对象。当下一帧出现时，代码会尝试找到该图块，如果图块与先前识别的对象相似，则学习代码可以继续跟踪该对象。如果检测结果与先前的不同，但统计上足够相似以至于仍然肯定是同一个对象，则将新的检测添加到目标列表中。如果添加的目标比先前的更好，则将其移除。

独特且酷的是，这段代码可以找到一小组独特的、能够清晰代表该对象的图像图块，涵盖不同的角度、模糊、尺度、仿射变换等。如果它在平均意义上与现有目标集相似，或与某个子集相似，那么它就肯定识别出了该对象。同时，它可能与大多数对象足够不同，以至于它可以成为一个新的独特目标。

作者的想法基于信号的演变方式。从非常基础的角度来看，跟踪一个物体就像跟踪任何事物一样，它是一个演变的信号。值会变化和偏移，但总的来说，它要么与前一个时间段相似，要么与过去的时间段相似。从信号处理的角度来说，当信号在一段时间内非常相似时，它是“平稳”的。代码尝试从视频的每个“平稳”周期中找到最有代表性的图像。

运行代码后，对象的状态可以序列化为XML。然后，跟踪器可以加载一个或多个命名的XML特征分类器，然后将其应用于视频并一次跟踪多个对象。

示例：假设你想训练一个机器人为每只走过的宠物命名。用户将拍摄每只宠物的视频，为每只宠物生成一个分类器目标，然后让跟踪器在摄像机图像上运行。

为了更好地理解学习过程，请想象一下。第一张图像是你的狗的侧面，所以这被声明为目标1。狗稍微移动了一下，但它与目标1非常相似，所以没有创建新目标。狗稍微转动了一下，创建了一个新的目标（2）。狗又转动了一下，创建了第三个目标（3）。这次目标3位于与1和2相同的位置，与两者相似，但略有不同。狗停止转动但小幅移动，创建了帧4和5。在第五帧，确定它与3和4非常相似，但与1和2非常不同。软件决定保留第五帧，丢弃3和4。如果软件使用了帧3、4、5中使用的所有先前图像，并找到了最能代表它们的那个目标，那就理想了，但这将需要大量的计算。相反，软件会一直替换之前的目标，直到看到一帧新的、不同的图像。它找到的不是信号“平稳”期的“最佳”图像，而是每个平稳期末尾的一个不错的图像，因为这在计算上更快。假设时间又过去了，狗转了几圈，闻了闻相机等等。可能会有50个目标。然后假设狗又回到了它之前采取的“模式”。假设它现在匹配了帧5，拟议的新目标（51）取代了帧5。

跟踪性能

作者已成功使用该代码跟踪了以下内容

• 瓶子或玻璃杯的底部、顶部和液位。
• 书写符号的位置。
• 写在人手臂上的符号，当人移动和转动时。
• 跟踪一个人的脸，当人移动、说话、转动和转回来时。
• 识别并跟踪武器（枪）。  

使用代码

代码的目标是使其足够好，能够快速（几分钟）训练一个新特征，并能够相对较好地跟踪它（如果训练具有代表性）。这意味着该技术不会像人脑那样创建一个三维尺度和旋转不变的模型进行匹配。它在速度上不如特征或Haar，也不是特别具有尺度/旋转不变性。因为它不仅使用边缘/细节，还使用轮廓，所以它比Haar或基于特征的技术能更好地锁定和跟踪图像的细微方面。

该技术速度快，训练快，易于编码，而且非常准确。例如，如果你想制造一个自校准的3D打印机器人（正如作者所希望的那样），或者让一个机器人根据摄像头在一个房子里导航（另一个副项目），这是一种绝佳的技术。

学习 

使用该代码最简单的方法是

1. 转到“Cam coder”选项卡，录制视频，将其保存为AVI。
2. 将其加载到学习选项卡中，选择要跟踪的特征。
3. 调整区域等，直到跟踪良好。
4. 将其保存为XML。 

分类 

分类器代码有一个演示选项卡，但总体的思路是，你将XML文件加载到分类器中作为要查找的不同对象，然后将其传递给一个要查看的帧，你就可以看到它找到的对象的（带矩形标记的）位置。

Classifier cls = new Classifier();
cls.Reset();
cls.AddFeature(fileName);
cls.AddFeature(otherFileName);
cls.Features.Add(myRuntimeCreatedFeature);
cls.Classify(iplImageFrame, outputBitmap); 

就是这么简单。

这样，你就可以使用内置的卡尔曼滤波器来检测和跟踪人脸、物体、汽车。

以下是内置的酷炫类/功能

• 用于关联跟踪的卡尔曼滤波器
• 一次跟踪多个特征/对象。 
• 实时学习跟踪新对象。
• 一个轻度封装的OpenCV相机接口。
• 一个用于在图像上添加文本/标记以进行调试/分析的类。

关注点

作者编写了大量优化代码，因此，任何可以变得更快的东西似乎都是需要做的。代码速度很快，足以在上网本上运行，在I3或更高配置上运行得很好，但如果更快，就可以做更多事情。除了优化之外，代码还是单线程的，在I7之类的设备上，通过添加多线程（当然，这也会占用其他资源的可用性），代码可以运行快2-4倍。

OpenCV的实现是半优化的。卷积速度很快（FFT），速度几乎最快。问题在于，要比较源与10个目标，源需要进行10次FFT，目标需要进行10次FFT，然后将它们相乘，并执行10次逆FFT。目标只需要进行一次前向FFT，而不是每帧一次，源只需要进行一次FFT。

• 当前实现 N 个目标： N*SFFT + N*TFFT + N*Multiply + N*IFFT
• N 个目标的最低要求： 1*SFFT + N*Multiply + N*IFFT。
• 潜在节省：超过一半。

作者还在考虑立体视觉。想象一下一个带有立体摄像头的机器人：对于每一对帧，帧的各个部分如何匹配，你就可以计算出距离。有趣的是，这可以自动识别出可能的跟踪对象，并提供对象的两个图像。有了快速的学习跟踪器，这意味着可以形成一个周围环境的心理地图，其中包含跟踪的对象。机器人还可以区分近处和远处的事物，以及远距离很可能是静止的（树木、地标、墙壁），然后利用这些事物来帮助建立导航。