Segmentation on Ripe Fuji Apple with Fuzzy 2D Entropy based on 2D histogram and GA Optimization

Abstract

In this work we developed a novel approach for the automatic recognition of red Fuji apples in natural scenes using L*a*b* color model and fuzzy two dimensional (2D) entropy based on 2D histogram in order to achieve intelligent harvesting. The L*a*b* model is applied to detect the fruit under different lighting conditions because the red Fuji apple has the highest red color among the objects in the image. The fuzzy 2D entropy, which could discriminate the object and the background in grayscale images, is obtained from the 2D histogram. The genetic algorithm (GA), compared to the heuristic searching method, is optimized to increase the precision of segmentation of Fuji apples under complex backgrounds with partially occluded branches and reflective lights. A series of morphological operations are applied to eliminate segmental fragments. Finally, the proposed approach is validated on apple images taken in natural orchards. The contributions reported in this work, is the whole effective approach which recognizes and segments apples under different natural scenes regardless of the recognition accuracy.

Keywords:

• Segmentation
• Apple
• Fuzzy Entropy
• 2D Histogram
• Genetic Algorithm

1. INTRODUCTION

The application of natural image processing corresponds with the characteristics of natural environment for intelligent agricultural harvesters. The first major task of a Fuji apple harvester is to recognize the fruit and to determine its location. For this purpose, a highly effective, lower cost-time recognition, and segmentation approach is developed to recognize the partially occluded red Fuji apples regardless of different backgrounds within a tree canopy. The complexity of the task involves the successful discrimination of red Fuji apples within natural scenes of green leaves, shadow patterns, branches, and other objects found in natural tree canopies, and the optimal segmental thresholding searching method for the maximum fuzzy entropy.

For apple harvesters in orchards, intelligent systems have been developed to pick up fruits 1-3, but without commercial success due to the high costs and low capacity of these systems, and a human operator is also needed. For apple recognition method, a chromaticity method [4,5], color difference index [6], HLS color model (H for Hue, L for Lighting, S for Saturation) [7], a normalized difference index NDI of thermal imaging [8], LCD color difference Model [9], and fruit features [10] have been adapted to recognize apples images, but being unable to satisfying the recognition requirements of fruits within a natural canopy under different light reflections.

Image thresholding is an important technique for image processing and pattern recognition, which is also regarded as the first step for image understanding. Numerous threshold selection algorithms or techniques have been proposed or reused to solve problems, where machine vision is needed such as region merging [11], watershed segmentation method, K-means cluster analysis [12], wavelet, fuzzy logic [13], artificial neural networks [14], and fuzzy and rough set theories [15], and so on. It is generally believed that image segmental processing bears some fuzziness in nature. The concept of fuzzy partition and the maximum fuzzy entropy principle were firstly proposed to select thresholds for gray images [16]. But the circle operation to find the optimal segmental thresholding costs lots of time.

To alleviate the repeated computations in searching process for optimal thresholding, many researchers resort to intelligent optimization methods such as genetic algorithm (GA) [17], simulated annealing [16], particle swarm optimization [18], ant colony optimization [19], and recursive algorithm [20,21] and so on. But it could not guarantee that the global optimization can be obtained using intelligent optimization methods. Based on this idea, Wang [22] proposed an improved GA for fuzzy entropy thresholding. Genetic algorithms (GAs) are search procedures for combinatorial optimization problems. Numerous applications of GA or improved GA to optimization problems have been reported [23–26]. However the optimized GA based for searching thresholding is not detailed.

The objective of this study is to develop a machine vision recognition method in natural apple orchards. In this paper, the objectives are to develop an image processing algorithm to recognize the apple fruit from the other portions of the tree, such as the leaf and the branch under different light or background conditions, and to segment the ripe red fruit from the varieties of backgrounds with maximum fuzzy entropy theory and GA optimized. This paper is organized as follows. In Section 2, the proposed approach of this study is introduced including the recognition model with L*a*b* color model, fuzzy 2D entropy based 2D histogram, heuristic searching thresholding and GA optimized searching method. Section 3 provides the implementation of the approach, and the experiment results and discussions. The conclusions are given in Section 4.

