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

HAL
open science

# A Separating Method of Adjacent Apples Based on Machine Vision and Chain Code Information

Juan Feng, Shengwei Wang, Gang Liu, Lihua Zeng

► To cite this version:

Juan Feng, Shengwei Wang, Gang Liu, Lihua Zeng. A Separating Method of Adjacent Apples Based on Machine Vision and Chain Code Information. 5th Computer and Computing Technologies in Agriculture (CCTA), Oct 2011, Beijing, China. pp.258-267, 10.1007/978-3-642-27281-3_32. hal-01351818

HAL Id: hal-01351818

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

Submitted on 4 Aug 2016

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_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# A Separating Method of Adjacent Apples Based on Machine Vision and Chain Code Information*

Juan Feng¹,², Shengwei Wang¹,³, Gang Liu¹**, and Lihua Zeng²

1. Key Laboratory of Modern Precision Agriculture System Integration Research, Ministry of Education, China Agricultural University. Beijing 100083, China

2. College of Information Science & Technology, Agricultural University of Hebei. Baoding, 071001, China

3. College of mathematics and information science, Northwest Normal University of Gansu. Lanzhou, 730070, China

**Abstract.** Fruit location is an important parameter for apple harvesting robot to conduct picking task. However, it is difficult to obtain coordinates of each apple under natural conditions. One of the major challenges is detecting adjacent fruits accurately. Previous studies for adjacent detection have shortcomings such as vast computation, difficulty in implementation and over-segmentation. In this paper, we propose a novel and effective separating method for adjacent apples recognition based on chain code information and obtain the centroid coordinates of each fruit. Firstly, those valid regions of fruit are extracted by pre-processing the initial image. Secondly, chain code information is obtained by following the contour of extracted regions. Thirdly, through observing the changing law of chain code difference and adopting local optimum principle, concave points are found. Finally, the best point pairs are determined with different matching principles, and those adjacent apples are separated exactly. The experimental results show that the average rate of successful separation is greater than 91.2% with the proposed method, which can meet the requirements of applications in harvesting robots.

**Keywords:** Separating method, Chain code difference, Concave point, Match

* The research was financially supported by National Natural Science Foundation(31071333)

** Corresponding author; Email: pac@cau.edu.cn
# 1 Introduction

Apple harvesting robot is one of important research and application fields in agriculture, the accurate and automatic recognition of fruit is part of its primary task [1] [2] [3]. In the process, multi-fruit adjacent recognition is more difficult than the others, because the adjacent region is apt to be considered as a whole, and centroid coordinates acquired are not the ones of single fruit. In this case, Not only is recognition rate affected, but also fruit may be damaged by hard manipulator and its quality can be affected. How to recognize centroid coordinates of each apple is a problem not satisfactorily resolved yet, due to the complexity of environment.

In the research of adjacent objects separation, many scholars have put forward different methods, Such as mathematics morphological operation [4] [5] [6], improved watershed algorithm [7], and active contour model tracking algorithm [8], etc. However, there are some obvious shortcomings in these algorithms, including a need to track the process of calculation every time, computation is vast, the demand of computer software and hardware is higher, and results often appear over-segmentation. Other scholars have studied unique brightness information within adjacent region to separate the fruit [9], but the brightness difference on the surface of fruit is an indispensable factor. Edge concave points split touching objects are widely used in the field of cell segmentation [10]. Its main advantage is in a faster processing speed. Extracting and matching those concave points are two important aspects. Using the method for separating adjacent fruit has never been reported before. Under natural conditions, noises, branches and leaves make fruit boundary uneven, and the adjacent fruit recognition in real time also need to be taken into account, in this way, conventional method is not applicable.

This paper presents a new separating method of adjacent apples based on machine vision and chain code information. It consists of six main steps: extraction of valid region, acquirement of chain code information, computation of chain code difference between discrete points, selection of concave points referring to given thresholds, match of those points according to different principles, determination of the separating point pairs and realization of fruit separation. The experimental results show that method is simple, effective, accurate and ideal for separating adjacent
apples.

# 2 Materials and Methods

## 2.1 Materials

In this study, the cultivar of apple was Fuji. A digital camera (DH-HV3130UC, CMOS color camera) was selected and shooting distance was 1.5m. A laptop was used to program and drive the camera to acquire the RGB images. Image frames were 512×512 pixels in the BMP format. The software for image processing was MATLAB7.0.

