<figure><img src="image_1.png" /></figure>

HAL
open science

# Detection of Overlapped Apples in Orchard Scene Using Improved K-means and Distance Least Square

Xia Xue, Zhou Guomin, Qiu Yun, Li Zhuang, Wang Jian, Hu Lin, Fan

Jingchao, Guo Xiuming

<figure><img src="image_2.png" /></figure>

## To cite this version:

Xia Xue, Zhou Guomin, Qiu Yun, Li Zhuang, Wang Jian, et al., Detection of Overlapped Apples in Orchard Scene Using Improved K-means and Distance Least Square. 11th International Conference on Computer and Computing Technologies in Agriculture (CCTA), Aug 2017, Jilin, China. pp.269-284, 10.1007/978-3-030-06137-1_25. hal-02124248

HAL Id: hal-02124248

https://inria.hal.science/hal-02124248

Submitted on 9 May 2019

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_3.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Detection of Overlapped Apples in Orchard Scene using Improved K-means and Distance Least Square

Xia Xue¹(✉), Zhou Guomin¹, Qiu Yun¹, Li Zhuang², Wang Jian¹, Hu Lin¹, Fan Jingchao¹, Guo Xiuming¹

¹ Institute of Agricultural Information, Chinese Academy of Agricultural Sciences, Beijing 10081 China (xiaxuecaas@126.com)

²Institute of Pomology, Chinese Academy of Agricultural Sciences, Xingcheng 125199 China

**Abstract.** Automatic detection of mature apples in a complex agricultural condition is still a challenge for an autonomous picking robot due to the influence from overlapping. In order to detecting overlapped apples in tree canopy using a low-cost camera, a robust apples detection and reconstruction approach based on improved K-means and distance least square algorithm was studied. Firstly, the region of potential apple objects was extracted by using improved K-means algorithm. Then, the contours of apples were obtained by utilizing Canny edge detection algorithm on the V component map and the intact contour of unobscured apple was separated from overlapped apples contour after Y-junction searching. Finally, the contour of obscured apple was reconstructed by use of the distance least square circle fitting algorithm. The proposed method was compared with Hough transform method and the experimental result indicated that the proposed method could get much better performance for overlapped apples detection than Hough transform method. Thus it could be concluded that the proposed method is available for robotic apple picking in overlapped fruits scene with low cost.

**Keywords:** apple; overlapped fruits; contour reconstruction; fruit detection; K-means; DLS

## 1 Introduction

Apple is one of the competitive agricultural products in China. In 2015, the planting areas of apples in China achieved more than 20 million hectares, and the yield of apples reached over 40 million tons which is the highest-yielding fruit in domestic. The workload of fruit operation like bagging and harvesting accounts for 40 percent of all workload in entire apple production cycle, and this work is still completed reliant on manual operation. However, labor shortage and increased labor costs in rural areas makes current human-based production pattern unable to meet the demand of apple production in large-scale[1]. Using robot to support fruit operation can not only boost the work efficiency, but also save the labor cost[2]. Therefore, introducing robots to replaced human labor for fruit operation is an inevitable
tendency in digitization and mechanization of modern orchards management[3]. The successful fruit operation depends on whether apple objects can be detected in correctly by visual system of the robot. Due to the unstructured characteristic of the grove, some disturbing factors that impacting the accuracy of apple detection are remained, in which fruits overlapping is a major influence factor and this is almost ubiquitous phenomenon in natural orchard condition. Hence the detecting overlapped apples has become a hit as well as difficulty[4].

Several studies have been carried out to detect overlapped objects and some progresses have been made[5, 6, 7, 8, 9]. Chen et al.[10] and Miao et al.[11] reported an approach merged region growing and improved watershed algorithms for overlapped citrus detection. This approach enhanced the segmentation accuracy of objects' edges while decreased the errors caused by over-segmentation of the traditional watershed algorithm. Xiang et al.[12] reported a method for overlapped tomato detection using curvature analysis and regression circle algorithm, and perfectly performance can be obtained when overlapped area was less than 25% of the area of fruits region. Wang et al.[13] explored a new method for overlapped ripe apples using K-means and Normalized cut. This method has a preferable performance for keeping the intact contour of unobscured apples, and improved general accuracy of the segmentation. Xie et al.[14] reported an approach combining concave point searching and random Hough transformation algorithm for overlapped peaches detection, and correct detection rate was 90%. Xu et al.[15] reported a detection method of two overlapped apples integrated snake active contour model and distance-based corner detection algorithm, which provides a brand-new ideal for the detection of overlapped fruits. Song et al.[16] reported a segmentation approach for overlapped apples based on convex-hull theory. The approach transformed concave point detection to salient point detection so as to complexity reduction of the detection algorithm. Lv et al.[17] realized the detection of overlapped apples using RHT algorithm on the image that add together binary image and saltation region generated by edge curvature detection. The approach has improved fruits' detection efficiency.

