Keywords

1 Introduction

Robot navigation could be based on satellite navigation (GPS), inertial navigation or vision systems. Vision based navigation requires sophisticated algorithms for general case, but the simplification for well known or defined working area is possible. Line following robots use intentionally added line that defines possible routes. Many line following robots are proposed and used, because vision system could be very simple. Simplest systems uses two light reflective sensors for the measurement of reflected light from the line and the background. Fixed value for both measurements is obtained if the sensor is over the line. Different values occurs if the sensor is misaligned and the error could be used by the control algorithm. Rapid movements and high velocities require more advanced sensors, so linear light sensors are applied also. Forward looking cameras (Fig. 1) allow the estimation of line before robot (Fig. 2) at far distance also and this is the best solution, but requires sophisticated algorithms. Systems with artificially added lines are simple to design and the desired high background to line contrast could be achieved.

Fig. 1
figure 1

Schematic of line following robot with forward looking camera

Full size image
Fig. 2
figure 2

Example line following robot with forward looking camera

Full size image

There are numerous application where the line is natural or artificial but significantly degraded. The quality of the line is low in such cases, so the contrast between the background and the line is not sufficient for the application of simple vision systems and algorithms. This paper assumes such cases, that are important for numerous applications of line following robots.

1.1 Related Works

Navigation using lines, that are highly deteriorated are considered in numerous Lane Departure Warning (LDW) systems. The traffic safety could be improved if LDW system is used [14]. The very interesting research area is the combined navigation and inspection of power lines by UAVs [2]. There are numerous application of line following robots related to the harvesting, trash compacting [12].

Line estimation could be improved by the application of Track–Before–Detect algorithms. Such class of tracking algorithm [1, 13] allows the line estimation for \(SNR<1\) cases also. Viterbi algorithm [15] for line following robots is proposed in [8]. Lines that are noise pattern only, could be processed by the approach considered in [10]. Directional filtering of lines improves estimation also [7]. Local approach for the detection of disturbed lines is considered in [4] for example.

1.2 Content of the Paper

Two metrics for quality of estimation are considered in Sect. 2 (direct and new proposed boundary metric). The selection of metric influences the results and it is shown in Sect. 2. The optimization of Viterbi algorithm could be based on different parameters and two of them are selected and considered in Sect. 3 due to mobile robot applications. Monte Carlo tests are provided in Sect. 4. The results and discussion are provided in Sect. 4. Final conclusions are described in Sect. 5.

2 Metrics for Horizontal Error

The direct metric (\(E_i\)) for the horizontal error value could be defined as a difference between true \(X_i\) and estimated \(\hat{X}_i\) positions:

$$\begin{aligned} E_i=X_i - \hat{X}_i. \end{aligned}$$
(1)

Alternative approaches are possible and another metric is proposed (\(E^B\)) that considers width of line, so left (\(X^L_i\)) and right (\(X^R_i\)) boundaries are used. The error value in horizontal direction is typically non–zero for direct metric, but the error value should be zero if the estimated line position is located between line boundaries:

$$\begin{aligned} E^B_i = \left\{ \begin{array}{ccl} 0 &{} : &{} X^L_i \le \hat{X}_i \le X^R_i \\ X^L_i - \hat{X}_i &{} : &{} \hat{X}_i \le X^L_i \\ \hat{X}_i - X^R_i &{} : &{} X^R_i \le \hat{X}_i \\ \end{array} \right. . \end{aligned}$$
(2)

Estimated line position (Fig. 3 left), with pixel accuracy, that is inside boundaries gives zero value error for direct metric. The application of boundary metric allows the acceptation of all position between boundaries (Fig. 3 right).

Fig. 3
figure 3

Direct (left) and boundary metrics (right) regions of zero value error (gray)

Full size image

New boundary metric is proposed, because the selection of metric has impact on results. The example of line tracking for wide line is presented in Fig. 4 and direct metric and boundary metrics are compared. The cumulative error value is significantly reduced which shows impact of the metric. The results of Monte Carlo test for variable noise are shown in Fig. 5 and the difference between both metrics is well visible.

Fig. 4
figure 4

Example results for std. dev. = 1.0

Full size image
Fig. 5
figure 5

Mean of horizontal error (left) and maximal mean error (right). Monte Carlo test for std. dev. = 0.13 and line direction change probability 0.25

Full size image

3 Adjustment of Viterbi Algorithm for Mobile Robots

Moving windows approach has a high degree of similarity to driving mobile robot with digital camera looking down on route. Mobile robots very often moves at different speed and directions. Windows approach ensure possibility of moving mobile robot simulation in the same direction with different speed.

Windows approach from previous publications [7, 8, 10] defines shifting windows in image. Window has dimensions width as image width and window height as depth parameter. Window in the image was started from \(n=1\) row and finish on \(n=n_{max}\), where \(n_{max}\) is known from value of depth parameter. Next processing of window starts from \(n=2\) row and finish on \(n=n_{max}+1\) row. The shift of window is equal one pixel in this case. This is the smallest possible move of the window in simulation. Added ability to change value of shifted window contributed to model mobile robot speed. If we parametrize this adding part we get \((n+step)\), where the step is mentioned parameter of shifted window. Markings shown in Fig. 5.

Fig. 6
figure 6

Shifted window approach

Full size image

The selection of depth and step parameters depends on several factors. First is resolution of image. The image from digital camera can be in different resolution. When resolution is low, the computation is fast but with less accuracy. When resolution increases, the accuracy is improved and the number of computation is growing. When the same image is captured with differs resolution, the depth parameter is various, because for higher resolution gained greater number of pixel. Second factor is height of the digital camera relative to ground, because when camera is on higher position it can register more route. Last factor is FPS (Frames Per Second) value of digital camera. Higher number FPS provided better accuracy with following line, because faster moving of mobile robot can be register (Fig. 6).

4 Results and Discussion

The same set of generated line was made on the image with \(200 \times 60\) pixel resolution. After generated line, disturbing lines with standard deviation from Gaussian noise were added. Next to the image Gaussian noise was added. Each set has 300 test scenario for specified Gaussian noise in std. dev. range (0–1.3) every 0.05 value.

Two values of parameters were studied in this paper: \(depth = (16, 32)\), and three value of parameter . For parameter \(depth = 16\) and \(step = (1, 4, 8)\), results are shown in Fig. 7. The results for parameter \(depth = 32\) and \(step = (1, 8, 16)\) are shown in Fig. 8.

Fig. 7
figure 7

Mean error and maximal mean error for different step parameter, (Monte Carlo test for std. dev. and line direction change probability 0.25 and \(depth = 16\))

Full size image
Fig. 8
figure 8

Mean error and maximal mean error for different step parameter, (Monte Carlo test for std. dev. and line direction change probability 0.25 and \(depth = 32\))

Full size image

The change of parameter step does not aggravate the algorithm, so algorithm will work with high speed of mobile robot. The result is better for higher noise level. The number of computation changes with step parameter. The algorithm finds faster for higher step parameter. The comparison between different depth parameter (Figs. 7 and 8) shown that parameter have small impact on the results.

The algorithm is resistant to change speed of mobile robot that is related to depth parameter. If we want our robot to move quickly we need to have as much as possible scope of the road. It can be achieved in several ways: by increasing the field–of–view of camera, or by increasing of height from the ground. The camera with more FPS could be applied for the better accuracy.

5 Conclusions

The computational cost of considered algorithm is acceptable for modern microcontrollers for low–resolution images. Proposed approach allows the reduction of computation cost by the application of larger step of moving window. High resolution images need TBD processing using multiple processors [9] or GPGPUs [5, 6].

Presented example assumes additive Gaussian noise disturbance. The removal of non–line object from the image could be based on concept presented in [3]. Texture related disturbances could be also identified [11].