Novel ray-tracing algorithms in NDE: Application of Dijkstra and A* algorithms to the inspection of an anisotropic weld

The degradation of ultrasonic array images due to propagation through an anisotropic material presents a significant inspection problem to the engineering industry. If the distribution of anisotropy is known, ray-tracing algorithms can be used to predict the path of sound through the material and hence correctly image anisotropic components. Conversely, ray-tracing can be used as part of an inversion procedure to infer the anisotropic properties from measured time-of-flight data. However, inversion methods often require thousands of ray-traces to map a single weld and as such, a rapid ray-tracing algorithm is essential for use. This paper explores the use of two path-finding algorithms as applied to a ray-tracing scenario: Dijkstra's algorithm and the A* algorithm. Although prevalent within computer science applications due to their low computation time, both algorithms have seen little use within the NonDestructive Evaluation (NDE) field. This paper aims to both describe the algorithms and to demonstrate their relative merits for application in NDE. Dijkstra's algorithm was applied to an anisotropic weld inspection and the optimal parameters explored, drawing comparison to an equivalent inspection using a beam-bending algorithm to ray-trace. A comparison of accuracy and computation time between Dijkstra's algorithm and the A* algorithm shows them to maintain similar accuracy, but the A* algorithm to exhibit significant reductions in computation time. (C) 2013 Elsevier Ltd. All rights reserved.