GFS-VO: Grid-based Fast and Structural Visual Odometry

We employ grid structure to divide image into separate areas, with each area referred to as a grid. The grid structure offers advantage of showing feature’s distribution in image. We then build a bipartite index to establish connections between grids and lines, which serves as the foundation of subsequent processes such as line homogenization and tracking.

As mentioned in chapter II, the challenge in line homogenization primarily lies in node allocation. To address this issue, we propose three line homogenization methods. The idea is as follows:

• •

  Quadtree based scheme: For lines in the image, a marker is added to all the grids they traverse. The sum of markers within a grid is considered as record.

• •

  Midpoint-Quadtree based scheme: Lines are assigned to a specific grid based on the position of their midpoint. The sum of midpoints within a grid is record.

• •

  Score based scheme: Linse within each grid are rewarded or penalized based on their average gradient. A scoring mechanism is employed to rank all lines, and a portion of lines with the highest scores are retained.

The first two scheme are extension of point homogenization. Our primary focus is on finding a unique node to represent a given line. In Quadtree-based scheme, we assign a record to every grid that line passes through. On the other hand, Midpoint-Quadtree scheme only adds a record to grid where the midpoint of line is located. As a result, the record of each grid can effectively describe density of lines within a specific range. Similar to point homogenization, subsequent division step can be performed based on records of grids.

Score-based scheme is designed from a global perspective. During the comparison experiment, we noticed that in some dense part of image like Fig. 4, complete divide a line into corresponding region of a node becomes challenging due to line’s inherent extension characteristics. Consequently, this often results in the incomplete homogenization. The key is that the selection of a line within a node does not imply that it is the best line, but rather that it is comparatively better than the other within a specific area. Building upon this concept, we replace division step in Quadtree or Midpoint-Quadtree based schemes with a scoring mechanism. In this approach, we prioritize lines with the highest average gradient and penalize the other within same grid. These rewards and punishments are reflected in the scores assigned to each line, which are determined based on the number of lines present in adjacent area of the grid.

Given that only one line in each grid is awarded while all remaining lines are punished, there is a significant disparity between numbers of punishment and award. To ensure fair selection of punished lines in the global screening process, we introduce an asymmetric score value, where the deduction for punished lines is less than the award. This asymmetric score value can be calculated as formula (1) and (2):

where $na$ is the number of lines in adjacent area of current grid and $np$ is the number of grids that line has passed through. After calculating score of all lines, we retain lines with higher scores as the outcome of homogenization.

Furthermore, it is important to note that the average gradient can’t reflect line’s length. Consequently, longer lines tend to receive lower scores due to their participation in scoring multiple times. In scenarios where there is a significant disparity in line’s length, it is recommended to utilize formula (3), which reduces deduction value for longer lines by incorporating an exponential function in denominator.

When system is able to accurately estimate speed, the change between two frames is not expected to be significant. Under these circumstances matching time can be greatly reduced by leveraging grid structure. Specifically, we first find grids that the line passes through, as well as neighboring grids. Lines that pass through these grids are selected as candidate matches. Subsequently, descriptor matching is performed between given line and candidate lines. This approach reduces the number of candidate matches compared to one-to-one exhaustive calculation. Furthermore, it incorporates geometric positioning into the matching process, thereby enhancing both the accuracy and speed of matching procedure.

In scenarios where estimated speed is unstable, matched line obtained from tracking tends to decrease. To address this issue, we can employ method of expanding search scope. Simply expanding the search radius, as done with point features, may not be effective due to the instability of line length. Nonetheless, the fracture of line segments does not alter their slope. Therefore, when tracking performance is poor, we can utilize an extension tracking method, as depicted in Fig. 5. The grids that the extension line passes through are then considered as an additional search range.

Pose will be optimized when we get enough matched feature. For matched points and lines, we use constraints in [2] and [6] to calculate rotation and translation. For two consecutive frames, lowercase letters are used to represent features in the image plane, while uppercase letters represent features in world coordinates.

where $\tau$ is a binary function which return 1 only if point $i$ and $j$ is matched. $\rho$ is Huber loss function to reduce interfaces of noise. $\pi$ is projection function used to project 3d points into image plane. In a similar way, the reprojection error of a map line can be defined as:

where $S_{i}$ and $E_{i}$ represent the coordinates of two endpoints of line $i$ and $n_{i}$ represents line’s normal vector. Base on this, loss function needs to be minimized can be defined as:

Formula (9) will be optimized by LM algorithm in g2o library [26]. Once the pose of the current frame is determined, we establish the connection between local map and current frame by utilizing both the pose and observation information.

