Open access peer-reviewed chapter

Simulated Annealing: A Novel Application of Image Processing in the Wood Area

Written By

Cristhian A. Aguilera, Mario A. Ramos and Angel D. Sappa

Submitted: November 23rd, 2011 Reviewed: June 12th, 2012 Published: August 29th, 2012

DOI: 10.5772/50635

Chapter metrics overview

2,361 Chapter Downloads

View Full Metrics

1. Introduction

Material’s internal structure knowledge is highly relevant to improve quality indexes [1]. 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 [2]). Internal characteristics of materials have been studied with different non-destructive techniques, including ultrasound [3], microwaves [4-7,8], gamma rays, X-rays, nuclear magnetic resonance and, lately, artificial vision techniques [9]. 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 [23]. 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.

Figure 1.

X-ray tomography process of wood log.

Advertisement

2. The deformable contour

A deformable contour or snake [24] is a parametric curve of the type:

us=(xs,ys)E1

where x(s)and y(s)are coordinates along the contour ands[0,1]. These contours are influenced by internal and external forces and forces typically related to the gradient of the intensity of the image, mathematically:

Esnake=01Eintu(s)+Eextu(s)+Eimgu(s)dsE2

where:

Eint(x)=α(s)|xs(s)|2+β(s)|xss(s)|2TensionStiffness

Eexts, = shape energy measurement of external constraints either from higher level shape information or user applied energy.

Eimg=-ϏI2

The internal energy, Eint, with alpha and beta parameters, controls the tension and rigidity of the contour; Eextrepresents measures or external considerations with respect to the shape of the contour; and Eimgis 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 2.

Evolution of a deformable contour.

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.

Figure 3.

a) Tomographic image; (b) knot (enlargement); (c) gradient of the image; (d) segmentation through a deformable contour.

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.

Figure 4.

Deformable contour and distracter points; (a) original contour; (b) final contour; (c) original contour with distracter point; and (d) final contour with distracter point.

Advertisement

3. Simulated Annealing

Simulated annealing (SA) is a stochastic optimization technique introduced by Kirkpatrick [25]. 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:

e-E/T>RE5

with:ΔE:Difference between the present and the candidate solutions

T:Temperature

R:Random uniform number between [0,1]

ΔEreflects the change in the objective function and Tis the current temperature. The way how the temperature decreases along the algorithm is commonly known as the Cooling Schedule and several types of cooling can be found in the literature as well as stopping criterion of the algorithm.

Figure 5.

X-ray tomography of de wood log.

Several implementations and variations of SA can be found in the literature: Threshold Accepting (TA), [26]; Boltzmann Annealing (BA), [27]; Simulated Quelching (SQ), [27]; Fast annealing (FA), [27] 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: T(k) =T0/ln k. It should be noticed that since the searching space of our application is not too big, the slowness problem of the method is not relevant. Figure 6 presents the pseudo-code of the algorithm used in the current work.

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.

Figure 6.

Simulated Annealing Algorithm used in the current work

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 nxnpixels is created for every pixel in the contour. Then, in that neighborhood a new candidate vertexis selected by evaluating it according to the energy function; the acceptance of this new vertex will depend on criteria such as the number of iterations, number of acceptances and the probability of “bad solution” acceptance according to the temperature. Additionally, a criterion for the elimination and creation of new vertices is used. This criterion is based on the distance between the vertices in the contour and allows a homogeneous distribution through the whole contour. Once all the vertices in the contour have been checked for a given temperature Ti(Fig. 6) the criterion for elimination and creation is applied. A vertex is eliminated in case the distance to its neighbor is smaller than a minimum distance (dmin). Similarly, a vertex is created in case the distance between two vertices is higher than a maximum allowed distance (dmax). Figure 7 shows an example where a neighborhood of 3x3pixels is considered

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 Pinus radiatawood. We can see that this method can be strongly influenced by other objects in the image, or by points of intensities not related to the object, producing a poor segmentation of the defect.

Figure 7.

Illustration of a contour evolution for a neighborhood patch of3x3pixels. For every contour vertex a new candidate vertex is created and accepted according to a set of user defined parameters.

Figure 8.

Evolution of a deformable contour: (a) initial image; (b) and (c) initial contour; (d) final contour.

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.

Figure 9.

a) and (b) Tomographic image of a knot, (c) knot (enlargement), (d) gradient of the image.

Advertisement

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.

Figure 10.

Tomography of a log; (left) transversal cuts; (right) enlarged image.

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.

Figure 11.

Evolution of an initial contour around an isolated knot; (a) greedy algorithm; (b) simulated annealing algorithm.

Figure 12.

Evolution of an initial contour around a knot with interference from growth rings; (a) greedy algorithm; (b) simulated annealing algorithm.

Figure 13.

Evolution of an initial contour around a knot with interference from growth rings; (a) greedy algorithm; (b) simulated annealing algorithm

