The key problem for picking robots is to locate the picking points of fruit. A method based on the moment of inertia and symmetry of apples is proposed in this paper to locate the picking points of apples. Image pre-processing procedures, which are crucial to improving the accuracy of the location, were carried out to remove noise and smooth the edges of apples. The moment of inertia method has the disadvantage of high computational complexity, which should be solved, so convex hull was used to improve this problem. To verify the validity of this algorithm, a test was conducted using four types of apple images containing 107 apple targets. These images were single and unblocked apple images, single and blocked apple images, images containing adjacent apples, and apples in panoramas. The root mean square error values of these four types of apple images were 6.3, 15.0, 21.6 and 18.4, respectively, and the average location errors were 4.9°, 10.2°, 16.3° and 13.8°, respectively. Furthermore, the improved algorithm was effective in terms of average runtime, with 3.7 ms and 9.2 ms for single and unblocked and single and blocked apple images, respectively. For the other two types of apple images, the runtime was determined by the number of apples and blocked apples contained in the images. The results showed that the improved algorithm could extract symmetry axes and locate the picking points of apples more efficiently. In conclusion, the improved algorithm is feasible for extracting symmetry axes and locating the picking points of apples.
Additional key wordspicking robotfruit picking pointsymmetry axes extractionmoment of inertiaconvex hullAbbreviations usedCCD (charge coupled device)CIE (Commission Internationale d’Eclairage)HSI (Hue-Saturation-Intensity)RMSE (root mean square error)ULR (unitary linear regression)YIQ (Y represents brightness, I color changes from orange to cyan, and Q color changes from purple to kelly)This work was supported by the National High Technology Research and Development Program of China (863 Program) (No.2013AA10230402); Natural Science Basic Research Plan in Shaanxi Province of China (No. 2014JQ3094); “National Natural Science Foundation” of China (No. 31000670); and the “Fundamental Research Funds for the Central Universities” of China (No. QN2011031).
This work has two supplementary tables and four supplementary figures that do not appear in the printed article but that accompany the paper online.
Competing interests: The authors have declared that no competing interests exist
Introduction
The fruit picking robot is one of the main research directions of modern agricultural development. The key problem is how to realize the goal of identification and localization of fruit through accurate use of machine vision technology. Under natural conditions, fruit have different growth postures due to different soil, seasons and weather conditions, which have strong impacts on locating the picking points of apples and the follow-up picking tasks.
Several studies have been carried out to locate fruit under natural conditions (Plebe & Grasso, 2001; Bulanon et al., 2004; Chinchuluun et al., 2006; Guo et al., 2008; Yin et al., 2009; Rajneesh et al., 2013). A computer vision-based method was presented by Jiménez et al. (2000) to locate fruit on trees. Special attention was paid to CCD (charge coupled device) sensors and accessories, which were utilized for capturing tree images, and image processing strategies, such as local and shape-based analysis, were used to detect fruit and then locate them. Local analysis allowed for rapid detection and was only able to detect fruit at specific maturity stages. Shape analysis was capable of detecting fruit of any color, but it was time consuming. A method based on binocular stereovision was utilized to locate tomatoes by Xiang et al. (2010). To improve the precision of depth measurement for ripe tomatoes, two stereo matching methods, centroid-based matching and area-based matching, were analyzed comparatively in their paper. Their performances in depth measurement were also compared. Then, models of ULR (unitary linear regression) were used to improve the results of depth measurement. A cherry-harvesting robot was manufactured by Tanigaki et al. (2008). The vision system of the robot was a 3D vision sensor equipped with red and infrared laser diodes. Both laser beams scan the object simultaneously. By processing the images from the 3D vision sensor, the locations of cherries and obstacles were recognized. However, the end effector of the robot should be improved according to the result of field evaluation, as cherries can be damaged easily. Arefi et al. (2011) proposed a machine vision-based method to recognize and locate ripen tomatoes. In Arefi’s paper, an R-G chromatic aberration image was defined to remove the background in the RGB color space. After extracting ripe tomatoes using a combination of RGB, HSI (Hue-Saturation-Intensity) and YIQ (Y represents brightness, I represents color changes from orange to cyan, and Q represents color changes from purple to kelly) color spaces, morphological features of the image were used to locate the ripe tomatoes; experimental results showed that the total recognition accuracy of the algorithm was 96.36%. A method based on convex hull (the convex hull is the minimum circumscribed polygons of a target; it is the smallest convex set that contains all of the objects in a set, and the vertexes must be in the point set) was proposed to locate occluded apples (Song et al., 2012). In Song’s paper, the convex hull of the contour was used to extract the smooth and real contours, and the extracted contours were utilized to estimate the centers and radii, which were used to localize occluded apples. The average positioning error using the method was 4.28%. However, because apples are not idealistically round targets, the location result would be influenced by candidate points, which were used to estimate centers and radii of apples. Xie et al. (2012) described four methods: the least distance, least slope variance, three collinear points and second-order central moment methods. A fusion of the four methods could reach recognition rates up to 90%. However, each of the four methods had its disadvantages, and the fusion of the four methods was time consuming.
As seen from the literature above, these methods have some unsolved disadvantages, such as low accuracy rate, highly time consuming, complexity of the operating process, etc. These disadvantages, to some extent, restrict the real-time capability of the apple harvesting robot in natural scenes. Thus, a new method should be proposed to solve these problems.
Symmetry axes detection of a 2D point set based on convex hull was presented by Zhang et al. (2010). After extracting the convex hull of the point set, the symmetry axes can be found through seeking the symmetry axes of the convex hull. A symmetry axis detection method based on the minimal value of the moment of inertia was proposed to extract the symmetry axis of gray images (Liang et al., 2009). The literature above gives an idea that the symmetry axes of the convex hull of an apple can be extracted to locate the apple target due to the good symmetry characteristics of apples.
Based on the descriptions above, this paper will try to describe a convex hull theory and contour symmetry axes extraction algorithm-based method to locate the picking points of apples. Firstly, the image is transformed from RGB color space to L*a*b* color space, and then the K-means color clustering algorithm is used to detect apples. Secondly, to weaken the influence of noise on the extraction of symmetry axes, image pre-processing algorithms, including mathematical morphology and noise removal, are carried out to remove noise and smooth the edges of the apples. Then the convex hull is used to replace the apple’s contour, which is useful to decrease the computational complexity. Finally, a moment of inertia algorithm is utilized to extract the symmetry axes of apples, which are used to realize the purpose of locating the picking points of apples accurately.
Material and methodsHardware and software
A personal computer with a 2.60 GHz processor and 4.0 GB of RAM was used as the hardware component of the computer vision system, and all algorithms were developed in MATLAB vers. R2013a. A digital camera (Fuji film A900, CMOS color camera) was selected, and the shooting distance was approximately 1.5 m. Our research will focus on the ‘Fuji’ apple (Malus domestica), which is the most popular apple species in China. Images used in the experiment were collected from September 2011 to September 2014 at Standard Rootstocks Density Planting Orchard at Northwest A&F University. All of the images were acquired under natural daylight conditions in the RGB color model. Image frames were 1600×1200 pixels in JPEG format. In this study, 30 single and unblocked apple images, 20 single and blocked apple images, 5 images containing adjacent apples and 6 panoramas containing 45 apples were selected to test the performance of the presented algorithm.
Picking point of an apple target
The picking point is located on the peduncle of an apple, and it is one of the intersections of the symmetry axes and the contour of the apple. The intersection near the peduncle of the apple is the picking point. Searching for the picking point of an apple target is one of the most important tasks for the apple picking robot. After detection of the picking point, the robot can drive the end effector to cut the peduncle at the picking point and then fulfill the picking task for the apple. Through this manner of shearing, damage and decay of apples can be effectively decreased during storage processes and transportation, thus reducing loss effectively. The picking point, convex hull, and contour of an apple are shown in Fig. 1.
Schematic of the picking point, contour and convex hull of an apple. The black curve is the contour of the apple, the convex hull of the apple is represented by the blue curve, and the cyan “∅” is the picking point of the apple.
Apple contour extraction
Apple contour extraction is one of the most important steps in locating apple targets. To extract the contours of apples accurately, the K-means clustering algorithm was used to extract the regions of apples, and then the vertexes of the convex hull of each apple were extracted, which were used to replace the contour points of each apple and were useful for improving the operation speed.
L*a*b* color space. An appropriate color space is the basis of image segmentation. There is a strong correlation between each component in the commonly used RGB color space (Luo et al., 2000), which makes it difficult to determine the hue and saturation information of pixels through the components of R, G and B. The L*a*b* color space is a color model specified in CIE (Commission Internationale d’Eclairage). Any color can be expressed in the L*a*b* color space. The L*a*b* color space is a color-opponent space with dimension L* for brightness, a* for the range from red to blue, and b* for the range from blue to yellow, based on nonlinearly compressed CIE XYZ color space coordinates (Yin et al., 2009). Thus, to distinguish apple targets from the background automatically, it is necessary to transform the image from the RGB color space to the L*a*b* color space before clustering.
There are no simple formulas for conversion between RGB and L*a*b*. The L*a*b* color space is based on the XYZ color space. Thus, RGB should be converted to the XYZ color space first and then transformed into the L*a*b* color space. The formulas that transform the RGB color space into the XYZ color space can be expressed as,
The formulas that transform the XYZ color space into the L*a*b* color space are as follows,
where the function is,
The K-means clustering algorithm can be employed to cluster the apple images into several different classifications based on the a* and b* color components, regardless of the brightness.
Target segmentation by the K-means clustering algorithm. The K-means clustering algorithm is a partitioning algorithm of the feature space and has been widely used in image segmentation fields (Rekik et al., 2006; Yao et al., 2013). The K-means algorithm has many advantages, such as its simple description, high efficiency and suitability for large-scale data processing, which make it more suitable to segment images in this work.
The K-means algorithm is an unsupervised learning algorithm that groups data objects into several clusters to obtain the highest similarity between objects in the same cluster but the minimum similarity between objects in different clusters. That is, single pieces of data are segmented into specified clusters through iterative search (Jim et al., 2008).
The K-means clustering algorithm is described as follows,
Step 1: Select k initial clustering centers, Z1(1), Z2(1), …, Zk(1), where k is the number of clusters.
Step 2: After n iterations, the sample set {Z} is classified in the following way: for all i, j = 1, 2, …k, i ≠ j, if ||Z-Zj(n)||<||Z-Zi(n)||, then Z∈Sj(n).
Step 3: Obtain a new class center Zj(n + 1) through Step 2 to minimize .
Step 4: For all j = 1, 2, …, k, if Zj(n + 1) = Zj(n), end the iteration; otherwise, n = n + 1 and go to Step 2 and continue.
For the K-means clustering algorithm, the parameter k must be determined first. When we chose k = 2, the image was divided into two classes: the fruit and the background. When we chose k = 3, the image was divided into three classes: the fruit, the branches and the leaves. In this paper, the main task was to locate the picking points of apples, so we chose k = 2, resulting in branches and leaves being classified as the background. To ensure the accuracy of clustering, the morphological opening operation of the original color image was performed first, and a ‘disk’-shaped structure element with a specified radius of 5 was used before clustering to ensure the data information consistency in a small area and to make the image smoother. The opening operation would inevitably fill the gaps between objects and increase the apple size. Select small structure elements and appropriate structure shapes could weaken the effect of these problems, and such operations will not affect the subsequent process.
The results of K-means clustering are shown in Fig. 2 (k = 3) and Fig. 3 (k = 2). Specifically, from Fig. 2, we can see that when we choose k = 3, the image can be clustered into three classes, that is, fruit, branches and leaves. Fig. 3a, which is the original color image, shows that the contours on the left and right parts of the target were smooth and symmetrical and that the apple’s symmetry axes lied on the line between the apple’s peduncle and calyx; Fig. 3b, the result of clustering from Fig. 3a, could be used for image segmentation; Fig. 3c is the gray image of Fig. 3b; Fig. 3d is the binary image of Fig. 3c, and it contains noise, such as holes and spurs, which would affect the accuracy of extraction of the symmetry axes. Therefore, further processing was needed before the image could be used to extract the symmetry axes of apples.
Result of the K-means algorithm when choosing the cluster parameter as<italic> k </italic>= 3. <bold>(a)</bold> Original digital image captured in natural daylight conditions. <bold>(b) </bold>Image of branches. <bold>(c)</bold> Image of leaves. <bold>(d)</bold> Extracted apple image.
Result of the K-means algorithm when choosing the cluster parameter as<italic> k </italic>= 2. <bold>(a)</bold> Original digital image captured in natural daylight conditions. <bold>(b)</bold> Extracted apple image after the K-means clustering algorithm with<italic> k </italic>= 2. (c) Gray image of the extracted apple. <bold>(d)</bold> Binary image of the extracted apple.
Pre-processing of clustered apple targets. Compared with the real apple contour, the obtained contour was not smooth enough, and this might affect the precision in identifying the symmetry axes of apples. To solve the problem, pre-processing measures, including hole filling and noise removal, were performed. Fig. 4a shows that the pre-processed image still contained spurs, which could be further removed by performing a morphological opening operation with a ‘disk’-shaped structural element with a radius of 30. As a result, the processed image (Fig. 4b) showed no spurs and the contour became smoother, which was helpful in improving the accuracy of the extraction of apples´ symmetry axes.
Pre-processing result of the apple image after the K-means algorithm. <bold>(a)</bold> Pre-process the apple image via procedures such as hole filling and removing noise. <bold>(b) </bold>Smooth the edge of the counter using a mathematical morphology open operation with a flat ‘disk’-shaped structuring element with the specified radius = 30.
Convex hull-based method of identifying apple contours. The method of replacing contour points with the convex hull has a number of advantages, including reducing the number of edge points, simplifying the complexity of the original algorithm and shortening the operation time. Thus, the convex hull is used to replace the contour of an apple. A classical volume package convex hull extraction algorithm (Zhou et al., 2008) was adopted in this work.
Fig. 5a shows the contour extracted from Fig. 4b using the volume package convex hull method, while Fig. 5b was derived from Fig. 3d using a canny boundary operator. The contour in Fig. 5b shows rough edges when compared with that in Fig. 5a. In addition, the convex hull of the apple target was almost the same as the real apple and was smoother than the contour extracted in Fig. 5b when the convex hull was added to its original color (Fig. 5c). Taken together, it was feasible to replace the contour of the apple with its convex hull.
Comparison of the convex hull and contour of an apple. <bold>(a)</bold> Convex hull of the apple. <bold>(b)</bold> Edge of the apple extracted using the canny algorithm. <bold>(c)</bold> Convex hull of the apple illustrated in the original image.
The number of peripheral points in Fig. 5a using the improved algorithm was only 398, whereas the original contour of the apple in Fig. 5b consisted of 2412 peripheral points. Using the convex hull instead of the contour of the apple offers an improvement in algorithmic complexity as well as computational efficiency.
Location of an apple’s picking point
Based on the good symmetry characteristics of apples, the symmetry axes of apples can be identified as a way to locate apple targets. There are many algorithms for target symmetry axes extraction, such as the Euclidean distance algorithm (Remy & Thiel, 2005), neural network algorithm (Fukushima & Kikuchi, 2006), minimal inertia algorithm (Gong et al., 2001), etc. Among these, both the Euclidean distance algorithm and neural network algorithm are more applicable to complex images and are more complicated with regard to image processing, while the moment of inertia method has the characteristic of a simple operation. Therefore, the moment of inertia algorithm was adopted to achieve the symmetry axes extraction in this paper.
Moment of inertia algorithm. The moment of inertia algorithm can detect the symmetry axes of images quickly and accurately (Liang et al., 2009). The symmetry axes of an image are the lines when the moment of inertia reaches its extreme values. This is the theoretical basis of the moment of inertia algorithm.
The moment of inertia of the curve y = f (x) relative to the axis y1 = ax + b is defined as (assuming that y = f (x) is continuously differentiable on [- c, c]) (Gong et al., 2001):
Specifically, μ is the linear density. If the mass distribution is uniform, then μ is a constant. D (x) is the distance between a point (x, f (x)) on the curve y = f (x) and the straight line y1 = ax + b; D (x) is defined as:
Assuming that the function y = f (x) is axis symmetric, that is, f (-x) = f (x), then by setting the rotation axis:
or:
Two extreme values of the moment of inertia can be obtained. The line is a symmetry axis if it makes the moment of inertia reach one of its extreme values (maximum value or minimum value, depending on the shape of the curve); the line that reaches another extreme value (minimum value or maximum value) of the moment of inertia is perpendicular to the symmetry axis of the curve.
Because the moment of inertia is invariant with shifts and rotations of the coordinate axis, the extraction of symmetry axes of any symmetrical curve in any placement can be realized by locating the line when the corresponding moment of inertia reaches its extreme value. As shown in Fig. 6, the dashed line l is the symmetry axis. The selection of coordinate axes has no effect on the moment of inertia, so the accuracy of the extreme value has nothing to do with the symmetry axes. In this respect, the moment of inertia algorithm is accurate and stable in the extraction of the symmetry axes.
Symmetry axes of the symmetrical curve in any placement.
Apple target symmetry axes extraction. According to the theory of the above-mentioned moment of inertia algorithm, the symmetry axes and picking points (marked with a cyan color “∅”) of the apple targets are indicated in Fig. 7. As observed from Fig. 7, we obtained symmetry axes of the apple targets that varied between apple varieties and light conditions, and the other line was vertical to the symmetry axes. For these two lines, which one is the symmetry axis of an apple should be determined by the variety of the apple. The picking points were basically the two points of the apple peduncle and the apple calyx, and the extracted symmetry axis was nearly the same as the real symmetry axes of the apple target. Thus, the method presented in this paper can extract the symmetry axes of apples and locate the picking points well.
Location of the apple by extracting the symmetry axis and picking point (picking points marked with cyan“∅”).
Results
To verify the validity of the improved contour symmetry axes method presented in this paper, four types of images containing 107 apple targets were used to conduct the experiment. The test was run on 30 single and unblocked apple images, 20 single and blocked apple images, 5 images containing 12 adjacent apples and 45 apples captured in 6 panoramas. The performances of the proposed methods of the first two types of images were compared to those of the unimproved method and the method of principal inertia axis (Guo et al., 2008). The unimproved method is a method using the apple contour extracted by the canny algorithm without a pre-processing measure to extract symmetry axes. The method of principal inertia axis (PIA method) is a method utilizing the extracted principal inertia axis of an apple to locate the apple target. The direction of the principal inertia axis can be expressed as [8] (Guo et al., 2008),
where θ is the orientation angle of the principal inertia axis and m11, m20, m02 are two-order center moments of the binary image. They can be calculated by Eq. [9],
where f (i, j) is the binary image and m, n are the height and width of the image, respectively. are coordinates of the centroid, which can be calculated by formula [10],
From the equation above, θ can be calculated, and then the principal inertia axis can be obtained, which is used to locate apples.
The location results of the last two types of apple images were not compared to the unimproved method and PIA method. There were many apple targets in the images, and some adjacent apples occluded severely, which resulted in the real contour of the apple being unable to be extracted for the follow-up experiment.
The locations of real symmetry axes were found through observation, and the location errors were the angles between the obtained symmetry axes and the real symmetry axes. Here, we assumed the angle of the real symmetry axes was α, the angle of the obtained symmetry axes was β,and the location error was γ, so the formula of the location error was as follows:
RMSE (root mean square error) was used in this paper to measure the performance of the method proposed. RMSE can be used to judge the deviations between the true value and the value obtained from the test. The picking point is on the symmetry axes of the apple, so the location error of the picking point is the location error of the symmetry axes of the apple. The picking point is one of the intersections of the symmetry axes and the contour of the apple. In this paper, the convex hull was used to replace the contour. Thus, the picking point is defined as one of the intersections of the symmetry axes and the convex hull, and it should be determined by the variety of the apple.
Location results of single and unblocked apple targets
For 30 single and unblocked apple images, the processing step was relatively easy. The main procedures of the experiment were as follows,
Step 1: Transform the original image from the RGB color space to the L*a*b* color space, and then cluster the apple image using the K-means clustering algorithm.
Step 2: Binarize the clustered apple image.
Step 3: Extract the symmetry axes using the moment of inertia algorithm to test the effectiveness of the unimproved method.
Step 4: Pre-process the binary image, such as by a mathematical morphological operation and/or noise removal.
Step 5: Extract the principal inertia axis to locate the apple and test the performance of the PIA method.
Step 6: Extract the convex hull of the apple, replace the apple contour with it and identify the apple symmetry axes using the moment of inertia algorithm to test the effectiveness of the improved method presented in this paper.
Step 7: Compare the performances of the methods from Steps 3, 5 and 6, and calculate the location error according to formula [11].
The location results of apple targets are shown in Fig. 8. Detailed results of the location, location errors and running time of 30 images are given in
Table 1. From Fig. 8, we can see that the contours of the binary images in Figs. 8e-h were not smooth enough. In stark contrast, the images in Figs. 8i-l pre-processed with the improved algorithm presented in this paper were smoother in contour, which could enhance the precision of locating the symmetry axes of the apple targets. Moreover, the apple symmetry axes obtained using the improved method in Figs. 8m-p were basically in agreement with the real symmetry axes. Additionally, the picking points marked with the cyan “∅” in Figs. 8m-p were basically correct. As clearly shown in Table 1, the smallest location error was 0.0° using the newly presented method, and the average location error was 4.9°. The average run time was 3.7 ms, and the RMSE of the method was 6.3. However, among all of the test images in Table 1, some apple targets (3, 4 and 7) were not accurate enough in location when performing the presented method. The location results are shown in Fig. 9. Among the three apples, the largest location error was 14.7°.
Location results of single and unblocked apples: <bold>(a, b, c, d)</bold> original digital images captured in natural daylight conditions; <bold>(e, f, g, h)</bold> binary images after being processed with the K-means clustering algorithm; <bold>(i, j, k, l)</bold> pre-processing results of the binary images; <bold>(m, n, o, p)</bold> location of apple targets using the method proposed in this paper (picking points marked with cyan “∅”); <bold>(q, r, s, t)</bold> location of apple targets using the unimproved method; <bold>(u, v, w, x)</bold> location results of apples using the PIA method.
Location of single and unblocked apple targets with larger errors: <bold>(a, b, c)</bold> original digital images captured in natural daylight condition; <bold>(d, e, f)</bold> results of the K-means algorithm;<bold> (g, h, i)</bold> result of binary images after pre-processing; <bold>(j, k, l) </bold>location of apple targets by using method presented in this paper (picking points marked with cyan “∅”); <bold>(m, n, o) </bold>location results after processed with unimproved method;<bold> (p, q, r) </bold>location results of apples using PIA method.
Location results of 30 single and unblocked apple images using the method described in this work.
Location results of single and blocked apple targets
In natural scenes, the localization of apples is always influenced by being blocked by branches and leaves, light intensity, shadows on the surface of apples and the ripeness of apples. Twenty single and blocked apple targets containing these four situations were selected to conduct the experiment. The main procedures were the same as above. The results of the location of single and blocked apples are shown in Table 2. Specifically, targets 1-12 were apples blocked by branches and leaves. Targets 13-15 were apples with shadows on their surfaces. Targets 16-18 were apples influenced by their maturity. Targets 19-20 were apples affected by light intensity. Some location results are shown in Suppl. Figs. S1 and S2 [pdfs online]. The apples were: blocked by leaves (Suppl. Fig. S1a-b), influenced by shadows and light intensity (Suppl. Fig. S1c), and affected by their maturity and light intensity (Suppl. Fig. S1d). Suppl. Fig. S2 [pdf online] shows location results with larger errors; despite this, the picking points of the apples could be extracted. Table 2 shows that the RMSE of the proposed method was 15.0, the average location error was 10.2°, and the average runtime was 9.2 ms. The smallest location error of the newly proposed method was only 0.1°, while the largest location error was 39.5°.
Location results of 20 single and blocked apple images using presented method.
Location results of apples captured in panoramas and images containing adjacent apples
Some apples in panoramas and images containing adjacent apples required reconstructing the contour for occluded areas that were too large. The main procedures for this were as follows,
Step 1: Transform the original image from the RGB color space to the L*a*b* color space, and then cluster the apple image using the K-means clustering algorithm.
Step 2: Binarize the clustered apple image.
Step 3: Pre-process the binary image, such as by a mathematical morphological operation and/or noise removal.
Step 4: Reconstruct the contour of adjacent and blocked apples (Song et al., 2013).
Step 5: Extract the convex hull of the apple, replace the apple contour with it and identify the apple symmetry axes using the moment of inertia algorithm to test the effectiveness of the improved method presented in this paper.
Step 6: Calculate the location error according to formula [11].
The experimental results and experimental data of images containing adjacent apples are shown in Suppl. Fig. S3 and Suppl. Table S1 [pdfs online], and those of the panoramas are shown in Suppl. Fig. S4 and Suppl. Table S2 [pdfs online]. As clearly shown in Suppl. Tables S1 and S2, the RMSE values of images containing adjacent apples and panoramas were 21.6 and 18.4, respectively, and the average location errors were 16.3° and 13.8°, respectively. The runtimes of these two types of images were determined by the number of apples and that of blocked apples contained in the image. From Suppl. Figs. S3 and S4, we can see that all of the apples in the images can be found and the picking points of the apples could be extracted.
DiscussionPerformance of the proposed method for single and unblocked apple targets
From Figs. 8 and 10, we can see the different performances of the PIA, improved and unimproved methods. As shown in Fig. 8, compared to the performance of the improved method, the obtained symmetry axes shown in Figs. 8q-t using the unimproved method and the extracted principal inertia axes utilizing the PIA method shown in Figs. 8u-x were rather biased. After analyzing the algorithm location error data of the 30 images in Figs. 10a,b in detail, we could find that the location error curve and runtime curve of the presented method were both under those of the other two methods. The average location error of the newly presented method was 80.6% and 73.8% lower than that of the PIA method (25.3°) and the original algorithm (18.7°), respectively. The accuracy of the proposed method improved by 80.7% and 71.7% when compared to the PIA method (32.8) and the unimproved method (22.3), respectively, in terms of RMSE. To further analyze the effectiveness of the algorithm presented in the paper, the runtime of the algorithm on 30 images was analyzed. The average runtime of the improved algorithm was 98.8% shorter than that of the PIA method (306.2 ms), and it was decreased by 96.6% when compared to the original algorithm (107.7 ms). Compared with these two methods, the runtime of the improved algorithm was drastically reduced, which indicated that the improved algorithm could improve the operational efficiency effectively. From Figs. 8 and 10a,b, it can be concluded that the pre-processing measures and convex hull algorithm smoothed and simplified the contour of apple, which could improve the accuracy of location precision.
Errors in location results (see Figs. 9, S2) might be caused by too strong or too weak light conditions, which could result in inaccurate segmentation during the color clustering process, thereby affecting the accuracy of extracting the symmetry axes. In detail, the light condition on the lower-left corner of target 3 in Fig. 9a was too dim, which led to mistaking it for the background, and the wrong contour extraction occurred when it was clustered. In Fig. 9b, the dim light conditions and lack of red in some areas of target 4 resulted in inaccurate contour extraction. In Fig. 9c, target 7 was incorrectly clustered due to overly dim light and overly strong light in some areas. The area where the light was too strong was corrected by image pre-processing, while the overly dim light resulted in incorrect classification when it was clustered.
Although the location error of the presented algorithm is obvious for some apple targets, the location error of these apple targets using the proposed algorithm is lower than that of the PIA method and the unimproved algorithm.
Analysis of the location of single and blocked apple targets
A comparison of the performance of the PIA method, the unimproved method and the presented method is shown in Figs. 10c,d. From Fig. 10c,d, the location error curve and runtime curve of the presented method were under those of the other two methods, which indicates that the proposed method was effective. Looking at the RMSE of these three methods, we find that the present method (RMSE=15.0) was a little better than the unimproved method (RMSE=19.3), while it was much better than the PIA method (RMSE=33.2). The average location error (10.2°) and average runtime (9.2 ms) of the proposed method were much smaller than those of the unimproved method and the PIA method. The results showed that the location accuracy was increased by 22.3%, the average location error was decreased by 36.3%, and the average runtime was decreased by 87.1% when compared to the unimproved method. When compared to the PIA method, the accuracy of the proposed method was improved by 54.8% and the average location error of the presented method was decreased by 67.9%. The improved method was more efficient in terms of runtime, which was 96.6% shorter than that of the PIA method. From the runtime of these methods, it can be concluded that the pre-processing measure and convex hull algorithm could simplify the complexity of the algorithm. As clearly shown in Fig. 10c, the proposed method was better than the PIA method. However, it was worse than the unimproved method in some cases (target 7, target 13, target 18 and target 20 in Table 2). The reason was that the convex hull of an apple cannot express the region of the apple accurately because of the too large block area, immaturity, light intensity, shadows on the apple and background factors (details shown in Fig. S2).
Comparison of the PIA method, unimproved method and improved method when processing 30 (left) or 20 (right) single and unblocked apple images. <bold>(a, c) </bold>Comparison of the location error of the three methods; <bold>(b, d) </bold>comparison of the runtime of the three methods.
Location of apples captured in panorama and images containing adjacent apples
For images containing adjacent apples, the entire contour of some apples could not be extracted because they were being blocked by adjacent apples or leaves, and thus, the contour of these apples should be reconstructed. Though there were location errors of reconstruction, the apple targets could be located. Location errors of some unblocked apple targets were larger (targets 3 and 11 in Suppl. Fig. S3 [pdf online]). This was due to the poor symmetry of these apples. For apples captured in panoramas, all apples in the images could be found. It was precise in locating some of the apples. The smallest location error was 0.0°. There were also some apples with larger location errors: the largest location error was 38.1°. Some of them were because of poor symmetry. Others were because the convex hull of the apple could not express the region of the apple accurately, which resulted from branches and background factors, light intensity, being blocked by leaves and/or the maturity of the apple. Details are shown in Suppl. Fig. S4 [pdf online].
For these two types of apple images, the runtime was slightly longer; this resulted from the execution loop of every apple and the reconstruction of the blocked region of the blocked apples in the images.
In summary, this paper utilized the convex hull theory in combination with the K-means clustering algorithm and mathematical morphology to replace the contour curve of single and unblocked apple targets with the convex hull, thereby improving the precision of the target localization, enhancing the efficiency of operation, and simplifying the computational complexity of the original algorithm. The moment of inertia method was used to extract symmetry axes of apple targets, which could better locate the picking points of apples. The correctness and the effectiveness of the algorithm presented in this paper showed that the improved algorithm was feasible for extracting symmetry axes and locating the picking points of apples. For occluded apple targets, though the apple targets could be located, the location result was not accurate enough because they were blocked by leaves, stems or other apples. Therefore, further study is needed to improve the accuracy of the location of occluded apple targets.
Acknowledgments
The authors would like to thank Leilei Niu (graduate student, College of Mechanical and Electronic Engineering, Northwest A&F University) and anonymous referees for their helpful comments and suggestions.
ReferencesArefiAMotlaghAMMollazadeKTeimourlouRFRecognition and localization of ripen tomato based on machine visionAust J Crop Sci201151011441149BulanonDMKataokaTOkamotoHHataSDevelopment of a real-time machine vision system for the apple harvesting robotSICE Annu Conf in SapporoAug 4-62004595598ChinchuluunRLeeWSBurksTFMachine vision-based Citrus yield mapping systemProc Fla State Hort Soc2006119142147FukushimaKKikuchiMSymmetry axis extraction by a neural networkNeuro- computing2006691618271836http://dx.doi.org/10.1016/j.neucom.2005.11.010GongJWHuangWYLuJLA new algorithm to estimate the symmetrical axis of a curve in data processingMeasurement Technique2001635GuoFCaoQXCuiYJNagataMFruit location and stem detection method for strawberry harvesting robotT CSAE200824108994JiménezARCeresRPonsJLA survey of computer vision methods for locating fruit on treesT ASAE200043619111920http://dx.doi.org/10.13031/2013.3096JimJJensenJRTullisJAObject-based change detection using correlation image analysis and image segmentationInt J Remote Sens2008292399423http://dx.doi.org/10.1080/01431160601075582LiangNGuoLYuYA symmetry detected method based on the minimal value of moment of inertiaMicroprocessors20093066264LuoMRCuiGRiggBThe development of the CIE 2000 color-difference formula: CIEDEColor Res Appl2000265340350http://dx.doi.org/10.1002/col.1049PlebeAGrassoGLocalization of spherical fruits for robotic harvestingMachine Vision Appl20011327079http://dx.doi.org/10.1007/PL00013271RajneeshBWonSLSaumyaSGreen citrus detection using fast fourier transform leakagePrecis Agric20131415970http://dx.doi.org/10.1007/s11119-012-9292-3RekikAZribiMBenjellounMBen HAA K-means clustering algorithm initialization for unsupervised statistical satellite image segmentationE-Learning in Industrial Electronics, 1st IEEE Int Conf20061116RemyEThielEExact medial axis with euclidean distanceImage Vision Comput2005232167175http://dx.doi.org/10.1016/j.imavis.2004.06.007SongHBHeDJPanJPRecognition and localization methods of occluded apples based on convex hull theoryT CSAE20122822174180SongHBZhangCDPanJPYinXSegmentation and reconstruction of overlapped apple images based on convex hullT CSAE2013293163168TanigakiKFujiuraTAkaseAImagawaJCherry-harvesting robotComput Electron Agr20086316572http://dx.doi.org/10.1016/j.compag.2008.01.018XiangRYingYBJiangHYPengYSThree-dimensional location of tomato based on binocular stereo vision for tomato harvesting robot5th Int Symp Advanced Optical Manufacturing and Testing Technologies, Int Soc for Optics and Photonics201076582Z76582ZXieZHXuYJiCYGuoXQZhuSXEstimation method of apple growing attitude based on computer visionT CSAM20124211154157YaoHDuanQLiDWangJAn improved K-means clustering algorithm for fish image segmentationMath Comput Model201358790798http://dx.doi.org/10.1016/j.mcm.2012.12.025YinHPChaiYYangSXSimonXMittalGSRipe tomato recognition and localization for a tomato harvesting robotic systemInt Conf of Soft Computing and Pattern RecognitionMelacca, TBD, Malaysia2009557562ZhangHMGaoMTZhangGMSymmetry axes search of 2D point set based on convex hull technologyComput Appl2010304905908ZhouQHHuangTWuHYLiZJLinXA new algorithm for finding convex hull with a maximum pitch of the dynamical base lineKnowledge Discovery and Data Mining, WKDD. First Int Workshop IEEE2008630634