AprilTags論文解讀
時間：2018-01-11 來源：未知
一、Apriltag是改進的ARToolkit、 ARTag 。
1.1 ARToolkit的劣勢：
A major disadvantage of this approach is the computational cost associated with decoding tags, since each template required a separate, slow correlation operation. A second disadvantage is that it is difficult to generate templates that are approximately orthogonal to each other.
主要意思是說：第一個劣勢每個模板都是獨立的所有校正操作非常的慢，第二個劣勢是說為每一個合適正交直線的圖像創建模板是非常的困難。
The tag detection scheme used by ARToolkit is based on a simple binarization of the input image based on a userspecified threshold.
這是因為在tag獲取的時候只是通過用戶給定的一個閾值得到一個簡單二值化圖像。
This scheme is very fast, but not robust to changes in illumination.
這種方法很快，但是在改變光強的時候就不實用。
In general, ARToolkit’s detections can not handle even modest occlusions of the tag’s border.
通常，ARToolkit也不能出來有適當遮擋的標簽邊緣。
1.2 ARTag 對ARToolkit的改進：
the detection mechanism was based on the image gradient, making it robust to changes in lighting.
使用圖像的梯度來獲取tag，這樣讓他在光照的改變上更加的實用。
While the details of the detector algorithm are not public, ARTag’s detection mechanism is able to detect tags whose border is partially occluded.
ARTag 的詳細的獲取算法不公開，并且他可以獲取tag邊緣被部分閉塞。
ARTag also provided the first coding system based on forward error correction, which
made tags easier to generate, faster to correlate, and provided greater orthogonality between tags.
ARTag 提供第一個向前糾錯的解碼系統，這個讓tag容易產生，快速糾錯，也提供更好的算法。
二、獲取tags(Detector)
2.1 整體描述：
we describe the detector whose job is to estimate the position of possible tags in an image. Loosely speaking, the detector attempts to find four-sided regions (“quads”) that have a darker interior than their exterior. The tags themselves have black and white borders in order to facilitate this.
尋找場景中可能的tag圖像，即嘗試著尋找內“黑”外“白”的四邊形，并且為了好識別tag本身有黑白的邊緣特征。如下圖。
2.2 獲取線段(Detecting line segments )
Our approach begins by detecting lines in the image. Our approach, similar in basic approach to the ARTag detector, computes the gradient direction and magnitude at every pixel and agglomeratively clusters the pixels into components with similar gradient directions and magnitudes.
大概意思是說，類似于ARTag 的獲取方法，即計算tag的每一個像素點的梯度方向和幅值，并且把相同的梯度方向和幅值得像素集群到一個部件中。
2.3 之前的方法(Early processing steps)
First：The tag detection algorithm begins by computing the gradient at every pixel, computing their magnitudes (通過計算像素的梯度得到幅值圖像)。
Second：gradient direction(得到梯度方向)
Third：similar gradient directions and magnitude are clustered into components(相似的梯度方向和幅值集群到一個組件)
集群算法：
The clustering algorithm is similar to the graph-based method of Felzenszwalb : a graph is created in which each node represents a pixel.
使用類似于Felzenszwalb集群算法，每一個節點node來代表一個像素。
算法描述：
Edges are added between adjacent pixels with an edge weight equal to the pixels’ difference in gradient direction. These edges are then sorted and processed in terms of increasing edge weight: for each edge, we test whether the connected components that the pixels belong to should be joined together.
邊緣被添加是通過臨近的不同的像素梯度方向的邊緣權重。這些邊緣在增長邊緣權重方面被分類和處理：為了每個邊緣，測試像素屬于應該被集群的像素是否連接組件。
算法問題：
This gradient-based clustering method is sensitive to noise in the image: even modest amounts of noise will cause local gradient directions to vary, inhibiting the growth of the components. The solution to this problem is to low-pass filter the image.
算法對于噪聲集群方法很敏感，甚至適當的噪聲會導致局部梯度不同，約束部件增長。解決方案的問題可以通過低通濾波。
Unlike other problem domains where this filtering can blur useful information in the image, the edges of a tag are intrinsically large-scale features (particularly in comparison to the data field), and so this filtering does not cause information loss. We recommend a value of σ = 0.8.
不像其他問題域，這個濾波會模糊一些有用的信息，tag的邊緣本質上是一個很大的特征，所以濾波不會導致信息丟失，建議設置值為0.8。
Fourth：Using weighted least squares, a line segment is then fit to the pixels in each component.(使用加權小二乘法,一條線段就適合每個組件的像素。)
The direction of the line segment is determined by the gradient direction, so that segments are dark on the left, light on the right. The direction of the lines are visualized by short perpendicular “notches” at their midpoint; note that these “notches” always point towards the lighter region.
線段的方向通過梯度的方向來決定，因此線段的左邊是暗部，右邊是亮部。線段的方向在線段的中部短的垂直槽口來直觀表示，注意這些槽口總是指向亮得區域。
2.4 獲取線段的總結
The segmentation algorithm is the slowest phase in our detection scheme. As an option, this segmentation can be performed at half the image resolution with a 4x improvement in speed. The sub-sampling operation can be efficiently combined with the recommended low-pass filter. The consequence of this optimization is a modestly reduced detection range, since very small quads may no longer be detected.
分割算法是慢的在獲取方案中，作為一個選項，這種分割可以在一半的圖像分辨率提升了4倍的速度。二級抽樣操作推薦與低通濾波器結合能增加效率。有效的結果是適當的減少獲取范圍，因此非常小的四邊形不再被獲取。
2.5 四邊形獲取
Our approach is based on a recursive depth-first search with a depth of four: each level of the search tree adds an edge to the quad. At depth one, we consider all line segments. At depths two through four, we consider all of the line segments that begin “close enough” to where the previous line segment ended and which obey a counter-clockwise winding order.
我們的方法是基于一個深度為4的遞歸深度優先搜索算法：每一層搜索添加一個邊緣到四邊形。在第一層深度，考慮所有的線段。在第二層到第四層，考慮所有的線段從“完全閉合”之前線段結束的地方開始，并且服從一個逆時針纏繞順序。
Robustness to occlusions and segmentation errors is handled by adjusting the “close enough” threshold: by making the threshold large, significant gaps around the edges can be handled. Our threshold for “close enough” is twice the length of the line plus five additional pixels. This is a large threshold which leads to a low false negative rate, but also results in a high false positive rate.
魯棒性遮擋和分割錯誤處理通過調整“完全閉合”閾值：通過標記大的閾值，大的間隙邊緣會被處理。我們閾值足夠近兩倍的長度線加另外5個像素，這是一個大門檻導致負錯誤率很低,但也導致較高正錯誤率。
We populate a two-dimensional lookup table to accelerate queries for line segments that begin near a point in space.
填充一個二維查找表來加快查詢線段,開始在空間中的一個點。
三、算出tag距相機距離與角度
3.1 Homography and extrinsics estimation(單應性和外在評估)
3.1.1 通過DLT得到單應矩陣
We compute the 3×3 homography matrix that projects 2D points in homogeneous coordinates from the tag’s coordinate system (in which [0 0 1]T is at the center of the tag and the tag extends one unit in the xˆ and yˆdirections) to the 2D image coordinate system. The homography is computed using the Direct Linear Transform (DLT) algorithm. Note that since the homography projects points in homogeneous coordinates, it is defined only up to scale.
計算的3x3 單應矩陣, 項目2D 點的均勻坐標從標簽的坐標系 (在其中 [0 0 1] T 是在標簽的中心和標簽擴展一個單位在 xˆ和 yˆ方向) 到2D 圖像坐標系統。應是使用直接線性變換 (DLT) 算法計算的。請注意，由于單應項目是以齊次坐標表示的, 所以它的定義只有按比例。
3.1.2 計算方法
Computation of the tag’s position and orientation requires additional information: the camera’s focal length and the physical size of the tag.
標簽的位置和方向的計算需要附加信息:相機的焦距和標簽的物理大小。
The 3 × 3 homography matrix (computed by the DLT) can be written as the product of the 3 × 4 camera projection matrix P (which we assume is known) and the 4 × 3 truncated extrinsics matrix E.
3 x 3 單應矩陣 (由 DLT 計算) 可以寫成 3 x 4 相機投影矩陣 P (我們假設已知) 和 4 x 3 截斷extrinsics矩陣E的乘積。
截斷extrinsics矩陣 E：
extrinsics matrix are typically 4 × 4, but every position on the tag
is at z = 0 in the tag’s coordinate system. Thus, we can rewrite every tag coordinate as a 2D homogeneous point with z implicitly zero, and remove the third column of the extrinsics matrix, forming the truncated extrinsics matrix.
extrinsics 矩陣通常是 4 x 4, 但每個位置上的標簽在標記的坐標系統中為 z = 0。因此, 我們可以將每個標記坐標重寫為一個具有 z 隱式零的2D 齊點, 并移除 extrinsics 矩陣的第三列。
We represent the rotation components of P as Rijand thetranslation components as Tk. We also represent the unknownscale factor as s.
我們代表 P 的旋轉分量為 Rij和轉換組件作為 Tk。我們也代表未知比例因子為s。
Note that we cannot directly solve for E because P is rankdeficient. We can expand the right hand side of Eqn. 2, andwrite the expression for each hij as a set of simultaneousequations。
請注意, 我們不能直接解決 E, 因為 P 是秩不足.我們可以擴大右手邊的 Eqn 2,將每個hij的表達式寫為一組同等方程。
These are all easily solved for the elements of Rij and Tkexcept for the unknown scale factor s. However, since thecolumns of a rotation matrix must all be of unit magnitude,we can constrain the magnitude of s. We have two columnsof the rotation matrix, so we compute s as the geometric the
geometric average of their magnitudes. The sign of s canbe recovered by requiring that the tag appear in front of thecamera, i.e., that Tz < 0. The third column of the rotationmatrix can be recovered by computing the cross product ofthe two known columns, since the columns of a rotation
matrix must be orthonormal.
這些都很容易解決的 Rij 和 Tk 的元素，除了未知的比例因子 s。然而, 由于旋轉矩陣的列必須都是單位幅值，我們可以限制 s 的大小。我們有兩列的旋轉矩陣, 所以我們計算 s 為他們幅值的幾何平均值。標記s可以重新獲得通過請求在相機前的tag。即Tz < 0。旋轉的第三列矩陣可以通過計算交叉乘積來恢復兩個已知列, 因為旋轉的列矩陣必須是正交的。
The DLT procedure and the normalization procedureabove do not guarantee that the rotation matrix is strictlyorthonormal. To correct this, we compute the polar decomposition of R, which yields a proper rotation matrix whileminimizing the Frobenius matrix norm of the error.
DLT 程序與規范化程序以上不保證旋轉矩陣是嚴格正交.為了糾正這一點, 我們計算 R 的極分解, 它產生一個適當的旋轉矩陣, 而小化誤差的 Frobenius 矩陣范數。
3.2PAYLOAD DECODING (有效載荷解碼)
3.2.1 整體概述
The final task is to read the bits from the payload field.We do this bycomputing the tag-relative coordinates of eachbit field, transforming them into image coordinates using thehomography, and then thresholding the resulting pixels. Inorder to be robust to lighting (which can vary not only fromtag to tag, but also within a tag), we use a spatially-varyingthreshold.
后的任務是從有效負載字段中讀取位。我們通過計算每個位字段的tag相對坐標系, 利用單應性將它們轉換為圖像坐標, 然后對結果像素進行閾值化。為了受光照影響小 (這不僅可以tag到tag, 而且也可以在一個tag), 我們使用空間變化閾。
we build spatially-varying model of the intensity of “black” pixels, and a second model for the intensity of“white” models. We use the border of the tag, which contains known examples of both white and black pixels.
我們建立了 "黑色" 像素的強度的空間變化模型, 以及第二個模型的強度"白色" 模型。我們使用標簽的邊框, 它包含白色和黑色像素的已知示例。
A fourth quad is detected around one of the payload bits of the larger
tag. These two extraneous detections are eventually discarded because their payload is invalid. The white dots correspond to samples around the tags border which are used to fit a linear model of intensity of “white” pixels; a model is similarly fit for the black pixels. These two models are used to threshold the data payload bits, shown as yellow dots.
在較大的一個有效載荷位的tag檢測到一個四個方形。這兩個外部檢測終被丟棄, 因為它們的有效負載無效。白點對應于tag周圍的樣本用于擬合 "白" 像素強度線性模型的邊界;模型同樣適合黑色像素。這兩種模型用于閾值數據有效負載位, 顯示為黃色點。
This model has four parameters which are easily computedusing least squares regression. We build two such models,one for black, the other for white. The threshold used whendecoding data bits is then just the average of the predictedintensity values of the black and white models.
該模型有四參數, 易于計算使用小二乘法回歸。我們建立了兩個這樣的模型一個是黑色的, 另一個是白色的。使用的閾值解碼數據位, 然后只是平均的預測黑白模型的強度值。
3.2.2 CODING SYSTEM (編碼系統，決定獲取的四邊形是否有效。)
Thegoals of a coding system are to:
• Maximize the number of distinguishable codes
• Maximize the number of bit errors that can be detectedor corrected
• Minimize the false positive/inter-tag confusion rate
• Minimize the total number of bits per tag (and thus thesize of the tag)
These goals are often in conflict, and so a given coderepresents atrade-off.
編碼系統的目標是:
·大化可區分碼的數量
·大化可檢測或更正的位錯誤數
·小的the false positive/inter-tag 混淆率
·小化每個tag的總位數 (tag的大小)
這些目標經常處于沖突中, 因此給定的代碼表示權衡。
we describe a newcoding system based on lexicodes that provides significantadvantages over previous methods. Our procedure can generate lexicodes with a variety of properties, allowing the userto use a code that best fits their needs.
我們描述了一個新基于 lexicodes 的編碼系統, 提供了顯著優于以前的方法。我們的程序可以生成具有多種屬性的 lexicodes, 允許用戶使用符合其需要的代碼。
we use a lexicode system that can generatecodes for any arbitrary tag size (e.g., 3x3, 4x4, 5x5, 6x6)and minimum Hamming distance. Ourapproach explicitlyguarantees the minimum Hamming distance for all four
rotations of each tag and eliminates tags which are oflow geometriccomplexity. Computing the tags can be anexpensive operation, but is done offline. Small tags (5x5)can be easily computed in seconds or minutes, but largertags (6x6) can take several days of CPU time.
我們使用一個 lexicode 系統, 可以生成任意標記大小的碼 (例如, 3x3, 4x4, 5x5, 6x6)和小漢明距離。我們的方法明確保證小漢明距離為每個tag的4方向旋轉和消除標簽低幾何復雜度。計算tag是昂貴的操作, 但離線完成。小標簽 (5x5)可以很容易地以秒或分鐘計算, 但更大標記 (6x6) 可能需要幾天的 CPU 時間。
