Keywords

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

1 Introduction

Line following robots are applied in numerous industrial [3] and entertainment applications . They use vision-based systems, that could be very simple or sophisticated. Simplest line following robots have applied two optical senors for the estimation of the position over the line. More advanced approach is based on the linear senor (1D camera) located under the robot. Cameras could be applied for the forward looking with perspective view of the line. This approach improves response of overall system, because the estimation of trajectory before the robot could be possible. Larger view allows better determination of line if distortions of many types occur. Some recent line following robots use 3D depth cameras for the estimation of the line. The main problem of line following robots is the vision system that should be robust for the poor light conditions and low line-to-background contrast. Such system should fulfill requirements of the real-time processing for constant speed maintaining. High-speed line following robots are in the area of interest of robotics enthusiasts and they are verified in numerous contests also. The importance of line following robots is not reduced by the availability of alternative navigation techniques. Satellite navigation (GPS) systems are not feasible for indoor applications. They have limited performance for outdoor scenarios and the real-time position is estimated with 2 m quality for single frequency receiver (L1) using standard (consumer grade) receivers. The position error could be reduced to 0.1  m for special civil receiver that are very costly. Moreover, limited availability of such receivers is related to political reasons. SLAM (Simultaneous Localization and Mapping) techniques are more costly due to higher computation power demands and line following robots are much simpler. This line could be artificially made or natural one.

1.1 Related Works

Line following robots are proposed in 60s of the previous century and the most notable is the Stanford Cart [14]. The area of applications related to harvesting and similar task, where the line is not specified directly, is considered in [13]. Road line estimation is necessary for automatic control of vehicle or is applied in lane departure warning system [15] using Hough Transform. Agricultural applications need natural lines estimation that could be low contrast [1] and the estimation of line is necessary even in LIDAR systems [17]. Recent works provide the approach based on the application of Track-Before-Detect algorithms [2] that improves lines estimation quality, so even lines hidden in the noise background could be detected [9, 10]. Additional trajectory filtering [4] may improve results independently on noise suppression in the spatial domain.

1.2 Content and Contribution of the Paper

The Viterbi algorithm is originally applied for time series with unknown multiple states at specific moments [16]. Replacing of such state by the 2D position is possible and the line estimation is possible for low curvatures. Directional filtering (FIR-based) that is parallel to the line direction improves the line estimation [9]. Local directional filtering is necessary with fixed direction for better estimation of curvatures. Such approach is important for the computation cost reduction also, so Viterbi algorithm is not applied for every image row. The idea of hierarchical processing of such data is introduced in [6]. Two filtering approaches are possible. First one is computed using original image and second one uses local Cartesian-to-polar transformation. The second approach is assumed in this paper and is considered in Sect. 2. Viterbi algorithm is applied for the selection of the most probable path and is considered in Sect. 3. Monte Carlo approach is applied for the numerical evaluation of algorithm performance and is considered in Sect. 4. The discussion is provided in Sect. 5 and the final conclusions are provided in Sect. 6.

2 Measurement Space Transformation

The acquired image frames are rectangular with Cartesian coordinates. Viterbi algorithm, discussed in next section, process them using small length track (tracklets). Every tracklet value is related to the average value of pixel related to the starting particular position and orientation:

$$\begin{aligned} d_{\left\{ x,y,\phi \right\} } = \int _{l_{\phi }} I\left( (x,y) \in l_{\phi } \right) \mathrm {d}l_{\phi }, \end{aligned}$$
(1)

where \(l_{\phi }\) is the line oriented with some angle direction \(\phi \) and \(\phi \in \langle -\alpha , \alpha \rangle \) Cartesian-to-polar transformation could be applied for limited angle range. The cone of analysis in such transformation is reduced to \(\langle -\alpha , \alpha \rangle \). Multiple tracklets are processed starting from the particular pixel \(\left( x,y\right) \) with assumed cone (Fig. 1). This cone could be modified to triangle for the equalization of tracklets length in vertical direction. Example input image and the result of Cartesian-to-polar conversion with cone area are shown in Fig. 2. Such conversion changes sloped lines to straight lines that allows the application of Viterbi algorithm in more straightforward way like it is considered in [9, 10]. The cone (Fig. 2) in converted to the rectangular region corresponding with \(\langle 180^{\circ }-60^{\circ }, 180^{\circ }+60^{\circ } \rangle \) range and this certain rectangular area is processed. Such reformulation simplifies the implementation of Viterbi algorithm, that is important in real-time processing applications. White areas present in Figs. 1 and 2 are omitted. Measurement space transformation could be applied locally with equal vertical length of tracklets what is computationally practicable.

