Title: Hybridisation of genetic algorithms and tabu search approach for reconstructing convex binary images from discrete orthogonal projections

Authors: Mohamed Hadded; Fethi Jarray; Ghassen Tlig; Hamadi Hasni

Addresses: TELECOM SudParis, CNRS Samovar UMR 5157, 91011 Evry, France; ENSI, CRISTAL Laboratory, University Campus 2010, Manouba, Tunisia ' Higher Institute of Computer Science, Gabes University, Madnine, Tunisia; CEDRIC CNAM, 292 Rue Saint-Martin 75003, Paris, France ' Higher Institute of Computer Science, Gabes University, Madnine, Tunisia; CEDRIC CNAM, 292 Rue Saint-Martin 75003, Paris, France ' National School of Computer Science, Manouba University, Tunisia; URAPOP Research Unit, 1060 Unversity Campus, Tunis, Tunisia

Abstract: In this paper, we consider a variant of the NP-complete problem of reconstructing HV-convex binary images from two orthogonal projections, noted by RCBI(H, V). This variant is reformulated as a new integer programming problem. Since this problem is NP-complete, a new hybrid optimisation algorithm combining the techniques of genetic algorithms and tabu search methods, noted by GATS is proposed to find an optimal or an approximate solution for RCBI(H, V) problem. GATS starts from a set of solutions called 'population' initialised by using an extension of the network flow model, incorporating a cost function. Two operators, namely crossover and mutation are used to explore the search space, then the quality of each individual in the population is improved by using another local search method named tabu search operator. In this paper we describe the proposed algorithm, then we evaluate and compare its performance with other optimisation techniques. The analysis of the experimental results shows the advantages of our GATS approach in terms of reconstruction quality and computational time.

Keywords: HV-convex discrete tomography; convex binary images; genetic algorithms; tabu search; network flow models; orthogonal projections; image reconstruction; orthogonal projections; modelling; integer programming; hybrid optimisation.

DOI: 10.1504/IJMHEUR.2014.068912

International Journal of Metaheuristics, 2014 Vol.3 No.4, pp.291 - 319

Received: 04 Nov 2013
Accepted: 09 Dec 2014

Published online: 16 Apr 2015 *

Full-text access for editors Access for subscribers Purchase this article Comment on this article