Microntracker 双目视觉定位仪 Microntracker 医疗手术导航仪 ClaroNav 加拿大

architecture

基于X-Triplet标记的Robust 3D物体跟踪：一种基于机器学习的方法

https://doi.org/10.1016/j.cjme.2025.100068 Get rights and content

Under a Creative Commons license

Open access

Abstract

Object tracking in 3D space is a classical problem in computer vision. In this paper, an efficient and robust X-Triplet detection method is proposed based on the support vector machine (SVM) and an adjacent matrix for locating and tracking objects through stereo vision with minimal feature points. The X-Triplet, denoted as Tri-X, is a composite marker consisting of three sequential X-corners. The definition and types of Tri-X markers are introduced at first. Then a fast and robust X-corner detector based on the block search strategy and SVM is proposed to extract X-corner candidates with sub-pixel locations and orientations. Thereafter the X-corner adjacent matrix (XAM) is constructed using the orientation angle error to describe the possibility that any X-corner pair form a valid edge vector. The Tri-X candidates are then extracted efficiently from the XAM. Finally once the Tri-X markers are detected in binocular images, their 6D pose information can be recovered through stereo matching and triangulation technique. When multiple targets are involved simultaneously, different Tri-X markers can be utilized to identify different objects. Experimental results show that the proposed method outperformed the state-of-the-art in terms of both accuracy and efficiency for Tri-X marker detection. In localization precision test, it achieved 0.1 mm error for the position and 1° error for the orientation. Our method exhibits great potential for utilization in user-defined specific tracking tasks, offering flexibility and adaptability to various tracking requirements, especially multi-tool tracking in medical robotics.

Keywords

Object tracking

Localization

Tri-X composite marker

Support vector machine

X-corner adjacent matrix

1. Introduction

Stereo vision has been widely applied in robot localization [1], [2], medical robotics-assisted surgery [3], [4] and augmented reality [5], [6]. In stereo vision, at least three non-collinear feature points are required [7] to determine the location and attitude of a space object. Collaborative or artificial feature points [8] are generally preferred over natural feature points due to their ease of detectability and stability. For example, for tracking surgical instruments during surgery, the NDI POLARIS optical tracking system [9] groups three or four active IR LEDs or passive IR balls into a template marker, while the MicronTracker optical tracking system [10] leverages a template marker consists of three or more X-corners for tracking. When multiple objects are involved, different template markers can be utilized. Then not only must these feature points be detected, but their association with specific objects and their order must also be determined.

Various artificial markers have been proposed for ease of detectability [11], [12], [13], [14], such as L‐type, arrow-type, dot-array, ArUco and chessboard markers. For example, Spinczyk et al. used a chessboard to track respiration motion [15]. Wang et al. utilized a dot-array marker to track forceps during minimally invasive surgery (MIS) in stereo laparoscopy [16]. Among these markers, X-corner point is widely adopted for camera calibration [17], [18], [19] and tracking of robots and surgical instruments [20], [21] due to its distinctive features and flexibility.

Numerous algorithms have been proposed for the detection of X-corner arrays, including chessboards, as well as individual X-corners. The chessboard pattern, being widely recognized, is commonly used in camera calibration methods, such as Zhang’s method [22]. Several research studies have specifically focused on the detection of chessboard patterns [23], [24]. Universal feature detectors, such as Harris [25], [26], [27], [28] and FAST [29], can be employed to detect X-corners, while a large number of outliers may be detected simultaneously. Several specialized X-corner detectors utilize symmetry and thus have better performance, including SV [30], Hessian-X [18], [31], [32], ChESS [33], HT-based detector [34], gradient-based detector [35], SC-X [36], segment test [37], and SVM-based detector [38]. However, since these approaches are all based on pixel-by-pixel search strategies, their speed is limited. To accelerate the search efficiency, a block-by-block based method called Block-X was proposed in Ref. [39], but it is unable to filter out certain false X-corners. Most of the above methods first extract X-corner candidates and then rely on hand-crafted thresholds to filter out outliers, which is not robust to noise and has limited generalization ability under different scales, camera poses and illumination conditions. As an alternative, we propose a machine learning based method to filter out false X-corners with high confidence. Most related to our work, Wang et al. [38] utilized SVM for X-corner detection, but they suffered from low speed and precision. Gieseler et al. [40] treated X-corner detection as an object detection task and employed CNN for detection, but it could not achieve real-time performance without a high-quality GPU.

The X-corner contains both position and orientation information. Hessian-X [18] leverages the eigenvector directions of the Hessian matrix for orientation but it is susceptible to noise. On the other hand, SC-X [36] and Block-X [39] utilize the edge direction as the orientation and are more stable. Although the orientation information of X-corners is considered in Hessian-X [18], SC-X [36] and Block-X [39], its utilization has not been discussed. While in our approach, the orientation information represented by the edge direction is obtained and explicitly utilized to extract Tri-X candidates in 2D image space.