## 2.2 Valid Region Extraction

Observing those apple pictures taken from natural environment, the color of ripe fruit is red while most of background is green. Both ends of a component of Lab color space are just the two colors. Therefore, the model was used for segmentation. The component can be matched by a non-linear combination of tricolor (Red, Green and Blue) [11]. The transformational relationship is known as Eq. (1).

$$a=500[1.006(0.607R+0.174G+0.201B)^{1/3}-(0.299R+0.587G+0.114B)^{1/3}] \quad (1)$$

<figure><img src="image_3.png" /><figcaption>**Fig. 1.** Filtering the apple image (a) Original image, (b) Blurring image</figcaption></figure>

Due to the influence of natural luminance, some objective colors aren't red, which results in losing some pixels after image segmentation. In order to reduce the effect, a
Gaussian lowpass filter was used to blur the initial image [12]. An example is displayed in Fig.1. Then a component was used to separate fruits from background. OTSU is regarded as an optimal means for auto threshold selection, it was used here to convert filtered image to binary form [13]. Medium value filter and area threshold were employed to remove noises.

The size of each ripe fruit is approximate and its shape is close to circle. When shooting distance is fixed, the size of fruits located the same distance on the image is similar. Calculating the sum of pix in many single-fruit regions, average area of fruit is obtained; Rotating single fruit region to find maximal width of all external rectangles and treating the width as average diameter of apple. By means of these methods, *S*<sub>threshold</sub> and *D*<sub>threshold</sub> were calculated, which are both a vital requirement of region extraction and constrain separating. It has been validated using data, finding that best value was obtained when *S*<sub>threshold</sub> was set at 5800 and *D*<sub>threshold</sub> was set at 97. Every area in the binary image was calculated. There was a multi-fruit adjacent region if its area value was greater than *S*<sub>threshold</sub> and the region was kept. On the contrary, there was a single apple and the region should be deleted by way of turning its gray value into zero [14].

From the above process, adjacent region on the apple image was extracted, which was called valid region. Speeds of separation and centroid coordinates determination would be accelerated.

## 2.3 Separating Method

<figure><img src="image_4.png" /><figcaption>**Fig. 2.** Procedure of separation (a) Valid region image (b) Concave points image (c) Separated image (d) Centroid coordinates image</figcaption></figure>

Fig.2a shows that ideal cut-points always locate the position of concave points for realizing apples separation. Therefore, it is significant that concave points are
extracted accurately. There are a lot of methods used for detecting concave points. This paper exploits an idea based on boundary curvature to detect, because curvature usually indicates the curving degree of border well. However, discrete curve is discontinuous and non-differentiable, it is difficult to calculate the curvature directly. Using the slope-difference of adjacent boundary line to describe curvature of line segment intersection proves to be reasonably effective [15].

This Freeman chain code represents a chain as a sequence of direction codes from one pixel to the adjacent one. This code is highly effective for compression of line images. According to the contour information of valid region from the boundary trace, chain code is obtained [16]. The common eight-direction chain code for the representation of line-drawing data has low precision, because one difference equals to 45° [17]. The concept of average chain code is introduced, which describes the direction of line approximately, and can be replaced by chain code sum if the number of points involved is fixed. Sum(i) denotes chain code sum and is given as Eq.2.

$$ Sum(i) = A(i) + A(i-1) + \cdots + A(i-n+1) \quad (i=1, 2, \cdots, n) \quad (2) $$

Where A(i) denotes absolute chain code of current point, specific procedure can be found in [18]. A local boundary is similar to straight line, so its tangent direction(slope) can be figured by the absolute chain code sum of n sequential points. Selecting n=3 means the whole circle being divided into 24, one difference equals to 15°, therefore, the accuracy of direction judgment improves greatly. Diff(i) denotes the difference of chain codes sum between the n sequential points ingoing and outgong, and is shown as Eq.(3). The value is proportional to curvature, which indicates the direction of boundary exactly and its positive and negative describes the convexo-concave of concerns. If the boundary is clockwise, those positive chain code difference shows concave points, while those negative shows convex points. The graph of Sum(i) and Diff(i) is shown as Fig.3.