In these researches mentioned above, problems included long computation time of algorithm and lower accuracy of fruit reconstruction are remained main because of the morphological diversity of apple growth in natural environment which made various overlapped condition and adaptive difficulty of detection algorithm. For the better detection performance for overlapped apples, a method combined improved K-means and distance least square algorithm was proposed for detection and reconstruction of overlapped apples. Firstly, the region of potential apple objects was extracted by using improved K-means algorithm in L*a*b* color space. Secondly, the contour of apples was obtained by utilizing Canny edge detection algorithm on the V component map in HSV color space. Thirdly, the intact contour of unobscured apple was separated from overlapped apples contour through Y-junction detection. Finally, the contour of obscured apple was reconstructed by use
of the distance least square circle fitting algorithm.

## 2 Materials and methods

### 2.1 Image acquisition

For developing and testing proposed algorithm, images of apples in orchard were acquired in natural daylight environment using digital camera (EOS 6D, Canon) with a resolution of 5472×3648 pixels. Images were photoed randomly in October 2016 in apple orchard of institute of pomology of CAAS, Xingcheng, China. The Hanfu ripe apple was selected as the testing fruit variety. The purpose of this research develop a detection method for overlapped apples using color images, thus images were re-sized to 821×547 pixels utilizing the bi-cubic interpolation algorithm for computational convenience.

### 2.2 Detection of ROI of overlapped apples

#### 2.2.1 ROI segmentation using improved K-means

The segmentation of apple objects region is the primary task for detection of overlapped apples. Thus the K-means algorithm was used for ROI segmentation of apple objects, K-means algorithm is a partition-based unsupervised clustering algorithm. The algorithm takes error sum of squares and Euclidean distance as the clustering rule function and the similarity measurement, respectively, then searching the optimal partition of k clusters by means of the iterative computations[18]. Due to initial clustering center of traditional K-means algorithm applied complete random scheme, however, clustering results were most likely to be affected by the selection of initial clustering center and easily traps into local optima[19]. To solve this issue, a heuristic method for clustering center searching was introduced. This method takes the distance square between data points and near clustering center as the computing weight, and calculating optimal clustering center through iterative computation, then obtained globally optimal results[20]. The detailed steps are as follows:

(1) Given data set $X: X = \{X_1, X_2, \dots, X_i, \dots, X_j, \dots, X_n\}$, a data point was randomly selected from X as the initial clustering center $c_1$;

(2) Computing the distance square between every sample point and $c_1$, the distance vector is defined as

$$D_i^2 = \|X_i - c_1\|^2, \text{ where } X_i \in X$$

(3) Randomly selecting the next clustering center $c_2$ from X according to the Eq.(1)

$$\frac{D_i^2}{\sum_{j=1}^{n} \|X_j - c_1\|^2} \qquad (1)$$

In which $X_j \in X$

(4) Recalculating the distance vector based on Eq.(2)
$$D_i^2 = \min(\|X_i - c_1\|^2, \|X_i - c_2\|^2) \qquad (2)$$

(5) Repeat step(3) and step(4) until *k* optimal clustering centers are chosen.

(6) Searching the optimal partition based on *k* optimal clustering centers.

It is very important to set parameter *k* during the clustering progress. Due to the color of apples' surface are not uniform, fruits in image might be clustered into different category if *k* was too large and results segmentation error. Thus the parameter *k* = 3 in this study, and image can be clustered into fruits, stems and branches, and others. The image clustering segmentation was commonly performed in L*a*b* color space when using K-means algorithm because it is a well-defined color model that three components in L*a*b* space can described all sorts of colors human perceived. Due to images captured by the visual sensors belong to RGB color space, images need to transformed form RGB space to L*a*b* color space before K-means clustering. However, the transformation between two spaces cannot transformed directly because of their non-linear relation. So RGB color space needs to converted to XYZ color space firstly, and then L*a*b* color space can be converted from XYZ color space. The transformation formulas are as follow:

$$\begin{bmatrix} X \\ Y \\ Z \end{bmatrix} = \begin{bmatrix} 0.431 & 0.342 & 0.178 \\ 0.222 & 0.707 & 0.071 \\ 0.020 & 0.130 & 0.939 \end{bmatrix} \begin{bmatrix} R \\ G \\ B \end{bmatrix} \qquad (3)$$

$$L^* = \begin{cases} 116[Y/Y_n]^{\frac{1}{3}} - 16, & Y/Y_n > 0.008856 \\ 903.3[Y/Y_n], & Y/Y_n \le 0.008856 \end{cases} \qquad (4)$$

$$a^* = 500[f(X/X_n) - f(Y/Y_n)] \qquad (5)$$

