Fast edge detection algorithm of working track for autonomous driving using Raspberry Pi

Graduation Thesis

In Partial Fulfilment of the Requirement for the Degree of

Bachelor of Telecommunication and Electronic Engineering

Thesis PDF and Codes: https://github.com/ChheangL/CodeAndResource/blob/main/Thesis%20Report%20.pdf 

Introduction:

Even though the advance of AI and Machine Learning enabled Advance Driving Assistance Systems (ADAS) in commercial vehicles, robust and compact cars still require good performance with low computational cost. The Sobel and Canny algorithms were used for edge detection in autonomous driving systems to detect sharp changes in lane intensity. However, facing the limitation of a Raspberry Pi, a robust edge detection algorithm is needed for real-time performance. The proposed method uses the convolution algorithm on transformed image data captured by a camera module. The image data are masked and linearized while covering the distance and direction needed to detect the lane marker. After testing with Track’s images, the result shows that the proposed method’s run time is faster than the Sobel and Canny algorithm by 10-40ms with a 96.5% success rate.

Fig. 2.1 Shows (a) the original image ,(b) Gaussian filtered image, (c)the Sobel operator, and (d) Canny operator.

Literature Review:

    Irwin Sobel, the Sobel algorithm creator, never published the Sobel algorithm; however, it was mentioned in other works [13]. The Sobel algorithm, also known as the Sobel-Feldman operator or Sobel filter, highlights the gradient regions of a high spatial frequency corresponding to edges of 2-D grayscale-image, as shown in Fig2.1. It uses two convoluting operations for horizontal and vertical edge detection over the entire image to discern the boundaries in the image. Moreover, the noise-sensitive operator requires a Gaussian pre-processing filter, as shown in Fig2.1.b.

Fig. 2.2 Shows the kernel used in the Sobel filter for detecting horizontal and vertical edges.

              In theory, the operator uses 3x3 kernels  and  as shown in Fig.2.2 which are convoluted with the 3x3 segments of the image. The convolution kernels  and  are a 90-degree difference from one another, which function is to detect edges in the horizontal and vertical directions, respectively. If we define the source image as A and the approximated derivative in the horizontal and vertical at each pixel of the image as  and , the mathematical representation is as shown in Equations (1) and (2):

              At each point of the image, the resulting gradient approximation from (1) and (2) can be combined to generate the magnitude and direction of the gradient with Equations (3) and (4). As shown in Fig.2.1.c, the gradient magnitudes are highlighted, representing the resultant rates of changes in the intensity spectrum.

              The example in Fig2.3 shows the computational illustration of the horizontal gradient on a simple image intensity in a 6x6 grid. From observation, the boundary is separated in the middle from the left and the right sections. For a computer to detect the edge, we calculated the magnitude and direction of the gradient  and  in every pixel of the image. From the result, the boundary in the image will have a significantly higher gradient magnitude.

Fig. 2.3 Shows an example of the Sobel operation on a source image with the horizontal kernel and the convolution result Gx.

The canny algorithm is the improved version of the Sobel operator, which is less susceptible to errors with additional steps. After the algorithm detects the edge using the Sobel method, it passes the resulting edges through a non-maximized suppression and hysteresis threshold. The resulting edge detection improves the edge detection algorithm by thinning the wall of the boundary to its center and removing any discrete line from the resulting image, as shown in Fig2.4.

Fig. 2.4 Shows the improvement made with Canny operator (b) compared with Sobel (a).

Non-Maxima Suppression

              The non-maxima suppress algorithm suppresses the edges boundaries width to its local maximum. With the Gradient magnitude and direction, the Sobel boundaries are moved to their local maximum along the gradient direction by comparing them with their neighbors. As shown in Fig2.5, the white areas are supposed edges with the highest gradient magnitude. The non-maximum suppression algorithm compares the magnitude to its closest point in the gradient direction. If the next gradient magnitude is greater than the current one, then the gradient magnitude in the current pixel is put down to zero. Otherwise, the operation moves to the next pixel. In the example, the gradient magnitude in the green box is 300, and the next pixel in the gradient direction has a greater magnitude of 500; as a result, the green box is pulled down to 0.  

Fig. 2.5 Illustrating an example of the non-maximum suppression in which the Sobel Boundary (green box) compared with its neighbor (yellow box).

Hysteresis Threshold

In this stage, the algorithm's initialization defines the upper (maxVal) and lower (minVal) threshold. The edges for gradient magnitudes are considered more significant than the maxVal. The gradient magnitudes are no edges where its gradient magnitude falls below MinVal. However, for the values in between the threshold, we have to consider their continuity. For example, in Fig2.6, section C has deemed an edge because it is a continuation from A. Sections B and D, on the other hand, are discarded.

Fig. 2.6 Shows an example of the hysteresis threshold with given maxVal and minVal.