$$ Diff(i) = Sum(i+n) - Sum(i) \quad (i=1, 2, \cdots, n) \quad (3) $$

In order to calculate an arc length of boundary, a concept of accumulated length is introduced, which indicates a length between starting and current point. Therefore, arc length between any two points is equal to difference of each accumulated length. For briefness, a step of level and vertical direction was set at 1, while other steps were set at 1.5. The corresponding rate of arc and chord was obtained by calculating distance and accumulated length between two points.

The boundary of the digital image is not absolutely smooth, and corners are mainly
points, whose chain code differences do not belong to the interval [-1,2]. For the sake of finding concave points of adjacent fruit boundary, those points corresponding to big curvature are extracted, where $Diff(i)>M(i=1,2, \cdots, n)$ is a requirement. After repeated test, $M=2.5$ was proved to be the best threshold. Chain code information of points extracted was stored into a two-dimensional array.

<figure><img src="image_5.png" /><figcaption>Fig. 3. Graph of chain code sum and chain code difference</figcaption></figure>

Because the accuracy of chain code difference is limited in the process of extraction, several neighbouring concave points may be selected at the same time. For this condition, the point of local maximal curvature should be selected from points meeting the expression as $d_{mn}<K$, where $d_{mn}$ is the distance between two concave points, where $K$ denotes a threshold of selecting candidate points. After experimental comparison, this paper was set at $K=9$. Result of extracting concave points is shown as Fig.2b.

According to different matching principles, point pairs matched could be located. Then, these point pairs were connected to form a separating line, which could realize the separation of adjacent apple. It is shown as Fig.2c.

If there is a region of two adjacent fruit, namely, expression is exhibited as $S_{threshold}<S_l \le 2S_{threshold}$, where $S_l$ is the area of No.1 valid region, only is a pair of concave points obtained at last, so there is no need to match, but to connect points directly.

If there is a region of many adjacent fruits, several pairs of concave points are obtained, which is shown in Fig.2b. It is obvious that there is a problem of concave point's combination and match. On the basis of test and analysis, the matching
procedure includes two following steps:

(1) Start from the first element in the two-dimensional array of concave points, and calculate the chord length between current and other point. The Equations can be expressed as Eq.(4):

$$C(i,j) = ((x_i - x_j)^2 + (y_i - y_j)^2)^{1/2} \quad (i,j=1,2, \dots, n) \quad (4)$$

Where $C(i,j)$ is chord length between i point and j point. In order to avoid the over-segmenting, those point pairs satisfy the predefined distance limits $C(i,j) < D_{threshold}$, Which are saved as matching point candidate.

(2) Let $AC=Arc(i,j)/C(i,j)$ denotes the rate of arc and chord. Objective boundary satisfied the major arc limitation, $AC > \pi/2$ can form arc. As far as optimum separating position is concerned, not only is its curvature relatively big but $AC$ is local maximum. By comparison $AC$ of point pairs obtained from step 1, the maximum and mark the corresponding points position can be found. As soon as a pair of matching points is determined, the gray value of separating line is changed into 0, then the region is divided into two parts. To judge from $S_{threshold}$, whether and which part has still adjacent fruits, and repeat the above process until all adjacent regions are separated completely. The separating flow is described as Fig.4.
<figure><img src="image_6.png" /><figcaption>**Fig. 4.** The flow chart of separation</figcaption></figure>

## 2.4 Centroid Coordinates Computation

After the separation of adjacent fruit region, each centroid coordinates calculated was regarded as approximate central position corresponding to a apple. Result is shown in Fig.2d. Their values are often not an integer. Considering a fruit region's size is far greater than a pixel'one, and the rounding coordinates will not cause an obvious effect on accuracy for post process.
## 3 Results and Discussion

<figure><img src="image_7.png" /><figcaption>**Fig. 5.** Images for experiment (a)The back lighted apple images including a two adjacent apples region (b)The back lighted apple images including a multi-apple adjacent region (c)The front lighted apple images including three adjacent regions</figcaption></figure>

