RECONSTRUCTION ALGORITHMS BASED ON SIMULATED ANNEALING IN DISCRETE TOMOGRAPHY

Abstract

The ability to retrieve information about the interior of any object without cutting or damaging the object in any way is simply incredible. This is the power of tomography. Tomography deals with reconstructing a structure of object from projection data obtained by illuminating the object by some radiation. Tomographic reconstruction has a huge impact on the world by its enormous and diverse applications. For instances, in radiology tomography provides insight into the human body without surgical intervention, in material science crystalline structures are reconstructed from images obtained by transmission electron microscopes, in archaeology tomographic techniques are used to extract vital information from the inside of fragile ancient excavations, tomography is used in non-destructive testing for detecting cracks in highly reliable objects, geologists examine the interior of the earth for useful raw materials, etc. In some applications like electron microscopy and non-destructive testing, the object to be reconstructed is composed of only few homogeneous materials or regions. In such cases the number of projections available or required are also very few. This gives rise to the field of Discrete Tomography (DT). DT is a special kind of tomography where the object is characterized by a small number of absorption values and the number of projections typically used are 2 to 10. Mathematically the object in DT is represented by a function 𝑓:𝑋→𝐸, where 𝑋⊆ℤ2 is a discrete set, 𝐸={𝑒1,𝑒2,…,𝑒𝑛:𝑒𝑖∈ℝ0+,1≤𝑖≤𝑛} and its projections along a lattice direction 𝑣∈ℤ2is represented by the function 𝒫𝑓(𝑣):ℒ(𝑣)→ℝ0+ defined as 𝒫𝑓(𝑣)(𝑙)=Σ𝑓(𝑥)𝑥∈𝑋∩𝑙 for each 𝑙∈ℒ(𝑣), where ℒ(𝑣) is the set of all lattice lines along direction 𝑣. Thus the reconstruction problem of DT is to find a discrete function 𝑓from the known values of projections 𝒫𝑓(𝑣𝑖)(𝑙) along lattice directions 𝑣1,…,𝑣𝑘. The most widely studied problem of DT is to build a binary matrix from the given row and column projections. This problem is extremely underdetermined and has a very large solution space. Therefore additional geometrical constraints are imposed on the binary matrix to reduce the solution space. In this thesis, this underdetermined problem is investigated with the additional constraints of periodicity, connectivity, convexity and adjacency. The inclusion of constraints reduces the solution space but makes the problem NP-hard. As a result heuristics like simulated annealing, genetic algorithm, etc. are frequently employed to solve the reconstruction problem. Simulated Annealing (SA) is gaining popularity in reconstruction problems of DT due to its ii efficiency and simplicity. In the present thesis SA is used to solve four reconstruction problems of DT. The first problem encountered in the thesis is reconstruction of (𝑝,𝑞) – periodic binary matrix from given row (𝑅) and column (𝐶) projections. This problem is converted into two independent optimization problems. The first problem searches for a (𝑝,𝑞) – periodic binary matrix in the space of binary matrices having 𝑅 and 𝐶 as row and column projections. The second optimization problem searches for a binary matrix satisfying the given two projections in the space of (𝑝,𝑞) – periodic binary matrices. Then two SA algorithms are developed for the two optimization problems. The algorithms are tested on random noiseless and noisy periodic binary matrices of different sizes and periodicities. The results obtained are promising and the algorithms showed convergence towards the optimal solution. The second problem is the reconstruction of connected binary matrix from two projections (𝑅,𝐶). The problem is transformed into two optimization problems. The first problem searches for a connected binary matrix in the class of binary matrices having projections (𝑅,𝐶) whereas the second problem searches for a binary matrix satisfying the projections (𝑅,𝐶) in the class of connected binary matrices. Further two SA algorithms are developed for the optimization problems and are tested on randomly generated connected binary matrices. Both the algorithms produced excellent results and are found to be robust when tested on noisy images. Third problem deals with the reconstruction of h-convex binary matrix from two projections (𝑅,𝐶). The problem is reformulated into two optimization problems. The first problem searches for an h-convex binary matrix in the class of binary matrices having projections (𝑅,𝐶) while the second problem searches for a binary matrix satisfying the projections (𝑅,𝐶) in the set of h-convex binary matrices. Two SA algorithms are developed for solving the two optimization problems. The algorithms were tested on random matrices and results obtained were encouraging and displayed the convergence of algorithms towards the optimal solution. The fourth and the last problem is to reconstruct an exactly-1-4-adjacent binary matrix from projections (𝑅,𝐶). The problem is once again changed into two optimization problems and two SA algorithms were developed to solve those problems. Both the optimization problems searches for an exactly-1-4-adjacent binary matrix in the space of binary matrices having projections (𝑅,𝐶). Once again the results showed the convergence of algorithms towards optimal solution.