2. THE PROPOSED APPROACH

2.1 Apple Recognition using L*a*b* Color Model

The apple tested in this study is the Fuji variety in Baishui Apple Experimentation Station, Baishui County, Shaanxi Province. The Fuji apple images were collected using a color CCD camera. The fruits were randomly selected from the apple orchard under different natural daylight lighting conditions. The red color and apple edges are features highly maintaining a low variability for illumination while texture is highly sensitive to the proximity of the apple. It seemed to be interesting to use information given by red color in the natural scenes.

A general approach to adaptive Fuji apple recognition in natural tree, and threshold segmentation is proposed. The flow diagram of methodology structure in Figure 1 shows the algorithm to automatically determine the optimal threshold and recognize the fruit.

Figure 1 The flowchart of proposed approach.

An L*a*b* color model is a color-opponent space with dimension L* for lightness, a* and b* for concentration and intensity of the color component dimensions. The input RGB image with ripe Fuji apples first needs to be transformed into L*a*b* [27], and the initial recognition segmentation threshold is calculated using equation (1), with T set as − 6.0, where T means a constant variable. Since + a* represents the red color component, if a*-value is set equal to and bigger than − 6.0 according to the fruit ripeness grading suggestions [28], the red apples that should be harvested include all the little red ripe Fuji apples regardless different background or different light conditions, and when the + a* value is smaller than − 6.0, the component of a* is definitely set as a background. Hence, all the little ripe apples should be detected and be harvested.

2.2 Fuzzy 2D Entropy with 2D histogram-based

For an M × N digital grayscale image with gray-level of L, L = 0, 1, 2… 255, let x _mn is grayscale value of the pixel x of position of , where , and . For a 3 × 3 neighborhood of pixel x, is the average gray value. A 2D histogram is an array (L × L) with the entries representing the number of occurrences of the pair . A two-dimension of histogram is composed of two element pair , where X represents the gray levels of pixel and Y represents the local average gray levels with its 3 × 3 neighborhood.

The 2D histogram of array (L × L) is divided into four parts by the thresholding shown in Figure 2(a), the higher gray-level block B represents for the objects, and the lower gray-level block A for the background, and the block C and D for the image edges and noises, respectively. The bright block named Block _B is divided into two parts, non-fuzzy block B ₁ and fuzzy block B ₂ as equation (2) and shown in Figure 2(b); and the dark block named Block _D is divided into two parts, non-fuzzy block D ₁ and fuzzy block D ₂, as equation (3) and shown in Figure 2(c).

where or is the fuzzy membership function for the bright target regions or dark background regions. is defined based on the S-function shown in Figure 3(a) as equation (4), and is defined based on the Z-function shown in Figure 3(b) as equation (5).

Figure 2 Description of 2D histogram of array (L × L). (a) 2D histogram divided into four blocks: A for the background, B for the objects, and the block C and D for the image edges and noises; (b) The Block _B are divided into two bright parts, B ₁ and B ₂; (c) The Block _D are divided into two dark parts, D ₁ and D ₂.

Figure 3 S-function and Z-function. (a) A genral S-function (central solid line), the left limitation function (left dashline) when a → 0, and the right limitation (right dashline) when c → L; (b) A genral Z-function (central solid line), the left limitation function (left dashline) when a → 0, and the right limitation (right dashline) when c → L.

where b is the midpoint of fuzzy range of [a, c].

where the range [a, c] denotes the fuzzy region of (x _mn, y _mn).

Let A be a fuzzy set with membership function , where ; i = 1, …L, are the possible outputs from source A with the probability . The fuzzy entropy of set A is defined as [29]

The total image entropy is defined as

As shown in Figure 2 and from the equations (2) and (3), the bright Block _B includes a non-fuzzy block B ₁ and a fuzzy block B ₂; the dark Block _D includes a non-fuzzy block D ₁ and a fuzzy block D ₂. So,

where is the element in the 2D histogram which represents the number of occurrences of the pair . The membership functions and are defined in equations (6) and (7) respectively, and shown in Figure 3. It should be noticed that the probability computations in the four regions are independent of each other.