With the purpose of evaluating the accuracy of centroid coordinates acquired after using the separating method, 100 apple images were tested in this study. 3 images were randomly selected to show the validate process. Each image was different from shooting and adjacent conditions. Fig.5a with a back light included two adjacent fruits occluded by leaves partly; Fig.5b with a back light included many adjacent fruits occluded by leaves and branches partly; Fig.5c with a front light included three adjacent regions, one was multi-fruit, two other were double-fruit. The aim of recognition is to separate adjacent apples each other and acquiring every centroid coordinates. The results acquired between by artificial and the newly presented methods have been compared. The distance between the two centroid coordinates weighs the disparity, the expression is followed as Eq.(5):

$$d_{mc} = ((x_m - x_s)^2 + (y_m - y_s)^2)^{1/2} \qquad (5)$$

Where $(x_m, y_m)$ denotes centroid coordinates acquired by artificial method, $(x_s, y_s)$ denotes centroid coordinates acquired by the separating method. Table.1 exhibits the comparison.

When $d_{mc}<10$, it means successful in separation, Table.1 showed the most of results meeting the above requirement, only two was largely different. No.5 fruit was overlapped by front fruits on the Fig.5b, most parts occluded were separated during the image processing, which resulted in notable coordinates migration; No.7 fruit was occluded by the leaves and branches, which made its area smaller after the separation of a component and its coordinates migrate. The rate of successful separation is
defined as Eq.(6).

$$R_s = (N_s/N_T) \times 100\% \qquad (6)$$

<table><caption>**Table 1.** Comparison of experimental results between artificial calculation and separating methods</caption><thead><tr><th>Figure Number</th><th>Apple number</th><th>Centric coordinate of artificial calculation (x<sub>m</sub>,y<sub>m</sub>)</th><th>Centric coordinate of separating method (x<sub>s</sub>,y<sub>s</sub>)</th><th>centroid distance d<sub>ms</sub></th></tr></thead><tbody><tr><td rowspan="2">a</td><td>1</td><td>(161,253)</td><td>(162,253)</td><td>1.00</td></tr><tr><td>2</td><td>(198,214)</td><td>(201,213)</td><td>3.16</td></tr><tr><td rowspan="4">b</td><td>3</td><td>(334,170)</td><td>(337,172)</td><td>3.61</td></tr><tr><td>4</td><td>(395,202)</td><td>(395,198)</td><td>4.00</td></tr><tr><td>5</td><td>(440,172)</td><td>(426,165)</td><td>15.65</td></tr><tr><td>6</td><td>(456,197)</td><td>(460,196)</td><td>4.12</td></tr><tr><td rowspan="9">c</td><td>7</td><td>(226,172)</td><td>(232,181)</td><td>10.81</td></tr><tr><td>8</td><td>(279,210)</td><td>(282,213)</td><td>4.24</td></tr><tr><td>9</td><td>(315,280)</td><td>(314,277)</td><td>3.16</td></tr><tr><td>10</td><td>(200,377)</td><td>(198,376)</td><td>2.24</td></tr><tr><td>11</td><td>(272,375)</td><td>(273,382)</td><td>7.07</td></tr><tr><td>12</td><td>(358,458)</td><td>(354,453)</td><td>6.40</td></tr><tr><td>13</td><td>(412,418)</td><td>(412,417)</td><td>1.00</td></tr></tbody></table>

Where $N_s$ is the number of apple meeting the expression, $d_{ms}<10$, $N_T$ is the total number of adjacent apples. Through testing with 100 apple images, we draw a conclusion that the average rate of successful separation is greater than 91.2%, which meets the requirements of application in harvesting robots. Furthermore, variable light has not obvious impact on the separation.

## 4 Conclusion

In this study, a novel and effective method for separating adjacent apples is developed in spite of various natural lighting conditions. Characteristics are as follows:
(1) In order to reduce the effect of natural luminance, a Gaussian lowpass filter is used to blur the initial image. Considering the feature of apple image itself, the component of Lab color space is employed to separate fruits from background, then medium value filter and area threshold are made use of removing image noises. Following the above steps, ideal binary images of apple are acquired for post processing.

(2) Valid regions of adjacent apples are extracted by area threshold method, which can improve the speed of total image processing. Following the contour of extracted regions, chain code information is obtained. Observing the changing law of chain code difference and adopting local optimum, concave points are found. Through the different matching principle, best point pairs are determined and adjacent apple can be separated accurately. The rate of arc and chord and the length of segment chord are key parameters of matching principle. Experimental results shows that average rate of successful separation is greater than 91.2% by this method, and meet the practical need of harvesting robot.

