The paper reviews current approaches to automated navigation tasks, such as localization and mapping, and proposes a different approach based on probability density approximation. The proposed system uses feature extraction to reduce computation complexity. Descriptors, are then used to match mapped features to a current view, and localization uses iterative pose estimation based on gradient descent. Current system limitations and weaknesses are also shown.
Kaidyk3,† and
In modern literature, in the context of visual navigation, the following tasks are considered:
localization, mapping, route planning and traffic control (traffic control and obstacle detection) [
There are several areas of computer vision research dealing with localization issues: Visual Odometry (VO), Visual Position Recognition (VPR), and Visual Simultaneous Localization and Mapping (VSLAM).
Visual odometry (VO) solves this problem directly by iteratively calculating the displacement of the robot both with the help of inertial sensors, odometers, and through the analysis of image changes from cameras, in particular, calculating the optical flux.
Optical flux in the context of visual odometry is a vector field that describes how pixels in an image are shifted between two consecutive camera frames. In other words, it is an estimate of the apparent movement of the points of the scene relative to the camera.
Usually, it is calculated either on a continuous wide area of the image (dense optical flow) or on individual features/key points (sparse optical flow).
To ensure sufficient accuracy, the calculation of displacement iterations must occur quite often – given limited computational resources, this imposes significant limitations on the algorithms that can be used to calculate the optical flux.
Another problem is that optical flux is not the true motion of objects — it is a projection of three-dimensional motion onto the plane of an image. Therefore, algorithms based on dense optical flux can lose accuracy if there are a significant number of repetitive patterns in the image.
Known methods for calculating dense flow:
1. Horn–Schunck (HS) [
4. Brox Optical Flow (Variational, multilevel) [
On the other hand, algorithms based on feature selection are used in VPR and VSLAM: instead of analyzing the entire frame, the algorithm finds noticeable local fragments (features) — points, corners, texture elements, and contours. A descriptor is built for each such point.
A descriptor is a compact numerical representation of a local view that can be compared between frames or with a memory base.
This allows: 1. Recognize terrain (VPR). 2. Evaluate camera movement and orientation (VSLAM). 3. Build an environment map (VSLAM).
Mapping in VSLAM is the process of building and gradually updating a spatial model of the environment based on images (video stream) and other sensory data.
In VSLAM, this includes the following key aspects: 1. Select and save landmarks (features/landmarks): From camera frames, stable points, objects, or characteristics of the scene are identified, which can be re-recognized during further movement. 2. Map formation in the form of 3D points or their structure: based on triangulation and assessment of the camera pose, a map of the environment (for example, a sparse point cloud) is created. 3. Constant map update: as the work progresses, the map is expanded, clarified, and corrected (via loop closure). 4. Cooperation with localization: mapping is closely related to the assessment of one's own posture. The map is used for better localization, and accurate localization allows you to refine the map.
Loop closure is the process of detecting that a current observation corresponds to an already known location on the map, followed by optimizing the posture and map to eliminate accumulated drift.
Simply put, mapping in VSLAM is the construction of an internal spatial representation of the environment (in the form of landmarks, 3D points, or keyframes) that allows the robot to navigate and localize.
In classical VPR (Visual Place Recognition), the concept of mapping in the usual sense for VSLAM is almost never used, but there is a concept that is similar in meaning.
VPR focuses on recognizing already known places from an image, rather than building a complete map of space. That is, the system receives the current frame and compares it with a database of reference images or features to determine "where I have already been". It is not required to build a 3D map or spatial model.
MMost VPR algorithms use a database of images or descriptors, which can be thought of as a passive observation map. It contains: 1. Global or local visual signs. 2. Coordinates or place indexes (if available). 3. Offline mapping.
In terms of computational resources, feature-highlighting algorithms have certain advantages compared to those that use dense optical flux, but they also lose accuracy in the case of large, uniform areas in the image. 3. Existing Algorithms for Determining the Trajectory of Robots
Today, there are a large number of algorithms for determining the trajectory of robots adapted for
various functions, designs, and conditions of use of these systems. In particular, for indoor spaces,
the following can be used:
1. PTAM (Parallel Tracking and Mapping) is one of the first successful real-time visual SLAM
algorithms developed by Hern Klaus and Andrew Davison (2007) [
Works with monocular, stereo, or RGB-D video [
In the context of the tasks of this work, localization algorithms can be classified according to the possibility of use in closed spaces (indoor), the number of cameras used, the use of additional sensors (IMU), and approaches to image processing (feature highlighting, optical flux calculation, neural networks) (Fig. 1).
Comparison of algorithms in terms of requirements for hardware and computing resources, and general areas of application, is given in Table 2.
DSO / LSD-SLAM
Support for large maps.
Loop closure + relocalization.
High fidelity on difficult scenesMono/stereo/RGB
D support. Track loss
resistance.
No identification of signs Works with weak signs.
Low dependence on
detectors.
Reliable VIO with
IMUOKVIS – optimization. ROVIO is a lightweight EKF.
D). Heavier than VIO or mono SLAM.
GPU is desirable for work. The main core is deep learning.
warehouses, indoor mapping.
Autonomous Robots, UAV, Complex Scenes, Academic Applications.
In this study, the authors consider the first two tasks of navigation: route mapping (using training video recording of movement along the route and accelerometric and odometrical data), and robot localization (based on video from the robot's camera, without auxiliary data).
Localization of a robot is the determination of the coordinates of its position (x, y, z) in a predetermined general coordinate system, as well as the determination of the coordinates of the heading vector of its camera in this coordinate system (hx, hy, hz) (Figure 2). the position , 0, , ℎ, ℎ, ℎ of the maximum ρ for a given set of :
E ρ (CV , x0 , y0 , z0 , hX 0 , hY 0 , hZ 0)=max X , H (ρ (CV , x , y , z , hX , hY , hZ )) , (1)
In order to simplify calculations, ρ can be represented as the product of probability density distribution functions for individual features ρi:
V ρ (CV , x , y , z , hX , hY , hZ )=∏ ρ f (uf , v f , x , y , z , hX , hY , hZ ) . (2) f =1 Here uf, vf are the screen coordinates of the f-th feature.
Thus, the construction of a navigation model can be viewed as approximation of distributions ρi.
The use of (2) and the gradient descent (ascent) method for estimation (1), in our opinion, can provide a flexible iterative process of refining the position of the robot by step-by-step consideration of features.
A distinctive feature of this approach is that we do not build a map of the environment in the sense of VSLAM, but create a database of features with approximated densities of probabilities of them being in certain point of multidimensional space S of position (x, y, z), heading vector of the camera ℎ, ℎ, ℎ, and screen coordinates (u, v): = (, , , , , ℎ, ℎ, ℎ) ∈ .
At the mapping phase for each feature f we collect a set of observations: = {(, , , , , ℎ, ℎ, ℎ)}. Before starting approximation process it is mandatory to consider rotational symmetry: given different camera orientation ℎ same feature f can be viewed at different screen coordinates (u, v) (see Figure 4).
To account for this fact, we inject in our set Sf additional points for set of pre-determined heading vectors ℎ for which the calculated (u, v) fits within viewport.
Let’s assume that approximation ρf is a hypersurface in (ρ, S) space defined by equation: ρ f (u , v , x , y , z , hx , h y , hz) =
P P P P = ∑ ∑ ... ∑ ... ∑ a pu=0 pv=0 phx =0 phz=0 pu , pv , px , ... , phx , ... , phz u pu v pv x px ... hxphz hzphz . (3)
a pu , pv , px ,..., phx ,..., phz
– coefficients that must be determined, P – maximal power we consider.
One limitation related to representation (3) that we already see is that feature have to be “local enough” – if there are many view areas producing similar features their corresponding approximations become less useful for pose estimation.
Having probability density in form (3) allows to compute partial derivatives easily, e.g.: ∂ ρ f = ∑P ∑P ... ∑P ... ∑P a ∂ u pu=0 pv=0 phx =0 phz=0 pu , pv , px , ... , phx , ... , phz u pu−1 v pv x px ... hxphz hzphz . The loss Lf,ρ for candidate distribution approximation ρf can be expressed as:
N f Lf , p=∑|N f ρ f ( si) w−n ( si)|2 .
i (4) (5)
Here Nf – number of data points in the set, () – number of observations of feature f in the small volume w around vector . The goal of approximation algorithm is to find a set of coefficients a pu , pv , px ,..., phx ,..., phz such that Lf,ρ is minimal.
Although the mapping phase is computationally intensive, ideally, it can be performed once for a given closed space. The result is a file with a list of stable features with their corresponding approximation coefficients.
The localization problem is solved by detecting features in a video frame and looking up their similarities in the map file. For each feature match the corresponding probability coefficients then used to compute estimated probabilities via (2) and their gradients using (5) that are used iteratively to adjust pose estimation.
To implement the data processing algorithm and navigation algorithm, OS Ubuntu v.24.04, the Python runtime environment v.3.12, and the interactive shell JuPyter are used. The PyPlot and ParaView tools are used for data visualization.
As part of development and testing a data collection and mapping subsystem was developed. To gather video and IMU information a smartphone app was created that records video and IMU data.
The Android Studio environment was used to develop the application to collect training data. The application supports Android OS version 13 and higher.
A screenshot of the application is shown in Figure 5.
Requirements for the application: 1. Ability to record video. 2. Ability to record accelerometer and gyroscope readings of a smartphone with a frequency of at least 25 measurements per second and store them together with the timestamp in CSV format (see Table 3).
Y
Z
X
Y
Z
An algorithm was also developed for intermediate processing of training data. Stages of the algorithm: 1. Select lighting-resistant feature sets from video frames. 2. Generation of a unique handle for each feature. 3. Define the timestamp of the frame. 4. Calculation of camera position and orientation for a given frame based on timestamps. 5. Saving data in CSV format.
X
Y
Z hx hy hz
In the course of the tasks, it was found that the direct detection of features on the Grayscale or RGB (separate ORB detector per channel) image is vulnerable to changes in lighting from daylight to artificial. The features that stand out under the daytime lighting are not reproduced with artificial lighting, and vice versa. In order to improve the persistence of feature detection, it was decided to convert the image to the LAB color space and select the features from channels A and B separately.
To distinguish features originating from different channels, the prefix 01 (for channel A) and 02 (for channel B) is added to their descriptors.
The current block diagram of the algorithm is as follows (Fig. 6).
A part of the room was used as a test site - an area of complex configuration shown in Figure 7.
For the convenience of calculations, the beginning of the general coordinate system coincides with the starting point of the training trajectory. The training trajectory passes through several points with pre-measured coordinates W1, W2, W3 and ends at point E (coordinates are also measured).
P,P,P,P,P,P,P,P
For storing map data, the following CSV file is currently used:
The map file generator structure is straightforward:
Note: Currently, the map generator and localizer algorithms use a reduced power factor P = 2. The localizer algorithm schema is shown in Fig. 9.
The output CSV trajectory file structure is presented below:
Z
hx hy hz
An algorithm was also developed for intermediate processing of training data.
Several data collections were carried out under different lighting conditions: 1. Natural light (daylight from a window on a sunny day). 2. Artificial lighting (cold white light) 100% brightness. 3. Artificial lighting 50% brightness.
The average recording time was 30 seconds.
The ORB detector was configured to allocate up to 500 characters per channel per frame. A total of 6 data collections were performed: 1. 3 entries – for the version of the algorithm with highlighting features from the Grayscale image in 3 different lighting modes. 2. 3 entries – for the version of the algorithm with the selection of features from LAB A, B channels, also for 3 lighting modes. It is worth noting that the daytime regime in this case differed due to weather conditions.
As was mentioned before, the system is in a work-in-progress state. At the moment of this paper writing, only the first training data collection and evaluation were performed, together with mapper and localizer debugging runs on mock-up data. Currently, we are working on proof-ofconcept implementation of described system and improving the mapping phase (ideally, to achieve feature observation-time iterative coefficient estimation).
During the preparation of this work, the authors used ChatGPT and Grammarly in order to: Grammar and spelling check, and as a smart Search Engine to find related works based on the context of the conversation. After using these tools/services, the authors reviewed and edited the content as needed and take full responsibility for the publication’s content.