In this study, in order to track the object pose efficiently and robustly with minimal feature points, X-Triplet (Tri-X) composite marker and its corresponding detection and recognition methods are proposed. A Tri-X composite marker is composed of triple X-corners under some combination rules, which can vary in type and side-length (the distance between adjacent X-corners). We have addressed some issues in our previous study [41], but the speed and accuracy were low due to the adoption of the Hessian matrix in Hessian-X [18]. Hence, based on our previous research, the SC-X [36] and Block-X [39], a faster and more robust X-corner detection method based on the block search strategy and support vector machine (SVM) is proposed. Compared to existing methods that adopt hand-crafted thresholds to filter out false X-corners, our machine learning based approach is more robust to noise, different scales, camera poses and illumination conditions. Thanks to the block search strategy, the proposed method can be applied to detect X-corners at a fast speed. Furthermore, an X-corner adjacent matrix (XAM) is constructed using both position and orientation information to determine whether an X-corner pair can form a valid edge vector. Next, Tri-X candidates are efficiently extracted from the XAM. We demonstrate that compared to MicronTracker [3], which projects X-corners into 3D space before circularly groups them to search for potential markers using template matching, our method is able to extract Tri-X candidates in 2D image space thanks to the usage of orientation information. Finally, the Tri-X markers extracted from binocular images are matched to recover their 6D pose information. When multiple targets are involved simultaneously, various Tri-X markers with different marker types and side-lengths can be utilized to identify them.

The major contributions of this study are as follows:

(1) The combination rule and characteristics of a Tri-X marker are introduced for stereo vision to track objects with minimal feature points. Tri-X markers can be changed to track and identify multiple objects.

(2) A robust and fast X-corner detector is proposed based on the block search strategy and SVM, which can extract X-corner candidates efficiently. Meanwhile, the sub-pixel position and edge orientation of X-corners are acquired too.

(3) An X-corner adjacent matrix (XAM) is constructed to describe the boundary line collinearity between X-corners, which can be used as basis for fast Tri-X markers extraction.

(4) An efficient Tri-X detection method is proposed based on the aforementioned X-corner detector and XAM, which establish the foundation for rapid tracking of multiple objects in 3D space.

2. Method

2.1. Definition of Tri-X marker

For an X-corner shown in Fig. 1(a), its two orthogonal boundary lines can be denoted as

l_{BW}

and as

l_{WB}

, where BW (Black-to-White) or WB (White-to-Black) are gray change according to its gray leap sequence anticlockwise around the X-corner point. Obviously, X-corner is the intersection of

l_{BW}

and

l_{WB}

. Suppose there are two coplanar X-corners

X_{i} (i = 1, 2)

, when

l_{BW}^{(1)}

is collinear with

l_{WB}^{(2)}

, they form an edge vector

\vec{X_{1} X_{2}}

, as shown in Fig. 1(b). Note that if

l_{BW}^{(2)}

is collinear with

l_{WB}^{(1)}

, then the edge vector becomes

\vec{X_{2} X_{1}}

A X-Triplet composite marker, abbreviated as Tri-X, comprises three X-corners arranged sequentially on a plane, which form two edge vectors connected at the beginning and end, as shown in Fig. 2. Normally the two edge vectors are arranged orthogonal. Let

\vec{X_{1} X_{2}}

be the first edge vector, and

\vec{X_{2} X_{3}}

be the second edge vector, note that X2 is endpoint of

\vec{X_{1} X_{2}}

while the starting point of

\vec{X_{2} X_{3}}

According to the definition, there are only two types of Tri-X markers, as shown in Fig. 2. The type of a Tri-X marker is determined by the direction of the cross product of

\vec{X_{1} X_{2}}

and

\vec{X_{2} X_{3}}

, following the right-hand rule. If the direction of

\vec{X_{1} X_{2}} \times \vec{X_{2} X_{3}}

points inward the plane, then it is defined as B-type; otherwise it is W-type. The type can be understood in another way: if the gray of the pixels along segment

X_{1} X_{3}

are always white, then it is W-type; or else B-type. Despite only two types of Tri-X markers defined, various Tri-X markers can be created by changing the marker type and lengths of

|\vec{X_{1} X_{2}}|

and

|\vec{X_{2} X_{3}}|

2.2. Frame workflow

The workflow of our proposed method is illustrated in Fig. 3. Firstly, X-corners are extracted from each image of the binocular system, including their position and orientation, using a block search strategy and SVM filter. Then, an X-corner adjacent matrix is constructed to identify the Tri-X markers. Finally, the Tri-X markers in the left and right images are matched, and their spatial 6D pose information is recovered.

2.3. SVM-based X-corner detection