(3) However, there are some limitations for this method: Need of obvious concave-convex change of adjacent boundary; chain code information can be taken full advantage for separating fruits; Fruits are occluded by leaves and branches and its boundary is brought about some marked concave points, which will influence extraction and match of concave points.

## References

1. Bulanon, D.M., Kataoka, T., Ota, Y. and Hiroma, T.: A Color Model for Recognition of Apples by a Robotic Harvesting System. Journal of the JSAM. 64(5), 123--133 (2002)

2. Stajnko, D., Cmelik, Z.: Modelling of Apple Fruit Growth by Application of Image Analysis. Agricultura Conspectus Scientificus. 70(2), 59--64 (2005)

3. Zhao, J., Tow, J., Katupitiya, J.: On-tree Fruit Recognition Using Texture Properties and Color Data. In: 2005 IEEE/RSJ International Conference on Intelligent Robots and Systems, pp.3993--3998. IEEE Press, New York (2005)

4. Zhou, T.J., Zhang, T.Z., Yang, L.: Comparison of Two Algorithms Based on Mathematical Morphology for Segmentation of Touching Strawberry Fruits. Transactions of the CSAE. 23(9), 164--168 (2007) (in Chinese)
5. Luengo-Oroz, M.A., Faure, E., Angulo, J.: Robust iris Segmentation on Uncalibrated Noisy Images Using Mathematical Morphology. Image and Vision Computing. 28, 278--284 (2009)

6. Chinchuluun, R., Lee, W.S.: Citrus Yield Mapping System in Natural Outdoor Scenes Using the Watershed Transform. ASABE Paper No. 063010, St. Joseph, MI USA, (2006)

7. Lee, W.S., Slaughter, D.C.: Recognition of Partially Occluded Plant Leaves Using a Modified Watershed Algorithm. Transactions of the ASAE. 47(4), 1269--1280 (2004)

8. Wang, Y.C., Chou, J.J.: Automatic Segmentation of Touching Rice Kernels with an Active Contour model. Transactions of the ASABE. 47(5), 1803--1811 (2005)

9. Zhang, Y.J., Li, M.Z., Liu, G.: Separating Adjoined Apples Based on Machine Vision and Information Fusion. Transactions of the Chinese Society for Agricultural Machinery. 40(11), 180--183 (2009) (in Chinese)

10. Liu, W.H., Sui, Q.M.: Automatic Segmentation of Overlapping Powder Particle Based on Searching Concavity Points. Journal of electronic measurement and instrument. 24(12), 1095--1100 (2010) (in Chinese)

11. Annerel, E., Taerwe, L.: Methods to Quantify the Colour Development of Concrete Exposed to Fire. Construction and Building Materials. 25(10), 3989--3997 (2011)

12. Lak, M.B., Minaer, S., Amiriparian, J. and Beheshti, B.: Apple Fruits Recognition Under Natural Luminance Using Machine Vision. Advance Journal of Food Science and Technology. 2 (6), 325--327 (2010)

13. Otsu, N.: A Threshold Selection Method from Gray-level Histograms. IEEE Transactions on System Man and Cybernetics. 9(1), 62--69 (1979)

14. Bulanon, D.M., Kataoka, T.: A Fruit Detection System and an End Effector for Robotic for Robotic Harvesting of Fuji Apples. Agricultural Engineering International: the CIGR Ejournal 12(1), 1285-1298 (2010)

15. Gonzalez, R.C.: Digital Image Processing Using MATLAB. Publishing House of Electronics Industry (2005)

16. Liu, K., Fei, S.M., Wang, M.L.: Cotton Recognition Based on Randomized Hough Transform. Transactions of the Chinese Society for Agricultural Machinery. 41(8), 160--165 (2010) (in Chinese)

17. Freeman, H.: Computer Processing of Line-drawing Date. Computer Surveys. 6(1), 57--96 (1974)

18. Zhu, Y., Jiang, L.J., Xiao, Y.L.: Concave Spots Localization and Region Segmentation in Fibrous Material Image Based on Chain Codes. Journal of Nanjing University of Science and Technology (Natural Science). 32(1), 110--113 (2008) (in Chinese)