$$b^* = 200[f(Y/Y_n) - f(Z/Z_n)] \qquad (6)$$

In which

$$f(t) = \begin{cases} t^{\frac{1}{3}}, & Y/Y_n > 0.008856 \\ 7.787t + 16/116, & Y/Y_n \le 0.008856 \end{cases} \qquad (7)$$

Where, $X_n$, $Y_n$, $Z_n$ are XYZ tristimulus values of reference white point, *t* is X, Y, Z to their corresponding reference white point ratio.

### 2.2.2 Fruits image de-noising

After clustering segmentation, the fruit's calyx in image could formed holes due to the obvious color differences between calyx and fruit surface. Besides, some stems and branches were still existed because the disturbance of varying sunlight, and formed image noise such as burrs isolated points or patches. To solve this issue, morphological processing approaches with the 3pixels-disk structuring element were used to reduced image noise. Utilizing Eq.(8), at first, to executing erosion operation to the image. Then, expanded object region by applied Eq.(9) to eliminate noise in image. Using flood-fill algorithm to filled the holes of apple's calyx in
processing image.

$$A \Theta B = \{x | (B)_i \subseteq A\} \qquad (8)$$

$$A \oplus B = \{x | [(B)_i \cap A] \neq \emptyset\} \qquad (9)$$

In which A is the processing image, B is the disk structuring element.

In addition, Given the pixel area of overlapped apples is considerably larger than image noise and is largest region in the image, regions that less than 1/5 largest region in the image were removed during the image de-noising.

## 2.3 Contour extraction and reconstruction of overlapped apples

It is found by observing that the contour of the unobscured apple was fully visible. Existing approaches, however, can usually only extracted the exterior outline of overlapped apples, and separated overlapped apples by connecting two concave points in overlapped area with a straight line, which leads to the loss of real edge in overlapped region and the lower accuracy of fruits detection. Therefore, a method that could keep the edge information of overlapped area is needed to boosted the accuracy of apples' detection.

### 2.3.1 Apples contour extraction using V component-based canny algorithm

Unlike single apple detection that do not consider the occlusion between fruits, separation of fruits was necessary operation when detecting overlapped apples. Although apples were overlapped, the intact contour of unobscured apple could be obtained and the missing contour of obscured apple could be fixed as long as contour information of apples can be detected.

Edge detection is an effective approach for contour tracing. The idea of the edge detection is that firstly highlighting the objects' edges in the image by using the edge enhancement operator, then the edge strength in intensity image were calculated, finally edge pixels were extracted by threshold setting. Due to contours were formed from the region that intensity abruptly changing, the contour can be extracted through differential operation of changing parts of the function. And in general, the first derivative of pixels was used to detection computing.

In first derivative operator, assuming intensity function of the image is $f(x, y)$,

where $(x, y)$ is the pixel coordination, then the gradient $g(x, y)$ and phase □□of

the location $(x, y)$ can be defined as Eq.(10)

$$g(x, y) = \sqrt{\left(\frac{\partial f}{\partial x}\right)^2 + \left(\frac{\partial f}{\partial y}\right)^2}, \theta = \arctan\left(\frac{\partial f}{\partial y} / \frac{\partial f}{\partial x}\right) \qquad (10)$$

Gradient $g(x, y)$ and phase

□ reflecting the amplitude and

variation, respectively.

The common edge detection operators include Roberts, Sobel, Prewitt, Kirsch, and Canny. The processing speed of Roberts operator is fast, but it is more vulnerable to
Gaussian noise because of the strategy that directly image difference calculation without smoothing process, which lead to unsatisfied accuracy of edge location. Sobel and Prewitt operators have better performance for edge extraction of low noise images, but feeble for detection of much noise images because of the high sensitivity. Kirsch operator are sensitive to incremental and have strong inhibition to image noise and better performance of edge detection, but extracted contours are thick and computing time is not acceptable. Detected edges by using Canny operator are thin and have better connection. The real weak edges could be detected more easily since details of objects are lucid and intact when using Canny operator. Therefore, Canny operator was used in this study to detect fruits' edge in the image.

Traditional Canny edge detection was commonly used with gray image of RGB image, but intensity of apples area in this gray image is uneven, which results much noise occurred and some long edge noise are difficult to remove. In V component of HSV space, the intensity of overlapped part of fruit image is more even and the edge gradient is more prominent. Therefore, using V component image in HSV space replaced the gray image of RGB image, then edges of apples were detected with Canny operator. The main steps of the processing were described as following:

(1) Converted RGB color space to HSV color space, and extract gray image from V component as the processing image.

(2) Smoothing image with the first derivative of two dimensional Gaussian function, which defined as

$$G(x, y) = \frac{1}{2\pi\sigma} \exp\left(-\frac{x^2 + y^2}{2\sigma^2}\right) \qquad (11)$$