METHODOLOGY

    The proposed method in the research addresses the problem where the conventional methods method in the previous section computes over the entire images. Moreover, the proposed method to detect the edge of a lane marker is through operating the kernel convolution with transformed image data, and it is composed of two components: data pre-processing and boundary detection, as shown in Fig 3.1. The images from the camera sensor are masked and transformed into linear data. The lines intersect with the lane marker, translating to sharps changes in the pictures. They are detectable by convoluting the 1D image data with the kernel, which returns the edge’s position on the data line. With just the Python interpreter, the process took longer than optimizing the OpenCV library’s edge detector. However, the algorithm can run in real-time by pre-compile the program using the Numba library [14].

Fig. 3.1 Showing the two components of the (name) detector: Pre-process and Detector.

Data pre-processing:

              Lane images are pre-processed by masking and linearizing the image data to reduce the computation loads. The masking process removes the top or bottom portion of the idea that presents unnecessary areas for computation, including houses, trees, or even the sky. Lines are generated at an angle to cover more spots on the sides rather than the center of the lane. As shown in fig3.2, the lines and mask are developed through a mathematical calculation, ignoring the top portion and areas other than the red lines. The parts are configured based on the camera settings and position; it is adjustable by setting the parameter in the code. By default, half of the images are masked. On the other hand, the lines are configured through an angle parameter which determines the angle between each line.

Fig. 3.2 Show the line generated (a) with an angle of 10° apart and limited to the lower half of the image, and used to extract data from the source image (b).

              The mask and lines are generated with tangent and comparison functions. First, the heights of the ROI are configured by setting the upper and lower bounds of the area. After that, the lines are generated by selecting the approximate pixel close to the bar as Equation (5) and fig3.3. For example, for a line at 30 degrees to the horizontal axis, we calculate the difference between  and the slope of the pixels . Then we compare the result with the threshold (t), usually within 0.01 errors. If the differences are slight, we select it as part of our generated line. Otherwise, the algorithm resumes iteration to the next point vertically . Only one side is generated since the lines on both sides are symmetrical along the middle vertical axis.

Fig. 3.3 Show the pixel selection process by estimating the closes pixel to the line.

              As shown in fig3.4, the lines generated and populated with data from the image in fig3.2b show drops in intensity in the lines. As a result, we can detect the boundaries of the lane markers on these lines. In Python, we generated the mask and serialized the data to remove redundancy in the code. Rather than generating the mask every time the process is run, we pull it from a serialized object directly.

Fig. 3.4 Shows the extracted linear pixel intensity data from the source image.

Edge detector

              The detector performs convolution on the linear data with a kernel. The data line consists of only one axis. Therefore only one kernel is required to find the boundaries. Furthermore, the convolution process is the same in the Sobel algorithm. First, small segments of the data  are extracted with the same dimension as the kernel. Then, the dot product between transposed kernel  and the segment matrix  is calculated. The convolution results are the gradient at the corresponding point with either positive or negative signs. Finally, we compare the gradient magnitude with a predefined threshold  as shown in Eq (6).

              The kernel  size and weights are set based on the application and the environment. The size of the kernel defines how far to consider its neighbor pixels in the convolution. For noisy environments, wider kernels are best suited to average convolution. If the kernel is too small, small changes can be detected easily. Furthermore, the weights on the kernel define the significance of its neighbor. A heavier weight on the kernel’s wing signifies more importance for the neighbors in the convolution.

              As shown in Fig3.5, the first element in the segment with the value 100 is multiplied by the first element of the kernel with -1, resulting in -100. Summing all the produces, the result is the gradient magnitude at the center pixel. The process is repeated for the next segment until a boundary is found or the data ends.

Fig. 3.5 Shows the convolution of a sample linear data with a kernel.

TEST AND EVALUATION METHODS

1.1 Testing hardware and track

1.1.1 Driving System Design

The demonstration used a steering system designed by the Thingiverse creator [15]. The design is 3D printed with ABS material and jointed using steel rods and super glue as shown in fig4.1. Using a single servo motor, the steering system can turn left and right 45 degrees similar to the actual car’s steering system.

The drive system of the demo car uses a gear and a drive shaft to transfer the rotational energy from a single motor to the wheels. The DC motor is already attached to a gearbox with a ratio of 48:1 which provide enough torque to move the vehicle. As shown in fig4.1, there is another gear connection that functions only to connect the motor to the shaft.

Fig. 4.1 The drive system design on the steering and mechanical transfer

1.1.2 Electrical Design

