ACO for Orchard Row Finding in Aerial Images

Related Work

Hough Transform

The Hough transform is a simple mathematical technique originally used in image analysis for detecting straight lines [15]. The relevance of this technique comes from the fact that orchard rows can be perceived as lines of trees or plants when viewed in an image. The idea of using the Hough transform to detect rows has been explored in several papers, in the context of both ground and aerial images.

Currently, to the best of our knowledge, the Hough transform has been the only technique used to identify orchard rows from aerial images. Despite the applicability of this approach, it is accompanied by numerous limitations. First and foremost, it is limited to detecting straight rows. Many of the papers using this technique neglect to mention this limitation and only consider straight rows as inputs. Additionally, all methods utilising the Hough transform require an extensive amount of pre-processing. The backbone of this pre-processing phase is a series of morphological operations that try to separate and reduce rows into distinct contiguous lines. These morphological operations are very much orchard dependent and rely heavily upon the definitive separation of rows from background pixels represented by soil, grass or other vegetation. The pre-processing employed by these methods is also dependent on spatial resolution and illumination changes of input images

Ant Colony Optimisation (ACO)

The first example of an ACO algorithm was called Ant System (AS), which was applied to the well-known travelling salesman problem (TSP). Although the results were promising, AS could not compete with state-of-the-art algorithms for TSP. Nevertheless, AS inspired many subsequent works that would later go on to achieve world class performance in their respective problem domains. Examples of successful applications of the ACO algorithm include applications to probabilistic TSP, scheduling, assembly-line balancing, the quadratic assignment problem, and so on.

An application of the ACO algorithm that bears relevance to the problem of orchard row finding is that of edge detection . The similarity between ACO for edge detection and ACO for orchard row detection comes from the fact that neither algorithm is trying to find a single optimal path in a graph. Instead, they are both finding a set of paths whose configuration is optimum. ACO for edge detection treats each pixel in an image as a node in a graph. Artificial ants move from pixel to pixel, marking the traversed pixels with pheromones. The transition rule is based on the changes in grey level intensity of a 3×3 pixel region, where the centre pixel is the ant’s position and the surrounding pixels are the ant’s traversable neighbourhood. The resulting pheromone trails serve as a rough-cut.

Experimental Setup

The data used in this paper comprises a selection of varying orchard input images. We consider four different orchard inputs with each input portraying a unique set of row and detection characteristics. The selected inputs are ordered by row curvature and detection density, which can be seen in the results section.

We compare the performance of the proposed ACO algorithm on each of these orchard inputs. The evaluation metrics used are precision, recall and intersection over union (IoU). To compute these metrics, we compare model-produced rows against hand-labelled rows. Model and hand-labelled rows comprise a series of edges which are compared for similarity. A true positive (TP) constitutes a model edge that correctly identifies a true edge, a false positive (FP) refers to a model edge that doesn’t correspond to a true edge and a false negative (FN) refers to a true edge that hasn’t been identified by a model edge.

Experiments were conducted on an Asus laptop running Windows 10 x64. The machine has 16.0 GB of RAM and a four core AMD Ryzen 7 CPU with clock speeds of 2.30 GHz.

Conclusion

In this paper, we explore a novel approach to the problem of orchard row identification in aerial images. The crux of the proposed method is a modified ACO algorithm in which artificial ants traverse graph-representations of orchards to produce optimal paths that represent the rows of trees in those orchards. ACO for orchard row-finding not only modifies the generic ACO algorithm, but also includes newly devised mechanisms specific to this problem domain.

Unlike Hough-based methods, the proposed approach constitutes minimal pre-processing and can reliably identify curved rows of trees or shrubs. Furthermore, experimental results illustrate the robustness of the method to orchards with varying tree density.