The first directional derivative in a certain direction of $G(x, y)$ was

$$G_n = \frac{\partial G(x, y)}{\partial n} = n \nabla G(x, y) \qquad (12)$$

$$n = \begin{bmatrix} \cos \theta \\ \sin \theta \end{bmatrix} \qquad \nabla G(x, y) = \begin{bmatrix} \frac{\partial G}{\partial x} \\ \frac{\partial G}{\partial y} \end{bmatrix}$$

In which $n = \begin{bmatrix} \cos \theta \\ \sin \theta \end{bmatrix}$ is the direction vector, $\nabla G(x, y) = \begin{bmatrix} \frac{\partial G}{\partial x} \\ \frac{\partial G}{\partial y} \end{bmatrix}$ is the gradient vector.

(3) Gradient magnitude and direction of smoothed image $I(x, y)$ were obtained by computing finite difference of the first partial derivative with 2x2 neighborhood.

$E_x(x, y)$ and $E_y(x, y)$ are first partial derivatives of direction x and direction y, respectively. They are defined as Eq.(13) and Eq.(14)
$$E_x(x, y) = \frac{I(x, y+1) - I(x, y) + I(x+1, y+1) - I(x+1, y)}{2} \quad (13)$$

$$E_y(x, y) = \frac{I(x, y) - I(x+1, y) + I(x, y+1) - I(x+1, y+1)}{2} \quad (14)$$

(4) Take Eq.(12) into first derivative operator and calculated gradient magnitude and direction. Non-maxima suppression was applied to gradient magnitude, which is defined as Eq.(15)

$$N(x, y) = NMS[M(x, y), \xi(x, y)] \quad (15)$$

In which $N(x, y)$ is the image with non-maxima suppression, $M(x, y)$ is gradient magnitude, $\xi(x, y)$ is the area of non-maxima suppression.

(5) The edge array image was obtained after magnitude thresholding of non-maxima suppression. Dual threshold algorithm was applied in this computational process. $\tau_1$ and $\tau_2$ are two thresholds in edge detection while $\tau_1 > \tau_2$. Processing image $N(x, y)$ with these thresholds. Setting the intensity of pixels that value is less than $\tau_1$ as 0, and obtained edge image $T_1$. In a similar way, another edge image $T_2$ was obtained. $T_1$ was regarded as compensatory to connecting edge while $T_2$ was regarded as the basis image for the reason that $T_2$ has few fake edges while $T_1$ keeps more edge information.

The contours of the overlapped apples were extracted with Canny edge detection algorithm, but the small edge noise were generated on fruits areas by reason of the uneven illumination. Therefore, a method that calculating numbers of edges pixels was utilized to remove noise edges contained less pixels and to keep fruits contour contained more pixels.

### 2.3.2 Separation of apples contour based on Y-junction detection

For the better detection accuracy, overlapped apples need to be separated into individual fruit. Due to the color uniformity, pixels noise and similar intensity of overlapped region in original image, the fruits' contour likely to be disconnected that affect the accuracy of fruit detection. Thus, dilation operation with 5-pixels disk structural element was used to connecting the broken contour.

Although contour has connected after dilation operation, but it is not single pixel level yet. Edge thinning can make contour to be the single pixel level, which benefit for the subsequent fruit separation[21]. The steps of edge thinning are as follow:

(1) Given a pixel point on the edge is P and pixel value is 1, then $X_i(i=1,2,...,8)$ are the values of the P-centered 8 neighbors pixels, as show in Fig.1.

<table><tr><td>X<sub>4</sub></td><td>X<sub>3</sub></td><td>X<sub>2</sub></td></tr><tr><td>X<sub>5</sub></td><td>P</td><td>X<sub>1</sub></td></tr></table>
<table><caption>Fig.1. The pixel values of the P-centered 8 neighbors</caption><tr><td>X<sub>6</sub></td><td>X<sub>7</sub></td><td>X<sub>8</sub></td></tr></table>

(2) Traverse all edge pixels according to the rule 1 that is setting pixel P as 0 if and only if the criterions C<sub>1</sub>, C<sub>2</sub>, C<sub>3</sub> are all met. Criterions C<sub>1</sub>, C<sub>2</sub>, C<sub>3</sub> are defined as follow:
Criterions C<sub>1</sub>,

$$X_H(p) = 1 \tag{16}$$

Where

$$X_H(p) = \sum_{i=1}^{4} b_i \\ b_i = \begin{cases} 1, & \text{if } X_{2i-1} = 0 \text{ and } (X_{2i} = 1 \text{ or } X_{2i+1} = 1) \\ 0, & \text{otherwise} \end{cases}$$

Criterions C<sub>2</sub>,

$$2 \le \min\{n_1(p), n_2(p)\} \le 3 \tag{17}$$

Where