The Raspberry Pi captures images from a wide-angle camera and computes the angle using the proposed boundary detection. The angle data is sent to an Arduino Uno board via I2C protocol and control the servo and motor. The pins used for the connection are shown in fig4.2. Furthermore, a wide-angle camera is used to capture the image. The camera module has a view angle of 160 degrees and a 1080p resolution. Furthermore, the power distribution is separated by its regulator. The 12v battery provides power to the Raspberry PI via a 12v to 5vUSB converter, the Arduino Uno through the power jack, and the motor driver.

Fig. 4.2 Show the wiring diagram connection and power distribution

1.1.3 Test Tracks

Some tracks were made for testing the proposed edge detection algorithm as shown in Fig4.3. The tracks we made series from easy to difficult. The first three tracks are simple tracks made using an electrical tap on a blue foam board. The first track is a straight path for the car to move. The second track shows a round curve at each end, which creates a loop. The third track added a curve to the middle sections. Furthermore, we tested the track with the performance of all of the tracks mentioned above. However, in this thesis, we are using the fourth track which is a combination of the tracks with an addition of 90-degree turning sections.

Fig. 4.3 Shows tracks used for testing: (a) straight path, (b) rounds loop, (c) curved loop, and (d) complex path.

1.2 Evaluation

To validate the proposed method, we compiled the codes in Python code with the help of Numba libraries. Several tests are run using a set of Track’s images. (1) We compare our proposed edge detection method for the run-time test with OpenCV’s Sobel and Canny algorithms. The test is performed on the Raspberry Pi 3b via remote Jupiter notebook. (2) We test the algorithm performance with the Track’s image set by counting the number of successes and failures to the detect boundary. (3) The algorithm’s susceptibility to noise and errors is tested by using generated and actual noisy image data. We used sampled images from the track to evaluate the proposed edge algorithm. The sample images are set to capture at 1280x720 resolution. The codes and resource in this research can be found in the GitHub repository [16].

1.2.1 Run-time evaluation

Validating the algorithm run-time, we compare the run-time of our algorithm and OpenCV’s Sobel and Canny algorithms with the image sets. The kernel used in this test is shown in Fig3.6 with the threshold set to 80. The upper and lower thresholds for the Canny algorithm are set to 100 and 200, respectively. The test runs through 100 images and outputs the statistical result, including min, max, and average run-time of each algorithm as follows:

Table 4.1  Run-time comparison between our works, Sobel and Canny algorithm using raspberry pi 3B (Unit = millisecond)

From the result, the run times of each algorithm are shown to be in the millisecond range. The algorithm presented is faster than the other two by 10 to 40 milliseconds. The Jupyter notebook used to evaluate the algorithm is available in Appendix B.

1.2.2 Performance evaluation

Fig. 4.4 Shown graphing the data on each line and the convolution results.

We evaluate the algorithm’s performance by manually counting the success rate with the image set. Using a more significant size kernel than the previous evaluation, we run it through 140 images from the Track’s image set. As shown in Fig4.4, most of the boundary results spiked to 90~100 level. As such, the threshold is set to 90 for this tracking environment. The algorithm can detect the boundary when it passes through the road for success detection. A false negative result is not detecting any edge when there is a boundary present, and a false positive is the result of detecting random noise in the data. We plotted the lines and boundaries point on to the image using the Matplotlib library. The resultant boundary detection images are shown in Appendix B. Over the 140 images tested, there are a few false negative detections among the image due to noise in the system. As shown in fig4.5, the lane markers of image 64 are shown to be too small and at the edges of the line.

Fig. 4.5 Shows the unsuccessful detection where the algorithm should detect the edge of the lane markers.

Table 4.2 Performance of the proposed edge detection algorithm over 140 Track images

Total Image	Failed	Successful detection	Success Rate
140	5	135	96.5%

 

1.2.3 Kernel size and weight to noise susceptibility

We tested different kernel sizes and weights to understand the kernel and its effect better. They can be tuned to have various performances based on environment setups. As shown in Fig4.6, the gradient magnitudes are sensitive to noise in the data line. Moreover, the gradient magnitudes scale linearly with the weights of the kernels. Furthermore, by increasing the size of the kernel, we can convolute over more extensive data for better detection. The first three graphs show that as the size of the kernel increase, the noise remains relatively the same while the boundary detection increases. With a larger kernel, the detector can account for more significant changes while damping short spikes in the data. In the figure with the kernel of [-1,-1, 0, 1, 1], the convolution on the outlier would not be more significant than the lane marker.

Fig. 4.6 Shows different kernel detection performances with noise in the data line.

The noise on the lane taken with a phone camera is more than the track images, as shown in Fig4.7. The kernel performance in a noisy environment is not ideal; however, sharper changes in the data are detectable with specified thresholds. Compared with Gaussian Filtered data, the result after filtering are slightly better, as shown in Fig4.8.

Fig. 4.7 Shows the noisy data line performance with different kernels without Gaussian Filter.

Fig. 4.8 Shows the noisy data line performance with different kernels with Gaussian Filter.