The detection of X-corners forms the foundation for Tri-X detection. In our previous work [39], we proposed a block-by-block search strategy for the fast extraction of X-candidates. Outliers are then filtered out utilizing simple threshold constraints, such as centrosymmetry, minimum step distance, and minimum intensity variance around the X-corner neighbor. Despite the high speed of this approach, the utilization of hand-crafted thresholds makes it vulnerable to noise and results in unsatisfactory performance in practical scenarios with different scales, camera poses, and illumination conditions. To address this issue, we propose an SVM classifier as an alternative outlier filter, which can effectively remove outliers with high confidence while maintaining high speed.

2.3.1. X-corner candidate selection

The same technique as Block-X [39] is employed to select X-corner candidates, in which a

(2 r + 1) \times (2 r + 1)

square sample window moves along the image from top-left every r pixels to determine whether there are four steps in the sampling ring. As depicted in Fig. 4, if there are four steps in the sampling ring, which are denoted as A, B, C and D, then the crossing point of line AC and line BD is selected as an X-corner candidate. To ensure that no possible X-corner candidates are missed while maintaining high speed, the moving step is set to half the side length of the sampling window (r).

2.3.2. Outlier filter with SVM classifier

Block-X [39] adopts a four-step principle to extract X-corner proposals, followed by the application of geometric and grayscale constraints to filter out negative samples. These constraints were designed to eliminate the most common negative case, namely a striped patch. However, they are incapable of filtering two additional types of negative cases, namely the blurred striped patch and the two-headed patch, as shown in Fig. 5.

Traditional techniques that rely on hand-crafted thresholds tend to be unstable across various scenarios, because of its inability to process the unconsidered condition as shown in Fig. 5. In contrast, machine learning based methods are more stable and robust, because they are able to learn various situation as long as the training data include the correspond samples. Therefore, we utilize an SVM classifier with an RBF kernel to filter out fake X-corner candidates. Support Vector Machine (SVM) is a supervised learning algorithm that finds the optimal hyperplane to separate data points of different classes with the maximum margin. The Radial Basis Function (RBF) kernel is widely used in SVM for non-linear classification.

To effectively train the SVM classifier, distinguishing features are required as input. We resample a

(2 r + 1) \times (2 r + 1)

window centered at the obtained candidate points and extract the features of each window for classification using the trained SVM classifier. The feature of each window is represented by a 12-dimensional vector that reflects the gray feature of the window. This 12-dimensional feature is extracted as shown in Fig. 6. Pixels A, B, C, and D represent the four steps of the window, with lines AC and BD serving to divide the window into four parts. We calculate the mean and variance of the gray intensity for each part as the global descriptor of the window, resulting in an 8-dimensional vector. If the current patch is an X-corner patch, each of the four parts should be either white or black. Therefore, the mean gray intensity of each part should be either high or low, with near-zero variance. Midpoints of segments AB, BC, CD, and DA are then calculated, and the mean gray intensity of the 3 × 3 neighborhood pixels of each is obtained. The resulting 4-dimensional vector is regarded as the local descriptor of the window. Finally, we concatenate the global and local descriptors to form the overall descriptor, which is a 12-dimensional feature vector.

For the bad case in Fig. 5, the variance of the gray intensity for each of the four parts separated by lines AC and BD will be significantly large, resulting in easy distinguishability.

We feed the feature vector into the trained SVM to classify whether the window is an X-corner window. Experiments demonstrate that this feature vector is exceptionally effective in filtering out all types of negative cases, while maintaining a high recall rate.

2.3.3. X-corner position and orientation refinement

Suppose

