在AR中玩俄罗斯方块

我想到这个房子可能是玩俄罗斯方块的好平台。 离我不远的地方只有一栋适合于此的建筑物。 结果可以在视频中看到：


该项目的实施水平很低，没有使用任何现成的解决方案。

源代码

大多数情况下，他们使用2个选项来实现增强现实：

• 无标记的，即 摄像机的位置取决于视频流关键点的移动；
• 图像作为相对于相机位置的标记。

这些实现不需要特殊的准备或特殊的条件。

还有另一个实现选项-识别特定对象并将其用作标记。 这至少需要它的存在，但是可以对其进行视觉控制。 这种识别的方法之一是通过边缘检测物体。 它有局限性-标记对象必须具有明确定义的边缘，即 该对象最有可能是固体。

或应明确划定边缘，例如建筑物的照明：



可以看出，背光可以容易地在图像中分离并用于检测。

实作

在Qt。 该框架使您可以在不同的平台上同时使用C ++进行工作。 由于性能对我们很重要，因此专业人士似乎是一个显而易见的选择。

尽管Qt在android上无法很好地运行（长时间启动，已禁用调试），但是通过在桌面上调试算法的能力，这一切都得到了解决。

在嵌入Qt的原始OpenGL中可视化了三维图形。

相机的工作是通过Qt进行的。 录制了一个视频以进行调试，它非常方便，可以用文件中的视频流替换摄像机的视频流。

输出是通过qml工具进行的。 结交qml和OpenGL并不是没有问题，但是我们不会对此进行详细介绍。

为了进行图像处理，连接了OpenCV库。

追踪算法

现在，让我们继续进行最有趣的部分-沿对象边缘跟踪对象的算法。
并从突出显示图像的边缘开始。 在我们的案例中，所有边缘均具有直线形式，因此首先想到的是使用线检测器。 霍夫变换可以用作线检测器。 但是，在我看来，这种方式不是很正确，因为霍夫变换非常昂贵，而且该检测器也不是很可靠（这是主观的，也许一切取决于任务）。
相反，让我们以一种不同的，更一般的方式进行。 我们不会考虑我们的直线是直线的，但是我们只会在二进制图像上工作。 边缘的存在将被编码到二进制图像中。 即 值为零的像素表示此位置存在边缘，该像素值大于零-没有边缘。 可以使用Canny边界检测器或简单的阈值转换来获得此类图像。 这些算法可以在OpenCV中找到。

OpenCV现在对我们还有另一个有用的功能-distanceTransform，它在输入处获取一个二进制图像，并在输出处提供一个图像，以像素为单位，其中距离最近的零像素被编码。

现在，假设我们已经对模型的位置有了一个很好的近似。 接下来，我们描述误差函数，该函数描述近似值的边缘与结果图像中的边缘不一致的程度。 使用distanceTransform中的图像，我们已经能够做到这一点。 然后，我们运行函数优化算法，仅更改对象在空间中位置的近似值。 结果，我们的近似值应该相当准确地描述物体的真实位置。
结果，该算法可以分为两个阶段：

1. 图像预处理-二值化，滤波和distanceTransfrom函数的使用。
2. 跟踪-错误功能的优化。

图像预处理

此时，您需要突出显示图像中的边缘。 您可以使用Canny边界检测器，但在我们的情况下，通常的阈值转换或其自适应版本效果更好（在OpenCV中，这些是阈值或adaptiveThreshold函数）。 显然，这样的图像上会有噪点，因此需要过滤。 让我们按照以下步骤进行操作-使用OpenCV函数findCountours选择轮廓，并删除太小或不够像线段的线段。

处理结果可以在图像中看到：



一致：原始图像->阈值变换后->过滤后。

该图像已经很清楚地告诉我们哪里有右边，哪里没有。 之后，我们使用distanceTransform函数，结果，我们将获得有关每个点距边缘多远的信息。 结果图像表示为 。

如果进行标准化和可视化，则外观如下：



接下来，我们将需要一些数学工具。

功能优化算法

功能优化是寻找功能最小值的任务。

如果我们要处理线性方程组，那么找到最小值非常简单。 想象一下矩阵形式的方程组： ，那么我们的解决方案： 。 如果我们有一个超定的方程组，那么我们可以使用最小二乘法 ： 。

如果我们的函数是非线性的，那么任务将变得更加复杂。 要找到最小值，可以使用Gauss-Newton算法 。 该算法的工作原理如下：