$$n_1(p) = \sum_{k=1}^{4} X_{2k-1} \lor X_{2k}$$

$$n_2(p) = \sum_{k=1}^{4} X_{2k} \lor X_{2k+1}$$

Criterions C<sub>3</sub>,

$$(X_2 \lor X_3 \lor X_8) \land X_1 = 0 \tag{18}$$

(3) Re-traverse all edge pixel points on the basis of the results of the first traverse according to the rule 2 that is setting pixel P as 0 if and only if the criterions C<sub>1</sub>, C<sub>2</sub>, C<sub>4</sub> are all met. Criterions C<sub>4</sub> is defined as follow:

$$(X_6 \lor X_7 \lor X_4) \land X_5 = 0 \tag{19}$$

For the separating fruits in correctly, the chief mission is extracting the intact contour of the unobstructed apple. It is found through observation that Y-like junctions are existed on the contour of overlapped area of the apple fruits. And the contour of overlapped apples can be separated into individual apple by detecting this Y-like junctions. The steps of detecting Y-like junctions are as follow:

(1) Given the pixels values of the contour is 1 and that of background is 0. Then traverse all pixels of the contour, and for each pixel on the contour, calculate the sum value of it's 3×3 neighbors pixels. This sum value is defined as:

$$T = \sum_{i=1}^{8} d_i \tag{20}$$
In which, $d_i$ presents the value of the i-th pixel point.

(2) If $T \ge 3$, then regarded the current point as Y-like junction. And delete the values of Y-like junction pixel and its 3×3 neighbors pixels, then the separated contours of apples were obtained.

(3) Given $P_0(x_0, y_0)$ is the center point of a contour of the apple, and $P_1(x_1, y_1)$, $P_2(x_2, y_2)$ are endpoints of the contour. Z is the tangent line crossed $P_0$. Two perpendicular line crossed endpoints perpendicular to Z and intersect at point $P_3(x_3, y_3)$ and point $P_4(x_4, y_4)$. Calculating curve direction of each contour of apples according to the following rules, as shown in Table 1, the contour of each apple was contained after grouped contours that opposite direction.

<table><caption>**Table 1.** Rules of curve direction calculation</caption><thead><tr><th>No.</th><th>Rules</th><th>Curve direction</th></tr></thead><tbody><tr><td>1</td><td>x<sub>1</sub>&lt;x<sub>0</sub>, x<sub>2</sub>&lt;x<sub>0</sub>, y<sub>1</sub>&lt;y<sub>0</sub>&lt;y<sub>2</sub>,<br>x<sub>1</sub>&lt;x<sub>3</sub>, y<sub>1</sub>=y<sub>3</sub>, x<sub>2</sub>&lt;x<sub>4</sub>, y<sub>2</sub>=y<sub>4</sub></td><td>Left opening curve</td></tr><tr><td>2</td><td>x<sub>1</sub>&gt;x<sub>0</sub>, x<sub>2</sub>&gt;x<sub>0</sub>, y<sub>1</sub>&gt;y<sub>0</sub>&gt;y<sub>2</sub>,<br>x<sub>1</sub>&gt;x<sub>3</sub>, y<sub>1</sub>=y<sub>3</sub>, x<sub>2</sub>&gt;x<sub>4</sub>, y<sub>2</sub>=y<sub>4</sub></td><td>Right opening curve</td></tr><tr><td>3</td><td>x<sub>1</sub>&gt;x<sub>0</sub>&gt;x<sub>2</sub>, y<sub>1</sub>&lt;y<sub>0</sub>, y<sub>2</sub>&lt;y<sub>0</sub>,<br>x<sub>1</sub>=x<sub>3</sub>, y<sub>1</sub>&lt;y<sub>3</sub>, x<sub>2</sub>=x<sub>4</sub>, y<sub>2</sub>&lt;y<sub>4</sub></td><td>Up opening curve</td></tr><tr><td>4</td><td>x<sub>1</sub>&lt;x<sub>0</sub>&lt;x<sub>2</sub>, y<sub>1</sub>&gt;y<sub>0</sub>, y<sub>2</sub>&gt;y<sub>0</sub><br>x<sub>1</sub>=x<sub>3</sub>, y<sub>1</sub>&gt;y<sub>3</sub>, x<sub>2</sub>=x<sub>4</sub>, y<sub>2</sub>&gt;y<sub>4</sub></td><td>Down opening curve</td></tr><tr><td>5</td><td>x<sub>1</sub>&gt;x<sub>0</sub>, y<sub>2</sub>&lt;y<sub>0</sub>,<br>x<sub>1</sub>&gt;x<sub>3</sub>, y<sub>1</sub>&lt;y<sub>3</sub>, x<sub>2</sub>&gt;x<sub>4</sub>, y<sub>2</sub>&lt;y<sub>4</sub></td><td>Up-right opening curve</td></tr><tr><td>6</td><td>x<sub>1</sub>&lt;x<sub>0</sub>, y<sub>2</sub>&gt;y<sub>0</sub>,<br>x<sub>1</sub>&lt;x<sub>3</sub>, y<sub>1</sub>&gt;y<sub>3</sub>, x<sub>2</sub>&lt;x<sub>4</sub>, y<sub>2</sub>&gt;y<sub>4</sub></td><td>Down-left opening curve</td></tr><tr><td>7</td><td>x<sub>2</sub>&gt;x<sub>0</sub>, y<sub>1</sub>&gt;y<sub>0</sub>,<br>x<sub>1</sub>&gt;x<sub>3</sub>, y<sub>1</sub>&gt;y<sub>3</sub>, x<sub>2</sub>&gt;x<sub>4</sub>, y<sub>2</sub>&gt;y<sub>4</sub></td><td>Down-right opening curve</td></tr><tr><td>8</td><td>x<sub>2</sub>&lt;x<sub>0</sub>, y<sub>1</sub>&lt;y<sub>0</sub>,<br>x<sub>1</sub>&lt;x<sub>3</sub>, y<sub>1</sub>&lt;y<sub>3</sub>, x<sub>2</sub>&lt;x<sub>4</sub>, y<sub>2</sub>&lt;y<sub>4</sub></td><td>Up-left opening curve</td></tr></tbody></table>

