Apriltags
AprilTag是一套免费开源的视觉定位系统，他们的主页：https://april.eecs.umich.edu/software/apriltag/
根据他们的论文AprilTag - A robust and flexible visual fiducial system, ICRA 2011，AprilTag主要的贡献是：
- 提出了一种可靠的检测视觉基准的方法：基于图形的图像分割、基于局部梯度，可以精确估计线条。还描述了一种可以处理重要遮挡的四边形提取方法。
- 描述了2D条形码系统独有的特性：旋转的稳健性，以及自然图像产生的误报的稳健性。
- 号称比ARTag和Studierstube Tracker更快更稳定。
ARToolkit
ARToolkit的标签包含一个由黑色边框包围，没有用二进制编码，而是使用了诸如拉丁字符“A”之类的符号。主要缺点是计算成本，第二个缺点是难以生成彼此近似正交的模板。 ARToolkit使用的标签检测方案基于用户指定的阈值对输入图像进行简单的二值化。该方案非常快，但对于照明变化不稳健，而且无法处理标签边框的适度遮挡。
ARTag
ARTag是改进的方案，检测机制基于图像梯度，使其对光照变化具有鲁棒性，同时能够检测边界部分被遮挡的标签。ARTag还提供了基于前向纠错的第一个编码系统，使标签更容易生成，更快地相关，并提供标签之间更大的正交性。ARTag是挺有意义的一项工作，不过是不开源的。
Apriltags
参考了之前的工作，Apriltags由两个主要部分组成：标签检测器(detector) 和 编码系统(encode/decode)。
检测线段 Detecting line segments
首先检测图像中的线条。与ARTag探测器的基本方法类似，计算每个像素的梯度方向和幅度，并将像素聚集成具有相似梯度方向和幅度的分量。
首先计算每个像素的梯度，计算它们的幅度（图1）和方向（图2）。使用基于图的方法，具有相似梯度方向和幅度的像素被聚类成组件（图3）。使用加权最小值然后，将线段拟合到每个组件中的像素（图四）。
线段的方向由梯度方向确定，因此，左边是暗段，右边是浅。 线的方向通过其中点处的短垂直“凹口”可视化; 注意这些“缺口”总是指向较轻的区域。
聚类算法类似于Felzenszwalb的基于图的方法：
- 创建了一个图，其中每个节点代表一个像素。在相邻像素之间添加边缘，边缘权重等于像素在梯度方向上的差异。
- 然后根据增加的边缘权重对这些边缘进行分类和处理：
对于每个边缘，我们测试像素所属的连接分量是否应该连接在一起。给定分量n，我们将梯度方向的范围表示为$D(n)$，将幅度范围表示为$M(n)$。换句话说，$D(n)$和$M(n)$是标量值，分别表示梯度方向和幅度的最大值和最小值之间的差值。在$D()$的情况下，必须小心处理2π环绕。但是，由于有用边缘的跨度远小于π度，因此这很简单。给定$n$和$m$两个分量，如果满足以下两个条件，我们将它们连接在一起：$D()$和$M()$的小值表示具有很小的组件内变化的组件。如果它们的结合大致与单独采集的簇一样均匀，则两个簇连接在一起。通过$K_D$和$K_M$参数允许适度增加组件内变化，但随着组件变大，这会迅速缩小。在早期迭代期间，K参数基本上允许每个组件“学习”其簇内变化。在我们的实验中，我们使用$K_D = 100$和$K_M = 1200$，尽管该算法在很宽的范围内都能很好地工作。
出于性能原因，边缘权重被量化并存储为定点数。这允许使用线性时间计数排序对边进行排序。 unionfind算法可以有效地执行实际的合并操作，梯度方向和幅度的上限和下限存储在由每个组件的代表成员索引的简单数组中。
这种基于梯度的聚类方法对图像中的噪声敏感：
即使适量的噪声也会导致局部梯度方向变化，从而抑制组件的生长。解决这个问题的方法是对图像进行低通滤波。与此过滤可能会模糊图像中的有用信息的其他问题域不同，标记的边缘本质上是大规模的特征（特别是与数据字段相比），因此这种过滤不会导致信息丢失。我们建议值$σ= 0.8$。
聚类操作完成后，使用传统的最小二乘法将线段拟合到每个连接的组件，按梯度幅度对每个点进行加权。我们调整每个线段，使线的暗侧位于其左侧，而光侧位于其右侧。在下一个处理阶段，这允许我们围绕每个四边形强制执行绕线规则。
- 分割算法是我们检测方案中最慢的阶段。
作为一种选择，这种分割可以在图像分辨率的一半下执行，速度提高4倍。子采样操作可以与推荐的低通滤波器有效地组合。这种优化的结果是适度减小的检测范围，因为可能不再检测到非常小的四边形。
四元检测 Quad detection
在图像中检测到四个四边形（包含两个标签）。第三个检测到的四边形对应于前景标签的三个边缘加上纸张的边缘。 在较大标签的一个payload field位周围检测到第四个四边形。 这两个无关的检测最终被丢弃，因为它们的payload field无效。 白点对应于标签边界周围的样本，用于拟合“白色”像素强度的线性模型; 模型同样适合黑色像素。 这两个模型用于阈值数据有效负载位，如黄点所示。
此时，已经为图像计算了一组有向线段。下一个任务是找到形成4边形状的线段序列，即四边形。面临的挑战是尽可能地保持线段中的遮挡和噪声。我们的方法基于深度为4的递归深度优先搜索：
搜索树的每个级别为四边形添加边缘。在深度1处，我们考虑所有线段。在深度为2到4的情况下，我们认为所有的线段开始“足够接近”前一个线段结束的位置并且遵循逆时针缠绕顺序。通过调整“足够接近”阈值来处理遮挡和分割误差的稳健性：通过使阈值变大，可以处理边缘周围的显着间隙。
我们的“足够接近”的阈值是线的长度加上五个额外像素的两倍。这是一个较大的阈值，导致较低的假阴性率，但也导致较高的假阳性率。我们填充二维查找表以加速对在空间中的点附近开始的线段的查询。通过这种优化，以及不遵守绕组规则的候选四边形的早期拒绝，或者多次使用一个分段，四元检测算法代表总计算要求的一小部分。一旦找到四条线，就会创建一个候选四元检测。这个四边形的角是构成它的线的交叉点。因为使用来自许多像素的数据来拟合线，所以这些角估计精确到像素的一小部分。
单应性以及外估计 Homography and extrinsics estimation
我们计算3×3单应矩阵，它从标签的坐标系（其中$[\begin{matrix}0&0&1\end{matrix}]^T$位于标签的中心并且标签在x和y方向上延伸一个单位）在同构坐标中投影2D点到2D图像坐标系。使用直接线性变换（DLT）算法计算单应性。
由于单应性投影指向齐次坐标，因此仅按比例定义。计算标签的位置和方向需要额外的信息：相机的焦距和标签的物理尺寸。
3×3单应矩阵（由DLT计算）可以写成3×4相机投影矩阵P（我们假设已知）和4×3截断的外在矩阵E的乘积。外部矩阵通常是4× 4，但标签上的每个位置在标签的坐标系中都是z = 0。因此，我们可以将每个标记坐标重写为2D齐次点，其中z隐式为零，并删除外部矩阵的第三列，形成截断的外部矩阵。我们将P的旋转分量表示为$R_{ij}$，将平移分量表示为$T_k$。我们还将未知比例因子表示为s：
这里不能直接求解E，因为P是秩不足的。 我们可以扩展Eqn的右侧，并将每个$h_{ij}$的表达式写为一组联立方程：
除了未知的比例因子s之外，这些都可以很容易地解决$R_{ij}$和{T_k}的元素。但是，由于旋转矩阵的列必须都是单位幅度，我们可以约束s的幅度。我们有两列旋转矩阵，因此我们将s计算为几何平均值的几何平均值。s的符号可以通过要求标签出现在摄像机前面来恢复，即$T_z<0$。旋转矩阵的第三列可以通过计算两个已知列的叉积来恢复，因为旋转矩阵必须是正交的。上面的DLT过程和归一化过程不保证旋转矩阵严格地是正交的。为了纠正这个问题，我们计算了R的极分解，它产生了一个合适的旋转矩阵，同时最小化了误差的Frobenius矩阵范数(F范数：矩阵各项元素的绝对值平方的总和)。
解码 playload decoding
最后的任务是从payload field中读取位。我们通过计算每个位域的标签相对坐标，使用单应性将它们转换为图像坐标，然后对得到的像素进行阈值处理来完成此操作。为了对照明（不仅可以从标签到标签，也可以在标签内）变化，我们使用空间变化的阈值。
具体来说，我们建立了“黑色”像素强度的空间变化模型，以及“白色”模型强度的第二个模型。 我们使用标签的边框来包含白色和黑色像素的已知示例，以学习此模型。我们使用以下强度模型：
该模型具有四个参数，可以使用最小二乘回归轻松计算。 我们建造了两个这样的模型，一个用于黑色，另一个用于白色。 解码数据位时使用的阈值就是黑白模型的预测强度值的平均值。
关于编码 playload encoding
Apriltags描述了一个新基于 lexicodes 的编码系统, 提供了显著优于以前的方法。程序可以生成具有多种属性的 lexicodes, 允许用户使用符合其需要的代码。
我们建议使用修改的词典。经典词典由两个量参数化：每个码字中的比特数n和任何两个码字之间的最小汉明距离d。 Lexicodes可以纠正$⌊（d - 1）/2⌋$位错误并检测$d/2$位错误。为方便起见，我们将表示36位编码，最小汉明距离为10（例如）为36h10代码。
Lexicodes从用于生成有效码字的启发式中得出它们的名称：候选码字以字典顺序（从最小到最大）被考虑，当它们距离先前添加到码本的每个码字至少距离d时，将新码字添加到码本。
在视觉基准的情况下，编码方案必须对旋转是鲁棒的。换句话说，当标签旋转90度，180度或270度时，至关重要的是它仍然与其他所有代码的汉明距离为d。标准词典生成算法不保证此属性。但是，标准生成算法可以通过简单的扩展来支持这一点：在测试新的候选码字时，我们可以简单地确保所有四个旋转都具有所需的最小汉明距离。事实上，lexicode算法可以很容易地扩展到包含额外的约束，这是我们的方法的一个优点。
尽管满足汉明距离约束，一些码字是糟糕的选择。例如，由全零组成的代码字将导致看起来像单个黑色方块的标签。这种简单的几何图案通常出现在自然场景中，导致误报。例如，ARTag编码系统明确禁止两个代码，因为它们很可能偶然发生。我们不是手动识别有问题的标签，而是通过拒绝导致简单几何图案的候选码字来进一步修改词典生成算法。我们的度量标准基于生成标签2D图案所需的矩形数量。例如，实心图案只需要一个矩形，而黑白黑色条纹则需要两个矩形（一个大的黑色矩形，第二个是较小的白色矩形）。我们的假设，在本文后面的实验结果的支持下，具有高复杂性的标签模式（需要重建许多矩形）在自然界中发生的频率较低，因此导致较低的假阳性率。使用这个想法，我们再次修改词典生成算法以拒绝过于简单的候选码字。我们使用简单的贪婪方法来近似生成标签模式所需的矩形数量，该方法重复考虑所有可能的矩形并添加最能减少误差的矩形。由于标签通常非常小，因此该计算不是瓶颈。最小复杂度小于阈值的标签（在我们的实验中通常为10）被拒绝。结果部分演示了此启发式的适当性和有效性。
最后，我们通过对词典生成算法进行一次修改，凭经验观察到较低的假阳性分数。我们考虑（b，b + 1p，b + 2p，b + 3p，…）而不是按顺序（0,1,2,3 ……）测试码字，其中b是任意数，p是一个大的素数，每一步都保留最低的n位。直观地说，这种方法生成的标签在每个比特位置都有更大的熵;另一方面，词典顺序有利于小值代码。这种方法的缺点是可以创建更少的可区分代码：词典排序倾向于非常密集地打包码字，而更随机的顺序导致码字的打包效率较低。总而言之，我们使用一个词典系统，可以生成任意标签大小（例如，3x3,4x4,5x5,6x6）和最小汉明距离的代码。我们的方法明确保证每个标签的所有四个旋转的最小汉明距离，并消除几何复杂度低的标签。计算标签可能是一项昂贵的操作，但是可以离线完成。小标签（5x5）可以在几秒或几分钟内轻松计算，但较大的标签（6x6）可能需要几天的CPU时间。许多有用的代码系列已经使用我们的软件进行计算和分发;大多数用户不需要生成自己的代码系列。
纠错分析
可以容易地估计理论假阳性率。假设识别出错误的四边形并且位模式是随机的。误报的概率是被接受为有效标签的码字的分数与可能的码字的总数，2 n。更积极的纠错会增加此速率，因为它会增加接受的码字数量。下面的36h10和36h15代码说明了这种不可避免的错误率增加：
当然，36h15编码的更好性能是有代价的：只有27个可区分的代码字，而不是36h10的2221个可区分的代码字。
我们的编码方案明显强于以前的方案，包括ARTag使用的方案和ARToolkitPlus使用的两种系统：我们的编码系统在编码大量可区分的ID时实现了所有码字对之间更大的最小汉明距离。最小汉明距离的改进如上图和下表所示：
为了解码可能损坏的代码字，计算代码字和代码簿中的每个有效代码字之间的汉明距离。如果最佳匹配的汉明距离小于用户指定的阈值，则报告检测。通过指定该阈值，用户能够控制误报和误报之间的权衡。
这个方法的缺点是该解码过程花费了码本大小的线性时间，因为必须考虑每个有效的码字。
然而，该系数非常小，以至于与其他图像处理步骤相比，计算复杂度可以忽略不计。对于给定的编码方案，较大的标签（即，具有36位而不是25位的标签）具有比较小标签明显更好的编码性能，尽管这是有代价的。在所有其他条件相同的情况下，给定摄像机读取36位标签的范围将短于同一摄像机读取16或25位标签的范围。然而，由于边界的4像素开销，较小标签的范围的益处非常适中；通过使用16位标签而不是36位标签，可以预期检测范围仅提高25％。因此，仅在范围最敏感的应用中，较小的标签是有利的。