當(dāng)前位置：首頁 > 嵌入式培訓(xùn) > 嵌入式學(xué)習(xí) > 講師博文 > AprilTags論文解讀
AprilTags論文解讀
時(shí)間：2018-01-11 來源：未知
一、Apriltag是改進(jìn)的ARToolkit、 ARTag 。
1.1 ARToolkit的劣勢(shì)：
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.
主要意思是說：第一個(gè)劣勢(shì)每個(gè)模板都是獨(dú)立的所有校正操作非常的慢，第二個(gè)劣勢(shì)是說為每一個(gè)合適正交直線的圖像創(chuàng)建模板是非常的困難。
The tag detection scheme used by ARToolkit is based on a simple binarization of the input image based on a userspecified threshold.
這是因?yàn)樵趖ag獲取的時(shí)候只是通過用戶給定的一個(gè)閾值得到一個(gè)簡(jiǎn)單二值化圖像。
This scheme is very fast, but not robust to changes in illumination.
這種方法很快，但是在改變光強(qiáng)的時(shí)候就不實(shí)用。
In general, ARToolkit’s detections can not handle even modest occlusions of the tag’s border.
通常，ARToolkit也不能出來有適當(dāng)遮擋的標(biāo)簽邊緣。
1.2 ARTag 對(duì)ARToolkit的改進(jìn)：
the detection mechanism was based on the image gradient, making it robust to changes in lighting.
使用圖像的梯度來獲取tag，這樣讓他在光照的改變上更加的實(shí)用。
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 的詳細(xì)的獲取算法不公開，并且他可以獲取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 提供第一個(gè)向前糾錯(cuò)的解碼系統(tǒng)，這個(gè)讓tag容易產(chǎn)生，快速糾錯(cuò)，也提供更好的算法。
二、獲取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.
尋找場(chǎng)景中可能的tag圖像，即嘗試著尋找內(nèi)“黑”外“白”的四邊形，并且為了好識(shí)別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 的獲取方法，即計(jì)算tag的每一個(gè)像素點(diǎn)的梯度方向和幅值，并且把相同的梯度方向和幅值得像素集群到一個(gè)部件中。
2.3 之前的方法(Early processing steps)
First：The tag detection algorithm begins by computing the gradient at every pixel, computing their magnitudes (通過計(jì)算像素的梯度得到幅值圖像)。
Second：gradient direction(得到梯度方向)
Third：similar gradient directions and magnitude are clustered into components(相似的梯度方向和幅值集群到一個(gè)組件)
集群算法：
The clustering algorithm is similar to the graph-based method of Felzenszwalb : a graph is created in which each node represents a pixel.
使用類似于Felzenszwalb集群算法，每一個(gè)節(jié)點(diǎn)node來代表一個(gè)像素。
算法描述：
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.
邊緣被添加是通過臨近的不同的像素梯度方向的邊緣權(quán)重。這些邊緣在增長(zhǎng)邊緣權(quán)重方面被分類和處理：為了每個(gè)邊緣，測(cè)試像素屬于應(yīng)該被集群的像素是否連接組件。
算法問題：
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.
算法對(duì)于噪聲集群方法很敏感，甚至適當(dāng)?shù)脑肼晻?huì)導(dǎo)致局部梯度不同，約束部件增長(zhǎng)。解決方案的問題可以通過低通濾波。
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.
不像其他問題域，這個(gè)濾波會(huì)模糊一些有用的信息，tag的邊緣本質(zhì)上是一個(gè)很大的特征，所以濾波不會(huì)導(dǎo)致信息丟失，建議設(shè)置值為0.8。
Fourth：Using weighted least squares, a line segment is then fit to the pixels in each component.(使用加權(quán)小二乘法,一條線段就適合每個(gè)組件的像素。)
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.
線段的方向通過梯度的方向來決定，因此線段的左邊是暗部，右邊是亮部。線段的方向在線段的中部短的垂直槽口來直觀表示，注意這些槽口總是指向亮得區(qū)域。
2.4 獲取線段的總結(jié)
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.
分割算法是慢的在獲取方案中，作為一個(gè)選項(xiàng)，這種分割可以在一半的圖像分辨率提升了4倍的速度。二級(jí)抽樣操作推薦與低通濾波器結(jié)合能增加效率。有效的結(jié)果是適當(dāng)?shù)臏p少獲取范圍，因此非常小的四邊形不再被獲取。
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.
我們的方法是基于一個(gè)深度為4的遞歸深度優(yōu)先搜索算法：每一層搜索添加一個(gè)邊緣到四邊形。在第一層深度，考慮所有的線段。在第二層到第四層，考慮所有的線段從“完全閉合”之前線段結(jié)束的地方開始，并且服從一個(gè)逆時(shí)針纏繞順序。
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.
魯棒性遮擋和分割錯(cuò)誤處理通過調(diào)整“完全閉合”閾值：通過標(biāo)記大的閾值，大的間隙邊緣會(huì)被處理。我們閾值足夠近兩倍的長(zhǎng)度線加另外5個(gè)像素，這是一個(gè)大門檻導(dǎo)致負(fù)錯(cuò)誤率很低,但也導(dǎo)致較高正錯(cuò)誤率。
We populate a two-dimensional lookup table to accelerate queries for line segments that begin near a point in space.
填充一個(gè)二維查找表來加快查詢線段,開始在空間中的一個(gè)點(diǎn)。
三、算出tag距相機(jī)距離與角度
3.1 Homography and extrinsics estimation(單應(yīng)性和外在評(píng)估)
3.1.1 通過DLT得到單應(yīng)矩陣
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.
計(jì)算的3x3 單應(yīng)矩陣, 項(xiàng)目2D 點(diǎn)的均勻坐標(biāo)從標(biāo)簽的坐標(biāo)系 (在其中 [0 0 1] T 是在標(biāo)簽的中心和標(biāo)簽擴(kuò)展一個(gè)單位在 xˆ和 yˆ方向) 到2D 圖像坐標(biāo)系統(tǒng)。應(yīng)是使用直接線性變換 (DLT) 算法計(jì)算的。請(qǐng)注意，由于單應(yīng)項(xiàng)目是以齊次坐標(biāo)表示的, 所以它的定義只有按比例。
3.1.2 計(jì)算方法
Computation of the tag’s position and orientation requires additional information: the camera’s focal length and the physical size of the tag.
標(biāo)簽的位置和方向的計(jì)算需要附加信息:相機(jī)的焦距和標(biāo)簽的物理大小。
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 單應(yīng)矩陣 (由 DLT 計(jì)算) 可以寫成 3 x 4 相機(jī)投影矩陣 P (我們假設(shè)已知) 和 4 x 3 截?cái)鄀xtrinsics矩陣E的乘積。
截?cái)鄀xtrinsics矩陣 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, 但每個(gè)位置上的標(biāo)簽在標(biāo)記的坐標(biāo)系統(tǒng)中為 z = 0。因此, 我們可以將每個(gè)標(biāo)記坐標(biāo)重寫為一個(gè)具有 z 隱式零的2D 齊點(diǎn), 并移除 extrinsics 矩陣的第三列。
We represent the rotation components of P as Rijand thetranslation components as Tk. We also represent the unknownscale factor as s.
我們代表 P 的旋轉(zhuǎn)分量為 Rij和轉(zhuǎn)換組件作為 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。
請(qǐng)注意, 我們不能直接解決 E, 因?yàn)?P 是秩不足.我們可以擴(kuò)大右手邊的 Eqn 2,將每個(gè)hij的表達(dá)式寫為一組同等方程。
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。然而, 由于旋轉(zhuǎn)矩陣的列必須都是單位幅值，我們可以限制 s 的大小。我們有兩列的旋轉(zhuǎn)矩陣, 所以我們計(jì)算 s 為他們幅值的幾何平均值。標(biāo)記s可以重新獲得通過請(qǐng)求在相機(jī)前的tag。即Tz < 0。旋轉(zhuǎn)的第三列矩陣可以通過計(jì)算交叉乘積來恢復(fù)兩個(gè)已知列, 因?yàn)樾D(zhuǎn)的列矩陣必須是正交的。
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 程序與規(guī)范化程序以上不保證旋轉(zhuǎn)矩陣是嚴(yán)格正交.為了糾正這一點(diǎn), 我們計(jì)算 R 的極分解, 它產(chǎn)生一個(gè)適當(dāng)?shù)男D(zhuǎn)矩陣, 而小化誤差的 Frobenius 矩陣范數(shù)。
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.
后的任務(wù)是從有效負(fù)載字段中讀取位。我們通過計(jì)算每個(gè)位字段的tag相對(duì)坐標(biāo)系, 利用單應(yīng)性將它們轉(zhuǎn)換為圖像坐標(biāo), 然后對(duì)結(jié)果像素進(jìn)行閾值化。為了受光照影響小 (這不僅可以tag到tag, 而且也可以在一個(gè)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.
我們建立了 "黑色" 像素的強(qiáng)度的空間變化模型, 以及第二個(gè)模型的強(qiáng)度"白色" 模型。我們使用標(biāo)簽的邊框, 它包含白色和黑色像素的已知示例。
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.
在較大的一個(gè)有效載荷位的tag檢測(cè)到一個(gè)四個(gè)方形。這兩個(gè)外部檢測(cè)終被丟棄, 因?yàn)樗鼈兊挠行ж?fù)載無效。白點(diǎn)對(duì)應(yīng)于tag周圍的樣本用于擬合 "白" 像素強(qiáng)度線性模型的邊界;模型同樣適合黑色像素。這兩種模型用于閾值數(shù)據(jù)有效負(fù)載位, 顯示為黃色點(diǎn)。
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.
該模型有四參數(shù), 易于計(jì)算使用小二乘法回歸。我們建立了兩個(gè)這樣的模型一個(gè)是黑色的, 另一個(gè)是白色的。使用的閾值解碼數(shù)據(jù)位, 然后只是平均的預(yù)測(cè)黑白模型的強(qiáng)度值。
3.2.2 CODING SYSTEM (編碼系統(tǒng)，決定獲取的四邊形是否有效。)
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.
編碼系統(tǒng)的目標(biāo)是:
·大化可區(qū)分碼的數(shù)量
·大化可檢測(cè)或更正的位錯(cuò)誤數(shù)
·小的the false positive/inter-tag 混淆率
·小化每個(gè)tag的總位數(shù) (tag的大小)
這些目標(biāo)經(jīng)常處于沖突中, 因此給定的代碼表示權(quán)衡。
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.
我們描述了一個(gè)新基于 lexicodes 的編碼系統(tǒng), 提供了顯著優(yōu)于以前的方法。我們的程序可以生成具有多種屬性的 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.
我們使用一個(gè) lexicode 系統(tǒng), 可以生成任意標(biāo)記大小的碼 (例如, 3x3, 4x4, 5x5, 6x6)和小漢明距離。我們的方法明確保證小漢明距離為每個(gè)tag的4方向旋轉(zhuǎn)和消除標(biāo)簽低幾何復(fù)雜度。計(jì)算tag是昂貴的操作, 但離線完成。小標(biāo)簽 (5x5)可以很容易地以秒或分鐘計(jì)算, 但更大標(biāo)記 (6x6) 可能需要幾天的 CPU 時(shí)間。
