Material’s internal structure knowledge is highly relevant to improve quality indexes . For example, the exact information of the internal structure of a wood log or lumber such as density and internal defects is an important economic advantage (see ). Internal characteristics of materials have been studied with different non-destructive techniques, including ultrasound , microwaves [4-7,8], gamma rays, X-rays, nuclear magnetic resonance and, lately, artificial vision techniques . X-rays have been used to examine the internal characteristics of many materials [10-13].
In the wood industry, some applications have been found that allow the recognition of different types of defects of the raw material [14,15]. Methods for measuring moisture [16-18] have also been developed. Some works have been presented related to knot detection [19,20]. Recently, several approaches have been proposed in the literature along these lines of research; for example in the detection of wood defects [21,22], and more specifically to detect tree-ring knots in wood . However, automatic defect recognition in the manufacture process is ever more necessary and fundamental.
An X-ray computerized tomography reflects variations on the density of an object or body. X-ray sensors reveal the shape of a log below the bark, allowing the detection of macroscopic and microscopic aspects. The latter favors its application in the wood industry, for example Figure 1 shows images of X-ray tomography on wood log. In these illustrations can be clearly seen internal constitutions such as knots and knotty cylinder: a) wood log, b) X-ray computed tomography, c) and d) images of two cuts.
The current work is focused on the visual inspection of wood in order to automatically detect classical defects such as knots and knotty cylinders. The proposed approach is based on the use of simulated annealing in deformable contours and X-ray tomography. The remainder of the manuscript is organized as follow. Firstly, the deformable contour technique, which is used to represent detected defect, is presented. Then, Section 3 introduces the simulated annealing-based optimization that is used to obtain an accurate description of wood’s defect. Experimental results and discussions are given in Section 4. Finally, conclusions and future works are provided in Section 5.
2. The deformable contour
A deformable contour or snake  is a parametric curve of the type:
, = shape energy measurement of external constraints either from higher level shape information or user applied energy.
The internal energy, , with alpha and beta parameters, controls the tension and rigidity of the contour; represents measures or external considerations with respect to the shape of the contour; and is the force related to the gradient of the image given a Gaussian-type convolution filter. The contour is initially located near the object to be segmented in the image. Then, the attraction and repulsion forces, generated by internal, external image forces, deform the contour until surrounds the object; thereby isolating the object with respect to the overall image. Minimizing the energy equation allows the final solution of the contour (see Fig. 2).
Figure 3 presents a tomographic image of a log; Fig. 3(a) shows the tomographic image itself, in which two knots, and the appearance of a third knot, can clearly be seen at the bottom of the image; Fig. 3(b) shows the enlarged sector of the image corresponding to a particular knot. Figure 3(c) represents the gradient of the image; the most intense points represent the greatest values of the gradient. These forces guide the contour around the knot in order to completely isolate it, as shown in Fig. 3(d). One of the problems to confront is to identify, given the energy function and initial contour, the location of each new point of the contour. This can be done with different search algorithms.
The deformable contour presented in Fig. 3(d) capture the knot’s shape present in the image but also some inaccuracies due to noisy date. Actually, these inaccuracies can be due to noise or distracter points; both points distort the contour by attracting or repulsing it (Fig. 4). This is the case of tomography X-ray images in which other objects or variation in object density (e.g., other knots or water saturation in wood pieces) artificially loses the form of the objects to detect, provoking by this influence, and a large error in segmentation.
For example, a tomography image with distinct singularities or objects can be appreciated in Fig. 5. In a) and b), the tomography with low humidity is presented, involving very clear and easy-to-segment images; however, in c) and d) an image with a very high humidity, can be appreciated. Since it is not homogeneously distributed, the object to be segmented can be deformed.
Several techniques have been employed to improve these aspects, like characteristic extraction techniques and improvements in the energy function. However, when there is a prior-knowledge about the objects to detect, such as in the case of well-defined objects and with known forms and characteristics, this information can be incorporated into the energy function. Some approaches, like Deformable Templates, use templates defined a priori and transform the deformation problem to a template adjustment problem. However, even though this produces good results, it suffers from the rigidity due to the templates.
Besides incorporating more information in the energy function, for the case of images of nodes, can significantly improve the quality of final contours. Hence, the final segmentation can be improved by using methods that allow the contour freely explore neighborhood areas in the stage of evolution. The latter makes the simulated annealing, an ideal candidate for solving this type of problems.
3. Simulated Annealing
Simulated annealing (SA) is a stochastic optimization technique introduced by Kirkpatrick . This algorithm begins by selecting an initial solution and later generating a new state, randomly generating a new solution in the neighbourhood of the current solution; this is called a neighbour solution. This new state is evaluated and compared with the previous solution. If the solution from the new state is better than the previous one, it is accepted; but if it is not, it is accepted or rejected with some probability. The probability of accepting a new state is given by:
with::Difference between the present and the candidate solutions
Several implementations and variations of SA can be found in the literature: Threshold Accepting (TA), ; Boltzmann Annealing (BA), ; Simulated Quelching (SQ), ; Fast annealing (FA),  among others. The latest approaches, SQ and FA, are mainly focused on speeding up the searching for the right solution, which is one of the main drawbacks of BA.
In the current work a classical simulated annealing algorithm is used. A Bolztman distribution (BA) is assumed and consequently, a logarithmic cooling schedule is used:
The ability to accept poor solutions early in the evolution of a deformable contour is a powerful tool to explore complex areas of the image and get better final solutions. Then, SA provides a method of local evolution of each of the points of a contour, allowing the objects in a target to be more accurately represented.
For the case of the images obtained by X-ray computed tomography applied to wood, unlike the steepest descent method that provides a global search method, there are other methods that are based on a local view to find a global minimum. In the current work we propose to use a method based on SA, which is based on a local view, and in this case, local portions of the contour, to find a global minimum of the energy function. SA explores the possibilities in a local environment of the contour and it evolves in the direction of minimum energy. The method initially considers the generation of a contour in the 2D image space by using a given number of vertices. A neighborhood patch of
Figure 8 shows a deformable contour applied to a knot in a X-ray tomography, the contour near to the object to be segmented is attracted and deformed by the force of the image until the contour completely surrounds the object. The forces coming from the gradient of the images guide the contour until it is located around the object’s borders. In Fig. 8, we can see the evolution of the contour for the segmentation of knots in
In general, the tomography of logs show the existence of the distortions in the shape of the knots and forces of attraction in other regions of the contour not associated with the knot (in this case, growth rings) and in zones or points that influence the contour, thereby causing a poor final segmentation. Figure 9(a) and (b) present a tomographic image of a wood log; an enlargement of a knot is presented in Fig. 9(c); the corresponding gradient image is depicted in Fig. 9(d). Note that in Fig. 9(c), the most intense points represent the greatest values of the gradient. These forces guide the contour around the knot in order to completely isolate it, but not all are related to force the knot. The latter is one of the problems to be properly solved by the segmentation methods.
4. Result and discussion
According to the above description and using the energy functions described in (2), we proceeded to analyse the images from the X-ray computerized topographies of logs with different characteristics. To carry out these experiments, we used discreet versions of the energy functions and a local optimization algorithm based on the greedy algorithm and another based on classic Boltzmann Annealing with T0=1000. The tests were carried out with topographies of various logs using a medical scanner. In total, 90 images were analysed. The most relevant results are shown in the following figures.
Figure 10 shows a sequence of images revealing the evolution of the knots inside a log. On the left, we can see the images of the complete log and, on the right, an enlargement of the image corresponding to a single knot. Figure 11 shows the situation of a knot that appears to be an isolated object in the image: Fig. 11(a) shows the result of the segmentation using the greedy algorithm; and Fig. 11(b) presents the result using SA. In both cases, the segmentation gives good results; the contour becomes deformed around the knot, isolating it completely. It should be noted here that, in this case, the knot in the image appears to be totally isolated and there are no objects that distort the contour deformation. Figure 12 presents the result of the segmentation in a case in which the knots are confused with the growth rings: Fig. 12(a) shows the result when the greedy algorithm is used; and Fig. 12(b) depicts the result with SA. In this case, a considerable difference can be appreciated between the two methods. The energy gradients generated by the image of the growth rings tend to move the contour away from the knot. However, with SA, due to its random exploration characteristic, in general it tends to better segment the knot. In Fig. 13, the situation is more critical. In these images the knots are merged with the growth rings; in fact, the knot is only partially visible in the tomographic image, and it appears to be an object with different geometric characteristics than those visible in the previous images. Figure 13(a) shows the result of the evolution of the contour with the greedy algorithm; in this case the algorithm clearly does not surround the knot correctly and the result of the segmentation is extremely poor. Nonetheless, in Fig. 13(b), with SA and thanks to a wider exploration, the general result is perceptibly better.
As we can see in the figures presented above, in some situations the images obtained by X-ray computerized topographies facilitate the segmentation. Nevertheless, in other situations, the segmentation is seriously complicated by confusion with other objects in the image. In particular, growth rings and other objects distract the contours. In such cases, a classical optimization algorithm such as the greedy algorithm does not provide good results, principally due to the tendency of local minima. However, SA provides a more robust method for presenting better results in these situations.
From the experimental results presented above, we can conclude that the proposed method is a very good alternative for knot segmentation. The use of SA allows much more precise segmentation of knots with greater irregularities in the images. Nonetheless, the initial position of the deformable contour is of vital importance for a good identification. We can also use the results obtained to infer that both excessive humidity content in the logs and growth rings present inconveniences. The latter presents a great challenge since the knot shows up in the images obtained with X-rays both in isolation and confused with other objects. In the second case, additional information, for example morphological information on the knots, can be incorporated into the contour’s energy function that describes the force of the image, offering a very good alternative. The cases examined correspond to segmentation by X-ray computerized tomography for logs having distortions mainly due to their storage; this causes the density of the material to increase, which then has an effect on the images. This case is of great interest for the wood industry. However, this technique can also be used in other situations such as the study of other defects in logs. The authors are currently developing 3D techniques and a way to reduce the method’s computerization costs that was not considered in this first study.
This work was partially supported from MECESUP2 Postdoctoral program and Regular Project 100710 3/R of the University of Bio-Bio, Chile; and the Spanish Government under Research Program Consolider Ingenio 2010: MIPRCV (CSD2007-00018) and Project TIN2011-25606.
Benson-Cooper D. Knowles R. Thompsom F. Cown D. 1982Detection of defaults in logs, Forest Research Institute of New Zeeland 8 9 12
Harless T. Wagner F. Steele P. Taylor F. Yadama V. Mc Millin C. 1991Methodology for locating defect within hardwood logs and determining their impact on lumber value yield, Forest Product Journal 41 25 30
Sandoz J. 1993Moisture content and temperature effect on ultrasound timber grading, Wood Science and Technology 27 373 380
Martin P. Collet P. Barthelemy P. Roussy G. 1987Evaluation of wood characteristics: internal scanning off the material by microwaves, Wood Science and Technology 21 361 371
King R. 1991Measurement of basic weight and moisture content of composite board using microwave, VIII Int. Symp. On non-destructive testing osf wood 1 21 32
Gapp V. Mallick G. 1995Capteur intelligent pour la mesure de la humdité dans le matériau par technique micro-ondes, Journées Nationales Micro-ondes 73 53 57
Baradit E. Aedo R. Correa J. 2006Knot detection in Wood using microwaves, Wood Science and Technology 40 118 123
Lundgren N. Brännström M. Hagman O. Oja J. 2007Predicting the Strength of Norway Spruce by Microwave Scanning: A Comparison with Other Scanning Techniques, Wood and Fiber Science 39 167 172
Thomas L. Mili L. 2006Defect Detection on Hardwood Logs Using Laser Scanning, Wood and Fiber Science 38 243 246
Funt B. Bryant E. 1987Detection of internal log defects by automatic interpretation of computer tomography images, Forest Product Journal 37 1 56 62
Zhu D. Conners R. Schmoldt D. Araman P. 1996A prototype Vision System for Analyzing CT Imagery of Hardwood Logs. IEEE Transactions on Systems, Man and Cybernetics 26 522 532
Rojas G. Hernández R. Condal A. Verret D. Beauregard R. 2005Exploration of the Physical Properties of Internal Characteristics of Sugar Maple Logs and Relationships with CT Images, Wood and Fiber Science 37 591 604
Eriksson J. Johansson H. Danvind J. 2006Numerical Determination of Diffusion Coefficients in Wood Using Data From CT-Scanning, Wood and Fiber Science 38 334 344
Sarigul E. Abbott L. Schmoldt D. 2001Nondestructive rule-based defect detection and indentification system in CT images of hardwood logs, Review of Progress in Nondestructive Evaluation 20 1936 1943
Oja J. Grundberg S. Gronlund A. 1998Measuring the outer shape of pinus sylvestris saw logs with an x-ray log scanner, Scandinavian Journal Forest 13 340 347
Sandoz J. 1993Moisture content and temperature effect on ultrasound timber grading, Wood Science and Technology 27 373 380
Lindgren L. 1991Medical CAT-Scanning: x-ray CT-numbers and their relation to wood density, Wood Science and Technology 25 341 349
Schmoldt D. He J. Abbort A. 2000Automated Labeling of log feature in CT imagery of multiple hardwood species, Wood and Fiber Science 32 287 300
Taylor F. Wagner F. Mc Millin C. Morgan I. Hopkins F. 1984Locating Knots by Industrial Tomography, Forest Product Journal 34 42 46
Wagner F. Roder F. 1989Ultrafast CT scanning of an oak log for internal defect, Technical Note, Forest product journal 39 62 64
Dawei Q. Zhang P. Xuejing J. 2010Detection of Wood Image, Sixth International Conference on Natural Computation 1459:1463.
Dawei Q. Hongbo M. Mingming Z. Lei Y. 2008Detection of Wood Defects From X-ray Image by ANN, Proceedings of the IEEE International Conference on Automation and Logistics 23:28.
Borianne P. Pernaudat R. Subsol G. 2011Automated Delineation of Tree-Rings in X-Ray Computed Tomography Images of Wood. IEEE International Conference on Image Processing 445 448
Kass M. Wikins K. Terzopoulos D. 1988Snake: Active Contour Model, International Journal of Computer Vision 4 321 331
Kirkpatrick S. Gelatt C. Vecchi M. 1983Optimization by Simulated Annealing, Science 220 4598 671 680
Ingber L. 1993Simulated annealing: Practice versus theory, Mathl. Comput. Modelling, 18 11 29 57
Dueck G. Scheuer T. 1990Threshold accepting: A general purpose optimization algorithm appearing superior to simulated annealing, Journal of Computational Physics, 90 161 175