Line homogenization introduces some instability to line features, which can result in reduction of map lines and reduction in their observation results. This may lead to tracking deviations. To address this issue, we propose two solutions. Firstly, we adjust the threshold for point and line observations when selecting keyframes, thereby weakening the connection between keyframes and local map. This adjustment helps mitigate the impact of line instability on the overall system. Secondly, in filtering keyframe, we extend point-based strategy to a point-and-line strategy. This means that a keyframe will only be considered redundant if there is a significant overlap in observations between both points and lines. By incorporating both point and line information, we ensure a more robust determination of redundant keyframes.

Considering structural constraints existing in line segments and MA, the way used in [19] is adopted here to embed structural constraints into optimization. The pose of covisible keyframe and coordinates of covisible elements will be optimizated. For a given keyframe $k$, we can get keyframes $K_{c}$ that have covisibility relationships from convisibility graph. We use $P$ and $L$ to represent map point and line seen by $K_{c}$. Set of keyframes $K_{f}$ that observe $P$ and $L$ but don’t connect to $K$ are also considered in optimization, but their pose is fixed. What we need to optimize is $\mathbb{N}=\left\{P_{i}^{w},L_{j}^{w},T_{k}\left|i\in P,j\in L,k\in K_{c}\right.\right\}$, so the loss function is:

This formula is composed of three parts, which respectively correspond to reprojection error($E_{R}$), structural constraints($E_{S}$), and parallel relation constraints with manhattan axis($E_{M}$). Specifically, $E_{R}$ is similar to the definition in formula (6), but match relationship changes to 2d feature and map elements. Structural constraints error $E_{S}$ is used to reflect the parallel and vertical relationship, which can be defined as:

where $L_{k}^{\perp}$ and $L_{k}^{\parallel}$ are sets of perpendicular and parallel line pairs in $L$. $E^{\perp}$ and $E^{\parallel}$ is given by:

Finally, We use $\mathbb{M}$ to represent map line that associated with a MA and seen by any keyframe in $K_{c}$. $E_{M}$ is used to reflect the parallel relationship between given line and extracted MA, which can be given by:

To assess time cost of proposed feature extraction method, we conducted a comparison between GFS-VO and MSC-VO[19], both utilizing MA for trajectory estimation. The results, presented in Table I, are represented by ”MA extraction/feature process”. It is important to note that in MSC-VO, the feature processing time includes both extraction and reconstruction of geometry features and the extraction of plane normal vectors. On the other hand, in GFS-VO, this processing time also encompasses grid distribution and line homogenization. Based on the results presented in Table I, it is evident that GFS-VO significantly improves the speed of feature extraction.

The reduction in time cost can be attributed to three main factors. Firstly, in geometry feature extraction, we employ EDLINE instead of LSD, which reduces line extraction time. Secondly, line homogenization scheme in our algorithm reduces the number of line segments involved in reconstruction. Lastly, BFS-based approach enables accurate and rapid extraction of normal vectors from image. This helps in reducing unstable features and mitigating the influence of noise during the MA extraction, thereby improving extraction speed without compromising accuracy.

At the same time, we also noticed deficiencies of GFS-VO. For datasets with large changes in the amount of line (like Fig. 7), careful consideration should be given to setting the homogenization threshold. The main challenge arises from the fact that the threshold required for locations with abundant line features differs from that needed for sparser areas. Setting a small threshold effectively filters lines in rich locations, but it may not apply in sparse areas, and vice versa. There is no universal scale to measure the intensity of line features in all scenes.

We use Root-Mean-Square Error (RMSE) of absolute trajectory error as evaluation standard. The performance of other methods in experiment are from the best results provided in the respective papers. The comparison is shown in Tab. II.

Upon experiment results, we notice that improvement in virtual scenes is limited. This limitation primarily stems from the scarcity of stable features in these datasets, particularly in the living room dataset. The instability of line features, in terms of length and quantity, not only affects the accuracy of pose estimation but also impacts MA extraction. Conversely, in TUM dataset, which represents real scenes, GFS-VO demonstrates significant improvement. We attribute this improvement to the complexity of point and line features in actual scenes, which highlights the benefits brought about by line homogenization. On one hand, our method preserves longer lines in the scene compared to traditional response-based line screening, establishing a more stable observation relationship between frames. On the other hand, homogenization removes short lines in dense areas. These short lines are more unstable and prone to errors in matching and pose estimation. The removal of such lines positively impacts the overall accuracy.