Using Image Processed Hough Lines for Path Planning Applications
Path planning is a corner stone problem in the field of automated navigation. In robotic manipulation, path planning is necessary to determine the movement of an appendage. In GPS systems, path planning is used to find the fastest route to a destination with the least amount of traffic. Even in video games, path planning is necessary to help the bad guys hunt you down. Because of its commonality, the topic has been extensively explored.
As someone who primarily studies robotic applications, path planning is necessary for most automated tasks. In many mobile robotic applications, robots make paths by developing a map of randomly generated points. Depending on the favorite algorithm chosen, these points are then connected to build a path. Because of the probabilistic nature of the method, generated paths can be clunky, have massive number of data points, and be sub-optimal. There are of course methods to optimize paths, which have their own trade-offs.
Filtering
In conjunction with my raspberry picking robot end effector, I explored a possible approach for robotic path planning through a farm. Eventually, robotic systems will need to navigate through farms and other natural environments. Brute forcing areas of freedom and restriction for robot motion is slow and cumbersome. Additionally, using surface cameras may not be informative, due to the lack of variety of color and variability of structure on a farm. Instead, we should take advantage of the holistic properties of a farm to develop a deterministic path planning method. The idea I developed used satellite images of farms and a series of spatial filters to distinguish between areas of land and crops.
Imagine your perfect farm. Rows of crops of your favorite fruit or vegetable with convenient paths dividing each row of plants. For the purpose of this article, I refer to these roads as minor roads. At the end of each row of crops, the minor roads connect to a larger road. These are denoted as major roads.
The goal is to identify these major and minor roads using an image processing technique known as Hough (pronounced Huff) transforms. This technique is detailed later. The found lines that are between a start and end point, designated by the farmer, will be stitched together to form a path. First the image being used needs to be properly filtered by binarizing the image and removing noise.
A satellite image was first taken from a random Floridian farm on google maps (shown below). The RGB image is converted to a grayscale image by taking only the red channel of the RGB. The red channel is specifically chosen as road pixels tend to contain “more” red. This makes it easier to apply a universal threshold on the image. Otsu’s method for thresholding was then used to convert the grayscale image into a binary image (either black or white). The image is then taken the inverse of. Inversion makes noise removal easier in later steps. Before removing noise, an erosion technique is applied to the image. This makes the major and minor roads thicker. Increasing the thickness of the roads reduces the chances of them being discarded during noise clean up.
Looking at the image, most of the noise is within the crop area. To remove this noise, a fill function is used to convert all regions of a specific area that is surrounded by white. Such areas are filled in leaving large white blocks in the locations of the crops. By taking the inverse of this final image, the object of interest comes into focus again. This last step was important for the application as the Hough transform function specifically searched for white points.
Hough Transfrom
Hough transforms are a mechanism for extracting features from an image using a voting policy. A single point (or pixel) can have an infinite number of lines pass through it. This can be more or less discretized into several lines with fixed intervals of angles between them. We then attempt to find which line is shared by the most points in the image. This voting process selects the line that contains the largest number of pixels on it. This is very much a high level explanation for the purpose of the article, and I recommend the curious to read up for a more robust understanding.
Using Hough transforms on the final filtered image, we can find a rather decent number of minor roads (right above image). The method does struggle with major roads, often detecting multiple lines in the region. This is not a huge issue, as functions that searche for lines in similar locations and slope can be written. Such lines can simply be combined.
There were two algorithms that were devised to perform the stitching of the lines. Both are described in images below, but only the second was implemented. As a result, I will only focus on Algorithm two.
Initially, the user selects two points on the image and the roads have been found using a Hough transform approach. It is also assumed that the minor and major roads have been appropriately separated into two different arrays. The algorithm finds the closest line to the starting point. An array that holds all the found points is created and initialized with the starting point and the point of intersection from the starting point to the nearest line. A loop is entered and continues until the end point that was designated by the farmer is passed. A new closest minor line is searched for. A check is made to make sure that the new minor line shortens the distance between the current point and end point. If this check is not made, the path can theoretically go into the opposite direction forever. Once a line is found, the point farther from the most recently added point is added to the Points array. This is what allows for the snaking path that is seen in the pictures below.
Running this algorithm to completion resulted in the paths above. For ideal farms, this worked pretty well. Unfortunately, if the farms start getting more curvy the calculated Hough lines become fairly useless. This appeared to be a bigger issue with the major roads. Minor roads on farm tend be standard, while the major roads connecting them come in all shapes and sizes. The filtered farm below is good example.
An advantage of this algorithm, is that a considerable less amount of data needs to be stored. Using probabilistic methods, hundreds of points may have to be generated. Hough lines do not suffer from this. Each line is composed of just two points.
As whimsical and interesting as I find this approach to be, it’s fairly limited in application. The path planner requires for the existence of lines within the image. Yet, it does beat probabilistic path planners in several ways. A probabilistic method would have difficulty forming a road map with farm images, as the majority of the farm is an obstacle. Furthermore, unlike most path planners, this algorithm does not actually search for the shortest path. The shortest path would simply connect the start and end point the farmer chose. This approach instead snakes through the farm, covering as many crops as possible.
This project gave me fairly useful experience working with image processing related problems. I used Matlab for the image processing libraries, but the same results can be achieved with open source libraries, such as OpenCV. I will not continue working to optimize this project in my free time. I am content with the results I got from this project (I’ve also moved on to another image processing/robotics relate project). It is precisely for this reason I wanted to document this project. If anyone is interested in continuing where I left off and has any questions, I’d be thrilled to help.
