Quantum Inspired Meta-Heuristics for Image Analysis

Preface xvii Acronyms xxi 1 Introduction 1 1.1 Image Analysis 4 1.1.1 Image Segmentation 7 1.1.2 Image Thresholding 9 1.2 Prerequisites of Quantum Computing 13 1.2.1 Dirac's Notation 14 1.2.2 Qubit 15 1.2.3 Quantum Superposition 15 1.2.4 Quantum Gates 16 1.2.5 Quantum Register 24 1.2.6 Quantum Entanglement 25 1.2.7 Quantum Solutions of NP-complete Problems 27 1.3 Role of Optimization 28 1.3.1 Single-objective Optimization 29 1.3.2 Multi-objective Optimization 32 1.3.3 Application of Optimization to Image Analysis 33 1.4 Related Literate Survey 34 1.4.1 Quantum Based Approaches 35 1.4.2 Meta-heuristic Based Approaches 38 1.4.3 Multi-objective Based Approaches 41 1.5 Organization of the Book 43 1.5.1 Quantum Inspired Meta-heuristics for Bi-level Image Thresholding 44 1.5.2 Quantum Inspired Meta-heuristics for Gray Scale Multi-level Image Thresholding 1.5.3 Quantum Behaved Meta-heuristics for True Colour Multi-level Thresholding 45 1.5.4 Quantum Inspired Multi-objective Algorithms for Multi-level Image Thresholding 1.6 Conclusions and Further Scope 46 1.7 Summary 47 1.8 Exercise Questions 48 1.8.1 Multiple Choice Questions 48 1.8.2 Short Answer Type Questions 50 1.8.3 Long Answer Type Questions 50 2 Review of Image Analysis 53 2.1 Introduction 53 2.2 Definition 54 2.3 Mathematical Formalism 55 2.4 Current Technologies 56 2.4.1 Digital Image Analysis Methodologies 56 2.5 Overview of Different Thresholding Techniques 65 2.5.1 Ramesh's Algorithm 66 2.5.2 Shanbag's Algorithm 67 2.5.3 Correlation Coefficient 68 2.5.4 Pun's Algorithm 70 2.5.5 Wu's Algorithm 71 2.5.6 Reny's Algorithm 72 2.5.7 Yen's Algorithm 73 2.5.8 Johannsen's Algorithm 74 2.5.9 Silva's Algorithm 75 2.5.10 Fuzzy's Algorithm 76 2.5.11 Brinks's Algorithm 76 2.5.12 Otsu's Algorithm 79 2.5.13 Kittlers's Algorithm 79 2.5.14 Li's Algorithm 80 2.5.15 Kapur's Algorithm 82 2.5.16 Huang's Algorithm 83 2.6 Applications of Image Analysis 85 2.7 Conclusion 88 2.8 Summary 88 2.9 Exercise Questions 89 2.10 Multiple Choice Questions89 2.11 Short Answer Type Questions91 2.12 Long Answer Type Questions91 3 Overview of Meta-heuristics 93 3.1 Introduction 93 3.1.1 Impact on Controlling Parameters 95 3.2 Genetic Algorithm 96 3.2.1 Fundamental Principles and Features 97 3.2.2 Pseudo-code of Genetic Algorithm 98 3.2.3 Encoding Strategy and Creation of Population 99 3.2.4 Evaluation Technique 99 3.2.5 Genetic Operators 100 3.2.6 Selection mechanism 100 3.2.7 Crossover 102 3.2.8 Mutation 103 3.3 Particle Swarm Optimization 103 3.3.1 Pseudo-code of Particle Swarm Optimization 104 3.3.2 PSO: Velocity and Position Update 105 3.4 Ant Colony Optimization 107 3.4.1 Stigmergy in Ants: Biological Inspiration 107 3.4.2 Pseudo-code of Ant Colony Optimization 108 3.4.3 Pheromone Trails 109 3.4.4 Updating Pheromone trails 109 3.5 Differential Evolution 110 3.5.1 Pseudo-code of Differential Evolution 111 3.5.2 Basic Principles of DE 112 3.5.3 Mutation 112 3.5.4 Crossover 113 3.5.5 Selection 113 3.6 Simulated Annealing 114 3.6.1 Pseudo-code of Simulated annealing 114 3.6.2 Basics of Simulated Annealing 116 3.7 Tabu Search 117 3.7.1 Pseudo-code of Tabu Search 118 3.7.2 Memory Management in Tabu Search 119 3.7.3 Parameters used in Tabu Search 120 3.8 Conclusion 121 3.9 Summary 121 3.10 Exercise Questions 122 3.10.1 Multiple Choice Questions 122 3.10.2 Short Answer Type Questions 123 3.10.3 Long Answer Type Questions 124 4 Quantum Inspired Meta-heuristics for Bi-level Image Thresholding 125 4.1 Introduction 125 4.2 Quantum Inspired Genetic Algorithm 129 4.2.1 Initialize the Population of Qubit Encoded Chromosomes 130 4.2.2 Perform Quantum Interference 130 4.2.3 Find threshold value in Population and Evaluate Fitness 134 4.2.4 Apply Selection Mechanism to Generate New Population 135 4.2.5 Foundation of Quantum Crossover 135 4.2.6 Foundation of Quantum Mutation 136 4.2.7 Foundation of Quantum Shift 137 4.2.8 Complexity analysis 137 4.3 Quantum Inspired Particle Swarm Optimization 138 4.3.1 Complexity Analysis 139 4.4 Implementation Results 140 4.4.1 Experimental Results (Phase I)142 4.4.2 Experimental Results (Phase II) 151 4.4.3 Experimental Results (Phase III) 185 4.5 Comparative Analysis among the Participating Algorithms 189 4.6 Conclusion 193 4.7 Summary 194 4.8 Exercise Questions 194 4.8.1 Multiple Choice Questions 194 4.8.2 Short Answer Type Questions 196 4.8.3 Long Answer Type Questions 197 4.9 Coding Examples 197 5 Quantum Inspired Meta-heuristics for Gray Scale Multi-level Image Thresholding 199 5.1 Introduction 199 5.2 Quantum Inspired Genetic Algorithm 202 5.2.1 Population Generation 203 5.2.2 Quantum Orthogonality 203 5.2.3 Determination of threshold values in Population and Measurement of Fitness 5.2.4 Selection 206 5.2.5 Quantum Crossover 206 5.2.6 Quantum Mutation 206 5.2.7 Complexity Analysis 207 5.3 Quantum Inspired Particle Swarm Optimization 208 5.3.1 Complexity Analysis 209 5.4 Quantum Inspired Differential Evolution 210 5.4.1 Complexity Analysis 211 5.5 Quantum Inspired Ant Colony Optimization 213 5.5.1 Complexity Analysis 214 5.6 Quantum Inspired Simulated Annealing 215 5.6.1 Complexity Analysis 216 5.7 Quantum Inspired Tabu Search 218 5.7.1 Complexity Analysis 219 5.8 Implementation Results 220 5.8.1 Consensus Results of the Quantum Algorithms 224 5.9 Comparison of QIPSO with Other Existing Algorithms 245 5.10 Conclusion 252 5.11 Summary 253 5.12 Exercise Questions 254 5.12.1 Multiple Choice Questions 254 5.12.2 Short Answer Type Questions 256 5.12.3 Long Answer Type Questions 257 5.13 Coding Examples 257 6 Quantum Behaved Meta-Heuristics for True Colour Multi-level Image Thresholding 271 6.1 Introduction 271 6.2 Background 273 6.3 Quantum Inspired Ant Colony Optimization 274 6.3.1 Complexity Analysis 275 6.4 Quantum Inspired Differential Evolution 277 6.4.1 Complexity Analysis 279 6.5 Quantum Inspired Particle Swarm Optimization 279 6.5.1 Complexity Analysis 280 6.6 Quantum Inspired Genetic Algorithm 281 6.6.1 Complexity Analysis 282 6.7 Quantum Inspired Simulated Annealing 284 6.7.1 Complexity Analysis 285 6.8 Quantum Inspired Tabu Search 287 6.8.1 Complexity Analysis 288 6.9 Implementation Results 290 6.9.1 Experimental Results (Phase I) 293 6.9.2 The performance Evaluation of the Comparable Algorithms of Phase I 311 6.9.3 Experimental Results (Phase II) 319 6.9.4 The Performance Evaluation of the Participating Algorithms of Phase II 344 6.10 Conclusions 363 6.11 Summary 364 6.12 Exercise Questions 365 6.12.1 Multiple Choice Questions 365 6.12.2 Short Answer Type Questions 367 6.12.3 Long Answer Type Questions 367 6.13 Coding examples 368 7 Quantum Inspired Multi-objective Algorithms for Multi-level Image Thresholding 383 7.1 Introduction 383 7.2 Multi-objective Optimization 385 7.3 Experimental Methodology for Gray Scale Multi-level Image Thresholding 387 7.3.1 Quantum Inspired Non-dominated Sorting Based Multi-objective Genetic Algorithm 7.3.2 Complexity Analysis 390 7.3.3 Quantum Inspired Simulated Annealing for Multi-objective algorithms 391 7.3.4 Quantum Inspired Multi-objective Particle Swarm Optimization 395 7.3.5 Quantum Inspired Multi-objective Ant Colony Optimization 399 7.4 Implementation Results 401 7.4.1 Experimental Results 402 7.5 Conclusions 417 7.6 Summary 418 7.7 Exercise Questions 419 7.7.1 Multiple Choice Questions 419 7.7.2 Short Answer Type Questions 420 7.7.3 Long Answer Type Questions 421 7.8 Coding Examples 421 8 Conclusion 427 Bibliography 432 Index