2.3 Fuzzy 2D Entropy Calculation with Heuristic Searching

To find the best set of a, b, and c is an optimization problem which can be solved by: heuristic searching, simulated annealing, genetic algorithm, etc.

Because of the four segmental variable ranges of fuzzy set as S (Z) –function, the method of heuristic searching is detailed as follows:

	Step 1. Input the grayscale image.
	Step 2. Compute the two dimensional histogram.
	Step 3. Use the exhausted search method to find the pair a opt and c opt , which form a fuzzy 2–dimensional maximum entropy:
	for a = 1 to 254 for b = (a+1) to (2b-a) a. if (2b-a) is bigger than 255, the circulation exit this circulation to continue. b. compute the piecewise of S-function of fuzzy set of and Z-function of fuzzy set of : only if the element of two dimensional histogram is unequal to zero, and start the circulation, for i = 1 to 255 i. if i < a, this means the range of [1, a], compute the total number of occurrences of the pair belonging to block D 1: ii. compute the entropy H(D 1) with equation (13). iii. if i < b, this means the range of [a, b], compute the total number of occurrences of the pair belonging to range , and computer the segment of fuzzy set of equations (6) and (7) which belong to block B 2 and D 2, respectively. iv. compute the entropy H(B 2) with equation (12) and H(D 2) with equation (14). v. if i < 2b-a, this means the range of [b, c], compute the total number of occurrences of the pair belonging to range , and computer the segment of fuzzy set of equations (6) and (7) which belong to block B 2 and D 2, respectively. vi. compute the entropy H(B 2) with equation (12) and H(D 2) with equation (14). Thus, the fuzzy entropy of block B 2 and D 2 are calculated completely. vii. if i belongs to others, this means the range of [c, L], compute the total number of occurrences of the pair belonging to block B 1: viii. compute the entropy H(B 1) with equation (11). c. End for the circulation of i, a, b.
	Step 4. Compute the total image entropy of equation (10). Find the maximum of H(image), and a, b. The middle point of b is optimal thresholding.

Note that in the processing (iii) and (iv) of the step 3, when computing the piecewise S-function or Z-function, the circulation variable i should be the x _mn, and when computing the cumulative summation of H(B ₂) and H(B ₃), the circulation variable should be the y _mn.

2.4 Fuzzy 2D Entropy Calculation with Optimized Genetic Algorithm