### 2.3.3 Contour reconstruction of obscured apple based on distance least square circle fitting algorithm

For contour completion in overlapped region, Distance Least Squares (DLS) algorithm was applied to reconstruct the contour of obscured apple. DLS is a mathematical optimization method that searching the best function matching of the data through minimizes the sum of the squares of the residuals. DLS algorithm can fit a serial of points, $\{P_i(x_i, y_i)_{i=1,2,...,N}\}$, on the fruit contour to a circle. Defined fitting residuals function as the quadratic sum $E$ of distances that from each point $P_i$ on the contour to the fitting circle. The quadratic sum $E$ was defined as Eq.(21)

$$E = \sum_{i=1}^{N} (\rho_i - R_c)^2 \qquad (21)$$
In which, $\rho_i = \|P_i - P_c\| = \sqrt{(x_i - x_c)^2 + (y_i - y_c)^2}$, $\rho_i$ is the distances that from each point on the contour to the center of fitting circle $P_c(x_c, y_c)$; $R_c$ is the radius of the fitting circle.

During the fitting process with traditional DLS algorithm, the fitting results are more likely to be affected by outliers. Thus the weight function was introduced to decrease interference from the outliers. The main steps of the weight function-based DLS algorithm were firstly fitting a circle with DLS algorithm, and then according to the distances that from each point on the contour to this circle, calculating the corresponding weight of each point that used in subsequent iteration process. For the distant outliers assigned small enough weights, Tukey weight function was chosen as the weight function of DLS algorithm. Tukey weight function was defined as Eq.(22)

$$ \omega(\delta_i) = \begin{cases} [1 - (\frac{\delta_i}{\tau})^2]^2 & (|\delta_i| \le \tau) \\ 0 & (|\delta_i| > \tau) \end{cases} \qquad (22) $$

In which, $\tau$ is clipping factor that determined which points could be the outliers; $\delta_i$ is the distances that from each point on the contour to the fitting circle.

calculating fitting residuals function by minimize iterative computation under the Eq.(23)

$$ E = \sum_{i=1}^{N} \omega_i (\rho_i - R_c)^2 \qquad (23) $$

# 3 Results and discussion

## 3.1 ROI segmentation and de-noising

Fig.2 shows an example of the result of K-means clustering segmentation. Fig.2(a) shows the re-sized original image. Fig.2(b) shows the segmented image by improved K-means clustering algorithm. It can be seen that the pixel region of apples has been extracted. And improved K-means algorithm has a good performance for segmentation of red mature apples.

<figure><img src="image_4.png" /><figcaption>Fig. 2. Example of the result of K-means clustering segmentation: (a) the re-sized original image, (b) the segmented image by using improved K-means clustering algorithm.</figcaption></figure>

As shown in the Fig.2(b), some image noise such as holes and patches of stems and
leaves were existed after clustering segmentation. For the better detection
performance, the image needs to be further treated. Morphological processing
algorithm was utilized for holes filling and patches noise removing. For keeping
details of the overlapped region of apple image, the processed binary image has been
converted into color image. Fig.3 shows the results of an example of image de-
noising. Fig.3(a) shows binary image of Fig.2(b). Fig.3(b) shows the results of
morphological processing and holes filling. Fig.3(c) shows the converted color
image. It can be seen that patches noise was completely eliminated by using
morphological processing while holes were perfectly filled by using flood-fill
algorithm. Through conversion between binary image and color image, the color
information of overlapped region in apples image were remained, which was
beneficial for the subsequent processing.