CONCLUSION AND FUTURE WORKS

Autonomous driving technology concerns the capability of the vehicle to avert any disaster. Sobel and Canny's algorithms were used; however, the computational power was limited. The proposed method utilize masking and linearization to reduce the computational load. By adjusting the kernel size and weight in the convolution, we could reduce the algorithm's susceptibility to noise.

The validation and testing results show that the algorithm performance is on par or better than the conventional method. Using the Track’ image captured with the Camera module on the raspberry pi, the performance on the image was 97% accurate in detecting the lane markers. The run-time performance of the algorithm is twist as fast as the conventional edge detection methods. Furthermore, the kernel size and weight can be adjusted to work with sensitive or noisy data. Using Gaussian Filter during the pre-processing work had shown promising results; however, larger kernels are enough to ascertain the boundary from noise.

For simple applications, the algorithm can be used for lane-keeping functionality in small autonomous cars with additional algorithms. By calculating the midpoints between the right and left boundary pairs, we can adjust the car motion to align with the midpoints. However, this simple algorithm did not account for other cases, including detecting only a single side or none. As a result, a more complex lane-keeping function required the assistance of machine learning and AI to learn and train with edge detection data.

The algorithm still needs to be improved in future works. The algorithm is required to be tested in a natural environment. A possible approach is automatically tuning the parameters and threshold to suit that environment. For instance, the color of the pavement may have drastically changed when the car moves through new or old roads. The kernel could abject and tune the threshold to adapt to the location change.

REFERENCES

[1] Tesla beams down “autopilot” mode to Model S. 2015 Oct 14. Automotive News. https://www.autonews.com/article/20151014/OEM06/151019938/tesla-beams-down-autopilot-mode-to-model-s.

[2] Lee TB. 2020 Oct 8. Waymo finally launches an actual public, driverless taxi service. Ars Technica. [accessed 2023 May 15]. https://arstechnica.com/cars/2020/10/waymo-finally-launches-an-actual-public-driverless-taxi-service.

‌[3] Hyperdrive Daily: The Driverless Shuttle Helping Toyota Win Gold. 2021 Aug 2. Bloombergcom. [accessed 2023 May 15]. https://www.bloomberg.com/news/newsletters/2021-08-02/toyota-seizes-olympic-glory-by-shuttling-athletes-autonomously.

[4] Honda Global | March 4, 2021 Honda to Begin Sales of Legend with New Honda SENSING Elite. globalhonda. [accessed 2021 Aug 20]. https://global.honda/newsroom/news/2021/4210304eng-legend.html.

[5] McCall JC, Trivedi MM. 2006. Video-Based Lane Estimation and Tracking for Driver Assistance: Survey, System, and Evaluation. IEEE Transactions on Intelligent Transportation Systems. 7(1):20–37. doi:https://doi.org/10.1109/tits.2006.869595.

[6] Yoo S, Lee H, Heesoo Myeong, Yun S, Park H, Cho J-H, Kim D-W. 2020 May 6. End-to-End Lane Marker Detection via Row-wise Classification. Computer Vision and Pattern Recognition. doi:https://doi.org/10.1109/cvprw50498.2020.00511.

[7] Chahal A. 2018 Jan 1. In Situ Detection of Road Lanes Using Raspberry Pi. doi:https://doi.org/10.26076/e34e-b372.

[8] SinghPannu G, Dawud Ansari M, Gupta P. 2015. Design and Implementation of Autonomous Car using Raspberry Pi. International Journal of Computer Applications. 113(9):22–29. doi:https://doi.org/10.5120/19854-1789.

[9] Fisher R, Perkins S, Walker A, Wolfart E. 2003. Feature Detectors - Sobel Edge Detector. https://homepages.inf.ed.ac.uk/rbf/HIPR2/sobel.htm.

[10] Canny J. 1986. A Computational Approach to Edge Detection. IEEE Transactions on Pattern Analysis and Machine Intelligence. PAMI-8(6):679–698. doi:https://doi.org/10.1109/tpami.1986.4767851. https://ieeexplore.ieee.org/document/4767851.

[13] Sobel I. 2014 Feb 2. History and Definition of the so-called “Sobel Operator”, more appropriately named the Sobel-Feldman Operator. [accessed 2023 May 15]. https://www.researchgate.net/publication/239398674_An_Isotropic_3x3_Image_Gradient_Operator.

[14] Lam SK, Pitrou A, Seibert S. 2015. Numba. Proceedings of the Second Workshop on the LLVM Compiler Infrastructure in HPC - LLVM ’15. doi:https://doi.org/10.1145/2833157.2833162.

[15] Extroo. 2018. 3D printed RC Car. url: https://www.thingiverse.com/thing:2404015

[16] This project resources and code, url: https://github.com/ChheangL/CodeAndResource.git