For the heuristic searching, the whole searching space is covered close to O(L ³) (256³ = 1.7 × 10⁶). Since the fuzzy sets of S-function and of Z-function are composed of piecewise function, the parameters optimized should be (a, b, c). For the each parameter set of (a, b, c), genetic algorithm is used to calculate the corresponding fitness value of H (image), which is composed of four entropies with equations (11-(14).

For an improved genetic algorithm, a fuzzy punishment function is constructed to evaluate the fitness in case of premature convergence of algorithm. In the optimizing processing of genetic algorithm when computing the maximum, the individual sets are sorted to a new individual sets as descending order according to the size of fitness, where N is the number of population size, is the biggest fitness of individual, and is the fitness of i-th individual. The fitness distance is the position of i-th individual after sorted.

The punishment function is constructed on the basis of three different periods of evolution. On the early period of evolution, the three-piecewise punishment function could be added to the individuals with higher fitness in order to reduce the fitness to certain extent, using equation (15), which could prevent much reproduction and from being trapped to get local solutions. On the medium of evolution, a linear slowly-changeable membership function with equation (16) is constructed to retain diverse and best individuals. On the last stage of evolution, a sharply-changeable membership function with equation (17) is constructed to improve the local searching.

In the prophase of evolution, the fuzzy punishment function used for the fitness evaluation is [22]

where N donates the population size; C ₁ and C ₂ as constant parameters, meet C ₁ <  C ₂ < 1.

In the medium of evolution

In the anaphase of evolution

In proposed improved genetic algorithm the new fitness function is defined as equation (18):

where is the initial fitness function before sorted as decreasing order.

For a genetic algorithm, several parameters need to be predefined as follows and the processing operations are described.

1.	Coding method. For every string parameter of a, b, and c, whose value is limited of range [0, 255], each chromosome is encoded randomly as 24-bit string within the range. The first 8-bit string is considered as parameter a, the middle 8-bit as parameter b, and the last 8-bit as parameter c. Notice that a, b and c have to follow the increasing order condition 0 ≤ a < b < c ≤ 255. If the chromosome produced does not satisfy the condition, the increasing order is adjusted according to parameter value, in case that many useless chromosomes produced are participated in the reproduction of next generation.
2.	Object functions and other parameters. Obviously, the object function is the entropy function of equation (10). The parameters of the genetic algorithm are set as follows. Maximal generation iteration number is set as 45; the population size is set as 100; the probability of crossover is set as 0.6; and the probability of mutation is set as 0.01.
3.	Fitness. Calculate H (image) of equation (10) as the initial fitness of each population, and as new fitness function. For the 45 maximal generation iterations, the first 15 is made as the prophase of evolution, the second 15 as the medium of evolution, and the last as the anaphase of evolution; C 1 is equal to 0.05, and C 2 is equal to 0.25.
4.	Selection. Execute selection operation with roulette wheel selection method. Calculate the accumulative summation of fitness of each individual among the populations, and then a randomly produced number is within the range from zero to the summation. The summation which is bigger than the random number is the selected individual. Repeat over in this way, and the new reproductive population is produced.
5.	Crossover. Execute crossover operation according to initial crossover probability. If a random number produced is smaller than this initial crossover probability, the crossover operation is executed in every interval string of 8-bit among each chromosome in the way of single point crossover to the corresponding position 2 times.
6.	Mutation: Execute mutation operation according to initial mutation probability. If a random number produced is smaller than this initial mutation probability, the crossover operation is executed in the way of randomly selecting certain bit of individual from the randomly selected populations.
7.	Termination condition: If the maximal generation iteration number is bigger than or equal to 45, terminate the algorithm; otherwise go to fitness calculation.
8.	Decoding. Decode the chromosome with highest fitness as the best individual according to the encoding method, and segment the image with the decoded result as the optimal threshold.

After segmentation, a series of mathematical morphology (MM) processing are employed to remove numerous segmental fragments to get the binary image. After creating a square-shaped structuring element with 2 × 2 dimensions, erosion operation is used to shrink the size of regions, and opening operation is used to remove all the small regions less than T ₁ pixels, where T ₁ is determined by the value of 4% of the rows multiplied by 4% of columns. Dilation is used to recover size of regions, flood-fill to fill the gaps.

3. EXPERIMENTS AND DISCUSSIONS

Here, the experimental results are obtained to demonstrate the effectiveness of the proposed method. This discussion includes the choice of the L*a*b color space, segmentation of fuzzy 2D entropy including optimal threshold with heuristic searching and optimized genetic algorithms. Varieties of red Fuji apple images taken under different light scenes are applied to the proposed approach, and some experiments are presented to illustrate the key points of the proposed method and its effectiveness for thresholding segmentation.

According to the flow diagram of Figure 1, different images under different scenes in real orchards are tested, and over 95% of the ripe red Fuji apples are successfully segmented from the 40 images tested. In most of these cases, the algorithm has only caused once a bit non-complete segmentation, and caused no over-segmentation.

To search for the optimal segmental thresholding, compared to the cost of time of heuristic searching, the optimized GA could only a little efficient, and the difference of two searching methods is within 10, and the difference of maximum fuzzy entropy within 0.05. Although the heuristic searching covers the searching space of O(L ³), yet there exists the quite a portion of pairs (x _mn, y _mn) whose values are equal to zero, thus could reduce greatly the searching time. Since the fuzzy punishment function is added to the fitness valuation function, the genetic algorithm could be more stable and more robust to search for the thresholding regardless of premature convergence.

Figure 4 and Figure 5 respectively depict two illustrational images taken under light conditions resulting from the various steps in the flow of the algorithm. Figure 4 shows the recognition and segmentation results with a strong front light. From equation (1), when the value of + a* channel of L*a*b* is smaller than − 6.0, the component of a* is definitely set as background. From the results shown in Figure 4 (b), some small parts which belong to dark green leaves and sky, directly turn black and their gray-levels remain 0, and ripe Fuji apples and only the reflective edges of leaves are highly lightened. The histogram with single-peak distribution shown in Figure 4(c) and its 2D histogram shown in Figure 4(d) depict that most of pixels concentrate on the lower gray-levels. Figure 4(e) shows the resulting of segmentation with fuzzy two-dimensional entropy based on GA optimized, where most backgrounds are removed, and the fragments are only composed of the reflective edges of leaves. Figure 4(f) shows the morphological operation resulting, where two reflective branches on the top are left. If the opening operation is set twice of size of T ₁, all the background can be cancelled and only the interesting objects are preserved.

Figure 4 Results of the proposed approach with a strong front light. (a) A test image under a strong front light condition; (b) Recognition with + a* channel, where some small parts which belong to dark green leaves and sky, directly turn black and their gray-levels remain 0, and ripe Fuji apples and the reflective edges of leaves are highly lightened; (c) Grayscale histogram of (b); (d) Grayscale two-dimensional histogram of (b); (e) Segmental resulting with fuzzy two-dimensional entropy based on optimized GA, where most backgrounds are removed, and the fragments are composed of only the reflective edges of leaves; (f) Morphological operation resulting of (e), where two reflective branches on the top are left.

Figure 5 Results of proposed approach with shadows and occluded leaves and branches. (a) A test image with shadows and occluded leaves and branches; (b) Recognition with + a* channel, where some small parts which belong to green leaves and branches, directly turn black and their gray-levels remain 0, and ripe Fuji apples are well preserved; (c) Grayscale histogram of (b); (d) Grayscale two-dimensional histogram of (b); (e) Segmental resulting with fuzzy two-dimensional entropy based on optimized GA, where the most majority of backgrounds are removed; (f) Morphological operation resulting of (e), where even the occluded red apples are well preserved.

Figure 5 shows the recognition and segmentation results with shadows and occluded leaves and branches. From the resulting shown in Figure 5(b), some small parts which belong to green leaves, branches and sky, directly turn black and their gray-levels remain 0, and ripe Fuji apples are highly lightened. The histogram with two-peak distribution shown in Figure 5(c) and the 2D histogram shown in Figure 5(d) depict that the most majority of pixels focus on the lower gray-levels. Figure 5(e) shows the resulting of segmentation with fuzzy two-dimensional entropy based on GA optimized, where the most majority of backgrounds are removed. Figure 5(f) shows the morphological operation resulting, where even the occluded red apples are well preserved.

4. CONCLUSIONS

In this paper, a novel recognition, segmentation method of red Fuji apples on natural scenes is proposed and demonstrated. Under the different lighting conditions, the original contributions of Fuji apple recognition, segmentation for an apple harvester presented lie in three aspects:

i.	L*a*b* color model is firstly used for Fuji apples detection with different backgrounds, thereby providing an apple recognition system with adaptability in real-world scene and satisfying different apple harvester;
ii.	A fuzzy 2D entropy based on 2D histogram is used as a fruit segmentation method, while clearly discriminating the background and the object part.
iii.	A GA optimized based searching is used as combinational optimization of segmental thresholding, while a fuzzy punishment function being added to the fitness valuation function, and regardless of being trapped into local solutions.

Recognition methods based on L*a*b* color model are quite flexible according to different application fields. The fuzzy 2D entropy based on the 2D histogram is suitable to different grayscales. The improved GA to choose an optimal thresholding value can meet different optimization conditions and prevent from premature convergence. Because of the limitations of experimental trials, future research may be conducted with robotic harvester that enables capture of image. The experimental results have shown the effectiveness and usefulness of the proposed methodologies for a real-time operating unit.

Acknowledgements

The work was supported by National Natural Science Foundation of China (NSFC) under Contract 60975007, and partially supported by Special Personnel Foundation of Northwest Agriculture and Forestry University under Contract 01140403. The authors would like to thank the Baishui Apple Experimentation Station, Baishui County, Shaanxi Province for providing the photos. The authors would also like to thank the reviewers for their kind suggestions.