<figure><img src="image_5.png" /><figcaption>**Fig. 3.** An example of the results of image de-noising: (a) the binary image of Fig.2(b), (b) the results of morphological processing and holes filling, (c) the converted color image.</figcaption></figure>

**3.2 Apples contour extraction and individual apple contour separation**

Fig.4 shows an example of the result of edge detection with Canny operator on the image of V component. It is observed that the contours of overlapped apples were extracted, but many short edges were existed, which lead to some image noise. Through edge de-noising, short edges that have less pixels were removed while long edges that have more pixels were kept. Fig.5 shows the result of edge de-noising. It can be seen that the outlines of the overlapped apples were extracted, and the largely intact contour of the unobscured apple was extracted too, which illustrated that V component-based Canny edge detection have preferable capacity to kept edge information of apples' overlapped area.

<figure><img src="image_6.png" /><figcaption>Fig. 4. Result of edge detection.

Fig. 5. Result of edge de-noising.

Fig.6 shows the procedure of contour separation of overlapped apples. Fig.6(a) shows the result of V component-based Canny edge detection. In this image, the contour of unobscured apple has broken and have not formed closed contour. Fig.6(b) shows the result of contour connection by using proposed method. It can be seen that</figcaption></figure>
the broken contour has been connected. Contours of apples were thinned firstly in order to searching Y-like junction, and pixels on the area of Y-like junction were deleted and the results of Y-like junction searching and removing were show as Fig.6(c) and Fig.6(d). It can be seen that the Y-like junctions of the contour were detected and removed in correctly. Curve direction of the contours were calculated by the above-mentioned steps and grouped together contours that curve direction were opposite, then the contour of the unobscured apple was obtained. Due to this contour is not a closed contour, morphological dilation and edge thinning were used to connect and thin contours of the unobscured apple, and the result was show as Fig.6(e). It can be seen that the complete contour of unobscured apple was extracted. These results shows that the proposed method was effective for keeping complete contour pixels of the unobscured apple. Fig.6(f) shows the contour of unobscured apple. It can be seen that partly contour of the apple object was loss and further processing is needed.

<figure><img src="image_7.png" /><figcaption>**Fig. 6.** Example of the results of contour separation of overlapped apples: (a) result of V component-based Canny edge detection, (b) result of contour connection, (c) result of the area of Y-like junction, (d) result of area deletion of Y-like junction, (e) complete contour of the unobscured apple, (f) the contour of the obscured apple.</figcaption></figure>

### 3.3 Contour reconstruction of the obscured apple

Fig.7 shows an example of the result of contour reconstruction with improved DLS algorithm for obscured apple object. In the result image, the white contour was the original contour of the obscured apple, and the blue contour was the reconstructed contour of the obscured apple. It can be seen that the reconstructed contour has
basically matched with the original contour of the obscured apple.

<figure><img src="image_8.png" /><figcaption>**Fig. 7.** Example of the result of contour reconstruction of the obscured apple with DLS.</figcaption></figure>

**3.4 Methods validity and analysis**

In order to verify the validity of the method, circular Hough transformation (CHT) was used in comparison with proposed method. Fig. 8 shows the result of methods comparison. Fig. 8(a) shows the result of detection of overlapped apples with CHT method. Fig. 8(b) shows the result of detection of overlapped apples with proposed method. It can be seen that the major detection error was generated because the big deviation of CHT fitting while proposed method has better performance of apples detection. Proposed method can not only keep complete contour of the unobscured apple in overlapped apples, but also reconstruct obscured apple with better result.

<figure><img src="image_9.png" /><figcaption>**Fig. 8.** Results of comparison between CHT method and proposed method: (a) result of detection of overlapped apples with CHT method, (b) result of detection of overlapped apples with proposed method.</figcaption></figure>

**4 Conclusion**

An approach to detecting overlapped apples on colour images was developed. To use information of shape and colour, K-means, Canny operator, Y-junction searching and DLS were implemented. Multiple detections were integrated for the final result. Using orchard scene images, experiments were conducted and performance of method were evaluated. K-means algorithm have potential for extracting ROI of overlapped apples in natural scenes which contains different visual objects due to complex colour and structure of the leaves, branches and other objects. It can be concluded that Canny operator and Y-junction searching algorithm are effective ways to traced contours of overlapped apples and separated individual apple from region of overlapped apples with complete contours, which benefit for detection accuracy improvement. The missing contour of the obscured apple were reconstructed by circular fitting with DLS algorithm. Through a comparison between CHT method and proposed method, it can be concluded that proposed
method has higher accuracy for the detection of overlapped apples.

