Quantum Inspired Meta-heuristics for Image Analysis

SANDIP DEY, PHD, is an Associate Professor and Chair in the department of Computer Science & Engineering at the Global Institute of Management and Technology, Krishnanagar, Nadia, West Bengal, India. SIDDHARTHA BHATTACHARYYA, PHD, is the Principal of RCC Institute of Information Technology, Kolkata, India. UJJWAL MAULIK, PHD, is the Chair of and Professor in the Department of Computer Science and Engineering, Jadavpur University, Kolkata, India.

• Preface xiiiAcronyms xv1 Introduction 11.1 Image Analysis 31.1.1 Image Segmentation 41.1.2 Image Thresholding 51.2 Prerequisites of Quantum Computing 71.2.1 Dirac’s Notation 81.2.2 Qubit 81.2.3 Quantum Superposition 81.2.4 Quantum Gates 91.2.4.1 Quantum NOT Gate (Matrix Representation) 91.2.4.2 Quantum Z Gate (Matrix Representation) 91.2.4.3 Hadamard Gate 101.2.4.4 Phase Shift Gate 101.2.4.5 Controlled NOT Gate (CNOT) 101.2.4.6 SWAP Gate 111.2.4.7 Toffoli Gate 111.2.4.8 Fredkin Gate 121.2.4.9 Quantum Rotation Gate 131.2.5 Quantum Register 141.2.6 Quantum Entanglement 141.2.7 Quantum Solutions of NP-complete Problems 151.3 Role of Optimization 161.3.1 Single-objective Optimization 161.3.2 Multi-objective Optimization 181.3.3 Application of Optimization to Image Analysis 181.4 Related Literature Survey 191.4.1 Quantum-based Approaches 191.4.2 Meta-heuristic-based Approaches 211.4.3 Multi-objective-based Approaches 221.5 Organization of the Book 231.5.1 Quantum Inspired Meta-heuristics for Bi-level Image Thresholding 241.5.2 Quantum Inspired Meta-heuristics for Gray-scale Multi-level Image Thresholding 241.5.3 Quantum Behaved Meta-heuristics for True Color Multi-level Thresholding 241.5.4 Quantum Inspired Multi-objective Algorithms for Multi-level Image Thresholding 241.6 Conclusion 251.7 Summary 25Exercise Questions 262 Review of Image Analysis 292.1 Introduction 292.2 Definition 292.3 Mathematical Formalism 302.4 Current Technologies 302.4.1 Digital Image Analysis Methodologies 312.4.1.1 Image Segmentation 312.4.1.2 Feature Extraction/Selection 322.4.1.3 Classification 342.5 Overview of Different Thresholding Techniques 352.5.1 Ramesh’s Algorithm 352.5.2 Shanbag’s Algorithm 362.5.3 Correlation Coefficient 372.5.4 Pun’s Algorithm 382.5.5 Wu’s Algorithm 382.5.6 Renyi’s Algorithm 392.5.7 Yen’s Algorithm 392.5.8 Johannsen’s Algorithm 402.5.9 Silva’s Algorithm 402.5.10 Fuzzy Algorithm 412.5.11 Brink’s Algorithm 412.5.12 Otsu’s Algorithm 432.5.13 Kittler’s Algorithm 432.5.14 Li’s Algorithm 442.5.15 Kapur’s Algorithm 442.5.16 Huang’s Algorithm 452.6 Applications of Image Analysis 462.7 Conclusion 472.8 Summary 48Exercise Questions 483 Overview of Meta-heuristics 513.1 Introduction 513.1.1 Impact on Controlling Parameters 523.2 Genetic Algorithms 523.2.1 Fundamental Principles and Features 533.2.2 Pseudo-code of Genetic Algorithms 533.2.3 Encoding Strategy and the Creation of Population 543.2.4 Evaluation Techniques 543.2.5 Genetic Operators 543.2.6 Selection Mechanism 543.2.7 Crossover 553.2.8 Mutation 563.3 Particle Swarm Optimization 563.3.1 Pseudo-code of Particle Swarm Optimization 573.3.2 PSO: Velocity and Position Update 573.4 Ant Colony Optimization 583.4.1 Stigmergy in Ants: Biological Inspiration 583.4.2 Pseudo-code of Ant Colony Optimization 593.4.3 Pheromone Trails 593.4.4 Updating Pheromone Trails 593.5 Differential Evolution 603.5.1 Pseudo-code of Differential Evolution 603.5.2 Basic Principles of DE 613.5.3 Mutation 613.5.4 Crossover 613.5.5 Selection 623.6 Simulated Annealing 623.6.1 Pseudo-code of Simulated Annealing 623.6.2 Basics of Simulated Annealing 633.7 Tabu Search 643.7.1 Pseudo-code of Tabu Search 643.7.2 Memory Management in Tabu Search 653.7.3 Parameters Used in Tabu Search 653.8 Conclusion 653.9 Summary 65Exercise Questions 664 Quantum Inspired Meta-heuristics for Bi-level Image Thresholding 694.1 Introduction 694.2 Quantum Inspired Genetic Algorithm 704.2.1 Initialize the Population of Qubit Encoded Chromosomes 714.2.2 Perform Quantum Interference 724.2.2.1 Generate Random Chaotic Map for Each Qubit State 724.2.2.2 Initiate Probabilistic Switching Between Chaotic Maps 734.2.3 Find the Threshold Value in Population and Evaluate Fitness 744.2.4 Apply Selection Mechanism to Generate a New Population 744.2.5 Foundation of Quantum Crossover 744.2.6 Foundation of Quantum Mutation 744.2.7 Foundation of Quantum Shift 754.2.8 Complexity Analysis 754.3 Quantum Inspired Particle Swarm Optimization 764.3.1 Complexity Analysis 774.4 Implementation Results 774.4.1 Experimental Results (Phase I) 794.4.1.1 Implementation Results for QEA 914.4.2 Experimental Results (Phase II) 964.4.2.1 Experimental Results of Proposed QIGA and Conventional GA 964.4.2.2 Results Obtained with QEA 964.4.3 Experimental Results (Phase III) 1144.4.3.1 Results Obtained with Proposed QIGA and Conventional GA 1144.4.3.2 Results obtained from QEA 1174.5 Comparative Analysis among the Participating Algorithms 1204.6 Conclusion 1204.7 Summary 121Exercise Questions 121Coding Examples 1235 Quantum Inspired Meta-Heuristics for Gray-Scale Multi-Level Image Thresholding 1255.1 Introduction 1255.2 Quantum Inspired Genetic Algorithm 1265.2.1 Population Generation 1265.2.2 Quantum Orthogonality 1275.2.3 Determination of Threshold Values in Population and Measurement of Fitness 1285.2.4 Selection 1295.2.5 Quantum Crossover 1295.2.6 Quantum Mutation 1295.2.7 Complexity Analysis 1295.3 Quantum Inspired Particle Swarm Optimization 1305.3.1 Complexity Analysis 1315.4 Quantum Inspired Differential Evolution 1315.4.1 Complexity Analysis 1325.5 Quantum Inspired Ant Colony Optimization 1335.5.1 Complexity Analysis 1335.6 Quantum Inspired Simulated Annealing 1345.6.1 Complexity Analysis 1365.7 Quantum Inspired Tabu Search 1365.7.1 Complexity Analysis 1365.8 Implementation Results 1375.8.1 Consensus Results of the Quantum Algorithms 1425.9 Comparison of QIPSO with Other Existing Algorithms 1455.10 Conclusion 1655.11 Summary 166Exercise Questions 167Coding Examples 1906 Quantum Behaved Meta-Heuristics for True Color Multi-Level Image Thresholding 1956.1 Introduction 1956.2 Background 1966.3 Quantum Inspired Ant Colony Optimization 1966.3.1 Complexity Analysis 1976.4 Quantum Inspired Differential Evolution 1976.4.1 Complexity Analysis 2006.5 Quantum Inspired Particle Swarm Optimization 2006.5.1 Complexity Analysis 2006.6 Quantum Inspired Genetic Algorithm 2016.6.1 Complexity Analysis 2036.7 Quantum Inspired Simulated Annealing 2036.7.1 Complexity Analysis 2046.8 Quantum Inspired Tabu Search 2046.8.1 Complexity Analysis 2066.9 Implementation Results 2076.9.1 Experimental Results (Phase I) 2096.9.1.1 The Stability of the Comparable Algorithms 2106.9.2 The Performance Evaluation of the Comparable Algorithms of Phase I 2256.9.3 Experimental Results (Phase II) 2356.9.4 The Performance Evaluation of the Participating Algorithms of Phase II 2356.10 Conclusion 2946.11 Summary 294Exercise Questions 295Coding Examples 2967 Quantum Inspired Multi-objective Algorithms for Multi-level Image Thresholding 3017.1 Introduction 3017.2 Multi-objective Optimization 3027.3 Experimental Methodology for Gray-Scale Multi-Level Image Thresholding 3037.3.1 Quantum Inspired Non-dominated Sorting-Based Multi-objective Genetic Algorithm 3037.3.2 Complexity Analysis 3057.3.3 Quantum Inspired Simulated Annealing for Multi-objective Algorithms 3057.3.3.1 Complexity Analysis 3077.3.4 Quantum Inspired Multi-objective Particle Swarm Optimization 3087.3.4.1 Complexity Analysis 3097.3.5 Quantum Inspired Multi-objective Ant Colony Optimization 3097.3.5.1 Complexity Analysis 3107.4 Implementation Results 3117.4.1 Experimental Results 3117.4.1.1 The Results of Multi-Level Thresholding for QINSGA-II, NSGA-II, and SMS-EMOA 3127.4.1.2 The Stability of the Comparable Methods 3127.4.1.3 Performance Evaluation 3157.5 Conclusion 3277.6 Summary 327Exercise Questions 328Coding Examples 3298 Conclusion 333Bibliography 337Index 355