1. 假设我们已经对解决方案有了一些初步的近似 我们将反复完善。
2. 使用泰勒展开，我们可以在当前逼近点逼近非线性函数。 我们用最小二乘法求解所得的线性方程组，得到 。 结果，所得解决方案将不是解决方案，但将比当前近似值更近。
3. 替换当前的近似值 收到决定 并转到步骤2。 和 将不小于特定值。

让我们更详细地分析算法。

让 -工作功能， -函数值的先前已知向量。 完美的方程式解决方案 以下说法是正确的 。 但是我们只有它的近似值 。 然后，该近似值的误差向量表示为： 。 该函数的一般错误将是： 。 现在发现这样 在哪 将达到最小值，我们将获得更好的解决方案近似值 。
从方法开始 我们将迭代逼近，每次迭代 。 为此，我们需要进行每次迭代以计算该函数的Jacobi矩阵 对于当前的近似值，由我们函数的导数组成：

并给出以下近似值： 。
通常，任务的构造方式使我们拥有大量彼此独立的数据（仅与值无关）。 ） 结果，一般的雅可比矩阵非常稀疏。 有一种方法可以优化计算。
假设从一组点计算出一个公共函数。 从第j点我们得到 。 代替计算雅可比矩阵 对于整个函数，我们专门计算雅可比矩阵 并表示为： 。 然后，将给出以下近似值： 。 此外，此更改使您可以并行计算。
可能发生以下值 会犯一个比 。 要解决此问题，您可以使用算法的改进形式-Levenberg-Marquardt算法 。 增值 变成我们的公式： 在哪里 是单位矩阵。 价值 选择如下：

• 首先，它具有一些相当小的值（以使算法收敛）；
• 那么如果有错误 超过 ，然后增加价值 并尝试计算错误 再来一次

函数越非线性 该值应该越大 。 但是价值越大 ，算法收敛速度越慢。

我们何时完成算法 与...不同 小到拿 作为解决方案。

该算法非常通用，可用于多种任务。

数学跟踪模型

由于我们正在处理空间中的坐标，因此很明显，我们需要能够操纵这些坐标。 假设我们有一些要点 。 我们需要将它们绕零坐标的点旋转。 可能最简单的方法是使用旋转矩阵R ，它描述了必要的旋转： 。 如果我们需要移动点，则只需添加所需的向量t ： 。
因此，您可以随意更改对象在空间中的位置。 事实证明，物体的坐标是由三维矩阵R和三维矢量t确定的 。 12个参数 而且，这些参数不是彼此独立的，旋转矩阵的分量在一定条件下相互连接。 因此，从在优化中使用这些功能的角度来看，这些参数不是最佳解决方案。 参数多于自由度，它们之间存在关系。 还有另一种旋转形式- 罗德里格（Rodrigue）的旋转公式 。 该旋转由三个参数指定，形成一个三维矢量。

归一化向量是旋转轴，该向量的长度是绕该轴的旋转角度。

我们设置向量v的旋转函数： 使用Rodrigue公式的r参数。 我们从中得到以下公式： 。
最后，我们可以使用6维向量设置对象位置的坐标：
我们得到以下公式： 。

针孔相机型号

现在，我们描述项目中使用的相机的简单数学模型：

$$

$$\ vec {p} = \开始{pmatrix} p_x＆p_y \结束{pmatrix} ^ T = cam（\ vec {v}）= \开始{pmatrix} f_x \ frac {v_x} {v_z} + c_x＆f_y \ frac {v_y} {v_z} + c_y \ end {pmatrix} ^ T$$

在哪里 -焦距（以像素为单位）； -光学中心也以像素为单位。 这些是单独的摄像机参数，称为摄像机的固有参数。 通常，这些参数是预先已知的。 在这个项目中，这些参数是通过肉眼选择的。

该模型未考虑相机的镜头畸变（ 畸变 ）。 假设它们不是。

使用此模型，我们得到一个中心投影，其所有点都更趋向于光学中心，离摄像机越远。 因此，我们得到了铁路收窄的影响：



在空间中，相机与z轴对齐，图像平面平行于xy平面。 我们通过在空间中移动的能力来补充我们的模型：

$$

$$\ vec {p} _j = cam（rot（\ vec {x} _r，\ vec {v} _j）+ \ vec {x} _t）$$

因此，我们获得了一个模型，利用该模型可以以代数形式模拟从外部世界到摄像机图像（从世界坐标到屏幕）的点投影。 对于我们而言，在此模型中相机在空间中的相对位置的参数仍然未知。 。 这些参数称为相机的外部参数。