Advertisement

5. Conclusions

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.

Advertisement

Acknowledgement

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.

References

  1. 1. Benson-CooperD.KnowlesR.ThompsomF.CownD.1982Detection of defaults in logs, Forest Research Institute of New Zeeland8912
  2. 2. HarlessT.WagnerF.SteeleP.TaylorF.YadamaV.Mc MillinC.1991Methodology for locating defect within hardwood logs and determining their impact on lumber value yield, Forest Product Journal412530
  3. 3. SandozJ.1993Moisture content and temperature effect on ultrasound timber grading, Wood Science and Technology27373380
  4. 4. MartinP.ColletP.BarthelemyP.RoussyG.1987Evaluation of wood characteristics: internal scanning off the material by microwaves, Wood Science and Technology21361371
  5. 5. KingR.1991Measurement of basic weight and moisture content of composite board using microwave, VIII Int. Symp. On non-destructive testing osf wood12132
  6. 6. GappV.MallickG.1995Capteur intelligent pour la mesure de la humdité dans le matériau par technique micro-ondes, Journées Nationales Micro-ondes735357
  7. 7. BaraditE.AedoR.CorreaJ.2006Knot detection in Wood using microwaves, Wood Science and Technology40118123
  8. 8. LundgrenN.BrännströmM.HagmanO.OjaJ.2007Predicting the Strength of Norway Spruce by Microwave Scanning: A Comparison with Other Scanning Techniques, Wood and Fiber Science39167172
  9. 9. ThomasL.MiliL.2006Defect Detection on Hardwood Logs Using Laser Scanning, Wood and Fiber Science38243246
  10. 10. FuntB.BryantE.1987Detection of internal log defects by automatic interpretation of computer tomography images, Forest Product Journal3715662
  11. 11. ZhuD.ConnersR.SchmoldtD.AramanP.1996A prototype Vision System for Analyzing CT Imagery of Hardwood Logs. IEEE Transactions on Systems, Man and Cybernetics26522532
  12. 12. RojasG.HernándezR.CondalA.VerretD.BeauregardR.2005Exploration of the Physical Properties of Internal Characteristics of Sugar Maple Logs and Relationships with CT Images, Wood and Fiber Science37591604
  13. 13. ErikssonJ.JohanssonH.DanvindJ.2006Numerical Determination of Diffusion Coefficients in Wood Using Data From CT-Scanning, Wood and Fiber Science38334344
  14. 14. SarigulE.AbbottL.SchmoldtD.2001Nondestructive rule-based defect detection and indentification system in CT images of hardwood logs, Review of Progress in Nondestructive Evaluation2019361943
  15. 15. OjaJ.GrundbergS.GronlundA.1998Measuring the outer shape of pinus sylvestris saw logs with an x-ray log scanner, Scandinavian Journal Forest13340347
  16. 16. SandozJ.1993Moisture content and temperature effect on ultrasound timber grading, Wood Science and Technology27373380
  17. 17. LindgrenL.1991Medical CAT-Scanning: x-ray CT-numbers and their relation to wood density, Wood Science and Technology25341349
  18. 18. SchmoldtD.HeJ.AbbortA.2000Automated Labeling of log feature in CT imagery of multiple hardwood species, Wood and Fiber Science32287300
  19. 19. TaylorF.WagnerF.Mc MillinC.MorganI.HopkinsF.1984Locating Knots by Industrial Tomography, Forest Product Journal344246
  20. 20. WagnerF.RoderF.1989Ultrafast CT scanning of an oak log for internal defect, Technical Note, Forest product journal396264
  21. 21. DaweiQ.ZhangP.XuejingJ.2010Detection of Wood Image, Sixth International Conference on Natural Computation 1459:1463.
  22. 22. DaweiQ.HongboM.MingmingZ.LeiY.2008Detection of Wood Defects From X-ray Image by ANN, Proceedings of the IEEE International Conference on Automation and Logistics 23:28.
  23. 23. BorianneP.PernaudatR.SubsolG.2011Automated Delineation of Tree-Rings in X-Ray Computed Tomography Images of Wood. IEEE International Conference on Image Processing445448
  24. 24. KassM.WikinsK.TerzopoulosD.1988Snake: Active Contour Model, International Journal of Computer Vision4321331
  25. 25. KirkpatrickS.GelattC.VecchiM.1983Optimization by Simulated Annealing, Science2204598671680
  26. 26. IngberL.1993Simulated annealing: Practice versus theory, Mathl. Comput. Modelling,18112957
  27. 27. DueckG.ScheuerT.1990Threshold accepting: A general purpose optimization algorithm appearing superior to simulated annealing, Journal of Computational Physics,90161175

Written By

Cristhian A. Aguilera, Mario A. Ramos and Angel D. Sappa

Submitted: November 23rd, 2011 Reviewed: June 12th, 2012 Published: August 29th, 2012