Rapid tree model reconstruction for fruit harvesting robot system based on binocular stereo vision

1. Introduction

The intelligent harvesting robot is an effective solution approach for the reduction of agricultural labor force and the high cost of fruit picking. Unstructured working environment is the biggest problem for harvesting robot. As the spatial location and posture of fruit are random, the existence of branches and other obstacles are the hidden dangers of the harvesting robot. Therefore, the identification and location of obstacles is a new problem. After the acquisition of branch spatial information, their 3D models are reconstructed by using appropriate method. In the work scene model, path planning for fruit picking are carried out to make robot real-time, securely, nondestructively pick fruit.

In the whole harvesting process, there are two key issues: identification and picking. So, the system must have two functions, by which obtain the identification information from the fruit data and obstacle avoidance information from the branch data. Until present, binocular stereo vision system is the best choice for the whole process system and connection platform have known. In the picking part, it is easy to reconstruct the real-time model and supply the data for obstacle avoidance by binocular stereo vision system. And in fact, when the model was reconstructed, the data transformation from that could supply enough data for the obstacle avoidance [1].

In 3D modeling, decompose a complicated object into simple modules, and then combine them according to a given rule. For three-dimensional modeling, this method of complexity-simpleness-complexity [2-9] is important. It is well known that OpenGL include the standard modules, if a module could be found that satisfies the rapid fruit model construction, all problems would become simple following the thinking mentioned before. In this paper, the cylinder module is choosing because though the tree's shape is complicated, the branch is made from a great deal of cylinders.

2. Extraction of branches information

Extraction of branches features information of fruit trees is to reconstruct tree model based on these features. From the scene images Fig. 1, it can be seen that the shape of branches are complex, it is very difficult to recover the branches 3D information. There are straight branches and curved branches. Reconstruction cylindrical through branch endpoints and radius can characterize direct branches, but not to characterize curved branches.

In this study, first, extract the tree skeleton, and then fit tree branches skeletons by multi-segment approximation method to obtain feature points coordinate information and extract radius information of the characteristic points by the branch range image. Finally, the original branches are reconstructed by multi cylindrical.

Fig. 1Scene image and binary image of branch

a)

b)

2.1. Skeletons extraction

Skeleton is the core part of the object, and the objects of different shapes have different skeletons. In general, the skeleton has three main characteristics: continuity, the minimum width is 1, and centrality [10]. Currently, extraction method of region skeleton mainly includes morphology method, distance transform and thinning method, etc.

1. Morphology method. Morphological method is a way to corrode awaiting processing region with a structure element, and then add each last time result before corrosion to empty set to get region skeleton [11]. But, this method can’t guarantee the connectivity, when the edge is not smooth or the width sudden changes in the region, that will cause skeleton points detected from the continuous region discontinuous.

2. Distance transform. Distance transform method extract region skeleton in two steps by distance transform and skeletonization. In this method, the range image is obtained through distance transform, the size of each pixel value in the range image directly reflects the distance from the pixel to edge; Then comparing the distance value of pixel in the range image, all the set of pixels which’s distance value are greater or equal to the maximum distance value of the neighborhood is used as region skeleton.

Distance transform method extract region skeleton points by range image. For the largest distance points in each row (or column) are only related to the edge, the skeleton points location relationship of adjacent two rows (or two column) is not necessarily related, when the edge is not smooth or the width sudden changes in the region, that will cause discontinuous skeleton points detected from the continuous region or generate noise points, which will cause difficulty in further processing.

3. Thinning method. Region thinning method thins the region to get line graph constituted by lines with small memory capacity and ease to be identified. In order to make line graph accurately represent the shape of the object, the thinning must meet the following requirements:

(1) The line-width is one pixel;

(2) Thin position lies in the center of the original region;

(3) Graph’s connectivity keeps invariant, and the hole and points can’t new increase or disappear;

(4) The graphic ends keep invariant.

So, one can see, the essence of region thinning is the process of finding the center line of graph without changing the length and the connectivity of graph.

There are various thinning methods, this paper adopts Yokoi thinning method to implement thinning region. When Yokoi thinning method repeatedly removing pixels in the surface of graphics, the graphic surface pixels are divided into upper-lower surface pixels and left-right surface pixels, and forward scanning and reverse scanning are alternately carried out to remove upper-lower surface pixels and left-right surface pixels until the center line was obtained.

In this study, the region skeletons extracted by Yokoi thinning method keep the connectivity of original region with better effect Fig. 2.

Fig. 2Features extraction of branch

a) Branch range image

b) Branch skeleton

c) Multi-segment approximation image

d) Overlay

3. Acquiring 3D information

This paper extracts the branch 3D information by binocular stereo vision technology, which includes the space coordinate of branch feature points and the radius of the branch. Because there are many feature points for one breach, feature points matching is unsuitable for branch matching.

Region matching is to select a $\left(2n+1\right)\times \left(2n+1\right)$ region (window) with one point as the center in an image, find the region with the greatest correlation degree to the window region in another image, and the center of the maximum correlation region found is used as the corresponding point of original regional centre, the disparity of the whole image can be obtained. So, region matching is suitable for branch matching in this study.

Typically, the gray matching method is the fastest way to reconstruction. Sum of absolute gray value differences (SAD) and sum of squared gray value differences (SSD) are two methods of similarity measure [16, 17]. The definition as follows:

