Multi-Objective Depth First Search for Orchard Row Detection

Related Work

Pathfinding

Coego and co-workers presented an improvement of the IDMOA* algorithm which searches for non-dominated solutions and simultaneously accounts for all objectives, called PIDMOA (Pareto Front Iterative Deepening Multi-Objective A*). Each iteration uses a new set of threshold non-dominated vectors for the search and this method uses iterative deepening. The idea of using a threshold to select solutions which relax every iteration seems like an intuitive idea. The changing threshold will allow for more confident rows to be identified first, before developing the uncertain rows on top of the pre-existing confident rows.

Comba and co-workers proposed an unsupervised algorithm for vineyard detection using 3D point-cloud mappings that are created from UAV imagery. The method begins an evaluation of features at each point in the cloud, using a small local radius of 5m, by using the local terrain surface and height evaluation. This algorithm shows robustness for curvilinear rows which is a key characteristic needed for our algorithm. The local circle evaluation techniques mentioned above is an excellent idea to capture local information within an orchard without being dependent on a global orchard row direction. The local circle evaluation may boost the chance for the identification of difficult curved rows while still permitting straight rows to be captured within the same orchard.

Hough Transform

Hough Transform (HT) methods, initially proposed by Hough, are industry-standard algorithms for finding shape primitives. Straight-line detection is the simplest case of these methods and is based on computing accumulations of counts corresponding to pixels that lie in straight-lines. The potential of using the HT methods stems from the fact that the tree centroids could represent these points, and a straight-line extracted could indicate a row in the orchard.

There are several academic papers which apply the HT methods to crop row problems with reasonable success. Unfortunately, the HT is limited in that it can only detect crop rows which are planted in a straight-line. While various techniques like approximating curves with many small tiles which contain straight-lines and predefining a shape to try and identify in the source image do exist, the HT is not flexible enough to robustly handle straight and curved row detections within our problem. The idea of breaking curves up into smaller segments to classify as straight-lines initially seem like a good way to deal with difficult sharp curves within an orchard. This will enable many short rows to be merged together to form an integrated curve that can be improved upon at a post-processing stage. This idea is what inspired the initial straight-line component in the MODFS algorithm.

Experiment Design

The unlabelled data used in this work can be viewed and manipulated using QGIS. Each orchard input represents information collected via aerial images. The inputs include polygon shape detections, which represent the trees in the orchard. Additionally, each tree has an associated confidence value which indicates how certain the object detector is of the tree’s presence. Furthermore, the inputs include a boundary and a georeferenced image of the selected orchard.

The main qualitative methodology of evaluation will be to compare the rows produced visually by the MODFS approach to the unlabelled data of the orchard rows. Each orchard solution will be judged in multiple categories. These categories serve to show the different aspects of the algorithm and where it may fail. The qualitative score options are good, average, and bad. The categories are:

• How well the overall row structure is captured
• How robustly the perimeter trees are handled
• Predicted Row Length to orchard data
• Frequency of incorrect classifications
• Frequency of missing classifications

Three testing orchards have been used to perform a comprehensive statistical analysis of the results due to hand-labelling of ground-truth rows. This allows for the computation of Precision and Recall of the orchard rows. These metrics were used to perform parameter tuning. Experiments were conducted with a Windows Laptop which has 8.0 GB of RAM, 2 cores and 2.20 GHz of processor power

Conclusion

The MODFS algorithm is shown to produce sufficiently accurate orchard row predictions for straight and slightly curved orchards. Additionally, the algorithm can adapt to multi-orientated straight orchards and it will produce accurate rows. Unfortunately, orchards which contain very dense or curved trees would result in inaccurate rows which do not capture the underlying row patterns. The rows produced on heavily curved orchards show potential as they partially map the arc of curved rows with a few short segments.

Additional areas where the MODFS may be improved upon include; handling perimeter trees and service tunnels within the orchard, and reducing the number of unassigned trees. Nevertheless, a robust algorithm has been developed, implemented and proven to accurately predict orchard rows for numerous cases. This is shown by the numerous orchard predictions which have visually correct rows, as well as the qualitative metrics which boost statistical confidence in the MODFS’s predictive power. The aims of the project have only been partially met; however, the project has been successfully informative on where the algorithm works correctly and indicates where it can be potentially enhanced.