Fig. 1
figure 1

Possible tracklets for particular pixel: equal length of tracklets (left) and equal vertical length of tracklets (right)

Full size image
Fig. 2
figure 2

Input image with line (black) and cone (gray) of analysis (left) and result of Cartesian-to-polar conversion (right)

Full size image
Fig. 3
figure 3

Local paths in example trellis

Full size image

3 Viterbi Algorithm

Viterbi algorithm could be applied for image processing using two approaches. First approach assumes direct relation between pixels and states. Second approach uses transformed image space using directional filtering for example, so tracklets could be processed. Viterbi algorithm uses two processing phases for particular starting row of pixels. The first phase uses forward processing and the second is backward for the best trajectory (best tracklets set) obtained from the first forward phase. Obtained result is the single tracklet related to the single starting pixel of the particular row. Such tracklets allows the robot motion control. Tracklets possible transitions are defined by the trellis. Example part of trellis is shown in Fig. 3 for two rows of pixels/nodes (n and \(n+1\)). There are \(n_{max}\) of rows in forward direction and Cartesian-to-polar conversion is well fitted to this definition of the Viterbi algorithm. The length of tracklets could be variable, but fixed is possible especially for polar measurement space. The transition cost is assumed as a value of particular tracklet which is added to the value of node. This node is related to the 2D position of tracklet beginning. Multiple tracklets are merged in nodes of the next row and only the maximal or minimal values are preserved. The minimal values are preserved in this paper for the following settings: grayscale image with values from the normalized \(\langle 0 - 1 \rangle \) range; white color (value 1) corresponds to the background; the black color corresponds to the line (value 0), for the ideal case. The local cost for modified cone (triangle) is corrected due to different length of tracklets between nodes of two following rows:

$$\begin{aligned} d_{corrected{\left\{ .,\phi \right\} }} = {{d_{\left\{ .,\phi \right\} }} \over {|d_{\left\{ .,\phi \right\} }|}}. \end{aligned}$$
(2)

The image is processed using trellis and the example part of the trellis is show in Fig. 3. The Viterbi algorithm process \(n_{max}\) rows of nodes starting from the bottom row (\(n=1\)) and the obtained result is the transition between first and second row only. Further transitions between rows \(n=2 \cdots n_{max}\) are processed for the selection of this particular transition and are not reused in next steps (e.g., \(n=2 \cdots n_{max}+1\)). Overall process is repeated for next sets (e.g., \(n=2 \cdots n_{max}+1\)) without relation to the previous results. Initialization is the assignment of zero value to the total cost V for nodes of the first row (\(n=1\)):

$$\begin{aligned} V_{n=1,.}=0 \end{aligned}$$
(3)

The local cost d (exactly \(d_{corrected}\)) is added to previous nodes:

$$\begin{aligned} V_{n+1,x}=\min \left( V_{n,x+g} +X_{n,x+g} \right) , \end{aligned}$$
(4)

but the minimal cumulative cost is preserved only. The transition is preserved in L using the following formula:

$$\begin{aligned} L_n^{n+1,x}=\arg \min _g \left( V_{n,x+g} + X_{n,x+g} \right) . \end{aligned}$$
(5)

The first phase of the Viterbi algorithm is computed up to \(n_{max}\). The solution for the first phase (path) is the node with minimal value:

$$\begin{aligned} P_{opt}=\max \left( V_{n=n_{min},.} \right) , \end{aligned}$$
(6)

that is related to the x–position:

$$\begin{aligned} x_{n=n_{max}}=\arg \min _x \left( V_{n=n_{max},x} \right) . \end{aligned}$$
(7)

The Selection of the final node allows backward processing for the selection of transition between two first rows. The following recursive processing formula:

$$\begin{aligned} x_{n-1}=x_m+L_{n-1}^{n,x}, \end{aligned}$$
(8)

for successively decremented row numbers:

$$\begin{aligned} n=n_{max}, \ldots , 2. \end{aligned}$$
(9)

Two results are obtained—most probable node and transition to the next row.

Fig. 4
figure 4

Processed path in the Viterbi Algorithm (left) and in the tracklet-based Viterbi algorithm (right)

Full size image

4 Monte Carlo Test of Tracklets-Based Algorithm

The Tracklet-based algorithm reduces number of the processed row by the Viterbi algorithm (Fig. 4) and introduces directional filtering by the accumulation of values related to the path between rows. The increased number of rows n is responsible for better noise suppression. The filtering expect low probability of line direction changes and such example line is show in Fig. 4. Monte Carlo approach allows the estimation of the properties of algorithms because is unbiased. The comparison of algorithms is possible also for identical input images. The generator of images allows the testing for different controllable conditions, which is very important for the algorithm evaluation. The test scenario is based on the analysis of image that has \(200 \times 60\) pixel resolution. An example results of the single case are depicted in the Fig. 5. The line has standard deviation 1.0 and image is disturbed by a few lines with standard deviation selected by additive Gaussian noise. Two algorithms are compared: Viterbi and Tracklet-based tracking for exactly the same input images. There are 1400 testing scenarios for specified Gaussian noise (std. dev. 0–0.8), with two different line direction change probabilities \(\left\{ 0.25, 1.25 \right\} \). The main test was related to different number of rows processed by the Tracklet-based algorithm. Comparative results for the Viterbi algorithm are provided also (Fig. 8). The cumulative computation time is 500 h of 2.4 GHz core using Matlab for this test, but the real-time processing is possible for robot using optimized code. The regression line is shown in Fig. 6 for comparison both algorithms. The slope and position of this line shows the advantages of the Tracklet-based algorithm, because the mean position error for horizontal direction is smaller.

Fig. 5
figure 5

Example results for specific image—std. dev. 0.45 and line direction change probability 0.25

Full size image
Fig. 6
figure 6

Comparison of mean errors for Viterbi and tracklet-based algorithms (Monte Carlo test for std. dev. 0.45 and line direction change probability 0.25)

Full size image

5 Discussion

Very interesting results are shown in Fig. 7. Two histograms are depicted for both algorithms and they are different. Better distribution of errors is achieved for the Tracklet-based algorithm because probability of errors is exponential (smaller errors are more probable). The errors for the Viterbi algorithm have mean value near to 5. Final test (Fig. 8) shows better performance of the Viterbi algorithm for very small noise of images. The dynamic of the line influences the results. Small n could be selected for higher probabilities of line direction changes. Longer integration (larger n) is recommended for the smooth lines.

Fig. 7
figure 7

Histogram of mean error for Viterbi and tracklet-based algorithm (Monte Carlo test for std. dev. 0.45 and line direction change probability 0.25)

Full size image
Fig. 8
figure 8

Mean error for Viterbi and tracklet-based algorithms (Monte Carlo test for variable noise and line direction change probability 0.25 (left) and 1.25 (right))

Full size image

6 Conclusions

Line following robots could be improved using vision systems based on 2D camera. Difficult light conditions or line deteriorations are not significant problem for advanced image processing algorithms. Track-Before-Detect (TBD) approach allows processing of weak lines, even below the noise floor. There are applications where only noise is observed, so object’s signal is the noise pattern [8, 11]. Such case needs preprocessing of measurements independently on impulse noise suppression. Textures suppression algorithms [12] are also important for the reduction of spatial interferences. The cost of computation for TBD algorithms is significant, but modern available computing devices like SIMD-based CPU cores, GPGPUs and FPGA devices support real-time processing. Optimization techniques for TBD algorithms implementations are also possible [5, 7]. Viterbi algorithms could be accelerated using dedicated hardware that is very often available in modern DSPs. This algorithm is used for the digital communication applications, and there are dedicated instructions or coprocessors in DSPs. Monte Carlo approach allows testing of Viterbi and proposed Tracklet-based Viterbi algorithms and fitting parameters for the best performance and computational cost reduction. This approach allows the comparison of algorithms and the selection of better if variable conditions related to estimated background noise occurs. Such technique of image analysis allows the design better line estimation. Further works will be related to the implementation of mentioned algorithms for the line following robot.