SAD and SSD are sensitive to illumination variation. As the shading of tree, and the different viewpoint of two cameras, illumination variation often occurs. Therefore, this study used normalized cross-correlation (NCC) method:

$m_k$ and $s_k$ ($s_k=left$, $right$) respectively represented mean value and standard deviation of the window in the left and right image. NCC has the advantage of anti interference to illumination variation, but with slightly longer computation time.

To find the match point in the left image, similarity measure should be calculated along the entire epipolar line in the right image. However, the disparity of the point related to the depth, which is decreased with depth increased, the disparity of infinite point can be seen as 0. Depth range of the object can set disparity search. A smaller searching range of disparity can be set by depth range of the object.

Therefore, $d\in \left[d_{\mathrm{m}\mathrm{i}\mathrm{n}},d_{\mathrm{m}\mathrm{a}\mathrm{x}}\right]$, $d_{\mathrm{m}\mathrm{i}\mathrm{n}}$ (min disparity) and $d_{\mathrm{m}\mathrm{a}\mathrm{x}}$ (max disparity) can be calculated by the depth extreme value. After the calculation of similarity measure for a point, the matching point is based determined by the maximum value of the NCC. However, the occlusion may result in failure matching of the pixels, a threshold value of similarity is set, and only when the pixel similarity measure is above this threshold, the matching results are accepted. Obviously, the setting for the threshold may result in multiple matching [18].

Fig. 4Disparity image using area-based matching and skeleton image

a) Disparity image

b) Skeleton image

c) Skeleton image processed by “and operation”

In this study, the distance from fruit trees to the camera is between 1.0-2.0 m, by calculating the disparity search range of $d_{\mathrm{m}\mathrm{a}\mathrm{x}}=$ 96 and $d_{\mathrm{m}\mathrm{i}\mathrm{n}}=$ 48 can be set. After two original images are converted to grayscale images, the two images are matched with setting 15×15 matching window by NCC method. Texture validation and uniqueness validation are set to prevent the match pixels generated by window texture level being declared to be invalid pixels and to optimal select one of the best match points from multiple matching pixels. Disparity image are shown in Fig. 4(a), Fig. 4(c) is the result of “and operation” between Fig. 4(a) and Fig. 4(b), which represents branches that can be measured. By comparing Fig. 4(c) and 4(b), it can be found in Fig. 4(c) that some of region skeletons are reduced, this is because part of the branches can’t find the matching points.

4. 3D reconstruction based OpenGL

Harvesting robot is complex and expensive, which is eased to be damaged by branches and other obstacles when picking citrus, apples and other fruits of tall trees. It is necessary for harvesting manipulator to possess the function of obstacle avoidance, as will ensure the occlusion fruit are picked safely and successfully. The premise conditions for obstacle avoidance are the perception of obstacle information in the robot work space and the reconstruction of scene model. The work scene includes fruits, leaves and branches, the fruits are the work target and the leaves will not cause damage to the robot, so that reconstructing branch model is enough.

On the basis of fitting branch by multi-segment approximation and branch feature extraction, the unit module is constructed by the 12- prism method, and then assembled into the tree model.

Fruit trees are with complexity structure and large individual differences, the breaches are composed of large number of truncated cones with constantly changing radius. The unit module is constructed branches have been divided into many segments by multi-segment approximation and extracted the 3D coordinate and radius of feature point. The data of each branch is stored as $\left\{\left(x_1,y_1,z_1\right),R_1;\left(x_2,y_2,z_2\right),R_2\right\}$ which is the necessary data for constructing unit module. Model is constructed by using OpenGL in VC platform.

4.2. Scene model combination

Each branch unit model needed to be moved to correct position with the original pos and composed of scene model with other model.

By spatial position transformation law, unit model will recurrence the branch original position and pos by twice rotations and once translation. Taking the cylindrical module for example, the transform process of module position and orientation is briefly introduced.

Each branch model in the scene was transformed by above methods to obtain scene tree model, shown in Fig. 5.

Fig. 5Scene model of virtual reconstruction

a) Front view

b) Left view

c) Top View

d) Bottom view

5. Conclusions

This paper has studied the method of spatial information extraction. Experiment used the region matching method to obtain the disparity of each pixel matched, extracted feature points combining with branch skeleton image by multi-segment approximation method, and calculated the spatial coordinates and the radius of branch feature points by using binocular stereo vision. Real-time model reconstructing for fruit tree has been researched on. Test has optimized extraction algorithm and matching algorithm of the branch region, improved matching rate, reduced matching errors, avoided matching confusion, accurately extracted branch spatial information and improve the success rate of robot path planning for obstacle avoidance.

Real-time model reconstruction for fruit trees had been researched on. Test proposed that each branch module was constructed by 12-prism in the coordinate origin and then in the space of tree build paragraphs, and then rotated twice and translated once to get correct posture, finally combined with other modules for the fruit tree model. Documents required for obstacle avoidance and path planning is analyzed, and the relationship between model accuracy and model generation time was found by comparing the model generation time in different condition. Experiments show that the fruit tree model provide environmental reference for obstacle avoidance and path planning of the fruit harvesting robot, and the speed and the accuracy essentially meet the requirements.