Automatic Wood Log Detection Based on Random Decision Forests Learning Algorithm and Histogram of Oriented Gradients Yuriy V. Chiryshev Anastasiya S. Atamanova Ural Federal University Ural Federal University Yekaterinburg, Russia, 620004 Yekaterinburg, Russia, 620004 iurii.chiryshev@mail.ru s050567@yandex.ru Abstract In this article the results of the round wood image recognition problem have been stated. This task is very important in woodworking industry. The paper provides a brief overview of existing solutions of round wood recognition, highs and lows of these approaches are shown. The pattern recognition technique feature for round timber is described. This technique is based on the histogram of oriented gradients (HOG) and random decision forests classifier. Based on the experiments, the optimal number of trees for round timber recognition is found. The analysis of results shows that from 64 trees there is no more appreciable difference between the forests using 128 trees or more. Experimental results have demonstrated a detection rate as high as 95.4% with a false-positive rate 10-3. 1 Introduction One of the most challenging tasks in the systems of raw materials accounting for the woodworking industry is to measure the geometric characteristics of timber and lumber. This task is especially relevant for determining the quantity and volume of round timber stacked, since the currently used manual measurement methods give an error of more than 15% [1]. The solution to this problem is possible due to the use of a measuring system based on technical vision, when the position, shape and dimensions of the logs are determined by specialized software for their photo images. The choice of this approach entails the need to solve the problem typical for computer vision systems - pattern recognition. The complexity of such a problem is that first of all it is necessary to find out each log’s cut on the image. All subsequent processing steps will be depending on the correction of the task solved. 2 Review of Existing Methods Several works have been devoted to the log cut image identification [1-6], some of them have found practical implementation in various application areas of measuring systems [1-3]. The methods of detection proposed in these works can be divided into two categories. The first group includes the methods based on machine learning. In [4], the authors proposed an iterative detection and segmentation scheme in which the descriptors of singular points based on the histogram of directed gradients (HOG) [7] together with Haar and local binary template operators (LBP) are used in the log cut detection phase [11]. In [5], the search for logs by their key features uses the method of ViolaJones [10]. Its main idea is to use a cascade of classifiers, each of which is a committee (ensemble) of weak classifiers. The signs for the recognition algorithm are rectangular Haar signs. The methods of the second group are constructed according to the scheme of teaching without a teacher and use the assumptions about the known form and size of the logs [2,3,6]. Basically, these methods are based on the Hafa transformation [6] or its modifications [9] and are used to detect cuts of logs on an image in the form of circles or ellipses. The shortcomings of such methods include the low degree of automation of the detection process, which ultimately affects the objectivity of the measurement results. The reasons for this are the well-known shortcomings of the Hafa transformation:  sensitivity to geometric distortions of objects and noise;  lack of a priori information about the size of objects in the image;  computational complexity of the algorithm. Such limitations, in our opinion, do not allow to fully use these methods and to obtain high quality of detection for the problem of log recognition. Nevertheless, the authors of one of these studies managed to achieve an average detection probability of 95.7% [3]. Under the conditions of this task, methods based on machine learning are the most promising and preferable from the point of view of the computational complexity and the requirements for distortions of objects. To search for log cuts on images, it is suggested to use the approach proposed in [7], but with some modifications. In this work, a classical HOG detector is implemented that uses the support vector method (SVM) as a classifier. The authors of this paper consider the implementation of the HOG detector using the ensemble of decision trees [8] and investigate the dependence of its work on the input parameters. 3 Description of the Method Histograms of directed gradients is a method of an indicative description characterizing the shape of an object. Initially, this method was used for the detection of people on images, but subsequent studies have shown its effectiveness for many other classification problems [12,13]. The implementation of the indicative description of the logs in this paper is based on the general scheme for describing the HOG- descriptor based on counting the number of gradient directions in the image cells, as described in [7]. Figure 1 shows a diagram of such a partitioning into cells and calculations of the histogram of gradients for the problem of log detection. Analysis of a set of more than 7000 images of log bundles [14] has shown that the characteristic features of images are subject to many factors, such as lighting, shape deformation, partial overlapping of trunk sections, a different view angle and scale of images, and require the use of special methods for fast and accurate calculation of logs features. In order to overcome these limitations of the initial data, the following solutions are used in the work:  to quickly calculate HOG descriptors, gradients of input images were previously presented in integral form. This technique is based on the discrete Green theorem and allows you to quickly calculate histograms of directed gradients in the area of interest (cells) of the image in a few simple arithmetic operations [15], while the calculation time does not depend on the area of the image.  to ensure invariance to scale, HOG descriptors are computed in a sliding window with a minimum step on several scales of the original image. This solution allows you to search for images of logs sections in a wide range of their sizes (radii).  the unevenness of log lighting is partially compensated by increasing the contrast of the original image [7]. As a classifier, the learning random decision algorithm (Random Forest) [8] is used in the work. His main idea is to build an ensemble of decision trees, while the classification - the assignment of a new object to a particular class is made by voting: each tree classifies the object to one of the classes, and the winner is the class that is voted for by the most trees. The pluses of this method are:  high classification accuracy;  high scalability and parallelizability;  the ability to efficiently process data with a large number of attributes and classes;  the ability to assess the importance of individual characteristics. There are also disadvantages, such as:  the algorithm is prone to retraining, especially on noisy data;  large size of the resulting models. a) b) c) d) e) Figure 1: Scheme of HOG descriptors calculation. a) input image; b) gradient of the input image; c) splitting the image into cells; d) the combination of cells into blocks and the normalization of feature vectors; e) combining the normalized block histograms into one descriptor To estimate the generalizing ability of the classifier, a k-block cross-check is used [16], when the entire sample of data is randomly divided into k non-intersecting blocks of the same size. Each block in turn becomes a test sample, while training is performed on the remaining k-1 blocks. The result of such testing is the average error in the control sample of the data. This method gives an unbiased estimate of the probability of error, and therefore, it makes it possible to detect the retraining of the classifier (Table 1). 4 Experimental Results To evaluate the proposed solutions, a number of experiments were conducted, designed to assess the quality of classification on real data for various parameters of the HOG descriptor construction and classifier. As the test data, 11068 marked images with 4632 "positive" logs and 6436 images with "negative" samples were used. Examples of images of the training sample are shown in Figure 2. In the first experiment, the dependence of the predictive ability effectiveness of decision trees on the input parameters of this classifier was investigated. Figure 3 shows a comparison of models trained using a different number of random decision trees (16, 32, 64, 128, 256 and 512). Analysis of performance curves (ROC) indicates that with the increase in the number of trees from 16 to 64, the quality of recognition is significantly improved (the area under the curves is increasing). With a further increase in the number of trees from 128 to 512, quality growth practically ceases. Thus, according to the results of the experiment, it can be assumed that the optimal number of trees for the problem of log recognition lies in the range between 64 and 128. For this reason, further studies used classifiers consisting of only 64 trees. a) b) Figure 2: Examples of images from the training sample. a) "positive" examples; b) "negative" examples Within the framework of the second experiment, the results of the classifiers work trained on six different sets of characteristics were investigated. The parameters of the HOG descriptors under investigation and the corresponding characteristics of the detectors trained using 64 trees are given in Table 1. In order to understand how and to what extent the performance characteristics of the classifiers vary depending on the parameters of the HOG descriptors, comparison. Figure 3: The work quality of ensemble decision trees comparison Table 1: Selecting HOG-descriptor parameters HOG Descriptor Parameters [7] Experiments results Descriptor’s Window / block Number of Block Complet Precision, Accuracy, F-metric,% name / cell size, pix. histogram cells step, pix. eness,% % % HOG64-8 64/16/8 8 8 95.0±0.8 99.0±0.1 96.9±0.5 97.4± 0.2 HOG64-9 64/16/8 9 8 95.4±0.5 99.1±0.3 97.1±0.3 97.5±0.3 HOG48-8 48/12/6 8 6 94.5±0.6 98.5±0.4 96.6± 0.2 97.3± 0.3 HOG48-9 48/12/6 9 6 95.0±0.8 98.7±0.3 96.9± 0.4 97.4± 0.4 HOG32-8 32/8/4 8 4 94.2±0.8 97.8± 0.4 95.7±0.6 96.7±0.5 HOG32-9 32/8/4 9 4 94.1±0.9 97.6± 0. 1 95.7±0.5 96.7±0.5 Figure 4: Comparison of HOG detectors performance based on the ensemble of decision trees. a) performance curve; b) the curve of compromise error determination Visualization of the classifiers performance is represented by two graphs: curves of the operating characteristic -off curve (Fig. 4b). The obtained curves quite clearly characterize the predictive ability of the constructed models. Figure 4 shows that the curve closest to the lower-left corner of the coordinate system corresponds to a descriptor with 9 histogram cells and a window size of 64 pixels. The same descriptor corresponds to a curve with a maximum area of 0.9972 (Fig. 4a). This means that the classifier with such a descriptor has the best predictive power. These conclusions are supported by the calculated characteristics: the descriptor named HOG64-9 has the maximum values from the presented values of completeness, accuracy and precision of the classifiers (Table 1). Thus, from the results of experiments it can be concluded that the set of features of HOG64-9 is the best among those considered. Such a classifier is able to detect positive examples (logs) with a probability of 95.4% at a false positives level of 10-3 (Fig. 4b). An illustration of the detection algorithm operation is shown in Figure 5 Fig 5.Log cut detection 5 Conclusion The experiments results have showed that the proposed HOG detector based on the training of random decision trees achieves higher quality indices compared to methods based on linear classifiers (SVM + HOG, accuracy 77.9% [4]) and cascades of weak classifiers (AdaBoost + Haar, Accuracy of 95.1% with the value of false positives 4.9 ∙ 10-3). However, it is inferior to these methods, when the latter is strengthened by several combined attributes and information on the color of logs (LBP + HOG + GMM, accuracy of 99.3% for false positives 3.6∙10-3 [4]). A further line of research presented in the paper is the development of effective algorithms for contour analysis and pixel segmentation and the research of these methods for the problem of accurate measurement of log cuts applied to their photo images. References 1. Knyaz, V. A. and Maksimov, A. A. Photogrammetric Technique for Timber Stack Volume Contol // Int. Arch. Photogramm. Remote Sens. Spatial Inf. Sci., XL-3, 157-162, 2014. 2. Knyaz V.A., Vizilter Yu.V., Zheltov S.Yu. Photogrammetric techniques for measurements in woodworking industry // International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences Proceedings. V. XXXIII. Part B5/2. P.42-47. 3. Kruglov, A. V. Development of the rounded objects automatic detection method for the log deck volume measurement // Proc. SPIE 10011, First International Workshop on Pattern Recognition, 1001104 (July 11, 2016). 4. Herbon C., Tönnies K., Stock B. Detection and segmentation of clustered objects by using iterative classification, segmentation, and Gaussian mixture models and application to wood log detection // Pattern Recognition. Springer International Publishing, (2014), pp. 354-364. 5. Gutzeit E., Voskamp J. Automatic segmentation of wood logs by combining detection and segmentation // International Symposium on Visual Computing. pp. 252–261 (2012). 6. Galsgaard B., Lundtoft D. H., Nikolov I., Nasrollahi K., Moeslund T. B. Circular Hough Transform and Local Circularity Measure for Weight Estimation of a Graph-Cut Based Wood Stack Measurement // IEEE Winter Conference on Applications of Computer Vision, Waikoloa, HI, 2015, pp. 686-693. 7. Dalal N., Triggs B. Histograms of oriented gradients for human detection // IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR'05), San Diego, CA, USA, 2005, pp. 886-893 vol. 1. 8. Breiman L. Random forests // Machine Learning, 45(1): 5–32, 2001. 9. Loy G., Zelinsky A. Fast radial symmetry for detecting points of interest // PAMI, vol. 25, pp. 959–973, August 2003. 10. Viola P., Jones M. Rapid object detection using a boosted cascade of simple features // Proc. Int. Conf. on Computer Vision and Pattern Recognition. 2001. № 1. P. 511−518. 11. Ojala T., Pietikainen M., Harwood D. Performance evaluation of texture measures with classification based on Kullback discrimination of distributions // Proceedings of the 12th IAPR International Conference on Pattern Recognition, 1994, vol. 1 - Conference A: Computer Vision & Image Processing, vol. 1, pp. 582–585, Oct 1994. 12. Déniz O., Bueno G., Salido J., De la Torre F. Face recognition using Histograms of Oriented Gradients // Pattern Recogn. Lett. 32, 12 (September 2011), 1598-1603. 13. Misra A., Takashi A., Okatani T., Deguchi K. Hand Gesture Recognition Using Histogram of Oriented Gradients and Partial Least Squares Regression // MVA2011, IAPR Conference on Machine Vision Applications; 2011; Nara, Japan. 14. Herbon С. The HAWKwood Database // CoRR abs/1410.4393 (2014): n. pag. 15. Wang X., Doretto G., Sebastian T.B., Rittscher J., Tu P.H. Shape and Appearance Context Modeling // Proceedings of IEEE International Conference on Computer Vision (ICCV) 2007.