**Acknowledgements.** This work was supported by a grant from the National High-tech R&D Program of China (863 Program No.2013AA102405) and Agricultural Science and Technology Innovation Project of Chinese Academy of Agricultural Sciences (Project No. CAAS-ASTIP-2016-AII).

**References**

1. Zhou G M. Research and development of digital orchard in China[J]. Agriculture Network Information, 2012(1):10-12.

2. Lu J, Wang X F, Hou D J. Development of Machine Vision System for Fruit Harvesting Robots[J]. Hubei Agricultural Sciences, 2012, 51(21):4705-4708.

3. Zhou G M. Application Situation and Outlook of Digital Orchard[J]. Agricultural Outlook, 2015(1):10-12.

4. Feng J, Wang S, Liu G, et al. A separating method of adjacent apples based on machine vision and chain code information[C]//International Conference on Computer and Computing Technologies in Agriculture. Springer, Berlin, Heidelberg, 2011: 258-267.

5. Xun Y, Chen X, Li W, et al. Automatic recognition of on-tree apples based on contour curvature [J]. Journal of Jiangsu University (Natural Science Edition), 2007, (28)6: 461-464.

6. Qiang L, Cai J R, Zhao J W, et al. Real-time recognition of citrus on trees in natural scene.[J]. Transactions of the Chinese Society for Agricultural Machinery, 2010, 41(2):185-188+170.

7. Nasiri F, Glozarian M R, Akhani M H. Development of intersection circle method for detecting and estimating the number of near-spherical clustered citrus fruits in robotic harvesting[C]// International Conference on Sustainable Development With a focus on Agriculture, Environment and Tourism. 2015.

8. Yamamoto K, Guo W, Yoshioka Y, et al. On plant detection of intact tomato fruits using image analysis and machine learning methods[J]. Sensors, 2014, 14(7): 12191-12206.

9. Zeng Q, Liu C, Miao Y, et al. Non-destructive measurement of diameter of overlapping grape fruit based on morphological image processing[J]. Transactions of the Chinese Society of Agricultural Engineering, 2009, 25(9): 356-360.

10. Chen Y, Lee W. Identification and Determination of the Number of Overlapping Citrus Fruit in Natural Outdoor Conditions[C]//2014 Montreal, Quebec Canada July 13-July 16, 2014. American Society of Agricultural and Biological Engineers, 2014: 1.

11. Miao Z H, Shen Y C, Wang X H, et al. Research on the optimized image processing algorithm of overlapping fruits in natural environment[J]. Transactions of the Chinese Society for Agricultural Machinery, 2016, 47(6): 21-26.

12. Xiang R, Jiang H, Ying Y. Recognition of clustered tomatoes based on binocular stereo vision[J]. Computers and electronics in agriculture, 2014, 106: 75-90.

13. Wang D D, Xu Y, Song H B, et al. Fusion of K-means and Ncut algorithm to realize segmentation and reconstruction of two overlapped apples without blocking by branches
and leaves[J]. Transactions of the Chinese Society of Agricultural Engineering, 2015, 31(10): 227-234.

14. Xie Z H, Ji C Y, Guo X Q, et al. Detection and Location Algorithm for Overlapped Fruits Based on Concave Spots Searching[J]. Transactions of the Chinese Society for Agricultural Machinery, 2011, 42(12):191-196.

15. Xu Y, Li Y H, Song H B, et al. Segmentation method of overlapped double apples based on Snake model and corner detectors[J]. Transactions of the Chinese Society of Agricultural Engineering, 2015, 31(1): 196 - 203.

16. Song H B, Zhang C D, Pan J P, et al. Segmentation and reconstruction of overlapped apple images based on convex hull[J]. Transactions of the Chinese Society of Agricultural Engineering, 2013, 29(3): 163 - 168.

17. Lv J D, Wang F, Ma Z H, et al. Yellow Apple Recognition Method under Natural Environment[C]//Intelligent Human-Machine Systems and Cybernetics (IHMSC), 2015 7th International Conference on. IEEE, 2015, 1: 46-49.

18. Yang X T, Sun W J, Li M, et al. Water droplets fluorescence image segmentation of cucumber leaves based on K-means clustering with opening and closing alternately filtering[J]. Transactions of the Chinese Society of Agricultural Engineering, 2016, 32(17): 136 - 143.

19. Xu L M, Lü J D. Bayberry image segmentation based on homomorphic filtering and K-means clustering algorithm[J]. Transactions of the Chinese Society of Agricultural Engineering, 2015, 31(14): 202 - 208.

20. Cen Z Y, Li B, Tian L F. High dimensional transfer function design based on K - Means++ for volume visualization[J]. Journal of Computer Applications, 2012, 32(12):3404-3407.

21. Lam L, Lee S W, Suen C Y. Thinning methodologies-a comprehensive survey[J]. IEEE Transactions on pattern analysis and machine intelligence, 1992, 14(9): 869-885.