A^{'}

B^{'}

C^{'}

and

D^{'}

are the sub-pixel positions of the four steps A, B, C and D, which can be determined using a quadratic curve fitting method, then the sub-pixel position of the X-corner can be refined by:

{\tilde{x}}_{sub} = {\tilde{l}}_{\bar{A^{'} C^{'}}} \times {\tilde{l}}_{\bar{B^{'} D^{'}}},

where

\tilde{*}

is the homogeneous coordinate of variable

*

{\tilde{l}}_{\overset{̅}{A^{'} C^{'}}}

is the line determined by

A^{'}

and

C^{'}

, and

{\tilde{l}}_{\overset{̅}{B^{'} D^{'}}}

is the line determined by

B^{'}

and

D^{'}

. Here,

{\tilde{l}}_{\overset{̅}{A^{'} C^{'}}}

and

{\tilde{l}}_{\overset{̅}{B^{'} D^{'}}}

are included to represent the orientation information of the X-corner, which is equivalent to

l_{BW}

l_{WB}

in Fig. 1.

2.4. Adjacent matrix construction

The sub-pixel position information and the orientation information of X-corners have been obtained so far, then an adjacent matrix is constructed to describe the possibility that any two X-corners can form a valid edge vector. As shown in Fig. 1, the edge vector

\vec{X_{1} X_{2}}

formed by the two X-corners are perfectly coincident with the

l_{BW}^{(1)}

and

l_{WB}^{(2)}

in ideal circumstance. However, in practice, the collinearity cannot be strictly satisfied due to noise and errors, as shown in Fig. 7.

Therefore, in order to estimate the possibility that two X-corners,

X_{i}

and

X_{j}

, can form a valid edge vector

\vec{X_{i} X_{j}}

, the maximum angle error is adopted as the score:

ε_{ij} = \max (θ_{1}, θ_{2}),

where

θ_{1}

is the angle between lines

l_{BW}^{(i)}

and

l_{X_{i} X_{j}}

, and

θ_{2}

is the angle between lines

l_{WB}^{(j)}

and

l_{X_{i} X_{j}}

l_{X_{i} X_{j}}

is the line determined by

X_{i}

and

X_{j}

. Ideally,

ε_{ij}

should be zero; therefore, the lower the value of

ε_{ij}

, the more possible is

\vec{X_{i} X_{j}}

a valid edge vector.

The angle

θ

between any two lines

l_{1}

and

l_{2}

is computed as

\cos θ_{\hat{l_{1}, l_{2}}} = \frac{l_{1}^{T} C_{\infty}^{*} l_{2}}{\sqrt{l_{1}^{T} C_{\infty}^{*} l_{1}} ∙ \sqrt{l_{2}^{T} C_{\infty}^{*} l_{2}}},

where

C_{\infty}^{*}

is the quadratic form of the duality of the circle points.

Then the adjacent matrix

A_{N \times N}

can be expressed as

A = [\begin{matrix} ε_{11} & \dots & ε_{1 j} & \dots & ε_{1 N} \\ ⋮ & ⋱ & ⋮ & ⋱ & ⋮ \\ ε_{i 1} & \dots & ε_{ij} & \dots & ε_{iN} \\ ⋮ & ⋱ & ⋮ & ⋱ & ⋮ \\ ε_{N 1} & \dots & ε_{Nj} & \dots & ε_{NN} \end{matrix}],

where

ε_{ij} (i \neq j)

is the error of

X_{i}

and

X_{j}

forming edge vector

\vec{X_{i} X_{j}}

, which is determined by both their position and orientation information, and

ε_{ii}

is set to

π

2.5. Tri-X marker candidate extraction

Once the X-corner adjacent matrix

A_{N \times N}

has been constructed utilizing both position and orientation information, Tri-X candidates can be extracted in 2D image space. This approach differs from that of MicronTracker [10], which sorely relies on position information to project X-corners into 3D space before circularly grouping them to search for potential markers using template matching.

To extract the Tri-X marker, a threshold

θ_{Th}

should be set, which limits the collinearity error of the valid edge vector. For any X-corner

X_{i}

, if

X_{j}

is its next X-corner, that is,

\vec{X_{i} X_{j}}

is a valid edge vector,

A_{ij}

should be less than

θ_{Th}

X_{j}

can be determined by searching the ith row in

A_{N \times N}

. After finding

X_{j}

, the next

X_{k}

can be determined by similarly searching the jth row in

A_{N \times N}

. Thus,

X_{i}

X_{j}

and

X_{k}

is the first, second and third X-corner in the Tri-X marker respectively, and the type of the Tri-X marker can be obtained according to the direction of the cross product of

\vec{X_{i} X_{j}}

and

\vec{X_{j} X_{k}}

In practical,

A_{ij} + A_{jk}

can be considered as the error of

X_{i}

X_{j}

and

X_{k}

forming a Tri-X marker. First, we conduct a search for all possible combinations of Tri-X candidate markers, denoted as set

\{S\}

, using the adjacent matrix. It is important to note that an X-corner may be present in multiple combinations within set

\{S\}

. Next, we sort the combination set

\{S\}

based on the magnitude of the error. Finally, we iteratively select the combination with the smallest error and add it to the final result set

\{R\}

, while excluding combinations from set

\{S\}

that have overlapping X-corners with the selected combination to ensure the uniqueness of X-corners in the final result.

Additionally, the expected number of Tri-X markers “K” can be set based on prior knowledge of the objects or devices that require localization or tracking. In such a scenario, the “K” Tri-X markers with the smallest error can then be selected as the final result.

2.6. Pose Estimation and Recognition

In general, projective transformation does not alter the marker type or the order of the three X-corners. Therefore, in a binocular vision image, the matched Tri-X markers should have the same marker type and X-corner order.

Hence, suppose there are M Tri-X composite markers in the left-eye image

I_{l}

, denoted by

{\{TriX\}}_{M}^{l}

, and N Tri-X composite markers in the right-eye image

I_{r}

, denoted by

{\{TriX\}}_{N}^{r}

, M and N may not be equivalent because the filed of view (FOV) of the two cameras are different.

This problem exists for any Tri-X composite marker

t_{m}^{(l)} \in {\{TriX\}}_{M}^{l} (m = 1, \dots, M)

, for which

t_{n}^{(r)} \in {\{TriX\}}_{N}^{r} (n = 1, \dots, N)

is the corresponding Tri-X composite marker, or vice-versa. Theoretically, if

t_{m}^{(l)}

and

t_{n}^{(r)}

are a correct stereo-match, the following conditions should be satisfied:

\{\begin{matrix} Type (t_{m}^{(l)}) = Type (t_{n}^{(r)}), \\ {\tilde{X}}_{i}^{t_{m}^{(l)}} F {\tilde{X}}_{i}^{t_{n}^{(r)}} = 0, i = 1, 2, 3, \end{matrix}

where

Type (t)

is the marker type of t, and F is the fundamental matrix between the two cameras of the stereo vision system.

After stereo-matching, the 3D positions of the three X-corners,

X_{1}

X_{2}

and

X_{3}

in the Tri-X composite marker can be recovered through triangulation. Let

X_{2}

be the origin of the local coordinate system,

\vec{X} = \vec{X_{2} X_{1}}

and

\vec{Y} = \vec{X_{2} X_{3}}

. Then, the Z-axis can be determined as

\vec{Z} = \vec{X} \times \vec{Y}

. Therefore, the pose of the Tri-X marker can be determined.

Recognizing multiple Tri-X composite markers becomes easier when they have different types or sizes. Prior knowledge of the Tri-X composite markers is necessary for recognition, which can be obtained by registering their information in a database

{\{TriX\}}^{*}

. The detected Tri-X marker can be recognized by comparing differences in marker type and side-length, as follows:

\min_{i} ||X_{1} X_{2}| - |X_{1}^{i} X_{2}^{i}|| + ||X_{2} X_{3}| - |X_{2}^{i} X_{3}^{i}||, i \in {\{TriX\}}^{*} .

3. Experiment and analysis

The proposed method was implemented with VS2019 and OpenCV 4.7.0 on a computer equipped with an 12th Gen Intel(R) Core(TM) i7‐12700 processor, 16 GB of RAM and Windows 11. Subsequently, the viability and effectiveness of the method were validated.

A binocular camera ZED2i was employed as the stereovision system, whose image resolution is 4416 × 1242 pixels, with 12 cm baseline distance and 2.1 mm focal lens.

3.1. X-detection experiment

The performance of X-corner detection was initially evaluated as it serves as the foundation of the entire process and directly influences the Tri-X detection performance. Experimental results demonstrated our method exhibits real-time X-corner detection with high precision and recall.

3.1.1. SVM training

A total of 107 binocular images of a chessboard were captured under different scenarios, which were then divided into left and right parts. Initially, the X-corner candidates were extracted using the block search strategy and four-step constraint. Subsequently, we computed the 12-dimensional feature vector for each candidate, which served as its distinguishing features and were utilized as input for the SVM. Additionally, the chessboard corners of each image were detected utilizing OpenCV library.

To establish the training set, we considered a candidate corner as a positive example if it was in close proximity to any of the chessboard corners. Conversely, if a candidate corner did not meet this criterion, it was classified as a negative example. The training set comprised a total of 18525 positive examples and 3192 negative examples.

Similarly, the test set was generated with 30 images. However, additional negative examples were added by including images without X-corners, which aimed to evaluate the robustness of our method.

The SVM classifier with an RBF kernel was trained using our training set, where the hyperparameters of SVM are set empirically as C= 100 and γ= 10 based on the experimental results. On our training set, it took less than 1 min to train the SVM classifier. The trained SVM classifier achieved an accuracy of 99.64 % on the training set, as well as a very close accuracy of 99.55 % on the test set. These results showed the efficacy of the crafted feature vector in accurately differentiating X-corners from various types of negative examples.

3.1.2. Detection performance under different parameters

The parameter “r”, which is equal to half the sampling window size, plays a crucial role in X-corner detection. Fig. 8 illustrates the precision, recall, F1-score and time required by our proposed X-detection method under different values of “r”, ranging from 3 to 20. Notably, the curves demonstrates that the highest precision, recall and F1-score on our test set are achieved when “r” equals to 12. It is observed that the average detection time per image, with a resolution of 2208 × 1242, remains below 25 ms when the “r” values exceeds 5. This implies that our method can effectively detect X-corners in real-time while maintaining high precision and recall.

To evaluate the performance of our algorithm across diverse scenarios, we captured images of a chessboard at varying distances and out-of-plane inclinations. For each scenario, we obtained 10 images and calculated the precision and recall. As shown in Table 1, the accuracy exhibits a gradual decrease as the distance (noted as L) and out-of-plane inclination angle (noted as R) increase. Specifically, when the out-of-plane rotation is less than 30°, the detection performance remains stable across different distance. However, a significant decline in recall is observed when the rotation exceeds 60°. Notably, when the distance reaches 1.5 m and out-of-plane rotation approaches 75°, there is a drastic degradation in performance, indicating that this is the boundary condition of our algorithm.

Table 1. Experiment with different distances and inclinations.

R (°)	L (m)
	0.5		1.0		1.5
	Precision	Recall	Precision	Recall	Precision	Recall
0	1.0000	0.9914	0.9979	0.9957	0.9971	0.9657
15	0.9986	0.9850	1.0000	0.9814	1.0000	0.9636
30	0.9938	0.9164	1.0000	0.9321	0.9992	0.9014
45	0.9884	0.9100	0.9931	0.9307	0.9973	0.8057
60	0.9930	0.9150	0.9902	0.7964	0.9946	0.7914
75	0.9983	0.8179	0.9943	0.7430	0.9955	0.6264

To evaluate the robustness of our method against noise, we conducted an experiment using images contaminated with Gaussian noise. In order to generate these images, we first normalized the gray values of the images in our test set to the range [0, 1] by dividing by 255. Next, we added Gaussian noise to each pixel in the images with a mean of zero and a standard deviation of

σ

. Finally, the images were multiplied by 255 and clipped to the range [0, 255]. We calculated the precision and recall under different noise levels, where the noise level is gradually increased by setting

σ

from 0 to 0.1 with a step size of 0.001. The results are presented in Fig. 9. It can be observed that even with moderate levels of noise, our method is able to maintain high precision and recall, demonstrating its robustness against noise.

Fig. 10 is an example of the X-corner detection result, in which all X-corners are detected. For each X-corner two red orthogonal lines are utilized to show its orientation and position which is the intersection of the two lines.

3.1.3. Comparison with SOTA methods

In order to demonstrate the superiority of our algorithm, we conducted a comparative evaluation against state-of-the-art methods using our test set. The evaluation considered precision, recall, F1-score and running time as performance metrics. The results presented in Table 2 clearly establish that our method outperforms all other methods by a significant margin, while maintaining real-time performance.

Table 2. Comparison with state-of-the-art methods.

Methods	Precision	Recall	F1-score	Time (ms)
Block-X [39]	0.8377	0.9825	0.9043	6.19
ChESS [33]	0.8991	0.9809	0.9382	53.85
Wang [38]	0.9817	0.9734	0.9772	56.95
Proposed	0.9965	0.9830	0.9897	9.13

Table 2 reveals that Block-X [39] stands out as the fastest method due to its utilization of the block search strategy to accelerate the search process, but it performs poorly on precision due to its heavy reliance on handcrafted thresholds to filter out outliers. On the other hand, ChESS [33] and Wang et al. [38] are pixel-wise methods that can maintain high accuracy but fail to achieve real-time performance. In comparison, our method takes advantage of the block search strategy to improve speed and incorporates machine learning techniques to enhance accuracy. As a result, our method substantially outperforms all other methods while still maintaining high speed.

3.2. Tri-X detection experiment

3.2.1. Tri-X detection performance

The parameter “

θ_{Th}

” which defines the maximum allowable angle error that two X-corners forming a valid edge vector, significantly impacts the performance of Tri-X detection. Fig. 11 illustrates the precision, recall, F1-score and time required of our proposed Tri-X detection method under different “

θ_{Th}

” values. It is evident that the recall is low when “

θ_{Th}

” is less than 5°. This occurrence can be attributed to the inability to strictly satisfy the collinearity between two X-corners forming a valid edge vector, owing to noise and errors. Benefiting from our robust search strategy based on the XAM, our method ensures high precision across various scenarios while maintaining stable performance when “

θ_{Th}

” exceeds 5°. However, as the value of “

θ_{Th}

” increases, the computational time also increases. This is because a larger “

θ_{Th}

” value leads to a higher number of false Tri-X combinations that need to be filtered out, resulting in longer processing time. Therefore, we suggest choosing a “

θ_{Th}

” value between 5° and 7°.

We captured images of the Tri-X markers at variant distances and angles, and applied our proposed method for marker detection. The resulting X-corner and corresponding Tri-X detection output is visualized in Fig. 12, where we utilize a sequential index starting from 1 to represent each Tri-X marker. Additionally, the W-type markers are highlighted in red, while the B-type markers are indicated in green.

We employed Block-X [39] for X-corner detection and subsequently utilized our proposed adjacent matrix to identify the Tri-X component, referred to as Block-X + . We conducted a comparison experiment between our method, Block-X + , and MTS [10], shown as Table 3. It can be observed that our method outperforms the other two methods in terms of recall, while maintaining a comparable level of precision to MTS. By employing a machine learning based approach instead of relying on handcrafted thresholds, our method enables more precise detection of X-corners. Consequently, the precision of our method surpasses that of Block-X + . The lower recall values for Block-X + and MTS can be attributed to the higher number of undetected X-corners compared to our method.

Table 3. Tri-X detection performance comparison.

Methods	Precision	Recall	F1-score
Block-X+	0.9337	0.8100	0.8655
MTS	1.0000	0.9012	0.9480
Proposed	0.9959	0.9125	0.9524

3.2.2. Time required for detection

The time required by the proposed method and the MTS are depicted in Fig. 13. As the number of Tri-X markers increases, there is a clear trend of a significant rise in the processing time of MTS. In contrast, our proposed method maintains a relatively stable speed. Statistical data highlights the superiority of our method over MTS in terms of speed. Notably, the detection of X-corners constitutes the main component of the overall processing time in our proposed method. Leveraging the fast block search strategy and SVM, our method requires approximately 26 ms to detect and match 30 Tri-X markers in binocular images. This breaks down to approximately 12.5 ms to for X-corner detection in each image and less than 1 ms for the detection, matching, and localization of the Tri-X corners in 3D space. These results indicate that our proposed method meets the real-time requirements efficiently.

3.3. Tri-X localization experiment

Once the Tri-X markers are extracted from both the left-eye and right-eye images, stereo matching and triangulation techniques can be employed to obtain the 3D coordinates of the three X-corners that form the Tri-X marker. Then the pose of the Tri-X marker, including its position and attitude, can be recovered through stereopsis. In order to evaluate the localization accuracy, we mounted the Tri-X markers at the end of a SCR5 robot, known for its accuracy of 0.02 mm. The stereo vision system was placed in a fixed manner within the scenario. In the localization experiment, we controlled the translation of the end of the SCR5 robot while maintaining a constant orientation. The changes in translation and rotation of the Tri-X markers were estimated, which should be equivalent to the movement of the end of the SCR5 robot.

The position localization error and orientation error are displayed in Table 4, Table 5, respectively. In Table 4,

∆ d

is the translation of the SCR5 robot and

∆ d^{'}

is the translation estimated by our algorithm. The absolute error and relative error are calculated and presented in the fourth and fifth columns of Table 4, respectively. The average absolute error of method is below 0.1 mm, indicating that our algorithm can achieve a high level of positioning accuracy within a margin of 0.1 mm.

Table 4. Positioning accuracy Unit (%).

Empty Cell	$∆ d (mm)$	$∆ d^{'} (mm)$	$\|∆ d - ∆ d^{'}\|$ $(mm)$	$\frac{\|∆ d - ∆ d^{'}\|}{∆ d} (%)$
1	20	20.005	0.005	0.025
2	40	39.955	0.045	0.112
3	60	60.088	0.088	0.147
4	80	80.029	0.029	0.036
5	100	99.922	0.078	0.078
6	150	150.033	0.033	0.022
7	180	179.916	0.084	0.047
8	200	199.896	0.104	0.052
Mean	-	-	0.058	0.065
Std	-	-	0.033	0.033

Table 5. Orientation accuracy (°).

Empty Cell	$∆ E$	$∆ E^{'}$
1	0, 0, 0	1.046, 1.117, 0.185
2	0, 0, 0	1.594, 0.571, 0.065
3	0, 0, 0	0.503, 0.562, 0.076
4	0, 0, 0	0.487, 0.152, 0.033
5	0, 0, 0	1.287, 0.409, 0.110
6	0, 0, 0	1.327, 0.190, 0.090
7	0, 0, 0	0.459, 0.904, 0.143
8	0, 0, 0	0.490, 0.272, 0.065
Mean	-	0.899, 0.522, 0.096
Std	-	0.437, 0.321, 0.046

In Table 5, the orientation change

∆ E = (∆ α, ∆ β, ∆ γ)

represented by the increments of the yaw, pitch and roll angles, is utilized to evaluate the orientation error. In our experiment, the SCR5 orientation remains unchanged, and therefore the estimated orientation change, denoted as

∆ E^{'}

, should be equal to zero theoretically. The average orientation error of our method is below 1°, indicating that our algorithm can achieve high orientation accuracy as well.

The localization experiment demonstrates the effectiveness of our Tri-X marker in tracking objects in 3D space robustly and precisely in real-time.

4. Discussions

The proposed method achieves comparable precision and higher recall compared to the available similar systems, while outperforming in terms of speed when tracking multiple objects. This can be attributed to the different techniques employed by X-corner extraction and Tri-X marker detection. If there are n Tri-X markers in the image, there will be 3 n X-corners, which don’t include those fake ones or noise yet. Other systems detect the Tri-X markers in 3D space, where there will be more than

C_{3 n}^{3}

combinations of Tri-X candidates to verify. However, in our method, by utilizing both position and orientation information to determine Tri-X markers in 2D image space, there will be at most n Tri-X candidates to be verified. Although we spend more time to filter the X-corner outliers and select Tri-X marker candidates, it is efficient by block-search strategy, SVM-based outliers recognition, and XAM-based Tri-X candidates selection.

However, in the proposed method, the value selection of parameter “r” and “

θ_{Th}

” will affect the performance, which both are related to the camera parameters including lens focus, pixel physical dimension, working distance, and the actual size of physical X-corner marker. Therefore, they should be adjusted for specific camera system to attain better performance.

“r” is the half side of the searching window. The searching window should be small enough that in the image the size of the smallest X-corner is bigger than it; while it should be big enough that the X-corner candidates can be extracted fast [39]. Therefore, too big or too small value r will both result in performance degradation. From Fig. 8, it can be found the detection speed and F1-score will get balanced when r is 12 in the experiment setup.

“

θ_{Th}

” is the maximum error threshold for determining whether two X-corners form a collinear edge vector. Since the distortion and edge blur, in then edge vector

\vec{X_{1} X_{2}}

the

l_{BW}^{(1)}

cannot be strictly collinear with

l_{WB}^{(2)}

. Small

θ_{Th}

will fiter more possible real edge vectors, thus the recall be cutdown; Big

θ_{Th}

will let in more possible edge vectors, but requires more time to filter those fake ones. In our experiment,

θ_{Th}

= 6° will get the balanced performance between the time consumption and F1-score.

In the experiment under different distances and inclination angles as shown in Table 1, the maxim test distance was 1.5 m which is similar to the work distance of the generally available MTS system. However, from Table 1 it can be found that the performance decreases with increasing distance and inclination. This implied that the performance at longer distance meanwhile less inclination can be at an accepted level, although we didn’t test.

In the comparison experiment as shown in Table 2, we just compared with some SOTA methods [33], [38], [39] because the X-corner extraction is just the basis for Tri-X marker detection. Furthermore, there are only some methods [18], [36], [39] which detected both the position and the orientation of X-corner. However, in Ref. [18] the orientation of X-corner is defined as the eigen-vector of Hessian matrix, not the boundary line orientation as in Refs. [36], [39]. In Ref. [40] we have tried to detect Tri-X markers based on Ref. [18], but its performance is not rather low. Both Refs. [36] and [39] are our previous work about X-corner detection, and in Ref. [39] we have shown the advantage of Block-X [39] over SC [36]. Ref. [40] proposed a CNN model for X-markers detection, but it just detects the rough block position of X-corners, neither the sub-pixel position nor boundary line orientation. Therefore, we didn’t compare with Ref. [40] either.

5. Conclusions

(1)
To track objects with minimal features, Tri-X marker is introduced, which consists of three coplanar X-corners, along with their detection, localization and recognition algorithms. When multiple targets are involved simultaneously, different Tri-X markers can be utilized to trace and identify different objects.
(2)
By combining the block search strategy and SVM, X-corners can be detected robustly and fast. Then Tri-X candidates can be extracted efficiently in 2D image space through the adjacent matrix (XAM) which is constructed by both position and orientation information of X-corners. Once the Tri-X markers are extracted from binocular images, the 6D pose information can be recovered through stereo matching and triangulation technique, which is faster than MTS.
(3)
Experimental results demonstrate that the proposed method can achieve position error below 0.1 mm and an orientation error below 1°, which outperforms the state-of-the-art approaches in terms of both accuracy and efficiency.
(4)
The proposed method has great potential in medical robotics, medical device tracking, and augmented reality. Future work will try to incorporate additional sensor modalities and advanced machine learning techniques to further enhance the performance in complex environments.

CRediT authorship contribution statement

Cai Meng was in charge of the idea and the whole paper; Yue Zeng and Hongbin Shen contributed in drafting, revising the paper; Hongbin Shen and Xinliang Deng implemented the algorithm, captured the dataset, and conducted the experiment during their study in Beihang University; Diansheng Chen assisted with laboratory result analysis. All authors read and approved the final manuscript.

Funding

Supported by National Natural Science Foundation of China (Grant No. 92148206) and National Key Research and Development Program of China (Grant No. 2024YFC2418102).

Declaration of Competing Interest

The authors declare no competing financial interests.

Acknowledgements

The authors sincerely thanks to Professor Shuzhi Sam Ge of National University of Singapore because this work was initialized in his Laboratory since 2010, and he abandoned to be listed as an co-author.

Robust 3D object tracking with X-Triplet markers: A machine learning-based approach

Abstract

Keywords

1. Introduction

2. Method

2.1. Definition of Tri-X marker

2.2. Frame workflow

2.3. SVM-based X-corner detection

2.3.1. X-corner candidate selection

2.3.2. Outlier filter with SVM classifier

2.3.3. X-corner position and orientation refinement

2.4. Adjacent matrix construction

2.5. Tri-X marker candidate extraction

2.6. Pose Estimation and Recognition

3. Experiment and analysis

3.1. X-detection experiment

3.1.1. SVM training

3.1.2. Detection performance under different parameters

3.1.3. Comparison with SOTA methods

3.2. Tri-X detection experiment

3.2.1. Tri-X detection performance

3.2.2. Time required for detection

3.3. Tri-X localization experiment

4. Discussions

5. Conclusions

CRediT authorship contribution statement

Funding

Declaration of Competing Interest

Acknowledgements