追踪

无需OpenCV工具即可实现。 首先，我们需要获得上述近似解决方案的误差函数。 我们将分阶段编写其计算：

1. 我们根据当前近似参数选择跟踪模型的可见边缘。
2. 我们将选定的一组边线变成一组固定的点，以简化计算。 例如，可以从每个边缘获取第n个点，或者（一种更正确的选择）选择一个数量，以使这些点之间的像素之间具有固定的距离。 我们将它们称为控制点（在项目中：controlPoint-控制点和controlPixelDistance-相同的固定距离，以像素为单位）。
3. 我们在图像上投影控制点。 借助distanceImage，我们可以获得控制点的投影到图像边缘的距离。 在理想情况下，所有控制点都应严格位于图像边缘，即 到肋骨的距离应为零。 基于此，我们得到特定控制点的错误： 。
4. 我们得到以下错误函数：

现在仍然需要找到最小的E。 为此，我们使用上述的Levenberg-Marquardt算法。 众所周知，该算法需要计算雅可比矩阵，即 派生函数。 您可以使用导数的数值发现。 您也可以对这种算法使用一些现成的解决方案。 但是，在该项目中，所有内容都是手动编写的，因此，我将描述整个解决方案的完整结论。

对于每个控制点，我们获得独立于其他点的方程。 上面已经描述了，在这种情况下，可以彼此独立地考虑这些方程，从而专门为每个方程计算雅可比矩阵。 我们将使用复杂函数的微分规则对命令进行分析：



我们表示 然后



从这里：



我们进一步表示 和 然后：


distanceImage的导数是数字形式的。 并用于计算向量 和 您将需要根据Rodrigue的旋转公式找到导数。 我在出版物“ 3D旋转导数的紧凑公式”中找到了雅可比矩阵。
指数坐标»吉列尔莫·加列戈，安东尼·叶兹 ：

，
其中R是根据旋转向量通过Rodrigue公式获得的旋转矩阵 ; -我们正在转向的重点； 我是单位矩阵； 。 正如我们在此处看到的，我们用旋转矢量的长度除以，如果矢量为零，则公式不再起作用。 这可能是由于在零矢量处未定义旋转轴这一事实。 如果旋转矢量非常接近于零，那么我们使用以下公式： 。
它仍然要绘画 和 （此处省略索引j ）：


因此，我们获得了所需点的Jacobi矩阵，并将其用于上述优化算法。

该算法存在几个问题。 首先，准确性。 结果，摄像机的全局位置在帧与帧之间略有跳跃。 您可以修复一下。 我们有一个先验信息，即摄像机的位置不会在帧与帧之间发生剧烈变化。 我们可以通过向函数添加其他方程式来减少这种抖动。

应当记住，在我们的情况下，位移矢量t不是摄像机全局位置的坐标。 全局位置是一个零坐标的局部点，因此可以如下得出：



我们记得上一帧在prevGlobalPosition中的位置。 现在以前的位置应该接近于零，即 向量长度 应该足够小。 即 除了差异的其他值，向量d也必须最小化。 为了确定此修改的影响程度，我们引入了 并乘以向量d ： 。 即 在优化算法中，我们另外将向量d'最小化。 当然，为此，有必要为其计算雅可比矩阵，该雅可比矩阵的推导方法与上文针对一般误差函数所推导的方法相同。

该算法的第二个问题是它可能陷入局部最小值。 在其他工作中，使用粒子过滤器可以解决此问题。 在我们的案例中，从原则上讲，这种选择就足够了。

跟踪物体带来的好处

了解了对象的位置和形状后，您可以在视觉上对其进行操作，这是我尝试在视频中演示的。 使用OpenGL着色器扭曲了对象。 在模型的帮助下，我将对象的点投影到图像上，从而获得了该点的颜色。 然后，您可以移动这一点，获得有趣的效果-例如，变形。 但是，必须记住，转移观点，有必要保留一些东西，否则不一致会变得很明显。 另外，根据我们跟踪的质量和物体的形状，由于累积的误差，我们会收到各种不良影响，而这种影响仍然存在。 它只是需要以某种方式加以考虑。 在上面展示的视频中，我想展示增强现实的使用范围可以不仅仅限于在图像上添加虚拟对象。

顺便说一下， Vuforia SDK可以通过对象的形状来跟踪对象，尽管我认为不可能用该对象来实现该项目，因为不可能使用严​​格定义的边缘并且不能与建筑物的照明关联。