How to rewrite the stars: Mapping your orchard over time through constellations of fruits Gonçalo P. Matos, Carlos Santiago, João P. Costeira, Ricardo L. Saldanha, Ernesto M. Morgado Abstract Following crop growth through the vegetative cycle allows farmers to predict fruit setting and yield in early stages, but it is a laborious and non-scalable task if performed by a human who has to manually measure fruit sizes with a caliper or dendrometers. In recent years, computer vision has been used to automate several tasks in precision agriculture, such as detecting and counting fruits, and estimating their size. However, the fundamental problem of matching the exact same fruits from one video, collected on a given date, to the fruits visible in another video, collected on a later date, which is needed to track fruits’ growth through time, remains to be solved. Few attempts were made, but they either assume that the camera always starts from the same known position and that there are sufficiently distinct features to match, or they used other sources of data like GPS. Here we propose a new paradigm to tackle this problem, based on constellations of 3D centroids, and introduce a descriptor for very sparse 3D point clouds that can be used to match fruits across videos. Matching constellations instead of individual fruits is key to deal with non-rigidity, occlusions and challenging imagery with few distinct visual features to track. The results show that the proposed method can be successfully used to match fruits across videos and through time, and also to build an orchard map and later use it to locate the camera pose in 6DoF, thus providing a method for autonomous navigation of robots in the orchard and for selective fruit picking, for example. Fig. 1: Overview of the proposed method. (A) Fruits are tracked throughout the image sequence in stereo 3D. (B) Constellations of 3D fruit centroids are matched using the proposed descriptor. (C) Fruits are re-identified across videos. I INTRODUCTION In the context of precision agriculture, measuring fruits’ growth over time provides insightful information to farmers, helping to predict what will be the fruit yield and to adjust agricultural practices, such as fruit thinning, to optimise the quality and quantity of production. Outliers in growth rates could also be symptoms of disease or irrigation anomalies. However, manually measuring and tracking fruits’ sizes with calipers or dendrometers is a laborious process that is not scalable for large orchards, and sampling them to extrapolate results is error-prone. In recent years, computer vision techniques have been applied to precision agriculture, automating tasks such as fruit counting [ 19 , 17 , 1 , 2 ] for yield estimation and fruit sizing [ 5 ] . These applications generally address the problem as an isolated act of analysing the fruit present in one video shot on a given date, but tracking the crop’s growth and evolution at fruit level through time requires capturing and relating multiple videos on different dates. However, matching individual fruits across videos is a challenging task, since their visual appearance and their surroundings (trees’ branches and leaves) change over time and in non-rigid ways, making it hard for common visual feature descriptors such as SIFT ( SIFT ) [ 15 ] to perform reliably. To our knowledge, this problem has not yet been solved in general settings, without assuming something about the initial pose and trajectory of the camera, or without the aid of external sensors like GPS ( GPS ) and IMU . The difficulty of finding distinct visual features to match images in cluttered and dynamic scenarios also hinders the task of creating a map for robots to navigate visually through the orchard, which could be useful to automate the selective application of chemicals or to perform fruit picking on only some trees. In this work, we propose a different paradigm, which we call the constellation paradigm , inspired by previous works with 2D semantic maps [ 24 , 23 ] . Instead of trying to find distinct features and matching them individually across images, we use semantic information — the 3D location of fruits, obtained with an object detector and a stereo camera — to lift the problem to a semantic sparse point cloud of object centroids, and then find a correspondence between small patterns of points, which we call constellations , similarly to how people identify constellations of stars in the night sky. The robustness of the method comes from (1) using semantic information that is less sensitive to changes in visual appearance between videos, and (2) recognising distinctive patterns (constellations) in the relative positions of a few static objects, which produces less false matches than trying to match individual points. We also contribute a new descriptor for very sparse 3D point clouds that is invariant to rotation, translation, and scale, which we use to match constellations of fruits across two 3D scenes with unknown relative pose and reconstruction scale. II RELATED WORK The problem of finding visual correspondences between scenes that change appearance through time, due to illumination or seasonal changes, can be related to other broader problems known in the field of robotics as hierarchical localisation [ 18 ] , long-term visual localisation [ 22 ] , and place recognition [ 6 ] . In many of these problems, a urban scene or an indoor scene, composed of mostly static and rigid objects with clear surfaces and edges, is usually the addressed scenario. Yet, in our case, we are dealing with objects (plants) that have no clear boundaries, surfaces or edges, which grow and change appearance in a non-rigid way over time. Hence, trying to match visual features or dense point clouds in these settings is not very effective, which is why we lift the problem to the semantic level of constellations of fruits and try to match these very sparse semantic point clouds. Therefore, we relate our approach with other works that specifically addressed crop monitoring through time, or to approaches that involve matching sparse point clouds. II-A Crop monitoring through time Lei et al. [ 13 ] proposed a method to monitor orchards through time at individual tree and fruit level in order to plot fruit growth charts, but their method fuses data from an RGB camera, a LiDAR ( LiDAR ) and an IMU in order to build a 3D semantic map. Several of these semantic maps are then registered with the ICP ( ICP ) algorithm, which requires a good initial pose estimation. The authors work-around the initialisation problem by placing a physical marker on the ground and always starting the data collection procedures with the camera/sensors on that same place, which is not a viable solution to be used “in the wild” by farmers with cameras mounted on agricultural vehicles. Dong et al. [ 7 ] also addressed the problem of monitoring the same 3D plant structures over time. They use a multi-sensor SLAM ( SLAM ) pipeline, combining RGB imagery, IMU and GPS in a factor graph, to achieve a 3D reconstruction of each row of trees, but their approach strongly relies on the GPS and IMU measurements to first roughly register two reconstructions and to later guide the search for image correspondences between them with SIFT [ 15 ] . Moreover, the imagery that can be in seen in [ 7 ] suggests a considerable distance from the camera to the peanut plants, showing large areas of terrain and several rows of plants both in the foreground and background from which it is possible to extract distinctive features to match. In our case, though, we have a camera mounted in a tractor, facing a row of trees just about 1 meter away. Chebrolou et al. [ 4 ] focused on the problem of long-term registration of point clouds for crop monitoring using UAV ( UAV ) imagery. They propose a 2D geometric descriptor that outperforms SIFT in the task of matching features across images captured at different dates, and use those matches in a BA ( BA ) problem to jointly compute the camera poses and 3D positions of landmarks in two different dates. However, their method requires a top-down and far view of the crop, where several plants are visible and easily discernible, and also assumes that the terrain is approximately planar. II-B Matching of (sparse) point clouds In recent years, several descriptors were proposed for point clouds and 3D points in the context of point cloud registration [ 3 ] , place recognition [ 6 ] or localisation [ 10 ] . However, they usually refer to dense point clouds obtained by LiDAR sensors mounted on vehicles, which depict mostly static and rigid scenes, such as cities, and from which surfaces and normals can be estimated [ 20 , 26 ] . In contrast, our point clouds of trees obtained from stereo, besides being noisier than those obtained with LiDAR , are cluttered, do not contain any planar surface, making it hard to compute normals, and hardly contain any distinctive features to track or match. Tinchev et al. [ 21 ] propose a descriptor specifically for cluttered vegetation scenes, but they use very dense and precise LiDAR point clouds, and they are not interested in identifying very small features at fruit level, but only in performing global localisation. Moreover, the authors note that the method struggled in a scene with uninterrupted bushes, and that it may fail if the sensor vantage point changes significantly between captures. If we consider our very sparse semantic point clouds resulting from fruit centroids instead, we cannot apply most descriptors designed for dense point clouds. Even descriptors that were specifically proposed for sparse point clouds, such as PGHCI [ 25 ] , NBDL [ 6 ] or GLAROT-3D [ 16 ] , usually work by dividing points in bins and computing relative densities or histograms, which still require some hundreds of points to extract a meaningful descriptor. As we shall see, in our case we have very few landmarks, with semantic point clouds that can be as low as 5 points, for which even these descriptors would not be effective. Some of the limitations commonly identified in the literature for place recognition methods include the lack of robustness of some descriptors to point of view changes, changes in appearance caused by varying light conditions, weather, or season, and occlusions in the point cloud caused by other objects, which are all issues we face in our data. These motivated several authors [ 8 , 9 , 27 , 14 ] to use semantic point clouds or graphs instead to tackle the place recognition and loop closure problem in SLAM in cluttered and dynamic scenes, which also seems a promisor approach to deal with noisy orchard point clouds like ours. This motivated our lifting of the problem to the semantic level. III PROPOSED METHOD III-A Overview The foundations for the “constellation paradigm” introduced before are to consider sets of fruits to form “constellations”, i.e. small point clouds, and to develop a descriptor for such “constellations”, in order to match them. Assuming that we have a method to obtain 3D representations of fruits as points corresponding to their centroids — in our case, we use an implementation of the 3D tracking algorithm described in [ 1 ] —, building a “constellation” of fruits amounts to forming groups of a fixed number of k such points and then encoding them with a descriptor. To group these points, we traverse the whole point cloud and consider one point (fruit) at a time, and find its k nearest neighbours. This set of k points becomes one constellation, and is encoded into a descriptor vector. Fruits are then matched across videos by finding a constellation with similar descriptor. Our descriptor allows the computation of a rigid transformation between the two matched constellations, hence it is possible to compute a relative camera pose, and localise a robot with respect to a map, for example. III-B STaR-i – A descriptor for sparse 3D constellations STaR-i — Scale, Translation and Rotation-invariant descriptor for very sparse 3D point clouds — is inspired by an astrometry solver published by Lang et al. [ 12 ] . Their descriptor works for constellations of stars in 2D images of the night sky and is invariant to translations, rotations, and scale. Our descriptor extends it to 3D while preserving these same properties. Without loss of generality, to keep the notation simple, we will consider in the following text and figures that we have k=4 points (“stars”) named A , B , C and D in a constellation. Stars A and B are chosen as the two most widely separated stars (Figure 2 ), and define the coordinate system over which the remaining stars will be represented. A is defined as the origin of such coordinate system, and B as the point (1,1,1) , and we chose them such that A is the closer one to the constellation centroid, in order to break ties. The coordinates (C_{x},C_{y},C_{z},D_{x},D_{y},D_{z}) of the remaining points in this new coordinate system will constitute the hash code that describes the constellation. C and D are chosen such that C_{x}